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.     

带自由曲面的三视图重建算法研究

针对蕴含自由曲面的三视图,提出了通过恢复边界线和轮廓线进而根据这些恢复 的空间曲线重建自由曲面的算法。首先分析并证明了自由曲面在三视图中的投影性质,从而提 出边界投影和轮廓投影的匹配算法。针对视图中存在的被打断的样条曲线,提出了分段样条曲 线的爬坡算法来解决此类曲线不能匹配的问题。然后基于投影匹配序列重建出自由曲面的边界 线,再由边界投影上的点和轮廓投影端点的对应关系重建出空间轮廓线。由轮廓线等参采样构 造截面线并和边界线一起蒙皮生成最终自由曲面。本文提出的算法扩展了工程图的重建域。     

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.     

参数曲线曲面实奇异点的计算

本文主要讨论了利用Grobner基理论对参数曲线（面）的奇异点进行判断和计算。如果曲线（面）存在奇异点,由定义可知它的导矢（法矢）等于0。因此,曲线（面）奇异点的判定就是方程组的求解问题。由Hilbert弱零点定理可知,若一组多项式方程无公共零点,则其生成理想约化的Grobner基为[1]。在计算时,首先根据Grobner基理论判断 曲线（面）是否存在奇异点。当存在奇异点时,利用区间算法对实奇异点进行隔离和迭代。在确定奇异点的存在性时,根据曲线（曲面）的导矢（法矢）方程的Grobner基直 接进行判断,而不需要求解非线性代数方程组。若曲线曲面存在奇异点,进一步采用区间方法对奇异点进行隔离以确定曲线段或曲面片的正则性。该方法可以得到参数曲线曲面的所有实奇异点且达到任意精度。     

Offset of curves on tessellated surfaces

Geodesic offset of curves on surfaces is an important and useful tool of computer aided design for applications such as generation of tool paths for NC machining and simulation of fibre path on tool surfaces in composites manufacturing. For many industrial and graphic applications, tessellation representation is used for curves and surfaces because of its simplicity in representation and for simpler and faster geometric operations. The paper presents an algorithm for computing offset of curves on tessellated surfaces. A curve on tessellation (COT) is represented as a sequence of 3D points, with each line segment of every two consecutive points lying exactly on the tessellation. With an incremental approach of the algorithm to compute offset COT, the final offset curve position is obtained through several intermediate offset curve positions. Each offset curve position is obtained by offsetting all the points of COT along the tessellation in such a way that all the line segments gets offset exactly along the faces of tessellation in which the line segments are contained. The algorithm, based entirely on tessellation representation, completely eliminates the formation of local self-intersections. Global self-intersections if any, are detected and corrected explicitly. Offset of both open and closed tessellated curves, either in a plane or on a tessellated surface, can be generated using the proposed approach. The computation of offset COT is very accurate within the tessellation tolerance.     

Visualizing nonmanifold and singular implicit surfaces with point clouds

We use octree spatial subdivision to generate point clouds on complex nonmanifold implicit surfaces in order to visualize them. The new spatial subdivision scheme only uses point sampling and an interval exclusion test. The algorithm includes a test for pruning the resulting plotting nodes so that only points in the closest nodes to the surface are used in rendering. This algorithm results in improved image quality compared to the naive use of intervals or affine arithmetic when rendering implicit surfaces, particularly in regions of high curvature. We discuss and compare CPU and GPU versions of the algorithm. We can now render nonmanifold features such as rays, ray-like tubes, cusps, ridges, thin sections that are at arbitrary angles to the octree node edges, and singular points located within plot nodes, all without artifacts. Our previous algorithm could not render these without severe aliasing. The algorithm can render the self-intersection curves of implicit surfaces by exploiting the fact that surfaces are singular where they self-intersect. It can also render the intersection curves of two implicit surfaces. We present new image space and object space algorithms for rendering these intersection curves as contours on one of the surfaces. These algorithms are better at rendering high curvature contours than our previous algorithms. To demonstrate the robustness of the node pruning algorithm we render a number of complex implicit surfaces such as high order polynomial surfaces and Gaussian curvature surfaces. We also compare the algorithm with ray casting interms of speed and image quality. For the surfaces presented here, the point clouds can be computed in seconds to minutes on atypical Intel based PC. Once this is done, the surfaces can be rendered at much higher frame rates to allow some degree of interactive visualization.     

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.     

