文档章节

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

xhload3d
 xhload3d
发布于 2015/12/14 00:34
字数 1294
阅读 3240
收藏 69
点赞 5
评论 3

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
粉丝 175
博文 147
码字总数 286340
作品 0
崇明
加载中

评论(3)

百度: OURLINK安全通道 你就知道什么是OURLINK 详细了解。。www.17fan.cc(一起翻)
百世经纶之傲笑红尘
百世经纶之傲笑红尘
js单线程模型下负责操作,例如大量三维图形绘制下,可能会卡
开源无憾
开源无憾
为啥有种会卡的蛋疼的感觉
HT for Web可视化QuadTree四叉树碰撞检测

QuadTree四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域。QuadTree常用于空间数据库索引,3D的椎体可见区域裁剪,甚至图片分析处理,我们今天介绍...

xhload3d ⋅ 2014/12/06 ⋅ 0

[Qt] 我的一款射击游戏及设计模式 - Hori Miona

时间:2017年7月28日-7月30日 耗时:2天 此前一直在玩OpenGL,做的都是三维世界的东西,已经好久没有写过2D类的小游戏了。上学期,玩了《charles》之后,就一直想要写一款类似的射击类小游戏...

Mahabharata_ ⋅ 2017/08/01 ⋅ 0

四叉树与八叉树

前序 四叉树或四元树也被称为Q树(Q-Tree)。四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等,而八叉树(Octree)主要应用于3D图形处理。对游戏编程,这会很有...

zhanxinhang ⋅ 2011/08/21 ⋅ 0

白鹭引擎 5.3.0 正式发布,支持 3D 游戏开发

一直关注白鹭引擎的童靴会发现,今天白鹭引擎先后完成了白鹭引擎5.2.0、白鹭引擎5.3.0两个版本的更迭,在周三发布《白鹭引擎稳定版即将发布,后续路线图同步公开》文中,我们已详细介绍了白鹭...

白鹭科技 ⋅ 05/25 ⋅ 0

超级绚丽,20款前端动画特效,轰炸你的眼睛

前言 HTML5一个相当出色的web技术,它不仅可以让你更加方便地操纵页面元素,而且可以通过canvas实现更多的动画特效,引进HTML5标准后,CSS3也就可以发挥更大的作用。本文主要介绍了一些基于H...

浪漫程序员 ⋅ 04/25 ⋅ 0

扣丁学堂HTML5培训课程怎么样

  在如今,随着移动互联网技术的发展和进步,比如HTML5在移动互联端的应用,让更多人了解到它的丰富性趣味性便利性,但HTML5就包括这些么?扣丁学堂HTML5培训课程怎么样?零基础能学会么?...

扣丁学堂 ⋅ 06/01 ⋅ 0

白鹭引擎 5.1.11 发布,集中修复数个 Bug

白鹭引擎5.1.11版本将于5月7日上线,本次版本的推出是对去年12月份发布的5.1版引擎的一次集中性缺陷修复。同时我们要再一次感谢多位开发者通过Egret社区等渠道提交的Bug反馈。5.1.11版本引擎...

白鹭科技 ⋅ 05/07 ⋅ 1

基于HTML5的电信网管3D机房监控应用

先上段视频,不是在玩游戏哦,是规规矩矩的电信网管企业应用,嗯,全键盘的漫游3D机房: 随着PC端支持HTML5浏览器的普及,加上主流移动终端Android和iOS都已支持HTML5技术,新一代的电信网管应...

xhload3d ⋅ 2014/02/22 ⋅ 1

HTML5学习之Web Storage基础知识

HTML5 Web 存储 在HTML5 Web Storage还没出来之前,本地存储使用的是 cookie. 但是Web 存储需要更加的安全与快速,这些数据不会被保存在服务器上,但是这些数据只用于用户请求网站数据上.它也可...

CHIEMINCHAN ⋅ 05/11 ⋅ 0

基于HTML5的WebGL电信网管3D机房监控应用

先上段视频,不是在玩游戏哦,是规规矩矩的电信网管企业应用,嗯,全键盘的漫游3D机房: http://www.hightopo.com/guide/guide/core/3d/examples/example3droom.html 随着PC端支持HTML5浏览器...

xhload3d ⋅ 2015/11/07 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Centos7重置Mysql 8.0.1 root 密码

问题产生背景: 安装完 最新版的 mysql8.0.1后忘记了密码,向重置root密码;找了网上好多资料都不尽相同,根据自己的问题总结如下: 第一步:修改配置文件免密码登录mysql vim /etc/my.cnf 1...

豆花饭烧土豆 ⋅ 31分钟前 ⋅ 0

熊掌号收录比例对于网站原创数据排名的影响[图]

从去年下半年开始,我在写博客了,因为我觉得业余写写博客也还是很不错的,但是从2017年下半年开始,百度已经推出了原创保护功能和熊掌号平台,为此,我也提交了不少以前的老数据,而这些历史...

原创小博客 ⋅ 今天 ⋅ 0

LVM讲解、磁盘故障小案例

LVM LVM就是动态卷管理,可以将多个硬盘和硬盘分区做成一个逻辑卷,并把这个逻辑卷作为一个整体来统一管理,动态对分区进行扩缩空间大小,安全快捷方便管理。 1.新建分区,更改类型为8e 即L...

蛋黄Yolks ⋅ 今天 ⋅ 0

Hadoop Yarn调度器的选择和使用

一、引言 Yarn在Hadoop的生态系统中担任了资源管理和任务调度的角色。在讨论其构造器之前先简单了解一下Yarn的架构。 上图是Yarn的基本架构,其中ResourceManager是整个架构的核心组件,它负...

p柯西 ⋅ 今天 ⋅ 0

uWSGI + Django @ Ubuntu

创建 Django App Project 创建后, 可以看到路径下有一个wsgi.py的问题 uWSGI运行 直接命令行运行 利用如下命令, 可直接访问 uwsgi --http :8080 --wsgi-file dj/wsgi.py 配置文件 & 运行 [u...

袁祾 ⋅ 今天 ⋅ 0

JVM堆的理解

在JVM中,我们经常提到的就是堆了,堆确实很重要,其实,除了堆之外,还有几个重要的模块,看下图: 大 多数情况下,我们并不需要关心JVM的底层,但是如果了解它的话,对于我们系统调优是非常...

不羁之后 ⋅ 昨天 ⋅ 0

推荐:并发情况下:Java HashMap 形成死循环的原因

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环。这个事情我4、5年前也经历...

码代码的小司机 ⋅ 昨天 ⋅ 2

聊聊spring cloud gateway的RetryGatewayFilter

序 本文主要研究一下spring cloud gateway的RetryGatewayFilter GatewayAutoConfiguration spring-cloud-gateway-core-2.0.0.RC2-sources.jar!/org/springframework/cloud/gateway/config/G......

go4it ⋅ 昨天 ⋅ 0

创建新用户和授予MySQL中的权限教程

导读 MySQL是一个开源数据库管理软件,可帮助用户存储,组织和以后检索数据。 它有多种选项来授予特定用户在表和数据库中的细微的权限 - 本教程将简要介绍一些选项。 如何创建新用户 在MySQL...

问题终结者 ⋅ 昨天 ⋅ 0

android -------- 颜色的半透明效果配置

最近有朋友问我 Android 背景颜色的半透明效果配置,我网上看资料,总结了一下, 开发中也是常常遇到的,所以来写篇博客 常用的颜色值格式有: RGB ARGB RRGGBB AARRGGBB 这4种 透明度 透明度...

切切歆语 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部