关于任意凸多边形的CPU剪裁问题


综述

在图像渲染的时候,我们可以使用硬件剪裁(在OpenGL中也就是glScissor或者使用stencilbuffer)。但这样做的劣势是必须增加一个drawcall,于是就涉及到了比较大的切换开销问题(具体的可以参考这篇知乎帖子)。

要在程序中做任意多边形的剪裁,也就需要把多边形和剪裁框的交算出来,然后在分解成triangle fan给硬件进行渲染。这其中涉及到的计算量显然要比单纯的AABB求交来的“重“的多。主要涉及三个方面:

  • 线段求交点
  • 如何判断点在凸多边形内部
  • 如何求凸包(convex hull)

所有的计算都基于向量积,但具体的实现有一些坑需要填(详细的可以参考下面的代码)。

算法

  1. 求多边形P和剪裁框C的所有交点的集合S
  2. 把P的所有在C内部的顶点加到集合S中
  3. 把C的所有在P内部的定点加到集合S中
  4. 对S进行去重操作
  5. 选取S的一个顶点,将其余顶点按照逆时针/顺时针排序然后顺次构建TriangleFan

对于这个算法的简单证明,如果点p在交集的边界上,则显然p或者在P的边界上,或者在C的边界上,但不是both。那么这个边界的顶点只有两种可能,要不然是P和C的边界相交而成,或者是P和C自己的边相交而成。前者由算法第一步求出,后者由算法2,3步补充。

DEMO

按顺序点击canvas区域创建一个凸四边形,双击取消当前四边形

浏览器不支持html5 canvas!
上篇: 室内定位技术研究 下篇: ShaderToy系列之一: 炫酷的海洋渲染Seascape