不等式绘图的一般实现计算几何-regionfill.m

不等式绘图的一般实现计算几何-regionfill.m
在可视化上matlab已经很强大了（但是令人吐槽的是它的默认色彩方案以及不光滑的线条），但是有些功能还是没有现成的官方函数能够简单实现，比如经常会遇到的区域绘图/不等式绘图。这种功能在 Mathematica 里面有build-in函数可以实现（RegionPlot和RegionPlot3D）。

严格来说，不等式绘图其实是属于计算几何里面的东西。更加一般的情况是，在指定空间区域绘制一个函数的图像——而不是仅仅绘制这个不等式区域。这一点，Mathematcia里面的RegionFunction选项可以很方便做到。

1. MATLAB实现任意不等式区域（空间）可视化
那么MATLAB想要实现这些功能，就必须自己动手了。下面是我写的两个函数regionfill和regionsurf，分别实现的是平面和三维 任意不等式绘图。使用的算法各自是：步进矩形 二分搜索、步进四面体 逻辑比较。因此，任意实数域（以及部分复数域）内的解集都能可视化。具体详细功能请阅读里面的说明和例子。
regionfill.m 二维不等式绘图
regionsurf.m 三维不等式绘图

2. 指定不等式区域（空间）内绘制曲面
1) 平面不等式的情况
只需要使用regionfill返回不等式解集面片fv，就能用于单值函数曲面在指定区域内的绘图（相当于RegionFunction的一部分功能）。

2) 三维情况
这个功能暂时没加入，主要是由于平均交点个数是二维情况的三次方，直接用m函数实现就显得效率不够高了（除非加入八叉树算法来减少检索时间），使用MT算法 C-mex可能比较快，但是没精力去做这个了，如果谁有兴趣可以试一试。

3. 曲面布尔运算
平面布尔运算，MATLAB有polybool函数可以实现，但是对于三维情况，就没有函数提供了。这是因为，三维布尔运算的难度不是从二维到三维那么简单的提升，而是有着非常大的难度。因此，现在已经有些工具包能实现这个功能（比如iso2mesh工具箱，以及最新的GBT工具箱），大多数都是采用通过m调用exe程序来计算，或者使用c-mex/dll。

要解决曲面布尔运算这个问题，关键在于三个地方：
a. 碰撞检测；
b. 曲面求交线；
c. 相交部分的拓扑重构。

要知道，上述每一点都是计算几何领域的热点问题，如今也没有很高效且简单的算法。目前已有的算法分为两种：牺牲准确度以提高速度，牺牲效率以提高准确度。作为非专业建模用途，仅仅是可视化的matlab，我们只需要选择前一种算法即可。

目前我只是用c-mex写了曲面求交线的一个函数surfs，由于使用的算法只是简单的相交测试 三角面片求交，并未用到比较高效的链表查询机制，因此很多相邻边的交点其实是重复计算了的，因而对于大量的三角面（比如5000以上的三角面片的两个复杂曲面）求交线，时间效率就会急剧上升（大概会在6s以上），对于三角面片不多1000左右，0-2s内可以给出结果。
surfs.rar 曲面求交线

上面给出的东西也算是抛砖引玉吧，希望有高手能将这些问题完美解决。




补充内容 : 更新：11楼发布了regionsurf的更新版，修正了一些bug，并改进了一些细节。