Computer Graphics & Geometry

An Octree Surface Codification Based On Discretized Planes .

Imma Boada,
IIiA,Institut Informatica i Aplicacions,
Universitat de Girona, Spain
e-mail: imma@ima.udg.es
Isabel Navazo,
UPC, Departament LSI,
Universitat Politecnica de Catalunya, Spain
e-mail: isabel@lsi.upc.es 

Contents

Abstract: In this paper we propose a method to maintain a multiresolution surface codificiation of a fitted surface in the nodes of an octree. The proposed codification is based on the number and the topology of the planes that define the surface of each intersected node. The surface is codified in the maximal division nodes of the octree, then a merging process is applied to detect and merge coplanar facets. At the end of this merging process the surface is encoded in a set of terminal nodes distributed at different levels of the octree. No error is introduced by the decimation method. The algorithm to reconstruct the surface of each intersected node is also presented. Various examples demonstrate that in the best situation a reduction of almost a 50 per cent on the number of polygons can be achieved.

Keywords: Octrees, Isosurface Fitting, Marching Cubes, Surface Simplification.

1.  Introduction

Multiresolution has become one of the most promising optimization methods for resolving the conflict among the increasing size of volume data sets and the capabilities of available hardware. Encoding in a single structure a large number of different representations, multiresolution schemes allow the extraction of variable resolution representations according to the user or the viewing parameters specifications. Many different approaches have been proposed for the multiresolution management of surfaces (see [CMS98] for a survey). The multiresolution volume data management has been also extendely analyzed with methods based on classical wavelets [Wes94, Mur95], on multidimensional trees [WVG94], or more sophisticated methods that take advantage of hardware capabilities [LHJ99,BNS01, WWHZE00]. Our interest has been centered on the idea of defining a multiresolution framework able to support multiresolution surface and volume data renderings. To define this framework we propose a method to codify a surface on an octree data structure that different of previous octree based methods maintains the surface-volume data connection. The proposed surface cofication is based on a classification of original Marching Cubes patterns in five classes characterized by the number and the topology of the planes that define the surface contained in an intersected cell. Such codification is used to represent the surface at maximal division nodes of an octree. Then, a merging process is applied in a bottom-up traversal and sibling nodes which can be represented in the parent node in one of the five possible configurations without introducing error are purged. At the end of this process the surface is codified in a set of nodes distributed at different levels of the octree. To generate the surface, a reconstruction technique is applied at each terminal intersected node achiving in the best situation simplifications of almost 50% on the number of polygons. The main advantage of this codication strategy is that not only reduces surface output fragmentation it also provides a framework able to support multiresolution renderings.

2 Previous Work

The Marching Cubes (MC) has become the best known of the surface-based rendering techniques  [LC87]. Since its publication in 1987 a lot of work has been done to overcome its main disadvantages: algorithm's efficiency has been enhanced with strategies that avoid processing all volume data cells [BPS96,CMM97,LSJ96,SHL96,WVG92]; several techniques to solve ambiguities have been proposed [Dur88,VGW94,MSS94b] and a lot of strategies to reduce the large amount of generated polygons defining surfaces have been also presented [Dee95,ESV96,Hop96,SZL92]. Centering our interest on surface simplification techniques we can consider two main categories of strategies. The first category is characterized by the application of a simplification process previously to the surface generation phase. In general, strategies in this group exploit spatial coherence defining coarser representations of the original volume data, just averaging or subsampling neighboring vertices of a given grid into the vertices of a new coarser grid. As the new grid has fewer cubes, the number of facets defining the surface will decrease. However, the new surface may show differences of the surface generated from the original data. Such approaches, combined with adaptive isosurface extraction techniques, are an efficient tool to achieve interactival exploration of volume models. Although, the surface reconstruction process becomes more complex, due to the possible cracks that could appear on the generated surface [MS93,SFY96,OR97,WKE98]. The second group, is characterized by the application of the simplification process on the reconstructed surface, commonly represented as a triangular mesh. Most of the techniques in this group, simplify triangular meshes, either by merging elements or by resampling vertices using different error criteria to measure the fitness of the approximated surfaces [SZL92,Hop96]. The Discretized Marching Cubes (DiscMC) proposed by Montani et al. [MSS94,MSS00] is a surface simplification technique that can be considered midway between the two groups. The DiscMC is a derivation of the MC that replaces the edge interpolation, applied for the vertex polygon computation in the standard MC by a midpoint selection. This simplification reduces the set of vertices that can be generated and implies that the generated facets that define the surface can lie only on a finite number of distinct plane incidences. The ability to merge co-planar elements of this method achieves a high simplification rate. The surface codification we propose exploits the simplifications introduced by the DiscMC.

