平面向量场与曲率分析在曲面求交中的应用

在曲面求交算法中，初始跟踪点的确定和交线分支的跟踪是最关键的两个问题．本文总结了用平面向量场确定初始跟踪点的算法，给出了使用曲率分析精确计算跟踪方向，并估计跟踪步长的方法．应用平面向量场和曲率分析，作者实现了高效可靠的ＮＵＲＢＳ曲面求交算法．     

Calculating ellipse overlap areas

We present an approach for finding the overlap area between two ellipses that does not rely on proxy curves. The Gauss-Green formula is used to determine a segment area between two points on an ellipse. Overlap between two ellipses is calculated by combining the areas of appropriate segments and polygons in each ellipse. For four of the ten possible orientations of two ellipses, the method requires numerical determination of transverse intersection points. Approximate intersection points can be determined by solving the two implicit ellipse equations simultaneously. Alternative approaches for finding transverse intersection points are available using tools from algebraic geometry, e.g., based on solving an Eigen-problem that is related to companion matrices of the two implicit ellipse curves. Implementations in C of several algorithm options are analyzed for accuracy, precision and robustness with a range of input ellipses.     

隐式曲面／参数曲面的求交算法

本文介绍了一种实用有效的隐式曲面／参数曲面求交算法。算法主要分为两部分：特征初始点的求取和单调段的跟踪。解双变量多项式方程求解特征初始点。跟踪在三维空间进行，易于控制跟踪步长和离散交点对交线的逼近精度。算法不离散参数曲面，不漏交。     

Intersecting a freeform surface with a general swept surface

We present efficient and robust algorithms for intersecting a rational parametric freeform surface with a general swept surface. A swept surface is given as a one-parameter family of cross-sectional curves. By computing the intersection between a freeform surface and each cross-sectional curve in the family, we can solve the intersection problem. We propose two approaches, which are closely related to each other. The first approach detects certain critical points on the intersection curve, and then connects them in a correct topology. The second approach converts the intersection problem to that of finding the zero-set of polynomial equations in the parameter space. We first present these algorithms for the special case of intersecting a freeform surface with a ruled surface or a ringed surface. We then consider the intersection with a general swept surface, where each cross-sectional curve may be defined as a rational parametric curve or as an implicit algebraic curve.     

Determining distance to a surface represented in piecewise fashion with surface patches

A previously reported method for finding the points of intersection of a vector and a parametric surface patch is examined. However, before the point of intersection of a vector and a patch can be determined, it is necessary to find the patch (or patches) on a multipatch surface intersected by the vector. A technique is described for determining the patch or patches intersected by a vector, given the patches intersected by a single plane containing the intersecting vector. Once these have been found, the point of intersection can be determined and the distance to the multipatch surface obtained.     

A linear pivoting method for detecting and tracing planar section curves of free-form surfaces

A linear programming procedure is presented for finding the curves of intersection of a plane with a bicubic surface patch. The procedure appears to work with any free-form surface having the property that the surface lies within the convex hull of its control points. Examples and images are provided.     

Projection matrix by orthogonal vanishing points

Calculation of camera projection matrix, also called camera calibration, is an essential task in many computer vision and 3D data processing applications. Calculation of projection matrix using vanishing points and vanishing lines is well suited in the literature; where the intersection of parallel lines (in 3D Euclidean space) when projected on the camera image plane (by a perspective transformation) is called vanishing point and the intersection of two vanishing points (in the image plane) is called vanishing line. The aim of this paper is to propose a new formulation for easily computing the projection matrix based on three orthogonal vanishing points. It can also be used to calculate the intrinsic and extrinsic camera parameters. The proposed method reaches to a closed-form solution by considering only two feasible constraints of zero-skewness in the internal camera matrix and having two corresponding points between the world and the image. A nonlinear optimization procedure is proposed to enhance the computed camera parameters, especially when the measurement error of input parameters or the skew factor are not negligible. The proposed method has been run on real and synthetic data for more precise evaluations. The provided experimental results demonstrate the superiority of the proposed method.     

