Irrlicht 3D Engine
triangle3d.h
Go to the documentation of this file.
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 
19  template <class T>
20  class triangle3d
21  {
22  public:
23 
27  triangle3d(const vector3d<T>& v1, const vector3d<T>& v2, const vector3d<T>& v3) : pointA(v1), pointB(v2), pointC(v3) {}
28 
30  bool operator==(const triangle3d<T>& other) const
31  {
32  return other.pointA==pointA && other.pointB==pointB && other.pointC==pointC;
33  }
34 
36  bool operator!=(const triangle3d<T>& other) const
37  {
38  return !(*this==other);
39  }
40 
42 
44  bool isTotalInsideBox(const aabbox3d<T>& box) const
45  {
46  return (box.isPointInside(pointA) &&
47  box.isPointInside(pointB) &&
48  box.isPointInside(pointC));
49  }
50 
52 
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 
66 
69  {
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 
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 
101 
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 
133 
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 
146 
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 
165 
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 
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 
198 
200  {
201  return (pointB - pointA).crossProduct(pointC - pointA);
202  }
203 
205 
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 
219  {
220  return plane3d<T>(pointA, pointB, pointC);
221  }
222 
224  T getArea() const
225  {
226  return (pointB - pointA).crossProduct(pointC - pointA).getLength() * 0.5f;
227 
228  }
229 
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 
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());
260  {
261  res = 0.f;
262  }
263  }
264  return (res >= 0.0f);
265  }
266  };
267 
268 
271 
274 
275 } // end namespace core
276 } // end namespace irr
277 
278 #endif
279 
vector3d< T > crossProduct(const vector3d< T > &p) const
Calculates the cross product with another vector.
Definition: vector3d.h:147
vector3d< T > MaxEdge
The far edge.
Definition: aabbox3d.h:357
T Y
Y coordinate of the vector.
Definition: vector3d.h:413
bool iszero(const f64 a, const f64 tolerance=ROUNDING_ERROR_f64)
returns if a equals zero, taking rounding errors into account
Definition: irrMath.h:307
bool isTotalInsideBox(const aabbox3d< T > &box) const
Determines if the triangle is totally inside a bounding box.
Definition: triangle3d.h:44
vector3d< T > getClosestPoint(const vector3d< T > &point) const
Get the closest point on this line to a point.
Definition: line3d.h:89
float f32
32 bit floating point variable.
Definition: irrTypes.h:108
triangle3d()
Constructor for an all 0 triangle.
Definition: triangle3d.h:25
bool getIntersectionOfPlaneWithLine(const vector3d< T > &linePoint, const vector3d< T > &lineVect, vector3d< T > &outIntersection) const
Calculates the intersection between a 3d line and the plane the triangle is on.
Definition: triangle3d.h:169
3d triangle template class for doing collision detection and other things.
Definition: triangle3d.h:20
T X
X coordinate of the vector.
Definition: vector3d.h:410
Everything in the Irrlicht Engine can be found in this namespace.
Definition: aabbox3d.h:12
bool isPointInside(const vector3d< T > &p) const
Determines if a point is within this box.
Definition: aabbox3d.h:219
triangle3d< f32 > triangle3df
Typedef for a f32 3d triangle.
Definition: triangle3d.h:270
3d vector template class with lots of operators and methods.
Definition: vector3d.h:22
bool getIntersectionWithLine(const vector3d< T > &linePoint, const vector3d< T > &lineVect, vector3d< T > &outIntersection) const
Get an intersection with a 3d line.
Definition: triangle3d.h:154
3D line between two points with intersection methods.
Definition: line3d.h:18
double f64
64 bit floating point variable.
Definition: irrTypes.h:112
bool isFrontFacing(const vector3d< T > &lookDirection) const
Test if the triangle would be front or backfacing from any point.
Definition: triangle3d.h:210
vector3d< T > pointA
the three points of the triangle
Definition: triangle3d.h:239
vector3d< T > pointB
Definition: triangle3d.h:240
vector3d< T > getVector() const
Get vector of line.
Definition: line3d.h:71
bool isTotalOutsideBox(const aabbox3d< T > &box) const
Determines if the triangle is totally outside a bounding box.
Definition: triangle3d.h:54
void set(const core::vector3d< T > &a, const core::vector3d< T > &b, const core::vector3d< T > &c)
sets the triangle's points
Definition: triangle3d.h:231
const f32 ROUNDING_ERROR_f32
Definition: irrMath.h:50
plane3d< T > getPlane() const
Get the plane of this triangle.
Definition: triangle3d.h:218
vector3d< T > end
End point of line.
Definition: line3d.h:132
triangle3d(const vector3d< T > &v1, const vector3d< T > &v2, const vector3d< T > &v3)
Constructor for triangle with given three vertices.
Definition: triangle3d.h:27
bool operator!=(const triangle3d< T > &other) const
Inequality operator.
Definition: triangle3d.h:36
Template plane class with some intersection testing methods.
Definition: plane3d.h:33
T getArea() const
Get the area of the triangle.
Definition: triangle3d.h:224
triangle3d< s32 > triangle3di
Typedef for an integer 3d triangle.
Definition: triangle3d.h:273
bool isPointInside(const vector3d< T > &p) const
Check if a point is inside the triangle (border-points count also as inside)
Definition: triangle3d.h:89
vector3d< T > & normalize()
Normalizes the vector.
Definition: vector3d.h:168
bool operator==(const triangle3d< T > &other) const
Equality operator.
Definition: triangle3d.h:30
vector3d< T > MinEdge
The near edge.
Definition: aabbox3d.h:354
bool isPointInsideFast(const vector3d< T > &p) const
Check if a point is inside the triangle (border-points count also as inside)
Definition: triangle3d.h:108
vector3d< T > start
Start point of line.
Definition: line3d.h:130
T dotProduct(const vector3d< T > &other) const
Get the dot product with another vector.
Definition: vector3d.h:125
core::vector3d< T > closestPointOnTriangle(const core::vector3d< T > &p) const
Get the closest point on a triangle to a point on the same plane.
Definition: triangle3d.h:68
T Z
Z coordinate of the vector.
Definition: vector3d.h:416
bool isBetweenPoints(const vector3d< T > &begin, const vector3d< T > &end) const
Returns if this vector interpreted as a point is on a line between two other points.
Definition: vector3d.h:157
T getDistanceFrom(const vector3d< T > &other) const
Get distance from another point.
Definition: vector3d.h:132
Axis aligned bounding box in 3d dimensional space.
Definition: aabbox3d.h:21
vector3d< T > pointC
Definition: triangle3d.h:241
bool getIntersectionWithLimitedLine(const line3d< T > &line, vector3d< T > &outIntersection) const
Get an intersection with a 3d line.
Definition: triangle3d.h:136
vector3d< T > getNormal() const
Get the normal of the triangle.
Definition: triangle3d.h:199
#define F32_LOWER_EQUAL_0(n)
Definition: irrMath.h:423