How to sort border edges for "bridge-type" operations?


#1

Hi. I guess everybody knows that standard bridge function on poly objects works a bit different if you apply bridge using borders insead of edges. Here’s a picture to demonstrate:

When you use edges and select 2 closed chains of edges and press bridge - everything will be messed up. Because in this case Its hard to understand which edges should be conneced to each other. Basically the problem is: when you have two arrays of unconnected edges, every first edge in 1st array should have a symmetrical edge in 2nd array and its kinda hard to define what is “symmetrical”.

But somehow they (max devs) solved this problem, because when you switch to borders and use bridge. It not only connecting 2 chains of edges correctly, but even more - 4, 6, etc…

I have a similar problem, but I can’t come up with something efficient. I know that they somehow analyze geometry in 3d space, because if you rotate one chain it will connect it differently. But how specifically?

Does anyone have some ideas?

Thanks.


#2

BridgeBorders uses MNMeshUtilites class do to the job. Its implementation isn’t available in the sdk source files.
Most likely it first divides borders into pairs by verts proximity and then connects them.


#3

Hm…
So… If i take random vertex (a) from 1st chain and find vertex (b) with shortest distance from (a) in 2nd chain. And then take an edge where (a) and (b) are on first position of getEdgeVerts array - that will be my starting edges to sort chain 1 and 2.

Sounds like an idea. Thanks.


#4

think I’d go with a two 2D shapes approach


#5

What do you mean?


#6

when you bridge between 2 edges they can be considered as two 2d polygons as projections onto a common plane. It can simplify the resulting comparison routines/best solutions.


#7

had a look at the difference in the code… it uses two different routines

MNMeshUtilities::BridgeSelectedBorders

and

IMNMeshUtilities8::BridgeSelectedEdges

I guess the edge routine just takes the edges in indexed order


#8

I guess the edge routine just takes the edges in indexed order

You mean like in the order of their indexes? Like: 5 123 456 2513?
If yes - that will give you random result.

But sorting unconnected edges is not hard you just can take edge selection, remove all “not open” edges. Then take any edge remove it from selection array and search for a neighbor from the left and from the right until you reach 2 edges which have only one neighbor or array is empty.

At the end you will get sorted chains of connected edges. To connect two chains - you just need to test if they are the same size and connect their vertices in reverse order.

Problems will start when chains become looped so the start and the end points will be unknown.


#9

Btw you was mentioned this…
But I keep thinking how to do it and nothing comes to my mind. Can you point me to right math or tell where I can see some examples?

I mean searching for a common plane in my mind already sounds like pretty complicated task. Finding a middle point is not hard its just an average, but how you can find an average normal vector? Like split it to triangles and do cross for each and then find an average?

Can you describe the idea in more detail?

Thanks.


#10

You can present a loop as a chain of verts ending with with the “first” index. And it is up to you to choose which index is first for particular loop.
What’s more complicated is what metric to use to determine the pairs of vert indexes that need to be connected.
Best result must consist of mostly rectangular polygons (in case when loops have equal verts count)

img

first and third are probably the best choise


#11

How about color? :grinning:

That approach of pair matching can lead to all kind of bad results, polygons crossing…

Algorithm is much straight, translate selection (groups) to common center and…

And no… If normals aren’t opposite enough it is mirroring x/y…
Checked after starting to write :grin:

But it is interactive tool, have option to twist result before committing.
Talking about Border/Poly version.


#12

And most likely it is also very slow.I tried to use minimal length of the resulting edges as metric, but it failed miserably in some cases. Skewed triangles count could be another one, but I didn’t try it. It probably doesn’t guarantee a good result as well.