Fast way to get loop end edges/verts?

#1

So I’m trying to go through an array of selected edges, on an Edit_Poly modifier, and find the ones which are attached to only 0-1 other selected edges. Unfortunately I’ve found doing this is extremely slow using the method posted below (processing just 3000 edges takes 4-5 seconds on my PC), and was wondering if there was a better method anyone could suggest?

objMod = modpanel.getCurrentObject()
allSelEdgesBIT = objMod.getSelection #Edge
allSelEdges = allSelEdgesBIT as array

gc()
t1 = timeStamp()
endEdges = #()
endVerts = #()
for edj in allSelEdges do (
    edjVrts = #((objMod.GetEdgeVertex edj 1), (objMod.GetEdgeVertex edj 2))
    endVrts = #()
    for vrt in edjVrts do (
        vrtEdjs = for i=1 to (objMod.GetVertexEdgeCount vrt) collect (objMod.GetVertexEdge vrt i)
        selVrtEdjs = ((vrtEdjs as bitarray) * allSelEdgesBIT)
        if selVrtEdjs.numberset == 1 do append endVrts vrt
    )
    if endVrts.count != 0 do ( append endEdges edj ; append endVerts endVrts )
)
format "maxscript\nresult:%\ntime:% ms\n" test (timeStamp() - t1)
--4608 ms for 3000 edges on Edit_Poly
#2

How fast is this:

(
	objMod = modpanel.getCurrentObject()
	allSelEdgesBIT = objMod.getSelection #Edge
	allSelEdges = allSelEdgesBIT as array
	
	gev = objMod.GetEdgeVertex
	gevc = objMod.GetVertexEdgeCount
	gve = objMod.GetVertexEdge

	gc()
	t1 = timeStamp()
	endEdges = #()
	endVerts = #()
	for edj in allSelEdges do 
	(
		edjVrts = #((gev edj 1), (gev edj 2))
		endVrts = #()
		for vrt in edjVrts do 
		(
			gvec = (gevc vrt)
			vrtEdjs = for i=1 to gvec collect (gve vrt i)
			selVrtEdjs = ((vrtEdjs as bitarray) * allSelEdgesBIT)
			if selVrtEdjs.numberset == 1 do append endVrts vrt
		)
		if endVrts.count != 0 do ( append endEdges edj ; append endVerts endVrts )
	)
	format "maxscript\nresult:%\ntime:% ms\n" test (timeStamp() - t1)
)
#3

Whoa! 0_0

I think you just blew my mind there Miauu. I can hardly believe assigning the commands like that gave such a massive performance boost; from 4608ms all the way down to 49ms. That’s just crazy.

Thank you so much, this will definitely be useful not just for this script but for many others in the future as well! :smiley:

#4

Glad to help. :slight_smile:

#5

yes… it’s known trick. it speeds up the method dramatically.

but check your algorithm -

you test all edges vertexes for “end” condition. but if you already know from previous edge that one of verts an “end” or not “end” vert what is the reason to test same verts again for another edge? so, potentially you can make your algorithm about two times faster for general case by changing the logic

#6

here is another point of optimization:

(
	t0 = timestamp()
	h0 = heapfree

	for k=1 to 10000 do
	(
		a = #()
		append a 2
		append a 1000
		a as bitarray
	)

	format "time:% heap:%\n" (timestamp() - t0) (h0 - heapfree)
)
(
	t0 = timestamp()
	h0 = heapfree

	for k=1 to 10000 do
	(
		a = #{}
		append a 2
		append a 1000
	)

	format "time:% heap:%\n" (timestamp() - t0) (h0 - heapfree)
)
(
	t0 = timestamp()
	h0 = heapfree

	for k=1 to 10000 do
	(
		a = #{2, 1000}
	)

	format "time:% heap:%\n" (timestamp() - t0) (h0 - heapfree)
)

it might give you another 1.5-2 times of acceleration

#7

Hey DenisT, I tried a few different methods to optimize the script further based on your advise, and was able to get it down to about 37ms (from 49ms) using this approach:

