View Frustum Culling Algorithm for Scene Based on Optimized Octree

doi:10.3969/j.issn.1006-2475.2024.01.017

Abstract

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

CLC Number:

TP391.41

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.

References

［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]	CHEN Kai1, LI Yiting1, 2, QUAN Huafeng1. A River Discarded Bottles Detection Method Based on Improved YOLOv8 [J]. Computer and Modernization, 2024, 0(11): 113-120.
[2]	CHENG Yazi1, LEI Liang1, 2, CHEN Han1, ZHAO Yiran1. Multi-scale Depth Fusion Monocular Depth Estimation Based on Transposed Attention [J]. Computer and Modernization, 2024, 0(09): 121-126.
[3]	LAI Kun. Chinese Paper Invoice Text Recognition Method with Character Blurring [J]. Computer and Modernization, 2024, 0(08): 114-119.
[4]	WU Li1, ZHANG Zhenghao2, GE Caicheng2, YU Jun2. Lane Line Detection Algorithm Based on Improved SCNN Network [J]. Computer and Modernization, 2024, 0(07): 87-92.
[5]	ZHU Fen, HE Lifeng, SUN Shuang, ZHANG Mengying, YU Jiajia. Pancreas Segmentation Model Based on Deformable Residual and Cascading Encoding [J]. Computer and Modernization, 2024, 0(06): 83-88.
[6]	QIAO Jia, XU Kun, HU Peirong. Layout Analysis Method of Multi-scale Feature Fusion [J]. Computer and Modernization, 2024, 0(05): 16-21.
[7]	XU Cheng1, ZHANG Yun2, ZENG Xiangjin1. Placenta Ultrasound Image Segmentation [J]. Computer and Modernization, 2024, 0(05): 115-119.
[8]	LIANG Jian-ye1, CHEN Jun-hong1, FANG Gui-biao1, WU Xing-cai2, LIU Wen-yin1. Optical Flow Estimation Based on Inverse Residual Attention [J]. Computer and Modernization, 2024, 0(02): 64-68.
[9]	FU Hong-lin, ZHANG Tai-hong, YANG Ya-ting, Aizimaiti Aiwanier, MA Bo. Scenes Text Modification Network for Uyghur Based on Generative Adversarial Network [J]. Computer and Modernization, 2024, 0(01): 41-46.
[10]	LUO Wei, LIU Si-yuan, XU Jian-xiang, DONG Tian-pei. Improved Solar Cell Defect Detection Algorithm Based on YOLOv5s [J]. Computer and Modernization, 2023, 0(07): 119-126.
[11]	LI Yun-chuan, WANG Xiao-hong, CHEN Si-ji, GE Yi-pan, LI Chuang. A Point Cloud Registration Algorithm Based on Multi-core Parallel and Dynamic Threshold [J]. Computer and Modernization, 2020, 0(09): 77-82.
[12]	BAI Shi-lei, YIN Ke-xin, ZHU Jian-qi. Lightweight YOLOv3 Traffic Sign Detection Algorithm [J]. Computer and Modernization, 2020, 0(09): 83-88.
[13]	ZHOU Xing, CHEN Li-fu. Object Detection of Remote Sensing Image Based on Dual Attention Mechanism [J]. Computer and Modernization, 2020, 0(08): 1-7.
[14]	Maierziyan Abudula， FENG Xiang-ping. Non-contact Horse Body Measurement Method Based on Machine Vision [J]. Computer and Modernization, 2019, 0(10): 108-.
[15]	LI Han1, HU Ming-xiao2, GONG Zhi-hong3, FAN Bing-jun3. Massive Spatial Data Parallel Processing Technology for Vector Tiles [J]. Computer and Modernization, 2018, 0(09): 32-.