高级碰撞检测技术　第一部分

高级碰撞检测技术　第部分
Advanced Collision Detection Techniques

这文章原载于Gamasutra共有 3部分我想将它翻译请大家指教

http://www.gamasutra.com/features/20000330/bobic_01.htm
http://www.gamasutra.com/features/20000330/bobic_02.htm
http://www.gamasutra.com/features/20000330/bobic_03.htm


/ 1 ………………………………………………………………………………………………….
自从电脑游戏降临以来员们不断地设计各种思路方法去模拟现实世界例如Pong(著名碰球游戏)展示了个动人场面(个球及两根摆绳)当玩家将拽住摆绳移动到定高度然后放开球球就会离开玩家向对手冲去以今天标准这样基础操作也许就是原始碰撞检测起源现在电脑游戏比以前Pong复杂多了而且更多是基于3D这也使3D碰撞检测困难要远远高于个简单2D Pong些较早飞行模拟游戏介绍说明了糟糕碰撞检测技术是怎样破坏个游戏如:当你飞机撞到座山峰时候你居然还可以安全幸存下来这在现实中是不可能发生甚至最近刚出些游戏也存在此类问题许多玩家对他们喜爱英雄或是女英雄部分身体居然可以穿过墙而感到失望甚至更坏是玩家被颗没有和他发生碰撞关系火箭击中今天玩家要求增加唯实论要求越来越高我们游戏开发者们将尽可能在我们游戏世界做些改进以便接近真实世界
　　 Since the advent of computer games, programmers have continually devised ways to simulate the world more precisely. Pong, for instance, featured a moving square (a ball) and two paddles. Players had to move the paddles to an appropriate position at an appropriate time, thus rebounding the ball toward the opponent and away from the player. The root of this basic operation is primitive(by today’s standards) collision detection. Today’s games are much more advanced than Pong, and most are based in 3D. Collision detection in 3D is many magnitudes more dficult to implement than a simple 2D Pong game. The experience of playing some of the early flight simulators illustrated how bad collision detection can ruin a game. Flying through a mountain peak and surviving isn’t very realistic. Even some recent games have exhibited collision problems. Many game players have been disappoed by the sight of their favorite heroes or heroines with parts of their bodies inside rigid walls. Even worse, many players have had the experience of being hit by a rocket or bullet that was “not even close” to them. Because today’s players demand increasing levels of realism, we developers will have to do some hard thinking in order to approximate the real world in our game worlds as closely as possible.

/ 2 …………………………………………………………………………………………………
这篇碰撞检测论文会使用些基础几何学及数学知识在文章结束我也会提供些参考文献给你我假定你已经读过Jeff Lander写图形教程中碰撞检测部分(“Crashing o the New Year,” ; “When Two Hearts Collide,”; and “Collision Response: Bouncy, Trouncy, Fun,” )我将给你些图片让你能快速联系起核心例程我们将要讨论碰撞检测是基于portal-based 及BSP-based 两种类型引擎每个引擎都有自己组织结构这使得虚拟世界物体碰撞检测技术也不尽相同面向对象碰撞检测是使用得比较多但这取决于你现实可实性就想将引擎分成两部分样稍后我们会概述多边形碰撞检测也会研究如何扩展我们弯曲物体
This article will assume a basic understanding of the geometry and math involved in collision detection. At the end of the article, I’ll provide some references in you feel a bit rusty in this area. I’ll also assume that you’ve read Jeff Lander’s Graphic Content columns _disibledevent=>


/ 4 …………………………………………………………………………………………………
让我们来看看个游戏基本循环引擎(Listing 1)
http://www.gamasutra.com/features/20000330/bobic_l1.htm
这段代码简要阐明了我们碰撞检测想法我们假设碰撞没发生并且更新物体位置如果我们发现碰撞发生了我们移动物体回来并且不允许它通过边界(或删除它或采取些另外预防措施)然而我们不知道物体先前位置是否仍然是可得到这个假设是太过分简单化你必须为这种情况设计个解决方案(否则你将可能经历碰撞而你将被粘住)如果你是个细心玩家你可能在游戏中会注意到当你走近面墙并且试图通过它时你会看见墙开始动摇你正在经历是感动运动返回来效果动摇是个粗糙时间坡度结果(时间片)
Let’s begin by taking a look at a basic game engine loop (Listing 1). A quick scan of this code reveals our strategy for collision detection. We assume that collision has not occurred and update the object’s position. If we find that a collision has occurred, we move the object back and do not allow it to pass the boundary (or destroy it or take some other preventative measure). However, this assumption is too simplistic because we don’t know the object’s previous position is still available. You’ll have to devise a scheme for what to do in this (otherwise, you’ll probably experience a crash or you’ll be stuck). If you’re an avid game player, you’ve probably noticed that in some games, the view starts to shake when you approach a wall and try to go through it. What you’re experiencing is the effect of moving the player back. Shaking is the result of a coarse time gradient (time slice).

/ 5 …………………………………………………………………………………………………
但是我们思路方法是有缺陷我们忘记在我们方程中加入时间图1显示了时间重要性因而它不能省去就算个物体不在时间 t1 或 t2 抵触它可以在时间t1 < t < t2穿过t边界哪儿这是非常正确我们已经有大而连续框架可操作我们会发现必须还要个好思路方法来处理差异
But our method is flawed. We forgot to the time in our equation. Figure 1 shows that time is just too important to leave out. Even an object doesn’t collide at time t1 or t2, it may cross the boundary at time t where t1 < t < t2. This is especially true when we have large jumps between successive frames (such as when the user hit an afterburner or something like that). We\'ll have to find a good way to deal with discrepancy as well.

/ 6 …………………………………………………………………………………………………
我们应该将时间作为第4维也加入到所有计算中去这些使得计算变得很复杂然而我们只能舍弃它们我们也可从原来物体在时间 t1 和 t2 的间占据然后靠着墙测试结果(图 2 )
We could treat time as a fourth dimension and do all of our calculations in 4D. These calculations can get very complex, however, so we’ll stay away from them. We could also create a solid out of the space that the original object occupies between time t1 and t2 and then test the resulting solid against the wall (Figure 2).

/ 7 …………………………………………………………………………………………………
条简单途径就是在 2 区别时间在个物体地点附近创造凸壳这条途径效率很低并且毫无疑问它会降低你游戏执行速度如果不建立凸壳我们可以在物体附近建立个范围框在我们熟悉几种技术后我们要再次回到这个问题上
An easy approach is to create a convex hull around an object’s location at two dferent times. This approach is very inefficient and will definitely slow down your game. Instead of constructing a convex hull, we could construct a bounding box around the solid. We’ll come back to this problem _disibledevent=>(N choose 2) comparisons. Thus, the number of comparisons that we’ll need to perform is of order N2 (or O(N2)). But we can avoid performing O(N2) pair-wise comparisons in _disibledevent=>

\" width=500>

延伸阅读