Iterate over all new faces and fix faces that are forming a concave or coplanar shape in order to always keep the hull convex by giving priority to large faces
| 426 | // Iterate over all new faces and fix faces that are forming a concave or coplanar shape in order to always keep the hull convex by |
| 427 | // giving priority to large faces |
| 428 | void QuickHull::mergeLargeConcaveFaces(QHHalfEdgeStructure& convexHull, Array<QHHalfEdgeStructure::Face*>& newFaces, |
| 429 | const Array<Vector3>& points, decimal epsilon, Set<QHHalfEdgeStructure::Face*>& deletedFaces) { |
| 430 | |
| 431 | assert(newFaces.size() > 0); |
| 432 | |
| 433 | // For each new face |
| 434 | uint32 i = 0; |
| 435 | while(i < newFaces.size()) { |
| 436 | |
| 437 | QHHalfEdgeStructure::Face* face1 = newFaces[i]; |
| 438 | |
| 439 | // If the face has not been deleted during the process of merging the concave faces |
| 440 | if (!deletedFaces.contains(face1)) { |
| 441 | |
| 442 | QHHalfEdgeStructure::Edge* concaveEdge = nullptr; |
| 443 | |
| 444 | // For each edge of the new face |
| 445 | QHHalfEdgeStructure::Edge* firstFaceEdge = face1->edge; |
| 446 | QHHalfEdgeStructure::Edge* faceEdge = firstFaceEdge; |
| 447 | do { |
| 448 | |
| 449 | assert(faceEdge != nullptr); |
| 450 | |
| 451 | // Get the two neighbor faces |
| 452 | assert(faceEdge->twinEdge != nullptr); |
| 453 | QHHalfEdgeStructure::Face* face2 = faceEdge->twinEdge->face; |
| 454 | assert(!deletedFaces.contains(face2)); |
| 455 | |
| 456 | if (face1->area > face2->area) { |
| 457 | |
| 458 | // We test if the center of face2 is below the face1 plane (if edge is convex w.r.t face1) |
| 459 | if (computePointToPlaneDistance(face2->centroid, face1->normal, face1->centroid) < -epsilon) { |
| 460 | |
| 461 | // Move to the next edge of the face |
| 462 | faceEdge = faceEdge->nextFaceEdge; |
| 463 | |
| 464 | continue; |
| 465 | } |
| 466 | |
| 467 | // The two faces at this edge are forming a concave or coplanar shape |
| 468 | concaveEdge = faceEdge; |
| 469 | break; |
| 470 | } |
| 471 | |
| 472 | // We test if the center of face1 is below the face2 plane (if edge is convex w.r.t face2) |
| 473 | if (computePointToPlaneDistance(face1->centroid, face2->normal, face2->centroid) < -epsilon) { |
| 474 | |
| 475 | // Move to the next edge of the face |
| 476 | faceEdge = faceEdge->nextFaceEdge; |
| 477 | |
| 478 | continue; |
| 479 | } |
| 480 | |
| 481 | // The two faces at this edge are forming a concave or coplanar shape |
| 482 | concaveEdge = faceEdge; |
| 483 | break; |
| 484 | |
| 485 | } while(faceEdge != firstFaceEdge); |
nothing calls this directly
no test coverage detected