Mini-challenge. Get ordered poly edge loops


#20

For the cases I could test it works great and the speed is as you said on my end (39ms for the torus test).
I wonder if it could be modified to work with opened loops as well. For example, from the torus test remove one edge in each loop.


#21

I’m just with it. Not easy. And performance will go down. :frowning:


#22

@Denis,

Did you find the algorithm I proposed useful? Do you have any other example it should handle?

I got it to solve many complex situations, and it does way better than the algorithm in Max used to create splines. But as you have no make any additional comment, I don’t know if this is what you where after. It does certainly solve the situation you posted.

As far as the performance, even as it is, I find it very good. Not to mention if it is optimized.


#23

I’ve stuck with the algorithm used for poly splines. Only changed using of BitArrays to CUSTOM FLAG, added passing of hidden edges, and added reversing loops which are going reversed to an ‘average’ loop direction…

Also I store a Point4 values instead of vertex index, where Point4 is vert’s position and it’s index.

I works for me well…

There are several my definitions in code but the code itself is:


def_visible_primitive(getPolyEdgeVertLoops, "getPolyEdgeVertLoops");
Value* getPolyEdgeVertLoops_cf(Value** arg_list, int count)
{
	check_arg_count_with_keys(getPolyEdgeVertLoops, 1, count);

	BOOL exact = default_exact_key(TRUE);
	BOOL convert = default_delete_key(FALSE);
	BOOL local = default_local_key(FALSE);
	BOOL hidden = default_BOOL_key(hidden, FALSE);

	BOOL canDelete = FALSE;
	TimeValue t = default_time_key(time);
	PolyObject* poly = getObjectPolyObject(arg_list[0], t, canDelete, exact, convert);

	if (poly)
	{
		MNMesh* mesh = &(poly->GetMesh());

		Matrix3* tm = AsMatrix3(arg_list[0], FALSE, FALSE, &t);
		if (Matrix3* m = AsMatrix3(key_arg(transform)))
		{
			if (tm) *tm = *tm * *m;
			else tm = m;
		}

		local_array(loops);
		vl.loops = new_array(0);

		BitArray oldsel;
		mesh->getEdgeSel(oldsel);
		BitArray* edges = GetSelectionBitArray(key_arg(edge), mesh->nume, oldsel, n_selection);
		if (edges && edges->AnyBitSet()) 
		{
			mesh->ClearVFlags(MN_VERT_DONE);
			for (int i=0; i < mesh->nume; i++) 
			{
				if ((*edges)[i] && (hidden || !mesh->e[i].GetFlag(MN_HIDDEN))) mesh->e[i].SetFlag(MN_LOCAL_SEL); 
				else mesh->e[i].ClearFlag(MN_LOCAL_SEL);
			}

			BitArray done;
			done.SetSize (mesh->nume);

			for (int i=0; i<mesh->nume; i++) 
			{
				if (done[i]) continue;
				if (mesh->e[i].GetFlag(MN_DEAD)) continue;
				if (!mesh->e[i].GetFlag(MN_LOCAL_SEL)) continue;

				// The array of points for the spline
				Point4Tab pts;

				// Add the first two points.
				int start = mesh->e[i].v1;
				pts.Append(1, &Point4(mesh->v[start].p, start + 1.0f), 10);
				int nextv = mesh->e[i].v2;
				pts.Append(1, &Point4(mesh->v[nextv].p, nextv + 1.0f), 10);
				
				// Mark this edge as done
				done.Set(i);

				// Trace along selected edges
				// Use loopcount/maxLoop just to avoid a while(1) loop.
				int loopCount, maxLoop=mesh->nume;
				for (loopCount = 0; loopCount < maxLoop; loopCount++) 
				{
					IntTab& ve = mesh->vedg[nextv];
					int j;
					
					for (j=0; j < ve.Count(); j++) 
					{
						if (done[ve[j]]) continue;
						if (mesh->e[ve[j]].GetFlag(MN_LOCAL_SEL)) break;
					}
					if (j == ve.Count()) break;

					if (mesh->e[ve[j]].v1 == nextv) nextv = mesh->e[ve[j]].v2;
					else nextv = mesh->e[ve[j]].v1;

					// Mark this edge as done
					done.Set(ve[j]);

					// Add this vertex to the list
					pts.Append(1, &Point4(mesh->v[nextv].p, nextv + 1.0f), 10);
				}
				int lastv = nextv;

				// Now trace backwards
				nextv = start;
				for (loopCount=0; loopCount<maxLoop; loopCount++) 
				{
					IntTab& ve = mesh->vedg[nextv];
					int j;

					for (j=0; j < ve.Count(); j++) 
					{
						if (done[ve[j]]) continue;
						if (mesh->e[ve[j]].GetFlag(MN_LOCAL_SEL)) break;
					}
					if (j == ve.Count()) break;
					if (mesh->e[ve[j]].v1 == nextv) nextv = mesh->e[ve[j]].v2;
					else nextv = mesh->e[ve[j]].v1;

					// Mark this edge as done
					done.Set(ve[j]);

					// Add this vertex to the list
					pts.Insert(0, 1, &Point4(mesh->v[nextv].p, nextv + 1.0f));
				}
				int firstv = nextv;

				if (!local && tm) for (int k = 0; k < pts.Count(); k++) pts[k] = Point4(tm->PointTransform(Point3(pts[k])), pts[k].w); 
				vl.loops->append(new Point4TabValue(pts));
			}
			if default_BOOL_key(align, TRUE)
			{
				Point3 normal = Point3::Origin;
				for (int k=0; k < vl.loops->size; k++)
				{
					Point4Tab tab = ((Point4TabValue*)vl.loops->data[k])->tab;
					normal += Point3(tab[1] - tab[0]);
				}
				for (int k=0; k < vl.loops->size; k++)
				{
					Point4TabValue* loop = (Point4TabValue*)vl.loops->data[k];
					if (DotProd(normal, Point3(loop->tab[1] - loop->tab[0])) < 0) loop->Reverse();
				}
			}
		}
		if (canDelete) poly->DeleteThis();
		return_value(vl.loops);
	}
	return &undefined;
}    

