[Bf-committers] Edge Loop Selection in Meshes

[Andy Davis]

I burned a brain cell or two considering how this problem might be solved
using standard techniques.  What I came up with is a modification of the
relaxation algorithm and control for Dijkstra's shortest path search.

What follows is the best that my limited Comp Sci skills can do to describe
the algorithm and relaxation function.  I'm sure I'll find a dozen errors in
this description, but it's a start.

First, my terminology:
d[u,v] is the edge distance between vertices u and v.
D[u] is the currently calculated distance from the start point to vertex u.
p[u] is the current ancestor vertex of vertex u (in the current state of
graph solution).
P[u] is the ancestor chain leading from vertex u back to the start point.
A[u] is the set of verticies adjacent to vertex u

C is the set of constraint verticies.
C[u] is the subset of constraint vertices that lies along P[u] and u.
Simply put, it is the intersection of P[u] +u & C.

White verticies have not been touched by the search.
Grey vertices have been touched by the search, but have not had their final
D[u] calculated
Black verticies have had their final D[u] calculated.  In this algorithm, a
vertex u cannot be black until C[u] == C

Dijkstra divided the vertices into two camps: Those where the shortest path
was known, and those where it wasn't. The first set S, would be the black
verticies.  The second set Q is repeatedly queried for the vertex with the
lowest D[u].  Once the  edges leaving this vertex are relaxed, the vertex is
moved to S.  To these two, I add a Limbo set, L.  These are gray verticies
that have been evaluated, but their C[u] at evaluation did not contain all
of C.

The relaxation function looks like:

relax(u,v)
	C[uv] = (P[u] + v) intersect C
	if( C[uv] is a superset of C[v] ||
		(C[uv] contains C[v] &&  D[u] + d(u,v) < D[v]) )
		D[v] = D[u] + d(u,v)
		p[v] = u

Essentially it favors the incoporation of constraint verticies to distance
(it will accept a longer path if it incorporates more of the constraint
verticies).  Similarly, the Q.ExtractMinimum() function gives precedence to
the vertex with the largest C[u], the shortest D[u] is a secondary criteria.

So the algorithm ends up looking like:

create search element for start vertex
Q.add( start )
while( ! Q.empty() )
    u = Q.ExtractMinimum()
    if( C[u] == C )
        S.add(u)
    else
        L.add(u)

    if any adjacent vertex is the end point, and this vertex is black, then
the solution is P[u], break the loop
    foreach v in A[u] - p[u]
        if( v is black )
            continue
        if( v is white )
            create search element, add to Q
        if( v in L )
            remove v from L, add to Q
        relax(u,v)


One nice implementation point is that the search should only need to
allocate memory for grey and black verticies.  White verticies (those that
have not yet been touched by the search) do not require any representation.
This should keep the memory footprint of the search down as long as the
constraint vertices aren't too wacko.

-Andy



-----Original Message-----
From: bf-committers-admin@blender.org
[mailto:bf-committers-admin@blender.org]On Behalf Of Willian Padovani
Germano
Sent: Thursday, May 22, 2003 8:04 PM
To: Blender Committers List
Subject: Re: [Bf-committers] Edge Loop Selection in Meshes


On Thu, 2003-05-22 at 11:46, Chris Want wrote:
> My feeling that the best approach for this
> is to create a 2nd editmode (ctrl-Tab, prehaps)
> that uses winged edge datatypes and allows for
> the selection of edges. Then there all sorts of
> edge based operations that become possible.
> There is also the wings source code to look
> at as a reference (if you don't mind reading
> erlang).

That's a pretty good idea.  The kind of feature that, well done, would
shake the open source modeling community.  Don't know how easy that
would be, though.

>From what I've seen -- corrections welcomed, of course -- in Edit Mode
Blender converts the mesh data to the "E" type, where verts/faces have
flags to indicate whether they are selected, etc.  Having a new "WMesh"
mode for winged edge structures seems to fit nicely.

Only thing (just something users would have to get used to) is that a
winged edge representation doesn't like lines and isolated vertices, but
its possible to "convert" from normal Blender representation to that and
back, of course.

We should really consider Chris' suggestion...

--
Willian, wgermano@ig.com.br

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