I’m working on a tool to close holes in geometry and for this I need to able to bridge two continuous open edges in a nice and clean fashion:
Using 3dsmax’s bridge yields a result, but usually it’s messy, because the borders have different vertex number and distribution.
From searching the web, it seems that looking into the delaunay triangulation is a step in the right direction, but even then it’s tricky because in this case I already have some faces and only need to add some - a simple convex hull around the border vertices would not be usable.
The thought of having to implement a 2.5-dimensional delaunay trianglulation algorithm makes my head spin… :s
How would you deal with this problem in the most effective manner?
How many assumptions are you willing to make? You could grab the two ‘groups’ of edges, and look at their relative positions/orientations/sizes, and best-guess the matching verts/edges from there. For your given example, it wouldn’t be too difficult. The more non-uniform the data gets, the more difficult such an algorithm would be to write (to the point that you’d need to write a more general purpose algorithm altogether). But if it suits your needs, you could start there.
An example algo would go something like:
For a given edge in ‘island 1’ (1A), find all edges of ‘island 2’ that have a similar orientation (normal from edge point 1 to edge point 2).
For each similar edge in island 2, get all the adjacent edges, and sort them according to their normal.
Compare the sorted edges to adjacent edges in island 1’s edge, and choose the island 2 edge that has the most similar matching adjacent edges.
If 2 island 2 edges match equally well, pick the one that is spatially closer.
That edge is the matching ‘bridge’ edge from island 1 edge A to island 2 edge A.
I know such an algorithm would work for many cases, and it could be improved substantially, but that’s a general (and verbose) idea for something that may not work at all for the cases you need it to
It took a while, but ended up with a solution - making many assumptions about the input geometry, like you said.
I would have loved to come up with a very general algogrithm, but it seems that even in the field of triangulation math, there’s no one-size-fits-all solution and those that exist are complicated to implement for my case.
So in the end I went by vertex proximity really.
First I extrude all border-edges of one island and weld the new verts to the closest vert of the other island. After that step all verts of the first island will be connected.
Then I loop through the remaining verts of the second island, find the closest open edge on the first island and divide that edge as close to the vert as possible - then the new verts gets welded again.
Here’s an animation to illustrate the steps:
It sounds simple on paper, but I needed to do use a lot of sorting and vert/edge-flagging tricks, because the vertex/edge-order changes constantly.
Also the algorithm will generate overlapping triangles if an edge has exotic ‘cavities’ or if there are very many vertices in a small area, but for my purpose this should happen rarely.
