格网划分的双策略跟踪多边形裁剪算法

论文提出了一种高效稳定的多边形裁剪算法,算法支持带内环的平面简单 多边形,同时也支持多边形的“并”和“差”等布尔运算。首先,设计了算法所需的数据结构; 其次,基于直线扫描转换Bresenham 算法原理提出了边网格划分的有效算法,并应用一个简 单的方法避免不同网格内边的重复求交;最后,将交点分类为普通交点和顶交点,并针对这 两类交点构造了不同的跟踪策略,在跟踪过程中交替、递归地应用这两个策略来确保算法处 理特殊情况时的稳定性。与其它同类算法的比较表明,新算法具有更高的效率。     

多边形组的布尔运算

本文讨论了二组多边形的布尔运算.多边形定义为全部内点的开集,对多连形边界的交点也作了相应的定义.在这种定义下作多边形的布尔运算比较简单,从理论和实践均证明运算结果的多边形不会出现不希望有的线段,而且在这种多边形定义下,多边形集对布尔运算也是封闭的.     

一种利用图形内角的多边形布尔运算新算法

现有的平面多边形布尔运算在一般情况下可以快速地获得正确结果,但如遇到奇异情况,则会产生错误.因此,采用图形内角概念分析奇异情况,并在原有交点遍历算法框架基础上给出一种全局化的奇异处理算法.与其他的多边形布尔运算算法相比,该算法对奇异的分析更为简洁有效,且具有高效性和鲁棒性.     

基于“内点”识别的多边形布尔运算

在多边形内、外侧边界识别的基础上，充分利用多边形本身是一个整体的事实，我们提出了一种基于“内点”(多边形内的点)识别的布尔运算算法，简化了布尔运算的复杂性，从根本上解决了由于多边形问可能存在重合点、重合线而造成的布尔运算不稳定问题。     

计算多边形交集、并集面积的算法

平面多边形交集与并集面积的计算机算法可以利用多边形裁剪算法来实现。本文提出的算法思想是利用Weiler-Atherton多边形裁剪算法中的多边形链表,在遍历链表时遇到交点就改变跟踪方向,这样可以求出并集顶点表,求交集时只要从入点开始跟踪遇到交点再改变跟踪方向;最后,通过交集和并集表求出它们的面积。多边形可以是凸的或凹的、甚至是带孔的。     

硬件加速的渐进式多边形模型布尔运算

多边形模型的布尔运算中包含复杂的求交计算以及多边形重建过程,精度控制和处理效率是其中的关键.为了降低布尔运算复杂度,提出一种适合硬件加速的基于渐进式布尔运算的多层次细节网格模型生成方法.该方法采用分层深度图像来近似表示多边形实体的封闭边界,将多边形的求交计算简化为坐标轴平行的采样点的实体内外部判断;为了免去各层次细节模型的重复采样过程,渐进式地将边界采样点归并到低分辨率下的立方体中;运用特征保持的多边形重建算法将相同立方体内的边界采样点转换成多边形顶点,根据邻接关系生成网格模型.上述算法使用支持图形硬件加速的CUDA编程并行实现.实验结果表明了算法的可行性.     

基于GPU栅格化的任意多边形布尔运算

任意多边形布尔运算大多基于CPU栅格化方法,而CPU的串行性会增加栅格化过程的耗时。为此,提出一种基于图形处理器(GPU)栅格化思想的多边形布尔运算算法。用GPU实现CPU中较耗时的二维图形栅格化过程并提取内外轮廓片元,构造GPU环境下的栅格数据结构及与之空间映射相对应的CPU环境下的顶点数据结构,采用CPU与GPU相协调的方式交替访问内外轮廓进行顶点跟踪及轮廓片元压缩,最终得到正确的布尔运算结果多边形。实验结果表明,与现有多边形布尔运算算法相比,该算法能有效控制精度,且具有更高的执行效率。     

雕塑物体的布尔运算

本文提出了一种带有trimmed曲面物体的快速布尔运算算法。算法首先对trimmed曲面在其trimmed区域内离散,并进行离散求交,在离散求交时保证三角形边面仅求交一次;算法采用交点表与连续跟踪相结的方法跟踪交线,并在跟踪交线的同时用Euler算子建立起交线的数据结构且对特殊交点进行特球处理;算法最后用一种新的交点修正法对离散交线进行求精。     

一种基于加减法求交和顶点类型的凹多边形水平扫描填色算法

本文给出了一种只有加减运算就能求大平线线与凹多边形边界交点的方法,并根据顶点类型定义,将凹多边形顶点分成“水平顶点”、“极占”、“拐点”三类。设计了基于三类顶点的边界存储结构;建立了凹多边形水平扫描填色算法,解决了当交为顶点时可能产生的“交点对”不配对的问题。     

用最小回路求两个简单多边形的交、并、差集

