interpolation in Chinese
#线性插值
线性插值有两点值得一提：我所用的基础插值方法，以及透视校正。
##基础插值方法
给定三角形abc内一点p，如下图所示：
对于p点的任何可线性插值的属性P来说，我们定义点abc和点p的线性关系如下：
其中P, P_a, P_b, 和P_c指这四个点上的任一可线性插值属性。C_a和C_b是顶点a和b对内点p的“贡献”比例。
现在我们要求出“贡献”比例，以便对任一属性进行插值。因为点坐标既可线性插值，又是已知量（内点p的坐标是通过栅格化获得的），所以我们把这四个点坐标代入上面方程组，可解得C_a和C_b。
具体解方程组的方法，可以预先做公式变换来解。但更方便的是对线性方程组的系数矩阵求逆，然后通过矩阵和向量相乘来计算。
=>
=>
上面的基本代数方法。不过实际上我们既不会真的去解方程组，也不会去计算逆矩阵，我们需要更快速的方法 —— 请别忘了，如果我们解方程组（或者求逆矩阵），则对三角形每一个内点都要解一遍方程组！并且在解得“贡献”比例后，对每一个内点上的每一个可插值属性，都要计算一遍P= (C_a C_b C_c) dot (P_a P_b P_c)，简直太慢了！
所以在实际程序里，我们用下面的简化方法来进行快速线性插值：（不过快速方法的基本代数原理不变）
- 对三角形覆盖的每一条扫描线（栅格化得到的扫描线），我们先为其两个端点进行线性插值，如下图所示。
可以证明，如果一个三角形内点p在一条边上，那么与p不共边的那个顶点对p没有贡献。例如以上面图中，顶点c对于黑色扫描线的左端点没有贡献，只有顶点ab与之有关。该扫描线的右端点的情况也类似。基于这一事实，我们可以进一步简化前述方程组，使得“贡献”比例计算简化为下面形式：
=>
简化后的计算代码如下面所示。
void PuresoftInterpolater::lineSegmentlinearInterpolate(const float* verts, int vert1,
int vert2, float x, float y, float* contributes)
{
const __POINT& p1 = *(((const __POINT*)verts) + vert1);
const __POINT& p2 = *(((const __POINT*)verts) + vert2);
float dx = p1.x - p2.x, dy = p1.y - p2.y;
contributes[vert1] = fabs(dx) > fabs(dy) ? ((x - p2.x) / dx) : ((y - p2.y) / dy);
contributes[vert2] = 1.0f - contributes[vert1];
contributes[3 - vert1 - vert2] = 0;
}-
得到一条扫描线两端的插值后，我们可以以“步进”的方式获得扫描线内每一点的插值。“步进”值的计算如下：
attributeStep = (attributeRight – attributeLeft) / scanlineLength; -
有了步进只，我们可以从左端点开始，通过如下方式获得每一点的插值。
attribute = attributeLeft;
for(point = leftEnd; point <= rightEnd; point++)
{
process(point, attribute);
attribute += attributeStep;
}通过这种方式，我们可以将插值计算的代价最小化。
##透视校正
我所使用透视校正的基础理论是这样：在插值前先将三个顶点的待插值属性值除以各自的（世界空间的）z值，然后将它们代入到线性插值公式获得某一内点的插值后，再将插值乘以该内点的（世界空间的）z值，即可得到透视校正后的插值，换句话说就是抵消掉了由透视投影变换带来的插值错误。下面是带有透视校正的插值公式：
这里面的W是指上文提到的世界空间的z值。（投影矩阵会将-z放在w上对吧？）
上面方法还有一个小问题，就是上文提到的“该内点的世界空间的z” —— 别忘了只有三个顶点的z是已知量，而任一内点的z也需要通过插值获得。好在对z进行插值不存在透视误差，不需要透视校正。但我们仍然不能直接把三个顶点的z代入上面“无校正版本”的插值公式，因为在NDC空间里（即经过透视除法后）z它根本就不是线性量，不能进行线性插值！幸亏z的倒数是线性的，所以为了插值获得“该内点的世界空间的z”，我们需要将三个顶点的z的倒数代入“无校正版本”的插值公式，得到该内点的z的倒数的插值，然后再倒一次获得该点的世界空间的z值。现在插值公式变成了如下形式：
上面方法还有最后一个需要注意的地方，就是我们**不可以在插值扫描线两端点时就完成全部透视校正！**因为后面的“步进”计算也是线性插值的一部分（正因为是线性插值，才使得我们能以均匀步长来进行步进计算），过早的完成校正会漏掉一部分插值过程没有校正。所以必须在插值得到两端点的两个z的倒数时，对它们也计算“步进”值并进行“步进”计算，直到到达具体某一个内点时，才能最终将z的倒数变成z，然后再将其他插值量乘以z。（或者直接除以z的倒数）
啥？我听见你说“这是什么鬼”？好吧，我表示理解。
##插值“着色器”
在Puresoft3D的三种着色器中，插值“着色器”非常特殊。在前面我已经解释过为什么OpenGL里没有插值“着色器”而Puresoft3D却有，如果需要你可以点过去复习一下。
由于这一特殊性，我想我最好在这里给出更多解释。
插值“着色器”类似于插值运算器的插件，由顶点着色器的开发者来实现。当顶点着色器希望输出一些额外的数据给片元着色器时，这些数据也必须经过插值。因为插值运算器框架不可能理解顶点着色器的“额外数据”到底是什么，所以需要插件来对“额外数据”执行具体的算数运算操作。
正因此，插值“着色器”的工作一般是非常简单而且套路化的。我将继续介绍一下插值“着色器”套路化的工作的细节，但这些对于你来说可能有些过于细节了。如果你正在仔细研读本项目代码，并且被插值“着色器”这一块所困扰，你可以继续读本页（或者直接联系我也行）。如果你只是想随便看看WIKI，那么到这里就可以返回上一页了。
假如你在基于Puresoft3D写自己的一套顶点和片元着色器，你必须自己实现一个配套的插值“着色器”。它必须以PuresoftInterpolationProcessor为基类，然后在派生类里实现下面所罗列的四个函数。
class PuresoftInterpolationProcessor : public PuresoftProcessor
{
public:
……
/*
Puresoft3D 要求顶点着色器将它要向片元着色器输出的“额外数据”打包在一个内存块里（比如在一个结构体里）。
我将在后面称之为“用户数据”。假设你的顶点着色器要输出下面的用户数据：
struct MYDATA
{
vec4 normal;
vec2 texcoord;
};
那么下面的函数interpolateByContributes的参数含义如下：
输入参数vertexUserData的实际类型是(const MYDATA*)[3]，它是当前三角形三个顶点的三份用户数据。输出参数
interpolatedUserData的实际类型是MYDATA*，它是插值后的当前内点的用户数据。当然此时的插值没有最终完成，
因为透视校正的最后一步需要在别的地方做。
一般在interpolateByContributes函数里的套路化运算如下：
const MYDATA* input0 = (const MYDATA*)vertexUserData[0];
const MYDATA* input1 = (const MYDATA*)vertexUserData[1];
const MYDATA* input2 = (const MYDATA*)vertexUserData[2];
MYDATA* output = (MYDATA*)interpolatedUserData;
Output->normal = input0->normal * correctedContributes[0] +
input1->normal * correctedContributes[1] +
input2->normal * correctedContributes[2];
Output->texcoord = input0->texcoord * correctedContributes[0] +
input1->texcoord * correctedContributes[1] +
input2->texcoord * correctedContributes[2];
*/
virtual void interpolateByContributes(void* interpolatedUserData,
const void** vertexUserData,
const float* correctedContributes) const = 0;
/*
框架会调用calcStep函数计算两端点之间插值的步长。（详见前文解释）
一般在calcStep函数里的套路化运算如下：
MYDATA* step = (MYDATA*)interpolatedUserDataStep;
const MYDATA* start = (const MYDATA*)interpolatedUserDataStart;
const MYDATA* end = (const MYDATA*)interpolatedUserDataEnd;
step->normal = (end->normal – start->normal) / stepCount;
step->texcoord = (end->texcoord – start->texcoord) / stepCount;
*/
virtual void calcStep(void* interpolatedUserDataStep,
const void* interpolatedUserDataStart,
const void* interpolatedUserDataEnd, int stepCount) const = 0;
/*
当程序处理某一具体内点时，框架会调用correctInterpolation函数完成透视校正计算。
一般在correctInterpolation函数里的套路化运算如下：
MYDATA* output = (MYDATA*)interpolatedUserData;
const MYDATA* input = (const MYDATA*)interpolatedUserDataStart;
output->normal = input->normal * correctionFactor2;
output->texcoord = input->texcoord * correctionFactor2;
*/
virtual void correctInterpolation(void* interpolatedUserData,
const void* interpolatedUserDataStart,
float correctionFactor2) const = 0;
/*
当程序在一个扫描线内顺序处理内点时，框架会调用stepForward函数来“步进”插值。
一般在stepForward函数里的套路化运算如下：
MYDATA* current = (MYDATA*)interpolatedUserDataStart;
const MYDATA* step = (const MYDATA*)interpolatedUserDataStep;
current->normal += step->normal * stepCount;
current->texcoord += step->texcoord * stepCount;
注意不可以忽略stepCount因为它不总是1
*/
virtual void stepForward(void* interpolatedUserDataStart,
const void* interpolatedUserDataStep,
int stepCount) const = 0;
};