[Bf-committers] Edge Loop Selection in Meshes

[Laurence Bourn]

Very nice idea. However, I am not sure that 2 is the minimum number of
paths. Take for example a sphere then all great circles of the sphere
through the point are minimum edge loops. I guess you can extend this to any
solid of revolution to get the same problem. Although maybe you can just
pick a representative solution in this case. 

I guess what you are trying to find is the set of locally least long paths
between the vertex and itself (ignoring the trivial path). I don't think the
number of solutions for complex objects is necessarily 2. 

That Hoppe guy was doing something similar in the initial step in his
geometry images paper, you might try and adapt that algorithm.

http://research.microsoft.com/~hoppe/#gim

Good luck!
Laurence.

> -----Original Message-----
> From: Andy Davis [mailto:biggernoise@attbi.com]
> Sent: 22 May 2003 05:16
> To: bf-committers@blender.org
> Subject: [Bf-committers] Edge Loop Selection in Meshes
> 
> 
> 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
> 
> 
> _______________________________________________
> Bf-committers mailing list
> Bf-committers@blender.org
> http://www.blender.org/mailman/listinfo/bf-committers
>