An efficient ray tracing algorithm and its implementation based on adaptive octree decomposition

Chunlong  Dong; Shengjun  Xue; Limin  Zhao

doi:10.59400/cai2514

An efficient ray tracing algorithm and its implementation based on adaptive octree decomposition

Chunlong Dong Silicon Lake College, Kunshan 215300, Jiangsu, China
Shengjun Xue School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044, Jiangsu, China
Limin Zhao Silicon Lake College, Kunshan 215300, Jiangsu, China

Article ID: 2514

DOI: https://doi.org/10.59400/cai2514

Keywords: surface discretization; adaptive octree; ray tracing algorithm; optical simulation; performance improvement

Abstract

This paper proposes a ray tracing algorithm based on adaptive octree decomposition to solve the problem of low efficiency of calculating the intersection point of light rays and complex surfaces in the optical simulation of vehicle lights. The algorithm significantly improves the efficiency of solving the intersection problem by discretizing the complex surface into a series of polygonal facets and using a bilinear interpolation algorithm to optimize the light refraction calculation. Experiments show that the algorithm can greatly reduce the computation time on vehicle light models of different complexity, especially when dealing with complex surfaces, the algorithm improves performance by nearly 50%. The algorithm has been successfully applied to simulating optical performance in the design of vehicle lights and has achieved good application results, providing an efficient solution for the optical simulation in the design of vehicle lights.

Published

2025-04-08

How to Cite

Dong, C., Xue, S., & Zhao, L. (2025). An efficient ray tracing algorithm and its implementation based on adaptive octree decomposition. Computing and Artificial Intelligence, 3(2), 2514. https://doi.org/10.59400/cai2514

Download Citation

Issue

Vol. 3 No. 2 (2025)

Section

Article

This work is licensed under a Creative Commons Attribution 4.0 International License.

References

[1]Zhao F. Key technologies and applications for cloud CAD software. Computer Integrated Manufacturing Systems. 2022; 28 (04): 959-978. doi: 10.13196/j.cims.2022.04.001

[2]Wang Y, Lyu H, Chen X. An Efficient Method for Computing the intersection between Two B-Spline Curves. Journal of Computer-Aided Design & Computer raphics. 2024; 36(05): 687-700. doi: 10.3724/SP.J.1089.2024.19869

[3]Xu X, Wu X, Chen Z, et al. A Survey of Ray Tracing Rendering of Large-Scale Scenes. Journal of Computer-Aided Design & Computer Graphics. 2024; 36(8): 1155-1170. doi: 10.3724/SP.J.1089.2024.2023-00614

[4]Qin Z, Zhang W, Jiang X, et al. Real-time Interactive Computer-generated Integral Imaging Method Based on Ray Tracing. Acta Photonica Sinica. 2019; 48(9): 0911002. doi: 10.3788/gzxb20194809.0911002

[5]Yan R, Huang L, Guo H, et al. Review of Real-Time Ray Tracing Technique Research. Journal of Frontiers of Computer Science and Technology. 2023; 17(02): 263-278. doi: 10.3778/j.issn.1673-9418.2207067

[6]Jin Y, Song D, Yu C, et al. Curve Design Method on Mesh Surface Based on Distance Constraints. Journal of Software. 2020; 31(10): 3266-3279. doi: 10.13328/j.cnki.jos.005804

[7]Zhao Z. Developable Approximations for Discrete Surfaces. University of Science and Technology of China; 2023. doi: 10.27517/d.cnki.gzkju.2023.000196

[8]Xiao H. Bilinear Interpolation Parallel Algorithm Based on GPU Computing. Journal of C hinese ComputerSystems. 2010; 31(11): 2241-2245. doi: 10.20009/j.cnki.21-1106/tp.2010.11.023

[9]Chen L, Gao C. Fast discrete bilinear interpolation algorithm. Computer Engineering and Design; 2007. doi: 10.3969/j.issn.1000-7024.2007.15.077

[10]Tang W, Qi S, Yang X, et al. Traffic Flow Data Repair Method Based on Random Forest and Nearest Neighbor Interpolation. Science Technology and Engineering. 2024; 24(32): 14056-14065. doi: 10.12404/j.issn.1671-1815.2307559

[11]Guo Y. Research on Path Planning and Autonomous Obstacle-avoidance Algorithm for Unmanned Vehicle. Beijing Jiaotong University; 2021. doi: 10.26944/d.cnki.gbfju.2021.001488

[12]Jackins CL, Tanimoto SL. Oct-tree and their use in representing three-dimensional objects. Computer Graphics & Image Processing. 1980; 14(3): 249-270. doi: 10.1016/0146-664X(80)90055-6

