亚洲免费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
        日韩av一区二区三区在线观看| 无遮挡又黄又刺激又爽的视频| 亚洲暴爽av天天爽日日碰| 亚洲国产精品久久九色| 国产精品自拍网站在线| 午夜福利理论片在线观看播放| 狠狠色噜噜狠狠狠狠米奇777| 青青在线精品2022国产| 人妻尤物娇呻雪白丰挺| 日本一区二区三区人妻| 日本最大色倩网站www| 99视频一区| 五月婷婷激情六月开心| av免费在线播放视频| 我把护士日出水了视频90分钟| 国产精品二区在线观看| 亚洲av乱码一区二区三区女同| 高清日韩av在线免费观看| 日韩欧美成人免费观看| 三上悠亚免费一区二区在线| 精品蜜桃一区二区三区| 日本伦理精品一区二区三区| 精品国产一区av天美传媒| 四虎成人精品无码永久在线| 亚洲精品中文字幕乱码三区99| 天堂8在线新版官网| 99久久99久久精品国产片果冻| 国产精品亚洲ΑV天堂无码| 国产色av一区二区三区| а√天堂资源官网在线资源| chinesefreexxxx国产麻豆| av网站影片在线观看| 亚洲av专区国产一区| 成人精品视频一区二区| 国内精品久久久久久久久齐齐| 国产精品狼人久久久影院| 偷拍一区二区三区四区视频| 粗大的内捧猛烈进出视频| 国产亚洲欧美在线| 69精品人妻一区二区| 第一次处破女18分钟高清|