大量圆的碰撞检测

发布于 2024-08-27 10:14:42 字数 936 浏览 5 评论 0原文

检查大量圆圈碰撞的最佳方法是什么？
检测两个圆之间的碰撞非常容易，但如果我们检查每个组合，那么它是O(n²)，这绝对不是最佳解决方案。

我们可以假设圆对象具有以下属性：

坐标
半径
速度
方向

速度是恒定的，但方向可以改变。

我提出了两种解决方案，但也许还有一些更好的解决方案。

解决方案1
将整个空间划分为重叠的正方形，并仅检查与同一正方形中的圆的碰撞情况。正方形需要重叠，这样当圆从一个正方形移动到另一个正方形时就不会有问题。

解决方案2
一开始需要计算每对圆之间的距离。
如果距离很小，那么这些对存储在某个列表中，我们需要在每次更新中检查碰撞。
如果距离很大，那么我们存储后更新可能会发生碰撞（可以计算，因为我们知道距离和速度）。它需要存储在某种优先级队列中。在之前计算出的更新次数之后，需要再次检查距离，然后我们执行相同的过程 - 将其放入列表中或再次放入优先级队列中。

马克·拜尔斯问题的答案

这是一个游戏吗？
它是为了模拟，但也可以被视为一个游戏
你想每n毫秒重新计算一次新位置，并在此时检查是否有碰撞吗？
是的，更新之间的时间是恒定的。
您想查找第一次/每次碰撞发生的时间吗？
不，我想找到每次碰撞并在发生时执行“某些操作”。
准确性有多重要？
这取决于您所说的准确性是什么意思。我需要检测所有碰撞。
如果非常小的快速移动的圆圈偶尔会相互穿过，这是一个大问题吗？
可以假设速度太小以至于不会发生。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

烈酒灼喉 2024-09-03 10:14:42

有“空间索引”数据结构用于存储您的圈子以便以后快速比较；四叉树、r 树和 kd 树就是示例。

解决方案 1 似乎是一个空间索引，而解决方案 2 会在每次重新计算对时从空间索引中受益。

让事情变得复杂的是，你的物体正在移动——它们有速度。

在游戏和模拟中对对象使用空间索引是很正常的，但主要是针对静止对象，并且通常是不会通过移动对碰撞做出反应的对象。

这是游戏中的正常情况，因此您可以按设定的时间间隔（离散）计算所有内容，因此，可能有两个物体相互穿过，但你没有注意到，因为它们移动得太快了。许多游戏实际上甚至不按照严格的时间顺序评估碰撞。他们有一个针对静止物体（例如墙壁）的空间索引，并列出了他们详尽检查的所有移动物体（尽管如我所概述的那样，采用了宽松的离散检查）。

准确的连续碰撞检测以及模拟中物体对碰撞的反应通常要求更高。

您概述的结对方法听起来很有希望。您可以按下一次碰撞对这些对进行排序，并在它们碰撞到适当的新位置时重新插入它们。您只需对两个对象的新生成的碰撞列表 (O(n lg n)) 进行排序，然后合并两个列表（每个对象的新碰撞和现有碰撞列表；插入新碰撞，删除那些碰撞）陈旧的碰撞列出了发生碰撞的两个对象），其时间复杂度为 O(n)。

另一种解决方案是调整空间索引，将对象存储在自上次计算以来所经过的每个扇区中，而不是严格存储在一个扇区中，并离散地执行操作。这意味着在空间结构中存储快速移动的对象，并且您需要针对这种情况对其进行优化。

请记住，链表或指针列表在现代处理器上对于缓存非常不利。我建议您将圆的副本（无论如何，它们对于碰撞检测的重要属性）存储在任何空间索引的每个扇区的数组（顺序内存）中，或者存储在上面概述的对中。

正如马克在评论中所说，并行计算可能非常简单。

There are "spatial index" data-structures for storing your circles for quick comparison later; Quadtree, r-tree and kd-tree are examples.

Solution 1 seems to be a spatial index, and solution 2 would benefit from a spatial index every time you recalculate your pairs.

To complicate matters, your objects are moving - they have velocity.

It is normal to use spatial indexes for objects in games and simulations, but mostly for stationary objects, and typically objects that don't react to a collision by moving.

