Iterate over all new faces and fix faces that are forming a concave or coplanar shape in order to always keep the hull convex
| 502 | |
| 503 | // Iterate over all new faces and fix faces that are forming a concave or coplanar shape in order to always keep the hull convex |
| 504 | void QuickHull::mergeConcaveFaces(QHHalfEdgeStructure& convexHull, Array<QHHalfEdgeStructure::Face*>& newFaces, |
| 505 | const Array<Vector3>& points, decimal epsilon, Set<QHHalfEdgeStructure::Face*>& deletedFaces) { |
| 506 | |
| 507 | assert(newFaces.size() > 0); |
| 508 | |
| 509 | // For each new face |
| 510 | uint32 i = 0; |
| 511 | while(i < newFaces.size()) { |
| 512 | |
| 513 | QHHalfEdgeStructure::Face* face = newFaces[i]; |
| 514 | |
| 515 | // If the face has not been deleted during the process of merging the concave faces |
| 516 | if (!deletedFaces.contains(face)) { |
| 517 | |
| 518 | QHHalfEdgeStructure::Edge* concaveEdge = nullptr; |
| 519 | |
| 520 | // For each edge of the new face |
| 521 | QHHalfEdgeStructure::Edge* firstFaceEdge = face->edge; |
| 522 | QHHalfEdgeStructure::Edge* faceEdge = firstFaceEdge; |
| 523 | do { |
| 524 | |
| 525 | assert(faceEdge != nullptr); |
| 526 | |
| 527 | // If the two faces at this edge are forming a convex shape |
| 528 | if (testIsConvexEdge(faceEdge, epsilon)) { |
| 529 | |
| 530 | // Move to the next edge of the face |
| 531 | faceEdge = faceEdge->nextFaceEdge; |
| 532 | |
| 533 | continue; |
| 534 | } |
| 535 | |
| 536 | // The two faces at this edge are forming a concave or coplanar shape |
| 537 | concaveEdge = faceEdge; |
| 538 | break; |
| 539 | |
| 540 | } while(faceEdge != firstFaceEdge); |
| 541 | |
| 542 | // If we have found a concave or coplanar edge |
| 543 | if (concaveEdge != nullptr) { |
| 544 | |
| 545 | assert(concaveEdge->face == face || concaveEdge->twinEdge->face == face); |
| 546 | |
| 547 | // Merge the two faces at this edge |
| 548 | mergeConcaveFacesAtEdge(concaveEdge, convexHull, points, deletedFaces); |
| 549 | |
| 550 | continue; |
| 551 | } |
| 552 | } |
| 553 | |
| 554 | i++; |
| 555 | } |
| 556 | } |
| 557 | |
| 558 | // Merge two faces that are concave at a given edge |
| 559 | void QuickHull::mergeConcaveFacesAtEdge(QHHalfEdgeStructure::Edge* edge, QHHalfEdgeStructure& convexHull, const Array<Vector3>& points, |