extrudedPolyList.cpp
Engine/source/collision/extrudedPolyList.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 "math/mMath.h" 26#include "console/console.h" 27#include "collision/extrudedPolyList.h" 28#include "math/mPolyhedron.h" 29#include "collision/collision.h" 30 31// Minimum distance from a face 32F32 ExtrudedPolyList::FaceEpsilon = 0.01f; 33 34// Value used to compare collision times 35F32 ExtrudedPolyList::EqualEpsilon = 0.0001f; 36 37ExtrudedPolyList::ExtrudedPolyList() 38{ 39 VECTOR_SET_ASSOCIATION(mVertexList); 40 VECTOR_SET_ASSOCIATION(mIndexList); 41 VECTOR_SET_ASSOCIATION(mExtrudedList); 42 VECTOR_SET_ASSOCIATION(mPlaneList); 43 VECTOR_SET_ASSOCIATION(mPolyPlaneList); 44 45 mVelocity.set(0.0f,0.0f,0.0f); 46 mIndexList.reserve(128); 47 mVertexList.reserve(64); 48 mPolyPlaneList.reserve(64); 49 mPlaneList.reserve(64); 50 mCollisionList = 0; 51 dMemset(&mPoly, 0, sizeof(mPoly)); 52} 53 54ExtrudedPolyList::~ExtrudedPolyList() 55{ 56} 57 58//---------------------------------------------------------------------------- 59 60bool ExtrudedPolyList::isEmpty() const 61{ 62 return mCollisionList->getCount() == 0; 63} 64 65 66//---------------------------------------------------------------------------- 67 68void ExtrudedPolyList::extrude(const Polyhedron& pt, const VectorF& vector) 69{ 70 // Clear state 71 mIndexList.clear(); 72 mVertexList.clear(); 73 mPlaneList.clear(); 74 mPolyPlaneList.clear(); 75 76 // Determine which faces will be extruded. 77 mExtrudedList.setSize(pt.mPlaneList.size()); 78 79 for (U32 f = 0; f < pt.mPlaneList.size(); f++) 80 { 81 const PlaneF& face = pt.mPlaneList[f]; 82 ExtrudedFace& eface = mExtrudedList[f]; 83 F32 dot = mDot(face,vector); 84 eface.active = dot > EqualEpsilon; 85 86 if (eface.active) 87 { 88 eface.maxDistance = dot; 89 eface.plane = face; 90 eface.planeMask = BIT(mPlaneList.size()); 91 92 // Add the face as a plane to clip against. 93 mPlaneList.increment(2); 94 PlaneF* plane = mPlaneList.end() - 2; 95 plane[0] = plane[1] = face; 96 plane[0].invert(); 97 } 98 } 99 100 // Produce extruded planes for bounding and internal edges 101 for (U32 e = 0; e < pt.mEdgeList.size(); e++) 102 { 103 Polyhedron::Edge const& edge = pt.mEdgeList[e]; 104 ExtrudedFace& ef1 = mExtrudedList[edge.face[0]]; 105 ExtrudedFace& ef2 = mExtrudedList[edge.face[1]]; 106 if (ef1.active || ef2.active) 107 { 108 109 // Assumes that the edge points are clockwise 110 // for face[0]. 111 const Point3F& p1 = pt.mPointList[edge.vertex[1]]; 112 const Point3F &p2 = pt.mPointList[edge.vertex[0]]; 113 Point3F p3 = p2 + vector; 114 115 mPlaneList.increment(2); 116 PlaneF* plane = mPlaneList.end() - 2; 117 plane[0].set(p3,p2,p1); 118 plane[1] = plane[0]; 119 plane[1].invert(); 120 121 U32 pmask = BIT(mPlaneList.size()-2); 122 ef1.planeMask |= pmask; 123 ef2.planeMask |= pmask << 1; 124 } 125 } 126} 127 128 129//---------------------------------------------------------------------------- 130 131void ExtrudedPolyList::setCollisionList(CollisionList* info) 132{ 133 mCollisionList = info; 134 mCollisionList->clear(); 135 mCollisionList->setTime( 2.0f ); 136} 137 138//---------------------------------------------------------------------------- 139 140void ExtrudedPolyList::adjustCollisionTime() 141{ 142 if( !mCollisionList->getCount() ) 143 return; 144 145 mCollisionList->setTime( mClampF( mCollisionList->getTime(), 0.f, 1.f ) ); 146} 147 148 149//---------------------------------------------------------------------------- 150 151U32 ExtrudedPolyList::addPoint(const Point3F& p) 152{ 153 mVertexList.increment(); 154 Vertex& v = mVertexList.last(); 155 156 v.point.x = p.x * mScale.x; 157 v.point.y = p.y * mScale.y; 158 v.point.z = p.z * mScale.z; 159 mMatrix.mulP(v.point); 160 161 // Build the plane mask, planes come in pairs 162 v.mask = 0; 163 for (U32 i = 0; i < mPlaneList.size(); i ++) 164 if (mPlaneList[i].distToPlane(v.point) >= 0.f) 165 v.mask |= BIT(i); 166 167 return mVertexList.size() - 1; 168} 169 170 171U32 ExtrudedPolyList::addPlane(const PlaneF& plane) 172{ 173 mPolyPlaneList.increment(); 174 mPlaneTransformer.transform(plane, mPolyPlaneList.last()); 175 176 return mPolyPlaneList.size() - 1; 177} 178 179 180//---------------------------------------------------------------------------- 181 182void ExtrudedPolyList::begin(BaseMatInstance* material, U32 /*surfaceKey*/) 183{ 184 mPoly.object = mCurrObject; 185 mPoly.material = material; 186 mIndexList.clear(); 187} 188 189void ExtrudedPolyList::plane(U32 v1, U32 v2, U32 v3) 190{ 191 mPoly.plane.set(mVertexList[v1].point, 192 mVertexList[v2].point, 193 mVertexList[v3].point); 194 195 // We hope this isn't needed but we're leaving it in anyway -- BJG/EGH 196 mPoly.plane.normalizeSafe(); 197} 198 199void ExtrudedPolyList::plane(const PlaneF& p) 200{ 201 mPlaneTransformer.transform(p, mPoly.plane); 202} 203 204void ExtrudedPolyList::plane(const U32 index) 205{ 206 AssertFatal(index < mPolyPlaneList.size(), "Out of bounds index!"); 207 mPoly.plane = mPolyPlaneList[index]; 208} 209 210const PlaneF& ExtrudedPolyList::getIndexedPlane(const U32 index) 211{ 212 AssertFatal(index < mPolyPlaneList.size(), "Out of bounds index!"); 213 return mPolyPlaneList[index]; 214} 215 216 217void ExtrudedPolyList::vertex(U32 vi) 218{ 219 mIndexList.push_back(vi); 220} 221 222void ExtrudedPolyList::end() 223{ 224 // Anything facing away from the mVelocity is rejected (and also 225 // cap to max collisions) 226 if (mDot(mPoly.plane, mNormalVelocity) > 0.f || 227 mCollisionList->getCount() >= CollisionList::MaxCollisions) 228 return; 229 230 // Test the built up poly (stored in mPoly) against all our extruded 231 // faces. 232 U32 cFaceCount = 0; 233 ExtrudedFace* cFace[30]; 234 bool cEdgeColl[30]; 235 ExtrudedFace* face = mExtrudedList.begin(); 236 ExtrudedFace* end = mExtrudedList.end(); 237 238 for (; face != end; face++) 239 { 240 // Skip inactive.. 241 if (!face->active) 242 continue; 243 244 // Update the dot product. 245 face->faceDot = -mDot(face->plane,mPoly.plane); 246 247 // Skip it if we're facing towards... 248 if(face->faceDot <= 0.f) 249 continue; 250 251 // Test, and skip if colliding. 252 if (!testPoly(*face)) 253 continue; 254 255 // Note collision. 256 cFace[cFaceCount] = face; 257 cEdgeColl[cFaceCount++] = false; 258 } 259 260 if (!cFaceCount) 261 { 262 face = mExtrudedList.begin(); 263 end = mExtrudedList.end(); 264 for (; face != end; face++) 265 { 266 // Don't need to do dot product second time, so just check if it's 267 // active (we already did the dot product in the previous loop). 268 if (!face->active) 269 continue; 270 271 // Skip it if we're facing away... 272 if(face->faceDot > 0.f) 273 continue; 274 275 // Do collision as above. 276 if (!testPoly(*face)) 277 continue; 278 279 // Note the collision. 280 cFace[cFaceCount] = face; 281 cEdgeColl[cFaceCount++] = true; 282 } 283 } 284 285 // If we STILL don't have any collisions, just skip out. 286 if (!cFaceCount) 287 return; 288 289 // Pick the best collision face based on best alignment with respective 290 // face. 291 face = cFace[0]; 292 bool edge = cEdgeColl[0]; 293 for (U32 f = 1; f < cFaceCount; f++) 294 { 295 if (cFace[f]->faceDot <= face->faceDot) 296 continue; 297 298 face = cFace[f]; 299 edge = cEdgeColl[f]; 300 } 301 302 // Add it to the collision list if it's better and/or equal 303 // to our current best. 304 305 // Don't add it to the collision list if it's too far away. 306 if (face->time > mCollisionList->getTime() + EqualEpsilon || face->time >= 1.0) 307 return; 308 309 if (face->time < mCollisionList->getTime() - EqualEpsilon) 310 { 311 // If this is significantly closer than before, then clear out the 312 // list, as it's a better match than the old stuff. 313 mCollisionList->clear(); 314 mCollisionList->setTime( face->time ); 315 mCollisionList->setMaxHeight( face->height ); 316 } 317 else 318 { 319 // Otherwise, just update some book-keeping stuff. 320 if ( face->height > mCollisionList->getMaxHeight() ) 321 mCollisionList->setMaxHeight( face->height ); 322 } 323 324 // Note the collision in our collision list. 325 Collision& collision = mCollisionList->increment(); 326 collision.point = face->point; 327 collision.faceDot = face->faceDot; 328 collision.face = face - mExtrudedList.begin(); 329 collision.object = mPoly.object; 330 collision.normal = mPoly.plane; 331 collision.material = mPoly.material; 332} 333 334 335//---------------------------------------------------------------------------- 336 337bool ExtrudedPolyList::testPoly(ExtrudedFace& face) 338{ 339 // Build intial inside/outside plane masks 340 U32 indexStart = 0; 341 U32 indexEnd = mIndexList.size(); 342 U32 oVertexSize = mVertexList.size(); 343 U32 oIndexSize = mIndexList.size(); 344 345 U32 frontMask = 0,backMask = 0; 346 for (U32 i = indexStart; i < indexEnd; i++) 347 { 348 U32 mask = mVertexList[mIndexList[i]].mask & face.planeMask; 349 frontMask |= mask; 350 backMask |= ~mask; 351 } 352 353 // Clip the mPoly against the planes that bound the face... 354 // Trivial accept if all the vertices are on the backsides of 355 // all the planes. 356 if (frontMask) 357 { 358 // Trivial reject if any plane not crossed has all it's points 359 // on the front. 360 U32 crossMask = frontMask & backMask; 361 if (~crossMask & frontMask) 362 return false; 363 364 // Need to do some clipping 365 for (U32 p=0; p < mPlaneList.size(); p++) 366 { 367 U32 pmask = BIT(p); 368 U32 newStart = mIndexList.size(); 369 370 // Only test against this plane if we have something 371 // on both sides - otherwise skip. 372 if (!(face.planeMask & crossMask & pmask)) 373 continue; 374 375 U32 i1 = indexEnd - 1; 376 U32 mask1 = mVertexList[mIndexList[i1]].mask; 377 378 for (U32 i2 = indexStart; i2 < indexEnd; i2++) 379 { 380 const U32 mask2 = mVertexList[mIndexList[i2]].mask; 381 if ((mask1 ^ mask2) & pmask) 382 { 383 // Clip the edge against the plane. 384 mVertexList.increment(); 385 VectorF& v1 = mVertexList[mIndexList[i1]].point; 386 VectorF& v2 = mVertexList[mIndexList[i2]].point; 387 VectorF vv = v2 - v1; 388 F32 t = -mPlaneList[p].distToPlane(v1) / mDot(mPlaneList[p],vv); 389 390 mIndexList.push_back(mVertexList.size() - 1); 391 Vertex& iv = mVertexList.last(); 392 iv.point.x = v1.x + vv.x * t; 393 iv.point.y = v1.y + vv.y * t; 394 iv.point.z = v1.z + vv.z * t; 395 iv.mask = 0; 396 397 // Test against the remaining planes 398 for (U32 i = p+1; i < mPlaneList.size(); i ++) 399 { 400 if (mPlaneList[i].distToPlane(iv.point) > 0.f) 401 iv.mask |= BIT(i); 402 } 403 } 404 405 if (!(mask2 & pmask)) 406 { 407 U32 index = mIndexList[i2]; 408 mIndexList.push_back(index); 409 } 410 411 mask1 = mask2; 412 i1 = i2; 413 } 414 415 // Check for degenerate 416 indexStart = newStart; 417 indexEnd = mIndexList.size(); 418 if (mIndexList.size() - indexStart < 3) 419 { 420 mVertexList.setSize(oVertexSize); 421 mIndexList.setSize(oIndexSize); 422 return false; 423 } 424 } 425 } 426 427 // Find closest point on the mPoly 428 Point3F bp(0.0f, 0.0f, 0.0f); 429 F32 bd = 1E30f; 430 F32 height = -1E30f; 431 for (U32 b = indexStart; b < indexEnd; b++) 432 { 433 Vertex& vertex = mVertexList[mIndexList[b]]; 434 F32 dist = face.plane.distToPlane(vertex.point); 435 if (dist <= bd) 436 { 437 bd = (dist < 0)? 0: dist; 438 bp = vertex.point; 439 } 440 441 // Since we don't clip against the back plane, we'll 442 // only include vertex heights that are within range. 443 if (vertex.point.z > height && dist < face.maxDistance) 444 height = vertex.point.z; 445 } 446 447 // hack for not jetting up through the cieling 448 F32 fudge = 0.01f; 449 F32 fudgeB = 0.2f; 450 if(mNormalVelocity.z > 0.0) 451 { 452 fudge = 0.01f; //0.015; 453 fudgeB = 0.2f; 454 } 455 456 // Do extruded points for back-off. 457 F32 oldBd=bd; 458 for (U32 b = indexStart; b < indexEnd; b++) 459 { 460 Vertex& vertex = mVertexList[mIndexList[b]]; 461 462 // Extrude out just a tad to make sure we don't end up getting too close to the 463 // geometry and getting stuck - but cap it so we don't introduce error into long 464 // sweeps. 465 F32 dist = face.plane.distToPlane( vertex.point 466 + Point3F(mPoly.plane) * getMin(face.maxDistance * fudgeB, fudge)); 467 468 if (dist <= bd) 469 { 470 bd = (dist < 0)? 0: dist; 471 bp = vertex.point; 472 } 473 } 474 475 // Remove temporary data 476 mVertexList.setSize(oVertexSize); 477 mIndexList.setSize(oIndexSize); 478 479 // Don't add it to the collision list if it's worse then our current best. 480 if (oldBd >= face.maxDistance) 481 return false; 482 483 // Update our info and indicate we should add to the model. 484 F32 oldT = oldBd / face.maxDistance; 485 F32 pushBackT = bd / face.maxDistance; 486 487 if(oldT - pushBackT > 0.1) 488 face.time = oldT - fudge; 489 else 490 face.time = pushBackT; 491 492 face.height = height; 493 face.point = bp; 494 return true; 495} 496 497//-------------------------------------------------------------------------- 498void ExtrudedPolyList::setVelocity(const VectorF& velocity) 499{ 500 mVelocity = velocity; 501 if (velocity.isZero() == false) 502 { 503 mNormalVelocity = velocity; 504 mNormalVelocity.normalize(); 505 setInterestNormal(mNormalVelocity); 506 } 507 else 508 { 509 mNormalVelocity.set(0.0f, 0.0f, 0.0f); 510 clearInterestNormal(); 511 } 512} 513