It is normal in games and such that you compute everything at set time intervals (discrete), so it might be that two objects pass through each other but you fail to notice because they moved so fast. Many games actually don't even evaluate collisions in strict chronological order. They have a spatial index for stationary objects e.g. walls, and lists for all the moving objects that they check exhaustively (although with relaxed discrete checks as I outlined).

Accurate continuous collision detection and where the objects react to collisions in simulations is usually much more demanding.

The pairs approach you outlined sounds promising. You might keep the pairs sorted by next collision, and reinsert them when they have collided in the appropriate new positions. You only have to sort the new generated collision list (O(n lg n)) for the two objects and then to merge two lists (the new collisions for each object, and the existing list of collisions; inserting the new collisions, removing those stale collisions that listed the two objects that collided) which is O(n).

Another solution to this is to adapt your spatial index to store the objects not strictly in one sector but in each that it has passed through since the last calculation, and do things discretely. This means storing fast moving objects in your spatial structure, and you'd need to optimise it for this case.

Remember that linked lists or lists of pointers are very bad for caching on modern processors. I'd advocate that you store copies of your circles - their important properties for collision detection at any rate - in an array (sequential memory) in each sector of any spatial index, or in the pairs you outlined above.

As Mark says in the comments, it could be quite simple to parallelise the calculations.

回复收藏 0 原文

话少情深 2024-09-03 10:14:42

我假设你正在做简单的硬球分子动力学模拟，对吧？我在蒙特卡罗和分子动力学模拟中多次遇到同样的问题。关于模拟的文献中经常提到您的两种解决方案。我个人更喜欢解决方案1，但稍作修改。

解决方案1
将您的空间划分为不重叠的矩形单元。因此，当您检查一个圆是否发生碰撞时，您会查找第一个圆所在单元格内的所有圆，并在周围的每个方向上查找 X 个单元格。我尝试了许多 X 值，发现 X=1 是最快的解决方案。所以你必须将空间划分为每个方向上大小等于的单元格：

Divisor = SimulationBoxSize / MaximumCircleDiameter;
CellSize = SimulationBoxSize / Divisor;

除数应大于3，否则会导致错误（如果太小，你应该放大你的模拟框）。
那么你的算法将如下所示：

将所有圆圈放入框内
创建单元格结构并存储指向单元格内圆圈的索引或指针（在数组或列表上）
及时采取步骤（移动所有内容）并更新内部的圆圈位置细胞
观察每个圆圈是否发生碰撞。您应该在每个方向检查一个单元格
如果发生碰撞 - 执行某些操作
转到 3。

如果您写得正确，那么您将得到大约 O(N) 复杂度，因为最大数量9 个单元格（2D）或 27 个单元格（3D）内的圆对于任何圆总数都是恒定的。

解决方案2
通常，这是这样完成的：

为每个圆创建一个距离 R R R < R_max，计算我们应该更新列表的时间（关于T_update = R_max / V_max；其中V_max是最大当前速度）
及时迈出一步
检查每个圆圈的距离它的列表
如果存在冲突 - 执行某些操作
如果当前时间大于 T_update，则转到 1。
否则转到 2。

通常通过使用 添加另一个列表来改进此列表解决方案R_max_2> R_max 并具有自己的 T_2 过期时间。在此解决方案中，第二个列表用于更新第一个列表。当然，在T_2之后，您必须更新所有列表，其时间为O(N^2)。另请注意 T 和 T_2 时间，因为如果碰撞可以改变速度，那么这些时间也会改变。另外，如果您向系统引入一些力，那么它也会导致速度变化。

解决方案1+2
您可以使用列表进行碰撞检测，使用单元格更新列表。一本书中写道，这是最好的解决方案，但我认为如果您创建小单元（如我的示例），那么解决方案 1 会更好。但这是我的意见。

其他东西
您还可以做其他事情来提高模拟速度：

当您计算距离时 r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ... ) 你不必进行平方根运算。您可以将 r^2 与某个值进行比较 - 没问题。另外，您不必执行所有 (x1-x2)*(x1-x2) 操作（我的意思是，对于所有维度），因为如果 x*x 是比某些 r_collision^2 更大，然后所有其他 y*y 等等，总而言之，会更大。
分子动力学方法很容易并行化。您可以使用线程甚至 GPU 来完成此操作。您可以计算不同线程中的每个距离。在 GPU 上，您可以轻松创建数千个线程，几乎不需要任何成本。

