zhigu 发表于 2007-5-8 21:38:00

关于椭球碰撞检测的思考

<p>如有转载,&nbsp;请注明出处:<br/><a href="http://www.azure.com.cn/" target="_blank">http://www.azure.com.cn/</a></p><p>近日突然变得的比较清闲，这样我就可以仔细想想以前没有想清楚的问题。</p><p>椭球碰撞是现今比较高效的一种方法。看了老外的一篇论文，&lt;&lt;<b>Improved&nbsp;Collision&nbsp;detection&nbsp;and&nbsp;Response</b>&gt;&gt;,&nbsp;发现老外说一个事情非常罗嗦,&nbsp;最前面还把线性代数的知识讲了一遍,&nbsp;看完了才发现是大学课本上的知识.&nbsp;便马上跳过了.<br/>实际碰撞中,&nbsp;将椭球包裹住角色,&nbsp;能产生比较好的吻合.这样碰撞效果更加的精确了.<br/>这里我所思考的范围还不涉及碰撞后的滑动,&nbsp;那是我下一步要思考的&nbsp;.</p><p>这里我主要总结下,&nbsp;椭球碰撞的几个要点:</p><p>1.&nbsp;椭球的表示:</p><p>这里说的椭球都是正椭球,&nbsp;是没有倾斜的那种(如果考虑倾斜的就超级复杂了&nbsp;&nbsp;),&nbsp;用三个半径&nbsp;X,&nbsp;Y,&nbsp;Z,&nbsp;和一个中心点坐标P来表示.如下图:</p><p><img src="UploadFile/2007-5/20075822845734.gif" border="0" alt=""/></p><p>在这个图里,&nbsp;三个半径分别是&nbsp;X=3,&nbsp;Y=7,&nbsp;Z=3</p><p>2.&nbsp;计算椭球下一次位置</p><p>只有发生移动才能发生碰撞,&nbsp;当然只用把椭球的中心坐标P改变位移即可.<br/>P'&nbsp;=&nbsp;P&nbsp;+&nbsp;v</p><p>3.&nbsp;根据新中心坐标P',&nbsp;把待碰撞检测的三角形变换到椭球空间中来(重点)</p><p>假设待碰撞检测的三角形三个顶点为a,&nbsp;b,&nbsp;c.&nbsp;在那个论文中,&nbsp;作者大肆炫耀他的数学知识,&nbsp;总是把一个非常简单的问题解释的又臭又长.&nbsp;说了半天线性代数中基础基的问题,&nbsp;赚取了不少的稿费.&nbsp;&nbsp;<br/>其实这个椭球空间的转换再简单不过了.<br/>我们假设转换后的顶点为a',&nbsp;b',&nbsp;c'</p><p>那么有<br/>a'&nbsp;=&nbsp;CBM&nbsp;*&nbsp;(a&nbsp;-&nbsp;P')<br/>b'&nbsp;=&nbsp;CBM&nbsp;*&nbsp;(b&nbsp;-&nbsp;P')<br/>c'&nbsp;=&nbsp;CBM&nbsp;*&nbsp;(c&nbsp;-&nbsp;P')&nbsp;<br/>其中CBM是一个转换矩阵<br/>[&nbsp;1/X&nbsp;0&nbsp;0]<br/>[&nbsp;0&nbsp;1/Y&nbsp;0]<br/>[&nbsp;0&nbsp;0&nbsp;1/Z]<br/>还记得吗,&nbsp;X,Y,Z是上图椭球的三个半径.</p><p>这样转换后,&nbsp;椭球就变成了一个处在原点,&nbsp;半径为1的正球了(想不过来,仔细想想&nbsp;&nbsp;)<br/>待检测的三角形(a'&nbsp;b'&nbsp;c')就被变换到原点附近,&nbsp;这样就只用判断其与这个半径为1正球的关系就可以知道是否发生碰撞了.&nbsp;&nbsp;</p><p>4.&nbsp;开始碰撞检测了</p><p>I.&nbsp;首先粗略排除绝对不可能相交的.<br/>通过变换后三点(a'&nbsp;b'&nbsp;c')形成一个平面&nbsp;Plane,&nbsp;首先判断此平面到原点的距离,&nbsp;如果大于1则绝对不可能与此待检测的三角形发生碰撞,&nbsp;在这里你可以直接从你的检测函数中退出了.&nbsp;当距离小于或者等于1,&nbsp;再跳到步骤II.</p><p>II.&nbsp;判断是否有任意一点在单位球内.<br/>这也是个快速剔除的方法,&nbsp;如果a'&nbsp;b'&nbsp;c'&nbsp;任意一点到原点的距离小于1,&nbsp;则发生碰撞了,&nbsp;如果都不小于1,&nbsp;则我们需要转到第III步,&nbsp;进行次昂贵的相交测试运算.</p><p>III.&nbsp;边与单位球的相交检测<br/>对于三角形&nbsp;a'&nbsp;b'&nbsp;c'&nbsp;,&nbsp;它有三条边a'b',&nbsp;b'c',&nbsp;c'a',&nbsp;那么我们检测原点到三条边的距离,&nbsp;如果有任意一条小于1,&nbsp;则发生了碰撞,&nbsp;如果非常遗憾的都不小于1的话,&nbsp;我们就进入最昂贵的第四步的碰撞检测.</p><p>IV.&nbsp;最后一步<br/>在前面第一步,&nbsp;我们已经计算出来了a'b'c'&nbsp;组成的平面Plane,&nbsp;这里第一步首先计算出从原点作垂线到Plane的垂足的坐标.&nbsp;然后判断此坐标是否在a'b'c'组成的三角形内.&nbsp;如果在内,&nbsp;则碰撞发生,&nbsp;如果不在内,&nbsp;则无碰撞发生.</p><p><br/>5.&nbsp;是否应该移动到下个位置呢.</p><p>我们可以把3,4步集成到一个函数&nbsp;bool&nbsp;collide(vec3&nbsp;newpos)中,&nbsp;如果我们把P'传进去发生碰撞了,&nbsp;那么我们第2步的坐标改变则不可以发生,&nbsp;如果不考虑滑动的话,&nbsp;则不改变位移,停在原地算了.如果没有发生碰撞,&nbsp;则我们可以大大方方改变原来椭球的中心坐标了,&nbsp;也就是物体可以向前移动了.当然如果移动速度过快,&nbsp;会发生穿墙的问题.&nbsp;这个问题暂时还没有想到如何解决,&nbsp;如果哪位想到了,&nbsp;也可以告诉我.&nbsp;谢谢.</p><p>总结:</p><p>以上的讲解,&nbsp;并未提供详细的代码,&nbsp;关于如何求到面的距离,&nbsp;到直线的距离,&nbsp;也不在这里的讨论范围内,&nbsp;这些算法网上非常多,&nbsp;在那篇老外的论文中,&nbsp;后面也提供了相关的代码,&nbsp;大家可以去看看.</p>
[此贴子已经被作者于2007-5-8 22:08:46编辑过]
页: [1]
查看完整版本: 关于椭球碰撞检测的思考