1 /**
2   This module implements some abstract geometric shapes:
3   $(UL
4   $(LI Line segments.)
5   $(LI Triangle.)
6   $(LI Circles/spheres.)
7   $(LI Rays)
8   $(LI Planes)
9   $(LI Frustum)
10   )
11  */
12 module gfm.math.shapes;
13 
14 import std.math,
15        std.traits;
16 
17 import gfm.math.vector,
18        gfm.math.box;
19 
20 /// A Segment is 2 points.
21 /// When considered like a vector, it represents the arrow from a to b.
22 struct Segment(T, int N)
23 {
24     public
25     {
26         alias Vector!(T, N) point_t;
27         point_t a, b;
28         
29         static if (N == 3 && isFloatingPoint!T)
30         {
31             /// Segment vs plane intersection.
32             /// See_also: "Geometry for Computer Graphics: Formulae, Examples
33             ///     and Proofs", Vince (2005), p. 62
34             /// Returns: $(D true) if the segment crosses the plane exactly
35             ///     once, or $(D false) if the segment is parallel to or does
36             ///     not reach the plane
37             /// Params:
38             ///     intersection = set to the point of intersection
39             ///     progress = set to the point's progress between endpoints
40             ///                $(D a) at 0.0 and $(D b) at 1.0, or T.infinity
41             ///                if parallel to the plane
42             @nogc @safe bool intersect(Plane!T plane, out point_t intersection, out T progress) pure const nothrow
43             {
44                 // direction vector from a to b
45                 point_t dir = b-a;
46                 
47                 // dot product will be 0 if angle to plane is 0
48                 T dp = dot(plane.n, dir);
49                 if (abs(dp) < T.epsilon)
50                 {
51                     progress = T.infinity;
52                     return false; // parallel to plane
53                 }
54                 
55                 // relative distance along segment where intersection happens
56                 progress = -(dot(plane.n, a) - plane.d) / dp;
57                 
58                 intersection = progress*dir + a;
59                 return progress >= 0 && progress <= 1;
60             }
61         }
62     }
63 }
64 
65 alias Segment!(float, 2) seg2f;  /// 2D float segment.
66 alias Segment!(float, 3) seg3f;  /// 3D float segment.
67 alias Segment!(double, 2) seg2d; /// 2D double segment.
68 alias Segment!(double, 3) seg3d; /// 3D double segment.
69 alias Segment!(int, 2) seg2i;    /// 2D integer segment.
70 alias Segment!(int, 3) seg3i;    /// 3D integer segment.
71 
72 /// A Triangle is 3 points.
73 struct Triangle(T, int N)
74 {
75     public
76     {
77         alias Vector!(T, N) point_t;
78         point_t a, b, c;
79 
80         static if (N == 2)
81         {
82             /// Returns: Area of a 2D triangle.
83             @nogc T area() pure const nothrow
84             {
85                 return abs(signedArea());
86             }
87 
88             /// Returns: Signed area of a 2D triangle.
89             @nogc T signedArea() pure const nothrow
90             {
91                 return ((b.x * a.y - a.x * b.y)
92                       + (c.x * b.y - b.x * c.y)
93                       + (a.x * c.y - c.x * a.y)) / 2;
94             }
95         }
96 
97         static if (N == 3 && isFloatingPoint!T)
98         {
99             /// Returns: Triangle normal.
100             @nogc Vector!(T, 3) computeNormal() pure const nothrow
101             {
102                 return cross(b - a, c - a).normalized();
103             }
104         }
105     }
106 }
107 
108 alias Triangle!(float, 2) triangle2f;  /// 2D float triangle.
109 alias Triangle!(float, 3) triangle3f;  /// 3D float triangle.
110 alias Triangle!(double, 2) triangle2d; /// 2D double triangle.
111 alias Triangle!(double, 3) triangle3d; /// 3D double triangle.
112 
113 /// A Sphere is a point + a radius.
114 struct Sphere(T, int N)
115 {
116     public nothrow
117     {
118         alias Vector!(T, N) point_t;
119         point_t center;
120         T radius;
121 
122         /// Creates a sphere from a point and a radius.
123         @nogc this(in point_t center_, T radius_) pure nothrow
124         {
125             center = center_;
126             radius = radius_;
127         }
128 
129         /// Sphere contains point test.
130         /// Returns: true if the point is inside the sphere.
131         @nogc bool contains(in Sphere s) pure const nothrow
132         {
133             if (s.radius > radius)
134                 return false;
135 
136             T innerRadius = radius - s.radius;
137             return squaredDistanceTo(s.center) < innerRadius * innerRadius;
138         }
139 
140         /// Sphere vs point Euclidean distance squared.
141         @nogc T squaredDistanceTo(point_t p) pure const nothrow
142         {
143             return center.squaredDistanceTo(p);
144         }
145 
146         /// Sphere vs sphere intersection.
147         /// Returns: true if the spheres intersect.
148         @nogc bool intersects(Sphere s) pure const nothrow
149         {
150             T outerRadius = radius + s.radius;
151             return squaredDistanceTo(s.center) < outerRadius * outerRadius;
152         }
153 
154         static if (isFloatingPoint!T)
155         {
156             /// Sphere vs point Euclidean distance.
157             @nogc T distanceTo(point_t p) pure const nothrow
158             {
159                 return center.distanceTo(p);
160             }
161 
162             static if(N == 2)
163             {
164                 /// Returns: Circle area.
165                 @nogc T area() pure const nothrow
166                 {
167                     return PI * (radius * radius);
168                 }
169             }
170         }
171     }
172 }
173 
174 alias Sphere!(float, 2) sphere2f;  /// 2D float sphere (ie. a circle).
175 alias Sphere!(float, 3) sphere3f;  /// 3D float sphere.
176 alias Sphere!(double, 2) sphere2d; /// 2D double sphere (ie. a circle).
177 alias Sphere!(double, 3) sphere3d; /// 3D double sphere (ie. a circle).
178 
179 
180 /// A Ray ir a point + a direction.
181 struct Ray(T, int N)
182 {
183 nothrow:
184     public
185     {
186         alias Vector!(T, N) point_t;
187         point_t orig;
188         point_t dir;
189 
190         /// Returns: A point further along the ray direction.
191         @nogc point_t progress(T t) pure const nothrow
192         {
193             return orig + dir * t;
194         }
195 
196         static if (N == 3 && isFloatingPoint!T)
197         {
198             /// Ray vs triangle intersection.
199             /// See_also: "Fast, Minimum Storage Ray/Triangle intersection", Mommer & Trumbore (1997)
200             /// Returns: Barycentric coordinates, the intersection point is at $(D (1 - u - v) * A + u * B + v * C).
201             @nogc bool intersect(Triangle!(T, 3) triangle, out T t, out T u, out T v) pure const nothrow
202             {
203                 point_t edge1 = triangle.b - triangle.a;
204                 point_t edge2 = triangle.c - triangle.a;
205                 point_t pvec = cross(dir, edge2);
206                 T det = dot(edge1, pvec);
207                 if (abs(det) < T.epsilon)
208                     return false; // no intersection
209                 T invDet = 1 / det;
210 
211                 // calculate distance from triangle.a to ray origin
212                 point_t tvec = orig - triangle.a;
213 
214                 // calculate U parameter and test bounds
215                 u = dot(tvec, pvec) * invDet;
216                 if (u < 0 || u > 1)
217                     return false;
218 
219                 // prepare to test V parameter
220                 point_t qvec = cross(tvec, edge1);
221 
222                 // calculate V parameter and test bounds
223                 v = dot(dir, qvec) * invDet;
224                 if (v < 0.0 || u + v > 1.0)
225                     return false;
226 
227                 // calculate t, ray intersects triangle
228                 t = dot(edge2, qvec) * invDet;
229                 return true;
230             }
231             
232             /// Ray vs plane intersection.
233             /// See_also: "Geometry for Computer Graphics: Formulae, Examples
234             ///     and Proofs", Vince (2005), p. 62
235             /// Returns: $(D true) if the ray crosses the plane exactly once,
236             ///     or $(D false) if the ray is parallel to or points away from
237             ///     the plane
238             /// Params:
239             ///     intersection = set to the point of intersection
240             ///     distance = set to the point's distance along the ray, or
241             ///                T.infinity if parallel to the plane
242             @nogc @safe bool intersect(Plane!T plane, out point_t intersection, out T distance) pure const nothrow
243             {
244                 // dot product will be 0 if angle to plane is 0
245                 T dp = dot(plane.n, dir);
246                 if (abs(dp) < T.epsilon)
247                 {
248                     distance = T.infinity;
249                     return false; // parallel to plane
250                 }
251                 
252                 // distance along ray where intersection happens
253                 distance = -(dot(plane.n, orig) - plane.d) / dp;
254                 
255                 intersection = distance*dir + orig;
256                 return distance >= 0;
257             }
258         }
259     }
260 }
261 
262 alias Ray!(float, 2) ray2f;  /// 2D float ray.
263 alias Ray!(float, 3) ray3f;  /// 3D float ray.
264 alias Ray!(double, 2) ray2d; /// 2D double ray.
265 alias Ray!(double, 3) ray3d; /// 3D double ray.
266 
267 
268 /// 3D plane.
269 /// See_also: Flipcode article by Nate Miller $(WEB www.flipcode.com/archives/Plane_Class.shtml).
270 struct Plane(T) if (isFloatingPoint!T)
271 {
272     public
273     {
274         vec3!T n; /// Normal (always stored normalized).
275         T d;
276 
277         /// Create from four coordinates.
278         @nogc this(vec4!T abcd) pure nothrow
279         {
280             n = vec3!T(abcd.x, abcd.y, abcd.z).normalized();
281             d = abcd.w;
282         }
283 
284         /// Create from a point and a normal.
285         @nogc this(vec3!T origin, vec3!T normal) pure nothrow
286         {
287             n = normal.normalized();
288             d = -dot(origin, n);
289         }
290 
291         /// Create from 3 non-aligned points.
292         @nogc this(vec3!T A, vec3!T B, vec3!T C) pure nothrow
293         {
294             this(C, cross(B - A, C - A));
295         }
296 
297         /// Assign a plane with another plane.
298         @nogc ref Plane opAssign(Plane other) pure nothrow
299         {
300             n = other.n;
301             d = other.d;
302             return this;
303         }
304 
305         /// Returns: signed distance between a point and the plane.
306         @nogc T signedDistanceTo(vec3!T point) pure const nothrow
307         {
308             return dot(n, point) + d;
309         }
310 
311         /// Returns: absolute distance between a point and the plane.
312         @nogc T distanceTo(vec3!T point) pure const nothrow
313         {
314             return abs(signedDistanceTo(point));
315         }
316 
317         /// Returns: true if the point is in front of the plane.
318         @nogc bool isFront(vec3!T point) pure const nothrow
319         {
320             return signedDistanceTo(point) >= 0;
321         }
322 
323         /// Returns: true if the point is in the back of the plane.
324         @nogc bool isBack(vec3!T point) pure const nothrow
325         {
326             return signedDistanceTo(point) < 0;
327         }
328 
329         /// Returns: true if the point is on the plane, with a given epsilon.
330         @nogc bool isOn(vec3!T point, T epsilon) pure const nothrow
331         {
332             T sd = signedDistanceTo(point);
333             return (-epsilon < sd) && (sd < epsilon);
334         }
335     }
336 }
337 
338 alias Plane!float planef;  /// 3D float plane.
339 alias Plane!double planed; /// 3D double plane.
340 
341 unittest
342 {
343     auto p = planed(vec4d(1.0, 2.0, 3.0, 4.0));
344     auto p2 = planed(vec3d(1.0, 0.0, 0.0),
345                      vec3d(0.0, 1.0, 0.0),
346                      vec3d(0.0, 0.0, 1.0));
347 
348     assert(p2.isOn(vec3d(1.0, 0.0, 0.0), 1e-7));
349     assert(p2.isFront(vec3d(1.0, 1.0, 1.0)));
350     assert(p2.isBack(vec3d(0.0, 0.0, 0.0)));
351 }
352 
353 /// Plane intersection tests
354 @nogc @safe pure nothrow unittest
355 {
356     void testR(planed p, ray3d r, bool shouldIntersect, double expectedDistance, vec3d expectedPoint = vec3d.init)
357     {
358         vec3d point;
359         double distance;
360         assert(r.intersect(p, point, distance) == shouldIntersect);
361         assert(approxEqual(distance, expectedDistance));
362         if (shouldIntersect)
363             assert(approxEqual(point.v[], expectedPoint.v[]));
364     }
365     // ray facing plane
366     testR(planed(vec4d(1.0, 0.0, 0.0, 1.0)), ray3d(vec3d(2.0, 3.0, 4.0), vec3d(-1.0, 0.0, 0.0)),
367         true, 1.0, vec3d(1.0, 3.0, 4.0));
368     testR(planed(vec4d(1.0, 1.0, 1.0, -sqrt(3.0))), ray3d(vec3d(1.0, 1.0, 1.0), vec3d(-1.0, -1.0, -1.0).normalized()),
369         true, 2.0*sqrt(3.0), vec3d(-1.0, -1.0, -1.0));
370     // ray facing away
371     testR(planed(vec4d(1.0, 0.0, 0.0, 1.0)), ray3d(vec3d(2.0, 3.0, 4.0), vec3d(1.0, 0.0, 0.0)),
372         false, -1.0);
373     testR(planed(vec4d(1.0, 0.0, 0.0, 5.0)), ray3d(vec3d(2.0, 3.0, 4.0), vec3d(-1.0, 0.0, 0.0)),
374         false, -3.0);
375     // ray parallel
376     testR(planed(vec4d(0.0, 0.0, 1.0, 1.0)), ray3d(vec3d(1.0, 2.0, 3.0), vec3d(1.0, 0.0, 0.0)),
377         false, double.infinity);
378     
379     void testS(planed p, seg3d s, bool shouldIntersect, double expectedProgress, vec3d expectedPoint = vec3d.init)
380     {
381         vec3d point;
382         double progress;
383         assert(s.intersect(p, point, progress) == shouldIntersect);
384         assert(approxEqual(progress, expectedProgress));
385         if (shouldIntersect)
386             assert(approxEqual(point.v[], expectedPoint.v[]));
387     }
388     // segment crossing plane
389     testS(planed(vec4d(1.0, 0.0, 0.0, 2.0)), seg3d(vec3d(1.0, 2.0, 3.0), vec3d(3.0, 4.0, 5.0)),
390         true, 0.5, vec3d(2.0, 3.0, 4.0));
391     // segment too short
392     testS(planed(vec4d(1.0, 0.0, 0.0, 0.0)), seg3d(vec3d(1.0, 2.0, 3.0), vec3d(3.0, 4.0, 5.0)),
393         false, -0.5);
394 }
395 
396 
397 /// 3D frustum.
398 /// See_also: Flipcode article by Dion Picco $(WEB www.flipcode.com/archives/Frustum_Culling.shtml).
399 /// Bugs: verify proper signedness of half-spaces
400 struct Frustum(T) if (isFloatingPoint!T)
401 {
402     public
403     {
404         enum int LEFT   = 0,
405                  RIGHT  = 1,
406                  TOP    = 2,
407                  BOTTOM = 3,
408                  NEAR   = 4,
409                  FAR    = 5;
410 
411         Plane!T[6] planes;
412 
413         /// Create a frustum from 6 planes.
414         @nogc this(Plane!T left, Plane!T right, Plane!T top, Plane!T bottom, Plane!T near, Plane!T far) pure nothrow
415         {
416             planes[LEFT] = left;
417             planes[RIGHT] = right;
418             planes[TOP] = top;
419             planes[BOTTOM] = bottom;
420             planes[NEAR] = near;
421             planes[FAR] = far;
422         }
423 
424         enum : int
425         {
426             OUTSIDE,   /// object is outside the frustum
427             INTERSECT, /// object intersects with the frustum
428             INSIDE     /// object is inside the frustum
429         }
430 
431         /// Point vs frustum intersection.
432         @nogc bool contains(vec3!T point) pure const nothrow
433         {
434             for(int i = 0; i < 6; ++i)
435             {
436                 T distance = planes[i].signedDistanceTo(point);
437 
438                 if(distance < 0)
439                     return false;
440             }
441             return true;
442         }
443 
444         /// Sphere vs frustum intersection.
445         /// Returns: Frustum.OUTSIDE, Frustum.INTERSECT or Frustum.INSIDE.
446         @nogc int contains(Sphere!(T, 3) sphere) pure const nothrow
447         {
448             // calculate our distances to each of the planes
449             for(int i = 0; i < 6; ++i)
450             {
451                 // find the distance to this plane
452                 T distance = planes[i].signedDistanceTo(sphere.center);
453 
454                 if(distance < -sphere.radius)
455                     return OUTSIDE;
456 
457                 else if (distance < sphere.radius)
458                     return INTERSECT;
459             }
460 
461             // otherwise we are fully in view
462             return INSIDE;
463         }
464 
465         /// AABB vs frustum intersection.
466         /// Returns: Frustum.OUTSIDE, Frustum.INTERSECT or Frustum.INSIDE.
467         @nogc int contains(box3!T box) pure const nothrow
468         {
469             vec3!T[8] corners;
470             int totalIn = 0;
471 
472             for (int i = 0; i < 2; ++i)
473                 for (int j = 0; j < 2; ++j)
474                     for (int k = 0; k < 2; ++k)
475                     {
476                         auto x = i == 0 ? box.min.x : box.max.x;
477                         auto y = i == 0 ? box.min.y : box.max.y;
478                         auto z = i == 0 ? box.min.z : box.max.z;
479                         corners[i*4 + j*2 + k] = vec3!T(x, y, z);
480                     }
481 
482             // test all 8 corners against the 6 sides
483             // if all points are behind 1 specific plane, we are out
484             // if we are in with all points, then we are fully in
485             for(int p = 0; p < 6; ++p)
486             {
487                 int inCount = 8;
488                 int ptIn = 1;
489 
490                 for(int i = 0; i < 8; ++i)
491                 {
492                     // test this point against the planes
493                     if (planes[p].isBack(corners[i]))
494                     {
495                         ptIn = 0;
496                         --inCount;
497                     }
498                 }
499 
500                 // were all the points outside of plane p?
501                 if (inCount == 0)
502                     return OUTSIDE;
503 
504                 // check if they were all on the right side of the plane
505                 totalIn += ptIn;
506             }
507 
508             // so if totalIn is 6, then all are inside the view
509             if(totalIn == 6)
510                 return INSIDE;
511 
512             // we must be partly in then otherwise
513             return INTERSECT;
514         }
515 
516     }
517 }
518 
519 unittest
520 {
521     seg2f se;
522     triangle3f tr;
523     Frustum!double frust;
524     planed pl;
525 }
526 
527 /// True if `T` is a kind of Segment
528 enum isSegment(T) = is(T : Segment!U, U...);
529 
530 /// True if `T` is a kind of Triangle
531 enum isTriangle(T) = is(T : Triangle!U, U...);
532 
533 /// True if `T` is a kind of Sphere
534 enum isSphere(T) = is(T : Sphere!U, U...);
535 
536 /// True if `T` is a kind of Ray
537 enum isRay(T) = is(T : Ray!U, U...);
538 
539 /// True if `T` is a kind of Plane
540 enum isPlane(T) = is(T : Plane!U, U);
541 
542 /// True if `T` is a kind of Frustum
543 enum isFrustum(T) = is(T : Frustum!U, U);
544 
545 /// True if `T` is a kind of 2 dimensional Segment
546 enum isSegment2D(T) = is(T : Segment!(U, 2), U);
547 
548 /// True if `T` is a kind of 2 dimensional Triangle
549 enum isTriangle2D(T) = is(T : Triangle!(U, 2), U);
550 
551 /// True if `T` is a kind of 2 dimensional Sphere
552 enum isSphere2D(T) = is(T : Sphere!(U, 2), U);
553 
554 /// True if `T` is a kind of 2 dimensional Ray
555 enum isRay2D(T) = is(T : Ray!(U, 2), U);
556 
557 /// True if `T` is a kind of 3 dimensional Segment
558 enum isSegment3D(T) = is(T : Segment!(U, 3), U);
559 
560 /// True if `T` is a kind of 3 dimensional Triangle
561 enum isTriangle3D(T) = is(T : Triangle!(U, 3), U);
562 
563 /// True if `T` is a kind of 3 dimensional Sphere
564 enum isSphere3D(T) = is(T : Sphere!(U, 3), U);
565 
566 /// True if `T` is a kind of 3 dimensional Ray
567 enum isRay3D(T) = is(T : Ray!(U, 3), U);
568 
569 unittest
570 {
571     enum ShapeType
572     {
573         segment,
574         triangle,
575         sphere,
576         ray,
577         plane,
578         frustum
579     }
580 
581     void test(T, ShapeType type, int dim)()
582     {
583         with (ShapeType)
584         {
585             static assert(isSegment!T  == (type == segment ));
586             static assert(isTriangle!T == (type == triangle));
587             static assert(isSphere!T   == (type == sphere  ));
588             static assert(isRay!T      == (type == ray     ));
589             static assert(isPlane!T    == (type == plane   ));
590             static assert(isFrustum!T  == (type == frustum ));
591 
592             static assert(isSegment2D!T  == (type == segment  && dim == 2));
593             static assert(isTriangle2D!T == (type == triangle && dim == 2));
594             static assert(isSphere2D!T   == (type == sphere   && dim == 2));
595             static assert(isRay2D!T      == (type == ray      && dim == 2));
596 
597             static assert(isSegment3D!T  == (type == segment  && dim == 3));
598             static assert(isTriangle3D!T == (type == triangle && dim == 3));
599             static assert(isSphere3D!T   == (type == sphere   && dim == 3));
600             static assert(isRay3D!T      == (type == ray      && dim == 3));
601         }
602     }
603 
604     with (ShapeType)
605     {
606         //    test case         type      #dimensions
607         test!(seg2f           , segment , 2);
608         test!(seg3d           , segment , 3);
609         test!(triangle2d      , triangle, 2);
610         test!(triangle3f      , triangle, 3);
611         test!(sphere2d        , sphere  , 2);
612         test!(Sphere!(uint, 3), sphere  , 3);
613         test!(ray2f           , ray     , 2);
614         test!(Ray!(real, 3)   , ray     , 3);
615         test!(planed          , plane   , 0); // ignore dimension (always 3D)
616         test!(Plane!float     , plane   , 0);
617         test!(Frustum!double  , frustum , 0);
618     }
619 }
620 
621 /// Get the numeric type used to measure a shape's dimensions.
622 alias DimensionType(T : Segment!U, U...) = U[0];
623 /// ditto
624 alias DimensionType(T : Triangle!U, U...) = U[0];
625 /// ditto
626 alias DimensionType(T : Sphere!U, U...) = U[0];
627 /// ditto
628 alias DimensionType(T : Ray!U, U...) = U[0];
629 /// ditto
630 alias DimensionType(T : Plane!U, U) = U;
631 /// ditto
632 alias DimensionType(T : Frustum!U, U) = U;
633 
634 ///
635 unittest
636 {
637     static assert(is(DimensionType!seg2i          == int));
638     static assert(is(DimensionType!triangle3d     == double));
639     static assert(is(DimensionType!sphere2d       == double));
640     static assert(is(DimensionType!ray3f          == float));
641     static assert(is(DimensionType!planed         == double));
642     static assert(is(DimensionType!(Frustum!real) == real));
643 }