基于GPU并行的高效B样条曲线Offset算法

doi:10.11896/jsjkx.260600137

计算机科学 ›› 2026, Vol. 53 ›› Issue (9): 188-195.doi: 10.11896/jsjkx.260600137

• 计算机图形学&多媒体 • 上一篇下一篇

基于GPU并行的高效B样条曲线Offset算法

杨逸轩^1,3, 王伟明^2,3, 杨周旺^1,3

1 中国科学技术大学数学科学学院合肥 230026
2 南京理工大学数学与统计学院南京 210094
3 合肥人工智能与大数据研究院合肥 230000

收稿日期:2026-03-03 修回日期:2026-06-21 出版日期:2026-09-15 发布日期:2026-09-10
通讯作者: 王伟明(wwmnjust@njust.edu.cn)
作者简介:(yyx111@mail.ustc.edu.cn)
基金资助:
国家自然科学基金委重大研究计划(92270205);安徽省科技重大科技攻坚计划(202423e09050003);重庆市自然科学基金(CSTB2025NSCQ-LZX0056);中央高校基本科研业务费专项资金(2026101001)

Efficient GPU-parallel Algorithm for B-spline Curve Offsetting

YANG Yixuan^1,3, WANG Weiming^2,3, YANG Zhouwang^1,3

1 School of Mathematical Sciences,University of Science and Technology of China,Hefei 230026,China
2 School of Mathematics and Statistics,Nanjing University of Science and Technology,Nanjing 210094,China
3 Hefei Institute of Artificial Intelligence and Big Data Research,Hefei 230000,China

Received:2026-03-03 Revised:2026-06-21 Published:2026-09-15 Online:2026-09-10
About author:YANG Yixuan,born in 2005,bachelor.His main research interest is optimization algorithms.
WANG Weiming,born in 1986,Ph.D,professor.His main research interests include geometry processing and computational fabrication.
Supported by:
National Natural Science Foundation of China Major Research Program (92270205),Major Science and Techno-logy Research Program of Anhui Province(202423e09050003),Natural Science Foundation of Chongqing,China(CSTB2025NSCQ-LZX0056)and Fundamental Research Funds for the Central Universities(2026101001).

摘要/Abstract

摘要： 针对集成电路版图设计、CAD/CAM、EDA等领域中大规模B样条曲线offset计算及自交消除的高效处理需求,虽然传统B样条offset算法能够在一定程度上控制offset后控制点的数量,但其整体计算流程难以统一在GPU上高效实现。针对这一问题,并综合考虑不同B样条offset算法在offset后控制点数量及OpenCascade中相关算法效率方面的差异,提出了一种GPU-CPU协同加速的B样条曲线 offset 算法。在该框架中,offset计算与求交运算统一在GPU上执行。首先,对offset曲线进行分段,并采用勒让德多项式进行逼近,构建一种包含细分阶段且能够避免分支发散的B样条offset算法,并输出分段Bézier曲线。随后,在GPU上对每一段Bézier曲线进行空间网格划分,根据包围盒平均尺寸自适应确定网格分辨率,并采用压缩稀疏行格式构建空间索引。在候选对筛选阶段,通过规范单元去重策略消除重复候选对,并结合凸包相交测试进行窄相位过滤。最后,对过滤后的候选曲线段并行计算交点,并将交点信息返回CPU进行拓扑重构,从而有效避免offset后产生的自交问题。所提算法在几何结构复杂的曲线以及实际EDA版图数据上进行了实验验证,结果表明,该方法具有良好的有效性和计算效率。

关键词: B样条offset, 自交处理, GPU优化, 并行计算

Abstract: To address the demand for efficient processing of large-scale B-spline curve offsetting and self-intersection removal in fields such as integrated circuit layout design,CAD/CAM,and EDA,traditional B-spline offset algorithms,although capable of controlling the number of control points after offsetting to a certain extent,are difficult to implement efficiently on GPUs in a unified computational workflow.To tackle this problem,and considering the differences among existing B-spline offset algorithms in terms of the number of control points after offsetting as well as the efficiency of related algorithms in OpenCascade,this paper proposes a GPU-CPU collaborative accelerated algorithm for B-spline curve offsetting.Within this framework,both the offset computation and intersection detection are executed on the GPU.Firstly,the offset curve is partitioned into segments and appro-ximated using Legendre polynomials,forming a B-spline offset algorithm with a subdivision stage that avoids branch divergence,and ultimately producing piecewise Bézier curves.Subsequently,spatial grid partitioning is performed on the GPU for each Bézier segment.The grid resolution is adaptively determined according to the average size of the bounding boxes,and a spatial index is constructed using the compressed sparse row(CSR) format.During the candidate pair filtering stage,duplicate candidate pairs are removed using a canonical cell deduplication strategy,followed by narrow-phase filtering based on convex hull intersection tests.Finally,intersections are computed in parallel for the filtered candidate curve segments,and the resulting intersection information is returned to the CPU for topological reconstruction,thereby effectively avoiding self-intersections generated after offsetting.The proposed algorithm is evaluated on geometrically complex curves as well as real EDA layout datasets,and the experimental results demonstrate the effectiveness and computational efficiency of the proposed method.