[13]Liu AA, Nie WZ, Su YT. 3D object retrieval based on multi-view latent variable model. IEEE Transactions on Circuits and Systems for Video Technology. 2019; 29(3): 868-880. doi: 10.1109/TCSVT.2018.2810191

[14]Zhang M, Yan M, Ma Y, et al. 3D Voxel Model Retrieval Based on octree Structure. Chinese Journal of Computers. 2021; 44(2): 334-346. doi: 10.11897/SP.J.1016.2021.00334

[15]Jia S, Zhang W, Yu X, et al. Parallel Collision Algorithms for Cutting Simulation of Octree-based Deformable Objects. Journal of Computer-Aided Design & Computer Graphics. 2017; 29(12): 2180-2188. doi: 10.3724/SP.J.1089.2017.16430

[16]Wang Y, Tan S, Jing W, et al. NURBS surface reconstruction based on space partitioning of octree. Computer Engineering and Design. 2015; 36(06): 1565–1570. doi:10.16208/j.issn1000-7024.2015.06.031

[17]Zhang P, Du C, Zhao W. Study on mesh generation algorithm of polyhedron in 3D scaled boundary finite element method based on image octree. Journal of Hohai University (Natural Sciences). 2020; 52(1): 46-54. doi: 10.3876/j.issn.1000-1980.2024.01.006

[18]Zhou H, Wu C. Ray tracing algorithm based on neighborhood search of octree spatial encoding. Computer Engineering and Design; 2017. doi: 10.16208/j.issn1000-7024.2017.01.050

[19]Zhang W, Xie S, Zhong J, et al. Acceleration algorithm in ray tracing by the octree neighbor finding. Journal of Graphics. 2015; 36(03): 339-344. doi: 10.3969/j.issn.2095-302X.2015.03.003

[20]Cai X, Zeng L, Liu G. Survey of ray tracing in volume rendering. Computer Engineering and Design. 2009; 30(21): 4956-4959. doi: 10.16208/j.issn1000-7024.2009.21.027

[21]Xiao W, Zhang L, Sun D, et al. Ray-tracing based occlusion detection algorithms. Acta Geodaetica et Cartographica Sinica. 2014; 43(8): 862-868. doi: 10.13485/j.cnki.11-2089.2014.0134

[22]Hou L, Liu Y, Wang Y. Study of collision detection based on ray tracing principle. Journal of System Simulation. 2006; 18(Suppl.1): 84-87. doi: 10.16182/j.cnki.joss.2006.s1.027

[23]Cai P. Rendering of point cloud data based on ray tracing and photon mapping. Beijing University of Technology; 2013. doi: CNKI:CDMD:1.1013.047307

[24]Cai P, Yin B, Kong D. A ray tracing method based on the nearest points. Journal of Graphics. 2013; 34(3): 1-6. doi: 10.3969/j.issn.2095-302X.2013.03.001

[25]Zheng Y, Xie Y, Ji Yu et al. 3D cloud simulation based on octree neighbor finding of ray tracing. Computer Engineering and Design. 2023; 41(5): 1489-1493. doi: 10.16208/j.issn1000-7024.2020.05.043

[26]Yao C, Ma C. Adaptive octree 3D image reconstruction based on plane patch. Optics and Precision Engineering. 2022; 30(9): 1113-1122. doi: 10.37188/OPE.20223009.1113

[27]Liu X, Weng X, Chen Hao, et al. An Improved Algorithm for Octree-Based Exact Collision Detection. Journal of Computer-Aided Design & Computer Graphics. 2005; 17(12): 2631–2635. doi: 10.3321/j.issn:1003-9775.2005.12.008

[28]Wang X. Octree algorithm for point surface matching. Computer Engineering and Applications; 2009. doi: 10.3778/j.issn.1002-8331.2009.32.054

[29]De Queiroz RL, Garcia DC, Chou PA, et al. Distance-basedprobability modelforoctreecoding. IEEE Signal Processing Letters. 2018; 25(6):739-742. doi: 10.1109/LSP.2018.2823701

[30]Zhang D. Development of CAE model interaction and icon rendering engine based on OpenGL. Hunan University; 2023. doi: 10.27135/d.cnki.ghudu.2023.000451

[31]Xu Z, Zhang Z, Ding Y. Application of Boost Library to analysis of geographical network. Engineering of Surveying and Mapping. 2010; 19 (03): 55-58. doi: 10.3969/j.issn.1006-7949.2010.03.016

