Finds needed mesh part based on components relative positions (inside/outside) returns std::nullopt if given cuts do not divide origin mesh on good components (e.g. cuts have self-interections or components are not consistently oriented)
| 25 | // Finds needed mesh part based on components relative positions (inside/outside) |
| 26 | // returns std::nullopt if given cuts do not divide origin mesh on good components (e.g. cuts have self-interections or components are not consistently oriented) |
| 27 | std::optional<FaceBitSet> findMeshPart( const Mesh& origin, |
| 28 | const std::vector<EdgePath>& cutPaths, const Mesh& otherMesh, bool needInsideComps, |
| 29 | bool originIsA, const AffineXf3f* rigidB2A, |
| 30 | bool mergeAllNonIntersectingComponents, const BooleanInternalParameters& intParams ) |
| 31 | { |
| 32 | MR_TIMER; |
| 33 | BaseUnionFind<FaceId> unionFind; |
| 34 | if ( cutPaths.empty() ) |
| 35 | unionFind = MeshComponents::getUnionFindStructureFaces( origin ); |
| 36 | else |
| 37 | { |
| 38 | UndirectedEdgeBitSet cutEdges( origin.topology.undirectedEdgeSize() ); |
| 39 | for ( const auto& path : cutPaths ) |
| 40 | for ( auto e : path ) |
| 41 | cutEdges.set( e ); |
| 42 | if ( intParams.graphCutSeparation ) |
| 43 | { |
| 44 | auto left = fillContourLeftByGraphCut( origin.topology, cutPaths, edgeAbsCurvMetric( origin ) ); |
| 45 | cutEdges |= findRegionBoundaryUndirectedEdgesInsideMesh( origin.topology, left ); |
| 46 | } |
| 47 | unionFind = MeshComponents::getUnionFindStructureFaces( origin, MeshComponents::PerEdge, &cutEdges ); |
| 48 | } |
| 49 | |
| 50 | FaceBitSet res( origin.topology.lastValidFace() + 1 ); |
| 51 | FaceBitSet connectedComp( origin.topology.lastValidFace() + 1 ); |
| 52 | AffineXf3f a2b = rigidB2A ? rigidB2A->inverse() : AffineXf3f(); |
| 53 | bool needRightPart = needInsideComps != originIsA; |
| 54 | |
| 55 | FaceId leftRoot; // root of the components to the left of cutPaths |
| 56 | FaceId rightRoot; // root of the components to the right of cutPaths |
| 57 | if ( !cutPaths.empty() ) |
| 58 | { |
| 59 | // unite regions separately to the left and to the right of cutPaths |
| 60 | for ( const auto& path : cutPaths ) |
| 61 | for ( auto e : path ) |
| 62 | { |
| 63 | if ( auto l = origin.topology.left( e ) ) |
| 64 | leftRoot = leftRoot ? unionFind.uniteUnbalanced( leftRoot, l ).first : unionFind.find( l ); |
| 65 | if ( auto r = origin.topology.right( e ) ) |
| 66 | rightRoot = rightRoot ? unionFind.uniteUnbalanced( rightRoot, r ).first : unionFind.find( r ); |
| 67 | } |
| 68 | |
| 69 | // if last unite merged left and right, we need to update roots |
| 70 | if ( leftRoot ) |
| 71 | leftRoot = unionFind.find( leftRoot ); |
| 72 | if ( rightRoot ) |
| 73 | rightRoot = unionFind.find( rightRoot ); |
| 74 | |
| 75 | if ( leftRoot && leftRoot == rightRoot ) |
| 76 | return std::nullopt; |
| 77 | } |
| 78 | |
| 79 | updateRootsParallel( unionFind ); |
| 80 | |
| 81 | // find correct part |
| 82 | auto includeRoot = needRightPart ? rightRoot : leftRoot; |
| 83 | auto excludeRoot = needRightPart ? leftRoot : rightRoot; |
| 84 | for ( auto f : origin.topology.getValidFaces() ) |
no test coverage detected