首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >超越交集测试的碰撞检测

问超越交集测试的碰撞检测
EN

Stack Overflow用户
提问于 2013-07-08 16:06:49
回答 1查看 121关注 0票数 0

为了澄清这个问题的目的,想象一个二维游戏,玩家控制一个小的精灵,可以给出任意的速度。它只受重力作用。它最初位于一个跨越屏幕底部大部分的大型平台上,而在屏幕上方的一个很小的距离则是另一个小得多的平台。如果精灵直接跳起来,它就能通过平台底部,在上面移动一段时间,然后降落在上面的平台上。它可以通过底部,但不能向下通过顶部。

要做到这一点,可以将屏幕上对象的每一条坚实的边缘看作一个向量,可以从右、左或两者通过;在示例中,主基础平台的顶部需要一条边缘(如果它从右角指向左侧,则从右到左),另一条用于较小的平台顶部,另一条用于雪碧(如果它是一个小矩形的话)。如果一个点从错误的方向穿过边缘,它会向冲突解决算法发送一个信号,以确保该点不会这样做。

这一切都很好,唯一的问题是它不是很有效率。利用传统的碰撞检测机制,正方形是一个物体。如果你有一个n个正方形的列表来测试碰撞,你最多只能运行--最多;大多数方法都会收缩这个数-n个平方碰撞测试。用点边法,每个正方形大约有四个边,每个边都有两个端点需要测试。这意味着对于n个正方形,你将运行(8n)平方碰撞测试。64倍的碰撞测试;这太糟糕了。

那么,基本上,是否有任何广泛使用或被接受的碰撞检测方法将完成与点边缘方法相同的事情,但不会过度负担计算机的处理能力?请注意,这实际上只适用于2D;它的意思是让事物层表示一种内轴,而3D完全能够表示空间的所有三个维度,不需要增加。

EN

回答 1

Stack Overflow用户

发布于 2014-01-30 02:20:53

这通常是使用四叉树的包围盒.树的每个节点都有包围其直接子节点的边界。对于n个节点,最多需要k个log( N)比较。这是一个二维的二元搜索。

请注意,包围框不一定与您的方格完全对应。他们是网格对齐的廉价命中测试通过范围比较。

一旦你击中了一个原子的包围盒,就对原子做一个完整的撞击测试。

这种方法最常与多边形命中测试结合使用,对于多个边的多边形(不要称它们为复多边形,复杂多边形是与相交边“扭曲”的多边形),这是相当昂贵的。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/17531183

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档