clippedPolyList.cpp
Engine/source/collision/clippedPolyList.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 "platform/platform.h" 25#include "collision/clippedPolyList.h" 26 27#include "math/mMath.h" 28#include "console/console.h" 29#include "platform/profiler.h" 30 31#include "core/tAlgorithm.h" 32 33bool ClippedPolyList::allowClipping = true; 34 35 36//---------------------------------------------------------------------------- 37 38ClippedPolyList::ClippedPolyList() 39 : mNormal( Point3F::Zero ), 40 mNormalTolCosineRadians( 0.0f ) 41{ 42 VECTOR_SET_ASSOCIATION(mPolyList); 43 VECTOR_SET_ASSOCIATION(mVertexList); 44 VECTOR_SET_ASSOCIATION(mIndexList); 45 VECTOR_SET_ASSOCIATION(mPolyPlaneList); 46 VECTOR_SET_ASSOCIATION(mPlaneList); 47 VECTOR_SET_ASSOCIATION(mNormalList); 48 49 mIndexList.reserve(IndexListReserveSize); 50} 51 52ClippedPolyList::~ClippedPolyList() 53{ 54} 55 56 57//---------------------------------------------------------------------------- 58 59void ClippedPolyList::clear() 60{ 61 // Only clears internal data 62 mPolyList.clear(); 63 mVertexList.clear(); 64 mIndexList.clear(); 65 mPolyPlaneList.clear(); 66 mNormalList.clear(); 67} 68 69bool ClippedPolyList::isEmpty() const 70{ 71 return mPolyList.size() == 0; 72} 73 74 75//---------------------------------------------------------------------------- 76 77U32 ClippedPolyList::addPoint(const Point3F& p) 78{ 79 return addPointAndNormal( p, Point3F::Zero ); 80} 81 82U32 ClippedPolyList::addPointAndNormal(const Point3F& p, const Point3F& normal) 83{ 84 mVertexList.increment(); 85 Vertex& v = mVertexList.last(); 86 v.point.x = p.x * mScale.x; 87 v.point.y = p.y * mScale.y; 88 v.point.z = p.z * mScale.z; 89 mMatrix.mulP(v.point); 90 91 mNormalList.increment(); 92 VectorF& n = mNormalList.last(); 93 n = normal; 94 if ( !n.isZero() ) 95 mMatrix.mulV(n); 96 97 AssertFatal(mNormalList.size() == mVertexList.size(), "Normals count does not match vertex count!"); 98 99 // Build the plane mask 100 U32 mask = 1; 101 S32 count = mPlaneList.size(); 102 PlaneF * plane = mPlaneList.address(); 103 104 v.mask = 0; 105 while(--count >= 0) { 106 if (plane++->distToPlane(v.point) > 0) 107 v.mask |= mask; 108 mask <<= 1; 109 } 110 111 return mVertexList.size() - 1; 112} 113 114 115U32 ClippedPolyList::addPlane(const PlaneF& plane) 116{ 117 mPolyPlaneList.increment(); 118 mPlaneTransformer.transform(plane, mPolyPlaneList.last()); 119 120 return mPolyPlaneList.size() - 1; 121} 122 123 124//---------------------------------------------------------------------------- 125 126void ClippedPolyList::begin(BaseMatInstance* material,U32 surfaceKey) 127{ 128 mPolyList.increment(); 129 Poly& poly = mPolyList.last(); 130 poly.object = mCurrObject; 131 poly.material = material; 132 poly.vertexStart = mIndexList.size(); 133 poly.surfaceKey = surfaceKey; 134 135 poly.polyFlags = 0; 136 if(ClippedPolyList::allowClipping) 137 poly.polyFlags = CLIPPEDPOLYLIST_FLAG_ALLOWCLIPPING; 138} 139 140 141//---------------------------------------------------------------------------- 142 143void ClippedPolyList::plane(U32 v1,U32 v2,U32 v3) 144{ 145 mPolyList.last().plane.set(mVertexList[v1].point, 146 mVertexList[v2].point,mVertexList[v3].point); 147} 148 149void ClippedPolyList::plane(const PlaneF& p) 150{ 151 mPlaneTransformer.transform(p, mPolyList.last().plane); 152} 153 154void ClippedPolyList::plane(const U32 index) 155{ 156 AssertFatal(index < mPolyPlaneList.size(), "Out of bounds index!"); 157 mPolyList.last().plane = mPolyPlaneList[index]; 158} 159 160const PlaneF& ClippedPolyList::getIndexedPlane(const U32 index) 161{ 162 AssertFatal(index < mPolyPlaneList.size(), "Out of bounds index!"); 163 return mPolyPlaneList[index]; 164} 165 166 167//---------------------------------------------------------------------------- 168 169void ClippedPolyList::vertex(U32 vi) 170{ 171 mIndexList.push_back(vi); 172} 173 174 175//---------------------------------------------------------------------------- 176 177void ClippedPolyList::end() 178{ 179 PROFILE_SCOPE( ClippedPolyList_Clip ); 180 181 Poly& poly = mPolyList.last(); 182 183 // Reject polygons facing away from our normal. 184 if ( mDot( poly.plane, mNormal ) < mNormalTolCosineRadians ) 185 { 186 mIndexList.setSize(poly.vertexStart); 187 mPolyList.decrement(); 188 return; 189 } 190 191 // Build initial inside/outside plane masks 192 U32 indexStart = poly.vertexStart; 193 U32 vertexCount = mIndexList.size() - indexStart; 194 195 U32 frontMask = 0,backMask = 0; 196 U32 i; 197 for (i = indexStart; i < mIndexList.size(); i++) 198 { 199 U32 mask = mVertexList[mIndexList[i]].mask; 200 frontMask |= mask; 201 backMask |= ~mask; 202 } 203 204 // Trivial accept if all the vertices are on the backsides of 205 // all the planes. 206 if (!frontMask) 207 { 208 poly.vertexCount = vertexCount; 209 return; 210 } 211 212 // Trivial reject if any plane not crossed has all it's points 213 // on the front. 214 U32 crossMask = frontMask & backMask; 215 if (~crossMask & frontMask) 216 { 217 mIndexList.setSize(poly.vertexStart); 218 mPolyList.decrement(); 219 return; 220 } 221 222 // Potentially, this will add up to mPlaneList.size() * (indexStart - indexEnd) 223 // elements to mIndexList, so ensure that it has enough space to store that 224 // so we can use push_back_noresize. If you find this code block getting hit 225 // frequently, changing the value of 'IndexListReserveSize' or doing some selective 226 // allocation is suggested 227 // 228 // TODO: Re-visit this, since it obviously does not work correctly, and than 229 // re-enable the push_back_noresize 230 //while(mIndexList.size() + mPlaneList.size() * (mIndexList.size() - indexStart) > mIndexList.capacity() ) 231 // mIndexList.reserve(mIndexList.capacity() * 2); 232 233 // Need to do some clipping 234 for (U32 p = 0; p < mPlaneList.size(); p++) 235 { 236 U32 pmask = 1 << p; 237 238 // Only test against this plane if we have something 239 // on both sides 240 if (!(crossMask & pmask)) 241 continue; 242 243 U32 indexEnd = mIndexList.size(); 244 U32 i1 = indexEnd - 1; 245 U32 mask1 = mVertexList[mIndexList[i1]].mask; 246 247 for (U32 i2 = indexStart; i2 < indexEnd; i2++) 248 { 249 U32 mask2 = mVertexList[mIndexList[i2]].mask; 250 if ((mask1 ^ mask2) & pmask) 251 { 252 // 253 mVertexList.increment(); 254 VectorF& v1 = mVertexList[mIndexList[i1]].point; 255 VectorF& v2 = mVertexList[mIndexList[i2]].point; 256 VectorF vv = v2 - v1; 257 F32 t = -mPlaneList[p].distToPlane(v1) / mDot(mPlaneList[p],vv); 258 259 mNormalList.increment(); 260 VectorF& n1 = mNormalList[mIndexList[i1]]; 261 VectorF& n2 = mNormalList[mIndexList[i1]]; 262 VectorF nn = mLerp( n1, n2, t ); 263 nn.normalizeSafe(); 264 mNormalList.last() = nn; 265 266 mIndexList.push_back/*_noresize*/(mVertexList.size() - 1); 267 Vertex& iv = mVertexList.last(); 268 iv.point.x = v1.x + vv.x * t; 269 iv.point.y = v1.y + vv.y * t; 270 iv.point.z = v1.z + vv.z * t; 271 iv.mask = 0; 272 273 // Test against the remaining planes 274 for (U32 rP = p + 1; rP < mPlaneList.size(); rP++) 275 if (mPlaneList[rP].distToPlane(iv.point) > 0) 276 { 277 iv.mask = 1 << rP; 278 break; 279 } 280 } 281 282 if (!(mask2 & pmask)) 283 { 284 U32 index = mIndexList[i2]; 285 mIndexList.push_back/*_noresize*/(index); 286 } 287 288 mask1 = mask2; 289 i1 = i2; 290 } 291 292 // Check for degenerate 293 indexStart = indexEnd; 294 if (mIndexList.size() - indexStart < 3) 295 { 296 mIndexList.setSize(poly.vertexStart); 297 mPolyList.decrement(); 298 return; 299 } 300 } 301 302 // Emit what's left and compress the index list. 303 poly.vertexCount = mIndexList.size() - indexStart; 304 memcpy(&mIndexList[poly.vertexStart], 305 &mIndexList[indexStart],poly.vertexCount); 306 mIndexList.setSize(poly.vertexStart + poly.vertexCount); 307} 308 309 310//---------------------------------------------------------------------------- 311 312void ClippedPolyList::memcpy(U32* dst, U32* src,U32 size) 313{ 314 U32* end = src + size; 315 while (src != end) 316 *dst++ = *src++; 317} 318 319void ClippedPolyList::cullUnusedVerts() 320{ 321 PROFILE_SCOPE( ClippedPolyList_CullUnusedVerts ); 322 323 U32 i = 0; 324 U32 k, n, numDeleted; 325 bool result; 326 327 IndexListIterator iNextIter; 328 VertexListIterator nextVIter; 329 VertexListIterator vIter; 330 331 for ( vIter = mVertexList.begin(); vIter != mVertexList.end(); vIter++, i++ ) 332 { 333 // Is this vertex used? 334 iNextIter = T3D::find( mIndexList.begin(), mIndexList.end(), i ); 335 if ( iNextIter != mIndexList.end() ) 336 continue; 337 338 // If not, find the next used vertex. 339 340 // i is an unused vertex 341 // k is a used vertex 342 // delete the vertices from i to j - 1 343 k = 0; 344 n = i + 1; 345 result = false; 346 numDeleted = 0; 347 348 for ( nextVIter = vIter + 1; nextVIter != mVertexList.end(); nextVIter++, n++ ) 349 { 350 iNextIter = T3D::find( mIndexList.begin(), mIndexList.end(), n ); 351 352 // If we found a used vertex 353 // grab its index for later use 354 // and set our result bool. 355 if ( (*iNextIter) == n ) 356 { 357 k = n; 358 result = true; 359 break; 360 } 361 } 362 363 // All the remaining verts are unused. 364 if ( !result ) 365 { 366 mVertexList.setSize( i ); 367 mNormalList.setSize( i ); 368 break; 369 } 370 371 // Erase unused verts. 372 numDeleted = (k-1) - i + 1; 373 mVertexList.erase( i, numDeleted ); 374 mNormalList.erase( i, numDeleted ); 375 376 // Find any references to vertices after those deleted 377 // in the mIndexList and correct with an offset 378 for ( iNextIter = mIndexList.begin(); iNextIter != mIndexList.end(); iNextIter++ ) 379 { 380 if ( (*iNextIter) > i ) 381 (*iNextIter) -= numDeleted; 382 } 383 384 // After the erase the current iter should 385 // point at the used vertex we found... the 386 // loop will continue with the next vert. 387 } 388} 389 390void ClippedPolyList::triangulate() 391{ 392 PROFILE_SCOPE( ClippedPolyList_Triangulate ); 393 394 // Copy the source lists to our temp list and clear 395 // the originals which will recieve the results. 396 mTempPolyList.set( mPolyList.address(), mPolyList.size() ); 397 mTempIndexList.set( mIndexList.address(), mIndexList.size() ); 398 mPolyList.clear(); 399 mIndexList.clear(); 400 401 U32 j, numTriangles; 402 403 // 404 PolyListIterator polyIter = mTempPolyList.begin(); 405 for ( ; polyIter != mTempPolyList.end(); polyIter++ ) 406 { 407 const Poly &poly = *polyIter; 408 409 // How many triangles in this poly? 410 numTriangles = poly.vertexCount - 2; 411 412 // Build out the triangles. 413 for ( j = 0; j < numTriangles; j++ ) 414 { 415 mPolyList.increment(); 416 417 Poly &triangle = mPolyList.last(); 418 triangle = poly; 419 triangle.vertexCount = 3; 420 triangle.vertexStart = mIndexList.size(); 421 422 mIndexList.push_back( mTempIndexList[ poly.vertexStart ] ); 423 mIndexList.push_back( mTempIndexList[ poly.vertexStart + 1 + j ] ); 424 mIndexList.push_back( mTempIndexList[ poly.vertexStart + 2 + j ] ); 425 } 426 } 427} 428 429void ClippedPolyList::generateNormals() 430{ 431 PROFILE_SCOPE( ClippedPolyList_GenerateNormals ); 432 433 AssertFatal(mNormalList.size() == mVertexList.size(), "Normals count does not match vertex count!"); 434 435 U32 i, polyCount; 436 VectorF normal; 437 PolyListIterator polyIter; 438 IndexListIterator indexIter; 439 440 Vector<VectorF>::iterator normalIter = mNormalList.begin(); 441 U32 n = 0; 442 for ( ; normalIter != mNormalList.end(); normalIter++, n++ ) 443 { 444 // Skip normals that already have values. 445 if ( !normalIter->isZero() ) 446 continue; 447 448 // Average all the face normals which 449 // share this vertex index. 450 indexIter = mIndexList.begin(); 451 normal.zero(); 452 polyCount = 0; 453 i = 0; 454 455 for ( ; indexIter != mIndexList.end(); indexIter++, i++ ) 456 { 457 if ( n != *indexIter ) 458 continue; 459 460 polyIter = mPolyList.begin(); 461 for ( ; polyIter != mPolyList.end(); polyIter++ ) 462 { 463 const Poly& poly = *polyIter; 464 if ( i < poly.vertexStart || i > poly.vertexStart + poly.vertexCount ) 465 continue; 466 467 ++polyCount; 468 normal += poly.plane; 469 } 470 } 471 472 // Average it. 473 if ( polyCount > 0 ) 474 normal /= (F32)polyCount; 475 476 // Note: we use a temporary for the normal averaging 477 // then copy the result to limit the number of arrays 478 // we're touching during the innermost loop. 479 *normalIter = normal; 480 } 481} 482