 |
+
+
+
+ Irrlicht 3D Engine
+
+
+
+ |
+
+
+
+
+
+
+
+
+
+
+ 
+
+ |
+
+
+
00001 // Copyright (C) 2002-2012 Nikolaus Gebhardt +00002 // This file is part of the "Irrlicht Engine". +00003 // For conditions of distribution and use, see copyright notice in irrlicht.h +00004 +00005 #ifndef __IRR_TRIANGLE_3D_H_INCLUDED__ +00006 #define __IRR_TRIANGLE_3D_H_INCLUDED__ +00007 +00008 #include "vector3d.h" +00009 #include "line3d.h" +00010 #include "plane3d.h" +00011 #include "aabbox3d.h" +00012 +00013 namespace irr +00014 { +00015 namespace core +00016 { +00017 +00019 template <class T> +00020 class triangle3d +00021 { +00022 public: +00023 +00025 triangle3d() {} +00027 triangle3d(vector3d<T> v1, vector3d<T> v2, vector3d<T> v3) : pointA(v1), pointB(v2), pointC(v3) {} +00028 +00030 bool operator==(const triangle3d<T>& other) const +00031 { +00032 return other.pointA==pointA && other.pointB==pointB && other.pointC==pointC; +00033 } +00034 +00036 bool operator!=(const triangle3d<T>& other) const +00037 { +00038 return !(*this==other); +00039 } +00040 +00042 +00044 bool isTotalInsideBox(const aabbox3d<T>& box) const +00045 { +00046 return (box.isPointInside(pointA) && +00047 box.isPointInside(pointB) && +00048 box.isPointInside(pointC)); +00049 } +00050 +00052 +00054 bool isTotalOutsideBox(const aabbox3d<T>& box) const +00055 { +00056 return ((pointA.X > box.MaxEdge.X && pointB.X > box.MaxEdge.X && pointC.X > box.MaxEdge.X) || +00057 +00058 (pointA.Y > box.MaxEdge.Y && pointB.Y > box.MaxEdge.Y && pointC.Y > box.MaxEdge.Y) || +00059 (pointA.Z > box.MaxEdge.Z && pointB.Z > box.MaxEdge.Z && pointC.Z > box.MaxEdge.Z) || +00060 (pointA.X < box.MinEdge.X && pointB.X < box.MinEdge.X && pointC.X < box.MinEdge.X) || +00061 (pointA.Y < box.MinEdge.Y && pointB.Y < box.MinEdge.Y && pointC.Y < box.MinEdge.Y) || +00062 (pointA.Z < box.MinEdge.Z && pointB.Z < box.MinEdge.Z && pointC.Z < box.MinEdge.Z)); +00063 } +00064 +00066 +00068 core::vector3d<T> closestPointOnTriangle(const core::vector3d<T>& p) const +00069 { +00070 const core::vector3d<T> rab = line3d<T>(pointA, pointB).getClosestPoint(p); +00071 const core::vector3d<T> rbc = line3d<T>(pointB, pointC).getClosestPoint(p); +00072 const core::vector3d<T> rca = line3d<T>(pointC, pointA).getClosestPoint(p); +00073 +00074 const T d1 = rab.getDistanceFrom(p); +00075 const T d2 = rbc.getDistanceFrom(p); +00076 const T d3 = rca.getDistanceFrom(p); +00077 +00078 if (d1 < d2) +00079 return d1 < d3 ? rab : rca; +00080 +00081 return d2 < d3 ? rbc : rca; +00082 } +00083 +00085 /* +00086 \param p Point to test. Assumes that this point is already +00087 on the plane of the triangle. +00088 \return True if the point is inside the triangle, otherwise false. */ +00089 bool isPointInside(const vector3d<T>& p) const +00090 { +00091 vector3d<f64> af64((f64)pointA.X, (f64)pointA.Y, (f64)pointA.Z); +00092 vector3d<f64> bf64((f64)pointB.X, (f64)pointB.Y, (f64)pointB.Z); +00093 vector3d<f64> cf64((f64)pointC.X, (f64)pointC.Y, (f64)pointC.Z); +00094 vector3d<f64> pf64((f64)p.X, (f64)p.Y, (f64)p.Z); +00095 return (isOnSameSide(pf64, af64, bf64, cf64) && +00096 isOnSameSide(pf64, bf64, af64, cf64) && +00097 isOnSameSide(pf64, cf64, af64, bf64)); +00098 } +00099 +00101 +00108 bool isPointInsideFast(const vector3d<T>& p) const +00109 { +00110 const vector3d<T> a = pointC - pointA; +00111 const vector3d<T> b = pointB - pointA; +00112 const vector3d<T> c = p - pointA; +00113 +00114 const f64 dotAA = a.dotProduct( a); +00115 const f64 dotAB = a.dotProduct( b); +00116 const f64 dotAC = a.dotProduct( c); +00117 const f64 dotBB = b.dotProduct( b); +00118 const f64 dotBC = b.dotProduct( c); +00119 +00120 // get coordinates in barycentric coordinate system +00121 const f64 invDenom = 1/(dotAA * dotBB - dotAB * dotAB); +00122 const f64 u = (dotBB * dotAC - dotAB * dotBC) * invDenom; +00123 const f64 v = (dotAA * dotBC - dotAB * dotAC ) * invDenom; +00124 +00125 // We count border-points as inside to keep downward compatibility. +00126 // Rounding-error also needed for some test-cases. +00127 return (u > -ROUNDING_ERROR_f32) && (v >= 0) && (u + v < 1+ROUNDING_ERROR_f32); +00128 +00129 } +00130 +00131 +00133 +00136 bool getIntersectionWithLimitedLine(const line3d<T>& line, +00137 vector3d<T>& outIntersection) const +00138 { +00139 return getIntersectionWithLine(line.start, +00140 line.getVector(), outIntersection) && +00141 outIntersection.isBetweenPoints(line.start, line.end); +00142 } +00143 +00144 +00146 +00154 bool getIntersectionWithLine(const vector3d<T>& linePoint, +00155 const vector3d<T>& lineVect, vector3d<T>& outIntersection) const +00156 { +00157 if (getIntersectionOfPlaneWithLine(linePoint, lineVect, outIntersection)) +00158 return isPointInside(outIntersection); +00159 +00160 return false; +00161 } +00162 +00163 +00165 +00169 bool getIntersectionOfPlaneWithLine(const vector3d<T>& linePoint, +00170 const vector3d<T>& lineVect, vector3d<T>& outIntersection) const +00171 { +00172 // Work with f64 to get more precise results (makes enough difference to be worth the casts). +00173 const vector3d<f64> linePointf64(linePoint.X, linePoint.Y, linePoint.Z); +00174 const vector3d<f64> lineVectf64(lineVect.X, lineVect.Y, lineVect.Z); +00175 vector3d<f64> outIntersectionf64; +00176 +00177 core::triangle3d<irr::f64> trianglef64(vector3d<f64>((f64)pointA.X, (f64)pointA.Y, (f64)pointA.Z) +00178 ,vector3d<f64>((f64)pointB.X, (f64)pointB.Y, (f64)pointB.Z) +00179 , vector3d<f64>((f64)pointC.X, (f64)pointC.Y, (f64)pointC.Z)); +00180 const vector3d<irr::f64> normalf64 = trianglef64.getNormal().normalize(); +00181 f64 t2; +00182 +00183 if ( core::iszero ( t2 = normalf64.dotProduct(lineVectf64) ) ) +00184 return false; +00185 +00186 f64 d = trianglef64.pointA.dotProduct(normalf64); +00187 f64 t = -(normalf64.dotProduct(linePointf64) - d) / t2; +00188 outIntersectionf64 = linePointf64 + (lineVectf64 * t); +00189 +00190 outIntersection.X = (T)outIntersectionf64.X; +00191 outIntersection.Y = (T)outIntersectionf64.Y; +00192 outIntersection.Z = (T)outIntersectionf64.Z; +00193 return true; +00194 } +00195 +00196 +00198 +00199 vector3d<T> getNormal() const +00200 { +00201 return (pointB - pointA).crossProduct(pointC - pointA); +00202 } +00203 +00205 +00210 bool isFrontFacing(const vector3d<T>& lookDirection) const +00211 { +00212 const vector3d<T> n = getNormal().normalize(); +00213 const f32 d = (f32)n.dotProduct(lookDirection); +00214 return F32_LOWER_EQUAL_0(d); +00215 } +00216 +00218 plane3d<T> getPlane() const +00219 { +00220 return plane3d<T>(pointA, pointB, pointC); +00221 } +00222 +00224 T getArea() const +00225 { +00226 return (pointB - pointA).crossProduct(pointC - pointA).getLength() * 0.5f; +00227 +00228 } +00229 +00231 void set(const core::vector3d<T>& a, const core::vector3d<T>& b, const core::vector3d<T>& c) +00232 { +00233 pointA = a; +00234 pointB = b; +00235 pointC = c; +00236 } +00237 +00239 vector3d<T> pointA; +00240 vector3d<T> pointB; +00241 vector3d<T> pointC; +00242 +00243 private: +00244 // Using f64 instead of <T> to avoid integer overflows when T=int (maybe also less floating point troubles). +00245 bool isOnSameSide(const vector3d<f64>& p1, const vector3d<f64>& p2, +00246 const vector3d<f64>& a, const vector3d<f64>& b) const +00247 { +00248 vector3d<f64> bminusa = b - a; +00249 vector3d<f64> cp1 = bminusa.crossProduct(p1 - a); +00250 vector3d<f64> cp2 = bminusa.crossProduct(p2 - a); +00251 f64 res = cp1.dotProduct(cp2); +00252 if ( res < 0 ) +00253 { +00254 // This catches some floating point troubles. +00255 // Unfortunately slightly expensive and we don't really know the best epsilon for iszero. +00256 vector3d<f64> cp1 = bminusa.normalize().crossProduct((p1 - a).normalize()); +00257 if ( core::iszero(cp1.X, (f64)ROUNDING_ERROR_f32) +00258 && core::iszero(cp1.Y, (f64)ROUNDING_ERROR_f32) +00259 && core::iszero(cp1.Z, (f64)ROUNDING_ERROR_f32) ) +00260 { +00261 res = 0.f; +00262 } +00263 } +00264 return (res >= 0.0f); +00265 } +00266 }; +00267 +00268 +00270 typedef triangle3d<f32> triangle3df; +00271 +00273 typedef triangle3d<s32> triangle3di; +00274 +00275 } // end namespace core +00276 } // end namespace irr +00277 +00278 #endif +00279 +