Intersection Free Simplification

S. Gumhold, Pavel Borodin und Reinhard Klein
In: International Journal of Shape Modeling (IJSM) (Dez. 2003), 9:2(155-176)
 

Abstract

Triangle mesh decimation and multi-resolution techniques are widely used in visualization applications for huge scenes. A large collection of different simplification algorithms exists in order to build a multi-resolution model from a given triangle mesh. All of the existing approaches focus on the creation of a geometrically close approximation of the original model. In order to produce a simplified version of a model with close layers - such as dressed humans - self-intersections result in intolerable results. Even methods that allow the sewing of close surface parts lead to unpleasant self-intersections. Only the simplification envelops allow to completely prevent them.

In this work we focus on the prevention and avoidance of self-intersection during simplication with vertex pair contractions. We examine the geomorph9 of the parametrized vertex pair contraction and detect collisions of the affected simplices. If no collision arises the operation cannot cause any new self-intersection. Otherwise we can simply discard the operation to prevent self-intersections as is done in the approach of simplification envelops. Our approach goes even further and tries to avoid the self-intersection by testing different target locations. This leads to better approximations as exhibited by a lower RMS and Hausdorff-distance. Furthermore our approach allows for arbitrary changes in the topology and garantees that geomorphs during progressive reception cannot cause self-intersections.

Stichwörter: collision detection, intersection-free simplification, pair contraction

Bilder

Paper herunterladen

Paper herunterladen

Bibtex

@ARTICLE{gumhold-2003-intersection-2,
    author = {Gumhold, S. and Borodin, Pavel and Klein, Reinhard},
     pages = {155--176},
     title = {Intersection Free Simplification},
   journal = {International Journal of Shape Modeling (IJSM)},
    volume = {9},
    number = {2},
      year = {2003},
     month = dec,
  keywords = {collision detection, intersection-free simplification, pair contraction},
  abstract = {Triangle mesh decimation and multi-resolution techniques are widely used in visualization
              applications for huge scenes. A large collection of different simplification algorithms exists in
              order to build a multi-resolution model from a given triangle mesh. All of the existing approaches
              focus on the creation of a geometrically close approximation of the original model. In order to
              produce a simplified version of a model with close layers - such as dressed humans -
              self-intersections result in intolerable results. Even methods that allow the sewing of close
              surface parts lead to unpleasant self-intersections. Only the simplification envelops allow to
              completely prevent them.
              
              In this work we focus on the prevention and avoidance of self-intersection during simplication with
              vertex pair contractions. We examine the geomorph9 of the parametrized vertex pair contraction and
              detect collisions of the affected simplices. If no collision arises the operation cannot cause any
              new self-intersection. Otherwise we can simply discard the operation to prevent self-intersections
              as is done in the approach of simplification envelops. Our approach goes even further and tries to
              avoid the self-intersection by testing different target locations. This leads to better
              approximations as exhibited by a lower RMS and Hausdorff-distance. Furthermore our approach allows
              for arbitrary changes in the topology and garantees that geomorphs during progressive reception
              cannot cause self-intersections.},
      issn = {0218-6543}
}