基于曲率优化的机器人砂带磨削轨迹规划

针对复杂曲面零件砂带磨削编程效率低、精度差的问题,基于B样条曲线曲面重构和机器人离线编程技术,提出了一种根据关键接触点曲率值生成工业机器人磨削轨迹的方法.首先,利用零件表面上需要进行砂带磨削的关键接触点和积累弦长参数化法构造节点矢量,从而计算出磨削轨迹的B样条基函数;其次,根据控制顶点反求矩阵得到全部未知控制点和3次B样条加工曲线;然后,分析关键接触点之间的曲率变化率和弧长,对关键点细化生成符合磨削工艺要求的目标点;最后,通过求解双3次B样条插值曲面方程获得目标点的加工姿态.以水龙头磨削为例进行试验,结果表明曲率优化算法磨削的零件表面轮廓形状明显优于截面法,且其粗糙度值能稳定在0.082 μm左右,可以有效提高工件表面加工质量.     

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

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

运动曲面求交优化算法

运动曲面求交通常采用曲面求交算法，通过反复迭代求取曲面交线，没有考虑运动曲面自身的特性进行求交简化．由于运动曲面不同运动瞬间的曲面交线之间存在必然联系，因此通过对曲面内在属性分析，提出了运用运动曲面不同运动瞬间曲面交线相似性进行运动曲面求交的优化算法．首先对两个运动曲面的基曲面进行预处理。获取表征曲面交线拓扑的特征点；根据特征点分布图确定不同运动瞬间曲面交线起始点搜索策略，采用跟踪法动态调整步长和跟踪方向求解整个交线环．采用文中方法可以有效地解决运动曲面的子环、奇点遗漏、分支跳跃、乱序跟踪和初始点求取问题，精确、鲁棒、快速地计算出交线．     

基于一元对称幂基的等距曲面有理逼近算法

给出了基于一元对称幂基的等距曲面蒙面逼近新算法。利用一元对称幂基逼近张量积Bézier曲面u向曲线的等距曲线,得到一组等距逼近曲线,取固定的v值,得到一组数据点,用反算控制顶点的方法得到过这组数据点的v向曲线。对这两组曲线用蒙面算法得到逼近的有理等距曲面。该算法计算简单,将二元等距曲面有理逼近转化为一元曲线有理逼近,同时方便地解决了整体误差问题,随着对称幂基阶数的升高,可以得到较理想的逼近效果。     

Generation of Discrete Bicubic G1 B-Spline Ship Hullform Surfaces from a Given Curve Network Using Virtual Iso-Parametric Curves

We propose a method that automatically generates discrete bicubic G1 continuous B-spline surfaces that interpolate the curve network of a ship hullform. First, the curves in the network are classified into two types: boundary curves and "reference curves". The boundary curves correspond to a set of rectangular (or triangular) topological type that can be represented with tensor-product (or degenerate) B-spline surface patches. Next, in the interior of the patches, surface fitting points and cross boundary derivatives are estimated from the reference curves by constructing "virtual" isoparametric curves. Finally, a discrete G1 continuous B-spline surface is generated by a surface fitting algorithm. Several smooth ship hullform surfaces generated from curve networks corresponding to actual ship hullforms demonstrate the quality of the method.     

The Applications of Wavelets in Hierarchical Representations and Smoothing of Curves and Surfaces

ＴｈｅＡｐｐｌｉｃａｔｉｏｎｓｏｆＷａｖｅｌｅｔｓｉｎＨｉｅｒａｒｃｈｉｃａｌＲｅｐｒｅｓｅｎｔａｔｉｏｎｓａｎｄＳｍｏｏｔｈｉｎｇｏｆＣｕｒｖｅｓａｎｄＳｕｒｆａｃｅｓ①ＳｕｎＹａｎｋｕｉＺｈｕＸｉｎｘｉｏｎｇＭａＬｉｎｇＢｅｉｊｉｎｇＵｎｖｉｅｒ...     

