Collect continuous selected edges/vertices in order?

[Malkalypse]

Trying to write a function to break the selected vertices or edges of an object into contiguous groups, such as multiple loops, while keeping them in order (i.e. according to how they connect on the object.)

I’ve found or been able to come up with scripts that do one or the other; in other words either
a) Get a single group of contiguous verts or edges in order, or
b) Collect multiple groups of contiguous verts or edges, but in numerical order rather than the order in which they connect on the model

But I can’t seem to find or figure out a function that satisfies both.

[denisT]

i don’t want to disappoint you but there is no safe way in mxs (and sdk) to get vertex selection (or poly loop/ring) order.
depending on what you want to do it can be a workaround. let’s say if you want to copy some vertex data from one set of verts to another (weights, uvs, etc.) they can be sorted in a specific order…
the idea is to find the right sorting method for the desirable mapping

[Malkalypse]

When I say “in order” I meant in terms of how they are arranged contiguously on the model, as shown in this post:

http://forums.cgsociety.org/showthread.php?f=98&t=639599

(or in this one: http://forums.cgsociety.org/showthread.php?f=98&t=481192 )

I just need something that will do this for multiple groups of selected edges/vertices, creating a separate array for each group…

[MatanH]

Maybe this could help:

(
	fn getContinuousEdgeGroups obj =
	(
		local edgesMask = polyop.getEdgeSelection obj
		local selectedEdges = edgesMask as array
		local continuousEdgeGroups = #()
		
		for i in selectedEdges where edgesMask[i] do 
		(
			local newGroup = #{}
			local frontier = #(i)
			
			while frontier.count > 0 do 
			(
				local current = frontier[1]
				deleteItem frontier 1
				edgesMask[current] = off
				newGroup[current] = on
				
				local verts = polyop.getVertsUsingEdge obj current
				local neighbors = polyop.getEdgesUsingVert obj verts
				neighbors *= edgesMask
				neighbors = neighbors as array
				for j in neighbors do
					appendIfUnique frontier j
			)
			
			append continuousEdgeGroups newGroup
		)
		
		continuousEdgeGroups
	)
	
	fn getOrderedEdgeGroups obj continuousEdgeGroups =
	(
		local orderedEdgeGroups = #()
		for edgeGroupMas in continuousEdgeGroups do
		(
			local ends = #()
			local edgeGroup = edgeGroupMas as array
			for i in edgeGroup as array do (
				local verts = polyop.getVertsUsingEdge obj i
				local neighbors = polyop.getEdgesUsingVert obj verts
				neighbors[i] = off
				neighbors *= edgeGroupMas
				if neighbors.numberSet < 2 then
					append ends i
			)
			
			local root
			if ends.count > 0 then (
				-- there is a starting point
				sort ends
				root = ends[1]
			) else (
				-- there is no starting point => this is a loop
				sort edgeGroup
				root = edgeGroup[1]
			)
			
			local newGroup = #()
			local frontier = #(root)
			local usedEdges = #{}
			
			while frontier.count > 0 do (
				local current = frontier[1]
				deleteItem frontier 1
				append newGroup current
				usedEdges[current] = on
				
				local verts = polyop.getVertsUsingEdge obj current
				local neighbors = polyop.getEdgesUsingVert obj verts
				neighbors *= edgeGroupMas
				neighbors -= usedEdges
				neighbors = neighbors as array
				sort neighbors
				join frontier neighbors
			)
			
			append orderedEdgeGroups newGroup
		)
		
		orderedEdgeGroups
	)
	
	if selection.count == 1 and classof $ == Editable_Poly then (
		local obj = $
		local continuousEdgeGroups = getContinuousEdgeGroups obj
		getOrderedEdgeGroups obj continuousEdgeGroups
	)
)

[Malkalypse]

It works about as well as anything I’ve come up with and is also a lot shorter. However, when dealing with closed loops it no longer keeps the edges in order (and also collects the last edge in sequence twice). E.g., what should be #(1,2,3,4) comes up as #(1, 2, 4, 3, 3).

[MatanH]

Malkalypse you are right, I didn’t test my code on loops but I did have a special case for it that I should have tested. Here is a fixed version with an extra visualisation / debugging function:

(
	fn getEdgeNeighbors obj i edgesMask:#{} =
	(
		local verts = polyop.getVertsUsingEdge obj i
		local neighbors = polyop.getEdgesUsingVert obj verts
		neighbors[i] = off
		neighbors * edgesMask
	)
	
	fn getContinuousEdgeGroups obj =
	(
		local edgesMask = polyop.getEdgeSelection obj
		local selectedEdges = edgesMask as array
		local continuousEdgeGroups = #()
		
		for i in selectedEdges where edgesMask[i] do 
		(
			local newGroup = #{}
			local frontier = #(i)
			
			while frontier.count > 0 do 
			(
				local current = frontier[1]
				deleteItem frontier 1
				edgesMask[current] = off
				newGroup[current] = on
				
				local neighbors = (getEdgeNeighbors obj current edgesMask:edgesMask) as array
				for j in neighbors do
					appendIfUnique frontier j
			)
			
			append continuousEdgeGroups newGroup
		)
		
		continuousEdgeGroups
	)
	
	fn getOrderedEdgeGroups obj continuousEdgeGroups =
	(
		local orderedEdgeGroups = #()
		for edgeGroupMas in continuousEdgeGroups do
		(
			local ends = #()
			local edgeGroup = edgeGroupMas as array
			for i in edgeGroup as array do (
				local neighbors = getEdgeNeighbors obj i edgesMask:edgeGroupMas
				if neighbors.numberSet < 2 then
					append ends i
			)
			
			local root
			local extraEdge
			if ends.count > 0 then (
				-- there is a starting point
				sort ends
				root = ends[1]
			) else (
				-- there is no starting point => this is a loop
				sort edgeGroup
				root = edgeGroup[1]
				local neighbors = (getEdgeNeighbors obj root edgesMask:edgeGroupMas) as array
				extraEdge = neighbors[1]
				edgeGroupMas[extraEdge] = off
			)
			
			local newGroup = #()
			local frontier = #(root)
			local usedEdges = #{}
			
			while frontier.count > 0 do (
				local current = frontier[1]
				deleteItem frontier 1
				append newGroup current
				usedEdges[current] = on
				
				local neighbors = getEdgeNeighbors obj current edgesMask:edgeGroupMas
				neighbors -= usedEdges
				neighbors = neighbors as array
				sort neighbors
				join frontier neighbors
			)
			
			if extraEdge != undefined then
				append newGroup extraEdge
			
			append orderedEdgeGroups newGroup
		)
		
		orderedEdgeGroups
	)
	
	fn visualizeGroup obj edgeGroup radius:0.1 =
	(
		for i = 1 to edgeGroup.count do (
			local verts = (polyop.getVertsUsingEdge obj edgeGroup[i]) as array
			local faces = (polyop.getFacesUsingEdge obj edgeGroup[i]) as array
			local v1 = polyop.getVert obj verts[1]
			local v2 = polyop.getVert obj verts[2]
			local x = normalize (v2 - v1)
			local y = [0,0,0]
			for j in faces do
				y += polyop.getFaceNormal obj j
			local z = normalize (cross x y)
			y = normalize (cross z x)
			local m = matrix3 x y z ((v1 + v2) / 2)
			local c = cylinder radius:radius wirecolor:red height:(distance v1 v2) pos:v1 dir:x
			Text text:(i as string) wirecolor:red size:(100. * radius) transform:m
		)
	)
	
	local debugMode = true
	if selection.count == 1 and classof $ == Editable_Poly then (
		local obj = $
		local continuousEdgeGroups = getContinuousEdgeGroups obj
		local orderedEdgeGroups = getOrderedEdgeGroups obj continuousEdgeGroups
		if debugMode == true then
			for g in orderedEdgeGroups do
				visualizeGroup obj g
	)
)

There are still unhanded cases, like if you have multiple loops in a single group, for these complex cases I think it’s better to build a directed graph and brake it to form a tree data structure and sort the edges this way, if I’ll have some more spare time tomorrow I can give it a go if you’re interested…

[Malkalypse]

Sure, if you don’t mind! One can never have too many tools, after all

EDIT:
Forgot to mention – that debugging option is really trippy looking!

[denisT]

if we are talking about poly edge loops, it’s much easier to use <EditablePoly>.setLoopShift

edtable poly has already sorted loop structures. so all that you need is

pick any edge from a loop

shift any direction until meet any not from loop or meet the start pick (closed loop)

if you didn’t meet a start pick do shift another direction

merge two sides and get sorted loop edges

[MatanH]

Here is the (probably no completely) correct method:

(
	fn getEdgeNeighbors obj i edgesMask:#{} vertMask:#{} =
	(
		local verts = polyop.getVertsUsingEdge obj i
		verts -= vertMask
		local neighbors = polyop.getEdgesUsingVert obj verts
		neighbors[i] = off
		neighbors * edgesMask
	)
	
	struct s_TreeNode
	(
		index,
		Children = #(),
		
		fn getChildren obj &edgesMask:#{} &vertsMask:#{} =
		(
			edgesMask[index] = off
			local neighbors = getEdgeNeighbors obj index edgesMask:edgesMask vertMask:vertsMask
			local NeighborTreeNodes = for i in neighbors collect s_TreeNode index:i
			
			for i in polyop.getVertsUsingEdge obj index do
				vertsMask[i] = on
			
			for i in neighbors where edgesMask[i] do
			(
				local Child = s_TreeNode index:i
				Child.getChildren obj edgesMask:&edgesMask vertsMask:&vertsMask
				append Children Child
			)
		),
		
		fn getGroup =
		(
			local edgeGroup = #(index)
			for Child in Children do
				join edgeGroup (Child.getGroup())
			edgeGroup
		)
	)
	
	fn getContinuousEdgeGroups obj =
	(
		local edgesMask = polyop.getEdgeSelection obj
		local selectedEdges = edgesMask as array
		local continuousEdgeGroups = #()
		
		for i in selectedEdges where edgesMask[i] do 
		(
			local newGroup = #{}
			local frontier = #(i)
			
			while frontier.count > 0 do 
			(
				local current = frontier[1]
				deleteItem frontier 1
				edgesMask[current] = off
				newGroup[current] = on
				
				local neighbors = (getEdgeNeighbors obj current edgesMask:edgesMask) as array
				for j in neighbors do
					appendIfUnique frontier j
			)
			
			append continuousEdgeGroups newGroup
		)
		
		continuousEdgeGroups
	)
	
	fn getOrderedEdgeGroups obj continuousEdgeGroups =
	(
		local orderedEdgeGroups = #()
		for edgeGroupMas in continuousEdgeGroups do
		(
			local ends = #()
			local edgeGroup = edgeGroupMas as array
			for i in edgeGroup do 
			(
				local isEndEdge = false
				local verts = polyop.getVertsUsingEdge obj i
				for j in verts do
				(
					local neighbors = polyop.getEdgesUsingVert obj j
					neighbors *= edgeGroupMas
					if neighbors.numberSet == 1 then
						exit with isEndEdge = true
				)
				
				if isEndEdge then
					append ends i
			)
			
			local Root = s_TreeNode index:(if ends.count > 0 then ends[1] else edgeGroup[1])
			Root.getChildren obj edgesMask:edgeGroupMas
			append orderedEdgeGroups (Root.getGroup())
		)
		
		orderedEdgeGroups
	)
	
	fn visualizeGroup obj edgeGroup radius:0.1 =
	(
		for i = 1 to edgeGroup.count do 
		(
			local verts = (polyop.getVertsUsingEdge obj edgeGroup[i]) as array
			local faces = (polyop.getFacesUsingEdge obj edgeGroup[i]) as array
			local v1 = polyop.getVert obj verts[1]
			local v2 = polyop.getVert obj verts[2]
			local x = normalize (v2 - v1)
			local y = [0,0,0]
			for j in faces do
				y += polyop.getFaceNormal obj j
			local z = normalize (cross x y)
			y = normalize (cross z x)
			local m = matrix3 x y z ((v1 + v2) / 2)
			local c = cylinder radius:radius wirecolor:red height:(distance v1 v2) pos:v1 dir:x
			Text text:(i as string) wirecolor:red size:((distance v1 v2) / 2) transform:m
		)
	)
	
	local debugMode = true
	if selection.count == 1 and classof $ == Editable_Poly then 
	(
		local obj = $
		local continuousEdgeGroups = getContinuousEdgeGroups obj
		local orderedEdgeGroups = getOrderedEdgeGroups obj continuousEdgeGroups
		if debugMode == true then
			for g in orderedEdgeGroups do
				visualizeGroup obj g
	)
)

If the debugging option doesn’t work very well it’s probably because it’s scale dependent, I didn’t bother making it scale independent :shrug:

EDIT: Already fixed a few issues

[Malkalypse]

After some poking and prodding, I think I get how it works now. One question though, what would need changing in order to collect the vertices in order instead of the edges?

[MatanH]

After some poking and prodding, I think I get how it works now. One question though, what would need changing in order to collect the vertices in order instead of the edges?

this is pretty easy to do, we can simply convert every edge in the ordered edge group to verts and add them to the vert group if they are not in it yet like this function does:

fn convertEdgesToVerts obj edgeGroup =
(
	local vertsGroup = #()
	for i in edgeGroup do (
		local verts = (polyop.getVertsUsingEdge obj i) as array
		for j in verts do
			appendIfUnique vertsGroup j
	)
	vertsGroup
)

and the complete example with debugging for both the edges and verts is here:

(
	fn getEdgeNeighbors obj i edgesMask:#{} vertMask:#{} =
	(
		local verts = polyop.getVertsUsingEdge obj i
		verts -= vertMask
		local neighbors = polyop.getEdgesUsingVert obj verts
		neighbors[i] = off
		neighbors * edgesMask
	)
	
	struct s_TreeNode
	(
		index,
		Children = #(),
		
		fn getChildren obj &edgesMask:#{} &vertsMask:#{} =
		(
			edgesMask[index] = off
			local neighbors = getEdgeNeighbors obj index edgesMask:edgesMask vertMask:vertsMask
			local NeighborTreeNodes = for i in neighbors collect s_TreeNode index:i
			
			for i in polyop.getVertsUsingEdge obj index do
				vertsMask[i] = on
			
			for i in neighbors where edgesMask[i] do
			(
				local Child = s_TreeNode index:i
				Child.getChildren obj edgesMask:&edgesMask vertsMask:&vertsMask
				append Children Child
			)
		),
		
		fn getGroup =
		(
			local edgeGroup = #(index)
			for Child in Children do
				join edgeGroup (Child.getGroup())
			edgeGroup
		)
	)
	
	fn getContinuousEdgeGroups obj =
	(
		local edgesMask = polyop.getEdgeSelection obj
		local selectedEdges = edgesMask as array
		local continuousEdgeGroups = #()
		
		for i in selectedEdges where edgesMask[i] do 
		(
			local newGroup = #{}
			local frontier = #(i)
			
			while frontier.count > 0 do 
			(
				local current = frontier[1]
				deleteItem frontier 1
				edgesMask[current] = off
				newGroup[current] = on
				
				local neighbors = (getEdgeNeighbors obj current edgesMask:edgesMask) as array
				for j in neighbors do
					appendIfUnique frontier j
			)
			
			append continuousEdgeGroups newGroup
		)
		
		continuousEdgeGroups
	)
	
	fn getOrderedEdgeGroups obj continuousEdgeGroups =
	(
		local orderedEdgeGroups = #()
		for edgeGroupMas in continuousEdgeGroups do
		(
			local ends = #()
			local edgeGroup = edgeGroupMas as array
			for i in edgeGroup do 
			(
				local isEndEdge = false
				local verts = polyop.getVertsUsingEdge obj i
				for j in verts do
				(
					local neighbors = polyop.getEdgesUsingVert obj j
					neighbors *= edgeGroupMas
					if neighbors.numberSet == 1 then
						exit with isEndEdge = true
				)
				
				if isEndEdge then
					append ends i
			)
			
			local Root = s_TreeNode index:(if ends.count > 0 then ends[1] else edgeGroup[1])
			Root.getChildren obj edgesMask:edgeGroupMas
			append orderedEdgeGroups (Root.getGroup())
		)
		
		orderedEdgeGroups
	)
	
	fn convertEdgesToVerts obj edgeGroup =
	(
		local vertsGroup = #()
		for i in edgeGroup do (
			local verts = (polyop.getVertsUsingEdge obj i) as array
			for j in verts do
				appendIfUnique vertsGroup j
		)
		vertsGroup
	)
	
	fn visualizeEdgeGroup obj edgeGroup radius:0.1 =
	(
		for i = 1 to edgeGroup.count do 
		(
			local verts = (polyop.getVertsUsingEdge obj edgeGroup[i]) as array
			local faces = (polyop.getFacesUsingEdge obj edgeGroup[i]) as array
			local v1 = polyop.getVert obj verts[1]
			local v2 = polyop.getVert obj verts[2]
			local x = normalize (v2 - v1)
			local y = [0,0,0]
			for j in faces do
				y += polyop.getFaceNormal obj j
			local z = normalize (cross x y)
			y = normalize (cross z x)
			local m = matrix3 x y z ((v1 + v2) / 2)
			local c = cylinder radius:radius wirecolor:red height:(distance v1 v2) pos:v1 dir:x
			Text text:(i as string) wirecolor:red size:((distance v1 v2) / 2) transform:m
		)
	)
	
	fn visualizeVertGroup obj vertGroup radius:0.2 =
	(
		for i = 1 to vertGroup.count do 
		(
			local faces = (polyop.getFacesUsingVert obj vertGroup[i]) as array
			local v = polyop.getVert obj vertGroup[i]
			local n = [0,0,0]
			for j in faces do
				n += polyop.getFaceNormal obj j
			n = normalize n
			local s = sphere radius:radius wirecolor:blue pos:v dir:n
			local t = Text text:(i as string) wirecolor:blue size:(radius * 50.) pos:v dir:n
			t.transform = PreRotateX t.transform 90
		)
	)
	
	local debugMode = true
	if selection.count == 1 and classof $ == Editable_Poly then 
	(
		local obj = $
		local continuousEdgeGroups = getContinuousEdgeGroups obj
		local orderedEdgeGroups = getOrderedEdgeGroups obj continuousEdgeGroups
		if debugMode == true then
			for g in orderedEdgeGroups do
				visualizeEdgeGroup obj g
		local orderedVertGroups = for g in orderedEdgeGroups collect convertEdgesToVerts obj g
		if debugMode == true then
			for g in orderedVertGroups do
				visualizeVertGroup obj g
	)
)

[Malkalypse]

Thank you, that seems to be exactly what I needed, and was actually much simpler than my own initial attempt!

[Malkalypse]

Hm… actually there seems to be a small issue with the convertEdgesToVerts function. Rather than trying to explain it, let me just use an image:

[MatanH]

Hm… actually there seems to be a small issue with the convertEdgesToVerts function. Rather than trying to explain it, let me just use an image:

Here is a (clumsy) way of solving this problem, just replace this function:

fn convertEdgesToVerts obj edgeGroup =
(
	local vertsGroup = #()
	for i = 1 to edgeGroup.count do 
	(
		local verts = (polyop.getVertsUsingEdge obj edgeGroup[i]) as array
		
		if i == 1 and edgeGroup.count > 1 then 
		(
			local nextVerts = (polyop.getVertsUsingEdge obj edgeGroup[i + 1]) as array
			if findItem nextVerts verts[1] > 0 then
				swap verts[1] verts[2]
		)
		
		for j in verts do
			appendIfUnique vertsGroup j
	)
	vertsGroup
)

[Malkalypse]

Thanks again!

[PolyTools3D]

If you have closed edges loops only, then the following algorithm may also work. It returns an array of both edges and vertices groups.

fn GetSortedEdgesVertsFromClosedLoops node =
    (
    	edges = polyop.getedgeselection node
    	
    	vertsGroups = #()
    	edgesGroups = #()
    	
    	while not edges.isempty and not keyboard.escPressed do
    	(
    		vGroup = #()
    		eGroup = #()
    
    		currentEdge = (edges as array)[1]
    		currentVert = ((polyop.getvertsusingedge node currentEdge) as array)[1]
    		
    		while currentEdge != undefined do
    		(
    			edges[currentEdge] = false
    			
    			append vGroup currentVert
    			append eGroup currentEdge
    			
    			nextVert = polyop.getvertsusingedge node currentEdge
    			nextVert[currentVert] = false
    
    			currentVert = (nextVert as array)[1]
    			currentEdge = (((polyop.getedgesusingvert node currentVert)*edges) as array)[1]
    		)
    		
    		append vertsGroups vGroup
    		append edgesGroups eGroup
    	)
    	return #(edgesGroups, vertsGroups)
    )