it takes almost 0 time for last (torus) example.

It doesn’t work well for loop crossings but as I said works good enough for me.


#24

https://www.youtube.com/watch?v=vTZfy9nLrZw
https://www.youtube.com/watch?v=PSIdb3IPVEg

some implementation of the loops …


#25

This new version seems to work in all cases, for paths of unconnected edges (closed or not).
Time for first Torus example (25 loops of 100 edges): 105ms (must be 43ms in your machine).
Again valid for meshes and polys (with few command changes).


(
	fn findLoops obj &loop_edge &loop_vert =
	(
		edges_b = polyop.getEdgeSelection obj
		edgeVerts_b  = polyop.getVertsUsingEdge obj edges_b
		edges = edges_b as array
		edgeVerts  = edgeVerts_b as array
		edgeVerts_check = #{1..edgeVerts.count}
		edgeVerts_index = edgeVerts_check as array
		
		fn compareFn val index valArray: =
		(
			arrayVal = valArray[index]
			case of (
				(val < arrayVal): -1
				(val > arrayVal): 1
				default: 0
			)
		)
		fn firstBit arr = 
		(
			local b
			for n in arr while (b = n; off) do ()
			b
		)
		fn reverseArray &arr =
		(
			arr = for i = arr.count to 1 by -1 collect arr[i]
		)
		
		data = #()
		for i = 1 to edges.count do
		(
			vv = polyop.getedgeverts obj edges[i]
			v1_index = bsearch vv[1] edgeVerts_index compareFn valArray:edgeVerts
			v2_index = bsearch vv[2] edgeVerts_index compareFn valArray:edgeVerts
			datatemp = #(edges[i], v2_index)
			if data[v1_index] == undefined then data[v1_index] = datatemp else (if data[v1_index][2] < v2_index then data[v1_index] += datatemp else data[v1_index] = datatemp + data[v1_index])
			datatemp = #(edges[i], v1_index)
			if data[v2_index] == undefined then data[v2_index] = datatemp else (if data[v2_index][2] < v1_index then data[v2_index] += datatemp else data[v2_index] = datatemp + data[v2_index])
		)
		
		loop_vert = #()
		loop_edge = #()
		closed = #()
		first = firstbit edgeVerts_check
		k = 0	
		while not keyboard.escPressed and first != undefined do
		(
			k += 1
			closed[k] = false
			edgeVerts_check[first] = off
			loop_vert[k] = #(edgeVerts[first])
			loop_edge[k] = #()
			next = data[first][data[first].count]
			prev = first
			pos = data[first].count - 1
			end = false
			
			while not keyboard.escPressed and not end do
			(
				edgeVerts_check[next] = off
				append loop_vert[k] edgeVerts[next]
				append loop_edge[k] data[prev][pos]
				prev = next
				dim = data[next].count
				used = true
				while used and dim > 1 do
				(
					used = not edgeVerts_check[data[next][dim]]
					if used do (dim -= 2)
				)
				if dim < 2 do (dim = 2; end = true)
				pos = dim - 1
				next = data[next][dim]
			)
			if next == first do (append loop_edge[k] data[prev][pos]; closed[k] = true)
			if loop_vert[k].count == 2 do (closed[k] = false; deleteItem loop_edge[k] 2)	--	Isolated Edges
			
			if not closed[k] and data[first].count > 2 do	--	Backwards in open loops
			(
				loop_vert_temp = #()
				loop_edge_temp = #()
				next = data[first][data[first].count-2]
				prev = first
				pos = data[first].count - 3
				end = false
				
				while not keyboard.escPressed and not end do
				(
					edgeVerts_check[next] = off
					append loop_vert_temp edgeVerts[next]
					append loop_edge_temp data[prev][pos]
					prev = next
					dim = data[next].count
					used = true
					while used and dim > 1 do
					(
						used = not edgeVerts_check[data[next][dim]]
						if used do (dim -= 2)
					)
					if dim < 2 do (dim = 2; end = true)
					pos = dim - 1
					next = data[next][dim]
				)
				reverseArray &loop_vert_temp; reverseArray &loop_edge_temp
				loop_vert[k] = loop_vert_temp + loop_vert[k] 
				loop_edge[k] = loop_edge_temp + loop_edge[k]
			)
			
			first = firstbit edgeVerts_check
		)
	)

	--- PolyTools3D's TEST ----
	--/*
	delete objects
	obj = converttopoly (Torus segs:100 sides:25 radius1:50 radius2:10)
	obj.EditablePoly.SetSelection #Edge #{2}
	obj.EditablePoly.SelectEdgeRing()
	obj.EditablePoly.SelectEdgeLoop()
	--*/
	
	/*
	delete objects
	obj = converttopoly (plane pos:[0,0,1] length:100 width:100 lengthsegs:9 widthsegs:9 wirecolor:yellow)
	polyop.setedgeselection obj #{34, 36, 38, 40, 42, 52, 55, 57, 59, 62, 71, 73, 76, 79, 81, 90, 92, 94..96, 98, 100, 109, 111..112, 114, 116..117, 119, 128..129, 131, 133, 135, 137..138}
	--*/
		
	t1 = timestamp()
		loop_edge = #()
		loop_vert = #()
		findLoops obj &loop_edge &loop_vert
	t2 = timestamp(); format "Time= %
" (t2-t1)
	
	-- loop_edge[k] ==> holds the sorted edges for the number 'k' loop: polyop.setEdgeSelection obj loop_edge[k] to select the edge loop
	-- loop_vert[k] ==> holds the sorted verts for the number 'k' loop: polyop.setVertSelection obj loop_vert[k] to select the vert loop
)

