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 Plane.h
16         @author Jukka Jyl�nki
17         @brief The Plane geometry object. */
18 #pragma once
19
20 #include "../MathGeoLibFwd.h"
21 #include "../Math/float3.h"
22
23 #ifdef MATH_OGRE_INTEROP
24 #include <OgrePlane.h>
25 #endif
26 #ifdef MATH_URHO3D_INTEROP
27 #include <Urho3D/Math/Plane.h>
28 #endif
29
30 MATH_BEGIN_NAMESPACE
31
32 /// Specifies a plane in 3D space. This plane is an affine 2D subspace of the 3D space, meaning
33 /// that its sides extend to infinity, and it does not necessarily pass through the origin.
34 class Plane
35 {
36 public:
37         /// The direction this plane is facing at.
38         /** This direction vector is always normalized. If you assign to this directly, please remember to only
39                 assign normalized direction vectors. */
40         vec normal;
41         /// The offset of this plane from the origin. [similarOverload: normal]
42         /** The value -d gives the signed distance of this plane from origin.
43                 Denoting normal:=(a,b,c), this class uses the convention ax+by+cz = d, which means that:
44                  - If this variable is positive, the vector space origin (0,0,0) is on the negative side of this plane.
45                  - If this variable is negative, the vector space origin (0,0,0) is on the on the positive side of this plane.
46                 @note Some sources use the opposite convention ax+by+cz+d = 0 to define the variable d. When comparing equations
47                         and algorithm regarding planes, always make sure you know which convention is being used, since it affects the
48                         sign of d. */
49         float d;
50
51         /// The default constructor does not initialize any members of this class.
52         /** This means that the values of the members normal and d are undefined after creating a new Plane using this
53                 default constructor. Remember to assign to them before use.
54                 @see normal, d. */
55         Plane() {}
56         /// Constructs a plane by directly specifying the normal and distance parameters.
57         /** @param normal The direction the plane is facing. This vector must have been normalized in advance.
58                 @param d The offset of this plane from the origin. The value -d gives the signed distance of this plane from the origin.
59                 @see normal, d. */
60         Plane(const vec &normal, float d);
61         /// Constructs a plane by specifying three points on the plane.
62         /** The normal of the plane will point to
63                 the halfspace from which the points are observed to be oriented in counter-clockwise order.
64                 @note The points v1, v2 and v3 must not all lie on the same line.
65                 @see Set(). */
66         Plane(const vec &v1, const vec &v2, const vec &v3);
67         /// Constructs a plane by specifying a single point on the plane, and the surface normal.
68         /** @param normal The direction the plane is facing. This vector must have been normalized in advance.
69                 @see Set(). */
70         Plane(const vec &point, const vec &normal);
71         /// Constructs a plane by specifying a line that lies on the plane, and the plane normal.
72         /** @param line The line object that is to be contained in the newly constructed plane.
73                 @param normal The direction the plane if facing. This vector must have been normalized in advance. The normal
74                         of the line must not be collinear with the direction of this normal. If a line segment is specified, the line
75                         segment must not be degenerate. */
76         Plane(const Ray &line, const vec &normal);
77         Plane(const Line &line, const vec &normal);
78         Plane(const LineSegment &line, const vec &normal);
79
80         bool IsDegenerate() const;
81
82         /// Sets this plane by specifying three points on the plane.
83         /** The normal of the plane will point to the halfspace from which the points are observed to be oriented in
84                 counter-clockwise order.
85                 @note The points v1, v2 and v3 must not all lie on the same line. */
86         void Set(const vec &v1, const vec &v2, const vec &v3);
87         /// Sets this plane by specifying a single point on the plane, and the surface normal.
88         /** @param normal The direction the plane is facing. This vector must have been normalized in advance. */
89         void Set(const vec &point, const vec &normal);
90
91         /// Reverses the direction of the plane normal, while still representing the same set of points.
92         /** This function sets normal = -normal and d = -d for this plane.
93                 @see normal, d. */
94         void ReverseNormal();
95
96         /// Returns a point on this plane.
97         /** @note This point has the special property that the line passing through the vector space origin (0,0,0)
98                         and the returned point is perpendicular to this plane (directed towards the normal vector of this plane).
99                 @see Point(). */
100         vec PointOnPlane() const;
101
102         /// Returns a point on this plane, parameterized at the given coordinates.
103         /** The basis directions for U and V are arbitrarily (but consistently) defined.
104                 Calling Point(0,0) is the same as calling PointOnPlane().
105                 @see PointOnPlane(). */
106         vec Point(float u, float v) const;
107
108         /// Returns a point on this plane, parameterized at the given coordinates.
109         /** The basis directions for U and V are arbitrarily (but consistently) defined.
110                 @param referenceOrigin A point that defines an origin for the returned points. This point does not have to lie
111                         on this plane.
112                 Calling Point(0, 0, referenceOrigin) returns the point referenceOrigin projected onto this plane.
113                 Calling Point(u, v) is the same as calling Point(u, v, PointOnPlane()).
114                 @see PointOnPlane(). */
115         vec Point(float u, float v, const vec &referenceOrigin) const;
116
117         /// Translates this Plane in world space.
118         /** @param offset The amount of displacement to apply to this Plane, in world space coordinates.
119                 @see Transform(). */
120         void Translate(const vec &offset);
121
122         /// Applies a transformation to this plane.
123         /** This function operates in-place.
124                 @see Translate(), classes float3x3, float3x4, float4x4, Quat. */
125         void Transform(const float3x3 &transform);
126         void Transform(const float3x4 &transform);
127         void Transform(const float4x4 &transform);
128         void Transform(const Quat &transform);
129
130         /// Tests if the given direction vector points towards the positive side of this plane.
131         /** @param directionVector The direction vector to compare with the normal of this plane. This vector
132                 may be unnormalized.
133                 @see IsOnPositiveSide. */
134         bool IsInPositiveDirection(const vec &directionVector) const;
135
136         /// Tests if the given point lies on the positive side of this plane.
137         /** A plane divides the space in three sets: the negative halfspace, the plane itself, and the positive halfspace.
138                 The normal vector of the plane points towards the positive halfspace.
139                 @return This function returns true if the given point lies either on this plane itself, or in the positive
140                         halfspace of this plane.
141                 @see IsInPositiveDirection, AreOnSameSide(), Distance(), SignedDistance(). */
142         bool IsOnPositiveSide(const vec &point) const;
143
144         /// Performs a Triangle-Plane intersection test.
145         /** @return This function returns the value 1 if the whole triangle is on the positive side of this plane, the
146                         value -1 if the whole triangle lies in the negative side of this plane, and 0 if the triangle intersects this plane.
147                 @see Intersects(), AreOnSameSide(), Distance(), SignedDistance(), Contains(). */
148         int ExamineSide(const Triangle &triangle) const;
149
150         /// Tests if two points are on the same side of this plane.
151         /** @return This function returns true if both p1 and p2 are on the positive side or this plane, or if both p1 and p2
152                         are on the negative side of this plane.
153                 @see IsOnPositiveSide(), Distance(), SignedDistance(). */
154         bool AreOnSameSide(const vec &p1, const vec &p2) const;
155
156         /// Returns the distance of this plane to the given object.
157         /** If the given object intersects or lies in this plane, then the returned distance is zero.
158                 @note This function always returns a positive distance value, even when the given object lies on the negative side
159                         of this plane. See the SignedDistance() function to produce a distance value that differentiates between the
160                         front and back sides of this plane.
161                 @see SignedDistance(), Intersects(), Contains(). */
162         float Distance(const float3 &point) const;
163         float Distance(const float4 &point) const;
164         float Distance(const LineSegment &lineSegment) const;
165         float Distance(const Sphere &sphere) const;
166         float Distance(const Capsule &capsule) const;
167
168         /// Returns the signed distance of this plane to the given point.
169         /** If this function returns a negative value, the given point lies in the negative halfspace of this plane.
170                 Conversely, if a positive value is returned, then the given point lies in the positive halfspace of this plane.
171                 @see Distance(), IsOnPositiveSide(), AreOnSameSide(). */
172         float SignedDistance(const vec &point) const;
173
174         float SignedDistance(const AABB &aabb) const;
175         float SignedDistance(const OBB &obb) const;
176         float SignedDistance(const Capsule &capsule) const;
177 //      float SignedDistance(const Circle &circle) const;
178         float SignedDistance(const Frustum &frustum) const;
179         float SignedDistance(const Line &line) const;
180         float SignedDistance(const LineSegment &lineSegment) const;
181         float SignedDistance(const Ray &ray) const;
182 //      float SignedDistance(const Plane &plane) const;
183         float SignedDistance(const Polygon &polygon) const;
184         float SignedDistance(const Polyhedron &polyhedron) const;
185         float SignedDistance(const Sphere &sphere) const;
186         float SignedDistance(const Triangle &triangle) const;
187
188         /// Computes the affine transformation matrix that projects orthographically onto this plane.
189         /** @see ObliqueProjection(), MirrorMatrix(), Project(). */
190         float3x4 OrthoProjection() const;
191
192         /// Projects the given object onto this plane orthographically.
193         /** @note This mapping can be expressed as a float3x4 matrix operation. See the OrthoProjection() function.
194                 @see OrthoProjection(), ProjectToPositiveHalf(), ProjectToNegativeHalf(). */
195         vec Project(const vec &point) const;
196         LineSegment Project(const LineSegment &lineSegment) const;
197         /** @param nonDegenerate [out] If the line or ray is perpendicular to the plane, the projection is
198                 a single point. In that case, the .pos parameter of the returned object will specify the point
199                 location, the .dir parameter of the object will be undefined and the nonDegenerate pointer will be
200                 set to false. This pointer may be null. */
201         Line Project(const Line &line, bool *nonDegenerate) const;
202         Ray Project(const Ray &ray, bool *nonDegenerate) const;
203
204         Triangle Project(const Triangle &triangle) const;
205         Polygon Project(const Polygon &polygon) const;
206
207         /// Projects the given point to the negative half-space of this plane.
208         /** This means that if the point lies on the plane, or in the negative half-space, the same point is 
209                 returned unchanged. If the point lies on the positive half-space, it is projected orthographically onto the plane.
210                 @see ProjectToPositiveHalf(), Project() */
211         vec ProjectToNegativeHalf(const vec &point) const;
212
213         /// Projects the given point to the positivehalf-space of this plane.
214         /** @see ProjectToNegativeHalf(), Project() */
215         vec ProjectToPositiveHalf(const vec &point) const;
216
217 #if 0
218         /// Computes the affine transformation matrix that projects onto this plane in an oblique (slanted) angle.
219         /** @param obliqueProjectionDir The projection direction. This vector must be normalized. If a vector collinear to the
220                         normal of this plane is specified, this function returns the same matrix as calling OrthoProjection() would.
221                 @see OrthoProjection(), MirrorMatrix(), ObliqueProject(). */
222         float3x4 ObliqueProjection(const float3 &obliqueProjectionDir) const;
223
224         /// Projects the given point onto this plane in the given oblique projection direction.
225         /** @param obliqueProjectionDir The projection direction. This vector must be normalized. If a vector collinear to the
226                         normal of this plane is specified, this function returns the same matrix as calling OrthoProjection() would.
227                 @note This mapping can be expressed as a float3x4 operation. See the ObliqueProjection() function.
228                 @see ObliqueProjection(), Project(). */
229         float3 ObliqueProject(const float3 &point, const float3 &obliqueProjectionDir) const;
230 #endif
231
232         /// Returns the transformation matrix that mirrors objects along this plane.
233         /** This matrix maps each point to its mirror point on the opposite side of this plane.
234                 @see Mirror(). */
235         float3x4 MirrorMatrix() const;
236
237         /// Mirrors the given point with respect to this plane.
238         /** This function maps the given point to its mirror point on the opposite side of this plane.
239                 @note This operation can be expressed as a float3x4 matrix operation. To compute the mirror matrix for this
240                         plane, use the MirrorMatrix() function.
241                 @see MirrorMatrix(). */
242         vec Mirror(const vec &point) const;
243
244         /// Refracts the given incident vector along this plane.
245         /** By convention, the input vector should point towards the plane, and the returned vector will point away from the plane.
246                 When the ray is going from a denser material to a lighter one, total internal reflection can occur.
247                 In this case, this function will just return a reflected vector from a call to Reflect().
248                 @param vec Specifies the incident ray direction.
249                 @param negativeSideRefractionIndex The refraction index of the material we are exiting.
250                 @param positiveSideRefractionIndex The refraction index of the material we are entering.
251                 @todo Add Plane::Reflect. */
252         vec Refract(const vec &vec, float negativeSideRefractionIndex, float positiveSideRefractionIndex) const;
253
254         /// Computes the closest point on this plane to the given object.
255         /** If the other object intersects this plane, this function will return an arbitrary point inside
256                 the region of intersection.
257                 @see Contains(), Distance(), Intersects(). */
258         vec ClosestPoint(const vec &point) const { return Project(point); }
259         vec ClosestPoint(const Ray &ray) const;
260         vec ClosestPoint(const LineSegment &lineSegment) const;
261
262         /// Tests if this plane contains the given object.
263         /** @param epsilon Since a plane is a 2D object in a 3D space, an distance threshold is used for the test.
264                 This value gives a "thickness" to this plane for the purposes of the test.
265                 @return True if the given object is contained in this plane, up to the given epsilon distance. */
266         bool Contains(const vec &point, float epsilon = 1e-3f) const;
267         bool Contains(const Line &line, float epsilon = 1e-3f) const;
268         bool Contains(const Ray &ray, float epsilon = 1e-3f) const;
269         bool Contains(const LineSegment &lineSegment, float epsilon = 1e-3f) const;
270         bool Contains(const Triangle &triangle, float epsilon = 1e-3f) const;
271         bool Contains(const Circle &circle, float epsilon = 1e-3f) const;
272         bool Contains(const Polygon &polygon, float epsilon = 1e-3f) const;
273
274         /// Returns true if this plane represents the same set of points than the other plane.
275         /** For this test, the surface normals of the two planes may point in opposite directions, as long as
276                 the set of points is the same.
277                 @see Equals(), IsParallel(), DihedralAngle(). */
278         bool SetEquals(const Plane &plane, float epsilon = 1e-3f) const;
279
280         /// Returns true if the two planes are equal, and their normals are oriented to the same direction.
281         /** @see SetEquals(), IsParallel(), DihedralAngle(). */
282         bool Equals(const Plane &other, float epsilon = 1e-3f) const;
283
284         /// Compares whether this Plane and the given Plane are identical bit-by-bit in the underlying representation.
285         /** @note Prefer using this over e.g. memcmp, since there can be SSE-related padding in the structures. */
286         bool BitEquals(const Plane &other) const { return normal.BitEquals(other.normal) && ReinterpretAsU32(d) == ReinterpretAsU32(other.d); }
287
288         /// Tests if two planes are parallel.
289         /** @see SetEquals(), Equals(), DihedralAngle(). */
290         bool IsParallel(const Plane &plane, float epsilon = 1e-3f) const;
291
292         /// Returns the angle of intersection between two planes, in radians.
293         /** @see SetEquals(), Equals(), IsParallel(). */
294         float DihedralAngle(const Plane &plane) const;
295
296         /// Computes the intersection of three planes.
297         /** This function computes the intersection of this plane, and the given two planes.
298                 @param outLine [out] If the three planes are configured in such a manner that intersection is a line,
299                         this parameter receives the line of intersection. This pointer may be null.
300                 @param outPoint [out] If the three planes are configured in such a manner that the interesction is a point,
301                         this parameter receives the point of intersection. This pointer may be null.
302                 @bug This function never outputs outLine.
303                 @return True if the intersection was a point, in which case outPoint is written to.
304                 @see Contains(), Distance(), ClosestPoint(). */
305         bool Intersects(const Plane &plane, const Plane &plane2, Line *outLine = 0, vec *outPoint = 0) const;
306
307         /// Tests whether this plane and the given object intersect.
308         /** @param outLine [out] The intersection of two planes forms a line. If an intersection occurs, this parameter will receive
309                 the line of intersection. This pointer may be null.
310                 @return True if the given object intersects with this plane. */
311         bool Intersects(const Plane &plane, Line *outLine = 0) const;
312         /** @param d [out] If specified, this parameter will receive the parametric distance of
313                         the intersection point along the line object. Use the GetPoint(d) function of the line class
314                         to get the actual point of intersection. This pointer may be null. */
315         bool Intersects(const Ray &ray, float *d = 0) const;
316         bool Intersects(const Line &line, float *d = 0) const;
317         bool Intersects(const LineSegment &lineSegment, float *d = 0) const;
318         bool Intersects(const Sphere &sphere) const;
319         bool Intersects(const AABB &aabb) const;
320         bool Intersects(const OBB &obb) const;
321         bool Intersects(const Polygon &polygon) const;
322         bool Intersects(const Polyhedron &polyhedron) const;
323         /// @todo Add a version of Plane-Triangle intersection which returns the line segment of intersection.
324         bool Intersects(const Triangle &triangle) const;
325         bool Intersects(const Frustum &frustum) const;
326         bool Intersects(const Capsule &capsule) const;
327         /// Tests if this plane intersects with the given circle.
328         /** @param pt1 [out] If specified, receives the first point of intersection. This pointer may be null.
329                 @param pt2 [out] If specified, receives the second point of intersection. This pointer may be null.
330                 @return The number of intersections that occurred: 0, 1 or 2. */
331         int Intersects(const Circle &circle, vec *pt1, vec *pt2) const;
332         int Intersects(const Circle &circle) const;
333
334         /// Clips a line segment against this plane.
335         /** This function removes the part of the line segment which lies in the negative halfspace of this plane.
336                 The clipping operation is performed in-place. If the whole line segment is clipped, the input variables
337                 are not modified.
338                 @return If this function returns true, the line segment after clipping did not become degenerate.
339                                 If false is returned, the whole line segment lies in the negative halfspace, and no output line segment
340                                 was generated. */
341         bool Clip(LineSegment &line) const;
342         bool Clip(vec &a, vec &b) const;
343
344         /// Clips a line against this plane.
345         /** This function removes the part of the line which lies in the negative halfspace of this plane.
346                 @param line The line to clip. If this function returns 2, then the input line should be preserved.
347                 @param outRay [out] If this function returns 1, then this parameter will receive the ray object that was formed.
348                 @return If the clipping removed the whole line, the value 0 is returned.
349                                 If the clipping resulted in a ray, the value 1 is returned.
350                                 If the clipping resulted in a line, the value 2 is returned. */
351         int Clip(const Line &line, Ray &outRay) const;
352
353         /// Clips a triangle against this plane.
354         /** This function removes the part of the triangle which lies in the negative halfspace of this plane.
355                 @return This function reports how many output triangles were generated.
356                                 If the whole input triangle was clipped, the value 0 is returned.
357                                 If this function returns 1, the value t1 will receive the generated output triangle.
358                                 If this function returns 2, t1 and t2 will receive the generated output triangles. */
359         int Clip(const Triangle &triangle, Triangle &t1, Triangle &t2) const;
360
361         /// Returns true if this plane contains the origin.
362         /** The test is performed up to the given epsilon.
363                 @note A plane passes through the origin if and only if d == 0 for the plane.
364                 @see d. */
365         bool PassesThroughOrigin(float epsilon = 1e-3f) const;
366
367         // Returns true if this plane is a separating plane for the given two objects.
368 //      bool IsSeparatingPlane(const Polyhedron &obj1, const Polyhedron &obj2) const;
369
370         /// Returns a circle that lies on this plane.
371         /** @return The generated circle has its center as close as possible to the specified center point,
372                 and the radius is as specified. */
373         Circle GenerateCircle(const vec &circleCenter, float radius) const;
374
375 //      float3 RandomPointInsideCircle(const float3 &circleCenter, float radius) const;
376 //      float3 RandomPointOnCircleEdge(const float3 &circleCenter, float radius) const;
377
378         /// Computes the intersection of a line and a plane.
379         /** @param planeNormal The plane normal direction vector. This vector can be unnormalized.
380                 @param planeD The distance parameter of the plane equation.
381                 @param linePos The starting point of the line.
382                 @param lineDir The line direction vector. This vector does not need to be normalized.
383                 @param t [out] If this function returns true, this parameter will receive the distance along the line where intersection occurs.
384                                         That is, the point lineStart + t * lineDir will be the intersection point. Note that if |lineDir| != 1,
385                                         then t will not contain the real distance, but one scaled to the units of lineDir.
386                 @return If an intersection occurs, this function returns true. */
387         static bool IntersectLinePlane(const vec &planeNormal, float planeD, const vec &linePos, const vec &lineDir, float &t);
388
389 #ifdef MATH_ENABLE_STL_SUPPORT
390         /// Returns a human-readable representation of this Plane. Most useful for debugging purposes.
391         std::string ToString() const;
392         std::string SerializeToString() const;
393
394         /// Returns a string of C++ code that can be used to construct this object. Useful for generating test cases from badly behaving objects.
395         std::string SerializeToCodeString() const;
396 #endif
397
398         static Plane FromString(const char *str, const char **outEndStr = 0);
399 #ifdef MATH_ENABLE_STL_SUPPORT
400         static Plane FromString(const std::string &str) { return FromString(str.c_str()); }
401 #endif
402
403 #ifdef MATH_OGRE_INTEROP
404         Plane(const Ogre::Plane &other):normal(other.normal), d(other.d) {}
405         operator Ogre::Plane() const { return Ogre::Plane(normal, d); }
406 #endif
407 #ifdef MATH_QT_INTEROP
408         operator QString() const { return toString(); }
409         QString toString() const { return QString::fromStdString(ToString()); }
410 #endif
411 #ifdef MATH_GRAPHICSENGINE_INTEROP
412         void Triangulate(VertexBuffer &vb, float uWidth, float vHeight, const vec &centerPoint, int numFacesU, int numFacesV, bool ccwIsFrontFacing) const;
413         void ToLineList(VertexBuffer &vb, float uWidth, float vHeight, const vec &centerPoint, int numLinesU, int numLinesV) const;
414 #endif
415 #ifdef MATH_URHO3D_INTEROP
416         Plane(const Urho3D::Plane &other) : normal(other.normal_), d(other.d_) {}
417         operator Urho3D::Plane() const { return Urho3D::Plane(float4(normal, d)); }
418 #endif
419 };
420
421 Plane operator *(const float3x3 &transform, const Plane &plane);
422 Plane operator *(const float3x4 &transform, const Plane &plane);
423 Plane operator *(const float4x4 &transform, const Plane &plane);
424 Plane operator *(const Quat &transform, const Plane &plane);
425
426 #ifdef MATH_QT_INTEROP
427 Q_DECLARE_METATYPE(Plane)
428 Q_DECLARE_METATYPE(Plane*)
429 #endif
430
431 #ifdef MATH_ENABLE_STL_SUPPORT
432 std::ostream &operator <<(std::ostream &o, const Plane &plane);
433 #endif
434
435 MATH_END_NAMESPACE