phi*_*131 13 algorithm simulation collision-detection
我想编写一个模拟许多粒子碰撞的小程序,首先从2D开始(我稍后将其扩展到3D),到(在3D中)模拟向Boltzmann分布的收敛,并且还看到分布如何在2D中演化.
我还没有开始编程,所以请不要问代码示例,这是一个相当普遍的问题,应该可以帮助我开始.这个问题背后的物理问题对我没有任何问题,而事实是我必须模拟至少200-500个粒子,以实现非常好的速度分布.我想实时做到这一点.
现在,对于每个时间步,我将首先更新所有粒子的位置,然后检查碰撞,以更新新的速度矢量.然而,这包括很多检查,因为我必须看看每个粒子是否与其他每个粒子发生碰撞.我发现这个帖子或多或少都是同一个问题,而且那里使用的方法也是我唯一能想到的.但是,我担心这不会在实时工作得很好,因为它会涉及太多的碰撞检查.
所以现在:即使这种方法在性能上有所提升(说得40fps),有人可以想办法避免不必要的碰撞检查吗？
我自己的想法是将板(或3D:空间)分成具有至少粒子直径的尺寸的正方形(立方体),并且如果两个粒子的中心在adjecent正方形内,则实现仅检查碰撞的方式在网格中......
我很乐意听到更多的想法,因为我想尽可能多地增加粒子数量,并且仍在进行实时计算/模拟.
编辑:所有碰撞都是纯粹的弹性碰撞,没有任何其他力量对粒子进行处理.我将实现的初始情况由用户选择的一些变量确定,以选择随机起始位置和速度.
EDIT2:我发现了粒子碰撞的模拟一个很好的和非常有益的纸在这里.希望它可以帮助一些对更深层次感兴趣的人.
如果你想起来了,移动的计划颗粒是一个真正的3D系统,其中三个维度x,y时间(t).
让我们说一个"时间步骤"从那里t0开始t1.对于每个粒子,您P0(x0, y0, t0)可以P1(x1, y1, t1)根据当前粒子位置,速度和方向创建一个3D线段.
在3D网格中划分3D空间,并将每个3D线段链接到它穿过的单元格.
现在,应检查每个网格单元.如果它链接到0或1段,则无需进一步检查(将其标记为已选中).如果它包含2个或更多段,则需要检查它们之间的碰撞:计算3D碰撞点Pt,缩短两个段以此时结束(并删除它们不再交叉的单元的链接),创建两个新段从去Pt到新计算P1根据颗粒的新的方向/速度点.将这些新线段添加到网格中,并将单元格标记为已选中.向网格添加线段会将所有交叉单元格转换为未选中状态.
当您的网格中没有未经检查的单元格时,您已经解决了时间步问.
编辑
空间划分的一个很好的高级例子是考虑乒乓球的比赛,并检测球和桨之间的碰撞.
假设桨位于屏幕的左上角,球接近屏幕的左下角......
--------------------
|? |
| |
| |
| ? |
--------------------
每次球移动时都没有必要检查碰撞.相反,将比赛场分成中间两个.球是球场的左侧吗？(矩形算法中的简单点)
Left Right
|
---------|----------
|? | |
| | |
| | |
| ? | |
---------|----------
|
如果答案是肯定的,再次将左侧分开,这次是水平分割,因此我们有一个左上角和一个左下角分区.
Left Right
|
---------|----------
|? | |
| | |
----------- |
| | |
| ? | |
---------|----------
|
这个球是否和屏幕一样在屏幕的左上角？如果没有,不需要检查碰撞!只有位于同一分区中的对象才需要进行相互冲突测试.通过一系列简单(且便宜)的内部矩形检查,您可以轻松地避免进行更昂贵的形状/几何碰撞检查.
您可以继续将空间拆分为越来越小的块,直到对象跨越两个分区.这是BSP背后的基本原理(在像Quake这样的早期3D游戏中开创的技术).网络上有大量关于2维和3维空间划分的理论.
http://en.wikipedia.org/wiki/Space_partitioning
在2维中,您经常使用BSP或四叉树.在3个维度中,您经常使用八叉树.然而,基本原则保持不变.
| 归档时间： |
|
| 查看次数： |
10298 次 |
| 最近记录： |