Feature-based decomposition of trimmed surface

A trimmed surface is usually represented by a parametric surface and a set of trimming curves. Because of the complexity in manipulating trimmed surfaces, many CAD processes and algorithms cannot be applied to trimmed surfaces directly. It is thus desirable to represent a trimmed surface by a group of regular surfaces. In this paper, an algorithm for decomposing a trimmed surface is presented. First, bisectors of the Voronoï diagram developed in the parametric space are used to define an isolated region for every trimming curve. Feature points on the trimming curves are extracted by considering curvatures of the curves. Correspondence between feature points and vertices on the bisectors are established by considering the similarity between the trimming curves and the bisectors. Regions of parametric patches are then identified. Finally, a group of regular surfaces are constructed by interpolating a set of sampled surface points on each of the identified regions.     

一种参数多项式曲面片的逐点生成算法

在计算机绘图中，一般来说，曲线实际上是由折线代替，而曲面实为小平面拼接而成，在使计算量降到最低的情况下画出真正的曲线方面，已有许多文章研究了曲线的逐点生成方法，并取得了一定的进展，但是尚无有效的快速逐点生成曲面的方法，为了快速逐点生成曲面，在建立多项式函数递推计算公式和算法的基础上，给出了一种逐点生成参数多项式曲面片的算法，由于此算法中只用到整数加法运算，且点数的适当选取可使计算量达到极小，因此是一种很有效的算法，该方法还可以加以改进，而用于有理函数，这无疑对有理曲线曲面（如NURBS曲线曲面）的快速生成以及对计算机图形学的其他一些领域都是有意义的。     

Bézier representation for cubic surface patches

The paper describes a new method for creating rectangular Bézier surface patches on an implicit cubic surface. Traditional techniques for representing surfaces have relied on parametric representations of surfaces, which, in general, generate surfaces of implicit degree 8 in the case of rectangular Bézier surfaces with rational biquadratic parameterization. The method constructs low-degree algebraic surface patches by reducing the implicit degree from 8 to 3. The construction uses a rectangular biquadratic Bézier control polyhedron that is embedded within a tetrahedron and satisfies a projective constraint. The control polyhedron and the resulting cubic surface patch satisfy all of the standard properties of parametric Bézier surfaces, including interpolation of the corners of the control polyhedron and the convex-hull property.     

Shape aware normal interpolation for curved surface shading from polyhedral approximation

Independent interpolation of local surface patches and local normal patches is an efficient way for fast rendering of smooth curved surfaces from rough polyhedral meshes. However, the independently interpolating normals may deviate greatly from the analytical normals of local interpolating surfaces, and the normal deviation may cause severe rendering defects when the surface is shaded using the interpolating normals. In this paper we propose two novel normal interpolation schemes along with interpolation of cubic Bézier triangles for rendering curved surfaces from rough triangular meshes. Firstly, the interpolating normal is computed by a Gregory normal patch to each Bézier triangle by a new definition of quadratic normal functions along cubic space curves. Secondly, the interpolating normal is obtained by blending side-vertex normal functions along side-vertex parametric curves of the interpolating Bézier surface. The normal patches by these two methods can not only interpolate given normals at vertices or boundaries of a triangle but also match the shape of the local interpolating surface very well. As a result, more realistic shading results are obtained by either of the two new normal interpolation schemes than by the traditional quadratic normal interpolation method for rendering rough triangular meshes.     

Surface-to-surface intersections

Techniques for computing intersections of algebraic surfaces with piecewise rational polynomial parametric surface patches and intersections of two piecewise rational polynomial parametric surface patches are discussed. The techniques are classified using four categories-lattice evolution methods, marching methods, subdivision methods, and analytic methods-and their principal features are discussed. It is shown that some of these methods also apply to the general parametric surface-intersection problem     

Constructive shell representations for freeform surfaces and solids

We usually model freeform surfaces (mathematically, 2D r-sets embedded in 3D Euclidean space E³) as a finite union of patches represented in the traditional parametric or the recently developed algebraic forms. The article introduces a new representation scheme for freeform surfaces called constructive shell representation (CSR), that draws on recent research on algebraic patches. CSRs of surfaces that constitute boundaries of solids are very useful for solid modeling. They represent thick shells derived from freeform surfaces and provide a means to compute exact CSG representations of freeform solids     

A new quadratic and biquadratic algorithm for curve and surface estimation

A new deterministic quadratic parametric algorithm is introduced for curve estimation. A parametric biquadratic algorithm for surface estimation, based on the one for curve estimation is also presented. Our algorithm does not assume that the surface to be estimated, based on a given set of data in the three-dimensional space, has a continuous first derivative, nor does it assume that the data satisfy the assumption of stationarity or the intrinsic hypothesis. The grid formed by the given data does not have to be equidistant; in other words the distance between neighboring points in the two-dimensional domain does not have to be the same. Also since the algorithm leads to parametric equations for the patches of the surface, the estimating surface does not need to be a function. Appropriate parameters are introduced in the blending functions of the parametric equations to produce tension. The algorithm does not require inversion of matrices and is faster than splines and kriging. The estimated surface passes through the given data points. Error analysis based on estimating surfaces of known functions from a sample of data and then comparing to their value, are made. A comparison with biqubic natural splines based on data generated from known functions is also given.     