3. The Octree Surface Codification

The hierarchical structure of octrees has lead this representation scheme a widespread used framework to maintain multiresolution on regular data sets. In the classical octree representation [Sam90] nodes are labeled as black, white or grey. according their position with respect the object being represented. Black nodes correspond to regions completely inside the object. White nodes correspond to regions completely outside the object. White and black nodes are leaves, i.e. they are no further subdivided. Nodes containing part of the surface are labeled as grey and are recursively subdivided. Leaf grey nodes are called terminal grey (TG). In the recent years, several extensions of the octree model have been proposed. One of them is the Extended Octree (EO) model [Nav90]. The EO incorporates new terminal nodes that contain part of the surface object, yielding exact representations for polyhedra and reducing the required storage. In particular, the EO introduces as a terminal nodes: Face nodes (crossed by a single planar face of the solid), Edge nodes (contains part of two neighboring faces and a part of their common edge), Vertex nodes (contains a vertex of the polyhedrom and a part of the faces and edges converging to it) and Nearly Vertex nodes (contains two or more faces that converge to a single vertex outside the node). Driven by the simplification introduced in the DiscMC and by the original MC patters, we propose a variation of the EO to codify the surface. The specific terminal grey nodes of the proposed octree codification are described in next section.

3.1 Characterization of TG Nodes

The selection of the terminal grey nodes has been done according the number and the position of the planes that define the surface contained in an intersected cell (see figure 2).
Let us consider P*={ p_0, p_1,..., p_n} the set of intersection points defining the surface on an intersected cell. These points have been obtined with the DiscMC ( to reduce the complexity of the codification process we apply the DiscMC algorithm instead of the MC). According the position of these polygons this cell can be classified as:

The correspondence between the MC patterns and the five configurations is represented in Table 1. The non intersected node is denoted as Null.
 

Terminal Grey Configuration MC pattern
Face 1, 2, 8, 9
Edge 5
Double Edge 11, 14
Band 3, 4, 6, 7, 10, 13
Special Band 12
Null 0
The  correspondence between terminal grey configuration and the MC patterns

Based on this classification we define as terminal grey nodes those that can be codified as a Face, an Edge, a DoubleEdge, a Band or a SpecialBand (see figure 1).


 

Figure 1: The surface contained in a cell can codified as a Face, an Edge, a DoubleEdge, a Bandn or Band*.
 
 

Figure2: The patterns of the original Marching Cubes. .

3.2 TG Codification

The surface of a terminal grey node n i is codified as {K,(V0,d0), ...,(Vn,dn)}where K represents the class at which the node belongs to (i.e. F, E, DE, Bn or B*)
and  (V0,d0), ...,(Vn,dn) represents the set of plane equations that define the surface. Each couple (Vi,di) corresponds to a ¶i plane where Vi is the normal vector and di
is the distance of the plane to the node's origin. Applying the simplification introduced by the DiscMC, the number of plane incidences is limited, hence, each Vi could be represented as an integer pointer to a pre-computed look-up-table that stores all possible plane incidences. This integer pointer is also used to maintain the information of the inner and outer side of the object (see figure 3). In this form, the codification of the surface is reduced to a set of integers.
 

Figure3: The sign of the integer pointer to the table of planes (+K or -K) points to the inside of the object

4.- Surface Codification Algorithm

