An Algorithm for Voxelizing Non—manifold Triangle Geometry

ZHANG Lu-peng　JIA Shi-yu　WANG Ji-qiang

（1.College of Computer Science and Technology，Qingdao University，Qingdao 266071，China；

2.College of Computer Science and Technology，Qingdao University，Qingdao 266071，China；

3.College of Computer Science and Technology，Qingdao University，Qingdao 266071，China）

【Abstract】Taking advantage of the characteristic of distance field and octree， we brought up a method which can discrete any triangle-geometry into voxel.As many triangles used for cutting simulation are unoriented，non-manifold or self-intersecting， which leads to ambiguity in mathematical terms. The algorithm firstly computes sign distance field and use the threshold value to reconstruct the surface，which is very close to the original mode.At last，the reconstructed surface is voxelized. Also we can produce voxelized model which is suitable for cutting simulation.

【Key words】Distance field；Octree；Non-manifold；Self-intersecting；Triangle-geometry；Voxelization

中圖分類號(hào)： TP391.9 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)：2095-2457（2018）04-0082-002

0 Introduction

In medical simulation， surgery simulation is a process， which realistically simulate that human organs are distorted even cut and other operations under the interaction of external force. Our algorithm defines the internal and external points of the model in the pure mathematical sense， and fill the holes on the model by using distance fields and surface reconstruction algorithm. Then， we voxelize the model to produce voxelized model which is suitable for cutting simulation.

1 Voxelization Algorithm

1.1 Compute Distance Field

Distance field is a scalar field that represents the minimum distance from each point to the nearest point on the object. Distance fields can be signed， and the sign specifying whether the query point is internal or external to the model， which mathematical definition is：

dist（x，Ω）=inf||‖p-x‖（x∈R3，p∈Ω）（1）

where the function represents the unsigned distance field from point x to model Ω， and p is a point on the surface mesh. Signed distance fields is based on distance fields， the sign of the point inside the mesh is determined to be negative and the sign of the point outside the mesh is positive. If σ denotes the interior of model Ω， we can define

φ（x）=sgn（x）inf‖ax-x‖（2）

Then，ax∈Ω，sgn（x）=-1 x∈σ1 otherwise

1.1.1 Extract Unsigned Distance Field

The model space should be divided before computing unsigned distance field[1]. First， use a bounding box that parallel to the axes to surround the input mesh. According to the offset σ of distance fields， we can expand the bounding box to generate sample space. For the sample space， we divided it evenly by using defined resolution h， and divide the bounding box evenly with a fixed value.

Calculate the minimum distance and the maximum distance for each sample point to the bounding box cube， and set lowest value of the maximum distance as a reference value of the minimum distance from sample point to triangle mesh. And then traverse all cubes. Eventually we get unsigned distance fields， use it as input， and use marching cubes algorithm to generate an offset manifold surface， which we can define

Sσ={X∈R3|dU（X，Ω）=σ}（3）

Offset surface may be nested：

（4）

Where Eare connected components that are not enclosed by any exterior components， and I are all the interior components. Note that ∪ denotes the “disjoint union”. Because the interior components need to be removed， we ？rst use union-find to detect all the connected components of . Once we know the surface is type I， we can remove it. At the end of this process， we have identified all surfaces of type E， that is the offset surface.

1.1.2 Calculate Signed Distance Field

Currently， we have the manifold exterior offset surface and the unsigned distance fields of input geometry， which obtained through calculating. One could now compute a signed distance field for Eσ， using the pseudonormal test. We take advantage of the following two lemmas that are proved by Hongyi Xu[2].

（1）If X is a point in the exterior region of ， then the signed distance equals

dS（X，Eσ）=dU（X，Ω）-σ≥0（5）

（2）If a point X satisfies dx（X，Ω）<σ， then X must be in the interior of.

We first divide the offset surface evenly， and tag all the cubes which intersect the offset surface as boundary by boundary detection. Next， we perform a S-shaped traversal over all the grid points， so that we can determine the sign of each grid points. At the end， we can offset the signed distance field that we compute by-σ， producing the nal signed distance field relative to input triangle mesh.

1.2 Repair Reconstructed Surface

The ultimate goal of this paper is to realize the voxelization of arbitrary triangular geometry. After computing the signed distance field， perform marching cubes algorithm to produce reconstructed surface of input mesh. As shown by the Stanford rabbit in Figure 1.

Figure1 Stanford Rabbit Offset Surface

However， not all non-manifold geometries are close to manifold. When a non-manifold geometry is composed of many disconnected triangles， the first reconstructed surface is not enough to voxelize. As shown by palm in the Figure 2.

Figure2 Palm Offset Surface

To solve the above issue， we perform repair operations based on the existing reconstructed surface. We know that reconstructed surface Fσ is produced by marching cubes algorithm， which uses signed distance field as iso-surface. When the input triangle geometry is disconnected， distance fields is also disconnected due to exact signed distance field that we compute. For above reason， reconstruct surface is not ideal， and now the exact signed distance field is defined as：

dU（X，Ω）=σ σ-0（6）

When all the input triangle geometries can be covered by signed distance fields， reconstructed surface is good enough to voxelize， so we need to realize covering by adjust the offset.

dU（X，Ω）=σ+δ（7）

The adjusted offset σ need to be entered by the user， after adjusting the distance fields， use marching cubes algorithm to rebuild a closed manifold surface.

1.3 Voxelize Model

Our remaining task is to voxelize the closed manifold surface. Compute a tight bounding box for reconstructed surface， and now bounding box space can be called voxel space V3. For each voxel， only a set of integer sequences （l，j，k）fix its position. After the voxel space is determined， divide it based on the octree[4]. Generally， the octree division method only divides the gray nodes. In this paper， all three nodes are divided to generate a uniform voxel grid， and the voxel sign：

f（i，j，k）=-1 voxels outside the boundary 0 voxels inside the boundary 1 voxels on the boundary（8）

Finally， we use progressive scanning to distinguish between interior and external data. At the end of scanning， volume data is known， and voxelization is finished.

2 Result

In order to verify the effectiveness of algorithm， we compared the voxelizing result between spatial partition algorithm and ours. The essence of voxelization algorithm based on spatial partition is that adopt a fast distance field computation method that is proposed by MIN[3] based on spatial partition， and reconstruct surface and voxelize. Our experiments were performed on an Intel（R） Core（TM） i7-3770 CPU @ 3.40GHz （8 cores） machine with 12GB RAM， and a GeForce GTX 750Ti graphics card with 2GB RAM.

Table1 Model Parameters and Distance Field Calculation Result

Table 1 gives the performance of our unsigned and signed distance field computation on three non-manifold meshes. Figure 3 shows the distance field results for the three models that include self-intersections， disconnected geometry and holes. Our algorithm solves the problem of calculating the signed distance field for non-manifold geometry with precise and ultra-thin features

In Figure 3， palm model shows different voxelization effects on our algorithm and voxelizing algorithm based on spatial partition. After repairing the reconstructed surface， our algorithm performs better on voxelizing input triangular meshes that include self-intersections and（下轉(zhuǎn)第95頁(yè)） （上接第83頁(yè)）disconnected geometry，and the voxel model is more close to the original model.

Figure3 Voxelization Effects Comparison

3 Conclusion

We presented a robust and accurate approach to voxelize any input geometry and solved the problem how to voxelize non-manifold geometry. Using surface repair to improve the shortcoming that the offset surface of “triangle soup” that is reconstructed with exact distance field is disconnected. The experimental results show that our algorithm performs better than voxelizing algorithm based on spatial partition.

【Reference】

[1]Nooruddin F S， Turk G. Simplification and repair of polygonal models using volumetric techniques[J].IEEE Transactions on Visualization and Computer Graphics， 2003， 9（2）： 191-205.

[2]Xu H， Barbic J. Signed distance fields for polygon soup meshes[C]//Proceedings of Graphics Interface 2014. Canadian Information Processing Society， 2014： 35-41.

[3]MIN D， JIA S， ZHANG X. Multi-threaded Fast Distance Field Computation Using Spatial Partition[J]. Science & Technology Vision， 2015， 8： 117.

[4]Meagher D.Geometric modeling using octree encoding[J]. Computer graphics and image processing，1982，19（2）：129-147.