Blending Parametric Patches with Subdivision Surfaces

In this paper the problem of blending parametric surfaces using subdivision patches is discussed. A new approach, named removing-boundary, is presented to generate piecewise-smooth subdivision surfaces through discarding the outmost quadrilaterals of the open meshes derived by each subdivision step. Then the approach is employed both to blend parametric bicubic B-spline surfaces and to fill n-sided holes. It is easy to produce piecewise-smooth subdivision surfaces with both convex and concave corners on the boundary, and limit surfaces are guaranteed to be C2 continuous on the boundaries except for a few singular points by the removing-boundary approach. Thus the blending method is very efficient and the blend-ing surface generated is of good effect.     

Finding Starting Points for Tracing Surface Intersections

1 Introduction Finding out proper starting points for all the intersection curves between two surfaces is a key process in numerical tracing methods for surface-surface intersection (SSI) problems. A number of methods [1] are introduced to calculate the starting points. Cugini et al. [2] introduced the concept of shrinking bounding boxes to calculate starting points. This method is simple and in some cases effective, but it may miss some intersection components. Muellenheim [3] presented an…     

Finding Starting Points for Tracing Surface Intersections

To find starting points for all the intersection curves, one of the surfaces is subdivided into some small surface patches. Based on a correlative algorithm of computing the minimum distance of two surfaces, the intersections of every patch with another surface are detected, and starting points are calculated by dichotomy. This algorithm shows superior efficiency in the computational complexity and number of iterations needed. It can be used to determine exact starting points on all possible solution curves between any kinds of parametric sculptured surfaces.     

Stripification of Free-Form Surfaces With Global Error Bounds for Developable Approximation

Developable surfaces have many desired properties in the manufacturing process. Since most existing CAD systems utilize tensor-product parametric surfaces including B-splines as design primitives, there is a great demand in industry to convert a general free-form parametric surface within a prescribed global error bound into developable patches. In this paper, we propose a practical and efficient solution to approximate a rectangular parametric surface with a small set of C ⁰ -joint developable strips. The key contribution of the proposed algorithm is that, several optimization problems are elegantly solved in a sequence that offers a controllable global error bound on the developable surface approximation. Experimental results are presented to demonstrate the effectiveness and stability of the proposed algorithm.     

Detection of loops and singularities of surface intersections

Two surface patches intersecting each other generally at a set of points (singularities), form open curves or closed loops. While open curves are easily located by following the boundary curves of the two patches, closed loops and singularities pose a robustness challenge since such points or loops can easily be missed by any subdivision or marching-based intersection algorithms, especially when the intersecting patches are flat and ill-positioned. This paper presents a topological method to detect the existence of closed loops or singularities when two flat surface patches intersect each other. The algorithm is based on an oriented distance function defined between two intersecting surfaces. The distance function is evaluated in a vector field to identify the existence of singular points of the distance function since these singular points indicate possible existence of closed intersection loops. The algorithm detects the existence rather than the absence of closed loops and singularities. This algorithm requires general C² parametric surfaces.     

在任意拓扑三角形网格上的光滑样条曲面

介绍了一种在控制三角形网格上创建光滑样条曲面的算法,该控制网格能够刻画具有或没有边界的任意自由曲面.生成的曲面有一个4次参数多项式表示并且被表示成一个切平面连续的三角形Bézier片网.曲面对网格的逼近程度受到一个混合比控制,当混合比为0时,产生的曲面插值网格.该算法是一种局部方法,简单且效率高,适合于外形设计.     

Isometric Piecewise Polynomial Curves

The main preoccupations of research in computer-aided geometric design have been on shape-specification techniques for polynomial curves and surfaces, and on the continuity between segments or patches. When modelling with such techniques, curves and surfaces can be compressed or expanded arbitrarily. There has been relatively little work on interacting with direct spatial properties of curves and surfaces, such as their arc length or surface area. As a first step, we derive families of parametric piecewise polynomial curves that satisfy various positional and tangential constraints together with arc-length constraints. We call these curves isometric curves. A space curve is defined as a sequence of polynomial curve segments, each of which is defined by the familiar Hermite or Bézier constraints for cubic polynomials; as well, each segment is constrained to have a specified arc length. We demonstrate that this class of curves is attractive and stable. We also describe the numerical techniques used that are sufficient for achieving real time interaction with these curves on low-end workstations.     

Approximate development of trimmed patches for surface tessellation

