我一直在寻找在我的 2D 模拟中实现四叉树的方法,以使碰撞检测更快,但我发现这个概念很难掌握。 sim 运行良好,因为它现在只是一旦我超过 160-180 个粒子,它就会变得非常慢,因为碰撞检测绝对不必要地通过所有粒子并且非常愚蠢。 现在它只是一堆或圆圈在屏幕上相互碰撞,我可以通过单击并拖动鼠标以新的速度和位置生成新的圆圈。
edit1:
好吧,我想我现在可以创建树了,正如您在图片中看到的那样
我的四叉 TreeMap 像:http://i.stack.imgur.com/c4WNz.jpg
所以现在的问题是如何让它对我的碰撞检测有用...
我每次检查时都必须从零开始创建整棵树吗?
我在等待期间要做的事情,希望它在某种程度上是正确的 :P
1_检查每个节点中是否有球,如果没有则将该节点排除在外。 2_继续检查交叉点,直到我达到叶级别并将那些相交的球添加到叶节点。 3_在我继续前进之前在叶节点中碰撞球??
这是我的 QuadTreeNode 类:
public class QuadTreeNode {
private QuadTreeNode parent;
private QuadTreeNode[] children;
private int id;
private double x;
private double y;
private double width;
private double height;
public QuadTreeNode(double x, double y, double width, double height, int id, QuadTreeNode parent){
this.x = x;
this.y = y;
this.width = width;
this.height = height;
this.children = new QuadTreeNode[4];
this.id = id;
this.parent = parent;
//System.out.println("<x:>"+x+"<y:>"+y+"<w:>"+width+"<h:>"+height);
if (this.width>=1000/12 && this!=null){
nodes+=1;
this.children[0] = new QuadTreeNode(x, y, width/2, height/2, id+1, this);
this.children[1] = new QuadTreeNode(x + width/2, y, width/2, height/2, id+2, this);
this.children[2] = new QuadTreeNode(x, y + height/2, width/2, height/2, id+3, this);
this.children[3] = new QuadTreeNode(x + width/2, y + height/2, width/2, height/2, id+4, this);
}
}
最佳答案
I find the concept quite hard to grasp
想法:
单元格的递归分区,因为:
- 单元格包含固定数量的基元。
- 出现最大分区数。
从整个场景的边界框开始。
- 递归:如果单元格中有太多基元,则划分单元格。
- 如果房间是空的则不划分(自适应分区)
- 几何所在的精分割区。
提示:由于层次结构中的许多上下移动,遍历相对昂贵。
- 将基元保存在内部节点或叶子中。
遍历: - 使用根的轴对齐边界框进行测试(首先:整个场景)
提示:第一个命中不可能是最近的。
简而言之,这就是四叉树或八叉树 (3D) 的原理。我这里有一张 cg 幻灯片,用图片描述了它,但我不想全部上传。我认为那不是您问题的完整答案,但也许会有所帮助。
关于java - 需要有关 Quadtrees java 的帮助,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11479277/