include/triangle3d.h

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