A game programmer, interested in graphics programming.
Posts by Simon Yeung
  1. Implementing Voxel Cone Tracing ( Counting comments... )
  2. Angle based SSAO ( Counting comments... )
  3. Shader Generator ( Counting comments... )
  4. Photon Mapping Part 2 ( Counting comments... )
  5. Photon Mapping Part 1 ( Counting comments... )
  6. Software Rasterizer Part 2 ( Counting comments... )
  7. Software Rasterizer Part 1 ( Counting comments... )
  8. Light Pre Pass Renderer on iPhone ( Counting comments... )
  9. Extracting dominant light from Spherical Harmonics ( Counting comments... )
  10. Inverse Kinematics (2 joints) for foot placement ( Counting comments... )
  11. Writing an iPhone Game Engine (Part 7- Postmortem) ( Counting comments... )
  12. Microfacet BRDF ( Counting comments... )
  13. Spherical Harmonic Lighting ( Counting comments... )
  14. Dual Quaternion ( Counting comments... )
  15. Dual Number ( Counting comments... )
  16. Using PID Controller ( Counting comments... )
  17. Writing an iPhone Game Engine (Part 6- Performance) ( Counting comments... )
  18. Writing an iPhone Game Engine (Part 5- Audio) ( Counting comments... )
  19. Writing an iPhone Game Engine (Part 4- Streaming) ( Counting comments... )
  20. Writing an iPhone Game Engine (Part 3- Scripting) ( Counting comments... )
  21. Writing an iPhone Game Engine (Part 2- Maya Tools) ( Counting comments... )
  22. Writing an iPhone Game Engine (Part 1- Memory management) ( Counting comments... )
  23. Writing an iPhone Game Engine (Part 0 - Introduction) ( Counting comments... )
  24. SSAO using Line Integrals ( Counting comments... )
Technology/ Code / Visual Arts /

Introduction

Continue with the previous post, after filling the triangle with scan line or half-space algorithm, we also need to interpolate the vertex attributes across the triangle so that we can have texture coordinates or depth on every pixel. However we cannot directly interpolate those attributes in screen space because projection transform after perspective division is not an affine transformation (i.e. after transformation, the mid-point of the line segment is no longer the mid-point), this will result in some distortion and this artifact is even more noticeable when the triangle is large:

interpolate in screen space
perspective correct interpolation

Condition for linear interpolation

When interpolating the attributes in a linear way, we are saying that given a set of vertices, vi (where i is any integer>=0) with a set of attributes ai (such as texture coordinates), we have a function mapping a vertex to the corresponding attributes, i.e.

f(vi)= ai

Say, to interpolate a vertex inside a triangle in a linear way, the function f need to have the following properties:

f(t0 *v0 + t1 *v1 + t2 *v2 ) = t0 * f(v0) + t1 * f(v1) + t2 * f(v2)
, for any t0t1t2 where t0 t1 t2=1

which means that we can calculate the interpolated attributes using the same weight ti used for interpolating vertex position. For functions having the above properties, those functions will be an affine function with the following form:

f(x)= Ax + b
, where A is a matrix, x and b are vector

Depth interpolation

When a vertex is projected from view space to normalized device coordinates(NDC), we will have the following relation (ratio of the triangles) between the view space and NDC space:

substitute equation 1 and 2 into the plane equation of the triangle lies on:

 

So, 1/zview is an affine function of xndc and yndc which can be interpolated linearly across the screen space (the transform from NDC space to screen space is a linear transform).

Attributes interpolation

In last section, we know how to interpolate the depth of a pixel linearly in screen space, the next problem is to interpolate the vertex attributes(e.g. texture coordinates). In view space, we know that those attributes can be interpolated linearly, so those attributes can be calculated by an affine function with the vertex position as parameters e.g.

Similar to interpolate depth, substitute equation 1 and 2 into the above equation:

Therefore, u/zview is an another affine function of xndc and yndc which can be interpolated linearly across the screen space. Hence we can interpolating u linearly by first interpolate 1/zview and u/zview across screen space, and then divide them per pixel.

The last problem...

Now, we know that we can interpolate the view space depth and vertex attributes linearly across screen space. But during the rasterization state, we only have vertices in homogenous coordinates (vertices are transformed by the projection matrix already), how can we get the zview to do the perspective correct interpolation?

Consider the projection matrix (I use D3D one, but the same for openGL):

After transforming the vertex position, the w-coordinate will be the view space depth!

i.e. w-homogenous = zview 

And look at the matrix again and consider the transformed z-coordinates, it will in a form of:

After transforming to the NDC,

So the depth value can be directly interpolated using z-NDC  for depth test.

Demo

A javascript demo to rasterize the triangles can be viewed here(although not optimized...). And the source code can be downloaded here.

Screen shot of the demo

Conclusion
In this post, the steps to linear interpolate the vertex in screen space is described. And for rasterizing the depth buffer only (e.g. for occlusion), the depth value can be linearly interpolated directly with the z coordinate in NDC space which is even simpler.

References
[1] http://www.lysator.liu.se/~mikaelk/doc/perspectivetexture/
[2] http://www.gamedev.net/topic/581732-perspective-correct-depth-interpolation/
[3] http://chrishecker.com/Miscellaneous_Technical_Articles
[4] http://en.wikipedia.org/wiki/Affine_transformation