search

mapbox / delaunator

An incredibly fast JavaScript library for Delaunay triangulation of 2D points
https://mapbox.github.io/delaunator/
ISC License
2.34k stars 141 forks source link

Preserving original triangles/faces indexing #64

Closed vkuchinov closed 4 years ago

vkuchinov commented 4 years ago

Hi there,

I have a pseudo quadtree geometry (THREE.BufferGeometry) set by a series of points.

screenshot1

Each partition has to be rendered through its own draw call by geometry.addGroup() method and individual material. Everything works fine.

However, for my own purposes, I have to use your Delaunator.JS to process original geometry and it seems that output has another indexing for triangles (faces) starting from center.

screenshot2

So, is there a way to rearrange faces back to original indexing, so I could get the same result as my first image with similar multiple draw calls?

I'm not asking for tweaking your Delanuator.JS code but for some hints.

mourner commented 4 years ago

Unfortunately this algorithm has no way of controlling how triangulation is formed in a case where there can be multiple Delaunay triangulations of the same point set (such as a grid). You could try rearranging it with a custom script but I'm not away of existing code examples to do so.

vkuchinov commented 4 years ago

That's really sad. I don't want to write another post-processing script for re-sorting, cause it could slow down the whole performance. I will try to tweak Delaunay.JS by extending 3D vectors with another indexing value and tweaking triangles generation according to these values.

redblobgames commented 4 years ago

It's not only the indexing that changed, but the triangles themselves are different. For example in the lower left there's a square that has a different triangle in Delaunator than in your original set of triangles. And Delaunator can't always reuse your original triangles because they're not a valid Delaunay triangulation.

Two ideas:

  1. If you use a different algorithm, like "edge flipping", you might be able to start with your original triangulation and incrementally change the triangles that do not match the Delaunay condition. This would preserve some of them.
  2. If you only want to find the triangles that are shared between the original and the Delaunator version, you can hash the original ones by sorted point id. For example if the original triangulation had a triangle [point id: 5, point id: 3, point id: 27] then you can sort those point ids to [3, 5, 27]. If Delaunator produces a triangle with those same points, but maybe a different order [27, 3, 5] then you can sort those too and get [3, 5, 27] and then match them up with the original triangles. This way you could find the original triangle ids.