interpolation
###INTERPOLATION
Interpolation includes two major points: fundamental interpolation method, and perspective correction.
###THE FUNDAMENTAL METHOD
Given a triangle abc, and its inner point p, as the below picture shows.
For any one of p’s attributes that can be linearly interpolated from related attribute of a, b, and c, we can define their linear relationship as below.
Where P, P_a, P_b, and P_c are interpolate-able attributes of the 4 points. C_a and C_b are contributes of vertex a and b.
Because coordinate is a typical interpolate-able attribute, and we know their coordinates, we can substitute their coordinates into the above equation and figure out the three vertices’ contribute values.
Resolve the above equation system and we can find C_a, C_b. After that, for any interpolate-able attributes, we can easily find its value. Generally, the three contributes can be found by the following way.
=>
=>
But in fact, neither do we have to resolve the equation system, nor do we have to calculate the reversed matrix, because we do not want to do interpolation in this way --- it is not fast enough! Do not forget that, if we interpolate in this way, we not only have to calculate (C_a C_b C_c) for every inner point p, we also have to calculate P= (C_a C_b C_c) dot (P_a P_b P_c) for every attribute! That would be a great deal of computation.
Hence we will do interpolation by the following simplified way.
- For each scanline that a triangle covers (remember we get the scanlines through rasterisation), we interpolate for the attributes only for the 1st and last points of the scanline. See the following picture.
It can be proved that, for points on edges of a triangle, the vertex that is not on the same edge contributes nothing to the point. For example, on the above picture, the vertex c does not contribute to the left end of the scanline in back colour, only a and b are related to it. The situation is the same for the other end. Knowing this fact, we can simply the contribute calculation to the following form:
=>
The following code snippet represents the above simplified calculation.
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;
}-
After interpolated for the two ends of a scanline, we calculate the ‘interpolation step’ for every attribute. attributeStep = (attributeRight – attributeLeft) / scanlineLength;
-
Then, start from the left end point, every point next to the previous point on the scanline can be interpolated by adding the step value.
attribute = attributeLeft;
for(point = leftEnd; point <= rightEnd; point++)
{
process(point, attribute);
attribute += attributeStep;
}
In this way, we can interpolate for every fragment with minimum cost.
###PERSPECTIVE CORRECTION
The world could have been a wonderful place if the above were all we need to care, but the truth is we have to take the effect that perspective projection makes to the contribute calculation. In other word, we have to do perspective correction to every interpolated value.
Well… I have to admit that the proving procedure for the method of perspective correction is a bit painful. I will skip it and directly give my approach here.
The base theory of perspective correction is that we divide the attribute of each vertex by its z value (in world space), then put them into the linear interpolation equation. After we get result, we multiply it by the point’s interpolated z (in world space). See the following modified equation:
Where W_a, W_b, and W_c are the z value of the triangle’s three vertices in world space, and W is the interpolated z value of the inner point being interpolated. Here we use W to denote the z values in world space is to avoid confusion with the z values in screen space. Remember that? After projection transformation, the W component is the -Z.
One last thing we have to notice is that actually we only have the W_(a,b,c) values of the triangle’s vertices, but we do not have the W in the above equation --- we also have to interpolate it. However, unfortunately, we cannot directly interpolate the W value as it is not linear at all, we have to interpolate reciprocal W! For the two ends of a scanline, we will do the following interpolation.
After that, when we do interpolation for every fragment by adding step value to the attributes of the previous fragment, we must complete the perspective correction by multiply the W_end.
What? I hear you said ‘WTF’...? Alright, surely I understand you.
###INTERPOLATION PROCESSOR
Interpolation processor is something special among the three types of processor programme. I have explained why Puresoft3D has it but OpenGL does not. Click this link to review it if necessary.
Due to its particularity, I guess it is necessary to explain more about it here.
Interpolation processor is like the interpolator’s plug-in module written by the processor’s developer. When a vertex processor wants to output something more than vertex position to a fragment processor, the extra output has to be interpolated too. Because, in a vertex processor’s output, the interpolator framework can only understand the vertex position data --- it knows it must be there, and it must be 4 floats, the framework needs a plug-in to do actual calculation to part of the vertex processor’s output which is not understandable by the framework.
Therefore, the interpolation processor is usually simple and routine. I will go on to introduce an interpolation processor’s routine job here. If you are reading the project’s source code and confused by it, or if you are interested in writing your own graphics programme based on this project, you may want to read this introduction. Otherwise if you are just skimming the pages, you can surely skip this section because it is too detailed to you.
Suppose you are writing your own vertex and fragment processers. You must also write an interpolation processor which must inherit from the interface class PuresoftInterpolationProcessor, and in the child class you must implement 4 functions which are listed and briefly described in the below code snippet.
class PuresoftInterpolationProcessor : public PuresoftProcessor
{
public:
……
/*
Puresoft3D requires vertex processor programme to pack its extra output in one block of
memory (i.e., in a structure). I will call it ‘user data’ in the following paragraph.
Suppose a vertex processor outputs the following user data:
struct MYDATA
{
vec4 normal;
vec2 texcoord;
};
The input parameter vertexUserData will be (const MYDATA*) [3]. It is the user data blocks
of the three vertices of the current triangle. The output parameter interpolatedUserData
will be MYDATA*. It is the ‘half-interpolated’ user data. The interpolation processor should
do the following calculation.
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;
/*
The framework will call this function to calculate ‘step’ user data block. The interpolation
processor should do the following calculation.
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;
/*
The framework will call this function to complete interpolation for user data block.
The interpolation processor should do the following calculation.
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;
/*
The framework will call this function to accumulate the step user data block to the current
user data block. The interpolation processor should do the following calculation.
MYDATA* current = (MYDATA*)interpolatedUserDataStart;
const MYDATA* step = (const MYDATA*)interpolatedUserDataStep;
current->normal += step->normal * stepCount;
current->texcoord += step->texcoord * stepCount;
*/
virtual void stepForward(void* interpolatedUserDataStart,
const void* interpolatedUserDataStep,
int stepCount) const = 0;
};