Remove doubles taking into account vertex normals

I need a fast algorithim for removing double vertexs from a mesh, but only ones where the vertexes have the same normal vector - so I can’t use .remDoubles(). It’s a fairly big mesh (6000 vertexs) so I’d like something reasonably quick! Any Python gurus out there there?

Many thanks


This is my attempt:

normalVectors=[ for v in mesh.verts]

for [v, nv] in zip(mesh.verts, normalVectors):
               if normalVectors.count(nv)>1 : 

[INDENT] v.sel = True
v.sel = False
Anybody think of anything better?

Does it work? If so, then its fine!

Yeah - it works - I just don’t like doing a .count for every vertex - I’d prefer to just run through the vertexs once. It just feels like there should be something cleverer.

You could probably make some data structure (some form of a binary tree) and put the vertex/normal data into it, and then traverse/construct it in such a way that you can know if there are duplicates, and mark those. That way you’d only wind up touching the data twice, essentially, once for construction and the next time for traversal.

Something where when you construct the tree you can have a node as:

node->left, right, vertex data, duplicate data

And store your duplicates in the duplicate data list, and then continue on.

When you traverse the tree, all your going to do is a standard traversal and at every node you check to see if the length of duplicate data is non-zero. If it is zero, continue the traversal without marking the vertex. If not, then you mark the vertex and each of its duplicates.

See the wikipedia page:

And there is also a link on that page to traversal of the trees as well.