Conversion to C# shouldn’t be too difficult and just have to pass ‘object’ handle.


#26

Same version but inserting items backwards instead of reversing and joining (for opened loops).
Really can’t find any performance difference, so this version is clearer:


(
	fn findLoops obj &loop_edge &loop_vert &closed =
	(
		edges_b = polyop.getEdgeSelection obj
		edgeVerts_b  = polyop.getVertsUsingEdge obj edges_b
		edges = edges_b as array
		edgeVerts  = edgeVerts_b as array
		edgeVerts_check = #{1..edgeVerts.count}
		edgeVerts_index = edgeVerts_check as array
		
		fn compareFn val index valArray: =
		(
			arrayVal = valArray[index]
			case of (
				(val < arrayVal): -1
				(val > arrayVal): 1
				default: 0
			)
		)
		fn firstBit arr = 
		(
			local b
			for n in arr while (b = n; off) do ()
			b
		)

		data = #()
		for i = 1 to edges.count do
		(
			vv = polyop.getedgeverts obj edges[i]
			v1_index = bsearch vv[1] edgeVerts_index compareFn valArray:edgeVerts
			v2_index = bsearch vv[2] edgeVerts_index compareFn valArray:edgeVerts
			datatemp = #(edges[i], v2_index)
			if data[v1_index] == undefined then data[v1_index] = datatemp else (if data[v1_index][2] < v2_index then data[v1_index] += datatemp else data[v1_index] = datatemp + data[v1_index])
			datatemp = #(edges[i], v1_index)
			if data[v2_index] == undefined then data[v2_index] = datatemp else (if data[v2_index][2] < v1_index then data[v2_index] += datatemp else data[v2_index] = datatemp + data[v2_index])
		)
		
		loop_vert = #()
		loop_edge = #()
		closed = #()
		first = firstbit edgeVerts_check
		k = 0	
		while not keyboard.escPressed and first != undefined do
		(
			k += 1
			closed[k] = false
			edgeVerts_check[first] = off
			loop_vert[k] = #(edgeVerts[first])
			loop_edge[k] = #()
			next = data[first][data[first].count]
			prev = first
			pos = data[first].count - 1
			end = false
			
			while not keyboard.escPressed and not end do
			(
				edgeVerts_check[next] = off
				append loop_vert[k] edgeVerts[next]
				append loop_edge[k] data[prev][pos]
				prev = next
				dim = data[next].count
				used = true
				while used and dim > 1 do
				(
					used = not edgeVerts_check[data[next][dim]]
					if used do (dim -= 2)
				)
				if dim < 2 do (dim = 2; end = true)
				pos = dim - 1
				next = data[next][dim]
			)
			if next == first do (append loop_edge[k] data[prev][pos]; closed[k] = true)
			if loop_vert[k].count == 2 do (closed[k] = false; deleteItem loop_edge[k] 2)	--	Isolated Edges
			
			if not closed[k] and data[first].count > 2 do	--	Backwards in open loops
			(
				next = data[first][data[first].count-2]
				prev = first
				pos = data[first].count - 3
				end = false
				
				while not keyboard.escPressed and not end do
				(
					edgeVerts_check[next] = off
					insertItem edgeVerts[next] loop_vert[k] 1
					insertItem data[prev][pos] loop_edge[k] 1
					prev = next
					dim = data[next].count
					used = true
					while used and dim > 1 do
					(
						used = not edgeVerts_check[data[next][dim]]
						if used do (dim -= 2)
					)
					if dim < 2 do (dim = 2; end = true)
					pos = dim - 1
					next = data[next][dim]
				)
			)
			
			first = firstbit edgeVerts_check
		)
	)

	--- PolyTools3D's TEST ----
	--/*
	delete objects
	obj = converttopoly (Torus segs:100 sides:25 radius1:50 radius2:10)
	obj.EditablePoly.SetSelection #Edge #{2}
	obj.EditablePoly.SelectEdgeRing()
	obj.EditablePoly.SelectEdgeLoop()
	--*/
	
	/*
	delete objects
	obj = converttopoly (plane pos:[0,0,1] length:100 width:100 lengthsegs:9 widthsegs:9 wirecolor:yellow)
	polyop.setedgeselection obj #{34, 36, 38, 40, 42, 52, 55, 57, 59, 62, 71, 73, 76, 79, 81, 90, 92, 94..96, 98, 100, 109, 111..112, 114, 116..117, 119, 128..129, 131, 133, 135, 137..138}
	--*/
		
	t1 = timestamp()
		loop_edge = #()
		loop_vert = #()
		closed = #()
		findLoops obj &loop_edge &loop_vert &closed
	t2 = timestamp(); format "Time= %
" (t2-t1)
	
	-- loop_edge[k] ==> holds the sorted edges for the number 'k' loop: polyop.setEdgeSelection obj loop_edge[k] to select the edge loop
	-- loop_vert[k] ==> holds the sorted verts for the number 'k' loop: polyop.setVertSelection obj loop_vert[k] to select the vert loop
	-- closed[k] 	  ==> tells if the number 'k' loop is closed or not (True/False)
)



