Find middle edge in four way junction

thomthom

See this link: http://wiki.cgsociety.org/index.php/Edge_Loop

http://download.autodesk.com/global/docs/maya2012/en_us/index.html?url=files/Polygon_selection_and_creation_Edge_ring_and_edge_loop_selection_tips.htm,topicNumber=d28e121580

@unknownuser said:

In Maya, an edge loop has the following properties:

The vertices that connect the edges must have a valency equal to four. Valency refers to the number of edges connected to a particular vertex.

**The criteria for connecting the sequence is that the next edge in the sequence is the (i + 2nd) edge of the shared vertex, determined in order from the current edge (i).**

The sequence of edges (loop) can form either an open or closed path on the polygonal mesh.

The start and end edges need not have a valency equal to four.

How can one determine what is the middle edge in 3d space? How does one determine the 'order'?

thomthom

I tried to poke about in Blenders source, but I got nowhere...

thomthom

Note to self:
Blender 2.58a
editmesh_mods.c
Line 1854

Will see if I can work out what the code does...

Simon B

Would you like someone else to comment tt or are you just coding in your sleep?

thomthom

I always talk to myself to fill the silence...

TIG

Debating with yourself is the best kind - you're always right, one way or another...

A picked 'initial_edge' always has 2 vertices.
We can test each of these to see if it has four edges; if not we stop looking at that vertex.
Assuming the vertex has four edges we now have a list of three edges [the original_edge is already known to us and is removed from the list].
We have a vector for the initial_edge got from the 'other_vertex' to the vertex we are considering.
We also have vectors for the other three edges from the vertex we are considering to their 'other_vertex'.
The three edges also have faces, we can make a unique list and get their normals and use 'dot' on them to get the 'vertex_normal'.
Using the vertex_normal as the axis and the position of the vertex we are considering we can make a plane, we flatten the four edge's vectors onto the plane and then compare the angles between the initial_edge_vector and the other three, the angle that is the least gives us the 'found_edge' which we will then examine.
We add the initial_edge to our 'collection'.
We now treat that found_edge in the same way as we did the 'initial_edge', and consider its other_vertex [we have already processed the vertex]...
We check as before and if there are four edges we find the next 'found_edge' and add this one to the collection etc etc.
Repeating until there is no new 'found_edge' [remembering that it might be possible to loop back to an edge that was already collected, so then we also stop too - otherwise we'll get an infinite loop].
The collection of edges are all of the edges that connect to the initial_edge selected with four edges at a vertex.
We highlight/process these or there vertices...

thomthom

I've been thinking of projecting the connected edges to a 2d plane and then find their order, either clockwise or counter-clockwise. But isn't there a risk of degenerate cases where this might fail? The projected edges overlaps each other?
And second consideration is whether it's processing intensive...

Blender does Edge Loop another way, somewhat similar to what I already do:

/* selects or deselects edges that;
- if edges has 2 faces;
	- has vertices with valence of 4
	- not shares face with previous edge
- if edge has 1 face;
	- has vertices with valence 4
	- not shares face with previous edge
	- but also only 1 face
- if edge no face;
	- has vertices with valence 2

Still trying to make up my mind to what method I prefer... ...in terms of end result.

TIG

If a vertex has four edges you trap that each edge only has one face [a taken].
If you get the vertex_normal and use a plane through the vertex.position to flatten [project] the vectors onto for the 4 edges being tested, can we ever get a zero length vector ? I think not, because the dot processing will never make a plane that's 'square' to a given vector - as there must always be some of the 4 edges spring off at angles...