aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/ode-0.9/OPCODE/Ice/IceIndexedTriangle.cpp
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--libraries/ode-0.9/OPCODE/Ice/IceIndexedTriangle.cpp548
1 files changed, 0 insertions, 548 deletions
diff --git a/libraries/ode-0.9/OPCODE/Ice/IceIndexedTriangle.cpp b/libraries/ode-0.9/OPCODE/Ice/IceIndexedTriangle.cpp
deleted file mode 100644
index db279c4..0000000
--- a/libraries/ode-0.9/OPCODE/Ice/IceIndexedTriangle.cpp
+++ /dev/null
@@ -1,548 +0,0 @@
1///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
2/**
3 * Contains a handy indexed triangle class.
4 * \file IceIndexedTriangle.cpp
5 * \author Pierre Terdiman
6 * \date January, 17, 2000
7 */
8///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
9
10///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
11// Precompiled Header
12#include "Stdafx.h"
13
14using namespace IceMaths;
15
16///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
17/**
18 * Contains an indexed triangle class.
19 *
20 * \class Triangle
21 * \author Pierre Terdiman
22 * \version 1.0
23 * \date 08.15.98
24*/
25///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
26
27///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
28/**
29 * Flips the winding order.
30 */
31///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
32void IndexedTriangle::Flip()
33{
34 Swap(mVRef[1], mVRef[2]);
35}
36
37///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
38/**
39 * Computes the triangle area.
40 * \param verts [in] the list of indexed vertices
41 * \return the area
42 */
43///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
44float IndexedTriangle::Area(const Point* verts) const
45{
46 if(!verts) return 0.0f;
47 const Point& p0 = verts[0];
48 const Point& p1 = verts[1];
49 const Point& p2 = verts[2];
50 return ((p0-p1)^(p0-p2)).Magnitude() * 0.5f;
51}
52
53///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
54/**
55 * Computes the triangle perimeter.
56 * \param verts [in] the list of indexed vertices
57 * \return the perimeter
58 */
59///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
60float IndexedTriangle::Perimeter(const Point* verts) const
61{
62 if(!verts) return 0.0f;
63 const Point& p0 = verts[0];
64 const Point& p1 = verts[1];
65 const Point& p2 = verts[2];
66 return p0.Distance(p1)
67 + p0.Distance(p2)
68 + p1.Distance(p2);
69}
70
71///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
72/**
73 * Computes the triangle compacity.
74 * \param verts [in] the list of indexed vertices
75 * \return the compacity
76 */
77///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
78float IndexedTriangle::Compacity(const Point* verts) const
79{
80 if(!verts) return 0.0f;
81 float P = Perimeter(verts);
82 if(P==0.0f) return 0.0f;
83 return (4.0f*PI*Area(verts)/(P*P));
84}
85
86///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
87/**
88 * Computes the triangle normal.
89 * \param verts [in] the list of indexed vertices
90 * \param normal [out] the computed normal
91 */
92///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
93void IndexedTriangle::Normal(const Point* verts, Point& normal) const
94{
95 if(!verts) return;
96
97 const Point& p0 = verts[mVRef[0]];
98 const Point& p1 = verts[mVRef[1]];
99 const Point& p2 = verts[mVRef[2]];
100 normal = ((p2-p1)^(p0-p1)).Normalize();
101}
102
103///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
104/**
105 * Computes the triangle denormalized normal.
106 * \param verts [in] the list of indexed vertices
107 * \param normal [out] the computed normal
108 */
109///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
110void IndexedTriangle::DenormalizedNormal(const Point* verts, Point& normal) const
111{
112 if(!verts) return;
113
114 const Point& p0 = verts[mVRef[0]];
115 const Point& p1 = verts[mVRef[1]];
116 const Point& p2 = verts[mVRef[2]];
117 normal = ((p2-p1)^(p0-p1));
118}
119
120///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
121/**
122 * Computes the triangle center.
123 * \param verts [in] the list of indexed vertices
124 * \param center [out] the computed center
125 */
126///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
127void IndexedTriangle::Center(const Point* verts, Point& center) const
128{
129 if(!verts) return;
130
131 const Point& p0 = verts[mVRef[0]];
132 const Point& p1 = verts[mVRef[1]];
133 const Point& p2 = verts[mVRef[2]];
134 center = (p0+p1+p2)*INV3;
135}
136
137///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
138/**
139 * Computes the centered normal
140 * \param verts [in] the list of indexed vertices
141 * \param normal [out] the computed centered normal
142 */
143///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
144void IndexedTriangle::CenteredNormal(const Point* verts, Point& normal) const
145{
146 if(!verts) return;
147
148 const Point& p0 = verts[mVRef[0]];
149 const Point& p1 = verts[mVRef[1]];
150 const Point& p2 = verts[mVRef[2]];
151 Point Center = (p0+p1+p2)*INV3;
152 normal = Center + ((p2-p1)^(p0-p1)).Normalize();
153}
154
155///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
156/**
157 * Computes a random point within the triangle.
158 * \param verts [in] the list of indexed vertices
159 * \param normal [out] the computed centered normal
160 */
161///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
162void IndexedTriangle::RandomPoint(const Point* verts, Point& random) const
163{
164 if(!verts) return;
165
166 // Random barycentric coords
167 float Alpha = UnitRandomFloat();
168 float Beta = UnitRandomFloat();
169 float Gamma = UnitRandomFloat();
170 float OneOverTotal = 1.0f / (Alpha + Beta + Gamma);
171 Alpha *= OneOverTotal;
172 Beta *= OneOverTotal;
173 Gamma *= OneOverTotal;
174
175 const Point& p0 = verts[mVRef[0]];
176 const Point& p1 = verts[mVRef[1]];
177 const Point& p2 = verts[mVRef[2]];
178 random = Alpha*p0 + Beta*p1 + Gamma*p2;
179}
180
181///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
182/**
183 * Computes backface culling.
184 * \param verts [in] the list of indexed vertices
185 * \param source [in] source point (in local space) from which culling must be computed
186 * \return true if the triangle is visible from the source point
187 */
188///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
189bool IndexedTriangle::IsVisible(const Point* verts, const Point& source) const
190{
191 // Checkings
192 if(!verts) return false;
193
194 const Point& p0 = verts[mVRef[0]];
195 const Point& p1 = verts[mVRef[1]];
196 const Point& p2 = verts[mVRef[2]];
197
198 // Compute denormalized normal
199 Point Normal = (p2 - p1)^(p0 - p1);
200
201 // Backface culling
202 return (Normal | source) >= 0.0f;
203
204// Same as:
205// Plane PL(verts[mVRef[0]], verts[mVRef[1]], verts[mVRef[2]]);
206// return PL.Distance(source) > PL.d;
207}
208
209///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
210/**
211 * Computes backface culling.
212 * \param verts [in] the list of indexed vertices
213 * \param source [in] source point (in local space) from which culling must be computed
214 * \return true if the triangle is visible from the source point
215 */
216///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
217bool IndexedTriangle::BackfaceCulling(const Point* verts, const Point& source) const
218{
219 // Checkings
220 if(!verts) return false;
221
222 const Point& p0 = verts[mVRef[0]];
223 const Point& p1 = verts[mVRef[1]];
224 const Point& p2 = verts[mVRef[2]];
225
226 // Compute base
227// Point Base = (p0 + p1 + p2)*INV3;
228
229 // Compute denormalized normal
230 Point Normal = (p2 - p1)^(p0 - p1);
231
232 // Backface culling
233// return (Normal | (source - Base)) >= 0.0f;
234 return (Normal | (source - p0)) >= 0.0f;
235
236// Same as: (but a bit faster)
237// Plane PL(verts[mVRef[0]], verts[mVRef[1]], verts[mVRef[2]]);
238// return PL.Distance(source)>0.0f;
239}
240
241///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
242/**
243 * Computes the occlusion potential of the triangle.
244 * \param verts [in] the list of indexed vertices
245 * \param source [in] source point (in local space) from which occlusion potential must be computed
246 * \return the occlusion potential
247 */
248///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
249float IndexedTriangle::ComputeOcclusionPotential(const Point* verts, const Point& view) const
250{
251 if(!verts) return 0.0f;
252 // Occlusion potential: -(A * (N|V) / d^2)
253 // A = polygon area
254 // N = polygon normal
255 // V = view vector
256 // d = distance viewpoint-center of polygon
257
258 float A = Area(verts);
259 Point N; Normal(verts, N);
260 Point C; Center(verts, C);
261 float d = view.Distance(C);
262 return -(A*(N|view))/(d*d);
263}
264
265///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
266/**
267 * Replaces a vertex reference with another one.
268 * \param oldref [in] the vertex reference to replace
269 * \param newref [in] the new vertex reference
270 * \return true if success, else false if the input vertex reference doesn't belong to the triangle
271 */
272///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
273bool IndexedTriangle::ReplaceVertex(udword oldref, udword newref)
274{
275 if(mVRef[0]==oldref) { mVRef[0] = newref; return true; }
276 else if(mVRef[1]==oldref) { mVRef[1] = newref; return true; }
277 else if(mVRef[2]==oldref) { mVRef[2] = newref; return true; }
278 return false;
279}
280
281///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
282/**
283 * Checks whether the triangle is degenerate or not. A degenerate triangle has two common vertex references. This is a zero-area triangle.
284 * \return true if the triangle is degenerate
285 */
286///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
287bool IndexedTriangle::IsDegenerate() const
288{
289 if(mVRef[0]==mVRef[1]) return true;
290 if(mVRef[1]==mVRef[2]) return true;
291 if(mVRef[2]==mVRef[0]) return true;
292 return false;
293}
294
295///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
296/**
297 * Checks whether the input vertex reference belongs to the triangle or not.
298 * \param ref [in] the vertex reference to look for
299 * \return true if the triangle contains the vertex reference
300 */
301///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
302bool IndexedTriangle::HasVertex(udword ref) const
303{
304 if(mVRef[0]==ref) return true;
305 if(mVRef[1]==ref) return true;
306 if(mVRef[2]==ref) return true;
307 return false;
308}
309
310///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
311/**
312 * Checks whether the input vertex reference belongs to the triangle or not.
313 * \param ref [in] the vertex reference to look for
314 * \param index [out] the corresponding index in the triangle
315 * \return true if the triangle contains the vertex reference
316 */
317///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
318bool IndexedTriangle::HasVertex(udword ref, udword* index) const
319{
320 if(mVRef[0]==ref) { *index = 0; return true; }
321 if(mVRef[1]==ref) { *index = 1; return true; }
322 if(mVRef[2]==ref) { *index = 2; return true; }
323 return false;
324}
325
326///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
327/**
328 * Finds an edge in a tri, given two vertex references.
329 * \param vref0 [in] the edge's first vertex reference
330 * \param vref1 [in] the edge's second vertex reference
331 * \return the edge number between 0 and 2, or 0xff if input refs are wrong.
332 */
333///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
334ubyte IndexedTriangle::FindEdge(udword vref0, udword vref1) const
335{
336 if(mVRef[0]==vref0 && mVRef[1]==vref1) return 0;
337 else if(mVRef[0]==vref1 && mVRef[1]==vref0) return 0;
338 else if(mVRef[0]==vref0 && mVRef[2]==vref1) return 1;
339 else if(mVRef[0]==vref1 && mVRef[2]==vref0) return 1;
340 else if(mVRef[1]==vref0 && mVRef[2]==vref1) return 2;
341 else if(mVRef[1]==vref1 && mVRef[2]==vref0) return 2;
342 return 0xff;
343}
344
345///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
346/**
347 * Gets the last reference given the first two.
348 * \param vref0 [in] the first vertex reference
349 * \param vref1 [in] the second vertex reference
350 * \return the last reference, or INVALID_ID if input refs are wrong.
351 */
352///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
353udword IndexedTriangle::OppositeVertex(udword vref0, udword vref1) const
354{
355 if(mVRef[0]==vref0 && mVRef[1]==vref1) return mVRef[2];
356 else if(mVRef[0]==vref1 && mVRef[1]==vref0) return mVRef[2];
357 else if(mVRef[0]==vref0 && mVRef[2]==vref1) return mVRef[1];
358 else if(mVRef[0]==vref1 && mVRef[2]==vref0) return mVRef[1];
359 else if(mVRef[1]==vref0 && mVRef[2]==vref1) return mVRef[0];
360 else if(mVRef[1]==vref1 && mVRef[2]==vref0) return mVRef[0];
361 return INVALID_ID;
362}
363
364///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
365/**
366 * Gets the three sorted vertex references according to an edge number.
367 * edgenb = 0 => edge 0-1, returns references 0, 1, 2
368 * edgenb = 1 => edge 0-2, returns references 0, 2, 1
369 * edgenb = 2 => edge 1-2, returns references 1, 2, 0
370 *
371 * \param edgenb [in] the edge number, 0, 1 or 2
372 * \param vref0 [out] the returned first vertex reference
373 * \param vref1 [out] the returned second vertex reference
374 * \param vref2 [out] the returned third vertex reference
375 */
376///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
377void IndexedTriangle::GetVRefs(ubyte edgenb, udword& vref0, udword& vref1, udword& vref2) const
378{
379 if(edgenb==0)
380 {
381 vref0 = mVRef[0];
382 vref1 = mVRef[1];
383 vref2 = mVRef[2];
384 }
385 else if(edgenb==1)
386 {
387 vref0 = mVRef[0];
388 vref1 = mVRef[2];
389 vref2 = mVRef[1];
390 }
391 else if(edgenb==2)
392 {
393 vref0 = mVRef[1];
394 vref1 = mVRef[2];
395 vref2 = mVRef[0];
396 }
397}
398
399///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
400/**
401 * Computes the triangle's smallest edge length.
402 * \param verts [in] the list of indexed vertices
403 * \return the smallest edge length
404 */
405///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
406float IndexedTriangle::MinEdgeLength(const Point* verts) const
407{
408 if(!verts) return 0.0f;
409
410 float Min = MAX_FLOAT;
411 float Length01 = verts[0].Distance(verts[1]);
412 float Length02 = verts[0].Distance(verts[2]);
413 float Length12 = verts[1].Distance(verts[2]);
414 if(Length01 < Min) Min = Length01;
415 if(Length02 < Min) Min = Length02;
416 if(Length12 < Min) Min = Length12;
417 return Min;
418}
419
420///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
421/**
422 * Computes the triangle's largest edge length.
423 * \param verts [in] the list of indexed vertices
424 * \return the largest edge length
425 */
426///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
427float IndexedTriangle::MaxEdgeLength(const Point* verts) const
428{
429 if(!verts) return 0.0f;
430
431 float Max = MIN_FLOAT;
432 float Length01 = verts[0].Distance(verts[1]);
433 float Length02 = verts[0].Distance(verts[2]);
434 float Length12 = verts[1].Distance(verts[2]);
435 if(Length01 > Max) Max = Length01;
436 if(Length02 > Max) Max = Length02;
437 if(Length12 > Max) Max = Length12;
438 return Max;
439}
440
441///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
442/**
443 * Computes a point on the triangle according to the stabbing information.
444 * \param verts [in] the list of indexed vertices
445 * \param u,v [in] point's barycentric coordinates
446 * \param pt [out] point on triangle
447 * \param nearvtx [out] index of nearest vertex
448 */
449///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
450void IndexedTriangle::ComputePoint(const Point* verts, float u, float v, Point& pt, udword* nearvtx) const
451{
452 // Checkings
453 if(!verts) return;
454
455 // Get face in local or global space
456 const Point& p0 = verts[mVRef[0]];
457 const Point& p1 = verts[mVRef[1]];
458 const Point& p2 = verts[mVRef[2]];
459
460 // Compute point coordinates
461 pt = (1.0f - u - v)*p0 + u*p1 + v*p2;
462
463 // Compute nearest vertex if needed
464 if(nearvtx)
465 {
466 // Compute distance vector
467 Point d(p0.SquareDistance(pt), // Distance^2 from vertex 0 to point on the face
468 p1.SquareDistance(pt), // Distance^2 from vertex 1 to point on the face
469 p2.SquareDistance(pt)); // Distance^2 from vertex 2 to point on the face
470
471 // Get smallest distance
472 *nearvtx = mVRef[d.SmallestAxis()];
473 }
474}
475
476 //**************************************
477 // Angle between two vectors (in radians)
478 // we use this formula
479 // uv = |u||v| cos(u,v)
480 // u ^ v = w
481 // |w| = |u||v| |sin(u,v)|
482 //**************************************
483 float Angle(const Point& u, const Point& v)
484 {
485 float NormU = u.Magnitude(); // |u|
486 float NormV = v.Magnitude(); // |v|
487 float Product = NormU*NormV; // |u||v|
488 if(Product==0.0f) return 0.0f;
489 float OneOverProduct = 1.0f / Product;
490
491 // Cosinus
492 float Cosinus = (u|v) * OneOverProduct;
493
494 // Sinus
495 Point w = u^v;
496 float NormW = w.Magnitude();
497
498 float AbsSinus = NormW * OneOverProduct;
499
500 // Remove degeneracy
501 if(AbsSinus > 1.0f) AbsSinus = 1.0f;
502 if(AbsSinus < -1.0f) AbsSinus = -1.0f;
503
504 if(Cosinus>=0.0f) return asinf(AbsSinus);
505 else return (PI-asinf(AbsSinus));
506 }
507
508///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
509/**
510 * Computes the angle between two triangles.
511 * \param tri [in] the other triangle
512 * \param verts [in] the list of indexed vertices
513 * \return the angle in radians
514 */
515///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
516float IndexedTriangle::Angle(const IndexedTriangle& tri, const Point* verts) const
517{
518 // Checkings
519 if(!verts) return 0.0f;
520
521 // Compute face normals
522 Point n0, n1;
523 Normal(verts, n0);
524 tri.Normal(verts, n1);
525
526 // Compute angle
527 float dp = n0|n1;
528 if(dp>1.0f) return 0.0f;
529 if(dp<-1.0f) return PI;
530 return acosf(dp);
531
532// return ::Angle(n0,n1);
533}
534
535///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
536/**
537 * Checks a triangle is the same as another one.
538 * \param tri [in] the other triangle
539 * \return true if same triangle
540 */
541///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
542bool IndexedTriangle::Equal(const IndexedTriangle& tri) const
543{
544 // Test all vertex references
545 return (HasVertex(tri.mVRef[0]) &&
546 HasVertex(tri.mVRef[1]) &&
547 HasVertex(tri.mVRef[2]));
548}
generated by cgit v1.1 at 2024-11-10 04:38:10 +0000