Applications of power series in computational geometry

A number of algorithms are presented for obtaining power series expansions of curves and surfaces at a point. Some results on the radius of convergence are given. Two applications of series are given:

1. • for curve tracing algorithms, where a truncated series is used to approximate the curve of intersection of two surfaces

2. • to define nth degree geometric continuity, for arbitrary

圆柱与圆锥轴线相交时左侧相贯线上最右点的解析证明与图解

轴线相交的圆柱、圆锥两曲面立体相贯时,产生左右两条空间相贯线曲线。该文以左侧相贯线为研究对象,用数学方法证明圆柱立体的半径在一定范围内变化时,左侧相贯线上最右点的变化规律,由此提出了准确绘制左侧相贯线上最右点的图解方法。左侧相贯线上的最右点在两条特殊相贯线上,分别在锥和与锥相切的球的相贯线上及在柱和与锥相切的球的相贯线上。     

曲面交线的B样条优化逼近

目前，在比较成熟的商业几何核心系统中，曲面的交线是一种基于位置算子的“精确”表示或称为“过程”表示．这样的交线如果用在几何建模操作中，必须输出为系统支持的曲线表示(如B样条表示)．现有的几何核心系统中曲面交线的B样条逼近算法存在控制点数目过多和连续性偏低(C^1)的缺点，导致下游操作结果太复杂且连续性低．基于此，提出了一种曲面交线的B样条逼近算法，使控制点数目减少为原来的三分之一，而连续阶上升为C^2．该算法已经在SolidWorks系统中得到应用，效果良好．     

复合三角Bézier曲面求交和裁剪的实现

该文利用三角Bézier曲面片的可分割性,解决了迭代收敛、初始交点计算等问题;通过近曲面点、边界点跨越等过程,实现了由一个初始交点将跨越许多曲面片的整条交线跟踪出来的设想.将各交点作为型值点插入曲面中,对三角网格进行三角再划分,以交线为界进行三角网格和型值点的分离,最后重新生成两张复合曲面,实现了裁剪的目的.测试结果显示,此方法简单、可靠,能够满足曲面造型的要求.     

参数多项式曲线的快速逐点生成算法

给出了参数多项曲线（包括Ｂｅｚｉｅｒ曲线、Ｂ样条曲线等）的一种快速逐点生成算法．在曲线的逐点生成过程中,只用到加减法,故效率极高．而且,此方法可在两３方面加以推广,一是推广到有理参数曲线（包括非均匀有理Ｂ样条曲线）,一是推广到多项式参数曲面以及更高维的多项式参数函数．     

Marching along surfacesurface intersection curves with an adaptive step length

A method for generating points on the intersection of two C² smooth parametric surfaces is presented. In each generated point the tangent and the curvature of the intersection curve are obtained from the surface positions, first and second derivatives. Initial approximation of the next point lies on a parabola approximating the intersection curve in a vicinity of the last point found. The length of the parabola between the two points is evaluated so that its maximal deviation from the chord joining the points is not greater than a given deviation tolerance. The new point is relaxed to the intersection curve.     

A theory of self-calibration of a moving camera

There is a close connection between the calibration of a single camera and the epipolar transformation obtained when the camera undergoes a displacement. The epipolar transformation imposes two algebraic constraints on the camera calibration. If two epipolar transformations, arising from different camera displacements, are available then the compatible camera calibrations are parameterized by an algebraic curve of genus four. The curve can be represented either by a space curve of degree seven contained in the intersection of two cubic surfaces, or by a curve of degree six in the dual of the image plane. The curve in the dual plane has one singular point of order three and three singular points of order two.If three epipolar transformations are available, then two curves of degree six can be obtained in the dual plane such that one of the real intersections of the two yields the correct camera calibration. The two curves have a common singular point of order three.Experimental results are given to demonstrate the feasibility of camera calibration based on the epipolar transformation. The real intersections of the two dual curves are found by locating the zeros of a function defined on the interval [0, 2]. The intersection yielding the correct camera calibration is picked out by referring back to the three epipolar transformations.     

Bezier surface/surface intersection

The computational requirements and accuracy of two methods for finding the intersection of Bezier surfaces are examined. In both methods, the existence of an intersection curve is confirmed by using the convex hull property of such surfaces. The first method evaluates the intersection by recursive subdivision of two patches with overlapping hulls. The second method detects a point on the intersection curve and then incrementally traces the intersection in the parametric spaces of the two surfaces. With both methods, the intersection of a pair of first-order planar patches must be solved analytically. The intersection is approximated by first-order Bezier patches in the first case and by planar triangles in the second. Overall, the method of incremental tracing is shown to give more accurate results than the method of recursive subdivision     

步长自适应追踪法曲面求交技术的研究

对具有多种曲面特征的实体进行建模,必须对相邻的单面片进行拼接。传统曲面求交技术有很多缺陷,例如在求交精度、求交速度上不能同时满足要求。对此提出步长可自适应的追踪法进行曲面求交,将五次非均匀B样条作为拟合曲线,在求交过程中将追踪步长值与交线末端曲率相关联,可以使步长根据具体环境实时变化。限定精度阈值[ε]为0.001?mm,将曲面求交试验在自主研发的逆向系统Surface Reverse中进行,分别采用传统追踪法和基于步长自适应的追踪法进行曲面求交,结果表明,追踪步长可自适应的追踪法求取交线的计算量少、用时较短,且交线精度可达到μm级。这种相交算法稳定、准确且速度较快。     

运动曲面求交优化算法

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

A reliable triangular mesh intersection algorithm and its application in geological modelling