针对求两个简单多边形交、并、差集问题,提出一种基于最小回路的新算法。首先,将初始多边形P和Q初始化为逆时针方向,并将两个多边形交点处的关联边排序。然后,从各个交点出发利用最小转角法搜索最小回路,并根据这些最小回路中包含P和Q边的方向性对它们进行分类。最终,不同类别的最小回路将对应P和Q的交、并、差集。算法的时间复杂度为O((n+m+k)logd),其中n、m 分别是P和Q的顶点数,k是两多边形的交点数,d为将多边形分割的单调链数。算法几何意义明显,对于多边形布尔运算中的重合顶点、重合边等奇异情形,具有较好的适应性。     

Boolean Operations on Conic Polygons

An algorithm for Boolean operations on conic polygons is proposed.Conic polygons are polygons consisting of conic segments or bounded conics with directions.Preliminaries of Boolean operations on general polygons are presented.In our algorithm,the intersection points and the topological relationships between two conic polygons are computed.Boundaries are obtained by tracking path and selecting uncrossed boundaries following rule tables to build resulting conic polygons. We define a set of rules for the i...     

Boolean operations on general planar polygons

Computing boolean operations between general planar polygons is one of the fundamental problems in geometric and solid modeling. In this work we present a new algorithm to calculate intersection, union and difference, valid for general planar polygons (manifold and non-manifold, with and without holes), based on a formal representation system. This formal model is based on the concept of simplicial chain, developed by Feito and Rivero (Computers & Graphics 22(5) (1998)). Using algebraic operations between simplicial chains we can obtain any general polygon and the Boolean operations between them. The fact of that our algorithm is based on simplicial chains and their operations, reduces the study of special cases, and allows us to develop a robust and efficient algorithm to calculate the intersection between general polygons.     

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.     

一般点模型的交互式布尔运算

提出了一个适用于一般点模型的交互式布尔运算算法,此算法由4个步骤组成．首先将点模型表示为自适应的三色八叉树,然后利用自适应八叉树结构加速内外测试．对于局部采样密度不一致的相交区域或曲率太大容易导致较大求交误差的地方,实行了自适应细分加密采样;重采样相交的部分以获得更精确的求交结果．与已有的点模型布尔运算方法相比,该算法适用于一般的实测点云数据,包括少量噪声的点模型、非均匀采样以及不同分辨率点模型之间的交互式布尔运算。     

三维网格模型的稳定布尔运算算法

给出一种稳定、高效的三维网格模型的布尔运算算法。该算法首先,基于网格模型原始的拓扑关系,结合层次包围盒相交检测实现网格模型相交区域快速定位;然后,采用改进的空间三角形求交算法求解离散交线段数据,并对单个三角形重新进行Delaunay三角剖分;最后,通过建立交线段与相交三角形间的拓扑关系对交线快速跟踪提取,通过局部区域快速分类组合,实现三角网格模型的精确布尔运算。该算法能有效地处理各种特殊情况且运行稳定;程序实现简单,实例证明符合工程需求。     

三维网格模型的布尔运算方法

提出了一种基于三维网格模型的布尔运算方法。首先通过基于方向包围盒（OBB）层次包围盒树的碰撞检测算法,得到实体的相交三角形对;接下来求出两相交三角形之间的交线,建立与三角形的交线拓扑关系;通过分类处理三种交线类型来对相交三角形进行区域划分,得到一系列多边形,并对多边形进行三角剖分形成结果区域;最后根据体的包含关系构建关系邻接表,判断多边形区域的相对于其他实体的内外关系并通过网格模型的拓扑关系,定位表面三角网格区域;同时根据交、并、差等布尔操作,对结果区域进行取舍,得到最终结果。实验结果表明相交部分的岩性与实体的岩性相吻合,验证了该算法的正确性以及可行性。     

NURBS体的DEXEL化与布尔运算

NURBS曲面与NURBS体造型技术是目前复杂体造型的重要工具,但复杂体之间的布尔运算求交困难。将NURBS曲面围成的体与NURBS体体素化(VOXEL化)为由一系列平面凸四边形或三角形表示的体,通过DEXEL射线组群与四边形或三角形求交,实现NURBS体的DEXEL化。在同一DEXEL模型空间实现复杂NURBS体之间的布尔运算,所有运算是线性的。该方法可推广到在逆向工程中生成的由三角面表示的体。在Java2.0与Java3D环境下编程实现并验证了该算法,给出了一个机械零件设计实例。     

连接不相交线段成简单多边形(链)的算法及其实现

提出一个如何连接平面上n条线段与一个简单多边形或者简单多边形链的实际问题，并证明了连接平面上线段集S成一简单多边形链的一个充分条件——S中有一条线段连接凸壳CH（S）中不相领顶点。提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法，其基本思想是首先农层计算线段集S的凸壳，并将这些凸壳改变为简单多边形；然后计算各多边形之间的交点，进而删去这些交点；最后俣并若干个简单多边形为一个简单多边形。当S中线段数目n较大时，用分治思想设计分治算法，较好地求解了这个问题。利用计算机求解这个问题具有实际应用价值。