对于硬球体，还有一种有效的算法，它不及时执行步骤，而是及时查找最近的碰撞并跳转到该时间并更新所有位置。它对于不太可能发生碰撞的不密集系统很有用。

I assume you are doing simple hard-sphere molecular dynamic simulation, right? I came accros the same problem many times in Monte Carlo and molecular dynamic simulations. Both of your solutions are very often mentioned in literature about simulations. Personaly I prefer solution 1, but slightly modified.

Solution 1
Divide your space into rectangular cells that don't overlap. So when you check one circle for collision you look for all circles inside a cell that your first circle is, and look X cells in each direction around. I've tried many values of X and found that X=1 is the fastest solution. So you have to divide space into cells size in each direction equal to:

Divisor = SimulationBoxSize / MaximumCircleDiameter;
CellSize = SimulationBoxSize / Divisor;

Divisor should be bigger than 3, otherwise it will cause errors (if it is too small, you should enlarge your simulation box).
Then your algorithm will look like this:

Put all circles inside the box
Create cell structure and store indexes or pointers to circles inside a cell (on array or on a list)
Make a step in time (move everything) and update circles positions inside on cells
Look around every circle for collision. You should check one cell around in every direction
If there is a collision - do something
Go to 3.

If you will write it correctly then you would have something about O(N) complexity, because maximum number of circles inside 9 cells (in 2D) or 27 cells (in 3D) is constant for any total number of circles.

Solution 2
Ususaly this is done like this:

For each circle create a list of circles that are in distance R < R_max, calculate time after which we should update lists (something about T_update = R_max / V_max; where V_max is maximum current velocity)
Make a step in time
Check distance of each circle with circles on its list
If there is a collision - do something
If current time is bigger then T_update, go to 1.
Else go to 2.

This solution with lists is very often improved by adding another list with R_max_2 > R_max and with its own T_2 expiration time. In this solution this second list is used to update the first list. Of course after T_2 you have to update all lists which is O(N^2). Also be carefull with this T and T_2 times, because if collision can change velocity then those times would change. Also if you introduce some foreces to your system, then it will also cause velocity change.

Solution 1+2
You can use lists for collision detection and cells for updating lists. In one book it was written that this is the best solution, but I think that if you create small cells (like in my example) then solution 1 is better. But it is my opinion.

Other stuff
You can also do other things to improve speed of simulation:

When you calculate distance r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...) you don't have to do square root operation. You can compare r^2 to some value - it's ok. Also you don't have to do all (x1-x2)*(x1-x2) operations (I mean, for all dimentions), because if x*x is bigger than some r_collision^2 then all other y*y and so on, summed up, would be bigger.
Molecular dynamics method is very easy to parallelise. You can do it with threads or even on GPU. You can calculate each distance in different thread. On GPU you can easly create thousends of threads almost costless.

For hard-spheres there is also effective algorithm that doesn't do steps in time, but instead it looks for nearest collision in time and jumps to this time and updates all positions. It can be good for not dense systems where collisions are not very probable.

回复收藏 0 原文

牵你的手，一向走下去 2024-09-03 10:14:42

一种可能的技术是在圆的中心使用Delaunay 三角剖分。

考虑每个圆的中心并应用德劳内三角剖分。这会将您的表面细分为三角形。这允许您构建一个图表，其中每个节点存储三角形的中心，每条边都连接到相邻圆的中心。上面操作的曲面细分会将邻居的数量限制为合理的值（平均 6 个邻居），

现在，当圆移动时，您需要考虑碰撞的圆集有限。然后，您必须再次将曲面细分应用于受移动影响的一组圆，但此操作仅涉及很小的圆子集（移动圆的邻居以及邻居的一些邻居），

关键部分是第一次曲面细分需要一些时间来执行，后面的曲面细分不是问题。当然，您需要在时间和空间方面有效地实现图表......

回复收藏 0 原文

嘿哥们儿 2024-09-03 10:14:42

将您的空间细分为多个区域，并维护一个列表，其中列出了每个区域的中心圆。

即使您使用非常简单的方案，例如将所有圆放入列表中，按 center.x 排序，也可以大大加快速度。要测试给定的圆，您只需针对列表中其两侧的圆进行测试，直到到达 x 坐标大于半径的圆。

