comp.graphics.algorithms

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

Fernando Cacciola wrote:
> 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:

> 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

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.