Systolic architecture for B-spline surfaces

B-spline surfaces are among the most commonly used types of surfaces for modeling objects in computer graphics and CAD applications. One of the time consuming operations in B-spline surface generation is that of inversion. An efficient algorithm is proposed for solving this problem. This algorithm is implemented on a systolic architecture in order to facilitate fast interactive surface design.     

B-样条曲面的保凸拼接

利用参数曲面局部凸的条件,导出了(准)均匀B-样条曲面局部凸的充分条件。证明了带有凸的平行四边形控制子网格的(准)均匀B-样条曲面片的凸的。给出了(准)均匀B-样条曲面保凸拼接的控制顶点算法,并给出了几个三次B-样条曲面保凸拼接实例。     

Blends of canal surfaces from polyhedral medial transform representations

We present a new method for constructing G¹ blending surfaces between an arbitrary number of canal surfaces. The topological relation of the canal surfaces is specified via a convex polyhedron and the design technique is based on a generalization of the medial surface transform. The resulting blend surface consists of trimmed envelopes of one- and two-parameter families of spheres. Blending the medial surface transform instead of the surface itself is shown to be a powerful and elegant approach for blend surface generation. The performance of our approach is demonstrated by several examples.     

An algorithm for finding the intersection lines between two B-spline surfaces

A divide-and-conquer algorithm is presented for finding all the intersection lines between two B-spline surfaces. Each surface is organized as an $\text{n-}\text{branch}$ tree. For each intersection line, an initial point is detected after a depth-first search along one tree, ie the host tree. Extrapolation methods are then used to trace the entire length of the line, thus the line appears naturally in a continuous form. Efficiency of the algorithm is achieved by the employment of an adaptive division strategy and by the careful choice of the representation basis of the patches on both surfaces.     

Computing a compact spline representation of the medial axis transform of a 2D shape

We present a full pipeline for computing the medial axis transform of an arbitrary 2D shape. The instability of the medial axis transform is overcome by a pruning algorithm guided by a user-defined Hausdorff distance threshold. The stable medial axis transform is then approximated by spline curves in 3D to produce a smooth and compact representation. These spline curves are computed by minimizing the approximation error between the input shape and the shape represented by the medial axis transform. Our results on various 2D shapes suggest that our method is practical and effective, and yields faithful and compact representations of medial axis transforms of 2D shapes.     

Exact and approximate computation of B-spline curves on surfaces

Curves on surfaces are important elements in computer aided geometric design. After presenting a method to explicitly compute these curves in three-dimensions, practical algorithmic issues are discussed concerning the efficiency of the implementation. Good approximations are important because of the quite high degree of exact curves on surfaces. We present two approximate solutions to the problem. The first is derived from the exact representation, while the second extends conventional least-squares approximation by incorporating the geometry of the surface as well. The efficiency and behaviour of the algorithms are evaluated by means of examples.     

Retrieving articulated 3-D models using medial surfaces

We consider the use of medial surfaces to represent symmetries of 3-D objects. This allows for a qualitative abstraction based on a directed acyclic graph of components and also a degree of invariance to a variety of transformations including the articulation of parts. We demonstrate the use of this representation for 3-D object model retrieval. Our formulation uses the geometric information associated with each node along with an eigenvalue labeling of the adjacency matrix of the subgraph rooted at that node. We present comparative retrieval results against the techniques of shape distributions (Osada et al.) and harmonic spheres (Kazhdan et al.) on 425 models from the McGill Shape Benchmark, representing 19 object classes. For objects with articulating parts, the precision vs recall curves using our method are consistently above and to the right of those of the other two techniques, demonstrating superior retrieval performance. For objects that are rigid, our method gives results that compare favorably with these methods. A preliminary version of this article was published in EMMCVPR 2005. In this extended version we have included results on the significantly larger McGill Shape Benchmark, making a stronger case for the advantages of our method for models with articulating parts. We have also included expanded introduction, medial surface computation, matching, indexing, experimental results, and discussion sections, along with several new figures.     

Fast variational design of multiresolution curves and surfaces with B-spline wavelets

