算法描述

1.基本变换矩阵

1. 缩放矩阵

  1. void ScaleMatrix(float Sx, float Sy, float m[3][2])
  2. {
  3.     for (int i = 0; i < 3; i++) {
  4.         m[i][0] *= Sx;
  5.         m[i][1] *= Sy;
  6.     }
  7. }

2. 旋转矩阵

  1. void RotateMatrix(float S, float C, float m[3][2])
  2. {
  3.     float temp;
  4.     for (int i = 0; i < 3; i++) {
  5.         temp = m[i][0];
  6.         m[i][0] = temp * C - m[i][1] * S;
  7.         m[i][1] = temp * S + m[i][1] * C;
  8.     }
  9. }

3. 平移矩阵

  1. void TranslateMatrix(float Tx, float Ty, float m[3][2])
  2. {
  3.     // 矩阵平移变换的位移量
  4.     m[2][0] += Tx;
  5.     m[2][1] += Ty;
  6. }

2.Cohn-Sutherland直线裁剪算法

Cohn-Sutherland直线裁剪算法即对直线段p1(x1 ,y1)、p2(x2 ,y2)进行裁剪

1.基本思想：对每条直线段p1(x1,y1)p2(x2,y2)分三种情况处理

  • 直线段完全可见，“简取”之。

  • 直线段完全不可见，“简弃”之。

  • 直线段既不满足“简取”的条件，也不满足“简弃”的条件，需要对直线段按交点进行分段，分段后重复上述处理。

2 编码方法

编码： 对于任一端点(x,y)，根据其坐标所在的区域，赋予一个4位的二进制码D3D2D1D0。

编码规则如下：

  1. 若x<wxl，则D0=1，否则D0=0；
  2. 若x>wxr，则D1=1，否则D1=0；
  3. 若y<wyb，则D2=1，否则D2=0；
  4. 若y>wyt，则D3=1，否则D3=0。

裁剪一条线段时，先求出端点p1和p2的编码 code1和code2，然后：

  • 若code1|code2=0，对直线段应简取之。
  • 若code1&code2≠0，对直线段可简弃之。
  • 若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二， 其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。

3.具体做法：

按左、下、右、上的顺序求出直线段与窗口边界的交点，分段处理

例：对于直线段P1P2

  • 求出P1P2与左边界有实交点P3，一分为二，简弃直线段P1P3，处理P2P3
  • 求出P2P3与下边界的实交点P4，一分为二，简弃P2P4，剩下的P3P4可以简取。

3. Liang-Barsky直线裁剪算法：

任意直线段I（X1 ,Y1）J(X2 ,Y2 )的参数方程：
x=x1+u•(x2 -x1)
y=y1+u•(y2 -y1)
（0 ≤ u ≤ 1）

给定裁剪窗口，如果任一点在窗口内则：
wxl≤ x1+u•(x2 -x1 )≤ wxr
wyb≤y1+u•(y2 -y1 ) ≤ wyt
u•(x1 -x2 )≤ x1 – wxl 左边界
u•(x2 -x1 )≤ wxr – x1 右边界
u•(y1 -y2 )≤ y1 – wyb 下边界
u•(y2 -y1 ) ≤ wyt – y1 上边界
（u•pk≤qk ，k=1,2,3,4）

令：
p1 = x1 -x2
p2 = x2 -x1
p3 = y1 -y2
p4 = y2 -y1
q1 = x1 – wxl
q2 = wxr – x1
q3 = y1 – wyb
q4 = wyt – y1
（u•pk≤qk，其中：k=1,2,3,4）

  • 取“=”时求得的u对应的是直线不窗口边界的交点
  • 1、2、3、4分别对应左、右、下、上边界
  • u=0和1时分别对应直线的起点和终点

Uone=max(0,uk|pk<0,uk|pk<0)
Utwo=min(1,uk|pk>0,uk|pk>0)

例如： 对于IJ P1、P4小于0 Uone在0、u1、u4取大者 P2、P3大于0 Utwo在1、u2、u3取小者

限制条件： 如果Uone≤ Utwo取可求得两端点

4. Sutherland-Hodgman多边形裁剪算法

1. 基本思想：一次用窗口的一条边来裁剪多边形。

算法的输入是以顶点序列表示的多边形，输出也是一个顶点序列，这些顶点能够构成一个或多个多边形。

处理对象： 任意凸多边形。

窗口的任意一条边的所在直线（裁剪线）把窗口所在平面分成两部分：

  • 可见一侧：包含窗口那部分
  • 不可见一侧：不包含窗口那部分

2. 算法说明：

1、已知：多边形顶点数组src，顶点个数n，定义新多边形顶点数组dest。

2、赋初值：用变量flag来标识：0表示在内侧，1表示在外侧。

3、对多边形的n条边进行处理，对当前点号的考虑为：0～n-1。

  1. for(i=0；i<n；i++)
  2. {
  3. 　　if(当前第i个顶点是否在边界内侧？)
  4. 　　{
  5. 　　　　if(flag!=0) /*前一个点在外侧吗？*/
  6. 　　　　{
  7. 　　　　　　flag=0；/*从外到内的情况，将标志置0,作为下一次循环的前一点标志*/
  8. 　　　　　　(dest + j) =求出交点；　/*将交点dest放入新多边形*/
  9.            j++；
  10.        }
  11.      　(dest + j)= (src + i)； /*将当前点srci放入新多边形*/
  12.        j++；
  13.     }
  14.     else 
  15.     {
  16.         if(flag==0) /*前一个点在内侧吗？*/
  17. 　　　　    {
  18. 　　　　　　flag=1；/*从内到外的情况，将标志置1,作为下一次循环的前一点标志*/
  19. 　　　　　　(dest + j) =求出交点；　/*将交点dest放入新多边形*/
  20.            j++；
  21.         }
  22.     }
  23.     s= (src + i)； /*将当前点作为下次循环的前一点*/
  24. }

3.算法特点：

Sutherland－Hodgeman多边形裁剪算法具有一般性，被裁剪多边形可以是任意凸多边形，裁剪窗口不局限于矩形。

上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的每一条边界依次调用该算法程序，并将前一次裁剪的结果多边形作为下一次裁剪时的被裁剪多边形，即可得到完整的多边形裁剪程序。

5. Weiler－Atherton多边形裁剪算法

1．Weiler－Atherton任意多边形裁剪算法思想：

假设被裁剪多边形和裁剪窗口的顶点序列都按顺时针方向排列。当两个多边形相交时，交点必然成对出现，其中一个是从被裁剪多边形进入裁剪窗口的交点，称为“入点”，另一个是从被裁剪多边形离开裁剪窗口的交点，称为“出点”。算法从被裁剪多边形的一个入点开始，碰到入点，沿着被裁剪多边形按顺时针方向搜集顶点序列；而当遇到出点时，则沿着裁剪窗口按顺时针方向搜集顶点序列。按上述规则，如此交替地沿着两个多边形的边线行进，直到回到起始点。这时，收集到的全部顶点序列就是裁剪所得的一个多边形。由于可能存在分裂的多边形，因此算法要考虑：将搜集过的入点的入点记号删去，以免重复跟踪。将所有的入点搜集完毕后算法结束。

2．Weiler－Atherton任意多边形裁剪算法步骤：

  1. 顺时针输入被裁剪多边形顶点序列Ⅰ放入数组1中。
  2. 顺时针输入裁剪窗口顶点序列Ⅱ放入数组2中。
  3. 求出被裁剪多边形和裁剪窗口相交的所有交点，并给每个交点打上“入”、“出”标记。 然后将交点按顺序插入序列Ⅰ得到新的顶点序列Ⅲ，并放入数组3中； 同样也将交点按顺序插入序列Ⅱ得到新的顶点序列Ⅳ，放入数组4中；
  4. 初始化输出数组Q，令数组Q为空。接着从数组3中寻找“入”点。如果“入”点没找到，程序结束。
  5. 如果找到“入”点，则将“入”点放入S中暂存。
  6. 将“入”点录入到输出数组Q中。并从数组3中将该“入”点的“入”点标记删去。
  7. 沿数组3顺序取顶点：如果顶点不是“出点”，则将顶点录入到输出数组Q中，流程转第7步。否则，流程转第8步。
  8. 沿数组4顺序取顶点：如果顶点不是“入点”，则将顶点录入到输出数组Q中，流程转第8步。否则，流程转第9步。
  9. 如果顶点不等于起始点S，流程转第6步，继续跟踪数组3。否则，将数组Q输出；流程转第4步，寻找可能存在的分裂多边形。算法在第4步：满足“入”点没找到的条件时，算法结束。算法的生成过程见下图所示。

3．Weiler－Atherton任意多边形裁剪算法特点：

  1. 裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。
  2. 可实现被裁剪多边形相对裁剪窗口的内裁或外裁，即保留窗口内的图形或保留窗口外的图形，因此在三维消隐中可以用来处理物体表面间的相互遮挡关系。3、裁剪思想新颖，方法简洁，裁剪一次完成，与裁剪窗口的边数无关。

源码参考（C++）

