Computer Science

Computer Science ›› 2026, Vol. 53 ›› Issue (9): 188-195.doi: 10.11896/jsjkx.260600137

• Computer Graphics & Multimedia • Previous Articles     Next Articles

Efficient GPU-parallel Algorithm for B-spline Curve Offsetting

YANG Yixuan1,3, WANG Weiming2,3, YANG Zhouwang1,3   

  1. 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 Online:2026-09-15 Published: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).

PDF (PC)

130

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

CLC Number: 

  • TP391
[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.
[1] WANG Dezhi, CHENG Kun. Collaborative Scheduling Strategies for Superconducting Quantum Processors and Heterogeneous Computing Systems [J]. Computer Science, 2026, 53(6A): 250600165-5.
[2] SUN Xiaoxue, JIA Haipeng, ZHANG Yunquan, YU Yue, QIN Pinle. GPU-based Implementation and Optimization of Banded Matrix LU Factorization [J]. Computer Science, 2026, 53(6): 117-127.
[3] LI Fei, LIU Song, GUO Songjian, LIU Jiazheng, ZHANG Ying, HONG Longwei, ZHANG Boxuan. High-performance Image Preprocessing Operators for Cambricon MLU Accelerator Card [J]. Computer Science, 2026, 53(6): 193-202.
[4] JI Liguang, ZHOU Bei, YANG Hongru, ZHOU Yuchang, CUI Mengqi, XU Jinchen. Parallel Detection Method of Maximum Floating-point Error Based on Gridding Particle SwarmOptimization Algorithm [J]. Computer Science, 2026, 53(2): 124-132.
[5] LIAO Qiucheng, ZHOU Yang, LIN Xinhua. Metrics and Tools for Evaluating the Deviation in Parallel Timing [J]. Computer Science, 2025, 52(5): 41-49.
[6] HUANG Chenxi, LI Jiahui, YAN Hui, ZHONG Ying, LU Yutong. Investigation on Load Balancing Strategies for Lattice Boltzmann Method with Local Grid Refinement [J]. Computer Science, 2025, 52(5): 101-108.
[7] ZHANG Manjing, HE Yulin, LI Xu, HUANG Zhexue. Distributed Two-stage Clustering Method Based on Node Sampling [J]. Computer Science, 2025, 52(2): 134-144.
[8] XU He, ZHOU Tao, LI Peng, QIN Fangfang, JI Yimu. LU Parallel Decomposition Optimization Algorithm Based on Kunpeng Processor [J]. Computer Science, 2024, 51(9): 51-58.
[9] ZHONG Zhenyu, LIN Yongliang, WANG Haotian, LI Dongwen, SUN Yufei, ZHANG Yuzhi. Automatic Pipeline Parallel Training Framework for General-purpose Computing Devices [J]. Computer Science, 2024, 51(12): 129-136.
[10] LI Siyao, LI Shanglin, LUO Jingzhi. Parallel Computing of Reentry Vehicle Trajectory by Multiple Shooting Method Based onOPENMP [J]. Computer Science, 2024, 51(11A): 231000019-6.
[11] HE Weilong, SU Lingli, GUO Bingxuan, LI Maosen, HAO Yan. Research and Implementation of Dynamic Scene 3D Perception Technology Based on BinocularEstimation [J]. Computer Science, 2024, 51(11A): 240300045-8.
[12] PENG Weidong, GUO Wei, WEI Lin. Reconfigurable Computing System for Parallel Implementation of SVM Training Based on FPGA [J]. Computer Science, 2024, 51(11A): 231100120-7.
[13] WANG Xiaozhong, ZHANG Zuyu. Multi Level Parallel Computing for SW26010 Discontinuous Galerkin Finite Element Algorithm [J]. Computer Science, 2024, 51(11A): 240700055-5.
[14] ZHAI Xulun, ZHANG Yongguang, JIN Anzhao, QIANG Wei, LI Mengbing. Parallel DVB-RCS2 Turbo Decoding on Multi-core CPU [J]. Computer Science, 2023, 50(6): 22-28.
[15] DING Yue, XU Chuanfu, QIU Haozhong, DAI Weixi, WANG Qingsong, LIN Yongzhen, WANG Zhenghua. Study on Cross-platform Heterogeneous Parallel Computing for Lattice Boltzmann Multi-phase Flow Simulations Based on SYCL [J]. Computer Science, 2023, 50(11): 32-40.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.