[32]Zheng Y, Zheng P. Topology reconstruction of STL data based on C++ standard template library. Chinese Journal of Engineering Design. 2013; 20(06): 522-528. doi: 10.3785/j.issn.1006-754X.2013.06.013

[33]Zhang Z. Research on Die Forging Process CAD System and Key Technologies for Large Aircraft Component Based on CATIA. Huazhong University of Science & Technology; 2016. doi: 10.7666/d.D01077044

[34]Meng X, Zhang L, Xiao T. Research on Assembly Simulation System Based on ACIS and HOOPS for Complex Products. Journal of System Simulation. 2014; 26(10): 2381-2385. doi: 10.16182/j.cnki.joss.2014.10.092

[35]Shang M, Zheng Y, Chen J, et al. A multi-threaded parallel algorithm for quality improvement of tetrahedral meshes. Chinese Journal of Computational Mechanics. 2016; 33(4): 613-620. doi: 10.7511/jslx201604030

[36]Wang F, Sun Z, Zheng X, et al. Discretizing approach for complex three-dimensional geometry based on meshless particle methods. Journal of Zhejiang University (Engineering Science). 2022; 56(08): 1597-1605. doi: 10.3785/j.issn.1008-973X.2022.08.014

[37]Sun Y, Luo S, Hu X, et al. Modeling of bulge formed join intersection region based on differential equation surface intersection tracking method. Chinese journal of construction machinery. 2024; 22(02): 141-145. doi: 10.15999/j.cnki.311926.2024.02.022

[38]Yu R. Research of Memory Management Mechanism Based on Dynamic Allocation Algorithm. Harbin Engineering University; 2017. doi: CNKI:CDMD:2.1018.081593

Editor-in-Chief

Prof. Shaohua Wan
University of Electronic Science and Technology of China, China

eISSN

3029-2786

Publication Frequency

Quarterly (since 2025)

About the Publisher

Academic Publishing insists on taking academic exchange and publication as the main line, carrying out comprehensive management based on science and technology, and fully exploring excellent international publishing resources. Within 5 years, it will form a strategic framework and scale with science (S), technology (T), medicine (M), education (E), and humanities and arts (H) as the main publishing fields. Academic Publishing is headquartered in Singapore and based in Malaysia, with the United States and China providing the main scientific and academic resources. At the same time, it has established long-term good cooperative relations with other publishing companies, scientific research communities, and academic organizations in more than a dozen countries and regions. Academic Publishing uses English and Chinese as its main publishing languages, mainly publishing books, journals, and conference papers in print and online. The vast majority of publications follow the international open access policy, providing stable and long-term quality and professional publications. With the joint efforts of the expert team and our professional editorial team, our publications will gradually be indexed by international databases in stages to provide convenient and professional retrieval for various scholars. At the same time, manuscripts we accept will be subject to the peer review principle, and cutting-edge and innovative research articles will be preferentially accepted for peer reference and discussion. All kinds of our publications are welcome for peer to contribute, access, and download.

more

Volume Arrangement

2025

2024

2023

Featured Articles

Identifying voices using convolution neural network models AlexNet and ResNet

Deep learning (DL) techniques which implement deep neural networks became popular due to the increase of high-performance computing facilities. DL achieves higher power and flexibility due to its ability to process many features when it deals with unstructured data. DL algorithm passes the data through several layers; each layer is capable of extracting features progressively and passes it to the next layer. Initial layers extract low-level features, and succeeding layers combine features to form a complete representation. This research attempts to utilize DL techniques for identifying sounds. The development in DL models has extensively covered classification and verification of objects through images. However, there have not been any notable findings concerning identification and verification of the voice of an individual from different other individuals using DL techniques. Hence, the proposed research aims to develop DL techniques capable of isolating the voice of an individual from a group of other sounds and classify them based on the use of convolutional neural networks models AlexNet and ResNet, that are used in voice identification. We achieved the classification accuracy of ResNet and AlexNet model for the problem of voice identification is 97.2039 % and 65.95% respectively, in which ResNet model achieves the best result.

Revolutionizing Neurosurgery and Neurology: The transformative impact of artificial intelligence in healthcare