随机抽样一致性平面拟合及其应用研究

针对传统平面拟合算法难以拟合包含异常值点云的问题,提出结合特征值法的随机抽样一致性（RANSAC）平面拟合算法。随机选取三个点云数据直接计算平面,选择阈值统计在此平面上的内点数量,多次重复求得包含最多内点的平面,并以这些内点以特征值法进行平面拟合得到所求平面方程。对各种包含误差及异常值的平面点云进行拟合计算,并与传统算法进行比较,将其应用于双目重构得到的隧道开挖掌子面岩体三维数字模型中节理面点云平面拟合。实验结果表明该方法可以很好地适应各种误差和异常值的情况,稳定地得到较好的平面参数估计值,是一种鲁棒的平面拟合算法。     

Torus to Torus Intersection

The most difficult problem in surface intersection is to determinate all the initial tracing points. Collinear normal line is a power tool for solving this problem. A lemma about the existence of collinear normal line between two tori is presented, based on this lemma an algorithm for finding all the initial tracing points is implemented, numerical examples show that it is robust and efficient.     

Direct boolean intersection between acquired and designed geometry

In this paper, a new shape modeling approach that can enable direct Boolean intersection between acquired and designed geometry without model conversion is presented. At its core is a new method that enables direct intersection and Boolean operations between designed geometry (objects bounded by NURBS and polygonal surfaces) and scanned geometry (objects represented by point cloud data).We use the moving least-squares (MLS) surface as the underlying surface representation for acquired point-sampled geometry. Based on the MLS surface definition, we derive closed formula for computing curvature of planar curves on the MLS surface. A set of intersection algorithms including line and MLS surface intersection, curvature-adaptive plane and MLS surface intersection, and polygonal mesh and MLS surface intersection are successively developed. Further, an algorithm for NURBS and MLS surface intersection is then developed. It first adaptively subdivides NURBS surfaces into polygonal mesh, and then intersects the mesh with the MLS surface. The intersection points are mapped to the NURBS surface through the Gauss-Newton method.Based on the above algorithms, a prototype system has been implemented. Through various examples from the system, we demonstrate that direct Boolean intersection between designed geometry and acquired geometry offers a useful and effective means for the shape modeling applications where point-cloud data is involved.     

Efficient geometric algorithms on the EREW PRAM

We present a technique that can be used to obtain efficient parallel geometric algorithms in the EREW PRAM computational model. This technique enables us to solve optimally a number of geometric problems in O(log n) time using O(n/log n) EREW PRAM processors, where n is the input size of a problem. These problems include: computing the convex hull of a set of points in the plane that are given sorted, computing the convex hull of a simple polygon, computing the common intersection of half-planes whose slopes are given sorted, finding the kernel of a simple polygon, triangulating a set of points in the plane that are given sorted, triangulating monotone polygons and star-shaped polygons, and computing the all dominating neighbors of a sequence of values. PRAM algorithms for these problems were previously known to be optimal (i.e., in O(log n) time and using O(n/log n) processors) only on the CREW PRAM, which is a stronger model than the EREW PRAM     

光栅投影式3维照相系统中光栅投影仪的标定

提出了一种光栅投影式立体照相系统中光栅投影平面的标定方法。将光栅投影到已知目标平面,通过数字摄影得到光栅平面与目标平面相交的光栅图像。根据光栅图像记录的信息,在每条交线上提取两点,作为对应光栅平面拟合用的两点。按一定规律移动目标平面,即可得到每个光栅平面上若干对点。利用最小二乘法分别拟合出每个光栅平面的空间平面方程。     

Mapping Based Algorithm for Large-Scale Computation of Quasi-Polynomial Zeros

A method for computing all zeros of a retarded quasi-polynomial that are located in a large region of the complex plane is presented. The method is based on mapping the quasi-polynomial and on utilizing asymptotic properties of the chains of zeros. First, the asymptotic exponentials of the chains are determined based on the distribution diagram of the quasi-polynomial. Secondly, large regions free of zeros are defined. Finally, the zeros are located as the intersection points of the zero-level curves of the real and imaginary parts of the quasi-polynomial, which are evaluated over the areas of the region outside those free of zeros.     

