Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/141397
Title: An intersection algorithm for disk B-spline curves
Authors: Ao, Xuefeng
Fu, Qian
Wu, Zhongke
Wang, Xingce
Zhou, Mingquan
Chen, Quan
Seah, Hock Soon
Keywords: Engineering::Computer science and engineering
Issue Date: 2018
Source: Ao, X., Fu, Q., Wu, Z., Wang, X., Zhou, M., Chen, Q., & Seah, H. S. (2018). An intersection algorithm for disk B-spline curves. Computers and Graphics, 70, 99-107. doi:10.1016/j.cag.2017.07.021
Journal: Computers and Graphics
Abstract: In this paper, we propose a method for finding all 2D intersection regions between disk B-spline curves (DBSCs), which is very crucial for DBSC's wide applications such as computer calligraphy, computer 2D animations, and non-photorealistic rendering. As a DBSC represents a region on a plane, the intersection of two DBSCs is a 2D region. To determine the region, the key is to compute the intersection points of the boundaries of two DBSCs. In our algorithm, the boundary of a DBSC is decomposed into four components: the upper boundary, the lower boundary, the start arc, and the end arc. The intersection of two DBSCs can be converted into the intersections between these four components. The main difficulty is to find the intersection involving the upper and lower boundaries of the two DBSCs, as they are variable offsets from the skeletons of the DBSC that are B-spline curves. In our approach, first the DBSCs are subdivided into several disk Bézier curves (DBCs). Therefore the problem of computing intersections of the DBSCs is converted into computing intersection of two DBCs. Then, the disk Bézier clipping method is proposed to exclude regions that have no intersection for the intersection of the two DBCs. In the case of where there is an intersection, we calculate the comparatively rough intersection to be used as initial values for later refinement through the disk Bézier clipping method. Besides, high precision (up to 10e−15) intersections are achieved by using the Newton's iteration, which is quadratic convergent. The experimental results demonstrate that our algorithm can very efficiently compute all intersections between DBSCs with high precision. Our main contributions in this paper are as follows. First, for the first time, we give the direct parametric expression of DBSC's boundary, which can be simply and conveniently used to compute the properties of DBSC's boundary. Second, our proposed approach of calculating high-accuracy intersections of DBSCs makes DBSC a flexible and effective stroke representation that can be applied to further research such as corresponding computation, automatically coloring, region detection and so on.
URI: https://hdl.handle.net/10356/141397
ISSN: 0097-8493
DOI: 10.1016/j.cag.2017.07.021
Rights: © 2017 Elsevier Ltd. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

SCOPUSTM   
Citations 20

2
Updated on Mar 2, 2021

PublonsTM
Citations 20

2
Updated on Mar 7, 2021

Page view(s)

143
Updated on May 28, 2022

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.