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