计算机图形学作业：Cohen-Sutherland和Liang-Barsky 裁剪算法

参考书籍和资料：

Liang-Barsky参考下面视频14.2.1

[14.2.1]--讲解经典的梁友栋-巴斯基算法。_哔哩哔哩_bilibili

?Cohen-Sutherland参考孔令德的计算机图形学实验及课程设计（第二版），实验五直线段的裁剪

题目如下：

3. 编写程序，采用 Cohen-Sutherland 裁剪算法实现矩形窗口 ABCD 对线段 P1P2的裁剪，并返回裁剪结果。

//设置标志flag表示有线段在窗口内，数组cohen保存裁剪后的线段端点信
//息。设wxl , wxr ,wyb , wyt分别为窗口ABCD的左右边界x，下上边界y
class CPCohen//COhen-Sutherland算法的编码
{
public:
	double x, y;
	short rc;//编码
};
const int LEFT = 1, RIGHT = 2, BOTTOM = 4, TOP = 8;int flag=0;
void EnCode(CPCohen& pt)//对端点进行编码
{
	pt.rc = 0;
	if (pt.x < wxl) pt.rc = pt.rc | LEFT;
	else if (pt.x > wxr) pt.rc = pt.rc | RIGHT;
	if (pt.y < wyb)  pt.rc = pt.rc | BOTTOM;
	else if (pt.y > wyt) pt.rc = pt.rc | TOP;
}
void Cohen(CPCohen& p1, CPCohen& p2)
{
	CPCohen p;
	EnCode(p1); 
	EnCode(p2);
	if (p1.rc == 0 && p2.rc == 0)//两端点都在窗口内
	{
		cohen[0] = p1, cohen[1] = p2;
		flag=1;
		return;
	}
while (p1.rc != 0 || p2.rc != 0)
	{
		if (0 != (p1.rc & p2.rc))//两端点都在窗口外,丢弃
			return;
		short rc = p1.rc;
		if (p1.rc == 0) rc = p2.rc; 
		
		if (rc & LEFT)//在某个窗口边界不可见一侧时才求交
		{
			p.x = wxl;
			p.y = p1.y + (p2.y - p1.y) * (p.x - p1.x) / (p2.x - p1.x);
		}
		else if (rc & RIGHT)
		{
			p.x = wxr;
			p.y = p1.y + (p2.y - p1.y) * (p.x - p1.x) / (p2.x - p1.x);
		}
		else if (rc & BOTTOM)
		{
			p.y = wyb;
			p.x=p1.x+ (p2.x - p1.x)  * (p.y - p1.y) /(p2.y - p1.y);
		}
		else if (rc & TOP)
		{
			p.y = wyt;
			p.x = p1.x + (p2.x - p1.x) * (p.y - p1.y) / (p2.y - p1.y);
		}
		EnCode(p);
		if (rc == p1.rc)//求出交点替换掉原来的点
			p1 = p;
		else
			p2 = p;
if (p1.rc == 0 && p2.rc == 0)//两端点都在窗口内
		{
			cohen[0] = p1, cohen[1] = p2;
			flag=1;
			return;
		}
	}
}

?4. 编写程序，采用 Liang-Barsky 算法实现矩形窗口 ABCD 对线段 P1P2 的裁剪，返回裁剪结果，并举例说明算法的执行过程。

//设置标志flag表示有线段在窗口内，数组cohen保存裁剪后的线段端点信
//息。设wxl , wxr ,wyb , wyt分别为窗口ABCD的左右边界x，下上边界y
void Liang(CPoint& p1, CPoint& p2)
{
	double xl = min(p1.x, p2.x), xr = max(p1.x, p2.x),k= (p2.y - p1.y) /(p2.x-p1.x),m= (p2.x - p1.x) / (p2.y - p1.y);
	xl = max(xl, wxl), xr = min(xr, wxr);
	double xt = m * (wyb - p1.y) + p1.x, xu = m * (wyt - p1.y) + p1.x; int flag=0;
	if (k > 0)
	{
		if (xl <= xr&&xl<=xu&&xt<=xr)
		{
			double tx=p1.x;
			p1.x = max(xl, xt);
			p1.y = k * (p1.x - tx) + p1.y;
			tx = p2.x;
			p2.x = min(xr, xu);
			p2.y= k * (p2.x - tx) + p2.y;
			cohen[0] = p1, cohen[1] = p2;flag=1;
			return;
		}
	}
if (k < 0)
	{
		if (xl <= xr && xl <= xt && xu <= xr)
		{
			double tx = p1.x;
			p1.x = max(xl, xu);
			p1.y = k * (p1.x - tx) + p1.y;
			tx = p2.x;
			p2.x = min(xr, xt);
			p2.y = k * (p2.x - tx) + p2.y;
			cohen[0] = p1, cohen[1] = p2;flag=1;
			return;
		}
	}

例子：

设有线段AB，A(3,3),B(-2,-1)，矩形窗口的wxl,wxr,wyb,wyt为0,2,0,2。

解：线段AB的参数方程为：x=3+u*(-2-3)=3-5u,y=3+u*(-1-3)=3-4u (0<=u<=1)

因此：

p1=x1-x2=5>0,q1=x1-wxl=3;p2=x2-x1=-5<0,q2=wxr-x1=-1;

p3=y1-y2=4>0,q3=y1-wyb=3;p4=y2-y1=-4<0,q4=wyt-y1=-1。pi均不为0。

线段与窗口边界的交点计算如下：

由uk*pk=qk(k=1,2,3,4)得u1=0.6,u2=0.2,u3=0.75,u4=0.25

由于p1、p3大于0，p2、p4小于0

则Uone=max(0,u2,u4)=0.25,Utwo=min(1,u1,u3)=0.6，满足Uone< Utwo，他们分别对应输出线段的起点和终点，将他们带入AB的参数方程，可得：

Uone对应点(1.75,2)，Utwo对应点(0,0.6)，即为裁剪后的线段端点。