ISSN:
1432-0541
Keywords:
Computational geometry
;
Hidden-line elimination
;
Perspective view
;
Isothetic rectangles
;
Parallelepipeds
;
Fractional cascading
;
Segment tree
;
Range tree
;
Dominance relation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We present a new hidden-line elemination technique for displaying the perspective view of a scene of three-dimensional isothetic parallelepipeds (3D-rectangles). We assume that the 3D-rectangles are totally ordered based upon the dominance relation of occlusion. The perspective view is generated incrementally, starting with the closest 3D-rectangle and proceeding away from the view point. Our algorithm is scene-sensitive and uses0((n +d) logn log logn) time, wheren is the number of 3D-rectangles andd is the number of edges of the display. This improves over the heretofore best known technique. The primary data structure is an efficient alternative to dynamic fractional cascading for use with augmented segment and range trees when the universe is fixed beforehand. It supports queries inO((logn +k) log logn) time, wherek is the size of the response, and insertions and deletions inO(logn log logn) time, all in the worst case.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01758847
Permalink
