首先吐槽一下：今天考IT项目管理，100道选择题。前几天考配置管理，10道大题。如今的老师都喜欢走极端……
这个方法是在考完试回宿舍的路上想到的，适用于2D与3D。主要想法是这样的。给定两个几何图形A、B，把A和B都分成『内『、『外』两部分。A的『内』就是处于B内部的部分。于是A和B就变成了A内、A外、B内、B外。然后就有如下公式：
·A and B=A外+B外
·A sub B=A外+B内
·A or B=A内+B内
·A xor B=A外+B外+A内+B内
这种数据结构是为了满足如下算法：一个A点在图形内<==>过这个点的直线交图形与点集P，其中|{Pi|Pi<=A}|和|{Pi|Pi>=A}|都是奇数。注意我们使用的是<=和>=，这样的话两个集合的数量的奇偶性都是一致的。这个算法无论2D、3D多边形还是3D多面体都能适用，就算是这个图形有孔（镶嵌）也可以，而且跟凹凸体无关。这个算法只有一种情况是不能用的：就是自己跟自己有交叉，譬如我们习惯的5条直线构成五角星的画法。这样的话首先要对这个图形进行处理，成为镶嵌的图形。
让我们来图示一下。现在我们给出两个回形的红色和蓝色向前多边形：
然后我们把两个图形分为内外一共四部分，其中内使用粗线：
我们把这个图形转换成拓扑结构，得到了下面的连线图。现在让我们来求蓝 sub 红，也就是蓝外+红内：
我们可以很容易地看到现在图形分成了4各部分，因为下面的拓扑结构构成的图一共有4个连同体。
后来我自己做过实验，求蓝 And 红的时候图形会被分成6个连同体，其中有5个是镶嵌的孔。但是哪个是孔在整个过程中并没有关系。因为我们只需要把所有的Component求出来，内Component就是Component内的一点在另一个图里，而且判断是不是内部点的算法已经给出了。整个流程跟哪一个连同体是孔并没有关系。而且在实际情况下，2D多边形和3D多面体的渲染并不在乎哪个是孔，可以正确渲染出来。唯独3D多边形在乎。这种情况下再慢慢处理吧。而且判断的算法也是差不多的。不过我似乎没有见到3D多边形的布尔运算有什么常见的应用。
期末考过后就可以开始写布尔运算的代码了。
posted on 2008-06-16 19:20
陈梓瀚(vczh) 阅读(4490)
评论(7) 编辑 收藏 引用 所属分类:
2D