Home Products Download Order Contacts


Subject: Fast determination of the link-condition in a triangular mesh

Hi people,

In the realm of triangulated surface mesh simplification there is a
technique known as edge-collapse which uses a so-called "link-condition".
That condition is a necessary (but not sufficient AFAICT) to preserve
the topological validity of the mesh after the collapse.

If the edge 'pq' is given by the vertices 'p' and 'q' (the orientation
of the edge is unimportant), the link condition is as follows:

link(p) .intersection. link(q) == link(pq)

The link of a vertex is the cycle of edges _around_ the vertex and
likewise the link of an edge is the cycle of edges around the edge.

Now, the above is what you can find in any paper on the subject.. but
what I can't find is the optimal algorithm to determine the
link-condition. Yet, it seems TO ME that this determination is actually
quite simple at least in the case where the input mesh is known to be a
valid 2-manifold (that is, a triangulation).

So this is the question I'm asking:

Is the following algorithm in pseudo-code the correct way to determine
the link condition assuming a valid (2-manifold) triangulated surface mesh?

"x_y" denotes the edge between "x_y"
next_ccw(x_y) denotes the next edge around x going ccw
next_cw(x_y) denotes the next edge around x going cw


p_t = next_ccw(p_q)
p_s = next_cw (p_q)
q_t = next_cw (q_p)
q_s = next_ccw(q_p)

// checks that 't' and 's' are in the intersection of
// link(p) and link(q)
if ( target(p_t) == target(q_t)
&& target(p_s) == target(p_s)
// check that nothing else is in that intersection

p_tn = next_ccw(p_t) ;
p_bn = next_cw (p_b) ;
q_tn = next_cw (q_t) ;
q_bn = next_ccw(q_b) ;

while ( p_tn != p_tb && q_tn != q_tb )
if ( target(p_tn) != target(q_tn)
|| target(p_bn) != target(q_bn)
p_tn = next_ccw(p_tn);
q_tn = next_cw (q_tn);
p_bn = next_cw (p_bn);
q_bn = next_ccw(q_bn);

link-condition broken,
there is a common vertex beside 't' and 's'
in both links

Is that optimal?


Fernando Cacciola


View All Messages in comp.graphics.algorithms


Re: Fast determination of the link-condition in a triangular mesh

Copyright 2006 WatermarkFactory.com. All Rights Reserved.