Sphere.h

1 /* Copyright Jukka Jyl�nki
2
3 Licensed under the Apache License, Version 2.0 (the "License");
4 you may not use this file except in compliance with the License.
5 You may obtain a copy of the License at
6
7 http://www.apache.org/licenses/LICENSE-2.0
8
9 Unless required by applicable law or agreed to in writing, software
10 distributed under the License is distributed on an "AS IS" BASIS,
11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 See the License for the specific language governing permissions and
13 limitations under the License. */
14
15 /** @file Sphere.h
16 @author Jukka Jyl�nki
17 @brief The Sphere geometry object. */
18 #pragma once
19
20 #include "../MathGeoLibFwd.h"
21 #include "../Math/float3.h"
22
23 #ifdef MATH_URHO3D_INTEROP
24 #include <Urho3D/Math/Sphere.h>
25 #endif
26
27 MATH_BEGIN_NAMESPACE
28
29 /// A 3D sphere.
30 class Sphere
31 {
32 public:
33 /// The center point of this sphere.
34 vec pos;
35 /// The radius of this sphere.
36 /** [similarOverload: pos] */
37 float r;
38
39 /// The default constructor does not initialize any members of this class.
40 /** This means that the values of the members pos and r are undefined after creating a new Sphere using this
41 default constructor. Remember to assign to them before use.
42 @see pos, r. */
43 Sphere() {}
44
45 /// Constructs a sphere with a given position and radius.
46 /** @param radius A value > 0 constructs a sphere with positive volume. A value of <= 0 is valid, and constructs a degenerate sphere.
47 @see pos, r, IsFinite(), IsDegenerate() */
48 Sphere(const vec &center, float radius);
49
50 /// Constructs a sphere that passes through the given two points.
51 /** The constructed sphere will be the minimal sphere that encloses the given two points. The center point of this
52 sphere will lie midway between pointA and pointB, and the radius will be half the distance between pointA and
53 pointB. Both input points are assumed to be finite. */
54 Sphere(const vec &pointA, const vec &pointB);
55
56 /// Constructs a sphere that passes through the given three points.
57 /** @note The resulting sphere may not be the minimal enclosing sphere for the three points! */
58 Sphere(const vec &pointA, const vec &pointB, const vec &pointC);
59
60 /// Constructs a sphere that passes through the given four points.
61 /** @note The resulting sphere may not be the minimal enclosing sphere for the four points! */
62 Sphere(const vec &pointA, const vec &pointB, const vec &pointC, const vec &pointD);
63
64 /// Translates this Sphere in world space.
65 /** @param offset The amount of displacement to apply to this Sphere, in world space coordinates.
66 @see Transform(). */
67 void Translate(const vec &offset);
68
69 /// Applies a transformation to this Sphere, in-place.
70 /** See Translate(), classes float3x3, float3x4, float4x4, Quat. */
71 void Transform(const float3x3 &transform);
72 void Transform(const float3x4 &transform);
73 void Transform(const float4x4 &transform);
74 void Transform(const Quat &transform);
75
76 /// Returns the smallest AABB that encloses this sphere.
77 /** The returned AABB is a cube, with a center position coincident with this sphere, and a side length of 2*r.
78 @see MaximalContainedAABB(). */
79 AABB MinimalEnclosingAABB() const;
80
81 /// Returns the largest AABB that fits inside this sphere.
82 /** The returned AABB is a cube, with a center position coincident with this sphere, and a side length of 2*r/Sqrt(3).
83 @see MinimalEnclosingAABB(). */
84 AABB MaximalContainedAABB() const;
85
86 /// Sets pos = (0,0,0) and r = -inf.
87 /** After a call to this function, both IsFinite() and IsDegenerate() will return true.
88 @see IsFinite(), IsDegenerate(). */
89 void SetNegativeInfinity();
90
91 /// Computes the volume of this sphere.
92 /// @return 4*pi*r^3/3.
93 /// @see SurfaceArea(), Diameter().
94 float Volume() const;
95
96 /// Computes the surface area of this sphere.
97 /// @return 4*pi*r^2.
98 /// @see Volume(), Diameter().
99 float SurfaceArea() const;
100
101 /// Computes the diameter of this sphere.
102 /// @return 2*r.
103 /// @see r, SurfaceArea(), Volume().
104 float Diameter() const { return 2.f * r; }
105
106 /// Returns the center of mass of this sphere.
107 /** @return pos.
108 @see pos */
109 vec Centroid() const { return pos; }
110
111 /// Quickly returns an arbitrary point inside this Sphere. Used in GJK intersection test.
112 vec AnyPointFast() const { return pos; }
113
114 /// Computes the extreme point of this Sphere in the given direction.
115 /** An extreme point is a farthest point of this Sphere in the given direction. For
116 a Sphere, this point is unique.
117 @param direction The direction vector of the direction to find the extreme point. This vector may
118 be unnormalized, but may not be null.
119 @return The extreme point of this Sphere in the given direction. */
120 vec ExtremePoint(const vec &direction) const;
121 vec ExtremePoint(const vec &direction, float &projectionDistance) const;
122
123 /// Projects this Sphere onto the given 1D axis direction vector.
124 /** This function collapses this Sphere onto an 1D axis for the purposes of e.g. separate axis test computations.
125 The function returns a 1D range [outMin, outMax] denoting the interval of the projection.
126 @param direction The 1D axis to project to. This vector may be unnormalized, in which case the output
127 of this function gets scaled by the length of this vector.
128 @param outMin [out] Returns the minimum extent of this object along the projection axis.
129 @param outMax [out] Returns the maximum extent of this object along the projection axis. */
130 void ProjectToAxis(const vec &direction, float &outMin, float &outMax) const;
131
132 /// Tests if this Sphere is finite.
133 /** A sphere is finite if its members pos and r do not contain floating-point NaNs or +/-infs
134 in them.
135 @return True if the members pos and r both have finite floating-point values.
136 @see pos, r, IsDegenerate(), ::IsFinite(), IsInf(), IsNan(), IsFinite(), inf, negInf, nan, float3::nan, float3::inf, SetNegativeInfinity(). */
137 bool IsFinite() const;
138
139 /// Returns true if this Sphere is degenerate.
140 /** A sphere is degenerate if it is not finite, or if the radius of the sphere is less or equal to 0.
141 @see pos, r, IsFinite(), SetNegativeInfinity(). */
142 bool IsDegenerate() const;
143
144 /// Resets the members of this Sphere to NaN values.
145 /** After calling this function, pos = NaN and r = NaN for this sphere. */
146 void SetDegenerate();
147
148 /// Tests if the given object is fully contained inside this sphere.
149 /** @see Distance(), Intersects(), ClosestPoint().
150 @todo Add Sphere::Contains(Circle/Disc). */
151 bool Contains(const vec &point) const;
152 bool Contains(const vec &point, float epsilon) const;
153 bool Contains(const LineSegment &lineSegment) const;
154 bool Contains(const Triangle &triangle) const;
155 bool Contains(const Polygon &polygon) const;
156 bool Contains(const AABB &aabb) const;
157 bool Contains(const OBB &obb) const;
158 bool Contains(const Frustum &frustum) const;
159 bool Contains(const Polyhedron &polyhedron) const;
160 bool Contains(const Sphere &sphere) const;
161 bool Contains(const Sphere &sphere, float epsilon) const;
162 bool Contains(const Capsule &capsule) const;
163
164 /// Computes a Sphere that bounds the given point array.
165 /** This functions implements a fast approximate (though rather crude) algorithm of Jack Ritter.
166 See "An Efficient Bounding Sphere", in Graphics Gems 1, pp. 301-303,
167 or Christer Ericson's Real-time Collision Detection, pp. 89-91.
168 This algorithm performs two linear passes over the data set, i.e. it has a time complexity of O(n).
169 @param pointArray An array of points to compute an enclosing sphere for. This pointer must not be null.
170 @param numPoints The number of elements in the input array pointArray.
171 @see OptimalEnclosingSphere(). */
172 static Sphere FastEnclosingSphere(const vec *pointArray, int numPoints);
173
174 /// Computes the minimal bounding sphere for the given point array.
175 /** This function implements Emo Welzl's optimal enclosing sphere algorithm.
176 See "Smallest enclosing disks (balls and ellipsoids)", Lecture Notes in Computer Science 555 (1991) pp. 359-370.
177 The running time is expected linear time, but compared to Ritter's algorithm (the FastEnclosingSphere() function),
178 this algorithm is considerably slower.
179 The implementation of this function is based on the book Geometric Tools for Computer Graphics, pp. 807-813, by
180 Schneider and Eberly.
181 @param pointArray An array of points to compute an enclosing sphere for. This pointer must not be null.
182 @param numPoints The number of elements in the input array pointArray.
183 @see FastEnclosingSphere(). */
184 static Sphere OptimalEnclosingSphere(const vec *pointArray, int numPoints);
185
186 /// Computes the minimal bounding sphere for two points.
187 /** This function computes the smallest volume sphere that contains the given two points. For two points,
188 the OptimalEnclosingSphere(a, b) is the same as calling FitThroughPoints(a, b).
189 @see FitThroughPoints(). */
190 static Sphere OptimalEnclosingSphere(const vec &a, const vec &b);
191
192 /// Computes the minimal bounding sphere for three points.
193 /** This function computes the smallest volume sphere that contains the given three points. The smallest
194 enclosing sphere may not pass through all the three points that are specified. */
195 static Sphere OptimalEnclosingSphere(const vec &a, const vec &b, const vec &c);
196
197 /// Computes the minimal bounding sphere for four points.
198 /** This function computes the smallest volume sphere that contains the given four points. The smallest
199 enclosing sphere may not pass through all the four points that are specified. */
200 static Sphere OptimalEnclosingSphere(const vec &a, const vec &b, const vec &c, const vec &d);
201
202 /// Computes the minimal bounding sphere for four points.
203 /** This function computes the smallest volume sphere that contains the given five points.
204 @param redundantPoint [out] Since a sphere is characterized by four points, one of the given points
205 will necessarily be redundant and not part of the support set of the minimal enclosing sphere. This
206 parameter will receive the index [0, 4] of the five input points denoting which point became redundant.
207 (Note that there may be more than one point not lying on the support set of the sphere, but this function
208 only returns one)
209 @return The smallest volume sphere that encloses the given five points. */
210 static Sphere OptimalEnclosingSphere(const vec &a, const vec &b, const vec &c, const vec &d, const vec &e,
211 int &redundantPoint);
212
213 /// Fits a sphere through the given two points.
214 /** Two points do not uniquely define a sphere in 3D space. This function computes the minimal enclosing
215 sphere for the given two points, which is uniquely defined. This function is identical to
216 OptimalEnclosingSphere(a, b) and is simply an alias for that function.
217 @see OptimalEnclosingSphere(). */
218 static Sphere FitThroughPoints(const vec &a, const vec &b) { return OptimalEnclosingSphere(a, b); }
219
220 /// Fits a sphere through the given three points.
221 /** Three points do not uniquely define a sphere in 3D space. This function computes the sphere that goes
222 through these three points and has the minimal volume. Note that this is not the same than the smallest
223 sphere that encloses three given points, since the smallest enclosing sphere does not necessarily pass
224 through all the three points.
225 @note The three points that are passed in must not be collinear, because in that case a sphere cannot
226 be fitted through these points.
227 @see OptimalEnclosingSphere(). */
228 static Sphere FitThroughPoints(const vec &a, const vec &b, const vec &c);
229
230 /// Fits a sphere through the given four points.
231 /** Four points uniquely define a sphere in 3D space. This function computes the sphere that passes through
232 these four points. Note that this is not the same than the smallest enclosing sphere for the four points,
233 since the smallest enclosing sphere does not necessarily need to pass through all of these four points.
234 @note The four points that are passed in must not be coplanar, because in that case a sphere cannot
235 be fitted through these points.
236 @see OptimalEnclosingSphere(). */
237 static Sphere FitThroughPoints(const vec &a, const vec &b, const vec &c, const vec &d);
238
239 /// Returns the distance between this sphere and the given object.
240 /** This function finds the nearest pair of points on this and the given object, and computes their distance.
241 If the two objects intersect, or one object is contained inside the other, the returned distance is zero.
242 @see Contains(), Intersects(), ClosestPoint().
243 @todo Add Sphere::Distance(Polygon/Circle/Disc/Frustum/Polyhedron). */
244 float Distance(const vec &point) const;
245 float Distance(const Sphere &sphere) const;
246 float Distance(const Capsule &capsule) const;
247 float Distance(const AABB &aabb) const;
248 float Distance(const OBB &obb) const;
249 float Distance(const Plane &plane) const;
250 float Distance(const Triangle &triangle) const;
251 float Distance(const Ray &ray) const;
252 float Distance(const Line &line) const;
253 float Distance(const LineSegment &lineSegment) const;
254
255 /// Returns the maximal distance of this sphere to the given point.
256 /** The maximal distance is the distance of the farthest point inside this sphere to the target point. */
257 float MaxDistance(const vec &point) const;
258
259 /// Computes the closest point on this sphere to the given object.
260 /** If the other object intersects this sphere, this function will return an arbitrary point inside
261 the region of intersection.
262 @see Contains(), Distance(), Intersects().
263 @todo Add Sphere::ClosestPoint(Line/Ray/LineSegment/Plane/Triangle/Polygon/Circle/Disc/AABB/OBB/Sphere/Capsule/Frustum/Polyhedron). */
264 vec ClosestPoint(const vec &point) const;
265
266 /// Tests whether this sphere and the given object intersect.
267 /** Both objects are treated as "solid", meaning that if one of the objects is fully contained inside
268 another, this function still returns true. (e.g. in case a line segment is contained inside this sphere,
269 or this sphere is contained inside a polyhedron, etc.)
270 @param intersectionPoint [out] If specified, receives the actual point of intersection. This pointer may be null.
271 @param intersectionNormal [out] If specified, receives the sphere normal at the point of intersection. This pointer may be null.
272 @param d [out] If specified, receives the distance along the Line/LineSegment/Ray to the intersection. This pointer may be null.
273 @return In the case of Ray/Line/LineSegment intersection tests, the number of intersections is returned (0, 1 or 2).
274 For other functions, true is returned if an intersection occurs or one of the objects is contained inside the other, and false otherwise.
275 @see Contains(), Distance(), ClosestPoint(), LineSegment::GetPoint(). */
276 int Intersects(const LineSegment &lineSegment, vec *intersectionPoint = 0, vec *intersectionNormal = 0, float *d = 0, float *d2 = 0) const;
277 int Intersects(const Line &line, vec *intersectionPoint = 0, vec *intersectionNormal = 0, float *d = 0, float *d2 = 0) const;
278 int Intersects(const Ray &ray, vec *intersectionPoint = 0, vec *intersectionNormal = 0, float *d = 0, float *d2 = 0) const;
279 bool Intersects(const Plane &plane) const;
280 bool Intersects(const AABB &aabb, vec *closestPointOnAABB = 0) const;
281 bool Intersects(const OBB &obb, vec *closestPointOnOBB = 0) const;
282 bool Intersects(const Triangle &triangle, vec *closestPointOnTriangle = 0) const;
283 bool Intersects(const Capsule &capsule) const;
284 bool Intersects(const Polygon &polygon) const;
285 bool Intersects(const Frustum &frustum) const;
286 bool Intersects(const Polyhedron &polyhedron) const;
287 bool Intersects(const Sphere &sphere) const;
288
289 /// Expands this sphere to enclose both the original sphere and the given object.
290 /** This function may adjust both the position and the radius of this sphere to produce a new sphere that encloses
291 both objects. The sphere that results may not be the optimal enclosing sphere.
292 This function operates in-place.
293 @param epsilon An extra distance-squared parameter for the amount to overgrow the Sphere to encompass the given point.
294 This can be set to zero, but it may cause that Sphere::Contains(point) may return false.
295 @note This function will not produce the optimal enclosure.
296 @see FastEnclosingSphere(), OptimalEnclosingSphere(). */
297 void Enclose(const vec &point, float epsilon = 1e-4f);
298 void Enclose(const vec *pointArray, int numPoints);
299 void Enclose(const LineSegment &lineSegment);
300 void Enclose(const AABB &aabb);
301 void Enclose(const OBB &obb);
302 void Enclose(const Sphere &sphere);
303 void Enclose(const Triangle &triangle);
304 void Enclose(const Polygon &polygon);
305 void Enclose(const Polyhedron &polyhedron);
306 void Enclose(const Frustum &frustum);
307 void Enclose(const Capsule &capsule);
308
309 /// Expands the radius of this Sphere until it encloses the given object.
310 /** @param epsilon A small amount to extrude the given object by for numerical precision.
311 @note This function is like Enclose(), but unlike Enclose(), this function keeps the center point of this Sphere fixed. */
312 void ExtendRadiusToContain(const vec &point, float epsilon = 1e-4f);
313 void ExtendRadiusToContain(const Sphere &sphere, float epsilon = 1e-4f);
314
315 /// Generates a random point inside this sphere.
316 /** The points are distributed uniformly.
317 This function uses the rejection method to generate a uniform distribution of points inside a sphere. Therefore
318 it is assumed that this sphere is not degenerate, i.e. it has a positive radius.
319 A fixed number of 1000 tries is performed, after which the sphere center position is returned as a fallback.
320 @param lcg A pre-seeded random number generator object that is to be used by this function to generate random values.
321 @see class LCG, RandomPointOnSurface(), IsDegenerate().
322 @todo Add Sphere::Point(polarYaw, polarPitch, radius). */
323 vec RandomPointInside(LCG &lcg);
324 static vec RandomPointInside(LCG &lcg, const vec &center, float radius);
325 /// Generates a random point on the surface of this sphere.
326 /** The points are distributed uniformly.
327 This function uses the rejection method to generate a uniform distribution of points on the surface. Therefore
328 it is assumed that this sphere is not degenerate, i.e. it has a positive radius.
329 A fixed number of 1000 tries is performed, after which a fixed point on the surface is returned as a fallback.
330 @param lcg A pre-seeded random number generator object that is to be used by this function to generate random values.
331 @see class LCG, RandomPointInside(), IsDegenerate().
332 @todo Add Sphere::PointOnSurface(polarYaw, polarPitch). */
333 vec RandomPointOnSurface(LCG &lcg);
334 static vec RandomPointOnSurface(LCG &lcg, const vec &center, float radius);
335
336 /// Returns a random normalized direction vector.
337 /** @param lcg A pre-seeded random number generator object that is to be used by this function to generate random values. */
338 static vec RandomUnitaryFloat3(LCG &lcg) { return Sphere(POINT_VEC(0,0,0), 1.f).RandomPointOnSurface(lcg); }
339
340 /// Produces a geosphere-triangulation of this sphere.
341 /** @param outPos [out] An array of size numVertices which will receive a triangle list of vertex positions. Cannot be null.
342 @param outNormal [out] An array of size numVertices which will receive vertex normals. If this parameter is null, vertex normals are not generated.
343 @param outUV [out] An array of size numVertices which will receive UV coordinates. If this parameter is null, UV coordinates are not generated.
344 @param numVertices The size of the input arrays outPos and outNormal. This value should be of form 24*4^n for some n >= 0. (24, 96, 384, 1536, 6144, 24576, ...)
345 @return The actual number of vertices generated (== the number of elements written to outPos and outNormal). */
346 int Triangulate(vec *outPos, vec *outNormal, float2 *outUV, int numVertices, bool ccwIsFrontFacing) const;
347
348 /// Computes the intersection of a line and a sphere.
349 /** This function solves the points of intersection between a line and a sphere.
350 A line intersects sphere at 0, 1 or 2 points. When only one point of intersection is reported,
351 the given line is tangent to the sphere.
352 @param linePos The source position of the line.
353 @param lineDir The direction of the line. This vector must be normalized in advance.
354 @param sphereCenter The center position of the sphere to test.
355 @param sphereRadius The radius of the sphere, which must be >= 0.
356 @param t1 [out] This parameter receives the parametric distance along the line to the first point of intersection.
357 If the sphere and the line do not intersect, this variable is not written to. To receive the actual
358 world space point corresponding to this point of intersection, compute the vector 'linePos + t1 * lineDir'.
359 @param t2 [out] This parameter receives the parametric distance along the line to the second point of intersection.
360 If the sphere and the line do not intersect, this variable is not written to. If the line is tangent to this
361 sphere (one point of intersection), this variable will be set equal to t1, so that the line segment
362 [t1, t2] always forms a line segment completely enclosed inside the sphere. To receive the actual world space
363 point corresponding to this point of intersection, compute the vector 'linePos + t2 * lineDir'.
364 @return The number of intersection points: 0, 1 or 2. In case of 0, the line and sphere do not intersect. In
365 case of 1, the line is tangent to the sphere. If the value of 2 is returned, the line properly intersects the
366 sphere.
367 @note The outputted variables t1 and t2 always satisfy t1 < t2. This allows distinguishing between the "enter"
368 and "exit" positions of the line, if the line is interpreted more like a ray starting at linePos, and extending
369 towards lineDir. */
370 static int IntersectLine(const vec &linePos, const vec &lineDir, const vec &sphereCenter,
371 float sphereRadius, float &t1, float &t2);
372
373 #ifdef MATH_ENABLE_STL_SUPPORT
374 /// Returns a human-readable representation of this Sphere. Most useful for debugging purposes.
375 std::string ToString() const;
376 std::string SerializeToString() const;
377
378 /// Returns a string of C++ code that can be used to construct this object. Useful for generating test cases from badly behaving objects.
379 std::string SerializeToCodeString() const;
380 #endif
381
382 static Sphere FromString(const char *str, const char **outEndStr = 0);
383 #ifdef MATH_ENABLE_STL_SUPPORT
384 static Sphere FromString(const std::string &str) { return FromString(str.c_str()); }
385 #endif
386
387 #ifdef MATH_QT_INTEROP
388 operator QString() const { return toString(); }
389 QString toString() const { return QString::fromStdString(ToString()); }
390 #endif
391 #ifdef MATH_GRAPHICSENGINE_INTEROP
392 void Triangulate(VertexBuffer &vb, int numVertices, bool ccwIsFrontFacing) const;
393 #endif
394 #ifdef MATH_URHO3D_INTEROP
395 Sphere(const Urho3D::Sphere &other) : pos(other.center_), r(other.radius_) {}
396 operator Urho3D::Sphere() const { return Urho3D::Sphere(pos, r); }
397 #endif
398
399 bool Equals(const Sphere &rhs, float epsilon = 1e-3f) const { return pos.Equals(rhs.pos, epsilon) && EqualAbs(r, rhs.r, epsilon); }
400
401 /// Compares whether this Sphere and the given Sphere are identical bit-by-bit in the underlying representation.
402 /** @note Prefer using this over e.g. memcmp, since there can be SSE-related padding in the structures. */
403 bool BitEquals(const Sphere &other) const;
404 };
405
406 #ifdef MATH_QT_INTEROP
407 Q_DECLARE_METATYPE(Sphere)
408 Q_DECLARE_METATYPE(Sphere*)
409 #endif
410
411 Sphere operator *(const float3x3 &m, const Sphere &s);
412 Sphere operator *(const float3x4 &m, const Sphere &s);
413 Sphere operator *(const float4x4 &m, const Sphere &s);
414 Sphere operator *(const Quat &q, const Sphere &s);
415
416 #ifdef MATH_ENABLE_STL_SUPPORT
417 std::ostream &operator <<(std::ostream &o, const Sphere &sphere);
418 #endif
419
420 MATH_END_NAMESPACE