|
The representation and manipulation of three dimensional
objects are important topic in the fields of computer graphics,
pattern recognition, medical imaging and robotics. Hierarchical
data structures such as quadtree and octree are efficient ways
to store the spatial information because they provide a compact
data structure and allow rapid data access to occupancy
informa- tion. The linear quadtree and linear octree are
hierarchical pointerless representation which store object
elements as sorted codes. In this thesis, we propose a new
method to reconstruct the linear octree from its edge view
projections. An improved algorithm for displaying linear octree
is also presented. In generally, volume intersection is the
underlying paradigm wherein the objects are reconstructed by
intersecting the vol- umes generated by sweeping the silhouette
along the respective view direction. On the basis of the
property of edge view pro- jction and active border, we
traverse the silhouette represented by linear quadtree to
obtain base nodes and a hash table is de- vised to store these
base nodes. Then we perform a tree traversal from target tree
and determine if the projections of its nodes overlap any black
nodes of the silhouette stored in the hash table, and colors
they are appropriate. In such a way, we find a linear time
algorithm for constructing linear octree from its edge view
projections. Projecting octrees to display three dimensional
objects is the converse problem of construction octrees from
projection images. Basically, it determines the efficiency of
displaying linear octree that how to find visible faces of
black octant, number of nodes traversed and time spent to scan
conversion. We propose an efficient algorithm based on
traversing linear octrees in a front-to-back order determined
by a given direc- tion, and the visible faces are decided by
using active border. We also show that the algorithm is a
linear time algorithm.
|