EdgeLine bad for finding distance to point

Rhino Developer
1

@pascal, @nathanletwory,
I am developing a Python script to trim a mesh in cases where Rhino’s Mesh trim fails. As part of this, a closed boundary curve is projected onto a mesh which creates points everywhere the line crosses the edge of a mesh face. ClosestPoint is used to find which mesh face the point falls on and then the distance from the point to each face edge is found to select the closest edge. But the shocking thing I discovered is that if I used the EdgeLine method to get lines representing the 3 edges, then the measured distances are about a million times less accurate than using the 3 vertices of a face to make 3 edge lines from scratch. Below is shown the portion of the script where I compare these two approaches:

# Use vertices of face to make edge lines for the face.
i2,i3,i1,ix = faces[f_index]; p1,p2,p3 = vertices[i1],vertices[i2],vertices[i3]
# Make lines for edges of face from vertices.
l1,l2,l3 = Line(p1,p2),Line(p2,p3),Line(p3,p1)
# Find distance from boundary point pt to edge lines.
d1p,d2p,d3p = l1.DistanceTo(pt,True),l2.DistanceTo(pt,True),l3.DistanceTo(pt,True)
# This gives very accurate results.
print 'Vertices: face {0} Distances = {1:.4e}, {2:.4e}, {3:.4e}'.format(f_index,d1p,d2p,d3p)
	
# Use EdgeLine to make edge lines of face.
e1,e2,e3 = edges.GetEdgesForFace(f_index)
# Get edge line of edges.
l1,l2,l3 = edges.EdgeLine(e1),edges.EdgeLine(e2),edges.EdgeLine(e3)
# Find distance from boundary point pt to edge lines.
d1p,d2p,d3p = l1.DistanceTo(pt,True),l2.DistanceTo(pt,True),l3.DistanceTo(pt,True)
# This is a million times less accurate.
print 'EdgeLines: face {0} Distances = {1:.4e}, {2:.4e}, {3:.4e}\n'.format(f_index,d1p,d2p,d3p)

If you run the attached Python script on the attached .3dm file, you will see a printout of the distances from each boundary point to the 3 edges of the mesh face it crosses calculated in 2 ways (1) First with the lines for the edges of the face constructed using the mesh vertices and (2) using EdgeLine to create a line for each edge. On each printout line (a few are shown below), the distance to the closest edge is very small, around 1e-14 when using vertice-created lines and around 1e-6 when using EdgeLine-created lines. Changing the document Absolute tolerance made no difference in this result.

Vertices:  face 1720 Distances = 8.8818e-16, 1.7747e-01, 6.7850e-02
EdgeLines: face 1720 Distances = 1.8368e-06, 1.7747e-01, 6.7850e-02

Vertices:  face 1719 Distances = 1.4222e-01, 1.4211e-14, 2.1637e-01
EdgeLines: face 1719 Distances = 1.4222e-01, 8.2492e-07, 2.1637e-01

One could say both are small so why worry? But for large meshes with 10M faces, I had been getting many failures in identifying the correct edge using EdgeLine. Now that I have switched to using vertice-created lines, all these failures are gone. This has provided a major improvement in the robustness of my mesh trimming script.

Is it reasonable that these two methods should give a million times different result?

EdgeLinePoor.py (10.3 KB)
TinyMeshEdgeLinePoor.3dm (341.4 KB)

2

It is coming up on 3 weeks since my first post without any response. I was hoping for some insight into this issue as it may be helpful in understanding other problematic numerical issues associated with meshes.

3

Hi @Terry_Chappell,

The indexer for MeshVertexList returns single-precision (Point3f) points, as where MeshTopologyEdgeList.EdgeLine constructs a line from the mesh’s double-precision (Point3d) vertices.

In this case you wall want to access vertex locations using MeshVertexList.Point3dAt().

– Dale

4

The results I obtained are opposite of what you said: Using MeshTopologyEdgeList.EdgeLine created from double-precision accurate mesh vertices results in finding a closest point that is over a million times further away that using edge lines created from the single-precision Point3f vertices from MeshVertexList.