We introduce a reliable intersection algorithm for manifold surface meshes. The proposed algorithm builds conforming surface meshes from a set of intersecting triangulated surfaces. This algorithm effectively handles all degenerate triangle–triangle intersection cases. The key idea of the algorithm is based on an extensive set of triangle–edge intersection cases, combined with an intersection curve tracking method. The intersection operations do not rely on global spatial search operations and no remeshing steps are needed. The intersection curves are introduced into each surface mesh using a unique curve imprinting algorithm. The imprinting algorithm naturally handles degenerate intersection cases of many surfaces at an edge or at a point. The algorithm produces a consistent mesh data structure for subsequent mesh optimization operations. The mesh intersection algorithm is used within a general framework for modelling and meshing of geological formations, which are essential for reliable mathematical modelling of oil reservoirs.     

曲率连续的三角B样条曲线与曲面

给出了一种二次参数三角样条曲线,基函数由一组特殊的二次三角多项式组成;曲线的每一段由三个控制顶点生成,不仅具有二次均匀B样条曲线的端点性质,而且具有更好的逼近性、整体达到曲率连续。该曲线(面)可用于曲线曲面的造型。     

线框设计中轮廓线的自动生成

通常的二维布尔运算只适用于封闭的轮廓线，无法应用于任意类型的曲线．本文在分析了二维封闭轮廓线布尔运算的基础上，给出了基于曲线交点处局部邻域的曲线分类方法，并由此得到任意曲线间的布尔运算，来自动生成所需的轮廓线，这种方法还可以推广到三维设计．     

Surface intersection by switching from recursive subdivision to iterative refinement

This paper discusses an attempt to devise an efficient (involving minimal computations), accurate (numerically high precision), exhaustive (detecting all possible solutions), and robust (working without failures) method for detecting intersection of two parametric surfaces. The method starts with subdivision to ensure that all solutions are detected. Later it switches over to numerical iterative refinement for efficient and accurate evaluation of the intersection curve. The switching takes place only when the convergence of the refinement method is guaranteed. The necessary theory to arrive at a computable condition leading to this guarantee has been developed using fixed-point and contractionmapping theorems from topology and mathematical analysis. The implementation is discussed elaborating the data structures and the algorithms used for (1) detecting segments of the intersection curve, (2) generating points on these segments using refinement, and (3) tracing a continuous curve by identifying neighboring segments and joining them in order.     

Computing isophotos of surface of revolution and canal surface

Isophote of a surface consists of a loci of surface points whose normal vectors form a constant angle with a given fixed vector. It also serves as a silhouette curve when the constant angle is given as π/2. We present efficient and robust algorithms to compute isophotes of a surface of revolution and a canal surface. For the two kinds of surfaces, each point on the isophote is derived by a closed-form solution. To find each connected component in the isophote, we utilize the feature of surface normals. Both surfaces are decomposed into a set of circles, where the surface normal vectors at points on each circle construct a cone. The vectors which form a constant angle with given fixed vector construct another cone. We compute the parametric range of the connected component of the isophote by computing the parametric values of the surface which derive the tangential intersection of these two cones.     

平面椭圆与二次曲线间位置关系的判别式

平面实体间的碰撞检测中,经常需要讨论二次曲线间的位置关系．根据切点既是交点,又是最近／最远距离点的性质,结合结式理论推导出若干代数多项式,并用来判定平面椭圆与二次曲线间的位置关系．该方法直观简单,仅需要简单四则运算,可以直接应用于判别运动曲线间的位置关系．最后的实例及其比较表明,该方法应用范围广,结果也稳定．     

Vector elimination: A technique for the implicitization, inversion, and intersection of planar parametric rational polynomial curves

In this paper vector techniques and elimination methods are combined to help resolve some classical problems in computer aided geometric design. Vector techniques are applied to derive the Bezout resultant for two polynomials in one variable. This resultant is then used to solve the following two geometric problems: Given a planar parametric rational polynomial curve, (a) find the implicit polynomial equation of the curve (implicitization); (b) find the parameter value(s) corresponding to the coordinates of a point known to lie on the curve (inversion). The solutions to these two problems are closed form and, in general, require only the arithmetic operations of addition, subtraction, multiplication, and division. These closed form solutions lead to a simple, non-iterative, analytic algorithm for computing the intersection points of two planar parametric rational polynomial curves. Extensions of these techniques to planar rational Bezier curves are also discussed.     

三角网格上的代数曲面重建

提出一种用分片代数曲面构造三角曲面片的方法,利用具有公共边的2个三角形区域的4个顶点的函数值以及公共边2个端点的外法向量来构造一个二次曲面V(g)和一个截面V(h),其交V(g,h)即为2个三角曲面片的公共边界曲线.对每个已确定了边界条件的三角片内部进一步划分成3部分,每部分各自定义一个三次代数曲面.这3个三次代数曲面不仅在其交线处光滑拼接,而且分别沿三角形的边界与V(g)光滑拼接,从而构成一个具有GC1连续性的分片代数曲面.对于只属于一个三角片的边界留有一个自由度,可对曲面形状加以控制.     

保测地曲率的曲面曲线设计

给出一种在给定光滑曲面上进行曲线设计的算法．由于曲面上曲线的曲率向量可分解为测地曲率向量与法曲率向量的和,故可以通过设计平面源曲线,并将这条源曲线保测地曲率对应到给定曲面上,得到一条测地曲率和平面源曲线的曲率相同的目标曲线．取给定曲面上一点为初始点,逐次迭代跟踪得到整条目标曲线．该算法既可以用来进行曲面上的图案设计,也可用于求解光滑曲面上的测地线。