‘壹’ 求英语高手翻译论文摘要,非常感谢!
This paper describes a computer line cutting technology and computer animation technology. Computer technology is cutting will be designated as a graphics window border, from a large screen to extract the required specific information, to show a partial picture or View. Computer animation technology is graphic, pictorial and video, or part of the display on the screen. and in accordance with certain rules or scheled at the request of movement on the screen, transform, so that the computer shows the dynamic changes of graphics. This paper also addresses the line clipping algorithm and the basic principles of computer animation technology to achieve animation proction process. First, introced a line of cutting algorithm, including three cutting algorithm : Cohen-Sutherland algorithm cutting, cutting the midpoint segmentation algorithm, friends of Liang Dong-Barskey cutting algorithm. Then, the computer animation technology to achieve animation proction process. In addition, the introction to this paper, also gave a detailed presentation of the concept of computer animation and computer animation in various fields of application, Let readership of this paper, when this new technology has a preliminary understanding.
‘贰’ XGBoost原理
更好的阅读体验请跳转至 XGBoost原理
一.绪论
在实际应用的机器学习方法里，GradientTree Boosting （GBDT）是一个在很多应用里都很出彩的技术。XGBoost是一套提升树可扩展的机器学习系统。2015年Kaggle发布的29个获胜方法里有17个用了XGBoost。在这些方案里，有8个仅用了XGBoost，另外的大多数用它结合了神经网络。对比来看，第二流行的方法，深度神经网络，只被用了11次。这个系统的成功性也被KDDCup2015所见证了，前十的队伍都用了XGBoost。此外，据胜出的队伍说，很少有别的集成学习方法效果能超过调好参的XGBoost。
主要创新点：
设计和构建高度可扩展的端到端提升树系统。
提出了一个理论上合理的加权分位数略图（weighted quantile
sketch ）来计算候选集。
引入了一种新颖的稀疏感知算法用于并行树学习。 令缺失值有默认方向。
提出了一个有效的用于核外树形学习的缓存感知块结构。 用缓存加速寻找排序后被打乱的索引的列数据的过程。
二.算法原理
1.学习目标
首先来看下我们是如何预测的：
XGBoost是一个树集成模型，他将K（树的个数）个树的结果进行求和，作为最终的预测值。即：
最终我们将关于树模型的迭代转化为关于树的叶子节点的迭代，并求出最优的叶节点分数。
将叶节点的最优值带入目标函数，最终目标函数的形式为：
上式可以作为得分函数用来测量树结构q的质量，他类似与决策树的不纯度得分，只是他通过更广泛的目标函数得到
节点划分
而通常情况下，我们无法枚举所有可能的树结构然后选取最优的，所以我们选择用一种贪婪算法来代替：我们从单个叶节点开始，迭代分裂来给树添加节点。节点切分后的损失函数：
上式用来评估切分后的损失函数，我们的目标是寻找一个特征及对应的值，使得切分后的loss rection最大。γ除了控制树的复杂度，另一个作用是作为阈值，只有当分裂后的增益大于γ时，才选择分裂，起到了预剪枝的作用。
缩减与列采样
除了在目标函数中引入正则项，为了防止过拟合，XGBoost还引入了缩减(shrinkage)和列抽样（column subsampling），通过在每一步的boosting中引入缩减系数，降低每个树和叶子对结果的影响；列采样是借鉴随机森林中的思想，根据反馈，列采样有时甚至比行抽样效果更好，同时，通过列采样能加速计算。
寻找最佳分割点算法
树模型学习的一个关键问题是如何寻找最优分割点。第一种方法称为基本精确贪心算法（exact greedy algorithm）：枚举所有特征的所有可能划分，寻找最优分割点。该算法要求为连续特征枚举所有可能的切分，这个对计算机要求很高，为了有效做到这一点，XGBoost首先对特征进行排序，然后顺序访问数据，累计loss rection中的梯度统计量（式6）。
上述方法是一个非常精确的分割点算法，但是当数据无法完全加载进内存或分布式的情况下，该算法就不是特别有效了。为了支持这两种场景，提出了一种近似算法：根据特征分布的百分位数，提出n个候选切分点，然后将样本映射到对应的两个相邻的切分点组成的桶中，聚会统计值，通过聚会后的统计值及推荐分割点，计算最佳分割点。该算法有两种形式：全局近似和局部近似，其差别是全局近似是在生成一棵树之前，对各个特征计算其分位点并划分样本；局部近似是在每个节点进行分裂时采用近似算法。近似算法的流程：
带权重的分位数略图（weighted quantile sketch）算法
在近似算法中重要的一步是寻找候选分割点，通常情况下，特征的百分位数使数据均匀的分布在数据上。现在我们定义一个数据集Dk = {(x1k, h1), (x2k, h2) ... }代表样本的第k个特征及其对应的二阶梯度，现在我们定义一个函数rk：
参考： https://arxiv.org/pdf/1603.02754.pdf
https://www.hu.com/question/41354392/answer/98658997
‘叁’ 计算机图形学问题：编写中点分割的线段裁剪算法
#include <GL/glut.h>
#include <stdlib.h>
#include "iostream.h"
int x0,y0,x1,y1;
int Max(int a,int b,int c)
{
if(a>b)
{
if(a>c)
return a;
else
return c;
}
else
{
if(b>c)
return b;
else
return c;
}
}
int Min(int a,int b,int c)
{
if(a<b)
{
if(a<c)
return a;
else
return c;
}
else
{
if(b<c)
return b;
else
return c;
}
}
void DrawLine1(int x0,int y0,int x1,int y1)
{
int d,temp;
temp=y0;
d=2*(y1-y0)-(x1-x0);
glBegin(GL_POINTS);
glVertex2d(x0,y0);
glEnd();
for(int k=x0+1;k<x1;k++)
{
if(d>=0)
{
glBegin(GL_POINTS);
glVertex2d(k,temp+1);
glEnd();
d=d+2*(y1-y0)-2*(x1-x0);
temp=temp+1;
}
else
{
glBegin(GL_POINTS);
glVertex2d(k,temp);
glEnd();
d=d+2*(y1-y0);
temp=temp;
}
}
glBegin(GL_POINTS);
glVertex2d(x1,y1);
glEnd();
}
void DrawLine2(int x0,int y0,int x1,int y1)
{
int d,temp;
temp=x0;
d=2*(x1-x0)-(y1-y0);
glBegin(GL_POINTS);
glVertex2d(x0,y0);
glEnd();
for(int k=y0+1;k<y1;k++)
{
if(d>=0)
{
glBegin(GL_POINTS);
glVertex2d(temp+1,k);
glEnd();
d=d+2*(x1-x0)-2*(y1-y0);
temp=temp+1;
}
else
{
glBegin(GL_POINTS);
glVertex2d(temp,k);
glEnd();
d=d+2*(x1-x0);
temp=temp;
}
}
glBegin(GL_POINTS);
glVertex2d(x1,y1);
glEnd();
}
void DrawTriangle(int x0,int y0,int x1,int y1,int x2,int y2)
{
int xmin,xmax,ymin,ymax;
float a,b,c;
xmin=Min(x0,x1,x2);
xmax=Max(x0,x1,x2);
ymin=Min(y0,y1,y2);
ymax=Max(y0,y1,y2);
glColor3f(1.0f,0.0f,0.0f);
glBegin(GL_POINTS);
glVertex2d(x0,y0);
glEnd();
glColor3f(0.0f,1.0f,0.0f);
glBegin(GL_POINTS);
glVertex2d(x1,y1);
glEnd();
glColor3f(0.0f,0.0f,1.0f);
glBegin(GL_POINTS);
glVertex2d(x2,y2);
glEnd();
for(float n=ymin;n<=ymax;n++)
for(float m=xmin;m<xmax;m++)
{
a=((y1-y2)*m+(x2-x1)*n+x1*y2-x2*y1)/((y1-y2)*x0+(x2-x1)*y0+x1*y2-x2*y1);
b=((y2-y0)*m+(x0-x2)*n+x2*y0-x0*y2)/((y2-y0)*x1+(x0-x2)*y1+x2*y0-x0*y2);
c=((y0-y1)*m+(x1-x0)*n+x0*y1-x1*y0)/((y0-y1)*x2+(x1-x0)*y2+x0*y1-x1*y0);
if(a>0 && b>0 && c>0)
{
float color0=a*1.0;
float color1=b*1.0;
float color2=c*1.0;
glColor3f(color0,color1,color2);
glBegin(GL_POINTS);
glVertex2d(m,n);
glEnd();
}
}
}
void display()
{
/* clear all pixels */
glClear (GL_COLOR_BUFFER_BIT);
glColor3f (1.0, 1.0, 1.0);
glBegin(GL_POINTS);
glVertex2d(x,y); 中间是点的坐标
glEnd();
*/
/*下面的语句是画一个白色的正方形*/
if((y1-y0)/(x1-x0)<=1)
{
DrawLine1(x0,y0,x1,y1);
}
else
{
DrawLine2(x0,y0,x1,y1);
}
DrawTriangle(35,35,135,185,235,35);
/* don't wait!
* start processing buffered OpenGL routines
*/
glFlush ();
}
void init (void)
{
/* select clearing color */
glClearColor (0.0, 0.0, 0.0, 0.0);
/* initialize viewing values */
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0, 600, 0, 600);
}
/*
* Declare initial window size, position, and display mode
* (single buffer and RGBA). Open window with "hello"
* in its title bar. Call initialization routines.
* Register callback function to display graphics.
* Enter main loop and process events.
*/
int main(int argc, char** argv)
{
cout<<"input x0,y0,x1,y1 :"<<endl;
cin>>x0>>y0>>x1>>y1;
glutInit(&argc, argv);
glutInitDisplayMode (GLUT_SINGLE | GLUT_RGB);
//设置窗口大小，以像素为单位
glutInitWindowSize (600, 600);
glutInitWindowPosition (100, 100);
glutCreateWindow ("hello");
init ();
glutDisplayFunc(display);
glutMainLoop();
return 0; /* ANSI C requires main to return int. */
}
////以前写的 不知道有没有用
‘肆’ 请教一个算法的实现原理
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：
1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；
2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；
3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
5）、重复第3、4步，直到I=J；
例如：待排序的数组A的值分别是：（初始关键数据X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 97 76 13 27
进行第一次交换后： 27 38 65 97 76 13 49
( 按照算法的第三步从后面开始找
进行第二次交换后： 27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )
进行第三次交换后： 27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找
进行第四次交换后： 27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )
此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。
快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：
初始状态 {49 38 65 97 76 13 27}
进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
分别对前后两部分进行快速排序 {13} 27 {38}
结束 结束 {49 65} 76 {97}
49 {65} 结束
结束
图6 快速排序全过程
1）、设有N（假设N=10）个数，存放在S数组中；
2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]，在S[K]以后的数都大于S[K]；
3）、利用分治思想（即大化小的策略）可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。
如具体数据如下，那么第一躺快速排序的过程是：
数组下标： 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
I J
（1） 36 36 18 53 72 30 48 93 15 45
（2） 36 36 18 45 72 30 48 93 15 53
（3） 36 36 18 15 72 30 48 93 45 53
（4） 36 36 18 15 45 30 48 93 72 53
（5） 36 36 18 15 30 45 48 93 72 53
通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1。。5]和S[6。。10]分别进行快速排序。
一般来说，冒泡法是程序员最先接触的排序方法，它的优点是原理简单，编程实现容易，但它的缺点就是--程序的大忌--速度太慢。下面我介绍一个理解上简单但编程实现上不是太容易的排序方法，我不知道它是不是现有排序方法中最快的，但它是我见过的最快的。排序同样的数组，它所需的时间只有冒泡法的 4% 左右。我暂时称它为“快速排序法”。
“快速排序法”使用的是递归原理，下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53，12，98，63，18，72，80，46， 32，21}，先找到第一个数--53，把它作为中间值，也就是说，要把53放在一个位置，使得它左边的值比它小，右边的值比它大。{21，12，32， 46，18，53，80，72，63，98}，这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组，而这两个数组继续用同样的方式继续下去，一直到顺序完全正确。
我这样讲你们是不是很胡涂，不要紧，我下面给出实现的两个函数：
/*
n就是需要排序的数组，left和right是你需要排序的左界和右界，
如果要排序上面那个数组，那么left和right分别是0和9
*/
void quicksort(int n[], int left,int right)
{
int dp;
if (left<right) {
/*
这就是下面要讲到的函数，按照上面所说的，就是把所有小于53的数放
到它的左边，大的放在右边，然后返回53在整理过的数组中的位置。
*/
dp=partition(n,left,right);
quicksort(n,left,dp-1);
quicksort(n,dp+1,right); //这两个就是递归调用，分别整理53左边的数组和右边的数组
}
}
我们上面提到先定位第一个数，然后整理这个数组，把比这个数小的放到它的左边，大的放右边，然后
返回这中间值的位置，下面这函数就是做这个的。
int partition(int n[],int left,int right)
{
int lo,hi,pivot,t;
pivot=n[left];
lo=left-1;
hi=right+1;
while(lo+1!=hi) {
if(n[lo+1]<=pivot)
lo++;
else if(n[hi-1]>pivot)
hi--;
else {
t=n[lo+1];
n[++lo]=n[hi-1];
n[--hi]=t;
}
}
n[left]=n[lo];
n[lo]=pivot;
return lo;
}
这段程序并不难，应该很好看懂，我把过程大致讲一下，首先你的脑子里先浮现一个数组和三个指针，第一个指针称为p指针，在整个过程结束之前它牢牢的指向第一个数，第二个指针和第三个指针分别为lo指针和hi指针，分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近，在逼近的过程中不停的与p指针的值比较，如果lo指针的值比p指针的值小，lo++，还小还++，再小再++，直到碰到一个大于p指针的值，这时视线转移到hi指针，如果 hi指针的值比p指针的值大，hi--，还大还--，再大再--，直到碰到一个小于p指针的值。这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面，这时把p指针的值和碰面的值做一个调换，然后返回p指针新的
‘伍’ 计算机图形学复习
第一章
1. 计算机图形：用数学方法描述，通过计算机生成、处理、存储和显示的对象。
2. 图形和图像的主要区别是表示方法不同：图形是用矢量表示；图像是用点阵表示的。图形和图像也可以通过光栅显示器（或经过识别处理）可相互转化。
3. 于计算机图形学紧密相关的学科主要包括 图像处理、计算几何和计算机视觉模式识别。它们的共同点是 以图形/图像在计算机中的表示方法为基础。
4. 交互式计算机图形系统的发展可概括为以下4个阶段：字符、矢量、二维光栅图形、三维图形。
5. 图形学研究的主要内容有：①几何造型技术 ②图形生成技术 ③图形处理技术 ④图形信息的存储、检索与交换技术 ⑤人机交互技术 ⑥动画技术 ⑦图形输入输出技术 ⑧图形标准与图形软件包的研发。
6. 计算机辅助设计和计算机辅助制造 是计算机图形学最广泛最活跃的应用领域。
7. 计算机图形学的基本任务：一是如何利用计算机硬件来实现图形处理功能；二是如何利用好的图形软件；三是如何利用数学方法及算法解决实际应用中的图行处理问题。
8. 计算机图形系统是由硬件系统和软件系统组成的。
9. 计算机图形系统包括处理、存储、交互、输入和输出五种基本功能。
10. 键盘和鼠标是最常用的图形输入设备。鼠标根据测量位移部件的不同，分为光电式、光机式和机械式3种。
11. 数字化仪分为电子式、超声波式、磁伸缩式、电磁感应式等。小型的数字化仪也称为图形输入板。
12. 触摸屏是一种 定位设备，它是一种对于触摸能产生反应的屏幕。
13. 扫描仪由3部分组成：扫描头、控制电路和移动扫描机构。扫描头由光源发射和光鲜接收组成。按移动机构的不同，扫描仪可分为平板式和滚筒式2种。
14. 显示器是计算机的标准输出设备。彩色CRT的显示技术有2种：电子穿透法和荫罩法。
15. 随机扫描是指电子束的定位及偏转具有随意性，电子束根据需要可以在荧光屏任意方向上连续扫描，没有固定扫描线和扫描顺序限制。它具有局部修改性和动态性能。
16. 光栅扫描显示器是画点设备。
17. 点距是指相邻像素点间的距离，与分辨指标相关。
18. 等离子显示器一般有三层玻璃板组成，通常称为等离子显示器的三层结构。
19. 用以输出图形的计算机外部设备称为硬拷贝设备。
20. 打印机是廉价的硬拷贝设备，从机械动作上常为撞击式和非撞击式2种。
21. 常用的喷墨头有：压电式、气泡式、静电式、固体式。
22. 绘图仪分为静电绘图仪和笔式绘图仪。
23. 图形软件的分层。由下到上分别是：①图形设备指令、命令集、计算机操作系统 ②零级图形软件 ③一级图形软件 ④二级图形软件 ⑤三级图形软件。
24. 零级图形软件是面向系统的、最底层的软件，主要解决图形设备与主机的通信与接口问题，又称设备驱动程序。
25. 一级图形软件即面向系统又面向用户，又称基本子系统。
26. 图形应用软件是系统的核心部分。
27. 从物理学角度，颜色以主波长、色纯度和辉度来描述；从视觉角度来看，颜色以色彩、饱和度和亮度来描述。
28. 用适当比列的3种颜色混合，可以获得白色，而且这3种颜色中的任意2种的组合都不能生成第三种颜色，称为三原色理论。
29. RGB模型的匹配表达式是：c=rR+gG+bB。
30. 常用颜色模型
颜色模型名称 使用范围
RGB 图形显示设备（彩色CRT和光栅显示器）
CMY 图形打印、绘制设备
HSV 对应画家本色原理、直观的颜色描述
HSL 基于颜色参数的模型
用基色青、品红、黄定义的CMY颜色模型用来描述硬拷贝设备的输出颜色。它从白光中滤去某种颜色，故称为减色性原色系统。
第二章
31. 直线生成的3个常用算法：数值微分法（DDA）、中点划线法和Bresenham算法。
32. DDA算法的C语言实现：
DDA算法生成直线，起点（x0,y0）,终点（x1,y1）.
Void CMy View ::OnDdaline()
{
CDC *pDC=GetDC(); //获得设备指针
int x0=100,y0=100,x1=300,y1=200,c=RGB(250,0,0);//定义直线两端点和直线颜色
int x,y,i;
float dx,dy,k;
dx=(float)(x1-x0);
dy=(float)(y1-y0);
k=dy/dx;
x=x0;
y=y0;
if(abs(k)<1)
{ for(;x<=x1;x++)
{pDC—>SetPixel(x,int(y+0.5),c);
y=y+k;}
}
if(abs(k)>=1)
{ for(;y<=y1;y++)
{pDC—>SetPixel(int(x+0.5),y,c);
x=x+1/k;}
}
ReleaseDC(pDC); //释放设备指针
}
33. 任何影响图元显示方法的参数称为属性参数。图元的基本表现是线段，其基本属性包括线型、线宽和色彩。
34. 最常见的线型包括实线、虚线、细线和点划线等，通常默认的线型是实线。
35. 线宽控制的实线方法：垂直线刷子、水平线刷子、方形线刷子。生成具有宽度的线条还可以采用区域填充算法。
36. 用离散量表示连续量时引起的失真现象称为走样。为了提高图形显示质量，减少或消除走样现象的技术称为反走样。
37. 反走样技术有：提高分辨率（硬件方法和软件方法）、简单区域取样、加权区域取样。
38. 区域连通情况分为四连通区域和八连通区域。四连通区域是指从区域上某一点出发，可通过上下左右4个方向移动，在不越出区域的前提下到达区域内的任意像素；八连通区域是指从区域内某一像素出发，可通过上下左右、左上左下、右上右下8个方向的移动，在不越出区域的前提下到达区域内的任意像素。
39. 字符的图形表示可以分为点阵式和矢量式两种形式。
40. 在图形软件中，除了要求能生成直线、圆等基本图形元素外，还要求能生成其他曲线图元、多边形及符号等多种图元。
41. 在扫描线填充算法中，对水平边忽略而不予处理的原因是实际处理时不计其交点。
42. 关于直线生成算法的叙述中，正确的是：Bresenham算法是对中点画线算法的改进。
43. 在中点画圆算法中叙述错误的是：为了减轻画圆的工作量，中点画圆利用了圆的四对称性性质。
44. 多边形填充时，下列论述错误的是：在判断点是否在多边形内时，一般通过在多变形外找一点，然后根据该线段与多边形的交点数目为偶数即可认为在多边形内部，若为奇数则在多边形外部，且不考虑任何特殊情况。
第三章
1. Cohen-Sutherland算法，也称编码裁剪法。其基本思想是：对于每条待裁剪的线段P1P2分三种情况处理：①若P1P2完全在窗口内，则显示该线段，简称“取”之；②若P1P2完全在窗口外，则丢弃该线段，简称“舍”之；③若线段既不满足“取”的条件也不满足“舍”的条件，则求线段与窗口边界的交点，在交点处把线段分为两段，其中一段 完全在窗口外，可舍弃之，然后对另一段重复上述处理。
2. Sutherland-Hodgman算法，又称逐边裁剪算法。其基本思想是用窗口的四条边所在的直线依次来裁剪多边形。多边形的每条边与裁剪线的位置关系有4种情况（假设当前处理的多边形的边为SP）：a>端点S在外侧，P在内侧，则从外到内输出P和I；b>端点S和P都在内侧，则从内到内输出P；c>端点S在内侧，而P在外侧，则从内到外输出I；d>端点S和P都在外侧，无输出。
3. 按裁剪精度的不同，字符裁剪可分为三种情况：字符串裁剪、字符裁剪和笔画裁剪。
4. 在线段AB的编码裁剪算法中，如A、B两点的码逻辑或运算全为0，则该线段位于窗口内；如AB两点的码逻辑与运算结果不为0，则该线段在窗口外。
5. n边多边形关于矩形窗口进行裁剪，结果多边形最多有2n个顶点，最少有n个顶点。
6. 对一条等长的直线段裁剪，编码裁剪算法的速度和中点分割算法的裁剪速度哪一个快，无法确定。（√）
7. 多边形裁剪可以看做是线段裁剪的组合。（X）
8. 对于线段来说，中点分割算法要比其他线段裁剪算法的裁剪速度快。（X）
9. 多边形的Weiler-Atherton裁剪算法可以实现对任意多边形的裁剪。（√）
第四章
1. 几何变换是指改变几何形状和位置，非几何变换是指改变图形的颜色、线型等属性。变换方法有对象变换（坐标系不动）和坐标变换（坐标系变化）两种。
2. 坐标系可以分为以下几种：世界坐标系（是对计算机图形场景中所有图形对象的空间定位和定义，是其他坐标系的参照）、模型坐标系（用于设计物体的局部坐标系）、用户坐标系(为了方便交互绘图操作，可以变换角度、方向)、设备坐标系（是绘制或输出图形的设备所用的坐标系，采用左手系统）。
3. 将用户坐标系中需要进行观察和处理的一个坐标区域称为窗口，将窗口映射到显示设备上的坐标区域称为视区。从窗口到视区的变换，称为规格化变换。（eg.4-1）
4. 所谓体素，是指可以用有限个尺寸参数定位和定形的体，如长方体、圆锥体。
5. 所谓齐次坐标表示，就是用n+1维向量表示n维的向量。
6. 二维点（x,y）的齐次坐标可以表示为：（hx hy h）,其中h≠0。当h=1时称为规范化的齐次坐标，它能保证点集表示的唯一性。
7. 旋转变换公式的推导、对称变换
第五章
1. 交互绘图技术是一种处理用户输入图形数据的技术，是设计交互绘图系统的基础。常见的交互绘图技术有：定位技术、橡皮筋技术、拖曳技术、定值技术、拾取技术、网格与吸附技术。
2. 常用的橡皮筋技术有：橡皮筋直线、橡皮筋矩形、橡皮筋圆。
3. 拖曳技术是将形体在空间移动的过程动态地、连续地表示出来，直到用户满意。
4. 定值技术有2种：一种是键入数值，另一种是改变电位计阻值产生要求的数量，可以用模拟的方式实现电位计功能。
5. 拾取一个基本的对象可以通过：指定名称法、特征点发、外界矩阵法、分类法、直接法。
第六章
1. 点、线、面是形成三维图形的基础，三维变换是从点开始。
2. 三维图形变换分类：三维图形变换包括三维几何变换和平面几何变换，三维几何变换包括基本几何变换和复合变换；平面几何变换包括平行投影和透视投影，平行投影包括正投影和轴测投影，透视投影包括一点透视、二点透视、三点透视。
3. 投影中心与投影面之间的距离是无限的投影叫做平行投影，它包括正投影和轴测投影。
4. 正投影形成的视图包括：主视图、俯视图和左视图。轴测投影形成的视图为轴测图。
5. 透视投影也称为中心投影，其投影中心与投影面之间的距离是有限的。其特点是产生近大远小的视觉效果
6. 对于透视投影，不平行于投影面的平行线的投影会汇聚到一个点，这个点称为灭点。透视投影的灭点有无限多个，与坐标轴平行的平行线在投影面上形成的灭点称为主灭点。主灭点最多有3个，其对应的透视投影分别称为一点透视、二点透视、三点透视。
第七章
1. 型值点是曲面或曲线上的点，而控制点不一定在曲线曲面上，控制点的主要目的是用来控制曲线曲面的形状。
2. 插值和逼近是曲线曲面设计中的两种不同方法。插值—生成的曲线曲面经过每一个型值点，逼近—生成的曲线曲面靠近每一个控制点。
3. 曲线曲面的表示要求：唯一性、统一性、几何不变性、几何直观、易于界定、易于光滑连接。
4. 曲线曲面有参数和非参数表示，但参数表示较好。非参数表示又分为显式和隐式两种。
5. 对于一个平面曲线，显式表示的一般形式是：y=f(x)。一个x与一个y对应，因此显式方程不能表示封闭或多值曲线。例不能用显式方程表示一个圆。
6. 如果一个曲线方程表示为f(x,y)=0的形式，我们称之为隐式表示。其优点是易于判断函数f(x,y)是否大于、小于或等于零，即易于判断是落在所表示曲线上还是在曲线的哪一侧。
7. 参数连续与几何连续的区别：参数连续性是传统意义上的、严格的连续，而几何连续性只需限定两个曲线段在交点处的参数导数成比例，不必完全相等，是一种更直观、易于交互控制的连续性。
8. 在曲线曲面造型中，一般只用到C1（1阶参数连续）、C2（2阶参数连续）、G1（1阶几何连续）、G2（2阶几何连续）。切矢量（一阶导数）反映了曲线对参数t的变化速递，曲率（二阶导数）反映了曲线对参数t变化的加速度。
9. 通常C1连续必能保证G1的连续，但G1的连续并不能保证C1连续。
10. 对于三次Hermite曲线，用于描述曲线的可供选择的条件有：端点坐标、切矢量和曲率。
11. 三次Hermite曲线特点：①可局部调整，因为每个曲线段仅依赖于端点约束；②基于Hermite样条的变化形式有Cardinal样条和Kochanek-Bartels样条；③具有几何不变性。
12. Bezier曲线的性质：①端点性质②端点切矢量③端点的曲率④对称性⑤几何不变性⑥凸包性⑦变差缩减性。
13. 一次Bezier曲线是连接起点P0和终点P1的直线段，二次Bezier曲线对应一条起点P0终点在P2处的抛物线。
14. B样条曲线的性质：①局部性②连续性或可微性③几何不变性④严格凸包性⑤近似性⑥变差缩减性。
15. NURRS曲线具有以下性质：①局部性②可微性③仿射不变性④严格保凸性⑤一般性⑥变差缩减性⑦端点性质。
第八章
1. 要把三维物体的信息显示在二维显示设备中，必须通过投影变换。由于投影变换失去了深度信息，往往会导致二义性，要消除二义性，就必须在绘制时消除实际不可见的线和面，称作消除隐藏线和隐藏面，简称消隐。
2. 面消隐常用算法有：深度缓冲区（Z-buffer）算法和深度排序算法（画家算法）。
3. 深度缓冲区算法和深度排序算法的区别：
‘陆’ 计算机图形学中有几种直线裁剪算法
计算机图形学(Computer Graphics，简称CG)是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。
简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。图形通常由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。从处理技术上来看，图形主要分为两类，一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等，另一类是明暗图，也就是通常所说的真实感图形。
计算机图形学一个主要的目的就是要利用计算机产生令人赏心悦目的真实感图形。为此，必须建立图形所描述的场景的几何表示，再用某种光照模型，计算在假想的光源、纹理、材质属性下的光照明效果。所以计算机图形学与另一门学科计算机辅助几何设计有着密切的关系。事实上，图形学也把可以表示几何场景的曲线曲面造型技术和实体造型技术作为其主要的研究内容。同时，真实感图形计算的结果是以数字图像的方式提供的，计算机图形学也就和图像处理有着密切的关系。
图形与图像两个概念间的区别越来越模糊，但还是有区别的：图像纯指计算机内以位图形式存在的灰度信息，而图形含有几何属性，或者说更强调场景的几何表示，是由场景的几何模型和景物的物理属性共同组成的。
计算机图形学的研究内容非常广泛，如图形硬件、图形标准、图形交互技术、光栅图形生成算法、曲线曲面造型、实体造型、真实感图形计算与显示算法、非真实感绘制，以及科学计算可视化、计算机动画、自然景物仿真、虚拟现实等。
‘柒’ 图形学编程问题
一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。Weiler-Atherton多边形裁剪算法正是满足这种要求的算法。
Weiler-Atherton又称双边裁剪法。
我找到了中国地质大的一个有关的教程，其中的算法过程具体如下：
1、算法在实现中，需要用到六个数组，分别用来存放：被裁剪多边形、裁剪窗口、交点数组、插入交点后的被裁剪多边形、插入交点后的裁剪窗口、输出多边形。
2、由于交点具有“入”、“出”标记，因此凡与交点有关的数组都要采用结构数组类型：
struct point
{
double x；
double y；
int flag；
}交点数组，数组3，数组4；
标记flag有三种状态：
0：非交点；
1：“入”点；
-1：“出”点。
3、求交点时，利用被裁剪多边形的各边去对裁剪窗口的各边求交点：
for（被裁剪多边形的各边）
{
…；
for（裁剪窗口的各边）
{
求有效交点；放入交点数组；
…；
}
}
4、交点的顺序插入，意味着要对交点数组排序后再分别插入到数组1、数组2的相应位置上。
5、所谓找“入”点、“出”点，必须根据flag找寻满足条件的顶点位置。不光数组3中要找“入”点、“出”点，而且找到后还要转到数组4的相应顶点位置处。对数组4的处理也同上。这种处理在本算法中大量遇到。
‘捌’ 分别解释直线生成算法DDA法、中点画线法和Bresenham法的基本原理
DDA称为数值微分画线算法，是直线生成算法中最简单的一种。原理相当简单，就是最直观的根据斜率的偏移程度，决定是以x为步进方向还是以y为步进方向。然后在相应的步进方向上，步进变量每次增加一个像素，而另一个相关坐标变量则为Yk_1=Yk+m（以x为步进变量为例，m为斜率）
假定直线斜率k在0~1之间，当前象素点为（xp,yp），则下一个象素点有两种可选择点P1（xp+1,yp）或P2（xp+1,yp+1）。若P1与P2的中点（xp+1,yp+0.5）称为M，Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取P1为下一个象素点。这就是中点画线法的基本原理
Bresenham：过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。该算法的优点在于可以采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列所求的像素。
大概就是这样，预知详细，可以参考图形学的书籍
‘玖’ 什么是中点分割裁剪法
中点分割剪取法，主要是对线段不断地进行对分，并排除在区域外的部分，找出线段落在窗口内的部分。其方法主要是通过求出离线段的一个端点最近并且在区域内的点的方法，来确定线段落在窗口内的端点。
‘拾’ 计算机图形学：线段剪裁中点分割算法，要求用C++做，急求源代码啊,谢谢！ 752512212
#include <GL/glut.h>#include <stdlib.h>#include "iostream.h"int x0,y0,x1,y1;int Max(int a,int b,int c){ if(a>b) { if(a>c) return a; else return c; } else { if(b>c) return b; else return c; }}int Min(int a,int b,int c){ if(a<b) { if(a<c) return a; else return c; } else { if(b<c) return b; else return c; }}void DrawLine1(int x0,int y0,int x1,int y1){ int d,temp; temp=y0; d=2*(y1-y0)-(x1-x0); glBegin(GL_POINTS); glVertex2d(x0,y0); glEnd(); for(int k=x0+1;k<x1;k++) { if(d>=0) { glBegin(GL_POINTS); glVertex2d(k,temp+1); glEnd(); d=d+2*(y1-y0)-2*(x1-x0); temp=temp+1; } else { glBegin(GL_POINTS); glVertex2d(k,temp); glEnd(); d=d+2*(y1-y0); temp=temp; } } glBegin(GL_POINTS); glVertex2d(x1,y1); glEnd();}void DrawLine2(int x0,int y0,int x1,int y1){ int d,temp; temp=x0; d=2*(x1-x0)-(y1-y0); glBegin(GL_POINTS); glVertex2d(x0,y0); glEnd(); for(int k=y0+1;k<y1;k++) { if(d>=0) { glBegin(GL_POINTS); glVertex2d(temp+1,k); glEnd(); d=d+2*(x1-x0)-2*(y1-y0); temp=temp+1; } else { glBegin(GL_POINTS); glVertex2d(temp,k); glEnd(); d=d+2*(x1-x0); temp=temp; } } glBegin(GL_POINTS); glVertex2d(x1,y1); glEnd();}void DrawTriangle(int x0,int y0,int x1,int y1,int x2,int y2){ int xmin,xmax,ymin,ymax; float a,b,c; xmin=Min(x0,x1,x2); xmax=Max(x0,x1,x2); ymin=Min(y0,y1,y2); ymax=Max(y0,y1,y2); glColor3f(1.0f,0.0f,0.0f); glBegin(GL_POINTS); glVertex2d(x0,y0); glEnd(); glColor3f(0.0f,1.0f,0.0f); glBegin(GL_POINTS); glVertex2d(x1,y1); glEnd(); glColor3f(0.0f,0.0f,1.0f); glBegin(GL_POINTS); glVertex2d(x2,y2); glEnd(); for(float n=ymin;n<=ymax;n++) for(float m=xmin;m<xmax;m++) { a=((y1-y2)*m+(x2-x1)*n+x1*y2-x2*y1)/((y1-y2)*x0+(x2-x1)*y0+x1*y2-x2*y1); b=((y2-y0)*m+(x0-x2)*n+x2*y0-x0*y2)/((y2-y0)*x1+(x0-x2)*y1+x2*y0-x0*y2); c=((y0-y1)*m+(x1-x0)*n+x0*y1-x1*y0)/((y0-y1)*x2+(x1-x0)*y2+x0*y1-x1*y0); if(a>0 && b>0 && c>0) { float color0=a*1.0; float color1=b*1.0; float color2=c*1.0; glColor3f(color0,color1,color2); glBegin(GL_POINTS); glVertex2d(m,n); glEnd(); } } }void display(){/* clear all pixels */ glClear (GL_COLOR_BUFFER_BIT); glColor3f (1.0, 1.0, 1.0); glBegin(GL_POINTS); glVertex2d(x,y); 中间是点的坐标 glEnd(); */ /*下面的语句是画一个白色的正方形*/ if((y1-y0)/(x1-x0)<=1) { DrawLine1(x0,y0,x1,y1); } else { DrawLine2(x0,y0,x1,y1); } DrawTriangle(35,35,135,185,235,35);/* don't wait! * start processing buffered OpenGL routines */ glFlush ();}void init (void) {/* select clearing color */ glClearColor (0.0, 0.0, 0.0, 0.0);/* initialize viewing values */ glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluOrtho2D(0, 600, 0, 600);}/* * Declare initial window size, position, and display mode * (single buffer and RGBA). Open window with "hello" * in its title bar. Call initialization routines. * Register callback function to display graphics. * Enter main loop and process events. */int main(int argc, char** argv){ cout<<"input x0,y0,x1,y1 :"<<endl; cin>>x0>>y0>>x1>>y1; glutInit(&argc, argv); glutInitDisplayMode (GLUT_SINGLE | GLUT_RGB); //设置窗口大小，以像素为单位 glutInitWindowSize (600, 600); glutInitWindowPosition (100, 100); glutCreateWindow ("hello");
希望能够帮助到你，望采纳，谢谢！