Have you loaded the EdgeLinePoor.3dm, run my TinyMeshEdgeLinePoor.py script and looked at the results? Look at the bottom of the .py file to see where the main work is being done. I believe it clearly shows how poor the result is when using the line from MeshTopologyEdgeList.EdgeLine. I think this may be due to the fact that Curve.ProjectToMesh uses edge lines created with a single-precision representation of the mesh vertices. It finds the intersections of the curve with the edge of mesh faces and creates a point at this intersection. So if I want to test these points to find which face edge is closest, I also need to use edge-lines made from single-precision vertices. This way I am getting 1e-16 relative difference between points and their nearest face edge. The other way, using edge-lines created with double-precision vertices, I get 1e-8 relative difference, a 100 million times further away.

What you said about MeshVertexList.Point3dAt() returning double-precision results is something I did not realize. Up until now I have been confused about Mesh Tools -> Mesh Repair Wizard reporting the mesh as being a double-precision polygon mesh and then seeing meshGeo.Vertices[0] return Point3f values. I just tested and see that I can get double-precision values using meshGeo.Vertices.Point3dAt(0). Sometimes I speed up access to the x,y,z of the vertices by using Vertices.ToFloatArray but this only provides single-precision results. It would be nice to have a ToDoubleArray option. This I could really use.

Regards,
Terry.

5

Use MeshVertexList.ToPoint3dArray.

– Dale

6

@dale (please read my updates in my post below),

That provides the vertices but not the x,y,z components which takes more time.

By the way, when I went back and used vertices from Vertices.Point3dAt(i) to make the face edge-lines, the closest edge to a point taken from a curve generated by Curve.ProjectToMesh is a 100 million times further away than using Vertices[i]. This is the same comparison as done in TinyMeshEdgeLinePoor. I think this is due to Curve.ProjectToMesh using edge-lines created with single-precision vertices. In order to match that result very closely, I need to also use single-precision vertices when making the edge-lines. So while common sense would say to use double-precision vertices in making the edge-lines in order to get better results, in this particular case this does not work out as it does not match what Rhino is doing.

The core of what I am doing is trying to separate corner points from points on the edge of mesh faces when a closed polyline curve (which, in a simple case, has 4 corner points to define its boundary) is projected down onto the mesh. From Curve.ProjectToMesh I get a curve from which I get all the points on the mesh. Then I separate the corner points from the points on a mesh face edge based upon how far a point is from the closest edge. It seems to be working really well with Vertices[i] but falls apart when I use Vertices.Point3dAt(i). This is detailed in the example .py script & .3dm file that I attached to my post above. I really hope you can take a closer look at this so I can become a better Python/Rhino developer.

In summary, I think this must have something to do with how Curve.ProjectToMesh finds the intersection between the curve and the edge of the mesh faces to create a list of points from which it generates a curve that is returned from this method. I believe one needs to match Rhino’s method in order to get the better than 1e-16 relative difference I have been getting between the intersection points and the nearest face edge. Using double-precision vertices to generate the edge line kills this, causing a 100 million times worse result, around 1e-8. So my current conclusion is that Rhino’s Curve.ProjectToMesh uses edge-lines with single-precision accurate vertices when computing the intersection of the curve with the edge lines.

I wonder if this use of single-precision vertices is what is behind the failures of Curve.ProjectToMesh for cases where the curve passes over a vertex. In this case the curve returned by Curve.ProjectToMesh breaks into segments with repeated points at the ends of the segment. This case requires differentiating between an intersection with an edge of a mesh face and a mesh vertex. But with single-precision edge-lines, an intersection with a face edge near a vertex becomes bogus. This intersection could be anywhere within a circle 1e-8 around the vertex. Somewhere in the Rhino code this creates a logical condition not anticipated, resulting in broken curves with repeated points at their ends.

Regards,
Terry.

7

I guess I don’t understand this statement, as MeshVertexList.ToPoint3dArray returns an array of 3-D (e.g. x,y,z) point coordinates, where:

point_array[index) == mesh.Vertices.Point3dAt(index)

– Dale

8

It is not a flat list of x0,y0,z0,x1,y1,z1,x2,y2,z2,…
which is returned by ToFloatArray.
It is a list of 3D points like you said, not their x,y,z values.

9

Does Curve.ProjectToMesh use edge lines made from Point3f vertices when computing the intersection with the curve?

10

@Terry_Chappell - I am looking but the grim truth is, Dale is far better qualified to comment on this than I am - he actually knows what he’s doing, I bang around with 8 penny nails and two by fours…

-Pascal