Multiresolution modeling provides a powerful tool for complex shape editing. To achieve a better control of deformations and a more intuitive interface, variational principles have been used in such multiresolution models. However, when handling multiresolution constraints, the existing methods often result in solving large optimization systems. Hence, the computational time may become too excessive to satisfy the requirements for interactive design in CAD. In this paper, we present a fast approach for interactive variational design of multiresolution models. By converting all constraints at different levels to a target level, the optimization problem is formulated and solved at the lower level. Thus, the unknown coefficients of the optimization system are significantly reduced. This improves the efficiency of variational design. Meanwhile, to avoid smoothing out the details of the shape in variational modeling, we optimize the change in the deformation energy instead of the total energy of the deformed shape. Several examples and the experimental results are given to demonstrate the effectiveness and efficiency of this approach.     

Approximation by skin surfaces

We present a method to approximate a simple, regular C² surface W in by a (tangent continuous) skin surface S. The input of our algorithm is a set of approximate W-maximal balls, where the boundary of the union of these balls is homeomorphic to W. By generating patches of spheres and hyperboloids over the intersection curves of the balls the algorithm determines a one-parameter family of skin surfaces, where a parameter controls the size of the patches. The skin surface S is homeomorphic to W, and the approximate W-maximal balls in the input set are also S-maximal. The Hausdorff distance between the regions enclosed by the input surface W and the approximating skin surface S depends linearly on a parameter related to the sampling density of the approximate W-maximal balls.     

Total curvature variation fairing for medial axis regularization

We present a new fairing method for planar curves, which is particularly well suited for the regularization of the medial axis of a planar domain. It is based on the concept of total variation regularization. The original boundary (given as a closed B-spline curve or several such curves for multiply connected domains) is approximated by another curve that possesses a smaller number of curvature extrema. Consequently, the modified curve leads to a smaller number of branches of the medial axis. In order to compute the medial axis, we use the state-of-the-art algorithm from [1] which is based on arc spline approximation and a domain decomposition approach. We improve this algorithm by using a different decomposition strategy that allows to reduce the number of base cases from 13 to only 5. Moreover, the algorithm reduces the number of conic arcs in the output by approx. 50%.     

A novel method for 3D reconstruction: Division and merging of overlapping B-spline surfaces

B-spline surfaces, extracted from scanned sensor data, are usually required to represent objects in inspection, surveying technology, metrology and reverse engineering tasks. In order to express a large object with a satisfactory accuracy, multiple scans, which generally lead to overlapping patches, are always needed due to, inter-alia, practical limitations and accuracy of measurements, uncertainties in measurement devices, calibration problems as well as skills of the experimenter. In this paper, we propose an action sequence consisting of division and merging. While the former divides a B-spline surface into many patches with corresponding scanned data, the latter merges the scanned data and its overlapping B-spline surface patch. Firstly, all possible overlapping cases of two B-spline surfaces are enumerated and analyzed from a view of the locations of the projection points of four corners of one surface in the interior of its overlapping surface. Next, the general division and merging methods are developed to deal with all overlapping cases, and a simulated example is used to illustrate aforementioned detailed procedures. In the sequel, two scans obtained from a three-dimensional laser scanner are simulated to express a large house with B-spline surfaces. The simulation results show the efficiency and efficacy of the proposed method. In this whole process, storage space of data points is not increased with new obtained overlapping scans, and none of the overlapping points are discarded which increases the representation accuracy. We believe the proposed method has a number of potential applications in the representation and expression of large objects with three-dimensional laser scanner data.     

准均匀B样条曲面的多分辨率表示及应用

在多分辨率曲线和曲面造型中，B样条小波已经得到了广泛应用。曲线和曲面的多分辨率造型成为一个研究热点。通过阐述准均匀B样条曲线曲面的基于小波分解的多分辨率表示的数学原理，给出了具体的曲线和曲面小波分解算法和实验结果，说明了准均匀B样条曲面多分辨表示的优点及其在工业上的应用。     

任意散乱点集的B-样条曲面重建

