1 /*---------------------------------------------------------------------------*
2 Project: Horizon
3 File: math_Geometry.h
4
5 Copyright (C)2009-2010 Nintendo Co., Ltd. All rights reserved.
6
7 These coded instructions, statements, and computer programs contain
8 proprietary information of Nintendo of America Inc. and/or Nintendo
9 Company Ltd., and are protected by Federal copyright law. They may
10 not be disclosed to third parties or copied or duplicated in any form,
11 in whole or in part, without the prior written consent of Nintendo.
12
13 $Revision: 24054 $
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 // 線や面等のジオメトリオブジェクトを定義しておく
26
27 // 名前予約
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 クラス定義
62 ======================================================================== */
63
64
65 /* ------------------------------------------------------------------------
66 LINE3:
67
68 L: P + td
69 パラメトリック形式の線(3D)である。Pが起点でdが線の方向である。
70 使用時にdは正規化されていることが前提となっている。
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 // 線分を、線分の始点を始点とする線に変換する。
91 void Set(const SEGMENT3* S);
NormalizeLINE392 void Normalize() { (void)VEC3Normalize(&d, &d); }
93 public:
94 VEC3 P;
95 VEC3 d; // 直接代入する場合は正規化しておくこと
96 };
97
98 /* ------------------------------------------------------------------------
99 RAY3
100
101 R: P + td (ただし、t >= 0)
102 起点からdの方向だけに向かう線である。Pが起点でdが線の方向である。
103 使用時にdは正規化されていることが前提となっている。
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; // 直接代入する場合は正規化しておくこと
127 };
128
129
130 /* ------------------------------------------------------------------------
131 SEGMENT3
132
133 S: (1 - t)P0 + tP1 (ただし、0 <= t <= 1)
134 P0とP1を繋ぐ線分である。
135 ------------------------------------------------------------------------ */
136 struct SEGMENT3
137 {
138 public:
139 typedef SEGMENT3 self_type;
140 public:
SEGMENT3SEGMENT3141 SEGMENT3() {}
SEGMENT3SEGMENT3142 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
166 S: |P - C| <= r
167 Cを中心の位置、rを半径とする球である。
168 ------------------------------------------------------------------------ */
169 struct SPHERE
170 {
171 public:
172 typedef SPHERE self_type;
173 public:
SPHERESPHERE174 SPHERE() {}
SPHERESPHERE175 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 // 点の集合を包含する球をセットする。
184 void Set(const VEC3* arrayPoint, unsigned int numPoints);
185 public:
186 VEC3 C;
187 f32 r;
188 };
189
190
191 /* ------------------------------------------------------------------------
192 PLANE
193
194 (N.x)x + (N.y)y + (N.z)z + d = 0
195
196 平面の陰関数表現をパラメータとして持っている。
197 法線ベクトルNは正規化されている必要がある。
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が平面の法線方向にある場合は正に、そうでない場合は負になります。
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; // 直接代入する場合は正規化しておくこと
238 f32 d;
239 };
240
241
242 /* ------------------------------------------------------------------------
243 CAPSULE
244
245 線分と線分に対する距離でカプセルが定義される。
246 ------------------------------------------------------------------------ */
247 struct CAPSULE
248 {
249 public:
250 typedef CAPSULE self_type;
251 public:
CAPSULECAPSULE252 CAPSULE() {}
CAPSULECAPSULE253 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
270 xyz軸に沿ったボックスです。2つの点PminとPmaxで定義されます。
271 Pminのそれぞれの座標はPmaxの座標よりも小さい必要があります。
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
305 半径rで原点からZ軸にhだけの高さを持つ円柱と解釈される。
306 lineやplaneとの交差判定は座標変換してから行う必要がある。
307 ------------------------------------------------------------------------ */
308 struct CYLINDER
309 {
310 public:
311 typedef CYLINDER self_type;
312 public:
CYLINDERCYLINDER313 CYLINDER() {}
CYLINDERCYLINDER314 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
327 半径rで原点からZ軸にhだけの高さを持つ円錐と解釈される。
328 lineやplaneとの交差判定は座標変換してから行う必要がある。
329 ------------------------------------------------------------------------ */
330 struct CONE
331 {
332 public:
333 typedef CONE self_type;
334 public:
CONECONE335 CONE() {}
CONECONE336 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
350 主にカリングに使用するためのフラスタムの定義
351 ------------------------------------------------------------------------ */
352 class FRUSTUM
353 {
354 public:
355 typedef FRUSTUM self_type;
356 public:
357 //---------------------------------------------------------------------------
358 //! @brief コンストラクタです。
359 //---------------------------------------------------------------------------
FRUSTUM()360 FRUSTUM() {}
361
362 //---------------------------------------------------------------------------
363 //! @brief コンストラクタです。
364 //!
365 //! @param[in] fovyRad 縦方向の視野角（Radian）。
366 //! @param[in] aspect アスペクト比(幅/高さ)
367 //! @param[in] n ニアクリッピング面までの距離。
368 //! @param[in] f ファークリッピング面までの距離。
369 //! @param[in] camera カメラ行列。
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 //! @brief コンストラクタです。
378 //!
379 //! @param[in] top ニアクリッピング面での視錐台上辺の Y 座標。
380 //! @param[in] bottom ニアクリッピング面での視錐台下辺の Y 座標。
381 //! @param[in] left ニアクリッピング面での視錐台左辺の X 座標。
382 //! @param[in] right ニアクリッピング面での視錐台右辺の X 座標。
383 //! @param[in] n ニアクリッピング面までの距離。
384 //! @param[in] f ファークリッピング面までの距離。
385 //! @param[in] camera カメラ行列。
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 /* ビュー座標系用のデータメンバ */
395 PLANE leftPlane;
396 PLANE rightPlane;
397 PLANE topPlane;
398 PLANE bottomPlane;
399 f32 znear;
400 f32 zfar;
401
402 /* ワールド座標系用のデータメンバ */
403 AABB box; // フラスタムを包含するAABBで粗い判定に用いる
404 PLANE planes[6]; // left, right, near, far, up, downの順(Optimized View Frustum Culling Algorithmより)
405 public:
406 //---------------------------------------------------------------------------
407 //! @brief FRUSTUM に設定を反映する Set 関数です。
408 //!
409 //! @param[in] top ニアクリッピング面での視錐台上辺の Y 座標。
410 //! @param[in] bottom ニアクリッピング面での視錐台下辺の Y 座標。
411 //! @param[in] left ニアクリッピング面での視錐台左辺の X 座標。
412 //! @param[in] right ニアクリッピング面での視錐台右辺の X 座標。
413 //! @param[in] n ニアクリッピング面までの距離。
414 //! @param[in] f ファークリッピング面までの距離。
415 //! @param[in] camera カメラ行列。
416 //---------------------------------------------------------------------------
417 void Set(f32 top, f32 bottom, f32 left, f32 right, f32 n, f32 f, const MTX34& camera);
418
419 //---------------------------------------------------------------------------
420 //! @brief FRUSTUM に設定を反映する Set 関数です。
421 //!
422 //! @param[in] fovyRad 縦方向の視野角（Radian）。
423 //! @param[in] aspect アスペクト比(幅/高さ)
424 //! @param[in] n ニアクリッピング面までの距離。
425 //! @param[in] f ファークリッピング面までの距離。
426 //! @param[in] camera カメラ行列。
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はワールド座標系
438 bool IntersectSphere(const SPHERE* S) const;
439
440 // AABBはワールド座標系
441 bool IntersectAABB(const AABB* B) const;
442
443 // AABBはワールド座標系
444 IntersectionResult IntersectAABB_Ex(const AABB* B) const;
445 };
446
447
448 //
449 // 3Dジオメトリ間の距離
450 //
451
452 // 点
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 // 線・レイ・線分
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 // 3Dジオメトリ間の交差
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 // 3Dジオメトリのマージ
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