文档章节

HTML5实现3D和2D可视化QuadTree四叉树碰撞检测

xhload3d
 xhload3d
发布于 2015/12/14 00:34
字数 1294
阅读 3.5K
收藏 68

行业解决方案、产品招募中!想赚钱就来传!>>>

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
    });
}

 


xhload3d
粉丝 213
博文 223
码字总数 474167
作品 0
崇明
私信 提问
加载中
此博客有 3 条评论,请先登录后再查看。
用vertx实现高吞吐量的站点计数器

工具:vertx,redis,mongodb,log4j 源代码地址:https://github.com/jianglibo/visitrank 先看架构图: 如果你不熟悉vertx,请先google一下。我这里将vertx当作一个容器,上面所有的圆圈要...

jianglibo
2014/04/03
3.9K
3
SQLServer实现split分割字符串到列

网上已有人实现sqlserver的split函数可将字符串分割成行,但是我们习惯了split返回数组或者列表,因此这里对其做一些改动,最终实现也许不尽如意,但是也能解决一些问题。 先贴上某大牛写的s...

cwalet
2014/05/21
9.6K
0
Swift百万线程攻破单例(Singleton)模式

一、不安全的单例实现 在上一篇文章我们给出了单例的设计模式,直接给出了线程安全的实现方法。单例的实现有多种方法,如下面: class SwiftSingleton { } 这段代码的实现,在shared中进行条...

一叶博客
2014/06/20
3.3K
16
beego API开发以及自动化文档

beego API开发以及自动化文档 beego1.3版本已经在上个星期发布了,但是还是有很多人不了解如何来进行开发,也是在一步一步的测试中开发,期间QQ群里面很多人都问我如何开发,我的业余时间实在...

astaxie
2014/06/25
2.7W
22
mvc框架--Razor

Razor 是一个轻巧而优雅的servlet mvc框架 # 又一个轮子? no,写就她是为了证实我个人的某些想法,并在这个过程中练练手,这两种冲动碰撞在一起,自然而然地产生了Razor # Razor的现在和未来...

dtubest
2013/01/25
2.9K
0

没有更多内容

加载失败,请刷新页面

加载更多

揭秘神秘的MarxDB

主题:MarxDB金融级分布式数据库 大纲: 1、石老师好像是第一次来3306π,可以先重点自我介绍一下。 2、石老师可以简单介绍一下MarxDB的情况吗? 3、跟传统的关系型数据库相比,MarxDB有什么...

叶金荣
昨天
0
0
ASP.NET Core搭建多层网站架构【13-扩展之支持全球化和本地化多语言】

2020/02/03, ASP.NET Core 3.1, VS2019, ResXManager 摘要:基于ASP.NET Core 3.1 WebApi搭建后端多层网站架构【13-扩展之支持全球化和本地化多语言】 使用资源管理多语言文件实现网站本地化...

osc_wip0vvls
22分钟前
9
0
浙江移动正式采用蚂蚁集团自研数据库OceanBase

近日,浙江移动正式引入蚂蚁集团的自研数据库OceanBase,首期应用于其政企网格智慧运营系统,这也是OceanBase首次落地于运营商场景。 政企网格智慧运营平台是浙江移动针对政企用户推出的服务...

支付宝技术
昨天
9
0
使用Charles代理功能将网络请求定向至本地文件

  最近在进行前端开发的时候发现Charles一个非常牛叉的功能,就是可以通过代理将网络请求定向至本地文件。有了这个功能在进行iOS开发时就可以在缺少后台接口的情况下更加真实的进行数据moc...

osc_qvtw8r10
23分钟前
7
0
多边形裁剪图片升级啦!Cocos Creator !

支持合图,支持gizmo添加节点和调整位置,支持缩放旋转。文章底部获取完整项目! 效果预览与使用 原理 回顾 在gizmo入门探索介绍了 gizmo 与多边形裁剪的配合。 在使用 mesh 实现多边形裁剪图...

白玉无冰
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部