1 /*---------------------------------------------------------------------------*
2 Project: Horizon
3 File: math_Geometry.h
4 Copyright (C)2009-2010 Nintendo Co., Ltd. All rights reserved.
5 These coded instructions, statements, and computer programs contain
6 proprietary information of Nintendo of America Inc. and/or Nintendo
7 Company Ltd., and are protected by Federal copyright law. They may
8 not be disclosed to third parties or copied or duplicated in any form,
9 in whole or in part, without the prior written consent of Nintendo.
10 $Revision: 34617 $
11 *---------------------------------------------------------------------------
12
13
14 */
15
16 #ifndef NN_MATH_GEOMETRY_H_
17 #define NN_MATH_GEOMETRY_H_
18
19 #include <nn/math/math_Config.h>
20 #include <nn/math/math_Types.h>
21 #include <nn/math/math_Triangular.h>
22
23 namespace nn { namespace math {
24
25 // Define geometric objects such as lines and surfaces first
26
27 // Reserve name
28 struct LINE2;
29 struct RAY2;
30 struct SEGMENT2;
31 struct CIRCLE2;
32 struct TRIANGLE2;
33
34 struct LINE3;
35 struct RAY3;
36 struct SEGMENT3;
37 struct SPHERE;
38 struct TRIANGLE3;
39 struct PLANE;
40 struct CYLINDER;
41 struct CONE;
42 struct AABB;
43 struct CAPSULE;
44
45 enum IntersectionResult
46 {
47 INTERSECTION_NONE = 0,
48 INTERSECTION_1 = 1,
49 INTERSECTION_2 = 2,
50
51 INTERSECTION_LINE3_ON_PLANE = 2,
52 INTERSECTION_RAY3_ON_PLANE = INTERSECTION_LINE3_ON_PLANE,
53 INTERSECTION_SEGMENT3_ON_PLANE = INTERSECTION_LINE3_ON_PLANE,
54
55 INTERSECTION_OUTSIDE = 0,
56 INTERSECTION_INSIDE = 1,
57 INTERSECTION_INTERSECT = 2
58 };
59
60 /* =======================================================================
61 Class definitions
62 ======================================================================== */
63
64
65 /* ------------------------------------------------------------------------
66 LINE3:
67 L: P + td
68 Parametric format line (3D). Line heading in direction d from its start point P.
69 It is assumed that d has been normalized during use.
70 ------------------------------------------------------------------------
71 */
72 struct LINE3
73 {
74 public:
75 typedef LINE3 self_type;
76 public:
LINE3LINE377 LINE3() {}
78 LINE3(const f32* p, bool isNormalized = false)
PLINE379 : P(p), d(p + 3)
80 { if (!isNormalized) Normalize(); }
81 LINE3(const VEC3& Pt, const VEC3& dir, bool isNormalized = false)
PLINE382 : P(Pt), d(dir)
83 { if (!isNormalized) Normalize(); }
84
85 operator f32*() { return &P.x; }
86 operator const f32*() const { return &P.x; }
87 bool operator==(const self_type& rhs) const { return P == rhs.P && d == rhs.d; }
88 bool operator!=(const self_type& rhs) const { return P != rhs.P || d != rhs.d; }
89
90 // Converts a line segment into a line having the same start point.
91 void Set(const SEGMENT3* S);
NormalizeLINE392 void Normalize() { (void)VEC3Normalize(&d, &d); }
93 public:
94 VEC3 P;
95 VEC3 d; // Be sure to normalize if substituting directly
96 };
97
98 /* ------------------------------------------------------------------------
99 RAY3
100 R: P + td (where, t >= 0)
101 Line heading in direction d only from its start point. Line heading in direction d from its start point P.
102 It is assumed that d has been normalized during use.
103 ------------------------------------------------------------------------
104 */
105 struct RAY3
106 {
107 public:
108 typedef RAY3 self_type;
109 public:
RAY3RAY3110 RAY3() {}
111 RAY3(const f32* p, bool isNormalized = false)
PRAY3112 : P(p), d(p + 3)
113 { if (!isNormalized) Normalize(); }
114 RAY3(const VEC3& Pt, const VEC3& dir, bool isNormalized = false)
PRAY3115 : P(Pt), d(dir)
116 { if (!isNormalized) Normalize(); }
117
118 operator f32*() { return &P.x; }
119 operator const f32*() const { return &P.x; }
120 bool operator==(const self_type& rhs) const { return P == rhs.P && d == rhs.d; }
121 bool operator!=(const self_type& rhs) const { return P != rhs.P || d != rhs.d; }
122
NormalizeRAY3123 void Normalize() { (void)VEC3Normalize(&d, &d); }
124 public:
125 VEC3 P;
126 VEC3 d; // Be sure to normalize if substituting directly
127 };
128
129
130 /* ------------------------------------------------------------------------
131 SEGMENT3
132 S: (1 - t)P0 + tP1 (where, 0 <= t <= 1)
133 This line segment connects P0 and P1.
134 ------------------------------------------------------------------------
135 */
136 struct SEGMENT3
137 {
138 public:
139 typedef SEGMENT3 self_type;
140 public:
SEGMENT3SEGMENT3141 SEGMENT3() {}
SEGMENT3SEGMENT3142 explicit SEGMENT3(const f32* p) : P0(p), P1(p + 3) {}
SEGMENT3SEGMENT3143 SEGMENT3(const VEC3& pt0, const VEC3& pt1) : P0(pt0), P1(pt1) {}
144
145 operator f32*() { return &P0.x; }
146 operator const f32*() const { return &P0.x; }
147 bool operator==(const self_type& rhs) const { return P0 == rhs.P0 && P1 == rhs.P1; }
148 bool operator!=(const self_type& rhs) const { return P0 != rhs.P0 || P1 == rhs.P1; }
149 public:
150 VEC3 P0;
151 VEC3 P1;
152 };
153
154 inline void
Set(const SEGMENT3 * S)155 LINE3::Set(const SEGMENT3* S)
156 {
157 P = S->P0;
158 VEC3Sub(&d, &S->P1, &S->P0);
159 Normalize();
160 }
161
162
163 /* ------------------------------------------------------------------------
164 SPHERE
165 S: |P - C| <= r
166 This sphere takes C as the center and has a radius of r.
167 ------------------------------------------------------------------------
168 */
169 struct SPHERE
170 {
171 public:
172 typedef SPHERE self_type;
173 public:
SPHERESPHERE174 SPHERE() {}
SPHERESPHERE175 explicit SPHERE(const f32* p) : C(p), r(*(p + 3)) {}
SPHERESPHERE176 SPHERE(const VEC3& center, f32 radius) : C(center), r(radius) {}
177
178 operator f32*() { return &C.x; }
179 operator const f32*() const { return &C.x; }
180 bool operator==(const self_type& rhs) const { return C == rhs.C && r == rhs.r; }
181 bool operator!=(const self_type& rhs) const { return C != rhs.C || r != rhs.r; }
182
183 // Set a sphere that includes a collection of points.
184 void Set(const VEC3* arrayPoint, unsigned int numPoints);
185 public:
186 VEC3 C;
187 f32 r;
188 };
189
190
191 /* ------------------------------------------------------------------------
192 PLANE
193 (N.x)x + (N.y)y + (N.z)z + d = 0
194 The shadow function representation of the plane is used as a parameter.
195 Normal vector, N, must be normalized.
196 ------------------------------------------------------------------------
197
198 */
199 struct PLANE
200 {
201 public:
202 typedef PLANE self_type;
203 public:
PLANEPLANE204 PLANE() {}
205 PLANE(const f32* p, bool isNormalized = false)
NPLANE206 : N(p), d(*(p + 3))
207 { if (!isNormalized) Normalize(); }
208 PLANE(f32 A, f32 B, f32 C, f32 D, bool isNormalized = false)
NPLANE209 : N(A, B, C), d(D)
210 { if (!isNormalized) Normalize(); }
211
PLANEPLANE212 PLANE(const VEC3& P0, const VEC3& P1, const VEC3& P2)
213 {
214 Set(&P0, &P1, &P2);
215 }
216
217 operator f32*() { return &N.x; }
218 operator const f32*() const { return &N.x; }
219 bool operator==(const self_type& rhs) const { return N == rhs.N && d == rhs.d; }
220 bool operator!=(const self_type& rhs) const { return N != rhs.N || d != rhs.d; }
221
222 // P is positive if it points in the normal direction of the plane; otherwise, it is negative.
TestPLANE223 f32 Test(const VEC3& P) const
224 {
225 return d + VEC3Dot(&N, &P);
226 }
227
NormalizePLANE228 void Normalize()
229 {
230 f32 r = FrSqrt(VEC3SquareLen(&N));
231 (void)VEC3Scale(&N, &N, r);
232 d *= r;
233 }
234
235 void Set(const VEC3* P0, const VEC3* P1, const VEC3* P2);
236 public:
237 VEC3 N; // Be sure to normalize if substituting directly
238 f32 d;
239 };
240
241
242 /* ------------------------------------------------------------------------
243 CAPSULE
244 The capsule is defined as the distance between two line segments.
245 ------------------------------------------------------------------------
246 */
247 struct CAPSULE
248 {
249 public:
250 typedef CAPSULE self_type;
251 public:
CAPSULECAPSULE252 CAPSULE() {}
CAPSULECAPSULE253 explicit CAPSULE(const f32* p) : S(p), r(*(p + 6)) {}
CAPSULECAPSULE254 CAPSULE(const SEGMENT3& S_, f32 r_) : S(S_), r(r_) {}
CAPSULECAPSULE255 CAPSULE(const VEC3& P0, const VEC3& P1, f32 r_) : S(P0, P1), r(r_) {}
256
257 operator f32*() { return &S.P0.x; }
258 operator const f32*() const { return &S.P0.x; }
259 bool operator==(const self_type& rhs) const { return S == rhs.S && r == rhs.r; }
260 bool operator!=(const self_type& rhs) const { return S != rhs.S || r != rhs.r; }
261 public:
262 SEGMENT3 S;
263 f32 r;
264 };
265
266
267 /* ------------------------------------------------------------------------
268 AABB
269 This box is aligned with the x, y, and z axes. This box is defined using the two points Pmin and Pmax.
270 Each of the coordinates of Pmin must be smaller than the coordinates of Pmax.
271 ------------------------------------------------------------------------
272 */
273 struct AABB
274 {
275 public:
276 typedef AABB self_type;
277 public:
AABBAABB278 AABB() {}
279 AABB(const f32* p, bool isNormalized = false)
PminAABB280 : Pmin(p), Pmax(p + 3)
281 { if (!isNormalized) Normalize(); }
282 AABB(const VEC3& min, const VEC3& max, bool isNormalized = false)
PminAABB283 : Pmin(min), Pmax(max)
284 { if (!isNormalized) Normalize(); }
285
286 operator f32*() { return &Pmin.x; }
287 operator const f32*() const { return &Pmin.x; }
288 bool operator==(const self_type& rhs) const { return Pmin == rhs.Pmin && Pmax == rhs.Pmax; }
289 bool operator!=(const self_type& rhs) const { return Pmin != rhs.Pmin || Pmax != rhs.Pmax; }
290
291 void Set(const VEC3* arrayPoint, unsigned int numPoints);
292 void Set(const AABB* box, const MTX34* M);
293 void Normalize();
294 public:
295 VEC3 Pmin;
296 VEC3 Pmax;
297 };
298
299
300
301
302 /* ------------------------------------------------------------------------
303 CYLINDER
304 This object is interpreted as a cylinder having a radius of r and a height of z from the start point.
305 Determination of intersection with lines and/or planes must be performed after coordinate conversion.
306 ------------------------------------------------------------------------
307 */
308 struct CYLINDER
309 {
310 public:
311 typedef CYLINDER self_type;
312 public:
CYLINDERCYLINDER313 CYLINDER() {}
CYLINDERCYLINDER314 explicit CYLINDER(const f32* p)
315 : r(*p), h(*(p + 1)) {}
CYLINDERCYLINDER316 CYLINDER(f32 radius, f32 height)
317 : r(radius), h(height) {}
318 public:
319 f32 r;
320 f32 h;
321 };
322
323
324 /* ------------------------------------------------------------------------
325 CONE
326 This object is interpreted as a cone having a radius of r and a height of h from the start point only on the Z axis.
327 Determination of intersection with lines and/or planes must be performed after coordinate conversion.
328 ------------------------------------------------------------------------
329 */
330 struct CONE
331 {
332 public:
333 typedef CONE self_type;
334 public:
CONECONE335 CONE() {}
CONECONE336 explicit CONE(const f32* p)
337 : r(*p), h(*(p + 1)) {}
CONECONE338 CONE(f32 radius, f32 height)
339 : r(radius), h(height) {}
340 public:
341 f32 r;
342 f32 h;
343 };
344
345
346
347 /* ------------------------------------------------------------------------
348 FRUSTUM
349 Define a frustum primarily used for culling
350 ------------------------------------------------------------------------
351 */
352 class FRUSTUM
353 {
354 public:
355 typedef FRUSTUM self_type;
356 public:
357 //---------------------------------------------------------------------------
358 //
359 //---------------------------------------------------------------------------
FRUSTUM()360 FRUSTUM() {}
361
362 //---------------------------------------------------------------------------
363 //
364 //
365 //
366 //
367 //
368 //
369 //
370 //---------------------------------------------------------------------------
FRUSTUM(f32 fovyRad,f32 aspect,f32 n,f32 f,const MTX34 & camera)371 FRUSTUM(f32 fovyRad, f32 aspect, f32 n, f32 f, const MTX34& camera)
372 {
373 Set(fovyRad, aspect, n, f, camera);
374 }
375
376 //---------------------------------------------------------------------------
377 //
378 //
379 //
380 //
381 //
382 //
383 //
384 //
385 //
386 //---------------------------------------------------------------------------
FRUSTUM(f32 top,f32 bottom,f32 left,f32 right,f32 n,f32 f,const MTX34 & camera)387 FRUSTUM(f32 top, f32 bottom, f32 left, f32 right, f32 n, f32 f, const MTX34& camera)
388 {
389 Set(top, bottom, left, right, n, f, camera);
390 }
391 private:
392 MTX34 cam;
393
394 /* Data members for view coordinates */
395 PLANE leftPlane;
396 PLANE rightPlane;
397 PLANE topPlane;
398 PLANE bottomPlane;
399 f32 znear;
400 f32 zfar;
401
402 /* Data members for world coordinates */
403 AABB box; // Use in a rough determination using AABB that contains the frustum
404 PLANE planes[6]; // In order of left, right, near, far, up, and down (from Optimized View Frustum Culling Algorithm)
405 public:
406 //---------------------------------------------------------------------------
407 //
408 //
409 //
410 //
411 //
412 //
413 //
414 //
415 //
416 //---------------------------------------------------------------------------
417 void Set(f32 top, f32 bottom, f32 left, f32 right, f32 n, f32 f, const MTX34& camera);
418
419 //---------------------------------------------------------------------------
420 //
421 //
422 //
423 //
424 //
425 //
426 //
427 //---------------------------------------------------------------------------
Set(f32 fovyRad,f32 aspect,f32 n,f32 f,const MTX34 & camera)428 void Set(f32 fovyRad, f32 aspect, f32 n, f32 f, const MTX34& camera)
429 {
430 f32 tanRad = TanRad(0.5f * fovyRad);
431 f32 ny = tanRad * n;
432 f32 nx = ny * aspect;
433 Set(ny, -ny, -nx, nx, n, f, camera);
434 }
435
436 public:
437 // SPHERE is in world coordinates
438 bool IntersectSphere(const SPHERE* S) const;
439
440 // AABB is in world coordinates
441 bool IntersectAABB(const AABB* B) const;
442
443 // AABB is in world coordinates
444 IntersectionResult IntersectAABB_Ex(const AABB* B) const;
445 };
446
447
448 //
449 // Distance between 3D geometric objects
450 //
451
452 // Points
453 f32 DistSqPoint3ToLine3(const VEC3* P, const LINE3* L, f32* t);
454 f32 DistSqPoint3ToRay3(const VEC3* P, const RAY3* R, f32* t);
455 f32 DistSqPoint3ToSegment3(const VEC3* P, const SEGMENT3* S, f32* t);
456 f32 DistSqPoint3ToPlane(const VEC3* P, const PLANE* J, VEC3* Q);
457 f32 DistSqSphereToPlane(const SPHERE* S, const PLANE* J);
458 f32 DistSqPoint3ToPolyline3(const VEC3* P, const VEC3* vertices, unsigned int nVertices);
459 f32 DistSqPoint3ToAABB(const VEC3* P, const AABB* B, VEC3* q);
460
461 // Lines, rays, and line segments
462 f32 DistSqLine3ToLine3(const LINE3* L0, const LINE3* L1, f32* s, f32* t);
463 f32 DistSqSegment3ToSegment3(const SEGMENT3* S0, const SEGMENT3* S1, f32* s, f32* t);
464 f32 DistSqLine3ToRay3(const LINE3* L, const RAY3* R, f32* s, f32* t);
465 f32 DistSqLine3ToSegment3(const LINE3* L0, const SEGMENT3* S, f32* s, f32* t);
466 f32 DistSqRay3ToRay3(const RAY3* R0, const RAY3* R1, f32* s, f32* t);
467 f32 DistSqRay3ToSegment3(const RAY3* R0, const SEGMENT3* S, f32* s, f32* t);
468
469
470
471
472 //
473 // Intersection of 3D geometric objects
474 //
475
476
477 IntersectionResult IntersectionLine3Plane(const LINE3* L, const PLANE* J, f32* t, VEC3* I);
478 IntersectionResult IntersectionRay3Plane(const RAY3* R, const PLANE* J, f32* t, VEC3* I);
479 IntersectionResult IntersectionSegment3Plane(const SEGMENT3* S, const PLANE* J, f32* t, VEC3* I);
480
481 IntersectionResult IntersectionLine3Sphere(const LINE3* L, const SPHERE* sphere, f32* t0, f32* t1);
482 IntersectionResult IntersectionRay3Sphere(const RAY3* R, const SPHERE* sphere, f32* t0, f32* t1);
483 bool IntersectionRay3Sphere(const RAY3* R, const SPHERE* sphere);
484 IntersectionResult IntersectionSegment3Sphere(const SEGMENT3* S, const SPHERE* sphere, f32* t0, f32* t1);
485
486 bool IntersectionRay3AABB(const RAY3* R, const AABB* box, f32* t);
487 bool IntersectionAABB(const AABB* a, const AABB* b);
488 bool IntersectionSphereAABB(const SPHERE* sphere, const AABB* aabb);
489 bool IntersectionSphere(const SPHERE* s0, const SPHERE* s1);
490 bool IntersectionPlaneAABB(const PLANE* J, const AABB* B);
491
492 bool IntersectionCapsule(const CAPSULE* C0, const CAPSULE* C1);
493 bool IntersectionRay3Capsule(const RAY3* R, const CAPSULE* C);
494 bool IntersectionLine3Capsule(const LINE3* L, const CAPSULE* C);
495 bool IntersectionPlaneCapsule(const PLANE* J, const CAPSULE* C);
496
497 inline bool
IntersectionSphereFrustum(const SPHERE * S,const FRUSTUM * F)498 IntersectionSphereFrustum(const SPHERE* S, const FRUSTUM* F)
499 {
500 return F->IntersectSphere(S);
501 }
502
503 inline bool
IntersectionAABBFrustum(const AABB * B,const FRUSTUM * F)504 IntersectionAABBFrustum(const AABB* B, const FRUSTUM* F)
505 {
506 return F->IntersectAABB(B);
507 }
508
509
510 inline IntersectionResult
IntersectionAABBFrustumEx(const AABB * B,const FRUSTUM * F)511 IntersectionAABBFrustumEx(const AABB* B, const FRUSTUM* F)
512 {
513 return F->IntersectAABB_Ex(B);
514 }
515
516 //
517 // Merge 3D geometry
518 //
519 SPHERE* MergeSphere(SPHERE* s2, const SPHERE* s0, const SPHERE* s1);
520 AABB* MergeAABB(AABB* a2, const AABB* a0, const AABB* a1);
521
522
523
524
525
526
527
528
529
530
531
532 }} // nn::math
533
534 #endif
535
536