1.基本变换矩阵

  1. //计算变换矩阵
  2. void CalculateMatrix(float transMatrix[3][2])
  3. {
  4.     Ccg2DTransDoc* pDoc = GetDocument();
  6.     switch (pDoc->m_transDir) {
  7.     case 0: // -X
  8.         switch (pDoc->m_transMode) {
  9.         case 0: // Move
  10.             TranslateMatrix(-DELTAX, 0, transMatrix);
  11.             break;
  12.         case 1: // rotate
  13.             RotateMatrix(-sin(DELTATHETA), cos(DELTATHETA), transMatrix);
  14.             break;
  15.         case 2: // Scale
  16.             ScaleMatrix(SSCALEX, 1, transMatrix);
  17.             break;
  18.         }
  19.         break;
  20.     case 1: // +X
  21.         switch (pDoc->m_transMode) {
  22.         case 0: // Move
  23.             TranslateMatrix(DELTAX, 0, transMatrix);
  24.             break;
  25.         case 1: // rotate
  26.             RotateMatrix(sin(DELTATHETA), cos(DELTATHETA), transMatrix);
  27.             break;
  28.         case 2: // Scale
  29.             ScaleMatrix(LSCALEX, 1, transMatrix);
  30.             break;
  31.         }
  32.         break;
  33.     case 2: // -Y
  34.         switch (pDoc->m_transMode) {
  35.         case 0: // Move
  36.             TranslateMatrix(0, -DELTAY, transMatrix);
  37.             break;
  38.         case 1: // rotate
  39.             RotateMatrix(-sin(DELTATHETA), cos(DELTATHETA), transMatrix);
  40.             break;
  41.         case 2: // Scale
  42.             ScaleMatrix(1, SSCALEY, transMatrix);
  43.             break;
  44.         }
  45.         break;
  46.     case 3: // +Y
  47.         switch (pDoc->m_transMode) {
  48.         case 0: // Move
  49.             TranslateMatrix(0, DELTAY, transMatrix);
  50.             break;
  51.         case 1: // rotate
  52.             RotateMatrix(sin(DELTATHETA), cos(DELTATHETA), transMatrix);
  53.             break;
  54.         case 2: // Scale
  55.             ScaleMatrix(1, LSCALEY, transMatrix);
  56.             break;
  57.         }
  58.         break;
  59.     }
  60. }
  1. //缩放矩阵
  2. void Ccg2DTransView::ScaleMatrix(float Sx, float Sy, float m[3][2])
  3. {
  4.     for (int i = 0; i < 3; i++) {
  5.         m[i][0] *= Sx;
  6.         m[i][1] *= Sy;
  7.     }
  8. }
  1. //旋转矩阵
  2. void RotateMatrix(float S, float C, float m[3][2])
  3. {
  4.     float temp;
  5.     for (int i = 0; i < 3; i++) {
  6.         temp = m[i][0];
  7.         m[i][0] = temp * C - m[i][1] * S;
  8.         m[i][1] = temp * S + m[i][1] * C;
  9.     }
  10. }
  1. //平移矩阵
  2. void TranslateMatrix(float Tx, float Ty, float m[3][2])
  3. {
  4.     // 矩阵平移变换的位移量
  5.     m[2][0] += Tx;
  6.     m[2][1] += Ty;
  7. }

2.绘制直线

  1. //绘制直线
  2. void DisplayLine(CDC* pDC, CPoint p1, CPoint p2, COLORREF rgbColor)
  3. {
  4.     CcgTransDoc* pDoc = GetDocument();
  6.     CPen newPen;
  7.     CPen* oldPen;
  8.     CPoint VP1, VP2;
  10.     newPen.CreatePen(PS_SOLID, 2, rgbColor);
  11.     oldPen = (CPen*)pDC->SelectObject(&newPen);
  13.     VP1.x = m_wndWidth / 2 + p1.x;
  14.     VP1.y = m_wndHeight / 2 - p1.y;
  15.     VP2.x = m_wndWidth / 2 + p2.x;
  16.     VP2.y = m_wndHeight / 2 - p2.y;
  18.     pDC->MoveTo(VP1);
  19.     pDC->LineTo(VP2);
  21.     pDC->SelectObject(oldPen);
  22.     newPen.DeleteObject();
  23. }

3.直线2D变换

  1. //直线2D变换
  2. void TransLine(CPoint p1, CPoint p2, CPoint* tp1, CPoint* tp2, float transMatrix[3][2])
  3. {
  4.     // 更改移动后的线段端点坐标p1, p2,利用矩阵乘法(x,y,1) * transMatrix[3][2]
  5.     tp1->x = p1.x * transMatrix[0][0] +
  6.              p1.y * transMatrix[1][0] +
  7.                     transMatrix[2][0];
  8.     tp1->y = p1.x * transMatrix[0][1] +
  9.              p1.y * transMatrix[1][1] +
  10.                     transMatrix[2][1];
  11.     tp2->x = p2.x * transMatrix[0][0] +
  12.              p2.y * transMatrix[1][0] +
  13.                     transMatrix[2][0];
  14.     tp2->y = p2.x * transMatrix[0][1] +
  15.              p2.y * transMatrix[1][1] +
  16.                     transMatrix[2][1];
  17. }