Subscribe Now Subscribe Today
Research Article
 

A New Method on Voxelizing Triangular Mesh Model



Ji Jia, Zheng Qin and Junying Chen
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
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.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Ji Jia, Zheng Qin and Junying Chen, 2007. A New Method on Voxelizing Triangular Mesh Model. Information Technology Journal, 6: 1286-1289.

DOI: 10.3923/itj.2007.1286.1289

URL: https://scialert.net/abstract/?doi=itj.2007.1286.1289

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 B-Rep etc. It can describe the internal structure and the organization information, for example density, material, temperature and so on. It is the extension of two-dimensional pixel to three-dimensional space (Eisemann and Décoret, 2006; Kaufman et al., 1993; Wu et al., 2004a). Therefore, a new visualization technique named as three-dimensional visualization technique for solid is applied to a number of domains, such as computer graphic, CAD and finite-element 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 (Cohen-Or 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 scale-space theory to obtain voxelized models which are based upon anti-aliased 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 real-time, 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 sub-nodes.

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 sub-nodes, 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 labeled-1, 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.

Image for - A New Method on Voxelizing Triangular Mesh Model
Fig. 1: Decompose space to eight completely same subspaces

Image for - A New Method on Voxelizing Triangular Mesh Model
Fig. 2: The six faces of each voxel unit can be marked with number 0-5

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.

Image for - A New Method on Voxelizing Triangular Mesh Model
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 non-completed 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

  1. Breen, D.E., S. Mauch and R. Whitaker, 2000. 3D scan conversion of csg models into distance, closest-point and colour volumes. Vol. Graphics, pp: 135-158.


  2. Cohen-or, D. and A. Kaufman, 1997. 3D line voxelization and connectivity control. IEEE CG Appiled, 17: 80-87.
    Direct Link  |  


  3. Dachille, F. and A. Kaufman, 2000. Incremental triangle voxelization. Proc. Graphics Interface, pp: 205-212.


  4. Dong, Z., W. Chen, H. Bao, H. Zhang and Q. Peng, 2004. Real-time voxelization for complex polygonal models. Proceedings of the 12th Pacific Conference on Computer Graphics and Applications (PG'04), October 6-8, 2004, Hangzhou, Chinapp, pp: 43-50
    CrossRef  |  


  5. Eisemann, E. and X. Decoret, 2006. Fast scene voxelization and applications. Proceedings of the Symposium on Interactive 3D Graphics and Games, March 14-17, 2006, Redwood City, Californiapp, pp: 71-78
    Direct Link  |  


  6. 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 9-10, 2000, Salt Lake City, Utah, pp: 43-48
    Direct Link  |  


  7. Haumont, D. and N. Warzee, 2002. Complete polygonal scene voxelization. ACM J. Graphics Tools, 7: 27-42.
    Direct Link  |  


  8. 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 19-20, 1998, Chapel Hill, North Carolina, USA., pp: 119-126
    Direct Link  |  


  9. Jones, M.W., 1996. The production of volume data from triangular meshes using voxelisation. Comput. Graphics Forum., 15: 311-318.
    Direct Link  |  


  10. 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


  11. Kaufman, A. and E. Shimony, 1986. 3D scan-conversion algorithms for voxel-based graphics. Proceedings of ACM Workshop on Interactive 3D Graphics, October 23-24, 1986, Chapel Hill, North Carolina, pp: 45-76
    Direct Link  |  


  12. Kaufman, A., 1987. Efficient algorithms for 3d scan-conversion 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: 171-179
    CrossRef  |  Direct Link  |  


  13. Kaufman, A., D. Cohen and R. Yagel, 1993. Volume graphics. Computer, 26: 51-64.
    Direct Link  |  


  14. Oomes, S., P. Snoeren and T. Dijkstra, 1997. 3d shape representation: Transforming polygons into voxels. Proceedings of the 1st International Conference on Scale-Space Theory in Computer Vision, July 2-4, 1997, Springer Verlag, pp: 349-352
    Direct Link  |  


  15. Sramek, M. and A. Kaufman, 1999. Alias-free voxelization of geometric objects. IEEE Trans. Visualizat. CG, 5: 251-267.
    Direct Link  |  


  16. Wang, S. and A. Kaufman, 1993. Volume sampled voxelization of geometric primitives. Proceedings of the 4th Conference on Visualization, October 25-29, 1993, San Jose, California, pp: 78-84
    Direct Link  |  


  17. 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 8-13, 2003, Irbid, Jordan, pp: 116-120
    CrossRef  |  


  18. 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: 592-597.


  19. 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: 270-275.
    Direct Link  |  


©  2022 Science Alert. All Rights Reserved