Conservative enclosing box construction algorithm based on implicit geometric coding with Lipschitz linear constraints

doi:10.11996/JG.j.2095-302X.2026010152

Abstract

Abstract:

Currently the mainstream enveloping box methods are widely used in 3D scene rendering, ray tracing, and collision detection tasks; however, these methods suffer from the problems of low space utilization and insufficient fitting accuracy in fitting complex geometries, which are difficult to ensure strict conservatism and still have room for improvement in reducing false detection rates. To address these issues, a conservative bounding-box construction method combining implicit geometric coding and Lipschitz constraints was proposed. Implicit geometric coding mapped the input coordinates to a high-dimensional space via position coding, thus capturing local and global geometric information and improving bounding-box adaptability. A trainable Lipschitz-constrained linear layer was introduced to dynamically adjust Lipschitz constants control gradient changes, and Lipschitz regularization loss was combined with dynamically weighted cross-entropy loss to reduce the FP rate while optimizing the boundary fitting. The experimental results demonstrated that the method can achieve a false-negative rate of 0 on multiple 3D models and reduce the false-detection rate by up to 3.1% compared to the benchmark method, and improve the single-ray query method by 1.7 ms, providing a highly efficient and robust solution for high-precision conservative bounding box fitting.

Key words: conservative bounding box, Lipschitz constraint, implicit geometric encoding, ray tracing, collision detection

CLC Number:

TP391.41

ZHANG Bingyu, KUANG Liqun, XIONG Fengguang, SUN Fanshu, JIAO Shichao. Conservative enclosing box construction algorithm based on implicit geometric coding with Lipschitz linear constraints[J]. Journal of Graphics, 2026, 47(1): 152-161.

Figures/Tables 13

Fig. 1 Classic bounding box types ((a) Bounding Sphere; (b) AABB bounding box; (c) OBB bounding box; (d) k-DOP bounding box)

Fig. 2 Model general network architecture diagram

Fig. 3 ImplicitNet module

Fig. 4 Lipschitz constraints module

Fig. 5 Dataset model images ((a) ShapeNet partial models; (b) The Stanford 3D scanning repository)

Table 1 Comparison of FPR for different methods of bounding boxes

方法	ShapeNet数据集				斯坦福大学三维扫描存储库
方法	Point	Box	Plane	Ray	Point	Box	Plane	Ray
AABB	49.3	45.4	55.2	69.2	66.6	51.2	49.6	70.2
OBB	42.1	49.2	58.4	63.3	51.2	41.9	45.3	65.6
Sphere	54.2	56.7	64.9	70.3	77.4	56.3	59.3	71.9
k-DOP	34.5	40.9	41.6	62.3	45.2	51.8	42.3	68.3
NN	4.2	6.1	7.6	6.9	5.9	7.5	8.2	8.7
NBE	3.9	5.5	6.2	7.5	5.5	7.5	8.4	8.3
SCNI	4.2	4.6	6.4	7.9	5.6	7.8	9.6	9.3
DRFC	11.6	12.4	23.1	29.9	10.4	16.6	26.7	32.8
Ours	3.5	4.1	4.3	5.5	3.2	4.4	5.9	6.9

Fig. 6 Comparison of FPR for each bracketed box methodology ((a) ShapeNet dataset; (b) Stanford 3D scanning repository)

Fig. 7 Comparison of FNR between the benchmark model and the method in this paper ((a) Point; (b) Plane; (c) Box; (d) Ray)

Table 2 Comparison of single ray query time/ms

方法	时间
AABB	2.83
OBox	2.85
Sphere	2.49
k-DOP	43.26
NN	71.38
NBE	47.52
SCNI	55.85
DRFC	65.44
Ours	45.82

Fig. 8 Visual comparison of model bounding boxes ((a) Ours; (b) SCNI; (c) NN; (d) NBE)

Table 3 Comparison of ablation experiment results

方法	FPR/%	时间/ms
Baseline	7.6	46.3
ImplicitNet	6.4	43.2
Lipschitz	5.9	43.6
ImplicitNet+Lipschitz	4.9	45.1

Fig. 9 Performance comparison of parameter λ on airplane model

Fig. 10 Performance comparison of parameter c on airplane model

References 25

[1]	MEISTER D, OGAKI S, BENTHIN C, et al. A survey on bounding volume hierarchies for ray tracing[J]. Computer Graphics Forum, 2021, 40(2): 683-712. DOI URL
[2]	MEISTER D, KULKARNI P, VASISHTA A, et al. HIPRT: a ray tracing framework in HIP[J]. Proceedings of the ACM on Computer Graphics and Interactive Techniques, 2024, 7(3): 44.
[3]	杨帆. 基于B+树存储的AABB包围盒碰撞检测算法[J]. 计算机科学, 2021, 48(S1): 331-333, 348.
	YANG F. Collision detection algorithm of AABB bounding box based on B+ tree[J]. Computer Science, 2021, 48(S1): 331-333, 348 (in Chinese).
