**comp.graphics.algorithms**

## 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

Algorithm:

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);

}

else

link-condition broken,

there is a common vertex beside 't' and 's'

in both links

}

}

Is that optimal?

TIA

Fernando Cacciola

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Replies:

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

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.