录十六

一、红黑树简介

红黑树（R-B Tree）,全称Red-Black Tree。它是一种自平衡二叉查找树，是计算机科学中一种非常重要的数据结构。红黑树实现比较复杂，但是它具有高效，稳定的查找效率，所以在很多地方都有应用。在C++ STL中，set, multiset, map, multimap底层都是基于红黑树实现的。

（1）红黑树性质

红黑树是一种普通的二叉树查找上，仅仅只是对每个节点添加一个颜色属性形成的，它具有以下五条性质：

一、什么是GLUT工具库

GLUT英文全称是OpenGL Utility Tookit，它是Mark J.Kilgard为了简化OpenGL窗口的创建，而开发出来的一个工具库。GLUT是开源的，同时也是独立于操作系统的。对于OpenGL开发，它不是必须的，但是它可以使我们很容易的创建出OpenGL窗口，而无需关注操作系统相关的窗口模块。

二、GLUT库和freeglut库的区别

GLUT库和freeglut库两者都是开源的，它们都是为了能让初学者更好地学习OpenGL而开发的窗口工具包。GLUT是一个非常古老的库，而且已经没有人维护了。后来就有好心的人士又开发了freeglut库，它所有的函数接口都和GLUT保持一致，并且新增了一些接口。因此，它比GLUT功能更加强大，并且完全可以替代GLUT库。

一、撤销git add操作

修改的文件已经添加到暂存区，但是还没有执行commit操作，可以通过下面命令撤销：

git rm --cached <added_file_to_undo>

虽然暂存区的文件会被撤回，但是工作区的内容还在本地磁盘上，这样是最安全的方法。

一、什么是抽稀？

在处理矢量曲线数据时，记录中往往会有很多重复数据，对进一步数据处理带来诸多不便。多余的数据一方面浪费了较多的存储空间，另一方面造成所要表达的图形不光滑或不符合标准。因此要通过某种规则，在保证矢量曲线形状不变的情况下， 最大限度地减少数据点个数，这个过程称为抽稀。

通俗的讲就是对曲线进行采样简化，即在曲线上取有限个点，将其变为折线，并且能够在一定程度保持原有形状。比较常用的两种抽稀算法是：道格拉斯-普克(Douglas-Peuker)算法和垂距限值法。

二维纹理映射

前面绘制三棱锥时，为了将模型移动到视景体范围内，我们修改了模型的顶点坐标。如果要在场景不同的位置渲染多个模型，直接修改模坐标显然是不合理的。为了解决这个问题，就需要引入模型变换的概念。

一、世界坐标系和模型坐标系

世界坐标系是一种特殊的坐标系，它建立了描述其它坐标系所需的参考框架。也就说要描述其它坐标系，必须依赖世界坐标系，而无法用其它坐标系来描述世界坐标系，因此它也叫全局坐标系。

模型坐标系是和特定模型相关联的坐标系。在定义一个三维模型，或者通过其它3D软件建立三维模型时，一般都需要以模型自身的中心建立坐标系的，然后在这个坐标系下构建三维模型。以模型自身建立的坐标系叫做模型坐标系，模型在模型坐标系下的坐标，叫模型坐标（也叫局部坐标）。

在正交投影下，物体和观察者之间的距离并不影响它的看上去的大小，这种类型的投影常用于工业制图和计算辅助设计等。因为在这类应用中，物体经过投影过后，保持它们的实际大小和它们之间的角度才是至关重要的。

一、平面上的正交投影

已知点P为平面上确定的一点，平面的法向量为N，则平面上的任意一点M满足平面的点法式方

一、平面上的透视投影

已知点P为平面上确定的一点，平面的法向量为N，则平面上的任意一点M满足平面的点法式方程：

N • (M - P) = 0

已知观察点为E，

一、3D笛卡尔坐标系

3D笛卡尔坐标系与我们常见2D笛卡尔坐标系相同，但是增加了一条Z轴。这三条轴互相垂直，坐标系有3个自由度。要定义3D空间中的一点P，需要三个坐标：x，y，z，或简写P（x，y，z）。另外，这三条轴构成了三个平面：x-y平面，x-z平面和y-z平面，每个平面将空间分成两个区域（半空间），这三个平面最终将整个空间分成8个子空间，也就是8个卦限。

一直对齐次坐标这个概念的理解不够彻底，只见大部分的书中说道“齐次坐标在仿射变换中非常的方便”，然后就没有了后文，今天在一个叫做”三百年重生”的博客上看到一篇关于透视投影变换的探讨的文章，其中有对齐次坐标有非常精辟的说明，特别是针对这样一句话进行了有力的证明：“齐次坐标表示是计算机图形学的重要手段之一，它既能够用来明确区分向量和点，同时也更易用于进行仿射（线性）几何变换。” F.S.Hill,JR 。

（1）对于一个向量V以及基o