Key words: B-spline offset, Self-intersection, GPU-optimized, Parallel computing

中图分类号:

TP391

杨逸轩, 王伟明, 杨周旺. 基于GPU并行的高效B样条曲线Offset算法[J]. 计算机科学, 2026, 53(9): 188-195. https://doi.org/10.11896/jsjkx.260600137

YANG Yixuan, WANG Weiming, YANG Zhouwang. Efficient GPU-parallel Algorithm for B-spline Curve Offsetting[J]. Computer Science, 2026, 53(9): 188-195. https://doi.org/10.11896/jsjkx.260600137

参考文献

[1] TILLER W,HANSON E G.Offsets of two-dimensional profiles[J].IEEE Computer Graphics and Applications,1984,4(9):36-46.
[2] KIM R H,HWANG S,OAK A,et al.Curvilinear standard cell design for semiconductor manufacturing[J].IEEE Transactions on Semiconductor Manufacturing,2024,37(2):152-163.
[3] Open CASCADE SAS.Open CASCADE Technology Documentation.Version7.9.3[EB/OL].[2026-07-10].https://dev.opencascade.org/doc/overview/html/.
[4] LI Y M,HSU V Y.Curve offsetting based on Legendre series[J].Computer Aided Geometric Design,1998,15(7):711-720.
[5] PIEGL L A,TILLER W.Computing offsets of NURBS curves and surfaces[J].Computer-Aided Design,1999,31(2):147-156.
[6] WU J Y,FENG Z W,ZOU Q.Matrix representation and GPU-optimized parallel B-spline computing[J].Computer-Aided Design,2025,189:103948.
[7] KARCANIAS N,MITROULI M,TRIANTAFYLLOU D.Ahybrid approach for normal factorization of polynomials[C] //International Conference on Computational Science-ICCS 2006.Berlin:Springer,2006:399-406.
[8] CHRISTOU D,KARCANIAS N,MITROULI M.The ERESmethod for computing the approximate GCD of several polynomials[J].Applied Numerical Mathematics,2010,60:94-114.
[9] COQUILLART S.Computing offsets of B-spline curves[J].Computer-Aided Design,1987,19(6):305-309.
[10] SEDERBERG TW,BUEHLER D B.Offset of polynomial Bézier curves:Hermite approximation with error bounds[C] //Mathematical Methods in Computer Aided Geometric Design II.San Diego:Academic Press,1992:549-558.
[11] KLASS R.An offset spline approximation for plane cubic splines[J].Computer-Aided Design,1983,15(5):297-299.
[12] CHEN X J.The Bezier Approximation of Planar offset Curve[J].Journal of Mathematical Study,2005,(2):196-199.
[13] ZHANG Z F,LING Z.An Offset Approximation Curve Based on Interval Bézier Curve[J].Journal of Hangzhou Dianzi University(Natural Sciences),2019,39(4):83-87.
[14] CHEN X,GUO S,WANG R,et al.B-spline curve fitting based on dynamic adjustment of knot vector using feature points[J].PLoS One,2025,20(6):e0325458.
[15] ZOU Q,ZHU L Z,WU J Y,et al.SplineGen:approximating unorganized points through generative AI[J].Computer-Aided Design,2025,178:103809.
[16] SEONG J K,ELBER G,KIM M S.Trimming local and global self-intersections in offset curves/surfaces using distance maps[J].Computer-Aided Design,2006,38(3):183-193.
[17] GERSHON E,MYUNG-SOO K.Geometric constraint solverusing multivariate rational spline functions[C] //Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications.New York:ACM,2001:1-10.
[18] WANG Y.Intersection ofoffsets of parametric surfaces[J].Computer Aided Geometric Design,1996,13:453-465.
[19] SHAO W B,CHEN F L,LIU X F.Robust algebraic curve intersections with tolerance control[J].Computer-Aided Design,2022,147:103228.
[20] LIN Y B.GPU acceleration in VLSI back-end design:overview and case studies[C] //Proceedings of the IEEE/ACM International Conference on Computer Aided Design(ICCAD).San Diego:IEEE/ACM,2020:1-4.
[21] WONG T N,WONG K W.NC toolpath generation for arbitrary pockets with Islands[J].International Journal of Advanced Manufacturing Technology,1996,12(3):174-179.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于GPU并行的高效B样条曲线Offset算法

Efficient GPU-parallel Algorithm for B-spline Curve Offsetting

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0