Coherence in scan-line algorithms for CSG

Meister Eduard Gröller, Peter Brunner
Coherence in scan-line algorithms for CSG
TR-186-2-94-10, January 1994 [paper]

Information

Abstract

Scan-line algorithms for visibility calculation exploit various types of coherence properties. Several scan-line algorithms for Constructive Solid Geometry (CSG) are discussed. In one approach CSG primitives are represented by polygonal approximations. Another technique processes CSG primitives as general quadric surfaces. We investigate the handling of frequently occurring quadric surfaces (cube, cone, sphere, cylinder) as distinct cases. Thus the differing properties of such objects can be used more efficiently than a uniform approach would allow. A so called eBRep (extended Boundary Representation) is defined for the frequently occurring quadric surfaces. An eBRep is an exact representation of a quadric object and contains curved edges and faces. For each of the above mentioned quadric surfaces a different, geometry dependent eBRep is specified. A comparison between the polygon-based scan-line algorithm for CSG and our eBRep based approach is done. eBRep is a storage efficient exact representation of quadric surfaces, well suited for scan-line visibility determination.

Additional Files and Images

Weblinks

No further information available.

BibTeX

@techreport{Groeller-1994-CSA,
  title =      "Coherence in scan-line algorithms for CSG",
  author =     "Meister Eduard Gr\"{o}ller and Peter Brunner",
  year =       "1994",
  abstract =   "Scan-line algorithms for visibility calculation exploit
               various types of coherence properties. Several scan-line
               algorithms for Constructive Solid Geometry (CSG) are
               discussed. In one approach CSG primitives are represented by
               polygonal approximations. Another technique processes CSG
               primitives as general quadric surfaces. We investigate the
               handling of frequently occurring quadric surfaces (cube,
               cone, sphere, cylinder) as distinct cases. Thus the
               differing properties of such objects can be used more
               efficiently than a uniform approach would allow. A so called
               eBRep (extended Boundary Representation) is defined for the
               frequently occurring quadric surfaces. An eBRep is an exact
               representation of a quadric object and contains curved edges
               and faces. For each of the above mentioned quadric surfaces
               a different, geometry dependent eBRep is specified. A
               comparison between the polygon-based scan-line algorithm for
               CSG and our eBRep based approach is done. eBRep is a storage
               efficient exact representation of quadric surfaces,         
                      well suited for scan-line visibility determination.",
  month =      jan,
  number =     "TR-186-2-94-10",
  address =    "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria",
  institution = "Institute of Computer Graphics and Algorithms, Vienna
               University of Technology ",
  note =       "human contact: technical-report@cg.tuwien.ac.at",
  keywords =   "visibility, scan-line algorithm, Constructive Solid Geometry
               (CSG), quadrics, coherence",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/1994/Groeller-1994-CSA/",
}