This paper presents a method for constructing an auxiliary planar domain of triangulation for tessellating trimmed parametric surface patches. By minimizing a mapping error function, an approximate locally isometric mapping between a given trimmed parametric surface patch and its triangulation domain is constructed. In this way the shape of triangular elements on the triangulation domain is approximately preserved when mapped into three-dimensional space. We also provide an efficient method to achieve a good initial guess for the minimization of the mapping error function. Furthermore, our proposed method guarantees a homeomorphism between a triangulation domain and parametric space/given surface patch by robustly removing the possibility of self-intersection on the developed surface net. Practical application of the proposed algorithm can include the formation of ship hulls, ducts, shoes, clothing and automobile parts as well as the surface meshing procedure.     

Surface parameterization in volumetric images for curvature-based feature classification

Curvature-based surface features are well suited for use in multimodal medical image registration. The accuracy of such feature-based registration techniques is dependent upon the reliability of the feature computation. The computation of curvature features requires second derivative information that is best obtained from a parametric surface representation. We present a method of explicitly parameterizing surfaces from volumetric data. Surfaces are extracted, without a global thresholding, using active contour models. A monge/spl acute/ basis for each surface patch is estimated and used to transform the patch into local, or parametric, coordinates. Surface patches are fit to a bicubic polynomial in local coordinates using least squares solved by singular value decomposition. We tested our method by reconstructing surfaces from the surface model and analytically computing Gaussian and mean curvatures. The model was tested on analytical and medical data.     

Loop detection in surface patch intersections

A condition is presented for guaranteeing that all branches of the curve of intersection of two parametric surfaces patches contain a point on at least one of the patch boundary curves. This is of value because it eliminates a robustness limitation which arises when computing surface intersections using the marching method, namely, assuring that all branches of the intersection curve have been found. The intersection curve of any two surface patches meeting the prescribed condition can be computed by locating points where patch boundary curves intersect the opposing patch, and then using those points as starting points for the marching algorithm.     

Toward a model-based Bayesian theory for estimating and recognizingparameterized 3-D objects using two or more images taken from differentpositions

A parametric modeling and statistical estimation approach is proposed and simulation data are shown for estimating 3-D object surfaces from images taken by calibrated cameras in two positions. The parameter estimation suggested is gradient descent, though other search strategies are also possible. Processing image data in blocks (windows) is central to the approach. After objects are modeled as patches of spheres, cylinders, planes and general quadrics-primitive objects, the estimation proceeds by searching in parameter space to simultaneously determine and use the appropriate pair of image regions, one from each image, and to use these for estimating a 3-D surface patch. The expression for the joint likelihood of the two images is derived and it is shown that the algorithm is a maximum-likelihood parameter estimator. A concept arising in the maximum likelihood estimation of 3-D surfaces is modeled and estimated. Cramer-Rao lower bounds are derived for the covariance matrices for the errors in estimating the a priori unknown object surface shape parameters     

The approximation of non-degenerate offset surfaces

This paper describes algorithms for approximating the offsets to general piecewise parametric surfaces by networks of bicubic patches. The surface to be offset may be composed of arbitrary parametric patches, provided precise tangent continuity obtains across all patch boundaries and the surface metric is everywhere non-singular (i.e., a unique surface normal is defined).The approximation scheme consists of three stages: (1) A differential surface analysis is performed to ascertain the extremum principal radii of curvature for each patch — this constrains the offset magnitude that may be specified without degeneration of the offset. (2) The parametric domain of each patch is sub-divided, and a bicubic approximant to the offset for each sub-domain is computed. (3) A tolerance analysis is performed on each patch of the offset approximation to evaluate its extremum deviations from the true offset.The accuracy of the offset approximation increases with the degree of subdivision of the parametric domain of each patch. Fractional errors in the range 10⁻² to 10⁻³ are typical for two- or three- fold sub-division of each parametric variable (four- and nine- fold area division respectively), provided the surface is smooth and its smallest concave radius of curvature considerably exceeds the specified offset magnitude. A fully automatic tolerance-based surface offset capability may be developed by providing feedback between stages (3) and (2), successive degrees of parametric sub-division being determined by the errors from prior approximations until the desired accuracy is achieved.     

细节高度复杂表面模型的视点相关渐进传输

针对细节高度复杂模型的特点,提出一种视点相关的渐进传输方法.根据人的视觉特征,算法将模型表示为多分辨率的四边形参数面片和表面法向细节纹理.该算法利用法向映射提高传输和绘制的效率,然后随着视点的变化动态细化和传输当前视点下轮廓部分的参数面片信息,从而最大限度地减少了模型传输时面片的数量.参数面片的结构规则,面片之间关联性低,因此能够按任意顺序高效地传输,从而实现真正的视点相关传输,并可以采用有效的编码方法对其结构和几何信息进行压缩.实验结果表明了该算法的有效性,特别适合于表面细节复杂的表面模型的交互传输和绘制.