凸包構(gòu)造與碰撞檢測的優(yōu)化研究
發(fā)布時間：2018-07-20 09:14
【摘要】：碰撞檢測是物理仿真、路徑規(guī)劃、虛擬裝配及觸覺渲染等諸多計算機科學(xué)領(lǐng)域內(nèi)的一類基礎(chǔ)問題,至今已有許多解決該問題的算法被提出,然而這些算法各有優(yōu)劣。例如V-Clip算法、Lin-Canny算法、GJK算法都將多面體視為凸體對象,因此對于凹多面體,需要通過構(gòu)造凸包來轉(zhuǎn)化為凸體對象。而且當(dāng)具體到實際應(yīng)用中時,還會遇到一些其他挑戰(zhàn):例如觸覺渲染要求極高的刷新率;精密零件的虛擬裝配不但需要算法能夠快速得到結(jié)果,而且對結(jié)果的準(zhǔn)確性要求也很高,因此根據(jù)實際應(yīng)用環(huán)境對已有的凸包構(gòu)造算法和碰撞檢測算法進行優(yōu)化改進是一個值得研究的領(lǐng)域,具有理論意義與實際工程價值。本論文以剛性的基于三角形圖元的機械表精密零件模型作為研究對象,論述了凸包構(gòu)造和碰撞檢測兩個階段的相關(guān)問題。本文主要進行的工作及成果如下:1.研究了凸包的性質(zhì),并在此基礎(chǔ)上對三維空間的卷包裹(Gift-Wrapping)算法和快速凸包(QuickHull)算法的基本思想和計算復(fù)雜度進行了論述,重點討論了快包法的優(yōu)缺點,并由此提出了一種改進的三維點集凸包構(gòu)造算法,該算法通過優(yōu)先考慮與凸包頂點共面的其他頂點,避免中間面的產(chǎn)生,減少最終構(gòu)成凸包的圖元數(shù)量。本文使用該算法構(gòu)造零件模型的凸包,利用凸包加快包圍體的構(gòu)造,并實現(xiàn)機械表零件與夾具及環(huán)境的快速碰撞檢測和仿真。2.研究了碰撞檢測全局階段的N-體剔除方法:包圍體樹、空間剖分以及拓?fù)浞?并討論了各自的適用場景。在拓?fù)浞ㄖ?我們重點分析了最著名的掃掠剪除(SaP)算法以及其各類變種的優(yōu)缺點和執(zhí)行效率,并提出一種基于樣本估計的SaP優(yōu)化算法,該算法通過樣本估計動態(tài)選擇離散排序軸,降低了大型場景中模型積聚和模型規(guī)模變化對實時性的負(fù)面影響。實驗結(jié)果表明新算法的性能優(yōu)于其他同類算法,且能夠適應(yīng)各種場景環(huán)境,其適用性更廣。3.研究了碰撞檢測局部階段的精確相交測試方法,針對現(xiàn)有包圍體樹算法的實時性不足、對機械表裝配場景的適用性不佳的問題,本文提出一種改進的混合包圍體樹算法,該算法在創(chuàng)建樹節(jié)點時使用了多個相關(guān)包圍體,并對樹的構(gòu)造方式進行修改,從而對零件模型間的相交狀態(tài)可以更加精確高效的檢測。我們還對如何優(yōu)化內(nèi)存占用進行了討論。4.利用Unity3D引擎實現(xiàn)了機械表虛擬裝配系統(tǒng),并以系統(tǒng)的場景為模板構(gòu)造實驗環(huán)境,以碰撞檢測算法的運行時間、準(zhǔn)確性以及綜合性能幾個方面為考察目標(biāo),設(shè)計了兩個算法對比實驗。通過分析與傳統(tǒng)算法的對比實驗結(jié)果,驗證了本文提出的SSVs混合包圍體樹算法在性能上優(yōu)于傳統(tǒng)算法。
[Abstract]:Collision detection is a basic problem in many fields of computer science, such as physical simulation, path planning, virtual assembly and tactile rendering. So far, many algorithms have been proposed to solve the problem, but these algorithms have their own advantages and disadvantages. For example, V-Clip algorithm / Lin-Canny algorithm / GJK algorithm regards polyhedron as convex object, so concave polyhedron needs to be transformed into convex object by constructing convex hull. And when it comes to practical applications, there are other challenges: for example, tactile rendering requires a very high refresh rate, and virtual assembly of precision parts requires not only fast algorithms to get results, Moreover, the accuracy of the results is very high. Therefore, the optimization and improvement of the existing convex hull construction algorithm and collision detection algorithm according to the practical application environment is an area worthy of study, which has theoretical significance and practical engineering value. In this paper, the rigid precision part model of mechanical watch based on triangular graph element is taken as the research object, and the problems related to the construction of convex hull and collision detection are discussed. The main work and results of this paper are as follows: 1. The properties of convex hull are studied, and the basic ideas and computational complexity of Gift-Wrapping algorithm and Quick Hull algorithm in 3D space are discussed, and the advantages and disadvantages of fast packet algorithm are discussed. An improved algorithm for constructing convex hull of three dimensional point set is proposed. The algorithm can avoid the generation of intermediate surface by giving priority to other vertices coplanar with convex hull vertices and reduce the number of graph elements that ultimately form convex hull. In this paper, the algorithm is used to construct the convex hull of the part model, the convex hull is used to accelerate the construction of the bounding body, and the rapid collision detection and simulation of mechanical watch parts, fixture and environment are realized. In this paper, the methods of N-Bounding in the global phase of collision detection, including bounding body tree, space partition and topological method, are studied, and their applicable scenarios are discussed. In the topological method, we focus on analyzing the advantages and disadvantages of the most famous sweep cut (SAP) algorithm and its various variants, and propose a sample estimation based SAP optimization algorithm. The algorithm dynamically selects discrete sorting axes by sample estimation, which reduces the negative effects of model accumulation and model size change on real-time performance in large scale scenarios. Experimental results show that the performance of the new algorithm is better than other similar algorithms, and it can adapt to various scene environments, and its applicability is wider. 3. In this paper, the accurate intersecting testing method in local phase of collision detection is studied. In view of the shortage of real-time performance of existing bounding tree algorithms and the poor applicability to the assembly scene of mechanical table, an improved hybrid bounding tree algorithm is proposed in this paper. In order to detect the intersecting state of part models more accurately and efficiently, the algorithm uses several related bounding bodies to create tree nodes and modifies the construction of the tree. We also discussed how to optimize memory usage. The virtual assembly system of mechanical table is realized by using the Unity3D engine, and the experimental environment is constructed with the system scene as the template. The object is the running time, accuracy and comprehensive performance of the collision detection algorithm. Two algorithm contrast experiments are designed. The performance of the SSVs hybrid bounding tree algorithm is proved to be superior to that of the traditional algorithm by analyzing the experimental results compared with the traditional algorithm.
【學(xué)位授予單位】：廣西師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP301.6
本文編號：2133066
[Abstract]:Collision detection is a basic problem in many fields of computer science, such as physical simulation, path planning, virtual assembly and tactile rendering. So far, many algorithms have been proposed to solve the problem, but these algorithms have their own advantages and disadvantages. For example, V-Clip algorithm / Lin-Canny algorithm / GJK algorithm regards polyhedron as convex object, so concave polyhedron needs to be transformed into convex object by constructing convex hull. And when it comes to practical applications, there are other challenges: for example, tactile rendering requires a very high refresh rate, and virtual assembly of precision parts requires not only fast algorithms to get results, Moreover, the accuracy of the results is very high. Therefore, the optimization and improvement of the existing convex hull construction algorithm and collision detection algorithm according to the practical application environment is an area worthy of study, which has theoretical significance and practical engineering value. In this paper, the rigid precision part model of mechanical watch based on triangular graph element is taken as the research object, and the problems related to the construction of convex hull and collision detection are discussed. The main work and results of this paper are as follows: 1. The properties of convex hull are studied, and the basic ideas and computational complexity of Gift-Wrapping algorithm and Quick Hull algorithm in 3D space are discussed, and the advantages and disadvantages of fast packet algorithm are discussed. An improved algorithm for constructing convex hull of three dimensional point set is proposed. The algorithm can avoid the generation of intermediate surface by giving priority to other vertices coplanar with convex hull vertices and reduce the number of graph elements that ultimately form convex hull. In this paper, the algorithm is used to construct the convex hull of the part model, the convex hull is used to accelerate the construction of the bounding body, and the rapid collision detection and simulation of mechanical watch parts, fixture and environment are realized. In this paper, the methods of N-Bounding in the global phase of collision detection, including bounding body tree, space partition and topological method, are studied, and their applicable scenarios are discussed. In the topological method, we focus on analyzing the advantages and disadvantages of the most famous sweep cut (SAP) algorithm and its various variants, and propose a sample estimation based SAP optimization algorithm. The algorithm dynamically selects discrete sorting axes by sample estimation, which reduces the negative effects of model accumulation and model size change on real-time performance in large scale scenarios. Experimental results show that the performance of the new algorithm is better than other similar algorithms, and it can adapt to various scene environments, and its applicability is wider. 3. In this paper, the accurate intersecting testing method in local phase of collision detection is studied. In view of the shortage of real-time performance of existing bounding tree algorithms and the poor applicability to the assembly scene of mechanical table, an improved hybrid bounding tree algorithm is proposed in this paper. In order to detect the intersecting state of part models more accurately and efficiently, the algorithm uses several related bounding bodies to create tree nodes and modifies the construction of the tree. We also discussed how to optimize memory usage. The virtual assembly system of mechanical table is realized by using the Unity3D engine, and the experimental environment is constructed with the system scene as the template. The object is the running time, accuracy and comprehensive performance of the collision detection algorithm. Two algorithm contrast experiments are designed. The performance of the SSVs hybrid bounding tree algorithm is proved to be superior to that of the traditional algorithm by analyzing the experimental results compared with the traditional algorithm.
【學(xué)位授予單位】：廣西師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP301.6
【參考文獻】
相關(guān)期刊論文 前8條
1 陳明晶;方源敏;陳杰;;初始凸包對改進快速凸包算法效率的影響[J];測繪科學(xué);2016年07期
2 謝倩茹;耿國華;;虛擬手術(shù)環(huán)境中軟組織的快速碰撞檢測[J];計算機應(yīng)用研究;2015年08期
3 岳玉潔;趙建國;;基于Inventor三維吊裝仿真系統(tǒng)的研究與應(yīng)用[J];機械設(shè)計與制造;2012年04期
4 趙偉;譚睿璞;楊秋娜;丁文保;李文輝;;基于著色算法的并行碰撞檢測算法[J];計算機應(yīng)用研究;2009年05期
5 朱元峰;孟軍;謝光華;馬文娟;;基于復(fù)合層次包圍盒的實時碰撞檢測研究[J];系統(tǒng)仿真學(xué)報;2008年02期
6 劉曉平;曹力;;基于MPI的并行八叉樹碰撞檢測[J];計算機輔助設(shè)計與圖形學(xué)學(xué)報;2007年02期
7 王建宇;吳慧中;;基于圖像的虛擬戰(zhàn)場環(huán)境[J];火力與指揮控制;2006年08期
8 魏小亮,魏尚榮;凸包算法的變形及應(yīng)用[J];中央民族大學(xué)學(xué)報(自然科學(xué)版);2000年01期
相關(guān)碩士學(xué)位論文 前5條
1 鄭曉輝;基于混合包圍盒的混凝土泵車防碰撞算法研究[D];湘潭大學(xué);2016年
2 王炫殊;高維Voronoi圖的生成與應(yīng)用研究[D];華南理工大學(xué);2016年
3 唐磊;凸包圍多面體生成算法及應(yīng)用[D];清華大學(xué);2015年
4 許熠;基于混合包圍盒的碰撞檢測算法的優(yōu)化研究[D];南京理工大學(xué);2013年
5 成軍;碰撞檢測在虛擬拆裝仿真系統(tǒng)中的研究與應(yīng)用[D];湖南大學(xué);2010年
，本文編號：2133066
本文鏈接：http://www.sikaile.net/kejilunwen/ruanjiangongchenglunwen/2133066.html
最近更新
教材專著