The key point of the surface codification algorithm is the application of a simplification strategy that reduces the number of polygons defining the surface. This simplification is based on the detection and merging of coplanar polygons. The algorithm starts with the surface (initially obtained with the DiscMC), codified at maximal subdivision intersected nodes of an octree data structure. We adopt the [WVG92] octree. On a bottom-up traversal of this octree, coplanar polygons are detected and merged.Starting at level n-1, i.e parents of maximal division nodes, the eight descendants of each intersected node n_i are evaluated:

Note that the merging process always starts with a set of eight terminal nodes and the simplification is possible if they can be reduced to a terminal node. As all possible terminal configurations are known, most of the computations required by the merging process are known in advance. Thus, they can be precomputed and stored in a table (the Merging Table). In this manner the merging process is reduced to access to this table.

The Merging Table

The Merging Table (MT) determines when the merging is possible and how has to be done. To generate the MT we have considered all possible combinationsof two terminal nodes and for each pair of configurations the set of resultant terminal configurations that can be generated (see Table 2).
 
 
 

  N F E DE BN B*
N N F E DE BN B*
F F F, E, B2  E,DE,B*  DE BN  B* B*
E E E, DE, B* E, DE NC B* NC
DE DE E, DE, BN  NC DE NC NC
BN BN BN  B* B* NC BN NC
B* B* B* NC NC NC NC

Table2: The Merging Table
 
 

Given a pair of terminal nodes the resultant codification not always can be obtained directly from the table. See for example the (F,F) pair, in this case three possible configurations can be obtained a F, an E or a BN. To select which of these possible codifications correspond to the analyzed pair, a Plane Position test has to
be applied. This test proceeds as follows: plane equations defining the surface contained in the F nodes are evaluated : (i) if the planes are Coplanar the resultant
 configuration is a face; (ii) if the planes are Parallel the resultant configuration is a B2; (iii)  if the planes are Incident and its intersection falls within the parent node
 the resultant configuration is an Edge; and (iv) if the planes are Incident and the intersection does not fall within the parent node the resultant configuration is a B2.

As all the plane equations are codified as pointers to a table of planes, the  Plane Position test is reduced to a set of integer comparisons.

 In figure 4, we have illustrated the application of the merging process to a node n_i, where { n_0,n_1,n_2,..,n_7} and {N,F,N,F,N,F,N,F} represent its codificable child nodes and their configurations.
 


Figure4: The reduction of a set of Face nodes to an Edge. The merging process starts grouping these descendents by pairs (n0,n1),(n2,n3),(n4,n5) and (n6,n7). At this first step the Plane Position test is not applied, the resultant configuration can be obtained from the MT table directly (see Table 2, where (N,F) generates a F). The resultant configurations {F,F,F,F} are grouped again and evaluated. In this case, the Plane Position test has to be applied to select if the pair (F,F) generates a Face, an Edge or a Bandn. As planes intersect into the node, the generated codifications are Edges. Finally, the pair (n0123,n4567) is evaluated. In this case, the (E,E) configurations generate an Edge.

This codification algorithm ends with the surfacerepresented in a set of terminal grey nodes distributed at different levels of the octree.

5.  Surface Reconstruction Algorithm

Once the surface has been codified in the octree, to generate the surface, a surface reconstruction algorithm has to be applied. This algorithm is composed of two steps. The first, traverses in a top-down manner the octree and selects all terminal intersected nodes. The set of selected nodes is represented as S.
The second step, applies a reconstruction process to each node n_i in S.

Before the description of this process some considerations have to be taken into account:
    (i) each plane equation represented in the node has to be represented by one polygon;
    (ii) this polygon is defined from the connection of all or some of the plane-node's edges intersection points.
    (iii) the number of polygons required to define the surface varies with the configuration of the node. In particular, the configuration-polygon relation is F:1, E:2, DE:3, Bn:n and B*:3.

