Dictionary key using Point3d fails in Python script

unhandled

#1

I tried using these three points in a mesh face:

p1 = Point3d(30.26158, 98.61151, 99.7001)
p2 = Point3d(30.06, 98.78133, 99.66506)
p3 = Point3d(30.04039, 98.67528, 99.86947)

as keys to a dictionary but p1 and p2 map to the same value creating a degenerate face. If the points are multiplied by 2 or more and then used as a key, all 3 points map to unique values. I noticed this when removing duplicate vertices in a mesh. A dictionary with the vertex as a key was used to detect duplicate vertices in the code below:

    vt = {}; i = 0; ii = -1; num = 0; xlate = {}
	for pt in vertices:
		kpt = 2*pt
		if pt in vt: vt[kpt].append(i); num += 1
		else: vt[kpt] = [i]; ii += 1; nvertices.Add(pt)
		xlate[i] = ii
		i += 1
	print 'At start, number of identical vertices = ',num

If a multiplier of 1 is used in place of 2 above, then 26,990 out of 1,364,883 vertices are reported as identical. With a multiplier of 2, no identical vertices are reported.

Another important case for me is trimming a mesh and preserving vertex colors. In this case it is very convenient to use the vertex point as a dictionary key for easy recovery of the vertex colors in the trimmed mesh.

In the starting mesh I do this:

vertices = meshGeo.Vertices
colors = meshGeo.VertexColors
vcount = vertices.Count
for i in xrange(vcount): p2c[vertices[i]] = colors[i]

Then for the trimmed mesh which has all new vertices and faces, I do this to recover the colors:

from System import Array
vertices = trimmed_meshGeo.Vertices
vcount = vertices.Count
# Create .NET type array for holding vertex colors.
colors = Array.CreateInstance(Color, vcount)
for i in xrange(vcount):
   vertex = vertices[i]
   # Try getting color from vertex in start mesh.
   if vertex in p2c: colors[i] = p2c[vertex]
meshGeo.VertexColors.Clear()
meshGeo.VertexColors.SetColors(colors)

Is there another way to do this without using vertices as keys?


(Graham) #2

Hmm this is presumably because the points are within the rhino tolerance ? You can use a tuple of the coordinates instead if you want to preserve neighbours. Also you can use a set instead of a dictionary if you don’t need to retain the order.
What is your aim in the end?


(Graham) #3

Can you use one of the closest point functions from rhinocommon?

Public method ClosestMeshPoint Gets the point on the mesh that is closest to a given test point. Similar to the ClosestPoint function except this returns a MeshPoint class which includes extra information beyond just the location of the closest point.
Public method ClosestPoint(Point3d) Gets the point on the mesh that is closest to a given test point.
Public method ClosestPoint(Point3d, Point3d, Double) Gets the point on the mesh that is closest to a given test point.
Public method ClosestPoint(Point3d, Point3d, Vector3d, Double) Gets the point on the mesh that is closest to a given test point.

#4

Thanks for replying.

I hate sets when working with meshes having 1M to 50M faces because they are so slow. Even using a dictionary burns up 20 sec to load the 9M vertices in an 18M face mesh. I am beginning to find ways to reduce this like by only loading points inside the area to be trimmed which is modeled by its bounding box. The load time is cut in half or more if the trimmed area is less than 50% of the starting mesh. This means that doing 4 bounds checks is over twice as fast as generating 1 dictionary entry.

Rhino’s tolerance is not in play as the points I showed are what go into the dictionary. It is the Python hashing function that is at fault. Maybe I should look at using a custom hash function that better comprehends using Point3d as a key.

Regards,
Terry.


(Graham) #5

Strange that a set should be slower - I wonder if that is an Ironpython thing as the implementation is pretty similar. Yes I think if you can use the builtin RTree methods to avoid searching outside your bounding area and to find the closest vertex then it should be much quicker than building your own hash table


#6

Maybe I should look at sets some more. How do I use a set for this application where I need to find a color given a vertex?


(Graham) #7

They won’t help with that part - I was only thinking of the bit where you remove duplicates. For the colour mapping you need a dict or a (presumably faster ) Rhinocommon function.


#8

I can’t quite figure out how your duplicate detector works (it is too cryptic for my primitive syntax skill level), but I was interested in the hashing.

For your 3 points, I get the .hash()es of:

p1 = R.Geometry.Point3d(30.26158, 98.61151, 99.7001)
p2 = R.Geometry.Point3d(30.06, 98.78133, 99.66506)
p3 = R.Geometry.Point3d(30.04039, 98.67528, 99.86947)

vertices = [p1, p2, p3]

for pt in vertices:
    print('Point {} has a hash of {}'.format(pt, pt.__hash__()))

output:

