[Bf-committers] Edge Loop Selection in Meshes

[Andy Davis]

As far as edge selection goes, for now I think I want to stay out of the GUI
code.  I think that if the general case of arbitray vertex inclusion is a
reasonable performer, it will incorporate the two vertex solution.  If we
want to add constraints to the required selections so that users aren't
confused, we can add that after the fact.  Perhaps a regular and 'expert'
mode.

I think that you're right about the algorithm being somthing fast to
generate.  Unless totally goofy verticies have been added to the selection,
a greedy algorithm should be able to arrive at a solution set pretty
quickly.

I have a couple of models that are reasonably complex, I'll probably also
test it on a Make Human mesh.

-Andy

-----Original Message-----
From: bf-committers-admin@blender.org
[mailto:bf-committers-admin@blender.org]On Behalf Of Ton Roosendaal
Sent: Thursday, May 22, 2003 5:28 AM
To: bf-committers@blender.org
Subject: Re: [Bf-committers] Edge Loop Selection in Meshes


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

_______________________________________________
Bf-committers mailing list
Bf-committers@blender.org
http://www.blender.org/mailman/listinfo/bf-committers