回复收藏 0 原文

万劫不复 2024-09-03 10:14:42

您可以制作“球体树”的 2D 版本，这是威尔建议的“空间索引”的特殊（并且非常容易实现）情况。这个想法是将圆“组合”成一个“包含”圆，直到得到一个“包含”“大量圆”的圆。

只是为了表明计算“包含圆”的简单性（我的头顶）：
1) 将两个圆的中心位置相加（作为向量）并按 1/2 缩放，即包含圆的中心
2) 减去两个圆的中心位置（作为向量），将半径和比例相加 1/2，即为包含圆的半径

回复收藏 0 原文

绿光 2024-09-03 10:14:42

什么答案最有效将在一定程度上取决于圆圈的密度。如果密度较低，那么在地图上放置一个低分辨率网格并标记那些包含圆圈的网格元素可能是最有效的。每次更新大约需要 O(N*m*k) 时间，其中 N 是圆圈总数，m 是平均数量每个网格点的圆数，k 是一个圆覆盖的平均网格点数。如果一个圆每转移动多个网格点，则必须修改 m 以包含扫描的网格点数量。

另一方面，如果密度非常高，您最好尝试图形遍历方法。让每个圆包含距离 R 内的所有邻居（对于每个圆半径 r_i，R > r_i）。然后，如果你移动，你会查询“向前”方向上的所有圆，寻找它们的邻居，并抓住任何位于 D 内的圆；那么你就忘记了现在比 D 更远的向后方向上的所有那些。现在完整的更新将需要 O(N*n^2) 其中 n 是平均值半径R内的圆数。对于像紧密排列的六角形晶格这样的东西，这会给你比上面的网格方法更好的结果。

回复收藏 0 原文

绅刃 2024-09-03 10:14:42

一个建议 - 我不是游戏开发者

预先计算碰撞何时发生

为什么不按照您指定的方式

我们可以假设圆形对象具有以下属性：
-坐标
-半径
-速度
-方向
速度是恒定的，但方向可以改变。

然后，当一个对象的方向发生变化时，重新计算受影响的那些对。如果方向变化不太频繁，则此方法非常有效。

回复收藏 0 原文

撩人痒 2024-09-03 10:14:42

正如威尔在他的回答中提到的，空间分区树是解决这个问题的常用方法。不过，这些算法有时需要进行一些调整才能有效地处理移动对象。您需要使用松散的桶安装规则，以便大多数移动步骤不需要对象来更换桶。

我之前见过你的“解决方案1”用于解决这个问题，被称为“冲突哈希”。如果您正在处理的空间足够小以便可以管理，并且您希望对象至少模糊地接近均匀分布，那么它可以很好地工作。如果您的对象可能聚集在一起，那么很明显这会导致问题。在每个哈希盒内使用某种类型的分区树的混合方法可以帮助解决此问题，并且可以将纯树方法转换为更容易同时扩展的方法。

重叠区域是处理跨越树桶或哈希盒边界的对象的一种方法。更常见的解决方案是测试与相邻框中的所有对象交叉的边缘的任何对象，或者将对象插入到两个框中（尽管这需要一些额外的处理以避免破坏遍历）。

回复收藏 0 原文

你不是我要的菜∠ 2024-09-03 10:14:42

如果您的代码依赖于“刻度”（并测试以确定对象是否在刻度处重叠），则：

当对象移动“太快”时，它们会相互跳过而不会发生碰撞< /p>
当多个物体在同一个时间点内碰撞时，最终结果（例如，它们如何弹跳，它们受到多少伤害，...）取决于按照您检查碰撞的顺序，而不是碰撞将会/应该发生的顺序。 在极少数情况下，这可能会导致游戏锁定（例如，3 个对象在同一时间点内发生碰撞；对象 1 和对象 2 的碰撞进行调整，然后对象 2 和对象 3 的碰撞进行调整，导致对象 2再次与 object1 碰撞，因此必须重做 object1 和 object2 之间的碰撞，但这会导致 object2 再次与 object3 碰撞，所以...）。