#27

i don’t think it’s correct at all…

check the setup:

	delete objects
	obj = converttopoly (plane width:100 length:100 widthsegs:4 lengthsegs:4)
	
	polyop.setedgeselection obj #all
		
	t1 = timestamp()
		global loop_edge = #()
		global loop_vert = #()
		closed = #()
		findLoops obj &loop_edge &loop_vert &closed
	t2 = timestamp(); format "Time= %
" (t2-t1)

it makes ONE loop. which is absolutely impossible for this setup


#28

loop is a sequence of points where every one is connected to only one, and it has to keep the same rule in backward direction…

what you make is more like a tree… where the ‘backward rule’ doesn’t work


#29

Please, DenisT, before saying that the routine is not correct, read its conditions: “it’s only valid for unconnected loops, closed or not”
In your example, all is connected and there is more than one solution for it. It’s not a case that my routine cares about. :beer:

My routine can be usefull, for example, when you slice a mesh and you need to have the new verts ordered for each ‘sliced section’ of the mesh.


#30

hmm… it changes the rule of the original challenge…

the original task was to find all loops in ANY edge selection…

definitely you can organize your algorithm the way to process ‘isolated loops’ first. but it’s just a step of the solution


#31

I see … I did not quite understand your requirements.
But my routine seems to work fine and fast for its purpose!


