diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/irrlicht-1.8.1/include/triangle3d.h | 279 |
1 files changed, 279 insertions, 0 deletions
diff --git a/libraries/irrlicht-1.8.1/include/triangle3d.h b/libraries/irrlicht-1.8.1/include/triangle3d.h new file mode 100644 index 0000000..2f5a36c --- /dev/null +++ b/libraries/irrlicht-1.8.1/include/triangle3d.h | |||
@@ -0,0 +1,279 @@ | |||
1 | // Copyright (C) 2002-2012 Nikolaus Gebhardt | ||
2 | // This file is part of the "Irrlicht Engine". | ||
3 | // For conditions of distribution and use, see copyright notice in irrlicht.h | ||
4 | |||
5 | #ifndef __IRR_TRIANGLE_3D_H_INCLUDED__ | ||
6 | #define __IRR_TRIANGLE_3D_H_INCLUDED__ | ||
7 | |||
8 | #include "vector3d.h" | ||
9 | #include "line3d.h" | ||
10 | #include "plane3d.h" | ||
11 | #include "aabbox3d.h" | ||
12 | |||
13 | namespace irr | ||
14 | { | ||
15 | namespace core | ||
16 | { | ||
17 | |||
18 | //! 3d triangle template class for doing collision detection and other things. | ||
19 | template <class T> | ||
20 | class triangle3d | ||
21 | { | ||
22 | public: | ||
23 | |||
24 | //! Constructor for an all 0 triangle | ||
25 | triangle3d() {} | ||
26 | //! Constructor for triangle with given three vertices | ||
27 | triangle3d(vector3d<T> v1, vector3d<T> v2, vector3d<T> v3) : pointA(v1), pointB(v2), pointC(v3) {} | ||
28 | |||
29 | //! Equality operator | ||
30 | bool operator==(const triangle3d<T>& other) const | ||
31 | { | ||
32 | return other.pointA==pointA && other.pointB==pointB && other.pointC==pointC; | ||
33 | } | ||
34 | |||
35 | //! Inequality operator | ||
36 | bool operator!=(const triangle3d<T>& other) const | ||
37 | { | ||
38 | return !(*this==other); | ||
39 | } | ||
40 | |||
41 | //! Determines if the triangle is totally inside a bounding box. | ||
42 | /** \param box Box to check. | ||
43 | \return True if triangle is within the box, otherwise false. */ | ||
44 | bool isTotalInsideBox(const aabbox3d<T>& box) const | ||
45 | { | ||
46 | return (box.isPointInside(pointA) && | ||
47 | box.isPointInside(pointB) && | ||
48 | box.isPointInside(pointC)); | ||
49 | } | ||
50 | |||
51 | //! Determines if the triangle is totally outside a bounding box. | ||
52 | /** \param box Box to check. | ||
53 | \return True if triangle is outside the box, otherwise false. */ | ||
54 | bool isTotalOutsideBox(const aabbox3d<T>& box) const | ||
55 | { | ||
56 | return ((pointA.X > box.MaxEdge.X && pointB.X > box.MaxEdge.X && pointC.X > box.MaxEdge.X) || | ||
57 | |||
58 | (pointA.Y > box.MaxEdge.Y && pointB.Y > box.MaxEdge.Y && pointC.Y > box.MaxEdge.Y) || | ||
59 | (pointA.Z > box.MaxEdge.Z && pointB.Z > box.MaxEdge.Z && pointC.Z > box.MaxEdge.Z) || | ||
60 | (pointA.X < box.MinEdge.X && pointB.X < box.MinEdge.X && pointC.X < box.MinEdge.X) || | ||
61 | (pointA.Y < box.MinEdge.Y && pointB.Y < box.MinEdge.Y && pointC.Y < box.MinEdge.Y) || | ||
62 | (pointA.Z < box.MinEdge.Z && pointB.Z < box.MinEdge.Z && pointC.Z < box.MinEdge.Z)); | ||
63 | } | ||
64 | |||
65 | //! Get the closest point on a triangle to a point on the same plane. | ||
66 | /** \param p Point which must be on the same plane as the triangle. | ||
67 | \return The closest point of the triangle */ | ||
68 | core::vector3d<T> closestPointOnTriangle(const core::vector3d<T>& p) const | ||
69 | { | ||
70 | const core::vector3d<T> rab = line3d<T>(pointA, pointB).getClosestPoint(p); | ||
71 | const core::vector3d<T> rbc = line3d<T>(pointB, pointC).getClosestPoint(p); | ||
72 | const core::vector3d<T> rca = line3d<T>(pointC, pointA).getClosestPoint(p); | ||
73 | |||
74 | const T d1 = rab.getDistanceFrom(p); | ||
75 | const T d2 = rbc.getDistanceFrom(p); | ||
76 | const T d3 = rca.getDistanceFrom(p); | ||
77 | |||
78 | if (d1 < d2) | ||
79 | return d1 < d3 ? rab : rca; | ||
80 | |||
81 | return d2 < d3 ? rbc : rca; | ||
82 | } | ||
83 | |||
84 | //! Check if a point is inside the triangle (border-points count also as inside) | ||
85 | /* | ||
86 | \param p Point to test. Assumes that this point is already | ||
87 | on the plane of the triangle. | ||
88 | \return True if the point is inside the triangle, otherwise false. */ | ||
89 | bool isPointInside(const vector3d<T>& p) const | ||
90 | { | ||
91 | vector3d<f64> af64((f64)pointA.X, (f64)pointA.Y, (f64)pointA.Z); | ||
92 | vector3d<f64> bf64((f64)pointB.X, (f64)pointB.Y, (f64)pointB.Z); | ||
93 | vector3d<f64> cf64((f64)pointC.X, (f64)pointC.Y, (f64)pointC.Z); | ||
94 | vector3d<f64> pf64((f64)p.X, (f64)p.Y, (f64)p.Z); | ||
95 | return (isOnSameSide(pf64, af64, bf64, cf64) && | ||
96 | isOnSameSide(pf64, bf64, af64, cf64) && | ||
97 | isOnSameSide(pf64, cf64, af64, bf64)); | ||
98 | } | ||
99 | |||
100 | //! Check if a point is inside the triangle (border-points count also as inside) | ||
101 | /** This method uses a barycentric coordinate system. | ||
102 | It is faster than isPointInside but is more susceptible to floating point rounding | ||
103 | errors. This will especially be noticable when the FPU is in single precision mode | ||
104 | (which is for example set on default by Direct3D). | ||
105 | \param p Point to test. Assumes that this point is already | ||
106 | on the plane of the triangle. | ||
107 | \return True if point is inside the triangle, otherwise false. */ | ||
108 | bool isPointInsideFast(const vector3d<T>& p) const | ||
109 | { | ||
110 | const vector3d<T> a = pointC - pointA; | ||
111 | const vector3d<T> b = pointB - pointA; | ||
112 | const vector3d<T> c = p - pointA; | ||
113 | |||
114 | const f64 dotAA = a.dotProduct( a); | ||
115 | const f64 dotAB = a.dotProduct( b); | ||
116 | const f64 dotAC = a.dotProduct( c); | ||
117 | const f64 dotBB = b.dotProduct( b); | ||
118 | const f64 dotBC = b.dotProduct( c); | ||
119 | |||
120 | // get coordinates in barycentric coordinate system | ||
121 | const f64 invDenom = 1/(dotAA * dotBB - dotAB * dotAB); | ||
122 | const f64 u = (dotBB * dotAC - dotAB * dotBC) * invDenom; | ||
123 | const f64 v = (dotAA * dotBC - dotAB * dotAC ) * invDenom; | ||
124 | |||
125 | // We count border-points as inside to keep downward compatibility. | ||
126 | // Rounding-error also needed for some test-cases. | ||
127 | return (u > -ROUNDING_ERROR_f32) && (v >= 0) && (u + v < 1+ROUNDING_ERROR_f32); | ||
128 | |||
129 | } | ||
130 | |||
131 | |||
132 | //! Get an intersection with a 3d line. | ||
133 | /** \param line Line to intersect with. | ||
134 | \param outIntersection Place to store the intersection point, if there is one. | ||
135 | \return True if there was an intersection, false if not. */ | ||
136 | bool getIntersectionWithLimitedLine(const line3d<T>& line, | ||
137 | vector3d<T>& outIntersection) const | ||
138 | { | ||
139 | return getIntersectionWithLine(line.start, | ||
140 | line.getVector(), outIntersection) && | ||
141 | outIntersection.isBetweenPoints(line.start, line.end); | ||
142 | } | ||
143 | |||
144 | |||
145 | //! Get an intersection with a 3d line. | ||
146 | /** Please note that also points are returned as intersection which | ||
147 | are on the line, but not between the start and end point of the line. | ||
148 | If you want the returned point be between start and end | ||
149 | use getIntersectionWithLimitedLine(). | ||
150 | \param linePoint Point of the line to intersect with. | ||
151 | \param lineVect Vector of the line to intersect with. | ||
152 | \param outIntersection Place to store the intersection point, if there is one. | ||
153 | \return True if there was an intersection, false if there was not. */ | ||
154 | bool getIntersectionWithLine(const vector3d<T>& linePoint, | ||
155 | const vector3d<T>& lineVect, vector3d<T>& outIntersection) const | ||
156 | { | ||
157 | if (getIntersectionOfPlaneWithLine(linePoint, lineVect, outIntersection)) | ||
158 | return isPointInside(outIntersection); | ||
159 | |||
160 | return false; | ||
161 | } | ||
162 | |||
163 | |||
164 | //! Calculates the intersection between a 3d line and the plane the triangle is on. | ||
165 | /** \param lineVect Vector of the line to intersect with. | ||
166 | \param linePoint Point of the line to intersect with. | ||
167 | \param outIntersection Place to store the intersection point, if there is one. | ||
168 | \return True if there was an intersection, else false. */ | ||
169 | bool getIntersectionOfPlaneWithLine(const vector3d<T>& linePoint, | ||
170 | const vector3d<T>& lineVect, vector3d<T>& outIntersection) const | ||
171 | { | ||
172 | // Work with f64 to get more precise results (makes enough difference to be worth the casts). | ||
173 | const vector3d<f64> linePointf64(linePoint.X, linePoint.Y, linePoint.Z); | ||
174 | const vector3d<f64> lineVectf64(lineVect.X, lineVect.Y, lineVect.Z); | ||
175 | vector3d<f64> outIntersectionf64; | ||
176 | |||
177 | core::triangle3d<irr::f64> trianglef64(vector3d<f64>((f64)pointA.X, (f64)pointA.Y, (f64)pointA.Z) | ||
178 | ,vector3d<f64>((f64)pointB.X, (f64)pointB.Y, (f64)pointB.Z) | ||
179 | , vector3d<f64>((f64)pointC.X, (f64)pointC.Y, (f64)pointC.Z)); | ||
180 | const vector3d<irr::f64> normalf64 = trianglef64.getNormal().normalize(); | ||
181 | f64 t2; | ||
182 | |||
183 | if ( core::iszero ( t2 = normalf64.dotProduct(lineVectf64) ) ) | ||
184 | return false; | ||
185 | |||
186 | f64 d = trianglef64.pointA.dotProduct(normalf64); | ||
187 | f64 t = -(normalf64.dotProduct(linePointf64) - d) / t2; | ||
188 | outIntersectionf64 = linePointf64 + (lineVectf64 * t); | ||
189 | |||
190 | outIntersection.X = (T)outIntersectionf64.X; | ||
191 | outIntersection.Y = (T)outIntersectionf64.Y; | ||
192 | outIntersection.Z = (T)outIntersectionf64.Z; | ||
193 | return true; | ||
194 | } | ||
195 | |||
196 | |||
197 | //! Get the normal of the triangle. | ||
198 | /** Please note: The normal is not always normalized. */ | ||
199 | vector3d<T> getNormal() const | ||
200 | { | ||
201 | return (pointB - pointA).crossProduct(pointC - pointA); | ||
202 | } | ||
203 | |||
204 | //! Test if the triangle would be front or backfacing from any point. | ||
205 | /** Thus, this method assumes a camera position from which the | ||
206 | triangle is definitely visible when looking at the given direction. | ||
207 | Do not use this method with points as it will give wrong results! | ||
208 | \param lookDirection Look direction. | ||
209 | \return True if the plane is front facing and false if it is backfacing. */ | ||
210 | bool isFrontFacing(const vector3d<T>& lookDirection) const | ||
211 | { | ||
212 | const vector3d<T> n = getNormal().normalize(); | ||
213 | const f32 d = (f32)n.dotProduct(lookDirection); | ||
214 | return F32_LOWER_EQUAL_0(d); | ||
215 | } | ||
216 | |||
217 | //! Get the plane of this triangle. | ||
218 | plane3d<T> getPlane() const | ||
219 | { | ||
220 | return plane3d<T>(pointA, pointB, pointC); | ||
221 | } | ||
222 | |||
223 | //! Get the area of the triangle | ||
224 | T getArea() const | ||
225 | { | ||
226 | return (pointB - pointA).crossProduct(pointC - pointA).getLength() * 0.5f; | ||
227 | |||
228 | } | ||
229 | |||
230 | //! sets the triangle's points | ||
231 | void set(const core::vector3d<T>& a, const core::vector3d<T>& b, const core::vector3d<T>& c) | ||
232 | { | ||
233 | pointA = a; | ||
234 | pointB = b; | ||
235 | pointC = c; | ||
236 | } | ||
237 | |||
238 | //! the three points of the triangle | ||
239 | vector3d<T> pointA; | ||
240 | vector3d<T> pointB; | ||
241 | vector3d<T> pointC; | ||
242 | |||
243 | private: | ||
244 | // Using f64 instead of <T> to avoid integer overflows when T=int (maybe also less floating point troubles). | ||
245 | bool isOnSameSide(const vector3d<f64>& p1, const vector3d<f64>& p2, | ||
246 | const vector3d<f64>& a, const vector3d<f64>& b) const | ||
247 | { | ||
248 | vector3d<f64> bminusa = b - a; | ||
249 | vector3d<f64> cp1 = bminusa.crossProduct(p1 - a); | ||
250 | vector3d<f64> cp2 = bminusa.crossProduct(p2 - a); | ||
251 | f64 res = cp1.dotProduct(cp2); | ||
252 | if ( res < 0 ) | ||
253 | { | ||
254 | // This catches some floating point troubles. | ||
255 | // Unfortunately slightly expensive and we don't really know the best epsilon for iszero. | ||
256 | vector3d<f64> cp1 = bminusa.normalize().crossProduct((p1 - a).normalize()); | ||
257 | if ( core::iszero(cp1.X, (f64)ROUNDING_ERROR_f32) | ||
258 | && core::iszero(cp1.Y, (f64)ROUNDING_ERROR_f32) | ||
259 | && core::iszero(cp1.Z, (f64)ROUNDING_ERROR_f32) ) | ||
260 | { | ||
261 | res = 0.f; | ||
262 | } | ||
263 | } | ||
264 | return (res >= 0.0f); | ||
265 | } | ||
266 | }; | ||
267 | |||
268 | |||
269 | //! Typedef for a f32 3d triangle. | ||
270 | typedef triangle3d<f32> triangle3df; | ||
271 | |||
272 | //! Typedef for an integer 3d triangle. | ||
273 | typedef triangle3d<s32> triangle3di; | ||
274 | |||
275 | } // end namespace core | ||
276 | } // end namespace irr | ||
277 | |||
278 | #endif | ||
279 | |||