optimizedPolyList.cpp
Engine/source/collision/optimizedPolyList.cpp
Detailed Description
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#include "math/mMath.h" 25#include "core/color.h" 26#include "console/console.h" 27#include "collision/optimizedPolyList.h" 28#include "materials/baseMatInstance.h" 29#include "materials/materialDefinition.h" 30 31//---------------------------------------------------------------------------- 32 33OptimizedPolyList::OptimizedPolyList() 34{ 35 VECTOR_SET_ASSOCIATION(mPoints); 36 VECTOR_SET_ASSOCIATION(mNormals); 37 VECTOR_SET_ASSOCIATION(mUV0s); 38 VECTOR_SET_ASSOCIATION(mUV1s); 39 VECTOR_SET_ASSOCIATION(mVertexList); 40 VECTOR_SET_ASSOCIATION(mIndexList); 41 VECTOR_SET_ASSOCIATION(mPlaneList); 42 VECTOR_SET_ASSOCIATION(mPolyList); 43 44 mIndexList.reserve(100); 45 46 mCurrObject = NULL; 47 mBaseMatrix = MatrixF::Identity; 48 mMatrix = MatrixF::Identity; 49 mTransformMatrix = MatrixF::Identity; 50 mScale.set(1.0f, 1.0f, 1.0f); 51 52 mPlaneTransformer.setIdentity(); 53 54 mInterestNormalRegistered = false; 55} 56 57OptimizedPolyList::~OptimizedPolyList() 58{ 59 mPoints.clear(); 60 mNormals.clear(); 61 mUV0s.clear(); 62 mUV1s.clear(); 63 mVertexList.clear(); 64 mIndexList.clear(); 65 mPlaneList.clear(); 66 mPolyList.clear(); 67} 68 69 70//---------------------------------------------------------------------------- 71void OptimizedPolyList::clear() 72{ 73 mPoints.clear(); 74 mNormals.clear(); 75 mUV0s.clear(); 76 mUV1s.clear(); 77 mVertexList.clear(); 78 mIndexList.clear(); 79 mPlaneList.clear(); 80 mPolyList.clear(); 81} 82 83//---------------------------------------------------------------------------- 84U32 OptimizedPolyList::insertPoint(const Point3F& point) 85{ 86 S32 retIdx = -1; 87 88 // Apply the transform 89 Point3F transPoint = point; 90 transPoint *= mScale; 91 mMatrix.mulP(transPoint); 92 93 for (U32 i = 0; i < mPoints.size(); i++) 94 { 95 if (mPoints[i].equal(transPoint)) 96 { 97 retIdx = i; 98 break; 99 } 100 } 101 102 if (retIdx == -1) 103 { 104 retIdx = mPoints.size(); 105 mPoints.push_back(transPoint); 106 } 107 108 return (U32)retIdx; 109} 110 111U32 OptimizedPolyList::insertNormal(const Point3F& normal) 112{ 113 S32 retIdx = -1; 114 115 // Apply the transform 116 Point3F transNormal; 117 mMatrix.mulV( normal, &transNormal ); 118 119 for (U32 i = 0; i < mNormals.size(); i++) 120 { 121 if (mNormals[i].equal(transNormal)) 122 { 123 retIdx = i; 124 break; 125 } 126 } 127 128 if (retIdx == -1) 129 { 130 retIdx = mNormals.size(); 131 mNormals.push_back(transNormal); 132 } 133 134 return (U32)retIdx; 135} 136 137U32 OptimizedPolyList::insertUV0(const Point2F& uv) 138{ 139 S32 retIdx = -1; 140 141 for (U32 i = 0; i < mUV0s.size(); i++) 142 { 143 if (mUV0s[i].equal(uv)) 144 { 145 retIdx = i; 146 break; 147 } 148 } 149 150 if (retIdx == -1) 151 { 152 retIdx = mUV0s.size(); 153 mUV0s.push_back(uv); 154 } 155 156 return (U32)retIdx; 157} 158 159U32 OptimizedPolyList::insertUV1(const Point2F& uv) 160{ 161 S32 retIdx = -1; 162 163 for (U32 i = 0; i < mUV1s.size(); i++) 164 { 165 if (mUV1s[i].equal(uv)) 166 { 167 retIdx = i; 168 break; 169 } 170 } 171 172 if (retIdx == -1) 173 { 174 retIdx = mUV1s.size(); 175 mUV1s.push_back(uv); 176 } 177 178 return (U32)retIdx; 179} 180 181U32 OptimizedPolyList::insertPlane(const PlaneF& plane) 182{ 183 S32 retIdx = -1; 184 185 // Apply the transform 186 PlaneF transPlane; 187 mPlaneTransformer.transform(plane, transPlane); 188 189 for (U32 i = 0; i < mPlaneList.size(); i++) 190 { 191 if (mPlaneList[i].equal(transPlane) && 192 mFabs( mPlaneList[i].d - transPlane.d ) < POINT_EPSILON) 193 { 194 retIdx = i; 195 break; 196 } 197 } 198 199 if (retIdx == -1) 200 { 201 retIdx = mPlaneList.size(); 202 mPlaneList.push_back(transPlane); 203 } 204 205 return (U32)retIdx; 206} 207 208U32 OptimizedPolyList::insertMaterial(BaseMatInstance* baseMat) 209{ 210 S32 retIdx = -1; 211 212 if ( !baseMat ) 213 return retIdx; 214 215 Material* mat = dynamic_cast<Material*>(baseMat->getMaterial()); 216 217 for (U32 i = 0; i < mMaterialList.size(); i++) 218 { 219 Material* testMat = dynamic_cast<Material*>(mMaterialList[i]->getMaterial()); 220 221 if (mat && testMat) 222 { 223 if (testMat == mat) 224 { 225 retIdx = i; 226 break; 227 } 228 } 229 else if (mMaterialList[i] == baseMat) 230 { 231 retIdx = i; 232 break; 233 } 234 } 235 236 if (retIdx == -1) 237 { 238 retIdx = mMaterialList.size(); 239 mMaterialList.push_back(baseMat); 240 } 241 242 return (U32)retIdx; 243} 244 245U32 OptimizedPolyList::insertVertex(const Point3F& point, const Point3F& normal, 246 const Point2F& uv0, const Point2F& uv1) 247{ 248 VertIndex vert; 249 250 vert.vertIdx = insertPoint(point); 251 vert.normalIdx = insertNormal(normal); 252 vert.uv0Idx = insertUV0(uv0); 253 vert.uv1Idx = insertUV1(uv1); 254 255 return mVertexList.push_back_unique(vert); 256} 257 258U32 OptimizedPolyList::addPoint(const Point3F& p) 259{ 260 return insertVertex(p); 261} 262 263U32 OptimizedPolyList::addPlane(const PlaneF& plane) 264{ 265 return insertPlane(plane); 266} 267 268 269//---------------------------------------------------------------------------- 270 271void OptimizedPolyList::begin(BaseMatInstance* material, U32 surfaceKey) 272{ 273 mPolyList.increment(); 274 Poly& poly = mPolyList.last(); 275 poly.material = insertMaterial(material); 276 poly.vertexStart = mIndexList.size(); 277 poly.surfaceKey = surfaceKey; 278 poly.type = TriangleFan; 279 poly.object = mCurrObject; 280} 281 282void OptimizedPolyList::begin(BaseMatInstance* material, U32 surfaceKey, PolyType type) 283{ 284 begin(material, surfaceKey); 285 286 // Set the type 287 mPolyList.last().type = type; 288} 289 290 291//---------------------------------------------------------------------------- 292 293void OptimizedPolyList::plane(U32 v1, U32 v2, U32 v3) 294{ 295 /* 296 AssertFatal(v1 < mPoints.size() && v2 < mPoints.size() && v3 < mPoints.size(), 297 "OptimizedPolyList::plane(): Vertex indices are larger than vertex list size"); 298 299 mPolyList.last().plane = addPlane(PlaneF(mPoints[v1], mPoints[v2], mPoints[v3])); 300 */ 301 302 mPolyList.last().plane = addPlane( PlaneF( mPoints[mVertexList[v1].vertIdx], mPoints[mVertexList[v2].vertIdx], mPoints[mVertexList[v3].vertIdx] ) ); 303} 304 305void OptimizedPolyList::plane(const PlaneF& p) 306{ 307 mPolyList.last().plane = addPlane(p); 308} 309 310void OptimizedPolyList::plane(const U32 index) 311{ 312 AssertFatal(index < mPlaneList.size(), "Out of bounds index!"); 313 mPolyList.last().plane = index; 314} 315 316const PlaneF& OptimizedPolyList::getIndexedPlane(const U32 index) 317{ 318 AssertFatal(index < mPlaneList.size(), "Out of bounds index!"); 319 return mPlaneList[index]; 320} 321 322 323//---------------------------------------------------------------------------- 324 325void OptimizedPolyList::vertex(U32 vi) 326{ 327 mIndexList.push_back(vi); 328} 329 330void OptimizedPolyList::vertex(const Point3F& p) 331{ 332 mIndexList.push_back(addPoint(p)); 333} 334 335void OptimizedPolyList::vertex(const Point3F& p, 336 const Point3F& normal, 337 const Point2F& uv0, 338 const Point2F& uv1) 339{ 340 mIndexList.push_back(insertVertex(p, normal, uv0, uv1)); 341} 342 343 344//---------------------------------------------------------------------------- 345 346bool OptimizedPolyList::isEmpty() const 347{ 348 return !mPolyList.size(); 349} 350 351void OptimizedPolyList::end() 352{ 353 Poly& poly = mPolyList.last(); 354 poly.vertexCount = mIndexList.size() - poly.vertexStart; 355} 356 357//---------------------------------------------------------------------------- 358 359Polyhedron OptimizedPolyList::toPolyhedron() const 360{ 361 Polyhedron polyhedron; 362 363 // Add the points, but filter out duplicates. 364 365 Vector< S32> pointRemap; 366 pointRemap.setSize( mPoints.size() ); 367 pointRemap.fill( -1 ); 368 369 const U32 numPoints = mPoints.size(); 370 371 for( U32 i = 0; i < numPoints; ++ i ) 372 { 373 bool isDuplicate = false; 374 for( U32 npoint = 0; npoint < polyhedron.mPointList.size(); ++ npoint ) 375 { 376 if( npoint == i ) 377 continue; 378 379 if( !polyhedron.mPointList[ npoint ].equal( mPoints[ i ] ) ) 380 continue; 381 382 pointRemap[ i ] = npoint; 383 isDuplicate = true; 384 } 385 386 if( !isDuplicate ) 387 { 388 pointRemap[ i ] = polyhedron.mPointList.size(); 389 polyhedron.mPointList.push_back( mPoints[ i ] ); 390 } 391 } 392 393 // Go through the polys and add all their edges and planes. 394 // We will consolidate edges in a second pass. 395 396 const U32 numPolys = mPolyList.size(); 397 for( U32 i = 0; i < numPolys; ++ i ) 398 { 399 const Poly& poly = mPolyList[ i ]; 400 401 // Add the plane. 402 403 const U32 polyIndex = polyhedron.mPlaneList.size(); 404 polyhedron.mPlaneList.push_back( mPlaneList[ poly.plane ] ); 405 406 // Account for polyhedrons expecting planes to 407 // face inwards. 408 409 polyhedron.mPlaneList.last().invert(); 410 411 // Gather remapped indices according to the 412 // current polygon type. 413 414 Vector< U32> indexList; 415 switch( poly.type ) 416 { 417 case TriangleFan: 418 AssertFatal( false, "TriangleFan conversion not implemented" ); 419 case TriangleStrip: 420 AssertFatal( false, "TriangleStrip conversion not implemented" ); 421 case TriangleList: 422 { 423 Vector< Polyhedron::Edge> tempEdges; 424 425 // Loop over the triangles and gather all unshared edges 426 // in tempEdges. These are the exterior edges of the polygon. 427 428 for( U32 n = poly.vertexStart; n < poly.vertexStart + poly.vertexCount; n += 3 ) 429 { 430 U32 indices[ 3 ]; 431 432 // Get the remapped indices of the three vertices. 433 434 indices[ 0 ] = pointRemap[ mVertexList[ mIndexList[ n + 0 ] ].vertIdx ]; 435 indices[ 1 ] = pointRemap[ mVertexList[ mIndexList[ n + 1 ] ].vertIdx ]; 436 indices[ 2 ] = pointRemap[ mVertexList[ mIndexList[ n + 2 ] ].vertIdx ]; 437 438 // Loop over the three edges. 439 440 for( U32 d = 0; d < 3; ++ d ) 441 { 442 U32 index1 = indices[ d ]; 443 U32 index2 = indices[ ( d + 1 ) % 3 ]; 444 445 // See if this edge is already in the list. If so, 446 // it's a shared edge and thus an interior one. Remove 447 // it. 448 449 bool isShared = false; 450 for( U32 nedge = 0; nedge < tempEdges.size(); ++ nedge ) 451 { 452 Polyhedron::Edge& edge = tempEdges[ nedge ]; 453 if( ( edge.vertex[ 0 ] == index1 && edge.vertex[ 1 ] == index2 ) || 454 ( edge.vertex[ 0 ] == index2 && edge.vertex[ 1 ] == index1 ) ) 455 { 456 tempEdges.erase( nedge ); 457 458 isShared = true; 459 break; 460 } 461 } 462 463 // If it wasn't in the list, add a new edge. 464 465 if( !isShared ) 466 tempEdges.push_back( 467 Polyhedron::Edge( -1, -1, index1, index2 ) 468 ); 469 } 470 } 471 472 // Walk the edges and gather consecutive indices. 473 474 U32 currentEdge = 0; 475 for( U32 n = 0; n < tempEdges.size(); ++ n ) 476 { 477 // Add first vertex of edge. 478 479 indexList.push_back( tempEdges[ currentEdge ].vertex[ 0 ] ); 480 481 // Find edge that begins at second vertex. 482 483 for( U32 nedge = 0; nedge < tempEdges.size(); ++ nedge ) 484 { 485 if( nedge == currentEdge ) 486 continue; 487 488 if( tempEdges[ nedge ].vertex[ 0 ] == tempEdges[ currentEdge ].vertex[ 1 ] ) 489 { 490 currentEdge = nedge; 491 break; 492 } 493 } 494 } 495 } 496 } 497 498 // Create edges from the indices. Indices are CCW ordered and 499 // we want CW order, so step everything in reverse. 500 501 U32 lastIndex = 0; 502 for( S32 n = indexList.size() - 1; n >= 0; -- n ) 503 { 504 polyhedron.mEdgeList.push_back( 505 Polyhedron::Edge( 506 polyIndex, 0, // face1 filled later 507 indexList[ lastIndex ], indexList[ n ] 508 ) 509 ); 510 511 lastIndex = n; 512 } 513 } 514 515 // Finally, consolidate the edge list by merging all edges that 516 // are shared by polygons. 517 518 for( U32 i = 0; i < polyhedron.mEdgeList.size(); ++ i ) 519 { 520 Polyhedron::Edge& edge = polyhedron.mEdgeList[ i ]; 521 522 // Find the corresponding duplicate edge, if any, and merge 523 // it into our current edge. 524 525 for( U32 n = i + 1; n < polyhedron.mEdgeList.size(); ++ n ) 526 { 527 const Polyhedron::Edge& thisEdge = polyhedron.mEdgeList[ n ]; 528 529 if( ( thisEdge.vertex[ 0 ] == edge.vertex[ 1 ] && 530 thisEdge.vertex[ 1 ] == edge.vertex[ 0 ] ) || 531 ( thisEdge.vertex[ 0 ] == edge.vertex[ 0 ] && 532 thisEdge.vertex[ 1 ] == edge.vertex[ 1 ] ) ) 533 { 534 edge.face[ 1 ] = thisEdge.face[ 0 ]; 535 polyhedron.mEdgeList.erase( n ); 536 break; 537 } 538 } 539 } 540 541 return polyhedron; 542} 543