为了解决工业设计中复杂形体的曲面造型问题,提出了一种张量积型的低阶B-样条曲面重建算法。先将采集到的任意拓扑形状的散乱数据点进行三次不同的参数化得到四边形控制网格,然后再采用张量积型的双二次、双三次B-样条进行拟合,在拟合的过程中采用距离函数来控制拟合误差,得到光滑的曲面。运用该方法,直接对初始散乱点集进行重建,方法简单易实施,重建效率高并且重建后的样条曲面自然满足切平面连续。与以往的方法相比,该方法在逆向工程中可以在保证连续性的情况下,得到精准的结果曲面,提高了曲面造型的质量和效率。     

Construction of the matched multiple knot B-spline wavelets on a bounded interval

In order to solve a boundary value problem using Galerkin's method, the selection of basis functions plays a crucial rule. When the solution of a boundary value problem is not enough smooth or the domain is irregular, multiple knot B-spline wavelets (MKBSWs) with locally compact support are appropriate basis functions. However, to have globally continuous basis functions, a matching across the subdomain interfaces is required. In other words, MKBSWs that are non-zero in the interelement boundaries should be matched. In this paper, we present the primal and dual matched multiple knot B-spline scaling and wavelet functions whose main properties of smoothness and biorthogonality are kept.     

LayTracks3D: A new approach for meshing general solids using medial axis transform

This paper presents an extension of the all-quad meshing algorithm called LayTracks to generate high quality hex-dominant meshes of general solids. LayTracks3D uses the mapping between the Medial Axis (MA) and the boundary of the 3D domain to decompose complex 3D domains into simpler domains called Tracks. Tracks in 3D have no branches and are symmetric, non-intersecting, orthogonal to the boundary, and the shortest path from the MA to the boundary. These properties of tracks result in desired meshes with near cube shape elements at the boundary, structured mesh along the boundary normal with any irregular nodes restricted to the MA, and sharp boundary feature preservation. The algorithm has been tested on a few industrial CAD models and hex-dominant meshes are shown in the Results section. Work is underway to extend LayTracks3D to generate all-hex meshes.     

Reconstruction of convergent smooth B-spline surfaces

Recently, there have been improvements on reconstruction of smooth B-spline surfaces of arbitrary topological type, but the most important problem of smoothly stitching B-spline surface patches (the continuity problem of B-spline surface patches) in surface reconstruction has not been solved in an effective way. Therefore, the motivation of this paper is to study how to better improve and control the continuity between adjacent B-spline surfaces.

In this paper, we present a local scheme of constructing convergent G¹ smooth bicubic B-spline surface patches with single interior knots over a given arbitrary quad partition of a polygonal model. Unlike previous work which only produces (non-controllable) toleranced G¹ smooth B-spline surfaces, our algorithm generates convergent G¹ smooth B-spline surfaces, which means the continuity of the B-spline surfaces tends to G¹ smoothness as the number of control points increases. The most important feature of our algorithm is, in the meaning of convergent approximation order, the ability to control the continuity of B-spline surfaces within the given tolerance and capture the geometric details presented by the given data points.     

A divide and conquer algorithm for medial surface calculation of planar polyhedra

The Medial Axis Transform surface, (or MAT or MS) is proving to be a useful tool for several applications and geometric reasoning tasks. However, calculation of the MAT is a time-consuming task and the benefits of the mathematical-based tool are offset by the cost of the calculation. This paper presents a method for medial surface calculation which uses subdivision to simplify the problem and hence speed up the calculation, a so-called ‘divide-and-conquer’ approach. The basis for this is a modification of the dual structure of the original object. As the calculation proceeds this structure is broken up into sub-pieces each representing a simpler sub-part of the MAT. Perhaps more importantly, this method creates a correct node decomposition of the dual structure. The paper goes on to demonstrate some applications of the results for geometric tasks, specifically offsetting and model subdivision, which are normally expensive but are simpler based on the MAT calculation results.     

基于结点调整B-spline曲面G1/G2的光滑拼接

文中提出了一种构造具有简单结点的B样条曲面G1/G2光滑拼接的方法。本方法根据B样条曲面达到拼接的条件,经过对原曲面和待拼接曲面的偏导曲线进行离散化处理和结点调整,将其转化为Bézier的表示方式。根据Bézier的拼接条件,获得B样条曲面间控制点的关系。最终实现B样条曲面G1/G2的光滑拼接。