基于优化八叉树的场景视锥体裁剪算法

doi:10.3969/j.issn.1006-2475.2024.01.017

计算机与现代化 ›› 2024, Vol. 0 ›› Issue (01): 103-108.doi: 10.3969/j.issn.1006-2475.2024.01.017

基于优化八叉树的场景视锥体裁剪算法

（1.西南交通大学计算机与人工智能学院，四川成都 611756； 2.西南交通大学信息科学与技术学院，四川成都 611756）

出版日期:2024-01-23 发布日期:2024-02-26
作者简介:李颖颖（1997—），女，河南商丘人，硕士研究生，研究方向:计算机图形学，E-mail: 1872874937@qq.com；黄文培（1967—），男，福建建瓯人，副教授，博士，研究方向:Web3D数字孪生，E-mail: 449192936@qq.com。
基金资助:
国家重点研发计划项目（2020YFB1708000）；四川省重点研发计划项目（2021YFG0039）

View Frustum Culling Algorithm for Scene Based on Optimized Octree

（1. College of Computers and Artificial Intelligence， Southwest Jiaotong University， Chengdu 611756， China；
2. College of Information Science and Technology， Southwest Jiaotong University， Chengdu 611756， China）

Online:2024-01-23 Published:2024-02-26

摘要/Abstract

摘要： 摘要：大体量3D模型容易导致浏览器端渲染帧数低、显示卡顿及资源消耗大等问题，其原因是这类模型通常包含数以亿计的三角面片，在有限的时间内无法实现快速加载与渲染。针对此类问题，提出一种基于优化八叉树的场景视锥体裁剪算法。该算法采用地址码（Morton码）、节点视距标准和按需增量划分技术，使得八叉树具有自适应性与良好的压缩效率；采用双层包围体和基础相交测试技术，提高视锥体裁剪的精确性，整体上实现提升渲染帧数、显示流畅的目标。高速列车实例模型研究表明，与传统八叉树视锥体裁剪算法相比，所提算法平均渲染帧数上提高了约 14帧，空间压缩率提高了37.8个百分点。

关键词: 关键词：地址码, 视距标准, 按需增量划分, 自适应性, 双层包围体, 基础相交测试

Abstract: Abstract：Large-volume 3D models are prone to low rendering frame rate， slow display and large resource consumption on the browser side. The reason is that such models usually contain hundreds of millions of triangular slices， which cannot be loaded and rendered quickly in a limited time. To address such problems， a scene view frustum culling algorithm based on an optimized octree is proposed. The algorithm adopts address code （Morton code）， node view distance criterion and on-demand incremental division technique， which makes the octree adaptive with good compression efficiency； it adopts double bounding volume and base intersection test techniques to improve the accuracy of view frustum culling and achieves the overall goal of improving rendering frame rate and smooth display. The high-speed train example model study shows that the proposed algorithm improves the average rendering frame rate by about 14 frames and the spatial compression rate by about 37.8 percentage points compared with the traditional octree view frustum culling algorithm.

Key words: Keywords： Morton code, view distance criteria, on-demand increments division, adaptivity, double bounding volume, base intersection test

中图分类号:

TP391.41

李颖颖, 黄文培. 基于优化八叉树的场景视锥体裁剪算法[J]. 计算机与现代化, 2024, 0(01): 103-108.

LI Ying-ying, HUANG Wen-pei. View Frustum Culling Algorithm for Scene Based on Optimized Octree[J]. Computer and Modernization, 2024, 0(01): 103-108.

参考文献

