【作者】 朱振华；

【导师】 何援军；

【作者基本信息】 上海交通大学 ， 计算机应用技术， 2008， 硕士

【摘要】 在图形系统中,二维布尔运算是最为基础的运算之一,在CAD和几何实体造型中有着广泛的应用。现有的布尔运算在一般的情况下可以快速地得出正确结果,但如遇到奇异情况,则会产生错误。现有的算法对奇异情况的探讨较少,因此,本文对高效的、鲁棒性高的二维布尔运算算法进行了探讨和研究。本文首先阐述了二维布尔运算的研究意义、相关概念、数据结构和已有算法,并着重叙述了与本文密切相关的交点遍历算法。然后对二维布尔运算中的奇异情况进行了分析,采用了一种用重叠和相交等概念分析奇异的思路,并在原有的交点遍历算法框架基础上给出一种全局化的奇异处理算法框架。这个算法框架包括三个部分:交点求取、交点遍历和结果正则化,论文对其中的交点求取和结果正则化分别提出了新的算法,使整个框架可以解决各种奇异现象。本文同时处理了圆弧段和无交点环。接着提出了一种局部化的奇异解决算法,该算法使用重交点的概念,对奇异的分析更为简洁,从另一个角度解决了奇异问题,并讨论了算法实现中需要进行的初始化步骤,同全局化算法进行了性能上的比较。最后,对全文进行总结,并对今后的研究方向作了一些展望。更多还原

【Abstract】 Two dimensional Boolean operation is the most basic operations in graphics system. It is universally used in CAD system and geometric modeling system. Nowadays’algorithms can give results rapidly enough in general cases. But when it comes to queer conditions, there will be errors. These algorithms have little to do about queer conditions. So this thesis endeavors to come up with an algorithm that can handle queer conditions.Firstly, we expound the main content of 2D Boolean operation, and its importance, summarize some relevant technology and explained intersection-traversal algorithm. Secondly, we do some research on queer conditions, and propose a method to analyze queer conditions using concept of collapse and intersect. We enhance the original intersection-traversal algorithm and give new algorithms on intersection calculation and intersection traversal. We call this algorithm framework global queer handling algorithm, and it can handle queer conditions correctly. In this part, we also discuss curve edges and non-intersect loops. We continue to propose a localized algorithm which can also handle queer condition, but using concept of multi-intersection point instead. We hold a discussion about initialization of the Boolean operation regarding queer conditions, and also hold a comparison of the two new algorithms.Finally, we conclude this dissertation and discus some directions for future work.更多还原