OctSolid

Conventional voxel (aka block) models represent a 3D volume by a fixed 3D array.  Its  major disadvantage is that 3D space is divided into equi-sized blocks, even in regions of homogeneity.  The size of the block is a significant limiting factor, since a small voxel size is required for accurate representation but may be impractical because of large memory requirements due to the uniform allocation of space to individual homogeneous voxels.  This also imposes computational overheads.

In simple terms, the octree may be regarded as a variably sized voxel model where areas of homogeneity are modeled by large blocks and complex zones modeled by smaller blocks  The number of blocks used to model any portion of geometric entity, is therefore a function of the homogeneity of the object and the complexity of its boundary.

Due to spatial coherence, octree modeling can achieve substantial storage compression compared to voxel model (even with sub-voxel breakage capabilities), particularly in the case of homogenous object.  Furthermore because space is recursively decomposed, homogeneous and heterogeneous entities can be represented in the same octree model at different resolutions.

There are two types of octree implementation: pointer based and pointer-less. Pointer-less representation has a substantial advantage over pointer-based representation due to its self-compression capability. It uses a unique locational key to represent each octant.  Such a key, when decoded, indicates not only the size and location of the octant it represents, but also its spatial relation with other octants in the model. Such a list of locational keys is sorted and called a linear octree.

Version 1.1 Capabilities

Over past few years, ThreeDify Incorporated has developed ThreeDify OctSolid, a compact linear octree library in C that exposes most linear octree operations through easily accessible APIs. ThreeDify OctSolid is available to third party developers in a static library format.

ThreeDify OctSolid v1.1 offers following capabilities:

• Linear octree creation through conversion from the following common geometric 3D entities:  line segment, surface consisting of polygons, voxel model and polyhedron
• Encoding, decoding and spatial indexing of linear octrees
• Compression of linear octrees
• Efficient (linear time) set operations including intersection, union and pair-wise differences on linear octree encoded objects
• Direct and indirect neighbour finding
• Connected component labelling
• Bordering (extract bordering voxels from a linear octree)
• Filling by octants (reconstruct a linear octree given its surface border)
• Easy integral property (volume, surface) calculations of objects encoded as linear octrees

For more information, download the ThreeDify OctSolid API documentation ThreeDify OctSolid.doc.

Applicability

Octree has been successfully used to reconstruct 3D medical objects from MRI images in medical imaging and to model orebodies in geological modeling and mine design. We briefly outline how ThreeDify OctSolid can be used to efficiently address real world problems in geological modeling many of which are computationally expensive to solve with other modeling methods.

Modeling Large Deposits

The maximum octree universe supported by ThreeDify OctSolid is (2^19 x 2^19 x 2^19), which is huge. Modeling such universe with a conventional block model is out of the question. With ThreeDify OctSolid, it becomes effortless even with any of today's 32 bit Visual C++ compilers.

Integral Property Calculations

Fast calculation of integral properties is one of the fundamental requirements in geological modeling and mine planning.  With linear octrees, the calculation is made easy by determining the number of voxels in an octree model and applying a multiplication factor.  That is,

Volume = (Total No. of Voxels) * (Volume per Voxel);

Surface Area = (Total No. of Voxel Border Faces) * (Volume per Voxel);

These operations are very efficient since they involve only a list scan and a single multiplication.

Spatial Search Functions

Spatial searches are realized by encoding/decoding and neighbour finding techniques.  All of them utilize integer processing and bit manipulations, and thus are computationally efficient.

The ability to investigate adjacency effectively offers some advanced capabilities which would otherwise be difficult to achieve with traditional CAD software.  Further research is needed to fully exploit these capabilities in the following areas:

Geostatistical analysis. For instance, a typical operation in Kriging is the search for nearby drill hole segments (within a specified search radius) to determine the grade at a given point.  The conventional approach employs an extra  fixed 3D grid which is memory demanding.  Neighbour finding techniques will provide an attractive alternative in this case, saving memory with no noticeable speed penalty;

Feature tracing. Determination of appropriate underground mining methods in multiple vein-type deposits requires detailed knowledge of geological structures and their spatial location.  By associating structural information with a linear octree model, and utilizing the spatial search functions, it is possible to trace a vein through the host rock and identify geological discontinuities, determine the average width of the vein along a given length, investigate the adjacency of neighbouring veins, and calculate average grade and tonnage for a given mining area.

Spatial and Relational Query

The generic spatial search functions are suitable for processing spatial queries, such as "Where is ...?", "How far from...?" and "What is the distance between ...?".  Other more complex queries can be made  through combinations of these simple queries.  For instance, the query:

"What is the tonnage and average grade of the nearest ore region to development end 5 on level 4?"

can be resolved by labelling all the components of ore using the connected component labelling algorithm, finding the border voxels of each component and determine the distance between the development end 5 and the border voxels.  The component whose border is closest to the development end is then identified and its mass and average grade calculated.

Relational queries cannot be handled by linear octrees alone.  However, when integrated with a commercial Relational Database Management System (RDBM), such as Oracle , linear octree models are capable of supporting relational queries.  Such an attempt has been made by Mao et. al. (1989) in their G-Quadtree/G-Octree Image Data Base System (GIDBS), which integrates an octree variant, G-octree, with a commercial RDBMS called G-Base.  By using the octal codes as table indices, the RDBMS was made to simulate a hierarchical tree structure so that both spatial and relational queries can be performed simultaneously (Mao et. al. 1989).

Key Benefits

• Compact, efficient and fully re-entrant, making it an ideal software component
• Support huge universe (2^19 x 2^19 x 2^19)
• Free maintenance releases and 60% off on all later major releases.

Pricing