The integration of artificial intelligence (AI) has brought about a paradigm shift in the landscape of Neurosurgery and Neurology, revolutionizing various facets of healthcare. This article meticulously explores seven pivotal dimensions where AI has made a substantial impact, reshaping the contours of patient care, diagnostics, and treatment modalities. AI’s exceptional precision in deciphering intricate medical imaging data expedites accurate diagnoses of neurological conditions. Harnessing patient-specific data and genetic information, AI facilitates the formulation of highly personalized treatment plans, promising more efficacious therapeutic interventions. The deployment of AI-powered robotic systems in neurosurgical procedures not only ensures surgical precision but also introduces remote capabilities, mitigating the potential for human error. Machine learning models, a core component of AI, play a crucial role in predicting disease progression, optimizing resource allocation, and elevating the overall quality of patient care. Wearable devices integrated with AI provide continuous monitoring of neurological parameters, empowering early intervention strategies for chronic conditions. AI’s prowess extends to drug discovery by scrutinizing extensive datasets, offering the prospect of groundbreaking therapies for neurological disorders. The realm of patient engagement witnesses a transformative impact through AI-driven chatbots and virtual assistants, fostering increased adherence to treatment plans. Looking ahead, the horizon of AI in Neurosurgery and Neurology holds promises of heightened personalization, augmented decision-making, early intervention, and the emergence of innovative treatment modalities. This narrative is one of optimism and collaboration, depicting a synergistic partnership between AI and healthcare professionals to propel the field forward and significantly enhance the lives of individuals grappling with neurological challenges. This article provides an encompassing view of AI’s transformative influence in Neurosurgery and Neurology, highlighting its potential to redefine the landscape of patient care and outcomes.

Enhancing user experience in large language models through human-centered design: Integrating theoretical insights with an experimental study to meet diverse software learning needs with a single document knowledge base

This paper begins with a theoretical exploration of the rise of large language models (LLMs) in Human-Computer Interaction (HCI), their impact on user experience (HX) and related challenges. It then discusses the benefits of Human-Centered Design (HCD) principles and the possibility of their application within LLMs, subsequently deriving six specific HCD guidelines for LLMs. Following this, a preliminary experiment is presented as an example to demonstrate how HCD principles can be employed to enhance user experience within GPT by using a single document input to GPT’s Knowledge base as new knowledge resource to control the interactions between GPT and users, aiming to meet the diverse needs of hypothetical software learners as much as possible. The experimental results demonstrate the effect of different elements’ forms and organizational methods in the document, as well as GPT’s relevant configurations, on the interaction effectiveness between GPT and software learners. A series of trials are conducted to explore better methods to realize text and image displaying, and jump action. Two template documents are compared in the aspects of the performances of the four interaction modes. Through continuous optimization, an improved version of the document was obtained to serve as a template for future use and research.

Clustering data analytics of urban land use for change detection

In this study, the author proposes and details a workflow for the spatial-temporal demarcation of urban areal features in 8 cities of Tamilnadu, India. During the inception phase, functional requirements and non-functional parameters are analyzed and designed, within a suitable pixel area and object-oriented derived paradigm. Land use categories are defined from OpenStreetMap (OSM) related works with the scope of conducting climate change, using multispectral sensors onboard Landsat series. Furthermore, we augment the bands dataset with Spatially Invariant Feature Transform (SIFT), Normalized Difference Vegetation Index (NDVI), Normalized Difference Built-Up Index (NDBI), Leaf Area Index (LAI), and Texture base indices, as a means of spatially integrating auto-covariance to stationarity patterns. In doing so, change detection can be pursuit by scaling up the segmentation of regional/zonal boundaries in a multi-dimensional environment, with the aid of Wide Area Networks (WAN) cluster computers such as the BEOWULF/Google Earth Engine clusters. GeoAnalytical measures are analyzed in the design of local and zonal spatial models (GRID, RASTER, DEM, IMAGE COLLECTION). Finally, multi variate geostatistical works are ensued for precision and recall in predictive data analytics. The author proposes reusing machine learning tools (filtering by attribute-based indexing in PaaS clouds) for pattern recognition and visualization of features and feature collection.

Application of computer vision in livestock and crop production—A review

Nowadays, it is a challenge for farmers to produce healthier food for the world population and save land resources. Recently, the integration of computer vision technology in field and crop production ushered in a new era of innovation and efficiency. Computer vision, a subfield of artificial intelligence, leverages image and video analysis to extract meaningful information from visual data. In agriculture, this technology is being utilized for tasks ranging from disease detection and yield prediction to animal health monitoring and quality control. By employing various imaging techniques, such as drones, satellites, and specialized cameras, computer vision systems are able to assess the health and growth of crops and livestock with unprecedented accuracy. The review is divided into two parts: Livestock and Crop Production giving the overview of the application of computer vision applications within agriculture, highlighting its role in optimizing farming practices and enhancing agricultural productivity.