Fix topological issue at a given edge
| 669 | |
| 670 | // Fix topological issue at a given edge |
| 671 | void QuickHull::fixTopologicalIssueAtEdge(QHHalfEdgeStructure& convexHull, QHHalfEdgeStructure::Face* face, |
| 672 | QHHalfEdgeStructure::Edge* inEdge, const Array<Vector3>& points, |
| 673 | Set<QHHalfEdgeStructure::Face*>& deletedFaces) { |
| 674 | |
| 675 | assert(inEdge->face == face); |
| 676 | |
| 677 | // If the opposite face is a triangle |
| 678 | if (inEdge->twinEdge->face->isTriangle()) { |
| 679 | |
| 680 | QHHalfEdgeStructure::Edge* edgeBeforeTriangle = inEdge->previousFaceEdge; |
| 681 | QHHalfEdgeStructure::Edge* edgeAfterTriangle = inEdge->nextFaceEdge->nextFaceEdge; |
| 682 | |
| 683 | QHHalfEdgeStructure::Face* faceToRemove = inEdge->twinEdge->face; |
| 684 | QHHalfEdgeStructure::Face* faceToKeep = face; |
| 685 | |
| 686 | // Make sure the face to keep does not reference the edge to be removed |
| 687 | faceToKeep->edge = edgeBeforeTriangle; |
| 688 | |
| 689 | // Make sure the remaining edge of the face to delete reference the face to keep |
| 690 | inEdge->twinEdge->nextFaceEdge->face = faceToKeep; |
| 691 | |
| 692 | // Fix the linked-list of face edges |
| 693 | edgeBeforeTriangle->nextFaceEdge = inEdge->twinEdge->nextFaceEdge; |
| 694 | inEdge->twinEdge->nextFaceEdge->previousFaceEdge = edgeBeforeTriangle; |
| 695 | edgeAfterTriangle->previousFaceEdge = inEdge->twinEdge->nextFaceEdge; |
| 696 | inEdge->twinEdge->nextFaceEdge->nextFaceEdge = edgeAfterTriangle; |
| 697 | |
| 698 | // Move the remaining closest vertices of the face to remove to the face to keep |
| 699 | faceToKeep->conflictPoints.addRange(faceToRemove->conflictPoints); |
| 700 | |
| 701 | // Remove the face |
| 702 | convexHull.deleteFace(faceToRemove); |
| 703 | deletedFaces.add(faceToRemove); |
| 704 | |
| 705 | QHHalfEdgeStructure::Vertex* vertexToRemove = inEdge->endVertex; |
| 706 | |
| 707 | // Remove the edges |
| 708 | convexHull.removeHalfEdge(inEdge->nextFaceEdge->twinEdge); |
| 709 | convexHull.removeHalfEdge(inEdge->nextFaceEdge); |
| 710 | convexHull.removeHalfEdge(inEdge->twinEdge); |
| 711 | convexHull.removeHalfEdge(inEdge); |
| 712 | |
| 713 | // Remove the redundant vertex |
| 714 | convexHull.removeVertex(vertexToRemove); |
| 715 | |
| 716 | assert(edgeBeforeTriangle->nextFaceEdge->previousFaceEdge == edgeBeforeTriangle); |
| 717 | assert(edgeAfterTriangle->previousFaceEdge->nextFaceEdge == edgeAfterTriangle); |
| 718 | assert(edgeBeforeTriangle->nextFaceEdge->face == faceToKeep); |
| 719 | assert(faceToKeep->edge->face == faceToKeep); |
| 720 | assert(edgeBeforeTriangle->nextFaceEdge->twinEdge->twinEdge == edgeBeforeTriangle->nextFaceEdge); |
| 721 | |
| 722 | // Recalculate the face centroid and normal to better fit its vertices (using Newell method) |
| 723 | faceToKeep->recalculateFace(points); |
| 724 | |
| 725 | assert(faceToKeep->isValid()); |
| 726 | } |
| 727 | else { // If the opposite face is not a triangle |
| 728 |
nothing calls this directly
no test coverage detected