Point 30.26158,98.61151,99.7001 has a hash of 586903699
Point 30.06,98.78133,99.66506 has a hash of 1888597473
Point 30.04039,98.67528,99.86947 has a hash of 320478372

I can’t quite figure out how to figure out how the hashes are made for a Point3d object, but they seem to be not close for close points.

Further test (maybe a more-simple duplicate detector):

p1 = R.Geometry.Point3d(30.26158, 98.61151, 99.7001)
p2 = R.Geometry.Point3d(30.06, 98.78133, 99.66506)
p3 = R.Geometry.Point3d(30.04039, 98.67528, 99.86947)

vertices = [p1, p2, p3]
points = {}

for pt in vertices:
    if pt not in points:
        print('point {} is not in dictionary'.format(pt))
        points[pt] = 1
    else:
        print('point {} is in dictionary'.format(pt))
        points[pt] += 1
        
for k, v in points.items():
    print('point {} occurred {} times'.format(k, v))
    
# try with some duplicates
vertices = [p1, p2, p2, p3, p3, p3]
# clear out the dict
points = {}

for pt in vertices:
    if pt not in points:
        print('point {} is not in dictionary'.format(pt))
        points[pt] = 1
    else:
        print('point {} is in dictionary'.format(pt))
        points[pt] += 1
        
for k, v in points.items():
    print('point {} occurred {} times'.format(k, v))

outputs:

point 30.26158,98.61151,99.7001 is not in dictionary
point 30.06,98.78133,99.66506 is not in dictionary
point 30.04039,98.67528,99.86947 is not in dictionary
point 30.06,98.78133,99.66506 occurred 1 times
point 30.26158,98.61151,99.7001 occurred 1 times
point 30.04039,98.67528,99.86947 occurred 1 times


point 30.26158,98.61151,99.7001 is not in dictionary
point 30.06,98.78133,99.66506 is not in dictionary
point 30.06,98.78133,99.66506 is in dictionary
point 30.04039,98.67528,99.86947 is not in dictionary
point 30.04039,98.67528,99.86947 is in dictionary
point 30.04039,98.67528,99.86947 is in dictionary
point 30.06,98.78133,99.66506 occurred 2 times
point 30.26158,98.61151,99.7001 occurred 1 times
point 30.04039,98.67528,99.86947 occurred 3 times

So I don’t see any problems with the hashes of your example points, unless I’m completely off in the weeds and don’t understand the problem.

No real answer for you. I thought perhaps that the multiplying by 2 would give you new hashes every time, but it seems consistent here, so I’m not sure why it makes a difference on your side. It would also suggest the hash is completely position dependent…hmm.


#9

Hi @Terry_Chappell, have you tried this:

import Rhino

a = Rhino.Geometry.Point3d(10,10,20)
print a.GetHashCode()

b = Rhino.Geometry.Point3d(10.0,10.0000000000000001,20.0)
print b.GetHashCode()

Probably best to avoid Point3d as dictionary keys. To reduce rounding errors or errors caused by scientific notations you might round / truncate the point coords, then get the hash as above. But it won’t be any faster if you’ll have to round again for dictionary lockups.

For larger meshes, you might compare the times. I’ll asume that getting closest mesh points / vertexcolor to the untrimmed mesh is faster as it can be threaded.

The real problem is that the vertex colors do not survive the trim operation.
_
c.


#10

Very interesting result. But not what happens inside the loop processing the 1M+ vertices when no multiplier is used. Using a 2 multiplier is enough. And that is what I am using for now. This is simple and avoids adding any more time by round/truncate the points coords for store/loopup.

I did some more timing and found this is working quite well:
Just touching the 1M+ vertices and checking that they lie within the bounding box of the trimmed area takes 3.5 sec. Generating the dictionary for typical cases where less than half of the mesh is left after trimming adds another 2 sec. So 5.5 sec total. Lookup and assigning colors after trimming takes less than a second.

Processing the whole mesh without bBox filtering, just loading the dictionary takes 20 sec.

So I am calling this good enough.

Thanks for looking into this. I especially liked learning how to view the hash being generated.

Regards,
Terry.


#11

After @clement 's reply I went back and found that if I incremented a point by 1/100000 (I think, it was a lot of zeroes) of the document absolute tolerance I could get an equal hash. But those are some close points!

If it works, it works!

Also the .GetHashCode() gave same results as the python hash.


#12

@clement,

I followed your advise and got rid of using Point3d as a dictionary key. I found that if I am careful to add a vertex color for every vertex I add to the mesh, then when I compress the mesh to help make it valid, all the vertex colors are kept. Thus I do not need a dictionary to add back the colors after trimming the mesh. This saves 20 sec for the dictionary creation and a few seconds for re-applying the colors after trimming. Overall a really great win.

Thanks for your help in this journey.

Regards,
Terry.