1/****************************************************************************
2**
3** Copyright (C) 2014 Klaralvdalens Datakonsult AB (KDAB).
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the Qt3D module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include "sphere_p.h"
41
42#include <Qt3DRender/private/qray3d_p.h>
43
44#include <QPair>
45
46#include <math.h>
47#include <algorithm>
48
49QT_BEGIN_NAMESPACE
50
51namespace {
52
53// Algorithms taken from Real-time collision detection, p178-179
54
55// Intersects ray r = p + td, |d| = 1, with sphere s and, if intersecting,
56// returns true and intersection point q; false otherwise
57bool intersectRaySphere(const Qt3DRender::RayCasting::QRay3D &ray, const Qt3DRender::Render::Sphere &s, Vector3D *q = nullptr)
58{
59 if (s.isNull())
60 return false;
61
62 const Vector3D p = ray.origin();
63 const Vector3D d = ray.direction();
64 const Vector3D m = p - s.center();
65 const float c = Vector3D::dotProduct(a: m, b: m) - s.radius() * s.radius();
66
67 // If there is definitely at least one real root, there must be an intersection
68 if (q == nullptr && c <= 0.0f)
69 return true;
70
71 const float b = Vector3D::dotProduct(a: m, b: d);
72 // Exit if r’s origin outside s (c > 0) and r pointing away from s (b > 0)
73 if (c > 0.0f && b > 0.0f)
74 return false;
75
76 const float discr = b*b - c;
77 // A negative discriminant corresponds to ray missing sphere
78 if (discr < 0.0f)
79 return false;
80
81 // If we don't need the intersection point, return early
82 if (q == nullptr)
83 return true;
84
85 // Ray now found to intersect sphere, compute smallest t value of intersection
86 float t = -b - sqrt(x: discr);
87
88 // If t is negative, ray started inside sphere so clamp t to zero
89 if (t < 0.0f)
90 t = 0.0f;
91
92 *q = p + t * d;
93 return true;
94}
95
96inline void constructRitterSphere(Qt3DRender::Render::Sphere &s, const QVector<Vector3D> &points)
97{
98 //def bounding_sphere(points):
99 // dist = lambda a,b: ((a[0] - b[0])**2 + (a[1] - b[1])**2 + (a[2] - b[2])**2)**0.5
100 // x = points[0]
101 // y = max(points,key= lambda p: dist(p,x) )
102 // z = max(points,key= lambda p: dist(p,y) )
103 // bounding_sphere = (((y[0]+z[0])/2,(y[1]+z[1])/2,(y[2]+z[2])/2), dist(y,z)/2)
104 //
105 // exterior_points = [p for p in points if dist(p,bounding_sphere[0]) > bounding_sphere[1] ]
106 // while ( len(exterior_points) > 0 ):
107 // pt = exterior_points.pop()
108 // if (dist(pt, bounding_sphere[0]) > bounding_sphere[1]):
109 // bounding_sphere = (bounding_sphere[0],dist(pt,bounding_sphere[0]))
110 //
111 // return bounding_sphere
112
113 const Vector3D x = points[0];
114 const Vector3D y = *std::max_element(first: points.begin(), last: points.end(), comp: [&x](const Vector3D& lhs, const Vector3D& rhs){ return (lhs - x).lengthSquared() < (rhs - x).lengthSquared(); });
115 const Vector3D z = *std::max_element(first: points.begin(), last: points.end(), comp: [&y](const Vector3D& lhs, const Vector3D& rhs){ return (lhs - y).lengthSquared() < (rhs - y).lengthSquared(); });
116
117 const Vector3D center = (y + z) * 0.5f;
118 const Vector3D maxDistPt = *std::max_element(first: points.begin(), last: points.end(), comp: [&center](const Vector3D& lhs, const Vector3D& rhs){ return (lhs - center).lengthSquared() < (rhs - center).lengthSquared(); });
119 const float radius = (maxDistPt - center).length();
120
121 s.setCenter(center);
122 s.setRadius(radius);
123}
124
125} // anonymous namespace
126
127namespace Qt3DRender {
128
129namespace Render {
130
131const float Sphere::ms_epsilon = 1.0e-7f;
132
133Sphere Sphere::fromPoints(const QVector<Vector3D> &points)
134{
135 Sphere s;
136 s.initializeFromPoints(points);
137 return s;
138}
139
140void Sphere::initializeFromPoints(const QVector<Vector3D> &points)
141{
142 if (!points.isEmpty())
143 constructRitterSphere(s&: *this, points);
144}
145
146void Sphere::expandToContain(const Vector3D &p)
147{
148 if (isNull()) {
149 m_center = p;
150 m_radius = 0.0f;
151 return;
152 }
153
154 const Vector3D d = p - m_center;
155 const float dist2 = d.lengthSquared();
156
157 if (dist2 > m_radius * m_radius) {
158 // Expand radius so sphere also contains p
159 const float dist = sqrt(x: dist2);
160 const float newRadius = 0.5f * (m_radius + dist);
161 const float k = (newRadius - m_radius) / dist;
162 m_radius = newRadius;
163 m_center += k * d;
164 }
165}
166
167void Sphere::expandToContain(const Sphere &sphere)
168{
169 if (isNull()) {
170 *this = sphere;
171 return;
172 } else if (sphere.isNull()) {
173 return;
174 }
175
176 const Vector3D d(sphere.m_center - m_center);
177 const float dist2 = d.lengthSquared();
178
179 const float dr = sphere.m_radius - m_radius;
180 if (dr * dr >= dist2) {
181 // Larger sphere encloses the smaller. Set our size to the larger
182 if (m_radius > sphere.m_radius)
183 return;
184 else
185 *this = sphere;
186 } else {
187 // The spheres are overlapping or disjoint
188 const float dist = sqrt(x: dist2);
189 const float newRadius = 0.5f * (dist + m_radius + sphere.m_radius);
190 if (dist > ms_epsilon)
191 m_center += d * (newRadius - m_radius) / dist;
192 m_radius = newRadius;
193 }
194}
195
196Sphere Sphere::transformed(const Matrix4x4 &mat) const
197{
198 if (isNull())
199 return *this;
200
201 // Transform extremities in x, y, and z directions to find extremities
202 // of the resulting ellipsoid
203 Vector3D x = mat.map(point: m_center + Vector3D(m_radius, 0.0f, 0.0f));
204 Vector3D y = mat.map(point: m_center + Vector3D(0.0f, m_radius, 0.0f));
205 Vector3D z = mat.map(point: m_center + Vector3D(0.0f, 0.0f, m_radius));
206
207 // Transform center and find maximum radius of ellipsoid
208 Vector3D c = mat.map(point: m_center);
209 float rSquared = qMax(a: qMax(a: (x - c).lengthSquared(), b: (y - c).lengthSquared()), b: (z - c).lengthSquared());
210 return Sphere(c, sqrt(x: rSquared), id());
211}
212
213Qt3DCore::QNodeId Sphere::id() const
214{
215 return m_id;
216}
217
218bool Sphere::intersects(const RayCasting::QRay3D &ray, Vector3D *q, Vector3D *uvw) const
219{
220 Q_UNUSED(uvw);
221 return intersectRaySphere(ray, s: *this, q);
222}
223
224Sphere::Type Sphere::type() const
225{
226 return RayCasting::QBoundingVolume::Sphere;
227}
228
229#ifndef QT_NO_DEBUG_STREAM
230
231QDebug operator<<(QDebug dbg, const Sphere &sphere)
232{
233 QDebugStateSaver saver(dbg);
234 dbg.nospace() << "Sphere(center("
235 << sphere.center().x() << ", " << sphere.center().y() << ", "
236 << sphere.center().z() << ") - radius(" << sphere.radius() << "))";
237 return dbg;
238}
239
240#endif
241
242} // Render
243
244} // Qt3DRender
245
246QT_END_NAMESPACE
247

source code of qt3d/src/render/frontend/sphere.cpp