**comp.graphics.algorithms**

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

Fernando Cacciola

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

Optimality can't be discussed without knowing the implementation

platform. If you can afford the memory space and bandwidth, the

optimal algorithm could be one that maintains stored links for each

vertex and edge, or even the result of the "link condition" test

itself, at all times. This follows from the two most fundamental rules

of optimization:

0) The fastest algorithm of all is the one you never have to run.

1) The next-fastest one is the on that is only ever run once.

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

NB: not all triangulations are 2-manifolds. Not even if the surface

that was triangulated was a manifold.

--

Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)

Even if all the snow were burnt, ashes would remain.

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Fast determination of the link-condition in a triangular mesh =>

Replies:

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

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.