1. Introduction - aim & objectives
2. Past Work
3. Halfedged data structures
4. Methodology
5. Source Code
6. Results
7. References
8. Resources

The octree space is usually modelled as a cubical region consisting of 2^n * 2^n * 2^n unit cubes, where n is the resolution parameter and 2^n is the length of the octree space.

fig. 1: octree octants

The above figure shows the nomenclature of the octree space. The octants are labelled as 0,1,2.....7 .  Each unit cube (0,1,2,....7)  has value 0/1 depending on whether it is outside or inside the object. The octree representation of the objects is obtained by recursively sub-dividing the cubic space into octants. A 2^d * 2^d * 2^d,  1<=d<=n, octant is divided into eight 2^(d-1) * 2^(d-1) * 2^(d-1) smaller octants if the unit cube contained in the octant are not entirely 1's (full - "black") or entirely 0's (void - "white"). The octant which is subdivided is referred to as "gray" .The same process continues recursively.
 
 

fig . 1 : example of an octree

A white octant is one which lies completely outside the given solid. A gray octant is one which lies partly inside the given solid.  A black solid is one which lies completely inside the given solid.

Snapshots taken from Geomview.
 

Gray octant	White octant

Octrees have been used in image processing, pattern recognition, volume computation, collision avoidance, motion planning.

       Aim of the project -

                    In this course project we propose to build a tool for generating oc-tree representations of polyhedral objects. Further an algorithm for display of line drawings of oc-trees generated will be implemented for visualization.

back to Contents

We are implementing the octree construction algorithm as underlined in [1], and line drawing algorithm for octrees as underlined in [3].

back to Contents

Halfedge data structure  (all figures and definitions from CGAL)
 

    A halfedge data structure is an edge-centered data structure capable of maintaining incidence informations of vertices, edges and facets, for example for planar maps,  polyhedra, or other orientable, two dimensional surfaces embedded in arbitrary dimension.

fig 4.  Half edge datastructure

Each edge is decomposed into two halfedges with opposite orientations. One incident facet and one incident vertex are stored in each halfedge. For each facet and each vertex one incident halfedge is stored. Reduced variants of the halfedge data structure can omit some of these informations, for example the halfedge pointers in vertices or the storage of vertices at all.

 

fig . 5:   The three classes Vertex, Halfedge, and Facet of the halfedge data structure.
 Member functions with shaded background are mandatory. The others are optionally  supported.

A Halfedge_data_structure consists of vertices V, edges E, facets F and an incidence relation on them. Each edge is represented by two halfedges with opposite orientations. Vertices and facets are optional. See Figure   for the incidences stored and the mandatory or optional member functions possible for vertices, halfedges and facets.

fig . 6 : Responsibilities of the different layers in the halfedge data-structure design.

back to contents

The algorithm for oc-tree construction is as follows :

1. Read data from a file descibing a polyhedron into a winged-edge data structure. This data structure essentially contains the faces, edges and the vertices of the polyhedron.
2. Start with universe square as the initial representation of the polyhderon. Insert the universe square into a FIFO list.
3. If FIFO list is empty, exit.
4. Current octant = head of FIFO list. If the depth of the current octant in the oc-tree > max depth required, GOTO 3.
5. Test current octant against the polyhedron - if the octant is
1. Fully inside : label the octant as full (F). GOTO 3.
2. Fully outside : label the octant as void (V). GOTO 3.
3. Partial : label the oc tant as mixed (M), sub-divide the octant into eight smaller octants and insert the octants into the FIFO list. Also the eight smaller octants are made the children node of the current octant. GOTO 3.

This essentially boils down to testing membership of an octant against a polyhedron, which essentially means face to face intersections between the octant and the polyhedron object. To speed up the process, we can restrict the test to those pairs of octants and faces whose bounding boxes overlap. Now if there is at least one intersection then the octant is labelled mixed (M). (note,  we do not need to determine the line of intersection if any). If there is no intersection then the octant is either full (F) or void (V). A simple PMC for one vertex of the octant can be done - this will be implemented with ray casting.
 

Display of Octree Model :

Line Drawing :

We use the line-drawing algorithm suggested by J. Veenstra and N. Ahuja. The algorithm proceeds as follows :

1. Do a Breadth First Traversal of the octree generated from the algorithm above.This traversal has a property that if a node x occludes a node y, then node x is visited first.
1. For each Full node (F) in the traversal "graphics information" is stored in a graphic node. This graphics node contains information like - a reference to the octree node (F octant), nine edges of  the projection of the octant, six vertices of the projected octant, bounding box for this projection, coordinate of the farthest point of the octant (as seen by the user), side lenght of the cube and a pointer to the next graphics node.  At this point only the screen coordinates of the vertices of the projection are stored in the graphics node.
2. Add this graphic node to the end of a linked list.
3. The six of eight unused child pointers of the F node are made point to neighbours in the six directions corresponding to the faces of the cube.
2. To Eliminate cracks (a crack is a line that should not be drawn because it corresponds to an edge between two octants whose surfaces are contiguous and, were it to be drawn would appear as a crack on an otherwise smooth surface), all neighbours of an octant must be found out and tested whether they share a common border. The threading done earlier for F nodes helps in this. This process may result in fragmentation of an edge, so edges are stored as linked lists of visible segments.
3. After eliminating cracks - the projection of the black octants are calculated and stored in the respective graphics nodes.
4. Now, for elimination of hidden lines - each edge of a projected octant is tested for intersection with projections of all other octants whose graphic nodes occur earlier in the list. For these tests a modified Cohen-Sutherland clipping algorithm is used.

back to Contents

Sample input file (in OFF format).

Source code tarred and zipped

Readme  file

Manifest file

back to Contents

Results
 

The following images are snapshots taken from real test runs on four objects. The  snapshots are taken from Geomview.
The fourth case is erroneous with some extra octants 

Input	Output

 
 
 
 
 
 

back to Contents

Homer H. Chen and Thomas S. Huang, A survey of construction and manipulation of octrees, Computer Vision, Graphics and Image Processing 43, 1988, 409-431.

Chris L. Jackins and Steven L. Tanimoto, Oct-Trees and Their Use in Representing Three Dimensional Objects, Computer Graphics and Image Processing, 14, 1980, 249-270.

Jack Veenstra and Narendra Ahuja, Line Drawing of Octree Represented Objects, ACM Transactions on Graphics, 7, January 1988, 61-75.

Hanan Samet, Neighbour Finding in Images Represented by Octrees, Computer Vision, Graphics and Image Processing, 46, 1989, 367-386.

 

• Computational Geometry Algorithms Library (CGAL) : This libray is extensively used in the implementaion
• Geomview : Software used for display of the octrees.

 
 
 
 
 
 
 
 

Back to Contents