Find the horizon (edges) forming the separation between the faces that are visible from the new vertex and the faces that are not visible
| 351 | |
| 352 | // Find the horizon (edges) forming the separation between the faces that are visible from the new vertex and the faces that are not visible |
| 353 | void QuickHull::findHorizon(const Vector3& vertex, QHHalfEdgeStructure::Face* face, |
| 354 | MemoryAllocator& allocator, |
| 355 | Array<QHHalfEdgeStructure::Vertex*>& outHorizonVertices, |
| 356 | Array<QHHalfEdgeStructure::Face*>& outVisibleFaces, decimal epsilon) { |
| 357 | |
| 358 | Stack<CandidateFace> facesToVisit(allocator); |
| 359 | Set<const QHHalfEdgeStructure::Face*> visitedFaces(allocator); |
| 360 | |
| 361 | facesToVisit.push(CandidateFace(face, face->edge)); |
| 362 | |
| 363 | outVisibleFaces.add(face); |
| 364 | |
| 365 | // While there still are faces to visit |
| 366 | while (facesToVisit.size() > 0) { |
| 367 | |
| 368 | // Get the next face to process |
| 369 | CandidateFace& candidateFace = facesToVisit.top(); |
| 370 | |
| 371 | // Mark the current face as visited |
| 372 | visitedFaces.add(candidateFace.face); |
| 373 | |
| 374 | bool goToVisibleFace = false; |
| 375 | |
| 376 | // For each edge of the current face |
| 377 | do { |
| 378 | |
| 379 | // Get the current edge to cross of the current face |
| 380 | const QHHalfEdgeStructure::Edge* edge = candidateFace.currentEdge; |
| 381 | assert(edge->face == candidateFace.face); |
| 382 | |
| 383 | const QHHalfEdgeStructure::Edge* twinEdge = edge->twinEdge; |
| 384 | |
| 385 | // Get the next face |
| 386 | QHHalfEdgeStructure::Face* nextFace = twinEdge->face; |
| 387 | |
| 388 | // If the next face is not visited yet |
| 389 | if (!visitedFaces.contains(nextFace)) { |
| 390 | |
| 391 | // If the next face is visible from the vertex |
| 392 | if (nextFace->normal.dot(vertex - nextFace->centroid) > epsilon) { |
| 393 | |
| 394 | // Add the next face to the stack of faces to visit |
| 395 | facesToVisit.push(CandidateFace(nextFace, twinEdge->nextFaceEdge)); |
| 396 | |
| 397 | outVisibleFaces.add(nextFace); |
| 398 | |
| 399 | goToVisibleFace = true; |
| 400 | |
| 401 | // If the face is visible we move to visit this new visible face (Depth First Search) |
| 402 | break; |
| 403 | } |
| 404 | else { // We have found a face that is not visible from the vertex |
| 405 | |
| 406 | // We add the edge between current face and next face to the array of horizon edges |
| 407 | outHorizonVertices.add(candidateFace.currentEdge->startVertex); |
| 408 | outHorizonVertices.add(candidateFace.currentEdge->endVertex); |
| 409 | } |
| 410 | } |