[4]	CHANG J W, WANG W P, KIM M S. Efficient collision detection using a dual OBB-sphere bounding volume hierarchy[J]. Computer-Aided Design, 2010, 42(1): 50-57. DOI URL
[5]	成居宝, 杜娟, 刘丽琴, 等. 基于数控机床特性的碰撞检测算法研究[J]. 组合机床与自动化加工技术, 2020(8): 101-105, 110. DOI
	CHENG J B, DU J, LIU L Q, et al. Research on collision detection algorithm based on characteristics of CNC machine tools[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2020(8): 101-105, 110 (in Chinese).
[6]	刘超, 蒋夏军, 施慧彬. 一种快速的双重层次包围盒碰撞检测算法[J]. 计算机与现代化, 2018(5): 6-10.
	LIU C, JIANG X J, SHI H B. A fast collision detection algorithm based on dual bounding volume hierarchy[J]. Computer and Modernization, 2018(5): 6-10 (in Chinese).
[7]	CHAO W, ZHANG Z L, YONG L, et al. Improved hybrid bounding box collision detection algorithm[J]. Journal of System Simulation, 2019, 30(11): 4236-4243.
[8]	ZHAO W, QU H Y. Application of improved algorithm based on sphere OBB hybrid hierarchical bounding box in Teaching[J]. Journal of Physics: Conference Series, 2021, 1732(1): 012080. DOI
[9]	林菲, 邹玲, 张聪. 基于混合层次包围盒的快速碰撞检测算法[J]. 计算机仿真, 2023, 40(9): 454-457.
	LIN F, ZOU L, ZHANG C. A fast collision detection algorithm based on hybrid hierarchical bounding boxes[J]. Computer Simulation, 2023, 40(9): 454-457 (in Chinese).
[10]	SABINO R, VIDAL C A, CAVALCANTE-NETO J B, et al. Building oriented bounding boxes by the intermediate use of ODOPs[J]. Computers & Graphics, 2023, 116: 251-261. DOI URL
[11]	BEHERA A P, MISHRA S. Neural directional distance field object representation for uni-directional path-traced rendering[C]// The 14th International Conference on Computing Communication and Networking Technologies. New York: IEEE Press, 2023: 1-6.
[12]	WEIER P, RATH A, MICHEL É, et al. N-BVH: neural ray queries with bounding volume hierarchies[C]// ACM SIGGRAPH 2024 Conference Papers. New York: ACM, 2024: 99.
[13]	ZESCH R S, MODI V, SUEDA S, et al. Neural collision fields for triangle primitives[C]// SIGGRAPH Asia 2023 Conference Papers. New York: ACM, 2023: 76.
[14]	STRÖTER D, THIERY J M, HORMANN K, et al. A survey on cage-based deformation of 3D models[J]. Computer Graphics Forum, 2024, 43(2): e15060. DOI URL
[15]	XU T H, HARADA T. Deforming radiance fields with cages[C]// The 17th European Conference on Computer Vision. Cham: Springer, 2022: 159-175.
[16]	PENG Y C, YAN Y C, LIU S Q, et al. CageNeRF: cage-based neural radiance field for generalized 3D deformation and animation[C]// The 36th International Conference on Neural Information Processing Systems. Red Hook: Curran Associates Inc., 2022: 2277.
[17]	LIU S W, FISCHER M, YOO P D, et al. Neural bounding[C]// ACM SIGGRAPH 2024 Conference Papers. New York: ACM, 2024: 98.
[18]	LUDWIG I, CAMPEN M. Strictly conservative neural implicits[J]. Computer Graphics Forum, 2024, 43(7): e15241. DOI URL
[19]	LIU H T D, WILLIAMS F, JACOBSON A, et al. Learning smooth neural functions via Lipschitz regularization[C]// ACM SIGGRAPH 2022 Conference Proceedings. New York: ACM, 2022: 31.
[20]	TANCIK M, SRINIVASAN P P, MILDENHALL B, et al. Fourier features let networks learn high frequency functions in low dimensional domains[C]// The 34th International Conference on Neural Information Processing Systems. Red Hook: Curran Associates Inc., 2020: 632.
[21]	YANG G D, BELONGIE S, HARIHARAN B, et al. Geometry processing with neural fields[C]// The 35th International Conference on Neural Information Processing Systems. Red Hook: Curran Associates Inc., 2021: 1722.
[22]	GROPP A, YARIV L, HAIM N, et al. Implicit geometric regularization for learning shapes[EB/OL]. [2025-01-08]. https://dl.acm.org/doi/abs/10.5555/3524938.3525293.
[23]	PRACH B, BRAU F, BUTTAZZO G, et al. 1-Lipschitz layers compared: memory, speed, and certifiable robustness[C]// 2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2024: 24574-24583.
[24]	NEACŞU A, PESQUET J C, BURILEANU C. EMG-based automatic gesture recognition using lipschitz-regularized neural networks[J]. ACM Transactions on Intelligent Systems and Technology, 2024, 15(2): 26.
[25]	CHANG A X. ShapeNet:an information-rich 3D model repository[EB/OL]. [2025-01-11]. http://arxiv.org/abs/1512.03012.