ALGORITHM FOR GENERATING OCTREES FROM OBJECT SILHOUETTES IN PERSPECTIVE VIEWS.

Octrees are useful for object representation when fast access to coarse spatial occupancy information is necessary. An efficient algorithm for generating octrees from multiple perspective views of an object is presented. The algorithm first obtains a polygonal approximation of the object silhouette. This polygon is then decomposed into convex components. For each convex component, a pyramid is formed treating the viewpoint as its apex and the convex components as one of their cross sections. The octree representation of each of these pyramids is obtained by performing intersection detection of the object with the cubes corresponding to octree nodes. The intersection detection step is made efficient by decomposing it into a coarse-to-fine sequence of intersection tests. The octree for one silhouette is obtained by taking the union of octrees obtained for each component. An intersection of octrees corresponding to different viewing directions gives the final octree of the object.