计算机图形与OpenGL学习二(输出图元2：填充区图元的理论部分)
1. 多边形
【多边形定义】：由三个或更多顶点的坐标位置描述的平面图形，这些顶点由多边形的边顺序相连。多边形的边除了端点之外没有其他的公共点。
【凸多边形、凹多边形与退化多边形】
凸多边形是一个内部为 凸集的简单多边形。简单多边形的下列性质与其凸性等价：1、所有 内角小于等于180度。2、任意两个 顶点间的 线段位于多边形的内部或边上。3、多边形内任意两个点，其连线全部在多边形内部
或边上。
凹多边形（Concave Polygon）：
1.至少有一个钝角（Reflexive Angle）的多边形。（例如下图中，∠CDE>180°）
2，把一个各边不自交的多边形任意一边向两方无限延长成为一直线，如果多边形的所有边中只要有一条边向两方无限延长成为一直线时，其他各边不在此直线的同旁（如上图左），那么这个多边形就叫做凹多边形。
退化多边形是多边形的一种，是一种退化的多边形，是指一个多边形在满足多边形定义的临界。退化三角形是指面积为零的三角形(顶点重合)。
【为什么要介绍凹凸退化多边形】
计算机图形中，图形软件包拒绝退化多边形。OpenGL也要求所有填充多边形为凸多边形，凹多变形需要分割成为凸多边形。下面介绍凹多边形的分割步骤。
【凹多边形转化为凸多边形】
1.识别凹多边形:为每一条边建立一个向量,使用相邻边的叉积来测试凹凸性,凸多边形的所有边的向量叉积均同号,因此一个多边形的所有边向量的叉积一些为正 ,一些为负,则可确定其为凹多边形。
其中Ek是第K条边向量，Vk是第K个顶点。
2.分割凸多边形
①向量法
我们可以通过逆时针方向来计算边向量之间的叉乘，如果有一个叉乘结果为负值，则多边形为凹，且可沿叉乘中第一条边向量的直线进行切割。如下图：
E2叉乘E3为负，延长E2求交点，将凹多边形进行了分割。
②旋转法：暂不介绍
【凸多边形分割成三角形集】
在计算机图形中，用于指定多边形的一组顶点并不严格在一个平面上。这是由于数值计算的舍入误差、多边形面片逼近曲面所引起的。因此需要将得到的凸多边形分割成三角形（三角形由三个顶点确定，可保证三个顶点所确定的三角形在一个平面）。
通过检测凹多边形，并将凹多边形分割，我们已经得到了只有凸多边形的顶点集。我们可以将其变成一组三角形。
凸多边形分割成三角形集的操作：将任意顺序的三个连续顶点定义为一个新多边形，然后将三角形的中间顶点从多边形原顶点队列中删除。（如Vk，Vk+1，Vk+2是三个连续顶点，组成一个三角形，移除Vk+1。因为Vk+1不会再形成新的三角形。）接着使用相同的过程处理修改后的顶点队列，直到原多边形只剩三个顶点，这就是最后一个三角形。
【内-外测试】
到目前为止，我们讲了如何进行多边形的填充，是不是就结束了？别着急，问题还没有完。我们之前讨论的是凸多边形等简单几何，但是对于填充问题，我们还要考虑有些图形是要区分内部和外部的（如下图），这就是要谈的内-外测试
【以奇偶规则或非零环绕数方法确定内-外区域】
详细请跳转到https://blog.****.net/heyuchang666/article/details/51383542
【多边形表】
场景中的对象一般用一组多边形面片来描述。对每个对象都描述包括：①指定多边形面片的集合信息②其他表面参数（如颜色、透明性及光的反射性）。在输入每个多边形的信息时，数据放进一些表格中等待后序处理、显示和场景的对象管理。所对应的就是多边形数据的两组表：几何数据表和属性数据表。几何数据表包含顶点坐标和标识多边形面片空间方向的参数，几何数据表又组织为顶点表、边表和面片表；属性数据表包含指定对象的透明程度及其表面的反射性能和纹理特征。
【一个实例】
如上图所示的图形，由五个顶点构成。
顶点表：储存了每一个顶点的坐标。
边表：包含指向顶点表的指针以确定每一多边形的边的端点。
面片表：包含指向边表的指针以确定每个多边形的边。
【平面方程】
要完成三维场景中的显示，就需要对图形系统进行若干步处理。如坐标变换，可见面判定、对各面片绘制。很多处理需要对象表面的空间方向信息，因此就需要从平面方程中去获得这些信息。
平面方程为：
用平面上的三个非共线点带入，就可以解出：
【前向面与后向面】
后向面：向着对象内部的一侧
前向面：可见或朝外的一侧
在右手笛卡尔坐标系下可用以下方法判断一个点方向
如果任意点(x,y,z)不在平面上，则
如果 ，则(x,y,z)在平面后方
如果 ，则(x,y,z)在平面前方
多边形表面空间方向可用其所在平面的法向量来描述，法向量从平面的内部指向外部，即从后方指向前方。