精确实数计算在求两条直线段交点问题中的应用

求两条直线段的交点问题是计算机图形学、计算几何、几何造型等领域的最基本问题之一。精确实数计算是指以任意精度表示实数,并能进行计算,以任意精度得到结果。给出了一种把基于LFT方法的精确实数的表示与计算应用在求两条直线段的交点问题中的算法,该算法能够以任意的精度得到两条直线段的交点。     

曲面实体造型中曲线和曲面交点的求解

求交是曲面实体造型系统中影响拼合算法效率和稳定性的重要因素，而求交算法又是和曲面的几何表示密切相关的。ＮＵＲＢＳ虽然能统一表示所有曲面，但却给二次曲面的求交带来了不必要的复杂性。二次曲面经常在机械零件的设计中被用来描述轴、孔、槽等几何特征，因此它们的求交算法应具有高精度、高效率和高稳定性。为此，对一种实用的二次曲面表示方法——几何法进行了深入研究后，给出了构成二次曲面轮廓的几种二次曲线和空间四次曲线与二次曲面交点的求法。     

奇异情况下两个二次曲面间的求交

曲面求交是几何造型系统的核心之一,奇异情况下求交算法的稳定性直接关系到后续的布尔运算乃至整个系统的稳定性.提出2种二次曲面间对应特征多项式有重根情形下鲁棒的求交算法.首先给出精确求解特征多项式重根的方法,若交线中存在奇异交点,则给出奇异交点关于特征多项式重根的显式表达式,从而稳定地求解出对应的奇异交点;同时给出一种交曲线有理参数化的构造性方法,可以弥补Farouki相应有理参数化方法中的缺陷.最后通过实例进一步说明了文中算法的求解稳定性及有理参数化的构造性方法的实用性.     

几何区间裁剪算法收敛性分析和比较

为了寻求简单、快速、稳定的求交算法来加速光线跟踪渲染三维场景,对一种快速计算2条平面曲线交点的方法--几何区间裁剪(GeoClip)算法进行了深入研究.严格证明了GeoClip算法在计算多项式的根以及计算2条平面曲线的交点中都具有三阶收敛性,该结果从理论上保证了GeoClip算法优于经典的曲线求交算法--Bézier Clipping算法;最后对GeoClip与二次裁剪(QuadClip)算法进行了比较,结果表明,虽然都是三阶收敛,但是GeoClip算法比QuadClip算法快30%左右.     

一种改进的基于微分方程的曲面求交跟踪算法

参数曲面求交是计算机辅助几何设计领域中的关键技术之一。针对传统跟踪算法 中曲面求交的漏交和法向共线点处难于处理的问题,提出一种改进的基于微分方程的跟踪算法。 首先选择边界点和拐点作为跟踪的起点,解决了漏交问题。并采用基于交线微分形式的跟踪公 式计算后继交点,解决了法向共线点处难于处理的问题。最后利用牛顿迭代得到精确交点。该 算法不仅正确地跟踪到交线的每个分支,而且易于处理法向共线点处的跟踪,不遗漏关键点, 解决了传统跟踪法在法向共线点处交线不连续的问题。与传统跟踪法对比,其鲁棒性和稳定性 更强,精度更高且收敛略快,适用于求解任意参数曲面求交问题。     

基于Bernstein基函数的曲线上点的几何迭代算法

文章针对传统的求曲线上点的插值法和幂基法的不足之处,提出了借鉴Berstein基函数求曲线上点的几何算法,并研究了如何将该方法用迭代算法来书写。采用了matlab编程的方法求解了一条平面曲线上指定的点,结果发现该算法能够比较精确地求出曲线上的点,比用通常的幂基函数的方法更简单,且对舍入误差不敏感;更重要的是易在计算机上用matlab编程实现,且具有较强的几何风格;但是该算法的计算效率稍差。因此在对计算效率要求不是很高的情况下,可以考虑用该几何迭代算法来弥补传统的求曲线上点的方法的不足之处。     

基于段码的离散直线求交

求交是计算机图形学的重要问题，而直线求交又是复杂曲线求交的基础。传统的求交算法多是基于欧氏几何的模型进行的，本文从泛欧几何的模型出发，论述了传统模型的不准确性，提出了基于段码的准确求交方法，该方法也是泛欧几何处理离散问题的基本原则，可以推广到曲线等复杂求交中。     

相交多边形轮廓线的获取

提出获取相关多边形轮廓线的一种算法，利用线段求交法求取相交多边形交点，利用 对位置判断交点处轮廓走向。该算法适用于任意多边形。     

裁剪后二次曲面的光线跟踪

提出了一个对裁剪后二次曲面进行光线跟踪的新方法。在该方法中引进了一个易于由世界坐标求参数的辅助参数空间，通过预处理，事先将原参数域下的边界变换到新的参数空间。这样，光线与曲面的求交仍可按二次曲面的几何参数进行，求出交点后，再将交点变换到辅助参数空间，在新的参数域中判断交点是否在裁剪过的曲面上。     

快速求取自由曲面上两点间的最短路径算法