(
	objMod = modpanel.getCurrentObject()
	allSelEdgesBIT = objMod.getSelection #Edge
    allSelEdges = allSelEdgesBIT as array
    
    gev = modFullName.GetEdgeVertex
    gvec = modFullName.GetVertexEdgeCount
    gve = modFullName.GetVertexEdge
    
    gc()
    t1 = timeStamp()
    allEdjVrts = #{} ; for edj in allSelEdges do ( join allEdjVrts #{(gev edj 1), (gev edj 2)} )
    combinedEnds = #() --Each sub-array looks like this: #(endVertIndex, endEdgeIndex)
    checkedVrts = #()
    for vrt in allEdjVrts do (
        if (finditem checkedVrts vrt == 0) do (
            vrtEdjs = (for i=1 to (gvec vrt) collect (gve vrt i)) as bitarray
            selEdjs = vrtEdjs * allSelEdgesBIT
            if selEdjs.numberSet == 1 do (
                selEdj = (selEdjs as array)[1]
                selEdjVrts = #{(gev selEdj 1), (gev selEdj 2)}
                remainingVrt = ((selEdjVrts - #{vrt}) as array)[1]
                append combinedEnds #(vrt, selEdj)
                append checkedVrts remainingVrt
            )
        )
    )
    format "maxscript\nresult:%\ntime:% ms\n" test (timeStamp() - t1)
)

I don’t think I’ll be able to optimize it any further, but thankfully this is already easily fast enough for the purposes I intend to use it for. Thanks again guys for the help :slight_smile:

#8

make a test setup that we all be able to play under the same settings

#9

ok … i made it:

delete objects
gc()

bx = box widthsegs:32 lengthsegs:32 heightsegs:32 name:#test isselected:on
ep = Edit_Poly()
addmodifier bx ep
max modify mode
modPanel.setCurrentObject ep

nume = ep.GetNumEdges()
numv = ep.GetNumVertices()
seed 0
ee = #{}
for k=1 to (nume/2) do append ee (random 1 nume)  

subobjectlevel = 2
ep.Select #edge ee 
ep.ButtonOp #SelectEdgeLoop
ep.Select #edge ee invert:on

now try any on the methods (find end edges), and give us the time and memory usage numbers :stuck_out_tongue_winking_eye:

#10

Ok, tried it. With 7508 edges selected;

First method: 11555 ms , heap size of -3152L
Second method: 191 ms, heap size of 1147880L
Third method: 103 ms, heap size of 3534192L

Heap size was all over the place during repeat testing, but was always much higher for the faster methods.

#11

try to beat mine :wink:

/*********************** test setup **************************/

delete objects
gc()

with redraw off
(
	global bx = box widthsegs:32 lengthsegs:32 heightsegs:32 name:#test isselected:on
	global ep = Edit_Poly()
	addmodifier bx ep
	max modify mode
	modPanel.setCurrentObject ep

	nume = ep.GetNumEdges()
	numv = ep.GetNumVertices()
	seed 0
	ee = #{}
	for k=1 to (nume/2) do append ee (random 1 nume)  

	subobjectlevel = 2
	ep.Select #edge ee 
	ep.ButtonOp #SelectEdgeLoop
	ep.Select #edge ee invert:on
)

/*********************** function ****************************/

fn getEditPolyEndEdges ep = 
(
	getVertexEdgeCount = ep.GetVertexEdgeCount
	getVertexEdge = ep.GetVertexEdge
	
	ee = ep.getSelection #edge
	ep.convertSelection #edge #vertex
	vv = ep.getSelection #vertex
	
	endverts = #{}
	endedges = #{}

	edge = [0,0]
	for v in vv do
	(
		n = 0
		edge.x = 0 
		for k=1 to getVertexEdgeCount v while n < 2 do
		(
			e = getVertexEdge v k
			if ee[e] do 
			(
				n += 1
				edge.x = e
			)
		)
		if n == 1 do 
		(
			append endverts v 
			append endedges edge.x
		)
	)
	#(endverts, endedges)
)
/*********************** test result *************************/

(
	gc()

	t0 = timestamp()
	h0 = heapfree
	
	ends = getEditPolyEndEdges ep

	format "time:% heap:%\n" (timestamp() - t0) (h0 - heapfree)
	
	subobjectlevel = 1

	vv = ep.getSelection #vertex
	ep.Select #vertex vv invert:on	
	ep.Select #vertex ends[1] select:on	
	
	format "\tverts:(%) % \n\tedges:(%) %\n" ends[1].numberset ends[1] ends[2].numberset ends[2]
)

… and check your results

#12

i updated my function to decrease memory usage

#13

Yea, yours is better. I take my hat off to you and your mastery of maxscript good sir :slight_smile:

#14

50-80% faster :wink:

fn GetEndEdgesAndVerts mdf =
(
	if not iskindof mdf edit_poly do return #(#{},#{})
	
	GetEdgeVert        = mdf.getedgevertex
	GetVertexEdgeCount = mdf.getvertexedgecount
	GetVertexEdge      = mdf.getvertexedge
	
	sel = mdf.getselection #edge
	
	vt1 = #{}
	vt2 = #{}
	edges = #{}
	
	for j in sel do
	(
		v1 = GetEdgeVert j 1
		v2 = GetEdgeVert j 2
		
		vt2[v1] = vt1[v1]
		vt2[v2] = vt1[v2]
		
		vt1[v1] = vt1[v2] = true
	)
	
	verts = vt1-vt2
	
	for j in verts do
	(
		done = false
		for k = 1 to GetVertexEdgeCount j while not done do
		(
			edge = GetVertexEdge j k
			edges[edge] = done = sel[edge]
		)
	)
	
	return #(edges, verts)
)
#15

~20% faster :stuck_out_tongue_winking_eye:

fn findEndEdges ep =
(	
	getEdgeVert = ep.GetEdgeVertex
	getVertexEdge = ep.GetVertexEdge
	
	ee = ep.GetSelection #edge
	
	vx = #{}
	vy = #{}

	for e in ee do
	(
		v = getEdgeVert e 1
		append (if vx[v] then vy else vx) v
		v = getEdgeVert e 2
		append (if vx[v] then vy else vx) v
	)
	verts = vx - vy
	
	edges = #{}
	for v in verts do
	(
		k = x = 1
		while not ee[x = getVertexEdge v k] do k += 1
		append edges x
	)
	
	return #(verts, edges)
)
#16

Mmm, well, fair 5-20% optimization of my algorithm, so I’ll give it a :2nd_place_medal: :yum:

#17

BTW… how might it be useful?
if it can be useful i would add it to my c++ mxs extension (of course the PolyObject version)

#18

I use it at the start of edge loop crawling/sorting functions.
Depending on the tool you’re making you may want to sort/crawl loops in different ways, such as when selected loops intersect each other, but I’ve found this to be a good way to start off in most cases.

There might be other uses, but that’s what I use it for.

#19

algorithmic the fastest method i found is:

fn searchEndEdges2 ep =
(	
	getEdgeVert = ep.GetEdgeVertex
	
	ee = ep.GetSelection #edge
	num = ep.GetNumVertices()
	
	vv = #()
	for e in ee do
	(
		v = getEdgeVert e 1
		vv[v] = if vv[v] == undefined then e else ok		
		v = getEdgeVert e 2
		vv[v] = if vv[v] == undefined then e else ok	
	)
	
	verts = #{}
	edges = #{}
	num = vv.count
	for v=1 to num do if classof (e = vv[v]) == Integer do 
	(
		append verts v
		append edges e
	)
	return #(verts, edges)
)

(we are not talking about memory usage here)

but specifically for built-in MXS implementation there are several slowdowns:

  • there is no way to initialize mxs array with default value
  • mxs array holds values and it needs conversion from sdk int to integer value and back.
  • mxs expression <if <> then <> else <> is slow

but you still see that it’s faster anyway

the c++ sdk implementation gives me about 2.5 time difference for both algorithms

#20

This version is slower on my end than the previous optimization.

Although if<>then may be generally slower, in this case I found that it is basically the same in this case.

What makes some difference here is the use of append() instead of accessing the array twice or overwriting unnecessary values.

So, the use of append() is generally faster as we have probed a few years ago.