Use octree for merging vertices?

[andybak]

I noticed you're using quantizing/hashing to determine when to weld nearly coincident vertices in the Combine method.

Am I right in thinking that this would incorrectly overlook vertices that were arbitrarily close but fell into different "bins" so to speak? I was wondering if an octree approach could be integrated - maybe as an optional alternative: https://github.com/bartofzo/NativeTrees

[CodeSmile-0000011110110111]

Can't recall off-hand but the intention was to weld close-by vertices, yes. To achieve that the space is subdivided into a very small grid, and if two vertices were on the same "grid" position they are welded but if not, then they weren't close enough.

It could be problematic if you were to move individual vertices, but since I work with generated meshes it does work. For example a cube's corner vertices will always be close enough to be welded and it will not happen that any face triangle will have a vertex not welded, whereas another triangle on another face has all of them welded.

But I'm not currently deep enough into the code to entirely reason about this. The Combine code was to be improved over time anyway.

[andybak]

My thinking was as follows. For the sake of simplicity let's assume you're quantizing to an integer grid. I'll also assume you're using "rounding to nearest integer" as the quantization method.

One vertex is at x=1.4999999 and that will get quantized into the x=1 bin. The nearest vertex is at x=1.50000001 and that will end up in the x=2 bin.

So - two vertices can be arbitrarily close but will get incorrectly missed by this algorithm. Does that make sense?