12.图形裁剪——二维裁剪+三维裁剪+Sutherland-Cohen裁剪算法+中点分割算法
♥,.*,.♥,.*,.♥,.*,.♥,.*♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥♥,.*,.♥,.*,.♥,.*,.♥,.*♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥
目录
1.二维裁剪
2.二维线裁剪
（1）Sutherland-Cohen裁剪
（2）中点分割裁剪
（3）梁友栋-Barsky裁剪
3.二维多边形裁剪
4.文本裁剪
5.三维裁剪
6.三维裁剪算法
♥,.*,.♥,.*,.♥,.*,.♥,.*♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥♥,.*,.♥,.*,.♥,.*,.♥,.*♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥
1.二维裁剪
裁剪：确定场景或者画面中位于给定区域之内的部分。
————————————————————
回忆一下三维变换流程：
局部坐标系->模型变换->
世界坐标系->取景变换->
视点坐标系->投影变换->
图像坐标系->设备变换->
规则化设备坐标系->视窗变换->屏幕坐标系
————————————————————
在投影变换的时候，将视点坐标系转换为了图像坐标系，从三维转换为了二维。
因此，二维裁剪主要在投影变换之后。
2.二维线裁剪
对于线的裁剪，就是确定哪些线段位于裁剪窗口之内，哪些线段位于裁剪窗口之外。
二维裁剪的主要方法有：Sutherland-Cohen裁剪、中点分割裁剪、梁友栋-Barsky裁剪等。
（1）Sutherland-Cohen裁剪
对于每条待裁剪的线段P1P2，算法的基本思想为：
- 若P1P2完全在窗口内，则显示这条线段
- 若P1P2完全在窗口外，则丢弃这条线段
- 如果P1P2部分在窗口内（外），则求交点。将完全在窗口外的线段舍弃。
Sutherland-Cohen裁剪对9个区域进行了四位编码（），然后按位进行运算：
则：
对于（）：
第一位为1：端点处于上边界的上方
第二位为1：端点处于下边界的下方
第三位为1：端点处于右边界的右方
第四位为1：端点处于左边界的左方
否则，相应位为0
算法步骤：
a.判断线段的两个端点的四位二进制编码是否都为0000。
如果是，则线段位于窗口内，则对其进行显示。如果不是，转b。
b.将线段的两个端点的四位二进制编码进行逻辑与运算。
如果不是全为0，则表示线段位于窗口外，则将其直接舍弃。
如果为0，则表示线段有部分位于窗口内，部分位于窗口外，转c。
c.线段有窗口有相交。则求交点。
算法优点：
- 简单、易实现
- 通过编码的方式，可以快速判断线段完全可见和完全不可见
（2）中点分割裁剪
中点分割算法与Sutherland-Cohen算法类似，
首先将线段的两端点P1，P2编码为C1，C2
根据C1和C2的值，可以分为三种情况：
a. C1=C2=0,则两端点都在窗口内，保留该线段
b. C1&C2≠0,则两个端点都在窗口外，舍弃该线段
c. 上面两种情况都不符合，则求交点。
求交点的方法用的是中点分割算法。
中点分割算法的思想是：中点将线段分为两部分，必有一部分存在交点。
当线段求出中点P后，如上图，则由于两种情况：
P与P1同侧，则交点在P和P2之间，则将P点的坐标赋值给P1；
P与P2同侧，则交点在P和P1之间，则将P点的坐标赋值给P2。
之后递归对中点进行分割，则可以收敛到交点。
（3）梁友栋-Barsky裁剪参考论文：Liang, Y.D., and Barsky, B., "A New Concept and Method for Line Clipping", ACM Transactions on Graphics, 3(1):1-22, January 1984.
算法的基本思想：当要裁剪的线段是P0P1， P0P1和窗口边界交于A,B,C,D四点。从A,B和P0三点中找出最靠近的P1的点，从C,D和P1中找出最靠近P0的点。
在计算的时候，首先将P0和P1点写成其参数方程：
如果线段在窗口内，则应该满足条件：
当有交点的时候，上式将存在等号，例如，
在该算法中，窗口边界的四条边将被分为两类，一类称为始边，一类称为终边。
当Δx≥0时，称x=xL为始边， x=xR为终边
当Δx<0时，称x=xL为终边， x=xR为始边
当Δy≥0时，称y=yB为始边， y=yT为终边
当Δy<0时，称y=yB为终边， y=yT为始边
3.二维多边形裁剪
对于二维多边形的裁剪，可以对多边形的每条线段采用线裁剪算法。
但是，需要注意的是，裁剪后的图形仍旧是封闭的图形。因此需要保证裁剪后的区域的封闭性。
所以，关键是要确定裁剪后区域的边界。
多边形裁剪的算法有：Sutherland-Hodgman
其思想是每次用窗口的边界对多边形进行裁剪。将落在窗口外部的图形去掉，落在窗口内部的图形保留，并将保留的图形作为下一次需要裁剪的多边形。以此对四个边界进行上述操作，最后得到的就是裁剪后的结果多边形。
示意图：
4.文本裁剪
对于矢量的文本，可以采用多边形裁剪算法进行裁剪；
对于点阵文本，则字符完全位于裁剪窗口内才会显示。
5.三维裁剪
————————————————————
回忆一下三维变换流程：
局部坐标系->模型变换->
世界坐标系->取景变换->
视点坐标系->投影变换->
图像坐标系->设备变换->
规则化设备坐标系->视窗变换->屏幕坐标系
————————————————————
在投影变换的时候，将视点坐标系转换为了图像坐标系，从三维转换为了二维。
因此，三维裁剪是在投影变换之前。
三维裁剪有线裁剪、面裁剪、立方体裁剪、四棱锥裁剪。
6.三维裁剪算法
二维裁剪算法Sutherland-Cohen、梁友栋-Basky可以推广到三维场景。
Click 下一篇文章：13图形光栅化——区域填充（种子填充）+多边形扫描转换（扫描线算法）
♥,.*,.♥,.*,.♥,.*,.♥,.*♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥♥,.*,.♥,.*,.♥,.*,.♥,.*♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥,.*,.♥
广告时间：
本宝宝开通了一个公众号，记录日常的深度学习和强化学习笔记。
希望大家可以共同进步，嘻嘻嘻！
求关注，爱你呦！