mPolyhedron.impl.h
Engine/source/math/mPolyhedron.impl.h
Public Defines
define
ADD_POINT(p) ( numOutPoints >= maxOutPoints ) \ return 0; \ outPoints[ numOutPoints ++ ] = p;
Detailed Description
Public Defines
ADD_POINT(p) ( numOutPoints >= maxOutPoints ) \ return 0; \ outPoints[ numOutPoints ++ ] = p;
1 2//----------------------------------------------------------------------------- 3// Copyright (c) 2012 GarageGames, LLC 4// 5// Permission is hereby granted, free of charge, to any person obtaining a copy 6// of this software and associated documentation files (the "Software"), to 7// deal in the Software without restriction, including without limitation the 8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 9// sell copies of the Software, and to permit persons to whom the Software is 10// furnished to do so, subject to the following conditions: 11// 12// The above copyright notice and this permission notice shall be included in 13// all copies or substantial portions of the Software. 14// 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21// IN THE SOFTWARE. 22//----------------------------------------------------------------------------- 23 24#ifndef _MPOLYHEDRON_IMPL_H_ 25#define _MPOLYHEDRON_IMPL_H_ 26 27#include "math/mPlaneTransformer.h" 28 29 30//----------------------------------------------------------------------------- 31 32template< typename Base > 33Point3F PolyhedronImpl< Base >::getCenterPoint() const 34{ 35 const U32 numPoints = this->getNumPoints(); 36 if( numPoints == 0 ) 37 return Point3F( 0.f, 0.f, 0.f ); 38 39 const typename Base::PointType* pointList = this->getPoints(); 40 Point3F center( pointList[ 0 ] ); 41 42 for( U32 i = 1; i < numPoints; ++ i ) 43 center += pointList[ i ]; 44 45 center /= ( F32 ) numPoints; 46 return center; 47} 48 49//----------------------------------------------------------------------------- 50 51template< typename Base > 52void PolyhedronImpl< Base >::transform( const MatrixF& matrix, const Point3F& scale ) 53{ 54 // Transform points. 55 56 const U32 numPoints = this->getNumPoints(); 57 typename Base::PointType* points = this->getPoints(); 58 59 for( U32 i = 0; i < numPoints; ++ i ) 60 { 61 matrix.mulP( points[ i ] ); 62 points[ i ].convolve( scale ); 63 } 64 65 // Transform planes. 66 67 const U32 numPlanes = this->getNumPlanes(); 68 typename Base::PlaneType* planes = this->getPlanes(); 69 70 PlaneTransformer transformer; 71 transformer.set( matrix, scale ); 72 73 for( U32 i = 0; i < numPlanes; ++ i ) 74 { 75 const typename Base::PlaneType& plane = planes[ i ]; 76 77 PlaneF result; 78 transformer.transform( plane, result ); 79 planes[ i ] = result; 80 } 81} 82 83//----------------------------------------------------------------------------- 84 85template< typename Base > 86U32 PolyhedronImpl< Base >::constructIntersection( const PlaneF& plane, Point3F* outPoints, U32 maxOutPoints ) const 87{ 88 // The assumption here is that the polyhedron is entirely composed 89 // of convex polygons implicitly described by the edges, points, and planes. 90 // So, any polygon can only have one of three relations to the given plane 91 // 92 // 1) None of its edges intersect with the plane, i.e. the polygon can be ignored. 93 // 2) One of its edges lies on the plane. 94 // 2) Two of its edges intersect with the plane. 95 // 96 // Conceptually, we need to find the first face with an intersecting edge, then find 97 // another edge on the same face that is also intersecting, and then continue with the 98 // face on the opposite side of the edge. 99 100 const U32 numEdges = this->getNumEdges(); 101 const typename Base::EdgeType* edges = this->getEdges(); 102 const typename Base::PointType* points = this->getPoints(); 103 U32 numOutPoints = 0; 104 105 #define ADD_POINT( p ) \ 106 if( numOutPoints >= maxOutPoints ) \ 107 return 0; \ 108 outPoints[ numOutPoints ++ ] = p; 109 110 Point3F intersection; 111 112 S32 firstEdge = -1; 113 S32 firstFace = -1; 114 115 U32 v1 = 0; 116 U32 v2 = 0; 117 118 PlaneF::Side v1Side = PlaneF::Front; 119 PlaneF::Side v2Side = PlaneF::Front; 120 121 // Find an edge to start with. This is the first edge 122 // in the polyhedron that intersects the plane. 123 124 for( U32 i = 0; i < numEdges; ++ i ) 125 { 126 const typename Base::EdgeType& edge = edges[ i ]; 127 128 v1 = edge.vertex[ 0 ]; 129 v2 = edge.vertex[ 1 ]; 130 131 const Point3F& p1 = points[ v1 ]; 132 const Point3F& p2 = points[ v2 ]; 133 134 v1Side = plane.whichSide( p1 ); 135 v2Side = plane.whichSide( p2 ); 136 137 if( v1Side == PlaneF::On || v2Side == PlaneF::On || 138 plane.clipSegment( p1, p2, intersection ) ) 139 { 140 firstEdge = i; 141 firstFace = edge.face[ 0 ]; 142 break; 143 } 144 } 145 146 if( firstEdge == -1 ) 147 return 0; 148 149 // Slice around the faces of the polyhedron until 150 // we get back to the starting face. 151 152 U32 currentEdge = firstEdge; 153 U32 currentFace = firstFace; 154 155 do 156 { 157 // Handle the current edge. 158 159 if( v1Side == PlaneF::On && v2Side == PlaneF::On ) 160 { 161 // Both points of the edge lie on the plane. Add v2 162 // and then look for an edge that is also connected to v1 163 // *and* is connected to our current face. The other face 164 // of that edge is the one we need to continue with. 165 166 ADD_POINT( points[ v2 ] ); 167 168 for( U32 n = 0; n < numEdges; ++ n ) 169 { 170 const typename Base::EdgeType& e = edges[ n ]; 171 172 // Skip current edge. 173 if( n == currentEdge ) 174 continue; 175 176 // Skip edges not belonging to current face. 177 if( e.face[ 0 ] != currentFace && e.face[ 1 ] != currentFace ) 178 continue; 179 180 // Skip edges not connected to the current point. 181 if( e.vertex[ 0 ] != edges[ currentEdge ].vertex[ 0 ] && 182 e.vertex[ 1 ] != edges[ currentEdge ].vertex[ 0 ] ) 183 continue; 184 185 // It's our edge. Continue on with the face that 186 // isn't our current one. 187 188 if( e.face[ 0 ] == currentFace ) 189 currentFace = e.face[ 1 ]; 190 else 191 currentFace = e.face[ 0 ]; 192 currentEdge = n; 193 break; 194 } 195 } 196 else if( v1Side == PlaneF::On || v2Side == PlaneF::On ) 197 { 198 // One of the points of the current edge is on the plane. 199 // Add that point. 200 201 if( v1Side == PlaneF::On ) 202 { 203 ADD_POINT( points[ v1 ] ); 204 } 205 else 206 { 207 ADD_POINT( points[ v2 ] ); 208 } 209 210 // Find edge to continue with. 211 212 for( U32 n = 0; n < numEdges; ++ n ) 213 { 214 const typename Base::EdgeType& e = edges[ n ]; 215 216 // Skip current edge. 217 if( n == currentEdge ) 218 continue; 219 220 // Skip edges not belonging to current face. 221 if( e.face[ 0 ] != currentFace && e.face[ 1 ] != currentFace ) 222 continue; 223 224 // Skip edges connected to point that is on the plane. 225 if( v1Side == PlaneF::On ) 226 { 227 if( e.vertex[ 0 ] == v1 || e.vertex[ 1 ] == v1 ) 228 continue; 229 } 230 else 231 { 232 if( e.vertex[ 0 ] == v2 || e.vertex[ 1 ] == v2 ) 233 continue; 234 } 235 236 // Skip edges not intersecting the plane. 237 238 U32 v1new = e.vertex[ 0 ]; 239 U32 v2new = e.vertex[ 1 ]; 240 241 const Point3F& p1 = points[ v1new ]; 242 const Point3F& p2 = points[ v2new ]; 243 244 PlaneF::Side v1SideNew = plane.whichSide( p1 ); 245 PlaneF::Side v2SideNew = plane.whichSide( p2 ); 246 247 if( v1SideNew != PlaneF::On && v2SideNew != PlaneF::On && !plane.clipSegment( p1, p2, intersection ) ) 248 continue; 249 250 // It's our edge. Continue with the face on the 251 // opposite side. 252 253 if( e.face[ 0 ] == currentFace ) 254 currentFace = e.face[ 1 ]; 255 else 256 currentFace = e.face[ 0 ]; 257 currentEdge = n; 258 259 v1 = v1new; 260 v2 = v2new; 261 262 v1Side = v1SideNew; 263 v2Side = v2SideNew; 264 265 break; 266 } 267 268 // Already have computed all the data. 269 continue; 270 } 271 272 // It's a clean intersecting somewhere along the edge. Add it. 273 274 else 275 { 276 ADD_POINT( intersection ); 277 } 278 279 // Find edge to continue with. 280 281 for( U32 n = 0; n < numEdges; ++ n ) 282 { 283 const typename Base::EdgeType& e = edges[ n ]; 284 285 // Skip current edge. 286 if( n == currentEdge ) 287 continue; 288 289 // Skip edges not belonging to current face. 290 if( e.face[ 0 ] != currentFace && e.face[ 1 ] != currentFace ) 291 continue; 292 293 // Skip edges not intersecting the plane. 294 295 v1 = e.vertex[ 0 ]; 296 v2 = e.vertex[ 1 ]; 297 298 const Point3F& p1 = points[ v1 ]; 299 const Point3F& p2 = points[ v2 ]; 300 301 PlaneF::Side v1SideNew = plane.whichSide( p1 ); 302 PlaneF::Side v2SideNew = plane.whichSide( p2 ); 303 304 if( v1SideNew != PlaneF::On && v2SideNew != PlaneF::On && !plane.clipSegment( p1, p2, intersection ) ) 305 continue; 306 307 // It's our edge. Make it the current one. 308 309 if( e.face[ 0 ] == currentFace ) 310 currentFace = e.face[ 1 ]; 311 else 312 currentFace = e.face[ 0 ]; 313 currentEdge = n; 314 315 break; 316 } 317 } 318 //TODO: I guess this is insufficient; edges with vertices on the plane may lead us to take different 319 // paths depending on edge order 320 while( currentFace != firstFace && 321 currentEdge != firstEdge ); 322 323 return numOutPoints; 324 325 #undef ADD_POINT 326} 327 328//----------------------------------------------------------------------------- 329 330template< typename Base > 331template< typename IndexType > 332U32 PolyhedronImpl< Base >::extractFace( U32 plane, IndexType* outIndices, U32 maxOutIndices ) const 333{ 334 AssertFatal( plane < this->getNumPlanes(), "PolyhedronImpl::extractFace - Plane index out of range!" ); 335 336 // This method relies on the fact that vertices on the edges must be CW ordered 337 // for face[0]. If that is not the case, it is still possible to infer the correct 338 // ordering by finding one edge and a point not on the edge but still on 339 // the polygon. By constructing a plane through that edge (simple cross product) and 340 // then seeing which side the point is on, we know which direction is the right one 341 // for the polygon. The implicit CW ordering spares us from having to do that, though. 342 343 const U32 numEdges = this->getNumEdges(); 344 const Edge* edges = this->getEdges(); 345 346 // Find first edge that belongs to the plane. 347 348 const Edge* firstEdge = 0; 349 350 for( U32 i = 0; i < numEdges; ++ i ) 351 { 352 const Edge& edge = edges[ i ]; 353 if( edge.face[ 0 ] == plane || edge.face[ 1 ] == plane ) 354 { 355 firstEdge = &edge; 356 break; 357 } 358 } 359 360 // If we have found no edge, the polyhedron is degenerate, 361 // so abort. 362 363 if( !firstEdge ) 364 return 0; 365 366 // Choose vertex that begins a CCW traversal for this plane. 367 // 368 // Note that we expect the planes to be facing inwards by default so we 369 // go the opposite direction to yield a polygon facing the other way. 370 371 U32 idx = 0; 372 U32 currentVertex; 373 const Edge* currentEdge = firstEdge; 374 375 if( firstEdge->face[ 0 ] == plane ) 376 currentVertex = firstEdge->vertex[ 0 ]; 377 else 378 currentVertex = firstEdge->vertex[ 1 ]; 379 380 // Now spider along the edges until we have gathered all indices 381 // for the plane in the right order. 382 // 383 // For larger edge sets, it would be more efficient to first extract 384 // all edges for the plane and then loop only over this subset to 385 // spider along the indices. However, we tend to have small sets 386 // so it should be sufficiently fast to just loop over the original 387 // set. 388 389 U32 indexItr = 0; 390 391 do 392 { 393 // Add the vertex for the current edge. 394 395 if( idx >= maxOutIndices ) 396 return 0; 397 398 ++indexItr; 399 400 if (indexItr >= 3) 401 { 402 outIndices[idx++] = firstEdge->vertex[0]; 403 indexItr = 0; 404 } 405 406 outIndices[idx++] = currentVertex; 407 408 // Look for next edge. 409 410 for( U32 i = 0; i < numEdges; ++ i ) 411 { 412 const Edge& edge = edges[ i ]; 413 414 // Skip if we hit the edge that we are looking to continue from. 415 416 if( &edge == currentEdge ) 417 continue; 418 419 // Skip edge if it doesn't belong to the current plane. 420 421 if( edge.face[ 0 ] != plane && edge.face[ 1 ] != plane ) 422 continue; 423 424 // If edge connects to vertex we are looking for, make it 425 // the current edge and push its other vertex. 426 427 if( edge.vertex[ 0 ] == currentVertex ) 428 currentVertex = edge.vertex[ 1 ]; 429 else if( edge.vertex[ 1 ] == currentVertex ) 430 currentVertex = edge.vertex[ 0 ]; 431 else 432 continue; // Skip edge. 433 434 currentEdge = &edge; 435 break; 436 } 437 } 438 while( currentEdge != firstEdge ); 439 440 // Done. 441 442 return idx; 443} 444 445//----------------------------------------------------------------------------- 446 447template< typename Polyhedron > 448void PolyhedronData::buildBoxData( Polyhedron& poly, const MatrixF& mat, const Box3F& box, bool invertNormals ) 449{ 450 AssertFatal( poly.getNumPoints() == 8, "PolyhedronData::buildBox - Incorrect point count!" ); 451 AssertFatal( poly.getNumEdges() == 12, "PolyhedronData::buildBox - Incorrect edge count!" ); 452 AssertFatal( poly.getNumPlanes() == 6, "PolyhedronData::buildBox - Incorrect plane count!" ); 453 454 // Box is assumed to be axis aligned in the source space. 455 // Transform into geometry space. 456 457 Point3F xvec = mat.getRightVector() * box.len_x(); 458 Point3F yvec = mat.getForwardVector() * box.len_y(); 459 Point3F zvec = mat.getUpVector() * box.len_z(); 460 461 Point3F min; 462 mat.mulP( box.minExtents, &min ); 463 464 // Corner points. 465 466 typename Polyhedron::PointListType& pointList = poly.mPointList; 467 468 pointList[ 0 ] = min; // near left bottom 469 pointList[ 1 ] = min + yvec; // far left bottom 470 pointList[ 2 ] = min + xvec + yvec; // far right bottom 471 pointList[ 3 ] = min + xvec; // near right bottom 472 pointList[ 4 ] = pointList[ 0 ] + zvec; // near left top 473 pointList[ 5 ] = pointList[ 1 ] + zvec; // far left top 474 pointList[ 6 ] = pointList[ 2 ] + zvec; // far right top 475 pointList[ 7 ] = pointList[ 3 ] + zvec; // near right top 476 477 // Side planes. 478 479 typename Polyhedron::PlaneListType& planeList = poly.mPlaneList; 480 481 const F32 pos = invertNormals ? -1.f : 1.f; 482 const F32 neg = - pos; 483 484 planeList[ 0 ].set( pointList[ 0 ], xvec * pos ); // left 485 planeList[ 1 ].set( pointList[ 2 ], yvec * neg ); // far 486 planeList[ 2 ].set( pointList[ 2 ], xvec * neg ); // right 487 planeList[ 3 ].set( pointList[ 0 ], yvec * pos ); // front 488 planeList[ 4 ].set( pointList[ 0 ], zvec * pos ); // bottom 489 planeList[ 5 ].set( pointList[ 4 ], zvec * neg ); // top 490 491 // The edges are constructed so that the vertices 492 // are oriented clockwise for face[0]. 493 494 typename Polyhedron::EdgeType* edge = &poly.mEdgeList[ 0 ]; 495 496 for( U32 i = 0; i < 4; ++ i ) 497 { 498 S32 n = ( i == 3 ) ? 0: i + 1; 499 S32 p = ( i == 0 ) ? 3: i - 1; 500 501 edge->vertex[ 0 ] = !invertNormals ? n : i; 502 edge->vertex[ 1 ] = !invertNormals ? i : n; 503 edge->face[ 0 ] = i; 504 edge->face[ 1 ] = 4; 505 edge ++; 506 507 edge->vertex[ 0 ] = !invertNormals ? 4 + n : 4 + i; 508 edge->vertex[ 1 ] = !invertNormals ? 4 + i : 4 + n; 509 edge->face[ 0 ] = 5; 510 edge->face[ 1 ] = i; 511 edge ++; 512 513 edge->vertex[ 0 ] = !invertNormals ? 4 + i : i; 514 edge->vertex[ 1 ] = !invertNormals ? i : 4 + i; 515 edge->face[ 0 ] = p; 516 edge->face[ 1 ] = i; 517 edge ++; 518 } 519} 520 521#endif // _MPOLYHEDRON_IMPL_H_ 522