利用求无向图中一定点到各项点间的最短通路算法──Ｄｉｊｋｓｔｒａ算法，并应用曲面片细分原理，提出了一种快速求取自由曲面上两定点间的最短路径值和路线的算法──快速ＦＳＰＦＦＳ算法。该算法广泛适用于凸凹自由曲面，具有广泛的实用价值，对计算机辅助几何设计的发展应用具有较重要的意义。     

Robust Computation of Intersection Graph between Two Solids

We propose a new robust algorithm for Boolean operations on solid models. The algorithm produces a consistent intersection graph between two input solids whose geometrical data are represented in floating point numbers. In order to prevent numerical calculation errors and inaccuracy of input data from causing inconsistency of the output, we put higher priority on symbolical connectivity of the edge-face intersection points than their numerical nearness. Each edge-face intersection point is symbolically represented using face names, which generate connectivity relations between the intersection points and the intersection line segments. The symbols with the same connectivity are made into clusters. The intersection line segments connected together at their end clusters form the intersection graph of two solids. Inconsistency of the connectivity of the clusters is detected and the intersection graph is corrected automatically. We describe the algorithm in detail for polyhedral solids, discuss extension to curves solids, and show its effectiveness by some examples of Boolean operations for two solids whose faces intersect at a very small angle.     

采用区域编码的椭圆对直线裁剪算法

裁剪算法的核心问题是速度问题,而求裁剪窗口和裁剪对象的交点是影响裁剪速度的主要因素。特别是椭圆对线段的裁剪,由于椭圆的方程是二次的,求椭圆与线段的交点 需要求解一元二次方程,涉及开方运算,非常浪费机器时间。为提高裁剪速度,设计出5位的区域编码,利用此技术能够迅速而准确地判断出椭圆和线段的位置关系。对于完全可见 或显然完全不可见的线段立即做出保留或弃掉的决定,避免求交运算;对于能够明确断定与椭圆相交的线段,采用中点分割算法求椭圆和线段的近似交点,避免求解一元二次方程 和开方运算;对于其他情形的线段通过求解一元二次方程来完成裁剪。基于前述思想设计出的椭圆对线段裁剪算法与现有的同类算法相比,算法实现简单,裁剪速度具有较大提高 。     

An intersection algorithm based on Delaunay triangulation

A robust method for finding points of intersection of line segments in a 2-D plane is presented. The plane is subdivided by Delaunay triangulation to localize areas where points of intersection exist and to guarantee the topological consistency of the resulting arrangement. The subdivision is refined by inserting midpoints recursively until the areas containing points of intersection are sufficiently localized. The method is robust in the sense that it does not miss points of intersection that are easily detectable when costly line-pair checking is performed. The algorithm is adaptive in the sense that most of the computational cost is incurred for the areas where finding points of intersection is difficult     

计算线段集合的相交直线及其最大存在范围

对给定的一个直线段集合S研究求与S中所有直线段都相交的直线的问题.设S中的线段满足一定的不交性假设,算法可回答是否存在与S中所有线段均相交的直线的问题.如果该直线存在,则求出这样的直线的最大存在范围——位于该范围内的每条直线都与S中的所有直线段相交.该算法的时间复杂性为O(n~*log,n),应用背景是模式匹配等领域.     

基于轨迹计算的临界多边形求解算法

将多边形滑动碰撞问题转化为顶点和边之间的轨迹线提取问题,从而降低了时间复杂度,并可统一处理边界空腔和内部靠接临界多边形问题．该算法的基本原理是：1）求解多边形顶点相对于另一多边形的轨迹线;2）求解轨迹线集合所形成的外包多边形和内部顺时针环,得到的多边形即为临界多边形．该算法采用基于网格的线段索引方法来加快线段之间的求交计算,进一步提高了临界多边形求解的计算速度．     

一个有效的多边形裁剪算法

通过对相交多边形交点的完备分类,给出了一个可靠的任意多边形裁剪算法.结果表 明,该算法非常稳定可靠,且能处理各种奇异情况.     

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.     

基于有界有向图形元素的投影分解法消隐算法的研究

论文利用有界有向图形的基本原理和简化了的相交性判别算法,提出了一种新的消隐算法;该算法大大简化了一般算法中求解联立方程组的算法要求,利用直线或平面的方程值进行比较,降低了算法的复杂度和外部要求;同时,对相关线段进行投影分解,解决了空间直线段与空间有界平面的相交性判别的复杂算法,较好地实现了将三维空间问题转变为二维空间问题的简化处理。实际应用表明,根据该文设计进行的系统实现完全达到了原定的系统设计目标。     

基于凸片段分解的多边形窗口线裁剪算法

将多边形窗口的边顺序地分割成一些片段,使得每个片段都能局部地形成一个凸多边形,称为凸片段,并建立一个二叉树来管理这些凸片段．在裁剪计算时,先根据二叉树快速地找到与被裁剪线段相交的凸片段,再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作．文中算法能有效地降低裁剪计算的时间复杂度,使其在O（logN）～O（N）之间自适应地变化,且大部分情况下时间复杂度小于O（N）．