To define the surface of an intersected node n_i we apply the three following steps:

  1.  Intersection Point Computation. On a first step the information of the node  is evaluated and for each plane equation  the plane-node's edges intersection points are computed. The limited number of plane incidences allows the definition of a look-up-table in which the intersection points generated for each plane are stored. Thus, the set of intersection points P_i of each plane  will be obtained directly from this table just applying a translation respect the origin of the n_i node. When the node corresponds to an Edge, a DoubleEdge or a Band* the points defining the generated edges are also computed.(see figures 5(a), 6(a))
  2. Point Selection. Once the intersection points are known, a selection process is applied to determine which of these points are members of the surface. This selection depends of the node's configuration and is done evaluating the signs of the plane equations  (see figure 3) Selected vertex are represented in P*_i (see figures 5(b),6(b)).
  3. Points Connection. Finally, P*_i vertices are connected. To proper ordering (clock-wise or counter clock-wise) these points we follow the order stablished for the intersection point computation. To guarantee the correct connection possible configurations of 4,5 and 6 intersection points have been evaluated and stored in a look-up-table (see figures 5(c),6(c)).

Figure5: The surface information of the nodeis (E,pi_0,pi_1). (a) In a first step the intersection of each plane with the node is computed obtaining: P_0={p_0.p_1,p_2,p_3 } and P_1={ p'_0.p'_1,p'_2,p'_3}. The edge vertices (e_0,e_1) are identified.(b) Point selection is done according the plane signs: pi >0  then p'_0,p'_3 are eliminated ;pi'<0  then p_1,p_2 are eliminated. (c){ p_0,p_3, e_1,e_0 } and {p'_1,p'_2,e_1,e_0} polygons define the surface.
 
 

Figure6: The surface information of the node is (DE,pi_0,pi_1,pi_2). (a) In a first step the intersection of each plane with the node is computed obtaining: P_0={ p_0.p_1,p_2,p_3 } , P_1={ p'_0.p'_1,p'_2,p'_3,p'_4,p'_5} and P_2={ p''_0.p''_1,p''_2,p''_3,p''_4,p''_5}. The edge vertices (e_0,e_1) and (e_0',e_1') are also computed.(b) The signs of the planes are used to select the points on the surface.(c) Intersection point are connected to define the final surface.
 

The error involved in all the surface extraction process is the error introduced by the DiscMC, i.e. an error of 1/2 of the cell size. This reconstruction algorithm can be extended to allow multiresolution renderings. The first step, is substituted by a selection process that selects nodes according to the distance to a focus of interest. The reconstruction step is also modified to reduce the number of polygons that define the surface of non-interesting nodes [BN01].
 

6.  Experimental Results

Four data models have been used for the tests:a CT-vertebra of 128x128x80; a CT-head of 96x96x69;a CT-scanned jaw of 128x128x40 and a sphere of 64x64x64.
The method has been implemented on a Pentium III at 450MHz.

In our tests we have evaluated the degree of simplification that can be achieved with respect to standard MC and the quality of the renderings. In table 3 the comparison of the performance of the proposed simplification algorithm and the original MC in terms of: the number of polygons, the number of intersection points defining the surface and the surface extraction time, are presented. Best results are obtained on the CT-vertebra (see figure 8). In this case the reduction on the number of polygons is 50\%. Despite the simplification on the number of polygons (see figure 7) the quality of the renderings is comparable with the MC renderings.The simplification on the CT-head only achieves 15% of reduction(see figure 9). While in the CT-jaw the reduction is approximately of a 38% (see figure 10). The sphere achieves a reduction of a 35%. Although the execution time is longer than that of the MC, the reduction on the number of polygons will reduce the complexity of posterior operations.

We are conscious of the similarity with the DiscMC algorihtm snd that the degree of simplification of our method is lower than the one obtained with the DiscMC. Despite this similarity, note that in the DiscMC the face merging is performed on all adjacent faces which lie on the same plane. To give in output a triangle-cased representation, it needs to triangulate these merged polygons; but these polygons might be non convex, or can contain holes. Therefore, it adopts an efficient solution for triangulating them on the fly (and thus times are fast, in most cases slightly better than standard MC). A disadvantage of this approach is that it usually produces in output very thin triangles, which can give problems both in rendering and in further geometrical processing of the mesh. Our approach, in contrast is based on a hierarchical approach so, by definition, the merged region should be much more regular (even if in some cases of lower extension than the DiscMC); therefore also the triangulated representation should posses a more regular shape.Moreover, we have to keep in mind that our main objetive is twofold: to reduce the number of polygons defining the surface and to maintain the connection between surface and volume data information.
 

