Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Depth-order point classification techniques for CSG display algorithms
Jansen F. (ed) ACM Transactions on Graphics (TOG)2 (3):40-70,1983.Type:Article
Date Reviewed: Aug 1 1991

Image generation by ray tracing is dominated by the cost of evaluating the intersections of rays with geometric objects. For objects and scenes modeled using constructive solid geometry, boundaries of objects are not stored explicitly, and intersection points with the geometric primitives must be further classified to determine whether they lie on portions of the primitives that are part of the constructed object. This paper is concerned with performing the classification task efficiently. Jansen gives a thorough survey of a variety of schemes to avoid unnecessary tree traversal and point classification. If the result of classifying a sequence of intersection points for a ray is stored in a list, this list can be used to exploit ray-ray coherence. While more elaborate list structures can be devised (storing all possible ray intersection classification sequences in a compact manner), experimental results indicate that maintaining and updating a single list is more efficient. Several methods of limiting tree traversal for a single ray are suggested. In combination, the status tree method (which records in each node the result of applying the node’s Boolean operator to its two subnodes) and the single list structure proved to be most efficient for the test object used by the author. It would have been instructive to include statistics for more than one object, but it is pleasant to note that the test object is a recognizable mechanical part and not an artificial concoction of checkerboards, mirrors, and spherical objects.

Reviewer:  A. R. Forrest Review #: CR115112
Bookmark and Share
 
Geometric Algorithms, Languages, And Systems (I.3.5 ... )
 
 
Constructive Solid Geometry (CSG) (I.3.5 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Geometric Algorithms, Languages, And Systems": Date
Oriented projective geometry
Stolfi J., Academic Press Prof., Inc., San Diego, CA, 1991. Type: Book (9780126720259)
Jul 1 1992
A linear time algorithm for computing the convex hull of an ordered crossing polygon
Ghosh S., Shyamasundar R. Pattern Recognition 17(3): 351-358, 1984. Type: Article
Jan 1 1985
Covering a square by small perimeter rectangles
Alon N., Kleitman D. Software Engineering Journal 1(1): 1-7, 1986. Type: Article
Sep 1 1987
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy