HTML5实现3D和2D可视化QuadTree四叉树碰撞检测
博客专区 > xhload3d 的博客 > 博客详情
HTML5实现3D和2D可视化QuadTree四叉树碰撞检测
xhload3d 发表于2年前
HTML5实现3D和2D可视化QuadTree四叉树碰撞检测
  • 发表于 2年前
  • 阅读 3200
  • 收藏 69
  • 点赞 5
  • 评论 3

腾讯云 技术升级10大核心产品年终让利>>>   

摘要: QuadTree四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域。QuadTree常用于空间数据库索引,3D的椎体可见区域裁剪,甚至图片分析处理,我们今天介绍的是QuadTree最常被游戏领域使用到的碰撞检测。采用QuadTree算法将大大减少需要测试碰撞的次数,从而提高游戏刷新性能,本文例子基于HT for Web的Canvas拓扑图和WebGL的3D引擎组件,通过GraphView和Graph3dView共享同一数据模型DataModel,同时呈现QuadTree算法下的2D和3D碰撞视图效果:

QuadTree四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域。QuadTree常用于空间数据库索引,3D的椎体可见区域裁剪,甚至图片分析处理,我们今天介绍的是QuadTree最常被游戏领域使用到的碰撞检测。采用QuadTree算法将大大减少需要测试碰撞的次数,从而提高游戏刷新性能,本文例子基于HT for Web的Canvas拓扑图和WebGL的3D引擎组件,通过GraphViewGraph3dView共享同一数据模型DataModel,同时呈现QuadTree算法下的2D和3D碰撞视图效果:http://v.youku.com/v_show/id_XODQyNTA1NjY0.html

http://www.hightopo.com/demo/QuadTree/ht-quadtree.html

Screen Shot 2014-12-06 at 12.41.24 AM

QuadTree的实现有很多成熟的版本,我选择的是 https://github.com/timohausmann/quadtree-js/ 四叉树的算法很简单,因此这个开源库也就两百来行代码。使用也非常简单,构建一个Quadtree对象,第一个参数传入rect信息制定游戏空间范围,在每次requestAnimationFrame刷新帧时,先通过quadtree.clear()清除老数据,通过quadtree.insert(rect)插入新的节点矩形区域,这样quadtree就初始化好了,剩下就是根据需要调用quadtree.retrieve(rect)获取指定矩形区域下,与其可能相交需要检测的矩形对象数组。

我构建了HT(http://www.hightopo.com/)的GraphViewGraph3dView两个组件,通过ht.widget.SplitView左右分割,由于两个视图都共享同一DataModel,因此我们剩下的关注点仅是对DataModel的数据操作,构建了200个ht.Node对象,每个对象的attr属性上保存了随机的运动方向vx和vy,同时保存了将要反复插入quadtree的矩形对象,这样避免每帧更新时反复创建对象,同时矩形对象也引用了ht.Node对象,用来当通过quadtree.retrieve(rect)获取需要检测的矩形对象时,我们能指定其所关联的ht.Node对象,因为我们需要对最终检测为碰撞的图元设置上红颜色的效果,也就是ht.Node平时显示默认的蓝色,当互相碰撞时将改变为红色。

需要注意从quadtree.retrieve(rect)获取需要检测的矩形对象数组中会包含自身图元,同时这些仅仅是可能会碰撞的图元,并不意味着已经碰撞了,由于我们例子是矩形,因此采用ht.Default.intersectsRect(r1, r2)最终判断是否相交,如果你的例子是圆形则可以采用计算两个圆心距离是否小于两个半径来决定是否相交,因此最终判断的标准根据游戏类型会有差异。

采用了QuadTree还是极大了提高了运算性能,否则100个图元就需要100*100次的监测,我这个例子场景下一般也就100*(10~30)的量:http://v.youku.com/v_show/id_XODQyNTA1NjY0.html

http://www.hightopo.com/demo/QuadTree/ht-quadtree.html


Screen Shot 2014-12-06 at 12.42.35 AM

除了碰撞检测外QuadTree算法还有很多有趣的应用领域,有兴趣可以玩玩这个 https://github.com/fogleman/Quads

Screen Shot 2014-12-06 at 12.52.17 AM

所有代码如下供参考:

function init(){  
    d = 200;
    speed = 8;
    dataModel = new ht.DataModel();                                
    g3d = new ht.graph3d.Graph3dView(dataModel);                                                  
    g2d = new ht.graph.GraphView(dataModel);                   
    mainSplit = new ht.widget.SplitView(g3d, g2d);                   
    mainSplit.addToDOM();                                        
    g2d.translate(300, 220);      
    g2d.setZoom(0.8, true);
      
    for(var i=0; i<100; i++) {
        var node = new ht.Node();
        node.s3(randMinMax(5, 30), 10, randMinMax(5, 30));
        node.p3(randMinMax(-d/2, d/2), 0, randMinMax(-d/2, d/2));
        node.s({
            'batch': 'group',
            'shape': 'rect',
            'shape.border.width': 1,
            'shape.border.color': 'white',
            'wf.visible': true,
            'wf.color': 'white'
        });
        node.a({
            vx: randMinMax(-speed, speed),
            vy: randMinMax(-speed, speed),
            obj: {
                width: node.getWidth(),
                height: node.getHeight(),
                data: node
            }
        });                    
        dataModel.add(node);
    }                
    createShape([
        {x: -d, y: d},
        {x: d, y: d},
        {x: d, y: -d},
        {x: -d, y: -d},
        {x: -d, y: d}
    ]);                   
    quadtree = new Quadtree({ x: -d, y: -d, width: d, height: d });                                
    requestAnimationFrame(update);
}               
function update() {   
    quadtree.clear();                
    dataModel.each(function(data){
        if(!(data instanceof ht.Shape)){
            var position = data.getPosition();
            var vx = data.a('vx');
            var vy = data.a('vy');
            var w = data.getWidth()/2;
            var h = data.getHeight()/2;
            var x = position.x + vx;
            var y = position.y + vy;
            if(x - w < -d){
                data.a('vx', -vx);
                x = -d + w;
            }
            if(x + w > d){
                data.a('vx', -vx);
                x = d - w;
            }
            if(y - h < -d){
                data.a('vy', -vy);
                y = -d + h;
            }
            if(y + h > d){
                data.a('vy', -vy);
                y = d - h;
            }
            data.setPosition(x, y);                        
            var obj = data.a('obj');
            obj.x = x - w;
            obj.y = y - h;
            
            quadtree.insert(obj);
            setColor(data, undefined);
        }
    });                
    dataModel.each(function(data){
        if(!(data instanceof ht.Shape)){ 
            var obj = data.a('obj');
            var objs = quadtree.retrieve(obj);
            if(objs.length > 1){                            
                for(var i=0; i<objs.length; i++ ) {
                    var data2 = objs[i].data;
                    if(data === data2){
                        continue;
                    }
                    if(ht.Default.intersectsRect(obj, data2.a('obj'))){
                        setColor(data, 'red');
                        setColor(data2, 'red');
                    }                                
                }                             
            }
        }
    });
    requestAnimationFrame(update);                    
}                        
function randMinMax(min, max) {
    return min + (Math.random() * (max - min));
}                      
function createShape(points){
    shape = new ht.Shape();
    shape.setPoints(points);
    shape.setThickness(4);
    shape.setTall(10);                                
    shape.s({
        'all.color': 'red',
        'shape.background': null,
        'shape.border.width': 2,
        'shape.border.color': 'red'                    
    });                
    dataModel.add(shape); 
    return shape;
}
function setColor(data, color){
    data.s({
        'all.color': color,
        'shape.background': color
    });
}

 


共有 人打赏支持
粉丝 149
博文 121
码字总数 212379
评论 (3)
开源无憾
为啥有种会卡的蛋疼的感觉
百世经纶之傲笑红尘
js单线程模型下负责操作,例如大量三维图形绘制下,可能会卡
非会员用户
百度: OURLINK安全通道 你就知道什么是OURLINK 详细了解。。www.17fan.cc(一起翻)
×
xhload3d
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: