Here’s a new version that works for the three examples of closed-unconnected loops (and hope for all cases).
It takes 99ms instead of 90ms for the first example (I suppose 40ms in Jorge’s machine).
In fact, the same algorithm should work for meshes, taking care of duplicated edges.
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.
I’m just with it. Not easy. And performance will go down.
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.
Also I store a Point4 values instead of vertex index, where Point4 is vert’s position and it’s index.
// Add the first two points.
// Use loopcount/maxLoop just to avoid a while(1) loop.
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.
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).
Conversion to C# shouldn’t be too difficult and just have to pass ‘object’ handle.
Same version but inserting items backwards instead of reversing and joining (for opened loops).
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.
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.
I see … I did not quite understand your requirements.
But my routine seems to work fine and fast for its purpose!
How many loops should you get in this schema?
You will need to leave unused edges or share them in different loops.
And, if the code is optimized, it is very fast.
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.
If you pick the correct edge to start, then the algorithm I proposed will work it out just perfectly.
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.
The code I posted is much worse than that, trust me 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.
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.
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.