PDA

View Full Version : Getting sorted verts from edges


Rorschach
06-06-2008, 12:03 AM
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
06-06-2008, 11: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
06-07-2008, 08: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
06-09-2008, 11: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
06-09-2008, 11: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
06-10-2008, 01: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
06-10-2008, 01:47 PM
Great, thanks a lot, will try this later

CGTalk Moderation
06-10-2008, 01: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.