Data set num.polygons num.intersection points time
CT-vert (MC) 13.597 52.755 3,59
CT-vert 7.501 28.637 3,8
CT-head (MC) 33.480 120.629 6,8
CT-head 28.990 104.033 8,4
CT-jaw (MC) 38.491 144.470 8,9
CT-jaw 23.656 86.357 9,83

Table3. Experimental results. All times are in seconds.


 

Figure7: Wire-mesh models of the CT-vertebra before and after the application of the merging process.
 


Figure8: Different views of the CT-vertebra.
 


Figure9: CT-head  Figure10: CT-jaw
 
 
 

7.  Conclusions and Future Work

We have presented a method to codify a surface in an octree data structure. The proposed surface codification is based on the classification of the original MC patterns in five configurations according the position and the number of planes that define the surface contained in an intersected node. Starting with the surface codified at maximal subdivion nodes, we have defined a simplification strategy that detects coplanar polygons and represents them in upper levels of the octree. Such simplification process achieves reductions of almost a 50% on the number of facets with respect to the standard MC. The algorithm to reconstruct the surface of an intersected node has been also described. The main advantages of the proposed codification are that not only reduces the output fragmentation it also maintains the connection between surface and volume data. The proposed codification method is the first step on the definition of an hybrid framework able to maintain multiresolution surface and volume data renderings. Our future work will be centered on multiresolution surface and volume hybrid renderings.

Acknowledgements

This paper was presented in the Spring Conference on Computer Graphics 2001.  The authors would like to thank the valuable comments of the reviewers.
This research has been supported in part by grants TIC98-0630-C03-01 and 2FD97-1511 of the Spanish Government.
 
 
 

References

