[Bf-committers] Edge Loop Selection in Meshes

Ton Roosendaal bf-committers@blender.org
Thu, 22 May 2003 12:27:36 +0200


Hi,

Alternively, you could introduce edge-selection, something more people  
have been talking about in the past. Or simpler, when you do it by just  
allowing to select 2 vertices first, it would minimize the available  
solutions a lot.

-Ton-

BTW: one second at 1.3 Ghz cpu with a Mesh how complex? If the solution  
time grows exponentially, it might be useless as a tool... or it will  
force you to program nasty 'saving' routines that need to be freed and  
updated all the time.
My guts says that this algorithm can be implemented nicely real-time  
though...



On Thursday, May 22, 2003, at 10:44 Europe/Amsterdam, Laurence Bourn  
wrote:

> 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
>>
> _______________________________________________
> Bf-committers mailing list
> Bf-committers@blender.org
> http://www.blender.org/mailman/listinfo/bf-committers
>
>
------------------------------------------------------------------------ 
--
Ton Roosendaal  Blender Foundation ton@blender.org