（模式识别与智能系统专业论文）基于物理的台球动画.pdf

摘要 传统动画技术要求预先描述物体在某一时刻的瞬时几何位置、方向和形状， 其运动则往往通过参数关键帧技术来完成，难以生成令人满意的运动。基于物理 的动画技术考虑了物体在真实世界中的属性，如它具有质量、转动惯矩、摩擦力 等，并采用动力学原理来自动产生物体的运动。因而，它能逼真地模拟各种自然 物理现象。 大部分台球动画主要用作游戏，并没有完全按照运动学和动力学原理开发， 建立的物理模型过于简单，失去了台球运动的物理特性。本文运用了运动学和动 力学原理对球杆击打主球的不同位置时主球的运动情况、球与球碰撞后的运动情 况进行分析。围绕小球的各种受力情况、球与桌壁之间、球与球之间的碰撞检测， 给出了适用于球体的基于c a c h e 信息的碰撞检测算法，实现了球的滚动及动画的 声音效果。 基于物理的台球动画对b 订1 i a r d s 开源程序进行了大幅度改造，核心程序根据 文中给出的模型采用v c + + 6 0 和o p e n g l 平台加以实现。 【关键词】物理学；碰撞检测；物理动画；台球运动 a b s t r a c t t r a d i t i o n a la i l i m a t i o n t e c l l i l 0 1 0 9 yr e q u i r e sp r e d e s c 曲e dn l ei n 咖t a i l e o u s g e o m e t r i cl o c a t i o n ，d i r e c t i o na n ds h a p eo fo b j e c t si nam o m e m t h e i rm o v 锄e n ti s o 矗e nf i n i s h e db yt h ek e y 疗釉et e c l l l l o l o g yw h i c hi st 1 1 e i rp a r a m e t e r s ，锄di ti s d i 伍c u l tt og e n e r a t eas a t i s f 犯t o 巧c 锄p a i g n t h e 觚i m a t i o nt e c h i l o l o g yb a s e do n p h y s i c a lt oc o n s i d e rt h ea 埘b u t e so f 嘶e c t si nt h er e a lw o r l d f o re x 姗p l e ，q 眦l 畋 i n e n i am o v e m e n t ，衔c t i o na n ds oo n i t a d o p t sd y n 锄i ct 量l e o r yt op r o d u c et h e m o v e m e n to fo b j e c t s a sar e s u l t ，i tc a ns i m u l a t er e a l i s t i cn a t 啪lp h e n o m e n a m o s to fb i l l i a r d sa n i m a t i o n sa r ec o n s i d e r e dt ob eag 锄e ，a n dn o tt ob e d e v e l o p e db yk i n e t i c s 锄dd ”锄i c s t h ep h y s i c a lm o d e lo fb i l l i a r d sa i l i m a t i o ni st o o s i m p l e ，i tl o s e sm ep h y s i c a lp r o p e r t yo f b i l l i a r d sm o v e m e n t t h i sp a p e r 如1 1 ya n a j y z e t 1 1 em o v e m e n to ft 1 1 em a i ns p h e r ea r e ri tr e c e i v e st 1 1 ef o r c ef b mt h eb a l la ma t d i 毹r e mp o s i t i o n ，t h em o v e m e n to fb a l l sa r e rc o l l i s i o na c c o r d i n gt ot h ep r i n c i p l eo f k n e m a t i c sa n d 由，i l 锄i c s a i md i r e c t l ya ts e v e r a lo ff o r c e s 锄o n gb a j l s ，t l l ec o l l i d e d e t e c t i o nb e 眦e nb a l l sa i l dt h et 叩o f t a b l e ，t h ec o l l i d ed e t e c t i o na m o n gb a l l s a n d m i sp a p e r 舀v et 量l ed e t e c tc o l l i s i o na l g o r i t l l i i lb a s eo nc a c h ei n f o 珊a t i o n ，r e a l i z e dt h e r o l lm o v e m e n ta n dt 1 1 es o u n de f r e c t b a s e do nm ep h y s i c a la i l i m a t i o nr e f 0 加t h eb i l l i a r d si nm o s tr e s p e c t s ，t h em a i n p m c e d u f e sa c c o r d i n gt 0m em o d e lg i v e db yt h i sp a p e ra l l du s ev c + + 6 oa n d o p e n g lp l a t f o m lt oa c l l i e v e 【k e yw o r d s 】p h y s i c s ；c o l l i s i o nd e t e c t i o n ；p h y s i c sa i l i m a t i o n ；b i l l i a r d sm o v e m e n t 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均己在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 丛 兰重量2 0 0 8 年6 月驴日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术 期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或 电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子 文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权 河海大学研究生院办理。 论文作者( 签名) ：秘； 臀2 0 0 8 年6 月 侈日 第一章绪论 1 1 引言 第一章绪论 基于物理的动画技术是八十年代后期发展起来的一种新技术，尽管该技术比 传统动画技术的复杂度要高得多，同时往往要求动画师拥有大量的物理背景知 识，但它能逼真地模拟各种自然物理现象，这是基于几何的传统动画生成技术所 无法比拟的。 传统动画技术要求预先描述物体在某一时刻的瞬时几何位置、方向和形状， 其运动则往往通过参数关键帧技术来完成。因而，欲模拟一个逼真的自然运动需 要动画设计者细致、耐心的调整，要求动画设计者依赖其对真实物理世界的直观 感觉来设计物体在场景中的运动。但由于我们对日常物理世界极为熟悉，并且真 实的物体运动往往非常复杂，因而，采用传统的动画设计技术一般来说难以生成 令人满意的运动。 事实上，现实世界就是一个物理的世界，其中的任何物体、任何过程都具有 各自相应的物理特性，这些特性都被各自相应的物理原理所反映着，如果要在动 画中模拟它们，采用必要的物理原理是不可避免的。从这一点来讲，动画技术除 去那些纯粹几何的以及图形学的成份外，所有的动画技术都是离不开物理原理 的，都应属于基于物理的计算机动画范畴。 基于物理的动画技术考虑了物体在真实世界中的属性，如它具有质量、转动 惯矩、摩擦力等【l 】，并采用动力学原理来自动产生物体的运动。当场景中的物体 受到外力作用时，牛顿力学中的标准动力学方程可用来自动生成物体在各个时间 点的位置、方向及其形状。 另外有些物体如单个刚体的运动，若不考虑碰撞，可以给出它们运动的严格 数学表达式，而对于变形体，如水波、云彩、树木、人体等，人们无法直接获得 它们的运动，只能通过解微分方程等手段来求得【2 引。更为严重的是，有些物体 如人体等至今尚未有有效的物理原理可供利用，这就更增加了动画实施的难度。 但是，如果不采用必要的物理原理，将无法生成它们的动画。因此，基于物理的 计算机动画技术是目前计算机动画领域的研究热点。 第一章绪论 1 2 物理动画相关技术发展 计算机动画是计算机科学的一个重要领域，而三维计算机动画是计算机动画 的主流。计算机动画的发展过程虽然只有短短的二十几年的时间，但它却在整个 计算机科学领域的理论和实践方面都引起了强大的震撼。 从理论上讲，首先，计算机动画特别是三维计算机动画的发展，促进了计算 机图形学和算法的迅速发展。计算机动画离不开计算机图形学的支持，从根本上 说，计算机动画所运用的算法几乎都来自计算机图形学。由于计算机动画生成速 度以及画面流畅性的要求，使得越来越多的高效算法和图形学理论如雨后春笋般 地诞生出来。尤其是三维动画，由于其向量、矩阵等运算的复杂性给各种算法提 出了严峻的挑战，特别是高性能并行算法。其次，计算机动画带动了相关计算机 领域的发展，如多媒体和人工智能的发展。当前的特技电影、计算机三维游戏等 几乎无一例外的都是计算机动画和多媒体相结合的产物【4 棚。只有将计算机动画 和声音、视频等多媒体要素结合起来，才能更好地突出动画的特点，使人达到身 临其境的效果。同样，只有单纯的动画而没有产生动画的动机和行为，也称不上 真正的虚拟现实，因此计算机动画和人工智能的结合也是大势所趋，这一点在计 算机游戏中体现得尤为明显。第三，计算机动画的发展也推动着计算机硬件以及 硬件接口的发展，特别是显卡的发展。计算机动画中复杂的计算没有计算机硬件 的支持而单纯依靠软件实现是不可能完成的。于是人们采用视频卡的处理器 g p u 来帮助c p u 进行变化，裁剪，渲染等的运算。由于g p u 采用了并行处理， 并且在硬件固化了一部分向量和矩阵的算法，使得计算机动画的运算速度有了大 规模的提高。与此同时，d i r e c t x ，o p e n g l 等硬件接口的软件以及3 dm a x ，m a y a 等计算机动画开发工具也应运而生了，这些都极大程度上方便了计算机动画开发 人员，减轻了他们的工作量，提高了开发效率。 1 3 国内外研究动态 基于物理模型的动画技术经过近几年的发展，它己在图形学中成为一种具有 潜在优势的三维造型和运动模拟技术。尽管该技术比传统动画技术的计算复杂度 要高得多，但它能逼真地模拟各种自然物理现象。在刚体运动模拟方面，其研究 重点集中在采用牛顿动力学的各种方程来模拟刚体系统的运动。舢m s t r o n g 和 2 第一章绪论 g r e e n ，、矾l h e h n s i7 】直接采用动力学方程来模拟刚体关节链的运动。对于柔性物体， 物体的变形一直是计算机图形学的研究热点。w | e i l l 8 】首次讨论了基于物理模型的 柔性物体的变形问题。h a d a p 桫j 等人采用纹理与几何相结合的方法模拟衣服上的 褶皱。涂晓嫒等人提出了一种模拟鱼的行为的动画，可在动画师较少干涉的情况 下生成真实的个体和群体运动。 基于物理的计算机动画一方面使得本身体现的现象能充分满足人们对真实 的需要，提高整个沉浸感；另一方面减轻了程序开发人员和艺术家的劳动强度， 不需要脚本去控制物体，不再需要单独去管理每一个细小事件，因为所有的事情 都会按着它本身的物理规律来完成。 近几年，研究者们更多地采用基于物理的方法去模拟。基于弹性理论， t e 亿o p o u l o s 【1 啦! 1 1 等人提出了一种控制变形曲面运动的方法，并用来模拟旗帜的 飘动和地毯的坠落过程。 浙江大学c a d & c g 国家重点实验室，国家重点基础研究发展规划项目， 周永霞、郁佳荣【1 2 】等研究基于物理的烟雾动画，通过无量纲化处理简化模型， 节省了计算时间，通过引入高阶精度紧致格式，提高了计算精度。 浙江大学王长波【l 引、彭群生等研究基于物理模型的自然景物真实感绘制， 指出基于物理的自然景物的真实感动态绘制是当前的主要研究方向之一，并考虑 折射的天空场景真实感模拟，飘雪场景的实时绘制，风吹草动的动态建模与绘制， 海市蜃楼场景的实时模拟，下雨场景的实时建模与绘制。 基于物理的计算机动画一直是计算机图形学领域的一个热点研究方向，尤其 是电影特效的发展以及电子游戏的强力需求推动着这一方向的研究。人们不仅需 要形象的真实感，也需要运动的真实感。而真实世界蕴涵着复杂的运动规律，其复 杂度往往使得人们难以用一些简单过程来表述。如何发现这些规律并通过计算机 计算重现真实世界的运动成为基于物理的计算机动画的关键技术。 1 4 主要研究内容 本文重点围绕球体的各种受力情况，以及球与球之间，球与桌壁之间的碰撞 检测进行分析讨论，最后根据前面的分析完成对整个台球动画的物理模拟。主要 工作如下： 第一章绪论 1 从物理学角度分析了球杆在击打主球的不同位置时，主球的运动情况。 其中包括了球杆在击打主球的上、中、下部时，主球的运动速度以及方向。靶球 在发生碰撞后的运动速度以及方向。球体与桌壁发生碰撞后的运动速度以及运动 方向。 2 分析了球与球之间的碰撞检测，球体与桌壁之间的碰撞检测。给出了适 用于球体的基于c a c h e 信息的碰撞检测算法，并进行了实验结果分析。 3 采用v c + + 6 o 和o p e n g l 平台实现了台球动画的物理模拟，并利用o p e n a l 函数加入了动画的声音效果。 1 5 论文结构 本文由以下五章和参考文献组成。这五章的内容是： 第一章绪论。 介绍了本文研究的背景，并给出了基于物理的台球动画所研究的主要内容和 相关成果。 第二章台球运动的物理分析。 本章主要从物理学角度分析了台球的各种运动情况，为后面的台球动画的实 现做了充分的理论准备。 第三章台球的碰撞检测算法。 本章主要对分析了球与球之间的碰撞检测，球体与桌壁之间的碰撞检测。给 出了适用于球体的基于c a c h e 信息的碰撞检测算法，并进行了实验结果分析。 第四章基于物理的台球动画的实现。 本章主要介绍了台球运动的具体实现思路及流程。主要包括球杆击打主球的 不同位置后，模拟对主球运动情况的模拟以及靶球运动情况的。 第五章总结全文工作，并做出展望。 4 第二章台球运动的物理分析 第二章台球运动的物理分析 物体的运动都是遵循一定的物理规律的运动，基于物理的台球动画基本思路 是用物理规律约束台球的运动，在动画中台球的运动符合物理运动规律，台球动 画可以更加逼真。 台球运动是一个复杂的运动过程。主要包括：球杆击球后，主球的运动情况， 球体之间发生碰撞后，球体的运动情况，以及球体与桌壁之间发生碰撞后的运动 状况。常见的台球动画中的描述都是为了台球游戏的需求而简化了台球的物理运 动过程，失去了台球运动过程中的真实物理属性，本章主要从球杆击打主球的不 同位置后，主球的具体运动情况进行分析，并对球体碰撞后的运动以及球体与桌 壁发生碰撞后的运动情况进行了分析。 2 1 力作用下主球的运动分析 台球在桌面上的运动就是小球的质心平动和绕质心转动的两种运动的合成， 在台球复杂的运动中，粗糙的桌面对台球的摩擦力起着重要的作用n 矧。 如图2 1 所示，一个质量为m ，半径为r 的匀质实心球静止在水平桌面上， 用球杆沿水平方向击打球体，设冲力f 沿水平方向距离球心c 的距离为h ，台球 受到的冲量为尸= f 2 融，沿x 正方向，因此击打施于台球时，沿顺时针方向的 冲量矩为j = p h ，另外台球还受到竖直向下的重力m g 和竖直向上的正压力f n 的作 用。根据刚体质心运动的动量定理和动量矩定理可知，球心获得沿x 正向的平动 速度u 。和顺时针转动的角速度( 1 ) 。分别满足以下关系：( 以下均化为标量的关系 表示) 口= p ，i = j ( 2 1 ) 第二章台球运动的物理分析 图2 1 沿水平方向击打球体 我们规定沿顺时针的转动方向为正方向，式中= 吾艘2 为球对质心的转动 惯量，台球与桌面接触点的速度为 = 一r ( 2 2 ) 将式( 2 1 ) 代入式( 2 2 ) ，则得 = 刍一半= 钟嗣 泣3 ) ( 1 ) 球杆击打主球的中心位置 当h _ 0 时，即球杆击打主球的中心位置时，由上式可知， 2 2 云 q 4 ) = o ( 2 5 ) 主球受球杆击打后的瞬间作纯滑动，此后将作无滑纯滚动，若与靶球发生对 心碰撞，靶球将以主球的速度甜。向前运动，而主球则静止不动。 此时主球的位移与转动角9 由式( 2 6 ) 得出： ( 2 ) 球杆击打主球的上部位置 当球杆击打主球的上部位置时，可分如下三种情况考虑主球的运动状态。 1 ) 当办= 0 4 r 的情形 由式( 2 3 ) 可见，当办= o 4 r 时，虼= 0 ，这时球心的速度与滚动角速度满足 6 )62l 一 “ = 出 o 。o i i i i 岛 伊 第二章台球运动的物理分析 不滑动的判据，因此，滑动摩擦力不存在，只有相对滑动摩擦力很小的滚动摩擦 力，于是球体将沿x 正方向匀速地持续滚动下去。球体的位移与转动角0 由式 ( 2 7 ) 给出。 f 岛2 r 田= r ( 2 7 ) 0 9 = ， 2 ) h o 4 r 的情形 由式( 2 3 ) 可知，在这种情形下，小球与桌面的接触点的速度 。 汜 当t t 。时，台球开始作无滑的顺时针滚动，沿x 正向前进。由式( 2 1 1 ) 可求得台球的质心沿x 正向运动的速度为 7 釜三耋鱼登圣垫箜塑堡坌堡 一一 俐一。= 甜嘲 沿顺时针方向转动的角速度为 ( 2 1 4 ) = 篙去雌 1 5 此时，球体的位移与转动角0 可由式( 2 1 6 ) 得出。 乒西+ 卜= 私+ 舟期+ 号去嘲卜u 旺 3 ) h o ，桌面对小球的摩擦力朝负x 方向， f 尸pm g ，因此小球的质心作减速运动，同时，f f 施于球心沿顺时针方向的力矩 为f ，r ，根据刚体的运动定理，质心平动的加速度“和角加速度缈分别为 三m ：叫彬，j 二：g 懈 ( 2 1 7 ) 则在t 时刻，球心的速度u ( t ) 和绕球心沿顺时针方向的转动角速度( t ) 分 别为 甜( f ) ：旷鹏( f ) ：+ 芈 ( 2 1 8 ) 小球与桌面接触点的速度为 叶一砌= 一+ 寺 t 一羔 1 9 ) 当既滑又滚的运动经过一段时间后，v = o ，由上式可求得为 乇弓南 - 一期如 q 2 当f 时，小球作无滑的纯滚动，其质心速度和转动角速度可由式( 2 2 0 ) 代入式( 2 1 8 ) 求得。 矾锄弓击睢l q 2 d 8 第二章台球运动的物理分析 缈：兰：三土f 1 + 鱼i ( 2 2 2 ) r7 懈l r j 此时，球体的位移与转动角0 可由式( 2 2 3 ) 得出 建= 了唧) 衍+ 弘撇= 一三簖+ 吉 - 一羔p + 号去 1 + 刽( 卜) 。2 仍， 秒= 耐 ( 3 ) 球杆击打主球的下部位置 用球杆沿水平方向击打台球的下半部，如图2 2 所示，和前面一样，我们仍 规定沿水平方向的冲力f 的方向为x 轴的正方向，冲力f 沿水平方向距球心的距 离为h 。击打后，台球的球心获得的初始速度u 。和绕球心转动的初始角速度。， = 吉，= 一孚，不同的是，这时的初始角速度。沿逆时针方向转动，是负 的转动方向，因此，d 。为负值。 m g 图2 2 沿水平方向击打台球的下半部 这时台球与桌面接触点的速度为 y = 一r = 去+ 半= 击l ，+ 羔l c 2 “， 显然接触点沿x 正向滑动，作用于台球的摩擦力指向负x 方向，因此，摩擦 力毋= 一豫，摩擦力施于相对于球心的力矩一r ，为顺时针转动方向。根据刚 体的质心运动定理和相对于质心的动量矩定理，有 m 材= 叫，j 缈= g 懈 ( 2 2 5 ) t 时刻台球球心的平动速度u ( t ) 和绕球心转动的角速度( t ) 分别为 9 第二章台球运动的物理分析 甜( ，) ：一，缈( f ) ：+ 丝竽， ( 2 2 6 ) 即 ) = 吉删州= 一孚+ 芈= 一芤篇删 2 7 ， 由上式可知，在较早的时刻，球心速度u ( t ) 0 ，台球沿x 正向运动，到了 2 乏= 时刻，球心速度u ( t i ) _ o ，此后，u ( t ) 伊t 2 的这段时间 内，台球沿x 正向前进，相对于球心作顺时针方向转动，在这段时间内，必有某 个时刻，o ”，台球的平动和转动相配合，使球与桌面的接触点的速度v = 0 ，即 y ( f o f t ) = “( ) 砌( ) = 去一删+ 竽一华= o ( 2 2 8 ) 妣”= 去钟剖 2 9 ， 在岛”时刻，台球开始作无滑滚动，沿x 正向前进，将f o ”代入式( 2 2 7 ) 则 得球心的平动速度和绕球心的转动速度： 砒t i ) = 渤一钢 3 。， w i ) _ 去井钢 眨3 t ， 这时台球将以速度“( ”) 、国( 岛”) 作无滑滚动，沿x 正向一直持续滚动下去。 其位移与转动角0 由式子( 2 3 2 ) 得出 岛= ( 厉+ l 脚+ 竽) 毛腭( 1 + 等户+ 去甜一咎一) ( 2 m ， 乡= 耐 假设袖冲力f 击打了下部的球为a 球。存t 。 眩3 5 ， 显然，接触点沿x 正向滑动，故施于a 球的摩擦力朝负x 方向，e = 叫， 乃施于相对于球心的力矩乃r 为顺时针方向。我们将相撞的，+ 时刻设为零时刻， 那么，相撞后的t 时刻a 球的球心的平动速度z ，和转动角速度缈。分别为 “= 一 ( 2 3 6 ) 国材+ 芈耐去 ( 2 3 7 ) 则a 球与桌面接触点的速度为 y = ”一只国= 一一尺缈一丢 ( 2 - 3 8 ) 由上式可求出y - o 的时刻 ，。= 去置 3 9 ， 当f r 时，主球沿负x 轴方向作无滑滚动，将，代入式( 2 3 6 ) 、( 2 3 7 ) ， 则得无滑滚动的质心速度“。和转动角速度缈分别为 “”= 一钆杀倒 4 。， 彩”：一三i 旦一“酊l ( 2 4 1 ) 彩一面l 面叫i 旺4 由此可见，被击打了下半部的a 球，与b 球相撞的越早，即f 越小，a 球 沿x 负向作无滑滚动退回的速度就越快，沿负x 方向持续运动的时间也就越长。 此时，球体的位移与转动角0 可由式( 2 4 2 ) 得出 = ，出+ p 出一；”一肼f 石( h ) 一云g ( 卜产) ( 2 4 2 ) o 广 9 = t 由方程可以看出，主球质心的运动距离随着滑动摩擦系数“的增大而减小， 随着质心初始速度的增加而增加，式中的负号代表运动方向与原来速度相反的方 1 2 第二章台球运动的物理分析 向。 2 2 两个球体碰撞的运动分析 如图2 5 所示，设有两个小球，小球1 质量为码，半径为蜀，小球2 质量 为，半径垦，不失一般性，令小球2 开始时静止位于桌面上，小球1 以速度v 运动，速度v 与两个小球中心连线q q 夹角为0 ，将0 角称为碰撞角，将由q q 和速度v 所构成的平面称为碰撞平面，由此可知两个小球均在碰撞平面内运动。 j l ， 叁 厂7 h 。 o 兰入兰 x 7 1 4 ，i 、瞎 图2 5 小球发生碰撞 两个小球在碰撞前的相对速度不沿两球球心连线的碰撞称为“斜碰”，又称 非对心碰撞 。台球的碰撞运动属于典型的斜碰问题1 2 1 2 2 】。斜碰也可分为弹性 碰撞和非弹性碰撞两类，具体到台球的碰撞，可近似地处理为大小和质量均相同 的两个小球的刚性碰撞，即弹性碰撞。 小球l小球2 图2 6 小球相互作用 假设两个小球均为光滑小球，发生非对心碰撞，如2 6 图所示，e 为两小球 第二章台球运动的物理分析 对心碰撞时的恢复系数。当两个小球接触时，相互作用力只有正压力r 。，目：。 且日，= 日：= 日，因此，可知两球碰撞后均无旋转。令两个小球碰撞后速度分 量分别为( _ ，h y ) 和( 屹，v 2 y ) ，分别对x 和y 方向应用动量定理，有 码h j ，= 1 ，s i n 口 秭 ，c 。s 口一码h ，= 一班 o m ，2 。= l f n 斑 聊2 吃j ，= 0 恢复系数 e ：鳖二塾：塾二堡! v l o j v j o j v c o s 口 其中t 为两个小球碰撞所经历的时间。 解方程( 2 4 3 ) 、( 2 4 4 ) 、( 2 4 5 ) 、( 2 4 6 ) 、( 2 4 7 ) 得 m ，：业v c o s 目h j 。v c o s i l l 、 h 2 u y = ，s i n 9 屹，：巫型v c 。s 口 n l 、m 2 y 2 ，= o 由式( 2 4 3 ) 、( 2 4 7 ) 得 ，m j ，+ 吃y = v s i n 矽 由式( 2 4 4 ) 、( 2 。4 5 ) 得 m v l ，+ ，竹2 v j j = ，v c o s 矽 ( 2 4 3 ) ( 2 4 4 ) ( 2 4 5 ) ( 2 4 6 ) ( 2 4 7 ) ( 2 4 8 ) ( 2 4 9 ) ( 2 5 0 ) 由上面的公式可以看出，在发生碰撞后，在x 和y 两个方向上遵守动量守恒 定律。 1 4 第二章台球运动的物理分析 f 小球l小球2 图2 7 小球受力分析 假设两个小球和历：均为非光滑小球，发生非对心碰撞，坐标系的选择与 图2 5 相l 司，两小球l 司的滑动摩擦系数为“，e 为两个小球对心碰撞时的恢复系 数。当两个小球接触时，相互作用力有沿法向的正压力目，目：和沿切向的摩 擦力哆，乃：。目。= 目z = r ，乃。= 哆：= 乃，哆= r ，由此可知两球碰撞 后将绕各自的球心发生旋转，且转动轴垂直于碰撞平面。令两个小球碰撞后速度 分量分别为( v 1 ，v l ，) 和( 屹，吃y ) ，角速度为q 和吐，则分别对x 和y 方向应用 动量定理，并结合角动量定理有 肛西= 铂1 ，c 。s p 一鸭m ， o l f n 斑= m 2 v 2 x p r 西= 鸭1 ，s i n 口一码k y o l “f n d t = m ，2 y o p r 、f n d t = i 、q o l 弘f n d t - j p 2 ( 2 5 1 ) 其中和厶分别为两个小球和绕球心旋转时的转动惯量： ：寻确尺，2 ，厶：吾鸭心2 ( 2 5 2 ) ) 联合求解以上方程组并令 第二章台球运动的物理分析 丑= 当冬( m ) 1 ，c 础 1 现+ 鸭。、 7 则可得 ( 2 5 3 ) ih ，：，c 。s p 一! 一五 i 卜去 j b y2 1 ，s i n p 一：【- 丑 。2 5 4 ， 卜去五 他。4 卜鲁五 卜鲁五 小球1 ( i ) 2 小球2 图2 8 小球受力分析 由图2 - 8 可知a 、b 两点在y 方向上的速度分量分别为分别为= u y 一墨q ， = 屹y 是哆，随着碰撞过程的进行，由于摩擦力的作用，v 0 将变小，逐 渐变大，当= 的时候，在y 方向上a 、b 两点将没有相对运动速度，也没 有相对运动的趋势，所以摩擦力将不再存在，v 0 和嘞将不再变化，由此可知， 碰撞后必须满足，即 m y r q v j y + 心呸 ( 2 5 5 ) 1 6 第二章台球运动的物理分析 将方程组( 2 4 4 ) 代入上式有 v s i n 秒一互一竿五玉+ 譬五 码l掰22 ( 2 5 6 ) 整理得 t a l l 秒l l 土+ 土+ 壁+ 壁l ( 2 5 7 ) 1 ，c o s 秒l 铂 厶j = 詈，碍曷2 ，厶= 吾心2 ， ( 2 5 8 ) t a l l 秒去( 1 + e ) ( 2 5 9 ) 令t a i l 岛= ( 1 + p ) ，称岛为碰撞临界角 由以上分析可知，当碰撞角大于等于临界角，即秒岛时，碰撞后两个小球 的运动情况由方程组( 2 5 4 ) 给出。 下面主要讨论碰撞角小于临界角，即秒皖的情况，并对方程组( 2 5 4 ) 以 必要的修正。 设以两个球开始接触时作为计时起点，= o ，碰撞持续时间为o f ，摩擦力 存在时间为o f ，当碰撞角小于临界角，即p 皖时，由以上分析可得f f ，故 对碰撞过程可写出方程组 ，r 班= 码v c o s 秒一， o l f n d t = m ，2 x 弘目西= 码，s i n 9 一铂m y o l “f n d t = m ，2 y o l ”r 、f n d t = i 限 o 陟厶哆 且碰撞后有 1 7 ( 2 6 0 ) 第二章台球运动的物理分析 h j ，一墨q = 屹j ，+ r 哆 联合求解方程 ( 2 6 1 ) ( 2 6 2 ) ( 2 6 3 ) ( 2 6 4 ) 由上面的分析可以得出秒= 岛时有 = 五。 通过上面的分析，可知两个小球碰撞后的运动情况将由碰撞角0 完全决定。 一， 当t a n 秒寺( 1 + p ) 时，碰撞结果将由方程组( 2 5 4 ) 给出。反之，如果 二 1 t a n 口 ( 1 + p ) ，碰撞结果将由方程组( 2 6 2 ) 给出。本节中的球体运动以矢量 二 形式进行了分析，可将矢量转化为标量，按照第一节中所介绍的公式计算碰撞后 球体的位移以及转动角度。 2 3 小球与桌壁发生碰撞的运动分析 在台球的运动过程中，小球不可避免的要与台球桌的桌壁发生碰撞，小球与 桌壁的碰撞主要分为正碰和斜碰。下面分别对小球发生这两种碰撞后的运动进行 分析。 1 8 第二章台球运动的物理分析 图2 - 9 小球以速度向前运动 图2 一1 0 发生碰撞后的运动 如图2 - 9 所示，当小球o 以速度方向前进，当运动到桌壁的位置时，会与 桌壁发生碰撞，如图2 1 0 所示，碰撞后由动量守恒和动能守恒定律可以推出小 球将以速度沿着与原来运动方向相反的方向运动。 ； 7 7 !， q 图2 - 1 1 小球沿着吒方向运动 图2 1 2 发生碰撞后小球的运动 1 9 第二章台球运动的物理分析 如图2 1 1 所示，当小球沿着速度1 l d 的方向运动时，在某一时刻t 会与桌壁发 生碰撞( 如图2 1 2 所示) 。由动量守恒和动能守恒定律可以推出在发生碰撞后， 小球会以同样的速度反弹并沿着如图所示的方向运动，图2 1 2 中与口：的角度 相同。 球体的位移与转动角0 由公式( 2 6 5 ) 得出 s = p 社= v o l o p = ， 2 4 本章小结 ( 2 6 5 ) 本章主要从物理学角度分析了台球的运动情况，主要包括在力作用下主球的 运动情况( 其中包含了球杆作用于球体的不同部位后小球的运动情况) 、两个小 球之间发生碰撞后小球的运动以及小球与桌壁碰撞后小球的运动情况。 第三章台球的碰撞检测算法 3 1 概述 第三章台球的碰撞检测算法 在虚拟环境中，由于物体的运动，物体问可能经常发生碰撞，此时为保持模 拟的真实性，需要及时检测到这些碰撞，并计算相应的碰撞反应，更新绘制结果， 否则物体间会发生穿透现象。鲳1 ，破坏虚拟环境的真实感和用户的沉浸感。 台球的碰撞检测问题是碰撞检测中较为特殊而简单的问题，台球的碰撞检测 要解决的实质问题是在当前帧如何从大量物体中排除相距较远的物体对，从而减 少需要进一步检测碰撞的物体对数。碰撞检测的算法有很多种，很多算法也适合 台球的碰撞检测。射线算法以球的运动方向作为射线的方向作一条射线，通 过在每个时间步长内，根据小球的运动方式，判断两个小球之间的的距离，从而 来达到碰撞检测的目的。该方法简单，易用，但是时间步长的确定比较困难，时 间步长取的大了，物体的运动过程，从视觉上看起来会失真：反之，则会增加系 统的开销等。距离跟踪法通过寻找和跟踪两个多面体之间的最近点来计算他 们之间的距离，当距离小于或等于零时，两者就发生了碰撞。该方法充分利用了 小球的几何特征，简单，易用。但是不能有效减少碰撞检测的次数，即在每一帧 都需要做碰撞检测，会增加系统的开销，也同样存在着时间步长确定困难的问题。 浙江大学杨柏林嘲1 等提出的动态多分辨率网格划分算法，该算法使用多层次碰撞 检测和动态多分辨率网格划分的方法来减少碰撞检测的计算次数，大大提高了算 法性能。在碰撞响应中，为了精确计算碰撞的交点以符合物体运动的物理规律， 采用了时间间隔二分查找算法来保证碰撞的计算精度和系统效率。但是该方法还 存在以下问题：1 、如何选取和决定实现动态多分辨率网格划分算法中的密度函 数；2 、如何选择碰撞响应中的间隔时间等等。本文给出了基于c a c h e 信息的碰 撞检测算法，本方法充分利用了帧与帧之间都会有很强的关联性的特性，利用 c a c h e 保存的前两帧的碰撞结果信息，来判断当前帧是否发生了碰撞，从而有效 减少了碰撞检测的次数，降低了系统的开销。 2 l 第三章台球的碰撞检测算法 3 2 台球常用的碰撞检测算法 3 2 1 射线算法 在三维矢量空间中，射线用以表示方向，由两个矢量定义：一个表示它的起 点，另个表示它的方向。射线的模为一。 在实际建模时仅仅考虑表面较简单的球体与平面之间的碰撞。以球心作为起 点，以球的运动方向作为射线的方向作一条射线。如果不考虑球的大小将丢失物 理上的真实性，而在视觉上表现为球体贯穿这个平面。为了实现真实的效果，在 模拟过程中，要假想在平面的法向一侧存在一个虚拟的平面，这个虚拟平面与真 实平面间的距离恰好等于球的半径。 碰撞时间及碰撞点的确定。在模拟过程中总是给定适当的时间步长，然后计 算球在这个时间步长中的运动，问题在于碰撞是否发生在当前的时间步长中以及 准确的碰撞时间的计算。 要计算碰撞点的位置矢量，首先找到一点作为起点，以平面的法线的反方向 为正方向作射线，很明显碰撞点就是射线上的点，因此碰撞点的位置矢量可以求 出。这一部分的算法设计：1 ) 判断球的运动方向是否和平面平行或者向着离开 平面的方向运动；2 ) 否则分别计算球到碰撞点以及球到时间步长终点的距离；3 ) 根据相关公式计算出发生碰撞的时刻；4 ) 如果碰撞时刻在当前的时间步长之内， 计算碰撞点。 在矢量空间中，球可以用一个点矢量和一个标量表示，要确定两个球体是否 发生碰撞，只要计算两个球心之间的距离，看其是否小于两个球的半径之和即可。 问题的关键在于如何确定两个运动的球的碰撞。 两个球体分别从一个位置移到另一位置。虽然两球运动的路径是交叉的，但 是它们是否一定会发生碰撞主要看两个球是否同时到达了路径的交叉点，而在模 拟中还与所采用的时间步长有关。 要准确确定两个球体碰撞发生的位置，时间步长必须足够小，虽然时间步长 越小，检测结果越精确，但是会增加太多的计算开销，只要检测到两个球体将在 某个时间步长中发生贯穿，那么就分别记下两个球在这一个时间步长开始时的位 置，然后使用内插法计算两个球碰撞的精确位置，或者直接使用这个时间步长开 第三章台球的碰撞检测算法 始时的位置作为碰撞发生的位置，只要时间步长适当，这样做并不会影响视觉上 的真实感。 3 2 2 距离跟踪法 该类算法通过寻找和跟踪两个多面体之间的最近点来计算他们之间的距离， 当距离小于或等于零时，两者就发生了碰撞。比较著名的算法有l i n c a n d y 算法 和e n h a n c e dg j k 算法。两种算法借鉴了时空连续性和几何连续性的原理来加 速算法，当物体运动速度不是很快时，前后两帧物体的移动距离和形状变化不是 很大，可以利用上一帧的物体位置和形状来加速算法。 l i n c a n d y 算法的主要思想就是寻找两个多面体之间的一队距离最近的特 征，称为最近对。当多面体运动时，该算法跟踪并更新最近特征对。这里的特征 对指的是多面体上的一个顶点，边或面，特征对的距离指两个特征上距离最近两 点的距离。该算法利用一个事实，即当物体沿一个路径移动时，最近特征对不经 常发生改变。该算法通过对多面体做预处理，可保证最近特征对不变，或者在一 个可预知的常量时间内更新相邻的特征对。 算法首先从两个多面体上各选一个候选特征，检测最近点是否在这对候选特 征上，因为多面体设为凸的，该项检测只需要涉及与相邻的特征对作为新的候选 特征对，重新检测，通过一些简单的预处理，可保证每个特征的相邻特征个数恒 定，因而可在预知的常量时间范围内更新相邻的特征对。 在应用到台球动画的碰撞检测过程中，则演化为通过判断两个球体的球心位 置之间的距离来检测两个球体在某一时刻t 是否发生了碰撞。假设球体a 与球 体q 的球心位置分别为( _ ，m ) 与( 恐，儿) ，半径分别为，；与。根据距离的计算 广_ = 公式d = ( 恐一五) 2 + ( 咒一m ) 2 可以求出两点的距离。当d = + 吒时，则两个球 体发生了碰撞。否则两个球体没有发生碰撞。 第三章台球的碰撞检测算法 x ：a 图3 一l 小球与桌壁的碰撞检测 如图3 1 所示，首先定义好台球桌的大小，令台球桌的长为a ，球桌的宽度 为b 。并建立如图3 1 所示的坐标系。 假设在某一时刻t 小球的运动到如图所示的位置，由坐标值可以得到小球的 具体位置分别为p o s x 和p o s y 。然后利用如下的距离的计算公式可以求得当前小 球的球心的位置与四个桌壁的距离，通过距离的大小与小球半径的比较可以得出 小球与平面是否发生碰撞 当小球的球心的位置满足上述公式之一时，小球便与桌壁发生了碰撞，否则 小球与桌壁之间没有发生碰撞。 3 2 3 动态多分辨率网格划分算法 为了解决固定子区域大小划分所带来的问题口卜3 别，采用一种动态多分辨率的 网格划分算法。在实际的场景变化中，球的分布会有一些规律性，如某些时刻球 会聚集在某几个网格区域里面，此时，可以采用细网格的划分方法来划分这些网 格区域。而在另一些时候，某些球会稀疏地分布在某几个区域里面，为了达到较 高的性能可以采用粗网格来划分。根据实际情况，充分利用粗细网格划分。 基于动态网格划分算法根据在每一次计算时刻球在球桌上分布的疏密情况， 动态地决定桌面上各个区域应该被分割的尺度，球越多的区域网格划分越细，分 ，j 口o 6 0 | i l f i i = r r 广 r + 一 + 一 j 少 娜 甜 p p p p 第三章台球的碰撞检测算法 辨率越高，而对于球分布越稀疏的网格区域划分的越粗，分辨率越低。分割之后 使得在每一个不同大小的子区域里面所包含的球数目控制在零到某个上限之间， 并且满足区域和区域之间的球数目保持大体一致，以便最高效率地利用相邻区域 判断方法初步筛选出可能碰撞的球。 算法采用了两层次碰撞检测的方法，即将判断球是否碰撞分为两个层次。在 第一个层次，用一种快速有效的算法粗略筛选出可能碰撞的球，然后将这些结果 送到第二级。在第二个层次，采用距离计算方法来精确判断两球是否发生碰撞。 这种方法，缩小了进入精确检测碰撞的范围，减少了计算量。 为了解决计算球的位置坐标时由于两帧之间的时间间隔是离散变量而造成 在球运动状态调整时计算的偏差，从而导致球的运动轨迹不真实采用时间间隔二 分查找算法。该算法在检测到两物体碰撞了以后，将计算间隔时间减少到原来的 l 2 ，再根据物体原来的状态参数重新计算位置参数，如果仍然发生碰撞，再将 间隔时间二分查找，重复以上步骤，直到碰撞两球的重叠面积可以忽略不计为止， 此时的交点位置就是刚发生碰撞的切点位置。 当两球发生碰撞以后，采用上述时间间隔二分查找算法来找到实际相碰撞的 切点，然后按照能量守恒定理计算碰撞以后两个物体的速度k ，k 。，计算公式如 下 k ，：k + 盟蔓塑型塑坐堕盟型堂剑 ( 3 2 ) “1 2 事【( s 一是) ( s 一莲) 】 k ：职一盟墨盥型塑坐鲨婴生巡坠婴 ( 3 3 ) “ 2 木【( & 一是) ( s 一是) 】 其中v 1 ，v 2 表示两球的速度向量，k 。和。表示两球碰撞以后的速度向量，s 和是是两球的位置向量，e 表示碰撞系数。 该算法目前仍然存在下列问题：如何选取和决定实现动态多分辨率网格划分 算法中的密度函数，如何选择碰撞响应中的间隔时间等等。这些都是在以后的工 作中需要解决的问题。 第三章台球的碰撞检测算法 3 3 基于c a c h e 信息的碰撞检测算法 3 3 1 算法原理 在虚拟环境中通常在帧与帧之间都会有很强的关联性，因为虚拟环境从一帧 过渡到另一帧时不会急剧变化。这意味着虚拟环境中物体从一帧变化到另一帧时 是相对静止的口3 。因此当有一次碰撞在两个球体之间发生时，很有可能会有一 次新的碰撞在这两个物体之间发生。假设新的碰撞总是会在接近上一次碰撞的球 体处发生，在需要测试碰撞发生与否时可以首先测试上一次发生碰撞的地方，同 时应该把上一次发生碰撞的相关信息缓冲下来，以供本次测试使用。 此方法在具体实现时，需要在原有的表示每个