ποΈ AABB Tree Construction and Acceleration of Nearest Neighbor Queries
The MR::AABBTree, subsequently calling its search interface to expedite nearest neighbor computations. This significantly enhances the efficiency of point-to-face or point-to-point lookups (related source implementations can be found in MRMeshIntersect.h, MRMeshDistance.h, and other files).
ποΈ Core Data Structures
Mesh, Points, Edges, Triangles
ποΈ Triangulated Face Selection and Mesh Segmentation via Closed Curves
When segmenting a mesh using a closed curve, the initial step typically involves projecting the user-drawn 2D closed line onto the 3D surface of the mesh to obtain the corresponding three-dimensional edge path (EdgePath). The specific implementation generally entails projecting each 2D line segment along the line of sight onto the mesh, calculating intersection points, and connecting them to form a closed path on the mesh. Subsequently, the region extraction tools within MeshTopology can be employed; for instance, MR::fillContourLeft(topology, contourEdges) can compute all the triangles located to the left (or right) of the edge path, effectively yielding the set of faces encompassed by the closed line.
ποΈ Implementation Details of Hole Filling
In MeshTopology, holes are defined by edges that have only a single adjacent face (naked edges). The function MeshTopology: it begins by forming a polygonal chain along the boundary of the hole starting from the given edge, and then triangulates this polygon according to the filling strategy. This strategy is controlled by the parameters in FillHoleParams, such as maxPolygonSubdivisions (default value of 20), which limits the maximum depth of polygon subdivision, and FillHoleMetric, which can be used to evaluate triangle quality. Ultimately, the newly generated triangles are incorporated into MeshTopology, effectively eliminating the original openings of the hole. A simple example code is as follows:
ποΈ Continuous Allocation and Remapping of Vertex/Edge/Face Ids
Mesh elements (vertices VertId, edges EdgeId, faces FaceId) are allocated using contiguous integer indices. During mesh construction (for example, using MeshTopology::addPart, which incorporates another mesh into the current one), the vertices and faces of the second mesh continue numbering based on the existing counts, avoiding any conflicts.
ποΈ Point-to-Mesh Projection and AABB Acceleration
The functionality for projecting points to the nearest point on a mesh is typically accelerated using AABB trees. The typical workflow involves first constructing an MR::AABBTree for the entire mesh. During projection or distance calculations, the querying interface of the AABB tree (such as functions to find the nearest triangle) is invoked to rapidly filter candidate triangles. Subsequently, the precise distance from the point to each of these candidate faces is computed individually to identify the true nearest point. This hierarchical spatial indexing significantly reduces the overhead of traversing all triangles.
ποΈ Fix Undercuts
Within the MR: