View Full Version : Getting sorted verts from edges
Rorschach 06052008, 11:03 PM Here's my problem, I need to get the sequence of verts from a selection of edges. The edges are always comntinuous (they share a vert, but unlike a true edgeloop they can go round corners). Using polyop.getvertsfromedges returns all the verts but in a bit array, so the seqeunce is lost.
So in my attahced pic I'd want to get
#(5,4,3,2,1,6,11,16,21,22,17,18,19,23,24) ... or the reverse of that, it's not important.
I've seen this asked before, but the soltions posted don't seem to work for me, not on all models, not on the picture posted.
I've been tryin to just check each edges loops and see if they share a vert and ordering like this, but I keep getting stuck. Feels like a simple problem but it seems to snowball quite quickly and I cant figure it out.
Help!


Rorschach
06062008, 10:43 AM
I've got the rule, if you check each edge in this edge selection you get a list of 2 verts.
Each of these vert pairs always shares at least one vert with enother edge, it's neighbour.
So I need an algorytm that sorts the verts based on this rule, but i'm really struggling...
thanks
SyncViewS
06072008, 07:39 AM
Hi Rorschach,
I came up with a two step algorithm to get the sorted list of vertices in a continuous edge chain:
1 Get the extreme vertices
2 Start from an extreme vertex and walk the whole edge chain collecting vertices
It's not the most optimized procedure. It runs along the edge chain twice, so it slows down with the increasing of the edge chain length, but at least it works.
 Pass to the function the "editable poly object" and the "edge selection"
function getChainVerts oEditPoly baEdgeSelection =
(
 Init Edge Selection
local baChainEdges = baEdgeSelection
local iNumChainEdges = baEdgeSelection.numberSet
 Init Vert Selection
local baChainVerts = (polyop.getVertsUsingEdge oEditPoly baEdgeSelection)
local baInnerVerts = copy baChainVerts
 Get chain extreme vertices
/*
The for loop runs through all selected edges, gets their vertices,
then inverts their bit value in the baInnerVerts bitArray. Each vertex
is inverted two times [true > false > true], with the exception
of the extremes, which are inverted only once [true > false],
taking them away from the bitArray.
Obtain extreme vertices by subtracting baInnerVerts from all
baChainVerts bitArray.
*/
for iEdge in baChainEdges do
(
local baEdgeVerts = (polyop.getVertsUsingEdge oEditPoly iEdge)
for iVert in baEdgeVerts do
(
baInnerVerts[iVert] = not baInnerVerts[iVert]
)
)
local baExtremeVerts = (baChainVerts  baInnerVerts)
 Choose the extreme vertex to start from to collect vertices.
/*
This determines the direction of the vertices chain collection, but
since it comes from a bitArray, it's quite random.
*/
local iExtremeStartVert = (baExtremeVerts as Array)[1]  or [2]
 Init array for vertices collection
local aiSortedVerts = #(iExtremeStartVert)
 Init current vertex index
local iCurrentVert = iExtremeStartVert
 Init bitArray of processed edges to avoid walking back in the chain
local baCrossedEdges = #{}
 Collect Vertices
for i = 1 to iNumChainEdges do
(
 do one step
local baEdgesFromVert = (polyop.getEdgesUsingVert oEditPoly iCurrentVert)
local baStepEdge = ((baEdgesFromVert * baChainEdges)  baCrossedEdges)
baCrossedEdges += baStepEdge
 collect the vertex
local iCurrentVert = (((polyop.getVertsUsingEdge oEditPoly baStepEdge)  (aiSortedVerts as BitArray)) as Array)[1]
aiSortedVerts[i+1] = iCurrentVert
)
 Return sorted vertices chain array
return aiSortedVerts
)
format "Sorted Vertices Chain > %\n" (getChainVerts $ (polyop.getEdgeSelection $))
gc light:true
There's not error catching in this code. Selected edges must be a single continuous chain.
I hope this is what you were looking for, or a good starting point.
 Cheers
Rorschach
06092008, 10:23 AM
Hey SyncViewS,
Thanks for the script, but I can't get it to work:
getChainVerts()
 Error occurred in i loop; filename: ; position: 1778
 Frame:
 baStepEdge: undefined
 i: 1
 baEdgesFromVert: undefined
 called in getChainVerts(); filename: ; position: 2073
 Frame:
 aiSortedVerts: #(undefined)
 baInnerVerts: #{1..9, 11, 14..16, 19..29}
 baChainVerts: #{1..9, 11, 14..16, 19..29}
 oEditPoly: $Plane01
 iNumChainEdges: 24
 baExtremeVerts: #{}
 baCrossedEdges: #{}
 iExtremeStartVert: undefined
 baEdgeSelection: #{1..2, 4, 6..9, 12..13, 20..21, 27..29, 31, 33, 35, 37, 39..44}
 baChainEdges: #{1..2, 4, 6..9, 12..13, 20..21, 27..29, 31, 33, 35, 37, 39..44}
 iCurrentVert: undefined
 called in anonymous codeblock
 Frame:
 Runtime error: Cannot convert value to bitArray: undefined
58239596L
Rorschach
06092008, 10:30 AM
My bad, I was running it on a closed loop, which is doesn't seem to like (but which I will need to do sometimes...
)
SyncViewS
06102008, 12:16 PM
Hi Rorschach,
I revised the code to accept closed edge loops. In that case, the sorted vertex list starts from the one with the lowest index, that's quite random in a standard selection. There's a little error catching preventing to accept non linear chains. All the code should be optimized for intensive use, like removing the "exit" in the for loop and avoiding to rewrite almost the full code for open and closed chains.
 Pass to the function the "editable poly object" and the "edge selection"
function getChainVerts oEditPoly baEdgeSelection =
(
 Init Edge Selection
local baChainEdges = baEdgeSelection
local iNumChainEdges = baEdgeSelection.numberSet
 Init Vert Selection
local baChainVerts = (polyop.getVertsUsingEdge oEditPoly baEdgeSelection)
local baInnerVerts = copy baChainVerts
 Sort out if it is a closed edge loop
if (iNumChainEdges != baChainVerts.numberSet) then
(
 Get chain extreme vertices
/*
The for loop runs through all selected edges, gets their vertices,
then inverts their bit value in the baInnerVerts bitArray. Each vertex
is inverted two times [true > false > true], with the exception
of the extremes, which are inverted only once [true > false],
taking them away from the bitArray.
Obtain extreme vertices by subtracting baInnerVerts from all
baChainVerts bitArray.
*/
for iEdge in baChainEdges do
(
local baEdgeVerts = (polyop.getVertsUsingEdge oEditPoly iEdge)
for iVert in baEdgeVerts do
(
baInnerVerts[iVert] = not baInnerVerts[iVert]
)
)
local baExtremeVerts = (baChainVerts  baInnerVerts)
 Choose the extreme vertex to start from to collect vertices.
/*
This determines the direction of the vertices chain collection, but
since it comes from a bitArray, it's quite random.
*/
local iExtremeStartVert = (baExtremeVerts as Array)[1]  or [2]
 Init array for vertices collection
local aiSortedVerts = #(iExtremeStartVert)
 Init current vertex index
local iCurrentVert = iExtremeStartVert
 Init bitArray of processed edges to avoid walking back in the chain
local baCrossedEdges = #{}
 Collect Vertices
for i = 1 to iNumChainEdges do
(
 do one step
local baEdgesFromVert = (polyop.getEdgesUsingVert oEditPoly iCurrentVert)
local baStepEdge = ((baEdgesFromVert * baChainEdges)  baCrossedEdges)
 non linear chain error catching
if (baStepEdge.numberSet == 1) then
(
baCrossedEdges += baStepEdge
 collect the vertex
local iCurrentVert = (((polyop.getVertsUsingEdge oEditPoly baStepEdge)  (aiSortedVerts as BitArray)) as Array)[1]
aiSortedVerts[i+1] = iCurrentVert
)
else
(
aiSortedVerts = #()
messageBox "Edge Selection is not a linear chain"
exit
)
)
)
else
(
 Choose a vertex to start the collection
local iStartVert = (baChainVerts as Array)[1]
 Init array for vertices collection
local aiSortedVerts = #(iStartVert)
 Init current vertex index
local iCurrentVert = iStartVert
 Init bitArray of processed edges to avoid walking back in the chain
local iStartEdge = (((polyop.getEdgesUsingVert oEditPoly iCurrentVert) * baChainEdges) as Array)[1]
local baCrossedEdges = #{iStartEdge}
 Collect Vertices
for i = 1 to (iNumChainEdges  1) do
(
 do one step
local baEdgesFromVert = (polyop.getEdgesUsingVert oEditPoly iCurrentVert)
local baStepEdge = ((baEdgesFromVert * baChainEdges)  baCrossedEdges)
 non linear chain error catching
if (baStepEdge.numberSet == 1) then
(
baCrossedEdges += baStepEdge
 collect the vertex
local iCurrentVert = (((polyop.getVertsUsingEdge oEditPoly baStepEdge)  (aiSortedVerts as BitArray)) as Array)[1]
aiSortedVerts[i+1] = iCurrentVert
)
else
(
aiSortedVerts = #()
messageBox "Edge Selection is not a linear chain"
exit
)
)
)
 Return sorted chain vertices array
return aiSortedVerts
)
format "Sorted Vertices Chain > %\n" (getChainVerts $ (polyop.getEdgeSelection $))
gc light:true
 Cheers
Rorschach
06102008, 12:47 PM
Great, thanks a lot, will try this later
CGTalk Moderation
06102008, 12:47 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.
vBulletin v3.0.5, Copyright ©20002014, Jelsoft Enterprises Ltd.