六面体体元网格三维地质模型剖切算法

针对常用的六面体体元网格三维地质模型,提出了一种求剖切面的算法.首先,采用分层投影求交点的方式,将地质体模型与切割面投影到同一平面,三维空间下的地质体模型与切割面的剖切转化为二维平面上的四边形网格与切线段求交点的运算.为减少判交次数,先根据切线走势判断可能存在交点的区域,再对可能区域进行精确判交.其次,找到并求出不能通过投影方式得到的交点.然后,将得到的所有交点按规则组成四边形网格,对每个四边形三角化处理得到TIN形式的剖切面.最后,对该TIN面进行显示.实验证明了对六面体体元网格三维地质模型剖切的可行性.     

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

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

Computing medial axes of generic 3D regions bounded by B-spline surfaces

A new approach is presented for computing the interior medial axes of generic regions in R³ bounded by C⁽⁴⁾-smooth parametric B-spline surfaces. The generic structure of the 3D medial axis is a set of smooth surfaces along with a singular set consisting of edge curves, branch curves, fin points and six junction points. In this work, the medial axis singular set is first computed directly from the B-spline representation using a collection of robust higher order techniques. Medial axis surfaces are computed as a time trace of the evolving self-intersection set of the boundary under the the eikonal (grassfire) flow, where the bounding surfaces are dynamically offset along the inward normal direction. The eikonal flow results in special transition points that create, modify or annihilate evolving curve fronts of the (self-) intersection set. The transition points are explicitly identified using the B-spline representation. Evolution of the (self-) intersection set is computed by adapting a method for tracking intersection curves of two different surfaces deforming over generalized offset vector fields. The proposed algorithm accurately computes connected surfaces of the medial axis as well its singular set. This presents a complete solution along with accurate topological structure.     

基于单目视觉的空间目标位置测量

针对工业生产过程中工件等空间目标定位的问题,给出了一种采用直线与平面相交的定位方法。首先利用单目视觉获得目标的图像,然后利用成像的基本原理,以及直线与目标所在平面的交点来确定目标特征点的空间坐标,进而得到目标的位置信息。该方法原理简单,并通过实验表明:其定位精确性较高,还能很好地满足工业过程中的生产要求。     

Robust and Efficient Ray Intersection of Implicit Surfaces

The generation of ray traced images of a variety of surfaces plays a central role in computer graphics. One of the main operations in ray tracing is the calculation of intersections between rays and surfaces. In case of implicitly given surfaces the intersection problem can be formulated as that of finding the smallest non-negative root of an equation in one variable. If the root finding is carried out by means of conventional numerical methods based on point sampling (such as bisection, regula-falsi or Newton) the resulting image can be wrong, e.g. when the surface is thin the ray may "miss" the surface, which may result in an image with background color spots on the surface. To obtain robust intersection detection, methods based either on Lipschitz constants for the function and its derivative or an interval inclusions for the function and its derivative have been suggested. In this paper robust methods are obtained with interval inclusions in a variant of Alefeld-Hansens globally convergent method for computing and bounding all the roots of a single equation. Alefeld-Hansens method has been modified so instead of searching for all roots, a recursive depth-first search is carried out to obtain the smallest non-negative root. When compared to other methods suggested, it is found that this variant of Alefeld-Hansens method is not only robust but also an efficient method for finding the ray intersections.     

结构光视觉传感器现场标定几何法研究

与基于交比不变性求解特征点坐标来标定激光平面的方法不同,本文提出了一种可适用于未知环境的线结构光三维视觉传感器现场标定的新方法,该方法只需简单几何知识,就可直接利用几何方法实现快速标定。通过拍摄一个与线结构光相交并以不同姿态随机自由移动的平面靶标的图像(至少三幅),就可同时实现三维视觉传感器CCD和激光平面的快速标定。该方法方便,快捷,简单,可实现自动化,标定精度高。实验结果证明了该方法的方便和有效性。