Feature Request (Mesh) - Speedy MidPoint Matching

Rhino Developer
1

I need things like the following “matching” operations all the time, and since they are quite expensive to code look up in big meshes, it would be great to have it solved on the lowest code level:

Mesh:
Point3d Edge.GetMidPoint()
Point3d[ ] TopologyEdges.GetMidPoints(); // Like GetFaceCenters();
int[ ] TopologyEdges.MatchMidPoint(Point3d point);
int[ ] Faces.MatchCenterPoint(Point3d center);

Why I often need these is that on huge meshes I manipulate only an extracted part of the original mesh, but the part-mesh will not have the same indices, so to map the two meshes I “match” edges (midpoint) and faces (also using midpoints) to get the corresponding indices.

Using part-meshes often speed things up with magnitudes, while the index-mapping (matching) between the two currently consumes some* of that performance gain.

Having the above functions with good performance would really be gold. And I would rush to upgrade to R7 :wink:

// Rolf

  • I do have a solution based on key-value Dictionary<Point3d, Int> lists where I precompute the Edge-midpoints and similarly for Face centers, but all that trickery should be done on the C/C++ level… :slight_smile:
2

Ping! @steve @dale :slight_smile:

// Rolf

3

Since this is RhinoCommon, not Grasshopper, I moved it to the Rhino Developer category.

1 Like
6

Added to the wishlist at
https://mcneel.myjetbrains.com/youtrack/issue/RH-62004

1 Like
7

I tried to make my own “unsafe” version of the basic idea (for Faces) but the code below wasn’t any faster than collecting the face-midpoints with the existing method (looping over Mesh.GetFaceCenters(i); ):

  public static class MeshExt
    {
        /// <summary>
        /// Unsafe. Extends a Mesh with a CenterPoint to Face-Indices 
        /// mapper (Dictionary).
        /// </summary>
        public unsafe static Dictionary<Point3d, int> GetPointToIndicesMapping_Unsafe(this Rhino.Geometry.Mesh mesh, 
            out int face_dupes_count,  int decimals = 4)
        {
            face_dupes_count = 0;
            var point_index_mapper = new Dictionary<Point3d, int>();

            // accessing the mesh and its raw arrays
            using (var mesh_access = mesh.GetUnsafeLock(false))
            {
                // Pointers to the beginning of the respective raw arrays
                var p_face = mesh_access.FacesArray(out int face_len);
                var p_vertices = mesh_access.VertexPoint3fArray(out int vert_len);

                // Calculate face center point from vertices and store the 
                // center point and the face indices in the dictionary.
                // Rounding (n decimals) helps prune off dupe faces being the 
                // the close but not having "bit-exactly" matching center points.
                for (int index = 0; index < face_len; index++)
                {
                    Point3f* p_vertice_A, p_vertice_B, p_vertice_C;

                    // Advance vertex pointer to each face-corner's respective vertex position:
                    p_vertice_A = p_vertices + p_face->A;
                    p_vertice_B = p_vertices + p_face->B;
                    p_vertice_C = p_vertices + p_face->C;

                    // Calc face center
                    var center = new Point3d
                    {
                        X = p_vertice_A->X + p_vertice_B->X + p_vertice_C->X,
                        Y = p_vertice_A->Y + p_vertice_B->Y + p_vertice_C->Y,
                        Z = p_vertice_A->Z + p_vertice_B->Z + p_vertice_C->Z
                    };
                    center /= 3; // = center

                    if (decimals > 0) // skip rounding if <= 0
                    {
                        center.X = Math.Round(center.X, decimals); // Fixed bug
                        center.Y = Math.Round(center.Y, decimals);
                        center.Z = Math.Round(center.Z, decimals);
                    }

                    // Add center point (=key) and face index (value) to 
                    // the mapper, returning count of any skipped dupes.
                    try { point_index_mapper.Add(center, index); }
                    catch {  face_dupes_count++; }

                    // advance face pointer
                    p_face++;
                }
                return point_index_mapper;
            }
        }

This kind of works, but calculating the center points with C# is slower than the API method GetFaceCenters() etc, etc.

The Dictionary should have been a ConcurrentDictionary to speed up the loading of items (reading is isn’t very fast using this dict either).

Hope this inspires you to much better ideas about how to speed this up.

The code above, plus the “remapper” resolving the indices, has the following profiling numbers for a 2.6 million faces “BaseMesh” (blue) with a smaller SubMesh (red) remapping its (280.000) indices against that big ugly one .

Profiling with Unsafe method
Profiling with Unsafe method1492×670 183 KB

Those numbers should go down significantly, both for the mapper and the remapper. Btw, the component to the far left is replacing the native Rhino.GetDuplicateFaces() and runs 2x faster. :wink:

// Rolf

  • Edit: Rounding bug fixed.