[Closed] Fast way to get loop end edges/verts?

try to beat mine

/******************** 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

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

50-80% faster

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)
)

~20% faster

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)
)

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

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)

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.

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

there is the better one (!) taking into account the mxs specifics:

fn searchEndEdges3 ep =
(	
	getEdgeVert = ep.GetEdgeVertex
	
	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 = #{}
	ep.getedgesusingvert edges verts
	return #(verts, edges * ee)
)

generally it’s two times faster

Jorge, i suggest to split the first place as usually

Yes, you got it. Don’t even need to test it.
This was a smart move:

ep.getedgesusingvert edges verts