注意：理论上，第二个问题可以通过“递归刻度细分”来解决（如果超过 2 个物体发生碰撞，则将刻度的长度分成两半，然后重试，直到“子细分”中只有 2 个物体发生碰撞）打钩”）。这也可能导致游戏锁定和/或崩溃（当 3 个或更多物体在同一时刻发生碰撞时，最终会出现“永远递归”的情况）。

有时，当游戏开发人员使用“刻度”时，他们也会说“1 个固定长度刻度 = 1 / 可变帧速率”，这是荒谬的，因为应该是固定长度的东西不能依赖于变量（例如，当 GPU 运行时）如果未能达到每秒 60 帧，整个模拟就会以慢动作进行）；如果他们不这样做并使用“可变长度刻度”，那么“刻度”的两个问题都会变得更加严重（特别是在低帧速率下），并且模拟变得不确定（这对于多线程来说可能是有问题的）玩家，并且当玩家保存、加载或暂停游戏时可能会导致不同的行为）。

唯一正确的做法是加上一个维度（时间），给每个物体一条描述为“起始坐标和终止坐标”的线段，加上一条“终止坐标后的轨迹”。当任何对象改变其轨迹时（因为发生了不可预测的事情或因为它到达了“结束坐标”），您可以通过执行“两条线之间的距离<（object1.radius + object2.radius）”来找到“最快”碰撞" 计算发生变化的对象和所有其他对象；然后修改两个对象的“结束坐标”和“结束坐标后的轨迹”。

外部“游戏循环”类似于：

    while(running) {
        frame_time = estimate_when_frame_will_be_visible(); // Note: Likely to be many milliseconds after you start drawing the frame
        while(soonest_object_end_time < frame_time) {
              update_path_of_object_with_soonest_end_time();
        }
        for each object {
            calculate_object_position_at_time(frame_time);
        }
        render();
    }

请注意，有多种方法可以优化它，包括：

将世界分割成“区域” - 例如，如果您知道 object1 将穿过区域 1 和 2，则它不能与任何其他不穿过区域 1 或区域 2 的物体发生碰撞
将对象保留在“end_time % bucket_size”存储桶中，以最大限度地减少查找“下一个最快结束时间”所需的时间
使用多个线程执行“calculate_object_position_at_time(frame_time);”对于并行的每个对象，
所有“直到下一帧时间的高级模拟状态”都与“render()”并行工作（特别是如果大多数渲染由 GPU 完成，从而使 CPU 空闲）。

对于性能：

当碰撞很少发生时，它可以比“滴答声”快得多（您可以在相对较长的时间内几乎不做任何工作）；当您有空闲时间时（无论出于何种原因 - 例如，包括因为玩家暂停了游戏），您可以机会主义地进一步计算未来（有效地“平滑”随着时间的推移而产生的开销，以避免性能峰值）。
当碰撞频繁发生时，它会给你正确的结果，但可能比在相同条件下给你错误结果的破笑话慢。
当碰撞频繁发生时，

它还使得“模拟时间”和“实时”之间的任意关系变得微不足道 - 像快进和慢动作这样的事情不会导致任何中断（即使模拟运行得与硬件可以处理的速度一样快或如此慢）很难判断是否有任何东西在移动）；并且（在没有不可预测性的情况下）您可以提前计算未来的任意时间，并且（如果您存储旧的“对象线段”信息而不是在过期时丢弃它）您可以跳到过去的任意时间，并且（如果您仅在特定时间点存储旧信息以最小化存储成本）您可以跳回到存储信息描述的时间，然后向前计算到任意时间。这些东西结合起来也使得“即时慢动作重放”之类的事情变得很容易。

最后;对于多人游戏场景也更方便，您不想浪费大量带宽在每次更新时向每个客户端发送每个对象的“新位置”。

当然，缺点是复杂性 - 一旦您想要处理诸如加速/减速（重力、摩擦、倾斜运动）、平滑曲线（椭圆轨道、样条线）或不同形状的物体（例如任意网格/多边形而不是球体）之类的事情/圆圈）计算最快碰撞何时发生所涉及的数学变得更加困难和昂贵；这就是为什么游戏开发者采用较差的“刻度”方法来进行比具有线性运动的 N 个球体或圆形更复杂的模拟。

If your code depends on a "tick" (and tests to determine if objects overlap at the tick), then:

