An algorithm for finding intersection between ball B-spline curves

摘要

A ball B-spline curve (BBSC) is a skeleton based solid model representation, which consists of a B-spline curve and a B-spline function serving as the (varying) radius of a ball moving along the B-spline curve. The surface shape specified by the BBSC is the envelope of the moving ball and thus the BBSC is very suitable for representing vascular shapes. To apply this good representation in various fields as CSG-to-boundary conversion, Boolean operations, geometric design, pattern recognition, scientific visualization, this paper proposes an efficient algorithm to solve their common fundamental intersection problem. The surface of each BBSC is decomposed into a starting spherical patch, a set of lateral surfaces defined by ball Bézier curves (BBC), and an ending spherical patch. The intersection algorithm proceeds in four steps: (1) tessellating both BBSCs into triangular meshes and computing the intersection curves between the triangular meshes, which serve as the initial intersections for later refinement; (2) parameterizing the surfaces/patches of one BBSC and implicitizing the surfaces/patches of the other BBSC; (3) calculating the intersection curves between a parametric surface and an implicit surface numerically by using the Newton’s method; and (4) tracing the intersection curves for the construction of intersection solid regions. In particular, we present simple methods for parameterization and implicitization of BBSCs, which are the core of the proposed algorithm. And BBSC is a solid model, therefore the intersection of BBSCs is the intersection of solid models, and the final intersection result is also a solid object. Experimental results show that our method is able to efficiently find the intersections of BBSCs with high accuracy.