[Bf-committers] Edge Loop Selection in Meshes

[Andy Davis]

Greetings.

As a getting to know you excercise in Blender, I am planning to put together
an edge loop selection algorithm.  I am soliciting any input, commentary, or
advice that this group can offer.

In short, this is what I have in mind:

-The active vertx is the start point.
-The mesh is treated as a cyclic undirected graph.
-The algorithm finds the shortest distance weighted cycle that incorporates
each vertex that is adjacent to the start point.  I think this will yield a
maximum of two paths.  To visualize, think of concentric loops forming a
mouth.  The obvious loop is the one going around the mouth, but there is
also a path that runs around the entire head.
-The algorithm can be further constrained by needing to incorporate all
selected vertices.

>From a UI perspective, the user can select a single vertex and then press a
key (I think CTRL-L might be the right thing here because that selects loops
when you are working with NURBS).  Pressing CTRL-L again would cycle through
the solutions (again, I think there is a maximum of two).

Should the user have some unusual geometry, or just want a different take on
the loop, they could select additional verticies, and then detect loops from
the last selected vertex.

Algorithmicly, I think that I can adapt a Dijkstra style greedy algorithm to
the task.  It just needs to be smart enough to reject any detected cycle
that isn't the desired cycle, and only traverse an edge once.  I'm less
confident that the feature of incorporating arbitrary additional verticies
can be accomodated, but I have really only just begun to look at this
problem.  I would greatly appreciate any input from someone with more formal
schooling in Comp Sci, or someone who just plain knows how to crack this
nut.

As far as implementation goes, this will be done with lazy evaluation so it
doesn't load anything down if you're not using it.  Depending on the search
times, it might be nice to keep some search tree history in the mesh object.
This way if you're alternating between loops as you model a face, an entire
recalc doesn't have to be done each time.  If it seems to take less than a
second on my machine (1.3GHz), I don't think that I'll bother.

That's the nickel tour, let me know what you think.

-Andy