when objects are moving "too fast" they skip over each other without colliding
when multiple objects collide in the same tick, the end result (e.g. how they bounce, how much damage they take, ...) depends on the order that you check for collisions and not the order that collisions would/should occur. In rare cases this can cause a game to lock up (e.g. 3 objects collide in the same tick; object1 and object2 are adjusted for their collision, then object2 and object3 are adjusted for their collision causing object2 to be colliding with object1 again, so the collision between object1 and object2 has to be redone but that causes object2 to be colliding with object3 again, so ...).

Note: In theory this second problem can be solved by "recursive tick sub-division" (if more than 2 objects collide, divide the length of the tick in half and retry until only 2 objects are colliding in that "sub-tick"). This can also cause games to lock up and/or crash (when 3 or more objects collide at the exact same instant you end up with a "recurse forever" scenario).

In addition; sometimes when game developers use "ticks" they also say "1 fixed length tick = 1 / variable frame rate", which is absurd because something that is supposed to be a fixed length can't depend on something variable (e.g. when the GPU is failing to achieve 60 frames per second the entire simulation goes in slow motion); and if they don't do this and have "variable length ticks" instead then both of the problems with "ticks" become significantly worse (especially at low frame rates) and the simulation becomes non-deterministic (which can be problematic for multi-player, and can result in different behavior when the player saves, loads or pauses the game).

The only correct way is to add a dimension (time), and give each object a line segment described as "starting coordinates and ending coordinates", plus a "trajectory after ending coordinates". When any object changes its trajectory (either because something unpredicted happened or because it reached its "ending coordinates") you'd find the "soonest" collision by doing a "distance between 2 lines < (object1.radius + object2.radius)" calculation for the object that changed and every other object; then modify the "ending coordinates" and "trajectory after ending coordinates" for both objects.

The outer "game loop" would be something like:

    while(running) {
        frame_time = estimate_when_frame_will_be_visible(); // Note: Likely to be many milliseconds after you start drawing the frame
        while(soonest_object_end_time < frame_time) {
              update_path_of_object_with_soonest_end_time();
        }
        for each object {
            calculate_object_position_at_time(frame_time);
        }
        render();
    }

Note that there are multiple ways to optimize this, including:

split the world into "zones" - e.g. so that if you know object1 would be passing through zones 1 and 2 then it can't collide with any other object that doesn't also pass through zone 1 or zone 2
keep objects in "end_time % bucket_size" buckets to minimize time taken to find "next soonest end time"
use multiple threads to do the "calculate_object_position_at_time(frame_time);" for each object in parallel
do all the "advance simulation state up to next frame time" work in parallel with "render()" (especially if most rendering is done by GPU, leaving CPU/s free).

For performance:

When collisions occur infrequently it can be significantly faster than "ticks" (you can do almost no work for relatively long periods of time); and when you have spare time (for whatever reason - e.g. including because the player paused the game) you can opportunistically calculate further into the future (effectively, "smoothing out" the overhead over time to avoid performance spikes).
When collisions occur frequently it will give you the correct results, but can be slower than a broken joke that gives you incorrect results under the same conditions.

It also makes it trivial to have an arbitrary relationship between "simulation time" and "real time" - things like fast forward and slow motion will not cause anything to break (even if the simulation is running as fast as hardware can handle or so slow that its hard to tell if anything is moving at all); and (in the absence of unpredictability) you can calculate ahead to an arbitrary time in the future, and (if you store old "object line segment" information instead of discarding it when it expires) you can skip to an arbitrary time in the past, and (if you only store old information at specific points in time to minimize storage costs) you can skip back to a time described by stored information and then calculate forward to an arbitrary time. These things combined also make it easy to do things like "instant slow motion replay".

Finally; it's also more convenient for multiplayer scenarios, where you don't want to waste a huge amount of bandwidth sending a "new location" for every object to every client at every tick.

Of course the downside is complexity - as soon as you want to deal with things like acceleration/deceleration (gravity, friction, lurching movement), smooth curves (elliptical orbits, splines) or different shaped objects (e.g. arbitrary meshes/polygons and not spheres/circles) the mathematics involved in calculating when the soonest collision will occur becomes significantly harder and more expensive; which is why game developers resort to the inferior "ticks" approach for simulations that are more complex than the case of N spheres or circles with linear motion.

回复收藏 0 原文

~没有更多了~