［1］杨艳芳，高居建，王奇，等. 面向复杂生产场景的数字孪生模型分布式渲染方法［J］. 计算机集成制造系统， 2023，29（6）:1811-1823.
［2］舒亮，张洁，陈璇，等. 面向大规模场景的数字孪生模型快速渲染方法［J］. 计算机集成制造系统， 2022，28（11）:3664-3672.
［3］徐磊，高广军，董威，等. 列车转向架数字孪生建模仿真关键技术研究［J］. 铁道科学与工程学报， 2023，20（5）:1846-1857.
［4］聂春萌. 列车虚拟现实系统关键技术研究［D］. 北京:北京建筑大学， 2019.
［5］陈昭明，邹劲松. 智能制造领域的数字孪生技术研究可视化知识图谱分析［J］. 机械科学与技术， 2023，42（8）:1249-1260.
［6］ DUAN F B， RIETVELD K F D， LAMERS G， et al. Real-time interactive visualization of 3D models from bioimaging in a holographic pyramid［C］// 2022 4th International Conference on Advances in Computer Technology， Information Science and Communications（CTISC）. 2022. DOI: 10.1109
/CTISC54888.2022.9849740.
［7］ FENG Y H， WAN F. Analysis of lightweight processing technology for WEB oriented BIM model［C］// 2022 11th International Conference of Information and Communication Technology （ICTech））. 2022:8-12.
［8］冯雨晴，奚雪峰，崔志明. 基于WebGL的BIM模型轻量化研究［J］. 苏州科技大学学报（自然科学版）， 2021，38（4）:72-78.
［9］刘宇. 基于三维可视化平台的场景管理的设计与实现［D］. 北京:中国科学院大学（中国科学院沈阳计算技术研究所）， 2020.
［10］ YILMAZ M， ERUYAR E E， YILMAZ B， et al. A split and merge based plane segmentation method with Octree data structure for unorganized point cloud data［C］// 2020 Innovations in Intelligent Systems and Applications Conference （ASYU）. 2020:1-6. DOI: 10.1109/ASYU50717.2020.9259
805.
［11］张满囤，燕明晓，马英石，等. 基于八叉树结构的三维体素模型检索［J］. 计算机学报， 2021，44（2）:334-346.
［12］危育冰. 基于八叉树编码的散乱点云数据压缩［J］. 武汉大学学报（工学版）， 2020，53（8）:734-739.
［13］黎玲，金恒，刘杰，等. 基于工业CT图像的自适应三维网格模型重建［J］. 光学学报， 2023，43（3）:243-252.
［14］袁昱纬，全吉成，吴晨，等. 基于八叉树自适应体归并的光线跟踪加速结构［J］. 光学学报， 2017，37（1）:251-260.
［15］ SISIAS G， BILETSKY D. Binary voxel map compression based on Quadtree and Octree subdivision， using arbitrary and non-power-of-2 dimensions［C］// 2018 South-Eastern European Design Automation， Computer Engineering， Computer Networks and Society Media Conference （SEEDA_CECNSM）. 2018:1-8. DOI: 10.23919/SEEDA-CECNSM.2018.8544941.
［16］鲍义东，吴冬梅. 自适应细分及优化编码八叉树碰撞检测算法［J］. 上海交通大学学报， 2015，49（8）:1114-1122.
［17］ DRICOT A， ASCENSO J. Hybrid Octree-plane point cloud geometry coding［C］// 2019 27th European Signal Processing Conference （EUSIPCO）. 2019:1-5.
［18］ KOH N， JAYARAMAN P K， ZHENG J M. Parallel point cloud compression using truncated Octree［C］// 2020 International Conference on Cyberworlds（CW）. 2020:1-8. DOI: 10.1109/CW49994.2020.00009.
［19］吴宇豪，曹雪峰. 面向Hilbert八叉树的邻近格元计算算法［J］. 武汉大学学报（信息科学版）， 2022，47（4）:613-622.
［20］周藤藤. 基于混合空间划分的视锥剔除算法研究［D］. 武汉:华中科技大学， 2020.
［21］ ZENG J H， WANG D C， CHEN P. Improved color region growing point cloud segmentation algorithm based on Octree［C］// 2022 3rd International Conference on Information Science， Parallel and Distributed Systems （ISPDS）. 2022:424-429.
［22］ WEI L， WAN S， SUN Z X， et al. Weighted attribute prediction based on morton code for point cloud compression［C］// 2020 IEEE International Conference on Multimedia & Expo Workshops （ICMEW）. 2020:1-6. DOI: 10.1109/ICMEW46912.2020.9105953.
［23］林鑫. 三维地形的简化与实时渲染技术研究［D］. 西安:西安电子科技大学， 2020.
［24］苏谟. 三维可视化服务平台关键技术研究及应用［D］. 北京:中国科学院大学（中国科学院沈阳计算技术研究所）， 2019.
［25］王淑君. 密集建筑场景下可见性剔除算法的应用研究［D］. 杭州:浙江大学， 2021.
［26］ WANG H J， ZHANG X L， ZHOU L Q， et al. Intersection detection algorithm based on hybrid bounding box for geological modeling with faults［J］. IEEE Access， 2020，8:29538-29546.
［27］ JIANG Y Z， NIU P. View frustum Culling algorithm for scene based on adaptive binary tree［C］// 2018 2nd IEEE Advanced Information Management， Communicates， Electronic and Automation Control Conference （IMCEC）. 2018:1159-1164.

[1]	杨少令，刁燕，罗华，徐天雄. 一种改进的Canny图像分割算法[J]. 计算机与现代化, 2018, 0(08): 57-.
[2]	周彬镔，陈雪波. 基于元胞自动机的小世界网络病毒传播研究[J]. 计算机与现代化, 2015, 0(1): 8-14.
[3]	白宁. 一种基于k-均值聚类的异常检测技术[J]. 计算机与现代化, 2014, 0(1): 93-95,113.

基于优化八叉树的场景视锥体裁剪算法

View Frustum Culling Algorithm for Scene Based on Optimized Octree

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价