Overview   Tree   Index 
NPR Literature
PREV  NEXT FRAMES  NO FRAME 

[KW+97]  Contour Edge Analysis for Polyhedron Projections

Kettner:1997:CAE (In a collection)
Author(s)Kettner L. and Welzl E.
Title« Contour Edge Analysis for Polyhedron Projections »
InGeometric Modeling: Theory and Practice: The State of the Art
Editor(s)Wolfgang Strasser and Reinhard Klein and René Rau
Page(s)379--394
Year1997
PublisherSpringer-Verlag
AddressBerlin
URLhttp://www.mpi-sb.mpg.de/~kettner/pub/contour_edge_blaubeuren_96_a.html
Editor(s)Wolfgang Strasser and Reinhard Klein and René Rau

Abstract
Given a polyhedron (in 3-space) and a view point, an edge of the polyhedron is called contour edge, if one of the two incident facets is directed towards the view point, and the other incident facet is directed away from the view point. Algorithms on polyhedra can exploit the fact that the number of contour edges is usually much smaller than the overall number of edges. The main goal of this paper is to provide evidence for (and quantify) the claim, that the number of contour edges is small in many situations. An asymptotic analysis of polyhedral approximations of a sphere with Hausdorff distance eps shows that while the required number of edges for such an approximation grows like Theta(1/eps), the number of contour edges in a random orthogonal projection is Theta(1/sqrt(eps)). In an experimental study we investigate a number of polyhedral objects from several application areas. We analyze the expected number of contour edges and the expected number of intersections of contour edges in a projection (a quantity relevant for line sweep algorithms). We conclude that, indeed, the number of contour edges is small and the number of intersections of contour edges appears to be even more favorable. As a specific application we describe the computation of the silhouette of a polyhedral object with a sweep line algorithm in object space.

BibTeX code
@incollection{Kettner:1997:CAE,
  optpostscript = {},
  author = {Lutz Kettner and Emo Welzl},
  optkey = {},
  optannote = {},
  optseries = {},
  opttype = {},
  editor = {Wolfgang Strasser and Reinhard Klein and Ren{\'e} Rau},
  optedition = {},
  url = {http://www.mpi-sb.mpg.de/~kettner/pub/contour_edge_blaubeuren_96_a.html},
  address = {Berlin},
  localfile = {papers/Kettner.1997.CAE.pdf},
  optchapter = {},
  publisher = {Springer-Verlag},
  optkeywords = {},
  optmonth = {},
  citeseer = {http://citeseer.ifi.unizh.ch/kettner97contour.html},
  optdoi = {},
  optwww = {},
  optcrossref = {},
  booktitle = {Geometric Modeling: Theory and Practice: The State of the Art},
  optvolume = {},
  optnumber = {},
  abstract = {Given a polyhedron (in 3-space) and a view point, an edge of the
              polyhedron is called contour edge, if one of the two incident
              facets is directed towards the view point, and the other incident
              facet is directed away from the view point. Algorithms on
              polyhedra can exploit the fact that the number of contour edges is
              usually much smaller than the overall number of edges. The main
              goal of this paper is to provide evidence for (and quantify) the
              claim, that the number of contour edges is small in many
              situations. An asymptotic analysis of polyhedral approximations of
              a sphere with Hausdorff distance eps shows that while the required
              number of edges for such an approximation grows like Theta(1/eps),
              the number of contour edges in a random orthogonal projection is
              Theta(1/sqrt(eps)). In an experimental study we investigate a
              number of polyhedral objects from several application areas. We
              analyze the expected number of contour edges and the expected
              number of intersections of contour edges in a projection (a
              quantity relevant for line sweep algorithms). We conclude that,
              indeed, the number of contour edges is small and the number of
              intersections of contour edges appears to be even more favorable.
              As a specific application we describe the computation of the
              silhouette of a polyhedral object with a sweep line algorithm in
              object space.},
  title = {{C}ontour {E}dge {A}nalysis for {P}olyhedron {P}rojections},
  year = {1997},
  pages = {379--394},
}

 Overview   Tree   Index 
NPR Literature
PREV  NEXT FRAMES  NO FRAME 

Submit a bug

This document was generated by bib2html 3.3.
Copyright © 1998-05 Stéphane GALLAND (under the GNU General Public License)

Valid HTML 4.01!Valid CSS!