[BN01] I.Boada and I.Navazo.Multiresolution Isosurface Fitting using an Octree based Surface Hierachy.The 6th International Fall Workshop: Vision, Modeling and Visualization 2001, Sttutgart (21-23 November), pp-??.
[BNS01] I.Boada, I.Navazo and R.Scopigno.Multiresolution Volume Visualization with Texture-based Octree.The Visual Computer, Springer International, 2001 (in press).
[BPS96] C.L. Bajaj, V. Pascucci and D.R. Schikore.Fast Isocontoruing for improved interactivity. In 1996 ACM Symposium on Volume Visualization, pages 39-46.IEEE Computer Society Press, Los Alamitos, CA, October 1996.
[CMM97] P. Cignoni,P. Marno, C.Montani, E.Puppo and R.Scopigno.Speeding up isosurface extraction using interval trees.IEEE Transactions on Visualization and Computer Graphics, 3(2):158-170, 1997.
[CMP96] P. Cignoni, C.Montani, E.Puppo and R.Scopigno.Optimal Isosurface Extraction from Irregular Volume Data.In 1996 Symposium on Volume Visualization, pages 31-49.IEEE Computer Society, IEEE Computer Society Press. Los Alamitos, CA, October 1996.
[CMS98] P.Cignoni, C. Montani and R.Scopigno.A comparison of mesh simplification algorithms. Computer and Graphics 22 (1), pp.37-54, 1998
[Dur88] M.J. Durst. Additional Reference to Marching Cubes (letter).Computer Graphics 22(4), pages 72-74, 1988.
[Dee95] M. Deering.Geometry Compression.In Computer Graphics (SIGGRAPH '95 Proceedings), pages 13-25, 1995.
[ESV96] F. Evans, S. Skiens and A. Varshney.Optimizing triangle strips for fast rendering.In IEEE Visualization 1996, pages 319-326, 1996.
[Hop96] Hugues Hoppe. Progressive Meshes.Computer Graphics (SIGGRAPH 96 Proceedings), 99-108, 1996.
[LC87] W.Lorensen and H.Cline.Marching cubes a high resolution 3D surface construction algorithm, ACM Computer Graphics (Proceedings of SIGGRAPH '87), vol.21, n 4, pp 163-170, 1987.
[LHJ99] E.LaMar, B.Hamman and K.Joy.Multiresolution Techniques for interactive texture-based volume visualization.In IEEE Visualization 99. IEEE CS Press, October 1999.
[LSJ96] Y.Livnat, H.W. Shen and C.R. Johsons. A Near Optimal Isosurface Extraction Algorithm using the Span Space.IEEE Transactions on Visualization and Computer Graphics, 2(1):73-84, 1996.
[Mur95] S.Muraki.Multiscale Volume Representation by a dog wavelet.IEEE Trans. on Visualization and Computer Graphics, 1(2):109:116, June 1995.
[MSS94] C.Montani, R.Scateni and R.Scopigno.Discretized Marching Cubes, in Visualization '94 Proceedings, R.D. Bergeron and A.E.Kaufman, Eds. 1994, pp.281-287, IEEE Computer Society Press.
[MSS94b] C.Montani, R.Scateni and R.Scopigno. A Modified Look-Up-Table for Implicit Disambiguation of Marching Cubes.The Visual Computer 1994, (10) pp.353-355, IEEE Computer Society Press.
[MSS00] C.Montani, R.Scateni and R.Scopigno.Decreasing Isosurface Complexity via Discrete Fitting, Computer Aided Geometric Design, 17 (2000) 207-232.
[MS93] H.Mueller and M.Stark. Adaptive Generation of Surface in Volume Data.The Visual Computer 9 (4), 182-199.
[Nav90] I.Navazo. Extended Octree Representation of General Solids with Plane Faces: Model Structure and Algorithms, Computer and Graphcics, vol 13, 1, 1989, pp.5-16.
[OR97] M.Ohlberger and M. Rumpf. Hierarchical and Adaptative Visualization on Nested Grids. Computing , 59(4), pages 269-285, 1997
[Sam90] H.Samet. Applications of Spatial Data Structures.Addison Wesley, Reading, MA, 1990.
[SZL92] W.Schroeder, J.A.Zarge and W.E. Lorensen.Decimation of Triangle Meshes.Proceedings SIGGRAPH 92, 65-70, 1992.
[SFY96] R.Shekhar, E.Fayyad, R.Yagel and J.Cornhill. Octree based Decimation of Marching Cubes surfaces.Visualization 96, 335-342, 1996.
[SHL96] H.W. Shen, C.Hansen, Y.Livnat and C.R.Johson. Isosurfacing in Span Space with Ulmost Efficiency (ISSUE).Proceedings IEEE Visualization 96, 287-294, 1996.
[VGW94] A.Van Gelder and J. Wilhems. Topological Considerations on Isosurface Generation. ACM Transactions on Graphics, 13(4). 337-375, October 1994.
[Wes94] R.Westemann. A Multiresolution Framework for Volume Rendering.In Proceedings of 1994 Sysmposium on Volume Visualization, pp. 51-58. ACM Press October 17-18 1994
[WKE98] R.Westemann, L.Kobbalt and T.Erl. Real-time exploration of Regular Volume Data by Adaptative Reconstruction of Isosurfaces. The Visual Computing 1998

[WVG92] J. Wilhems and A. Van Gelder.Octrees for Faster Isosurface generation. ACM Transactions on Graphics, 11(3). 201-227, July 1992.
[WVG94] J.Wilhems and A. Van Gelder. Multi-dimensional Trees for Controlled Volume Rendering and Compression. In proceedings of 1994 Symposium on Volume Visualization, pp 27-34. ACM Press, October 17-18 1994.
[WWHZE00] M. Weiler, R. Westermann, C. Hansen, K. Zimmerman, T.Ertl: Level-of-Detail Volume Rendering via 3D Textures.In Volume Visualization and Graphics Symposium 2000, pp.7-13, 2000.

Computer Graphics & Geometry