摘要
布料仿真技术近几年来成为计算机图形学领域的研究热点,它在计算机动画、服装设计、电子游戏等方面有着广泛的应用。布料由大量的几何元素构成,且易于变形,因此布料的自碰撞检测需要耗费大量的时间。布料厚度很薄,在自碰撞检测中很难确定布料自身是否发生自碰撞。因此布料的自碰撞检测和响应已经成为布料仿真中一个重要瓶颈。本文针对布料仿真中的自碰撞问题进行研究,主要工作体现在以下几个方面:
采用k-DOPs包围体层次结构对布料之间的自碰撞进行粗率的检测,减少不必要的几何元素之间的碰撞检测。同时,为了准确地检测到布料之间的自碰撞,对k-DOPs进行了一定的扩张,从而保证了布料自碰撞的准确性。在利用层次包围体结构对布料进行自碰撞检测中,引入表面曲率准则以及法向量锥的概念,提高了布料自碰撞检测效率。
假设布料存在一定的厚度,将布料的几何元素之间的碰撞检测分为:逼近性检测和相交检测。为了准确地检测几何元素之间的相交,先找出几何元素共面的时刻,再进行逼近性测试,以避免出现由于数值误差而没有检测到相交的现象。
鉴于传统的直接修改碰撞点的位置的方法,容易造成系统的不稳定。本文采用排斥力和摩擦力,通过施加冲量的方法来修正发生碰撞的质点的速度,进而通过数值积分方法确定质点的位置。同时,使用数值插值的方法保证冲量施加到三角面片的顶点上。
对布料的自碰撞进行仿真实验。实验结果证明本文的自碰撞算法能够较为快速正确地检测和处理布料之间发生的简单的自碰撞。
Cloth simulation is one of the most fascinating areas of computer graphics in recent years.It is widely applied to the fields such as computer animation,cloth design and computer games.Since a lot of points on the cloth's surface,all points may potentially collide with each other.Since the cloth is very thin,it's difficult to detect the self-collision. Therefore the cloth's self-collision has become a bottleneck of cloth simulation.We research on the cloth's self-collision.And the main works in the thesis can be stated as follows:
Applying k-DOPs bounding volume hierarchies to detect the self-collision of the cloth, reduces the number of comparisons that must be made when detecting collisions in meshes consisting of many triangles.In order to detect the self-collision of the cloth accurately, inflation of bounding volumes is introduced.Inflation of bounding volumes enables us to detect proximities and collision accurately with a minimum extra cost.A curvature and coherence criteria is also used to save the computation time.
Models cloth thickness,and divide the cloth's self-collision detection into proximate detection and collision detection.The collision detection between triangles is also improved. We find the times at which the points are coplanar,and then take a proximate test in increasing order at the times.
Directly altering the position and velocity of the collision points will cause the system unstable.In the thesis,we using repulsion forces and friction,applying the impulse to alter the velocity of the collision points,then get the position though the internal cloth dynamics.
Experiment result demonstrates that the proposed algorithm can detect and hand the simple self-collision of cloth.
引文
1 陈辉,沈毅.关于织物仿真技术的综述[J].丝绸,2005(8).
2 冯广慧.基于弹簧质点模型的快速布料仿真研究[D].吉林大学,2007.
3 朱淮冰,金小刚,冯结青,彭群生,布料动画模拟综述[J],计算机辅助设计与图形学报,2004,16(5):613-618.
4 Samet H.Spatial data structures:quadtree,octrees and other hierarchical methods[M].Addison Wesley,1989:23-27.
5 James T.Klosowski.Efficient Collision Detection Using Bounding Volume Hierarchies of k-Dops.IEEE Transactions on Visualization and Computer Graphics,1998,4(1),26-27.
6 Hubbard,P.M.,Approximating polyhedra with spheres for time critical collision detection.ACM Transactions on Graphics,1996,15(3):179-210.
7 Naylor BF,Amanatides JA,Thibault WC.Merging BSP trees yield polyhedral modeling results[A].In Proceedings of ACM SIGGRAPH,1990,115-124.
8 McNeely W,Puterbaugh K,Troy J.Six degree-of-freedom haptic rendering using voxel sampling[A].In Proceedings of Siggraph 1999,401-408.
9 Pascal Volino,Nadia Magnenat Thalmann.Collision and self-collision detection:Efficient and robust solutions for highly deformable surfaces.Computer animation and simulation'95,euro-graphics.:Springer-Verlag,1995,3:55-65.
10 Xavier Provot.Collision and self-collision handling in cloth model dedicated to design garments.Graph Interf'97 1997,147-154.
11 Suejung Huh,Dimitris Metaxas,Norman Badler.Collision resolutions in cloth simulation[J].Comput Animat 2001.
12 Bridson R,Fedkiv R,Anderson J.Robust treatment of collisions,contact and friction for cloth animation[A].Comput Graph(SIGGRAPH' 02 Proceedings) 2002.
13 Weil,J.The synthesis of cloth object[J].Computer Graphics.1986,20(4):49-54.
14 T.Agui Y.Nagao and M.Nakajima.An expression method of cylindrical cloth objects and expression of folds of a sleeve using computer graphics[J].Trans Soc of Electronics Information and Communications.1990,1095-1097.
15 Hinds B K,McCartney J.Interactive garment design[J].The Visual Computer,1990,6(2):53-61
16 Hinds B K,McCartney,Woods G.Pattern developments for 3D surfaces[J].Computer Aided Design,1991,23(8):583-592.
17 H.Ng and R.L.Grimsdale.Geoff-a geometrical editor for fold formation.Lecture Notes in Computer Science.1995,10(24):124-131.
18 Feynman C R.Modeling the Appearance of Cloth[D],MSc Thesis,Department of Electrical Engineering and Computer Science,MIT,Cambridge,MA,1986.
19 Breen D E,House D H,Wozny M J.Predicting the drape of woven cloth using interacting particles[A].In Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Orlando,FL,1994,365-372.
20 S.Kawabata.The Standardization and Analysis of Hand Evaluation[M].Textile Machinery Society of Japan,1980.
21 Terzopoulos D,Platt JC,Barr H.Elastically deformable models[A].Comput Graph (SIGGRAPH'97 proceedings) 1987,21:205-214.
22 Terzopoulos D,Fleischer K.Modeling inelastic deformation:viscoelasticity.Plast,Fract[A].Comput Graph(SIGGRAPH'88 proceedings) 1988,22:269-278.
23 Xavier Provot.Deformation constraints in a mass-Spring model to describe rigid cloth behavior[A].In Proceedings of Graphics Interface,Quebec:Canadian information Processing Society,1995,12(6):147-154.
24 Rudomin,I.J.Simulating Cloth Using a Mixed Geometric-Physical Method[D].University of Pennsylvania,1990.
25 Kunii,T.L.and H.Gotoda.Singularity Theoretical Modeling and Animation of Garment Wrinkle Formation Processes[J].The Visual Computer,1990,6(6):326-336.
26 凌海燕,姜建国,陈守满.数值积分法在布料仿真中的应用[J].2003,20(4),12-15.
27 Eberhardt,Bernhard,Andreas Weber,and Wolfgang Strasser.A Fast,Flexible,Particle-System Model for Cloth Draping[J].IEEE Computer Graphics and Applications,1996,16(5):52-59.
28 Volino P,Courchese M,Magnenat-Thalmann N,Versatile and efficient techniques for simulating cloth and other deformable objects[A].In Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Los Angeles,CA,1995.137-144.
29 W H Press,W T Vetterling,S A Teukolsky,B P Flannery.Numerical Recipes[M].Second edition.Cambridge University Press.1992.
30 BaraffD,Witkin A.Large steps in cloth simulation[A].In:Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,Orlando,FL,1998,106-117.
31 J H Clark.Hierarchical Geometric Models for Visible Surface Algorithms[A].Comm.ACM,1976,19(10).
32 张茂军,虚拟现实系统[M],科学出版社,2001,第一版,2-8.
33 S.Suri.Analyzing Bounding Boxes for Object Intersection[A].ACM Transactions on Graphics,1999,18:257-277.
34 Van Den Bergen.Efficient collision detection of complex deformable models using AABB trees[J].Journal of Graphics Tools,1997,2(4):1-13.
35 Gottschalk S,Lin M.C and Manocha D.OBB Tree:a hierarchical structure for rapid interference detection[A].In SIGGRAPH 96 Conference Proceedings,Annual Conference Series,ACM SIGGRAPH,New Orleans,USA,Aug.1996,171-180.
36 Jimenez P,Thomas F,Torras C.Collision detection:a survey[J],Computers and Graphics,2001,25(2),269-285.
37 G.Barequet,B Chazelle,L.J.Guibas,J.S.B.Mitehell,A.Tal.BOXTREE:A hierarchical representation for surfaces in 3D[A].Eurographies'96,Computer Graphics' Forum,1996,15(3):387-484
38 魏迎梅.虚拟环境中碰撞检测问题的研究[D].长沙:国防科学技术大学,2000.
39 魏迎梅,王涌,吴泉源,等.碰撞检测中的固定方向凸包包围盒的研究[J].软件学报,2001,12(7):1056-1062.
40 M.Moore,J.Wilhelms,Collision detection and response for computer animation[A].The Proceeding ofACM SIGGRAPH'88,1988:28-298.
41 赵亮。基于k-DOPs的碰撞检测及其算法研究[D].青岛:青岛大学,2007.