An extension algorithm for B-splines by curve unclamping

This paper presents an algorithm for extending B-spline curves and surfaces. Based on the unclamping algorithm for B-spline curves, we propose a new algorithm for extending B-spline curves that extrapolates using the recurrence property of the de Boor algorithm. This algorithm provides a nice extension, with maximum continuity, to the original curve segment. Moreover, it can be applied to the extension of B-spline surfaces. Extension to both single and multiple target points/curves are considered in this paper.     

具有规整曲率线网的光滑曲面设计

为了设计具有规整曲率线网且无脐点的光滑曲面,提出一种曲面交互设计算法。 采用 Bézier 曲面片光滑拼接构成的复合曲面作为表达形式,通过交替曲率线网的优化和曲面细 分得到自由形状的设计曲面,所得曲面具有规整曲率线网而且没有脐点。以此复合 Bézier 曲面 为基础,通过圆纹样条曲面优化算法得到结构规整的圆纹样条曲面,同时也能得到圆锥曲面条 模型以及曲面多层支撑结构等自由建筑曲面设计中有重要应用的几何结构。     

一种参数化可调的NURBS曲面G~2光滑拼接算法

提出一种用于NURBS曲面G2光滑拼接算法。在创建拼接曲面时,采用"参数可调"的思想,用拼接函数和指重参数先统一两基曲面的参数,计算出拼接曲面上的插值点,并以这些插值点为参考点根据G2连续的几何性质对拼接曲面的内部控制点进行修正。此算法适用于各类曲面的拼接,通过调整平衡因子和指重参数可以得到在满足G2连续的前提下各种曲率的拼接曲面,简化曲面拼接的计算过程。     

Recovering Structure from r-Sampled Objects

For a surface     in 3-space that is represented by a set S of sample points, we construct a coarse approximating polytope P that uses a subset of S as its vertices and preserves the topology of     . In contrast to surface reconstruction we do not use all the sample points, but we try to use as few points as possible. Such a polytope P is useful as a 'seed polytope' for starting an incremental refinement procedure to generate better and better approximations of     based on interpolating subdivision surfaces or e.g. Bézier patches.
Our algorithm starts from an r -sample S of     . Based on S , a set of surface covering balls with maximal radii is calculated such that the topology is retained. From the weighted α-shape of a proper subset of these highly overlapping surface balls we get the desired polytope. As there is a rather large range for the possible radii for the surface balls, the method can be used to construct triangular surfaces from point clouds in a scalable manner. We also briefly sketch how to combine parts of our algorithm with existing medial axis algorithms for balls, in order to compute stable medial axis approximations with scalable level of detail.     

Assembly variation analysis of flexible curved surfaces based on Bézier curves

Assembly variation analysis of parts that have flexible curved surfaces is much more difficult than that of solid bodies, because of structural deformations in the assembly process. Most of the current variation analysis methods either neglect the relationships among feature points on part surfaces or regard the distribution of all feature points as the same. In this study, the problem of flexible curved surface assembly is simplified to the matching of side lines. A methodology based on Bézier curves is proposed to represent the side lines of surfaces. It solves the variation analysis problem of flexible curved surface assembly when considering surface continuity through the relations between control points and data points. The deviations of feature points on side lines are obtained through control point distribution and are then regarded as inputs in commercial finite element analysis software to calculate the final product deformations. Finally, the proposed method is illustrated in two cases of antenna surface assembly.     

Plus curves and surfaces

The formulations for parametric curves and surfaces that are based on control points are revised to use control lines and control planes instead. Curves defined by control lines are called control-line curves or plus curves, and surfaces defined by control planes are called control-plane surfaces or plus surfaces; the plus implies that in addition to the control points, gradient vectors at the control points are used to design curves and surfaces. The new curve and surface formulations provide more flexibility than traditional formulations in geometric design. Properties of plus curves and surfaces are investigated and an application of plus surfaces in smooth parametric representation of polygon meshes is introduced.