nel/src/3d/ray_mesh.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "std3d.h"
  18
  19 #include "nel/3d/ray_mesh.h"
  20 #include "nel/misc/vector_2f.h"
  21 #include "nel/misc/fast_mem.h"
  22 #include "nel/misc/plane.h"
  23
  24 #include "nel/3d/matrix_3x4.h"
  25
  26 using namespace NLMISC;
  27 using namespace std;
  28
  29 #ifdef DEBUG_NEW
  30 #define new DEBUG_NEW
  31 #endif
  32
  33 namespace NL3D
  34 {
  35
  36
  37 // ***************************************************************************
  38 // The number of byte to process per block
  39 const   uint    NL_BlockByteL1= 4096;
  40
  41 // Number of vertices per block to process For vertices mul
  42 uint    CRayMesh::NumCacheVertex= NL_BlockByteL1 / sizeof(CVector);
  43
  44
  45 // ***************************************************************************
  46 template<class TIndex>
  47 static bool     getRayIntersectionT(std::vector<NLMISC::CVector> &vertices, const std::vector<TIndex> &tris,
  48                                                            float &dist2D, float &distZ, bool computeDist2D)
  49 {
  50         uint    numTris= (uint)tris.size()/3;
  51         if(!numTris)
  52                 return false;
  53
  54         // test all tris
  55         const TIndex    *pTri= &tris[0];
  56         float   minSkinDistZ= FLT_MAX;
  57         for(uint i=0;i<numTris;i++)
  58         {
  59                 const CVector &p0= vertices[*(pTri++)];
  60                 const CVector &p1= vertices[*(pTri++)];
  61                 const CVector &p2= vertices[*(pTri++)];
  62
  63                 // 2D tri seg
  64                 CVector2f       p01(p1.x-p0.x, p1.y-p0.y);
  65                 CVector2f       p12(p2.x-p1.x, p2.y-p1.y);
  66                 CVector2f       p20(p0.x-p2.x, p0.y-p2.y);
  67
  68                 // If some vertices are equal (cause of graphists, or cause of projection), then  this triangle cannot
  69                 // include the ray.
  70                 // must do this, else it is bugguy (if one degenerated triangle exist, will return true for all the skin)
  71                 if(p01.isNull() || p12.isNull() || p20.isNull())
  72                         continue;
  73
  74                 /* Since the triangle is "rendered" in the ray "camera", the ray here is (Pos=Null,dir=K)
  75                         Therefore we can do fast triangle intersection test, only testing the 2D intersection in
  76                         the X/Y plane first
  77                 */
  78                 float           a,b,c;          // 2D cartesian coefficients of line in plane X/Y.
  79                 bool    allInf= true;
  80                 bool    allSup= true;
  81                 // Line p0-p1.
  82                 a= -p01.y;
  83                 b= p01.x;
  84                 c= (p0.x*a + p0.y*b);
  85                 allInf= allInf && c<=0;
  86                 allSup= allSup && c>=0;
  87                 // Line p1-p2.
  88                 a= -p12.y;
  89                 b= p12.x;
  90                 c= (p1.x*a + p1.y*b);
  91                 allInf= allInf && c<=0;
  92                 allSup= allSup && c>=0;
  93                 // Line p2-p0.
  94                 a= -p20.y;
  95                 b= p20.x;
  96                 c= (p2.x*a + p2.y*b);
  97                 allInf= allInf && c<=0;
  98                 allSup= allSup && c>=0;
  99
 100                 // all on same side (don't bother front or backfaces)?
 101                 if(allInf || allSup)
 102                 {
 103                         // => ray intersect. compute the intersection now.
 104                         // This code is called for a very small subset of faces, hence don't bother optim.
 105                         CPlane  plane;
 106                         plane.make(p0,p1,p2);
 107                         // intersect with the ray. Since vertices are in ray basis, the Ray is (Null, K).
 108                         CVector hit= plane.intersect(CVector::Null, CVector::K);
 109                         // then dist of Null to the tri is just Z.
 110                         float   distToTri= hit.z;
 111                         // avoid problems if the plane is // to the ray. take maximum proj dist with the 3 points
 112                         float   minVertDist= min(p0.z, p1.z);
 113                         minVertDist= min(minVertDist, p2.z);
 114                         // distToTri cannot be less than minVertDist
 115                         distToTri= max(minVertDist, distToTri);
 116
 117                         // NB: it is possible than distToTri<0 (face behind or clipped by camera). clamp then to 0
 118                         distToTri= max(distToTri, 0.f);
 119                         minSkinDistZ= min(minSkinDistZ, distToTri);
 120                 }
 121         }
 122
 123         // don't intersect?
 124         if(minSkinDistZ==FLT_MAX)
 125         {
 126                 // get the nearest distance to the ray (do the compute only if no IT found at all => optim)
 127                 const TIndex    *pTri= &tris[0];
 128                 float   minSkinSqrDist2D= FLT_MAX;
 129
 130                 // only if user want this feature
 131                 if(computeDist2D)
 132                 {
 133                         for(uint i=0;i<numTris;i++)
 134                         {
 135                                 const CVector &p0= vertices[*(pTri++)];
 136                                 const CVector &p1= vertices[*(pTri++)];
 137                                 const CVector &p2= vertices[*(pTri++)];
 138
 139                                 // 2D tri seg
 140                                 CVector2f       p01(p1.x-p0.x, p1.y-p0.y);
 141                                 CVector2f       p12(p2.x-p1.x, p2.y-p1.y);
 142                                 CVector2f       p20(p0.x-p2.x, p0.y-p2.y);
 143
 144                                 // If some vertices are equal (cause of graphists, or cause of projection), then  this triangle cannot
 145                                 // include the ray.
 146                                 // must do this, else it is bugguy (if one degenerated triangle exist, will return true for all the skin)
 147                                 if(p01.isNull() || p12.isNull() || p20.isNull())
 148                                         continue;
 149
 150                                 // compute the min dist to the ray
 151                                 // ** Min 2D vert dist to Center(Null)
 152                                 float   p0sqdist= sqr(p0.x) + sqr(p0.y);
 153                                 float   p1sqdist= sqr(p1.x) + sqr(p1.y);
 154                                 float   p2sqdist= sqr(p2.x) + sqr(p2.y);
 155                                 float   sqdTri= min(p0sqdist, p1sqdist);
 156                                 sqdTri= min(sqdTri, p2sqdist);
 157                                 // ** Minimize with segment dist
 158                                 // compute 2D segment sqrdist
 159                                 float   p01sqdist= sqr(p01.x) + sqr(p01.y);
 160                                 float   p12sqdist= sqr(p12.x) + sqr(p12.y);
 161                                 float   p20sqdist= sqr(p20.x) + sqr(p20.y);
 162                                 float   fSeg;
 163                                 // project Null onto segment (Null-p0)*(p1-p0) => value between 0 and p01sqdist (if in segment)
 164                                 fSeg= -p0.x*p01.x -p0.y*p01.y;
 165                                 if(fSeg>0 && fSeg<p01sqdist)
 166                                 {
 167                                         // project on segment
 168                                         CVector2f       pProj= CVector2f(p0) + p01*(fSeg/p01sqdist);
 169                                         // min sq dist of tri with (Null-pProj)
 170                                         sqdTri= min(sqdTri, pProj.sqrnorm());
 171                                 }
 172                                 // same for p12
 173                                 fSeg= -p1.x*p12.x -p1.y*p12.y;
 174                                 if(fSeg>0 && fSeg<p12sqdist)
 175                                 {
 176                                         CVector2f       pProj= CVector2f(p1) + p12*(fSeg/p12sqdist);
 177                                         sqdTri= min(sqdTri, pProj.sqrnorm());
 178                                 }
 179                                 // same for p20
 180                                 fSeg= -p2.x*p20.x -p2.y*p20.y;
 181                                 if(fSeg>0 && fSeg<p20sqdist)
 182                                 {
 183                                         CVector2f       pProj= CVector2f(p2) + p20*(fSeg/p20sqdist);
 184                                         sqdTri= min(sqdTri, pProj.sqrnorm());
 185                                 }
 186
 187                                 // ** minimize with the whole 2D skin dist
 188                                 minSkinSqrDist2D= min(minSkinSqrDist2D, sqdTri);
 189                         }
 190                 }
 191
 192
 193                 // NB: in case of all degenerated triangles FLT_MAX is return...)
 194                 if(minSkinSqrDist2D==FLT_MAX)
 195                         dist2D= FLT_MAX;
 196                 else
 197                         dist2D= sqrtf(minSkinSqrDist2D);
 198                 distZ= 0.f;
 199         }
 200         else
 201         {
 202                 dist2D= 0.f;
 203                 distZ= minSkinDistZ;
 204         }
 205
 206         return true;
 207 }
 208
 209
 210 // ***************************************************************************
 211 bool            CRayMesh::getRayIntersection(std::vector<NLMISC::CVector> &vertices, const std::vector<uint32> &tris,
 212                 float &dist2D, float &distZ, bool computeDist2D)
 213 {
 214         return getRayIntersectionT(vertices, tris, dist2D, distZ, computeDist2D);
 215 }
 216
 217
 218 // ***************************************************************************
 219 bool            CRayMesh::getRayIntersection(std::vector<NLMISC::CVector> &vertices, const std::vector<uint16> &tris,
 220                 float &dist2D, float &distZ, bool computeDist2D)
 221 {
 222         return getRayIntersectionT(vertices, tris, dist2D, distZ, computeDist2D);
 223 }
 224
 225
 226 // ***************************************************************************
 227 bool            CRayMesh::fastIntersect(const NLMISC::CMatrix &worldMatrix, const NLMISC::CVector &p0, const NLMISC::CVector &dir, float &dist2D, float &distZ, bool computeDist2D) const
 228 {
 229         if(empty())
 230                 return false;
 231
 232
 233         // *** Compute toRaySpace matrix
 234         // The skinning must be done in final RaySpace.
 235         CMatrix         toRaySpace;
 236         // compute the ray matrix
 237         CVector dirn= dir;
 238         if(dirn.isNull())
 239                 dirn= CVector::K;
 240         dirn.normalize();
 241         toRaySpace.setArbitraryRotK(dirn);
 242         toRaySpace.setPos(p0);
 243         // The skinning must be done in ray space: (RayMat-1)*worldMatrix;
 244         toRaySpace.invert();
 245         toRaySpace*= worldMatrix;
 246
 247         CMatrix3x4              fastMat;
 248         fastMat.set(toRaySpace);
 249
 250
 251         // *** Make all points in ray space
 252         uint    numVerts= (uint)Vertices.size();
 253         const CVector   *src= &Vertices[0];
 254         // enlarge temp buffer
 255         static std::vector<CVector>     meshInRaySpace;
 256         if(Vertices.size()>meshInRaySpace.size())
 257                 meshInRaySpace.resize(Vertices.size());
 258         CVector *dst= &meshInRaySpace[0];
 259
 260         // Then do the skin
 261         for(;numVerts>0;)
 262         {
 263                 // number of vertices to process for this block.
 264                 uint    nBlockInf= min(NumCacheVertex, numVerts);
 265                 // next block.
 266                 numVerts-= nBlockInf;
 267
 268                 // cache the data in L1 cache.
 269                 CFastMem::precache(src, nBlockInf * sizeof(CVector));
 270
 271                 //  for all InfluencedVertices only.
 272                 for(;nBlockInf>0;nBlockInf--, src++, dst++)
 273                 {
 274                         fastMat.mulSetPoint( *src, *dst );
 275                 }
 276         }
 277
 278
 279         // *** and get ray intersection
 280         return getRayIntersection(meshInRaySpace, Triangles, dist2D, distZ, computeDist2D);
 281 }
 282
 283
 284 } // NL3D