#32

I really still don’t understand what do you need…
How many loops should you get in this schema?
http://matap.dmae.upm.es/cursofractales/capitulo2/square-g.gif

  • 2 closed unconnected loops? (then 2 valid solutions and 4 edges not used)
  • 4 closed loops sharing 1 edge? (then using 4 edges twice in different loops)

And in this other one? https://upload.wikimedia.org/wikipedia/commons/thumb/b/b5/4CT_Inadequacy_Example.svg/200px-4CT_Inadequacy_Example.svg.png
You will need to leave unused edges or share them in different loops.


#33

for picture #1 there two loops minimum…

the algorithm mostly has to solve these loops:

There are two loops on my picture


#34

The algorithm I proposed does solve these cases perfectly. It even gives you the two possible solutions, bridged and unbridged paths :slight_smile:
And, if the code is optimized, it is very fast.

I get these results using a modified (fixed) version of the code I posted earlier:

Bridged Paths
#(60, 62, 63, 49, 61, 74, 75, 77, 79, 81, 82, 69, 55, 67, 68, 70)
#(36, 38, 40, 41, 28, 11, 26, 39, 52)

Unbridged Paths
#(60, 61, 49, 63, 62, 74, 75, 77, 79, 81, 82, 68, 67, 55, 69, 70)
#(36, 38, 39, 26, 11, 28, 41, 40, 52)


#35

Here is one of the many “hard cases” to solve. It can be solved, but I can’t figure out a logic for a 1 or 2 passes solution for it.

The challenging part is to pick the correct edge to start.

(
	delete objects
	obj = converttopoly (plane pos:[0,0,1] length:100 width:100 lengthsegs:6 widthsegs:6 wirecolor:yellow isselected:on)
	obj.selectededges = #{8, 11, 23..25, 27..29, 35..37, 39, 41..43, 51..53, 63..64, 66..67}
	max modify mode
	subobjectlevel = 2
)

If you pick the correct edge to start, then the algorithm I proposed will work it out just perfectly.


#36

I’m not sure, but:

  • If I’m not wrong, you do the calculation of ‘neigthbors edges’ for each edge. Perhaps you can do it once at the beginning for all the edges and store the result in an array (you can use some sort of dictionnary, as I’ve done in my routine).
  • In your ‘FindHeadTail’ routine, if there aren’t pure ‘tail edges’, chose those with 2 neigthbors in one side.
  • Start with one of them, in the opposite direction of this intersection.
  • Add a final function for ‘gluing’ loops in these intersection points if needed.

#37

The code I posted is much worse than that, trust me :slight_smile: It is just a sketch as proof of concept. But the algorithm does work.

So, the code has many bugs, is redundant, and of course not optimized. Even the algorithm misses a few things, which I’ve found later when working with different scenes. But I think I’ve solved them.

The problem I face is not how to solve it, but how to do it quickly. For example, if the loop is as one of the torus test, we can pick any random edge and that will be fine. But maybe it can’t be done the way I would like and it needs to be analyzed differently. Sometime things are just like that. I haven’t put too much work on it, so I am still not sure whether there is a better/simple approach.


#38

Hi Jorge.
No, the first item wasn’t an improvement of your code (I’m not able to do that), it’s just a way to pre-store neigthbors so you can search for edges that have just 2 connections in one side.


#39

Ah, I misunderstood the comment.

Yes, for figuring out if there are intersections, I just go thru all the edges and if a vertex appears more than twice we have an intersection.