2

我一直在寻找一些在我的 2D 模拟中实现四叉树的方法，以使碰撞检测更快，但我发现这个概念很难掌握。sim 效果很好，因为现在它只是一旦我超过 160-180 个粒子，它就会变得非常慢，因为碰撞检测会毫无必要地通过所有粒子，而且非常愚蠢。现在它只是一堆或圆圈在屏幕周围相互碰撞，我可以通过单击并拖动鼠标以新的速度和位置产生新的。

编辑1：

好吧，我想我现在可以创建树了，正如您在图像中看到的那样

我的四叉树图片：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);
    }
}
4

1 回答 1

1

我觉得这个概念很难掌握

主意：

  • 单元格的递归分区，因为：

    • 单元格包含固定数量的基元。
    • 发生最大分区数。

  • 从整个场景的边界框开始。

  • 递归：如果单元格中的原语太多，则划分单元格。
  • 空房间不分区（自适应分区）
  • 几何所在的精细分区。

提示：由于层次结构中有许多上下移动，遍历相对昂贵。

  • 将图元保存在内部节点或叶子中。

遍历： - 使用根的轴对齐边界框进行测试（第一：整个场景）

提示：第一个命中不可能是最近的。

简而言之，这就是四叉树或八叉树 (3D) 的原理。我在这里有一张 cg 幻灯片，它用图像进行了描述，但我不想全部上传。我认为这不是您问题的完整答案，但也许会有所帮助。

于 2012-07-14T00:07:50.967 回答