Comprehensive explanation of conservative rasterization algorithm

Question

I am trying to implement conservative voxelization as part of real time GI in my hobby rendering engine. I find this article by NVIDIA. I am stuck at understanding the second algorithm. The problem that I have is that I don't understand this section of the article

We describe both algorithms in window space, for clarity, but in practice it is impossible to work in window space, because the vertex program is executed before the clipping and perspective projection. Fortunately, our reasoning maps very simply to clip space. For the moment, let us ignore the z component of the vertices (which is used only to interpolate a depth-buffer value). Doing so allows us to describe a line through each edge of the input triangle as a plane in homogeneous (x c , y c , w c )-space. The plane is defined by the two vertices on the edge of the input triangle, as well as the position of the viewer, which is the origin, (0, 0, 0). Because all of the planes pass through the origin, we get plane equations of the form

ax c + by c + cw c = 0 a(xw c ) + b (yw c ) + cw c ) + cw c = 0 ax + by + c = 0

The planes are equivalent to lines in two dimensions. In many of our computations, we use the normal of an edge, which is defined by (a, b) from the plane equation.

First, I don't understand how to visualize a plane that use w value as one of this coordinates and what is the meaning of this plane. And then later in the article, they calculate this plane by doing a cross product like this

// Compute equations of the planes through the two edges

float3 plane[2];

plane[0] = cross(currentPos.xyw - prevPos.xyw, prevPos.xyw);

plane[1] = cross(nextPos.xyw - currentPos.xyw, currentPos.xyw);

Again, I still don't understand why this is true.

Is there any relation between the plane normal with the line normal because in the next part, the algorithm use this normal xy value to move the line outwards by substracting the z value of this plane.

// Move the planes by the appropriate semidiagonal

plane[0].z -= dot(hPixel.xy, abs(plane[0].xy));

plane[1].z -= dot(hPixel.xy, abs(plane[1].xy));





// Compute the intersection point of the planes.

float4 finalPos;

finalPos.xyw = cross(plane[0], plane[1]);

I can understand it if the xy component of the plane's normal is actually the normal of the line as well and the z value of the plane's normal represent the line distance from point (0, 0)

Can someone please explain in more detail or provide me some visualization of this algorithm ?

Answer 1

I'm not sure what exactly you mean by

how to visualize a plane that use w value as one of this coordinates

but here's a sketch that will, hopefully, clarify this sentence:

a line through each edge of the input triangle as a plane in homogeneous (x c , y c , w c )-space

I've used uppercase letters for clip-space, and lowercase letters for window space.

Let's say AB is an edge of your original triangle. It projects to an edge ab in window coordinates. Point A is defined using [X_A, Y_A, Z_A, W_A] coordinates. After projection it will have coordinates [x_A, y_A] = [X_A/W_A, Y_A/W_A] and the value Z_A/W_A will be used to determine which object is closer to the camera at this point. So your [X, Y, Z, W] always turns into a [X/W, Y/W] in the end. You can see that Z doesn't play any role in where the point is going to end up on the screen. So we just throw it away for now and interpret the remaining [X, Y, W] as 3D coordinates of the points.

Now we have point A = [X_A, Y_A, W_A] and B = [X_B, Y_B, W_B].

The projected point a will lie on the line that connects [0, 0, 0] and A. Point b will lie on the line [0, 0, 0] and B. Three points define a plane, and a normal to the plane defined by 3 points can be found as a cross product of two vectors in this plane (OA and OB, for example). "For a convex polygon (such as a triangle), a surface normal can be calculated as the vector cross product of two (non-parallel) edges of the polygon." More on why in Wikipedia here and here.

Generally this moves your problem from 2D domain in the projected coordinates into a 3D domain of not-yet-projected points. The 2D and 3D are "dual" to each other. For example, if a point lies in the plane of OAB, it for sure lies on the line through ab (and vice versa).

The thing you need to remember is that W is your 3'rd coordinate, not Z! I know, it's very counter-intuitive, but it is what it is, Z only carries depth information, it does not affect position of objects on the screen.

I hope I cleared it up for you a bit.