Document Type

Technical Report

Publication Date

1982-01-01

Filename

WUCS-82-1.pdf

Technical Report Number

WUCS-82-1

Abstract

An octal tree subdivision recursively divides a bounded three-dimensional volume into octanta about an internal division point. This scheme has been used to represent cellular or enumerated voxel models of solid objects. Given one or more sets of points sampled from the surface of a solid, an octal tree may be generated in which each leaf node contains m or less points. By specifying the tree traversal rule, the points are accessed in a sorted order. By defining m=3, a divide-and-conquer surface triangulation algorithm may be developed which does not require special sampling conditions (such as co-planarity) on subsets of the sample points. By element(octal) a pre-ordering is established on the faces. From any viewpoint, surface polygons can be visited in a priority ordered fashion by appropriate tree traversal. The pre-ordering established is shown to be useful in several graphics related contexts. The ability to preprocess the faces so as to establish a viewpoint independent data structure for priority sorting leads to a useful hidden surface techniques. By appropriate modification of the traversal rule a ray-tracing algorithms may visit only faces lying on the ray in a priority order. The tree traversal visits faces in a fashion which causes reference to regions in a frame buffer to be geometrically localized, substantiating reducing page faults in a virtual buffer. The sorting process allows for simple geometric merging of sets of surface measurements which contain no fiducial information.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7862DT8

Download

Share

COinS