亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        An Algorithm for Voxelizing Non—manifold Triangle Geometry

        2018-04-12 10:08:54ZHANGLu-pengJIAShi-yuWANGJi-qiang
        科技視界 2018年10期
        關(guān)鍵詞:中圖標(biāo)識碼分類號

        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

        中圖分類號: TP391.9 文獻(xiàn)標(biāo)識碼: A 文章編號: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頁) (上接第83頁)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.

        猜你喜歡
        中圖標(biāo)識碼分類號
        The Tragic Color of the Old Man and the Sea
        Connection of Learning and Teaching from Junior to Senior
        English Language Teaching in Yunann Province: Opportunities & Challenges
        A Study of Chinese College Athletes’ English Learning
        A Study on the Change and Developmentof English Vocabulary
        Translation on Deixis in English and Chinese
        Process Mineralogy of a Low Grade Ag-Pb-Zn-CaF2 Sulphide Ore and Its Implications for Mineral Processing
        Study on the Degradation and Synergistic/antagonistic Antioxidizing Mechanism of Phenolic/aminic Antioxidants and Their Combinations
        潤滑油(2014年3期)2014-11-07 14:30:02
        A Comparative Study of HER2 Detection in Gastroscopic and Surgical Specimens of Gastric Carcinoma
        The law of exercise applies on individual behavior change development
        国产成人精品亚洲日本在线观看| 国产一区不卡视频在线| 久久精品亚洲一区二区三区画质 | 精品国际久久久久999波多野| 亚洲国产另类久久久精品黑人| 久久中文字幕日韩无码视频| 国产福利一区二区三区在线观看 | 中文字幕人妻乱码在线| 一区二区三区中文字幕p站| 欧美另类高清zo欧美| 97精品国产91久久久久久久| 亚洲av熟女天堂久久天堂| 在线无码中文字幕一区| 美丽的熟妇中文字幕| 99久久久国产精品丝袜| 日本视频一区二区三区在线| 亚洲无线码一区二区三区| 久久国产36精品色熟妇| 被驯服人妻中文字幕日本| 精品国产亚洲级一区二区| 国产亚洲精品久久久ai换| 女人体免费一区二区| 国产主播一区二区三区在线观看| 日本熟妇人妻xxxx| 久久久久亚洲av无码a片软件| 亚洲在战AV极品无码| 风韵人妻丰满熟妇老熟女视频| 亚洲精品熟女国产| 亚洲av日韩av综合aⅴxxx| 美女性色av一区二区三区| 色狠狠色狠狠综合天天| 免费特级黄毛片| 日本一区二区三区在线观看免费 | 亚洲av永久无码精品成人| 亚洲国产精品婷婷久久| 被黑人猛躁10次高潮视频| 98精品国产综合久久| 国产精品麻豆一区二区三区| 日韩av无码中文无码电影| 国产精品黄网站免费观看| 精品在线视频免费在线观看视频 |