decomposePoly.cpp
Engine/source/math/util/decomposePoly.cpp
Detailed Description
1 2#include "math/util/decomposePoly.h" 3 4// twoIndices Methods 5 6twoIndices::twoIndices() 7{ 8 i1 = i2 = 0; 9} 10 11twoIndices::twoIndices(U8 a, U8 b) 12{ 13 i1 = a; 14 i2 = b; 15} 16 17// decompTri Methods 18 19decompTri::decompTri() 20{ 21 mVertIdx[0] = 0; 22 mVertIdx[1] = 0; 23 mVertIdx[2] = 0; 24} 25 26void decompTri::orderVerts() 27{ 28 // Bubble sort, smallest to largest 29 U8 temp; 30 31 for (U8 i = 2; i > 0; i--) 32 { 33 for (U8 j = 0; j < i; j++) 34 { 35 if (mVertIdx[j] > mVertIdx[j + 1]) 36 { 37 temp = mVertIdx[j]; 38 mVertIdx[j] = mVertIdx[j + 1]; 39 mVertIdx[j + 1] = temp; 40 } 41 } 42 } 43} 44 45void decompTri::setVert(U8 val, U8 idx) 46{ 47 if(idx < 3) 48 mVertIdx[idx] = val; 49} 50 51U8 decompTri::getVert(U8 idx) 52{ 53 if(idx < 3) 54 return mVertIdx[idx]; 55 56 return mVertIdx[2]; 57} 58 59twoIndices decompTri::getOtherVerts(U8 idx) 60{ 61 if(idx == mVertIdx[0]) 62 return twoIndices(mVertIdx[1], mVertIdx[2]); 63 64 if(idx == mVertIdx[1]) 65 return twoIndices(mVertIdx[0], mVertIdx[2]); 66 67 if(idx == mVertIdx[2]) 68 return twoIndices(mVertIdx[0], mVertIdx[1]); 69 70 return twoIndices(0,0); 71} 72 73// decompPoly Methods 74 75void decompPoly::addVert(Point3F &newVert) 76{ 77 bool found = false; 78 79 for(U8 i = 0; i < mVertList.size(); i++) 80 { 81 if(newVert == mVertList[i]) 82 found = true; 83 } 84 85 if(!found) 86 mVertList.push_back(newVert); 87} 88 89void decompPoly::initEdgeList() 90{ 91 mEdgeList.clear(); 92 93 S32 next = 0; 94 95 for(S32 i = 0; i < mVertList.size(); i++) 96 { 97 if(i == mVertList.size()-1) 98 next = 0; 99 else 100 next = i+1; 101 102 mEdgeList.push_back(twoIndices(i, next)); 103 } 104} 105 106bool decompPoly::sameSide(Point3F &p1, Point3F &p2, Point3F &l1, Point3F &l2) 107{ 108 return ((p1.x-l1.x)*(l2.y-l1.y)-(l2.x-l1.x)*(p1.y-l1.y))*((p2.x-l1.x)*(l2.y-l1.y)-(l2.x-l1.x)*(p2.y-l1.y)) > 0; 109} 110 111bool decompPoly::isInside(decompTri &tri, U8 vertIdx) 112{ 113 Point3F a(mVertList[tri.getVert(0)]); 114 Point3F b(mVertList[tri.getVert(1)]); 115 Point3F c(mVertList[tri.getVert(2)]); 116 Point3F p(mVertList[vertIdx]); 117 118 return (sameSide(p,a,b,c) && sameSide(p,b,a,c) && sameSide(p,c,a,b)); 119} 120 121U8 decompPoly::leftmost() 122{ 123 F32 xMin = 9999999.f; 124 U8 idx = 0; 125 126 for(U8 i = 0; i < mVertList.size(); i++) 127 { 128 if(mVertList[i].x < xMin && isVertInEdgeList(i)) 129 { 130 xMin = mVertList[i].x; 131 idx = i; 132 } 133 } 134 135 return idx; 136} 137 138U8 decompPoly::rightmost() 139{ 140 F32 xMax = -9999999.f; 141 U8 idx = 0; 142 143 for(U8 i = 0; i < mVertList.size(); i++) 144 { 145 if(mVertList[i].x > xMax && isVertInEdgeList(i)) 146 { 147 xMax = mVertList[i].x; 148 idx = i; 149 } 150 } 151 152 return idx; 153} 154 155U8 decompPoly::uppermost() 156{ 157 F32 yMax = -9999999.f; 158 U8 idx = 0; 159 160 for(U8 i = 0; i < mVertList.size(); i++) 161 { 162 if(mVertList[i].y > yMax && isVertInEdgeList(i)) 163 { 164 yMax = mVertList[i].y; 165 idx = i; 166 } 167 } 168 169 return idx; 170} 171 172U8 decompPoly::lowermost() 173{ 174 F32 yMin = 9999999.f; 175 U8 idx = 0; 176 177 for(U8 i = 0; i < mVertList.size(); i++) 178 { 179 if(mVertList[i].y < yMin && isVertInEdgeList(i)) 180 { 181 yMin = mVertList[i].y; 182 idx = i; 183 } 184 } 185 186 return idx; 187} 188 189twoIndices decompPoly::findEdges(U8 vertIdx, bool ¬Unique) 190{ 191 U8 found = 0; 192 U8 edgeIdx[2]; 193 194 for(U8 i = 0; i < mEdgeList.size(); i++) 195 { 196 if(mEdgeList[i].i1 == vertIdx || mEdgeList[i].i2 == vertIdx) 197 { 198 edgeIdx[found++] = i; 199 } 200 } 201 202 notUnique = found > 2; 203 204 return twoIndices(edgeIdx[0], edgeIdx[1]); 205} 206 207decompTri decompPoly::formTriFromEdges(U8 idx1, U8 idx2) 208{ 209 decompTri tri; 210 211 tri.setVert(mEdgeList[idx1].i1, 0); 212 tri.setVert(mEdgeList[idx1].i2, 1); 213 214 if(mEdgeList[idx2].i1 == tri.getVert(0) || mEdgeList[idx2].i1 == tri.getVert(1)) 215 { 216 tri.setVert(mEdgeList[idx2].i2, 2); 217 } 218 else 219 { 220 tri.setVert(mEdgeList[idx2].i1, 2); 221 } 222 223 return tri; 224} 225 226twoIndices decompPoly::leftmostInsideVerts(U8 idx1, U8 idx2) 227{ 228 F32 xMin = 9999999.f; 229 S32 left[] = {-1, -1}; 230 231 for(U8 i = 0; i < 2; i++) 232 { 233 for(U8 j = 0; j < mInsideVerts.size(); j++) 234 { 235 if(mVertList[mInsideVerts[j]].x < xMin && mInsideVerts[j] != left[0]) 236 { 237 xMin = mVertList[mInsideVerts[j]].x; 238 left[i] = mInsideVerts[j]; 239 } 240 } 241 242 if(mVertList[idx1].x < xMin && idx1 != left[0]) 243 { 244 xMin = mVertList[idx1].x; 245 left[i] = idx1; 246 } 247 248 if(mVertList[idx2].x < xMin && idx2 != left[0]) 249 { 250 xMin = mVertList[idx2].x; 251 left[i] = idx2; 252 } 253 254 xMin = 9999999.f; 255 } 256 257 return twoIndices(left[0], left[1]); 258} 259 260twoIndices decompPoly::rightmostInsideVerts(U8 idx1, U8 idx2) 261{ 262 F32 xMax = -9999999.f; 263 S32 right[] = {-1, -1}; 264 265 for(U8 i = 0; i < 2; i++) 266 { 267 for(U8 j = 0; j < mInsideVerts.size(); j++) 268 { 269 if(mVertList[mInsideVerts[j]].x > xMax && mInsideVerts[j] != right[0]) 270 { 271 xMax = mVertList[mInsideVerts[j]].x; 272 right[i] = mInsideVerts[j]; 273 } 274 } 275 276 if(mVertList[idx1].x > xMax && idx1 != right[0]) 277 { 278 xMax = mVertList[idx1].x; 279 right[i] = idx1; 280 } 281 282 if(mVertList[idx2].x > xMax && idx2 != right[0]) 283 { 284 xMax = mVertList[idx2].x; 285 right[i] = idx2; 286 } 287 288 xMax = -9999999.f; 289 } 290 291 return twoIndices(right[0], right[1]); 292} 293 294twoIndices decompPoly::uppermostInsideVerts(U8 idx1, U8 idx2) 295{ 296 F32 yMax = -9999999.f; 297 S32 up[] = {-1, -1}; 298 299 for(U8 i = 0; i < 2; i++) 300 { 301 for(U8 j = 0; j < mInsideVerts.size(); j++) 302 { 303 if(mVertList[mInsideVerts[j]].y > yMax && mInsideVerts[j] != up[0]) 304 { 305 yMax = mVertList[mInsideVerts[j]].y; 306 up[i] = mInsideVerts[j]; 307 } 308 } 309 310 if(mVertList[idx1].y > yMax && idx1 != up[0]) 311 { 312 yMax = mVertList[idx1].y; 313 up[i] = idx1; 314 } 315 316 if(mVertList[idx2].y > yMax && idx2 != up[0]) 317 { 318 yMax = mVertList[idx2].y; 319 up[i] = idx2; 320 } 321 322 yMax = -9999999.f; 323 } 324 325 return twoIndices(up[0], up[1]); 326} 327 328twoIndices decompPoly::lowermostInsideVerts(U8 idx1, U8 idx2) 329{ 330 F32 yMin = 9999999.f; 331 S32 down[] = {-1, -1}; 332 333 for(U8 i = 0; i < 2; i++) 334 { 335 for(U8 j = 0; j < mInsideVerts.size(); j++) 336 { 337 if(mVertList[mInsideVerts[j]].y < yMin && mInsideVerts[j] != down[0]) 338 { 339 yMin = mVertList[mInsideVerts[j]].y; 340 down[i] = mInsideVerts[j]; 341 } 342 } 343 344 if(mVertList[idx1].y < yMin && idx1 != down[0]) 345 { 346 yMin = mVertList[idx1].y; 347 down[i] = idx1; 348 } 349 350 if(mVertList[idx2].y < yMin && idx2 != down[0]) 351 { 352 yMin = mVertList[idx2].y; 353 down[i] = idx2; 354 } 355 356 yMin = 9999999.f; 357 } 358 359 return twoIndices(down[0], down[1]); 360} 361 362void decompPoly::findPointsInside() 363{ 364 mInsideVerts.clear(); 365 366 for(U8 i = 0; i < mVertList.size(); i++) 367 { 368 if(i != mTestTri.getVert(0) && i != mTestTri.getVert(1) && i != mTestTri.getVert(2)) 369 { 370 if(isInside(mTestTri, i)) 371 { 372 mInsideVerts.push_back(i); 373 } 374 } 375 } 376} 377 378void decompPoly::addRemoveEdge(U8 idx1, U8 idx2) 379{ 380 twoIndices edge1(idx1, idx2); 381 382 if(!mEdgeList.remove(edge1)) 383 mEdgeList.push_back(edge1); 384} 385 386void decompPoly::newPoly() 387{ 388 mVertList.clear(); 389 mEdgeList.clear(); 390 mInsideVerts.clear(); 391 mTris.clear(); 392} 393 394bool decompPoly::isVertInEdgeList(U8 idx) 395{ 396 for(U8 i = 0; i < mEdgeList.size(); i++) 397 { 398 if(mEdgeList[i].i1 == idx || mEdgeList[i].i2 == idx) 399 return true; 400 } 401 402 return false; 403} 404 405Point3F decompPoly::getVert(U8 idx) 406{ 407 if(idx < mVertList.size()) 408 return mVertList[idx]; 409 410 return Point3F(0.0f, 0.0f, 0.0f); 411} 412 413U8 decompPoly::getTriIdx(U32 tri, U8 idx) 414{ 415 if(tri < mTris.size() && idx < 3) 416 return mTris[tri].getVert(idx); 417 418 return 0; 419} 420 421bool decompPoly::checkEdgeLength(F32 len) 422{ 423 Point3F p1, p2; 424 425 for(U8 i = 0; i < mEdgeList.size(); i++) 426 { 427 p1 = mVertList[mEdgeList[i].i1]; 428 p2 = mVertList[mEdgeList[i].i2]; 429 430 p1 = p2 - p1; 431 432 if(p1.len() < len) 433 return false; 434 } 435 436 return true; 437} 438 439//--------------------------------------------------- 440// Concave polygon decomposition into triangles 441// 442// Based upon this resource: 443// http://www.siggraph.org/education/materials/HyperGraph/scanline/outprims/polygon1.htm 444// 445// 1. Find leftmost vertex in polygon (smallest value along x-axis). 446// 2. Find the two edges adjacent to this vertex. 447// 3. Form a test tri by connecting the open side of these two edges. 448// 4. See if any of the vertices in the poly, besides the ones that form the test tri, are inside the 449// test tri. 450// 5. If there are verts inside, find the 3 leftmost of the inside verts and the test tri verts, form 451// a new test tri from these verts, and repeat from step 4. When no verts are inside, continue. 452// 6. Save test tri as a valid triangle. 453// 7. Remove the edges that the test tri and poly share, and add the new edges from the test tri to 454// the poly to form a new closed poly with the test tri subtracted out. 455// 456// Note: our polygon can contain no more than 255 verts. Complex polygons can create situations where 457// a vertex has more than 2 adjacent edges, causing step 2 to fail. This method improves on the resource 458// listed above by not limiting the decomposition to the leftmost side only. If step 2 fails, the 459// algorithm also tries to decompose the polygon from the top, right, and bottom until one succeeds or 460// they all fail. If they all fail, the polygon is too complex to be decomposed with this method. 461 462bool decompPoly::decompose() 463{ 464 // Must have at least 3 verts to form a poly 465 if(mVertList.size() < 3) 466 return false; 467 468 // Clear out any previously stored tris 469 mTris.clear(); 470 471 // Initialize the edge list with the default edges 472 initEdgeList(); 473 474 twoIndices otherVerts, outerVerts2; 475 U32 counter = 0; 476 U8 uniqueVertAttempt = 0; 477 U8 formTriAttempt = 0; 478 bool notUnique = false; 479 480 // The main decomposition loop 481 while(mEdgeList.size() > 3) 482 { 483 // Find outermost vert in poly, LMV 484 U8 outerVertIdx; 485 486 switch(uniqueVertAttempt) 487 { 488 case 0: outerVertIdx = leftmost(); break; 489 case 1: outerVertIdx = rightmost(); break; 490 case 2: outerVertIdx = uppermost(); break; 491 case 3: outerVertIdx = uppermost(); break; 492 default: outerVertIdx = leftmost(); 493 } 494 495 // Find edges that share LMV 496 twoIndices edgesIdx = findEdges(outerVertIdx, notUnique); 497 498 // If vert shares more than two edges, try decomposing from different direction 499 if(notUnique) 500 { 501 if(uniqueVertAttempt < 4) 502 { 503 uniqueVertAttempt++; 504 continue; 505 } 506 else 507 { 508 newPoly(); 509 return false; 510 } 511 } 512 513 // Sanity check 514 if(edgesIdx.i1 >= mEdgeList.size() || edgesIdx.i2 >= mEdgeList.size()) 515 { 516 newPoly(); 517 return false; 518 } 519 520 // Form the test tri from these 2 edges 521 mTestTri = formTriFromEdges(edgesIdx.i1, edgesIdx.i2); 522 523 // See if there are any other poly verts inside the test tri 524 findPointsInside(); 525 526 // If there are verts inside, repeat procedure until there are none 527 while(mInsideVerts.size() > 0 && formTriAttempt++ < mVertList.size()) 528 { 529 // Get the two verts of the test tri that are not the LMV 530 otherVerts = mTestTri.getOtherVerts(outerVertIdx); 531 532 // Get the 2 outermost verts of the inside and test tri verts (excluding LMV) 533 switch(uniqueVertAttempt) 534 { 535 case 0: outerVerts2 = leftmostInsideVerts(otherVerts.i1, otherVerts.i2); break; 536 case 1: outerVerts2 = rightmostInsideVerts(otherVerts.i1, otherVerts.i2); break; 537 case 2: outerVerts2 = uppermostInsideVerts(otherVerts.i1, otherVerts.i2); break; 538 case 3: outerVerts2 = uppermostInsideVerts(otherVerts.i1, otherVerts.i2); break; 539 default: outerVerts2 = leftmostInsideVerts(otherVerts.i1, otherVerts.i2); 540 } 541 542 // Form a new test tri from LMV, and the 2 new leftmost verts above 543 mTestTri.setVert(outerVerts2.i1, 0); 544 mTestTri.setVert(outerVertIdx, 1); 545 mTestTri.setVert(outerVerts2.i2, 2); 546 547 // See if there are verts inside this new test tri 548 findPointsInside(); 549 } 550 551 // We have found a valid tri 552 mTris.push_back(mTestTri); 553 554 // Remove edges common to test tri and poly... add unique edges from test tri to poly 555 addRemoveEdge(mTestTri.getVert(0), mTestTri.getVert(1)); 556 addRemoveEdge(mTestTri.getVert(1), mTestTri.getVert(2)); 557 addRemoveEdge(mTestTri.getVert(0), mTestTri.getVert(2)); 558 559 // This should never take 255 iterations... we must be stuck in an infinite loop 560 if(counter++ > 255) 561 { 562 newPoly(); 563 return false; 564 } 565 566 // Reset attempts 567 formTriAttempt = 0; 568 uniqueVertAttempt = 0; 569 } 570 571 // The last tri 572 mTris.push_back(formTriFromEdges(0,1)); 573 574 // The verts need to be ordered to draw correctly 575 for(U8 i = 0; i < mTris.size(); i++) 576 { 577 mTris[i].orderVerts(); 578 } 579 580 return true; 581} 582