
Research Article


A New Method on Voxelizing Triangular Mesh Model 

Ji Jia,
Zheng Qin
and
Junying Chen



ABSTRACT

In this study, we propose a method for voxelizing triangular mesh model based on space partitioning and octree encoding. It describes the 3D model by octree structure and then processes it with both surface voxelization and internal voxelization to generate volume model. Our experimental results show that the method can voxelize 3D polygon meshes correctly and effectively.





INTRODUCTION
In the recent 20 years, volume models are becoming important in a number of disciplines, including medicine visualization, material information modeling, CAD and manufacture (Dong et al., 2004; Eisemann and Décoret, 2006; Wu et al., 2004b). Volume model is 3D solid model by information encoding which is different from traditional graphical presentation based on surface, such as CSG and BRep etc. It can describe the internal structure and the organization information, for example density, material, temperature and so on. It is the extension of twodimensional pixel to threedimensional space (Eisemann and Décoret, 2006; Kaufman et al., 1993; Wu et al., 2004a). Therefore, a new visualization technique named as threedimensional visualization technique for solid is applied to a number of domains, such as computer graphic, CAD and finiteelement analysis, in order to describe the internal feature of a solid model. The volumetric representation provides a uniform, simple and robust description to synthetic and measured objects and founds the basis of volume graphics (Kaufman et al., 1993).
Conceptually, a reformulation process is required to generate volumetric representation from geometric object. This stage is typically called voxelization (Dong et al., 2004). The voxelization can be classified as surface voxelization (Dachille and Kaufman, 2000; Huang et al., 1998) and solid voxelization methods (Haumont and Warzee, 2002; Sramek and Kaufman, 1999). There are a number of methods for line (CohenOr and Kaufman, 1997), triangle (Dachille and Kaufman, 2000), polygon (Jones, 1996; Kaufman and Shimony, 1986; Wang and Kaufman, 1993), CSG (Breen et al., 2000; Fang and Liao, 2000), parametric surface (Kaufman, 1987; Sramek and Kaufman, 1999) and implicit surface voxelization. The voxelization in this study is a main step to transform a mesh model to a solid model, so that the voxelization method must be efficient and precise. There are various voxelization methods, they have advantages and drawbacks. Eisemann and Decoret (2006) dynamically calculate scene presentation based on voxel by using graphical hardware. Oomes et al. (1997) utilize the scalespace theory to obtain voxelized models which are based upon antialiased of points, lines and surfaces. Dong et al. (2004) research and implement a voxelization method by using programmable graphical hardware, which focuses on complex polygon models. Huang et al. (1998) transform discreetly polygon mesh model to voxelization model with normal vector function of each surface. Jones and Satherley (2000) propose a voxelization theory based on Distance Fields and Distance Transform. All the methods above could be implemented by graphics workstation which needs high level hardware (for example GUP and special graphics workstation). Wu et al. (2003) describe an octree based method to voxelize the mesh to volume model. This paper introduced a voxelization method by referencing and improving the method in Wu et al. (2003). Firstly, we voxelize the surface, including voxelization of points, lines and faces. Then we process flood algorithm to internally voxelize. Finally, the polygon meshes are transformed to voxelized models. The experimental results show that our method could be realtime, accurate and efficient on light workstation such as notebook and PC platform.
METHOD OF VOXELIZING TRIANGULAR MESH MODEL
Space partition and octree coding: Octree is a kind of tree data structures
to describe 3D object, widely used in computer graphic, computer vision, visualization
and image process. Every node of octree identifies a square volume element and
consists of 8 subnodes.
The principle of octree is space partition, which means continuously decompose space to eight completely same subspaces, shown as Fig. 1, unless the subspace is single attribute.
Octree could be distinguished as traditional octree and linear octree. Every traditional octree node records ten values, which are eight pointers point to subnodes, the other two are parent pointer and attribute. In contrast, linear octree only records address code and attribute of every leaf node. Therefore, linear octree could save space and support directly addressing and encoding node by calculating its coordinate. There are efficient encoding solutions, as Meagher mentioned in Wu et al. (2003), using less coding to completely present octree and transform among voxel coordinate, encoding and 3D coordinate. Also, all combinations of six numbers are used as indices, which drive the adjacent search for octree and accelerate going to the correct voxel unit quickly (Fig. 2).
For triangle mesh model, we firstly calculate the bounding box and then set the minim vertex as the origin to establish the voxelization coordinate system. Next, we partition the region of bounding box using the space partition based approach and establish corresponding octree structure. Finally, we voxelize the surface and inside based upon vertices, lines and faces.
Surface voxelization: First of all, we introduce three attributes for voxel. If a voxel is labeled1, it means that the voxel is outside the model. In the same way, label zero means on the boundary and label 1 means inside the model. According to the attributes, we give two definitions:
An original cell is a boundary voxel (with label plus one) if and only if one of these neighbors is not a voxel with a positive label.
An original cell is an internal voxel (with label minus one) if and only if all the neighbors are not null.
The voxelization procedure for 3D polygon model is to revise every voxels whether they are boundary or internal voxels by modifying the attributes of every octree nodes. It includes voxelization of vertices, edges and face for every triangle surface.
When processing vertices voxelization for a given triangle surface, we transform
the traditional 3D coordinates to voxel coordinates first. Then, the voxel coordinates
are encoded in order to find the voxel cell and the voxel`s attribute is set
zero, which means a potential boundary voxel.
When handling edges voxelization for the triangle surface, we trace the edge
from the start point to end point with Bresenham algorithm to find all voxels
passed through by the edge.

Fig. 1: 
Decompose space to eight completely same subspaces 

Fig. 2: 
The six faces of each voxel unit can be marked with number
05 
It is distinctly that the voxel of the start point is intersected with the
edge. According to the voxel coordinates and the index of the intersectional
point, we can find the next boundary voxel need to label zero. Particularly,
the edges with special position need more attention, such as the parallel edges
and the upright edges.
When doing surface voxelization, we use the projection mechanism. Firstly,
the maximal component of normal vector is selected and then we project the surface
along the component. For example, if y component is maximal of the surface normal,
the surface will project onto XOZ plane. Next, we find the minimum and maximum
voxel from each direction of the projection plane, for example, the minimum
and maximum voxeles of X direction and Z direction.

Fig. 3: 
Voxelization results 
For every fixed x, we find the corresponding minimum and maximum voxel though
z direction. But the current x and y may not be exact boundary voxel coordinates,
the accurate coordinate of y component need to be calculate according to the
coordinate value of x, z component and the plane equation of triangle face.
Internal voxelization: In the study, we introduce Flooding operator (Huang et al., 1998) to voxelize the internal part of a model. We testify the attribute of every neighbor. If it is labeled minus one, the neighbor voxel is outside the model. As a result, all the outer voxels could be distinguished and the internal part, boundary and external part of the model can be distinguished too.
As characteristics of the model and the discrete results when voxelizing surface, the flooding operator should be small fault. For instance, the internal voxel is affected by external voxel to be false attribute as an external voxel. In this study, we improve the traditional flooding operator. If the voxel only affect less than N of the six neighbors (N is the threshold), the effects are rolled back, which means to reserve the original attributes of all six neighbors. The purpose of this improvement is to reducing the affection of the internal voxels caused by flooding operator.
To summarize, the key improvements of voxelizing polygon model are list as follows:
• 
Solution to edge voxelization with special position such as
the edge that parallels a coordinate plane. 
• 
When voxelizing surface, we respectively projection the surface
to XOZ, ZOY and YOX planes, which replaces the method in Wu et al.
(2003) that only project to the coordinate plane with maximum projection
area. Maximum projection area based method leads to noncompleted voxelization,
which may cause null space among the surface and will affect the result
of internal voxelization. 
EXPERIMENT AND RESULT
Here, we evaluated the effectiveness of our method on PC with Pentium 1.73 GHz. The voxelization results are visually shown as Fig. 3, the 1, 2 and 3 columns are results of boundary voxels, while the 4, 5 and 6 columns are final results with distinguished internal voxels and boundary voxels with red and blue colors.
CONCLUSION
In this study, we have described a method for voxelizing polygon meshes. The methodology we used is based on space partition and octree encoding. Our method firstly voxelize the surface, including vertices, edges and triangle planes. Then we voxelize the internal parts of the model using improved flooding operator. After distinguishing the internal part and the external part, we finally obtain the volume model. The experimental results show that our method can transform mesh model to voxelized model correctly and effectively. We believe that voxelized model is of considerable importance for 3D model processing and more research is definitely needed to investigate other approaches.
Currently, this method has been applied to 3D model processing system of the project of National Grand Fundamental Research 973 Program of China. Possible future directions involve voxelizing 3D mesh model more quickly.
ACKNOWLEDGMENTS
We gratefully acknowledge the support of the National Basic Research Program of China (973 Program) under Grant No. 2004CB719401 and the National Natural Science Foundation of China under Grant No. 60542004.
We would like to thank the members in the 973 Intelligent Design team. Supplemental support from the members of the EC institute of Xi’an Jiaotong University is acknowledged. We also thank the anonymous reviewers of this paper for their making many valuable comments.

REFERENCES 
Breen, D.E., S. Mauch and R. Whitaker, 2000. 3D scan conversion of csg models into distance, closestpoint and colour volumes. Vol. Graphics, pp: 135158.
Cohenor, D. and A. Kaufman, 1997. 3D line voxelization and connectivity control. IEEE CG Appiled, 17: 8087. Direct Link 
Dachille, F. and A. Kaufman, 2000. Incremental triangle voxelization. Proc. Graphics Interface, pp: 205212.
Dong, Z., W. Chen, H. Bao, H. Zhang and Q. Peng, 2004. Realtime voxelization for complex polygonal models. Proceedings of the 12th Pacific Conference on Computer Graphics and Applications (PG'04), October 68, 2004, Hangzhou, Chinapp, pp: 4350 CrossRef 
Eisemann, E. and X. Decoret, 2006. Fast scene voxelization and applications. Proceedings of the Symposium on Interactive 3D Graphics and Games, March 1417, 2006, Redwood City, Californiapp, pp: 7178 Direct Link 
Fang, S. and D. Liao, 2000. Fast csg voxelization by frame buffer pixel mapping. Proceedings of the ACM/IEEE Volume Visualization and Graphics Symposium, October 910, 2000, Salt Lake City, Utah, pp: 4348 Direct Link 
Haumont, D. and N. Warzee, 2002. Complete polygonal scene voxelization. ACM J. Graphics Tools, 7: 2742. Direct Link 
Huang, J., R. Yagel, V. Filippov and Y. Kurzion, 1998. An accurate method for voxelizing polygon meshes. Proceedings of the Symposium on Volume Visualization, October 1920, 1998, Chapel Hill, North Carolina, USA., pp: 119126 Direct Link 
Jones, M.W., 1996. The production of volume data from triangular meshes using voxelisation. Comput. Graphics Forum., 15: 311318. Direct Link 
Jones, M.W. and R. Satherley, 2000. Voxelisation. In: Modelling for Volume Graphics, Girod, B., G. Greiner, H. Niemann and H.P. Seidel (Eds.). IOS Press USA
Kaufman, A. and E. Shimony, 1986. 3D scanconversion algorithms for voxelbased graphics. Proceedings of ACM Workshop on Interactive 3D Graphics, October 2324, 1986, Chapel Hill, North Carolina, pp: 4576 Direct Link 
Kaufman, A., 1987. Efficient algorithms for 3d scanconversion of parametric curves, surfaces and volumes. Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, Volume 21, July 1987, New York, USA., pp: 171179 CrossRef  Direct Link 
Kaufman, A., D. Cohen and R. Yagel, 1993. Volume graphics. Computer, 26: 5164. Direct Link 
Oomes, S., P. Snoeren and T. Dijkstra, 1997. 3d shape representation: Transforming polygons into voxels. Proceedings of the 1st International Conference on ScaleSpace Theory in Computer Vision, July 24, 1997, Springer Verlag, pp: 349352 Direct Link 
Sramek, M. and A. Kaufman, 1999. Aliasfree voxelization of geometric objects. IEEE Trans. Visualizat. CG, 5: 251267. Direct Link 
Wang, S. and A. Kaufman, 1993. Volume sampled voxelization of geometric primitives. Proceedings of the 4th Conference on Visualization, October 2529, 1993, San Jose, California, pp: 7884 Direct Link 
Wu, X., W. Liu and T. Wang, 2003. A new method on converting polygonal meshes to volumetric datasets. Proceedings of the International Conference on Robotics, Intelligent Systems and Signal Processing, October 813, 2003, Irbid, Jordan, pp: 116120 CrossRef 
Wu, X., W. Liu, T. Wang and P. Wen, 2004. Modified polygonal mesh voxelization based on euclidean distance measurement. J. Comput. Aided Design Comput. Graphics, 16: 592597.
Wu, X.J., W.J. Liu and T.R. Wang, 2004. Functionally graded material modeling based on 3d voxel models. Comput. Integrated Manuf. Syst., 10: 270275. Direct Link 



