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 ?


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.

plane through 3D points that project onto a 2D screen

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 [XA, YA, ZA, WA] coordinates. After projection it will have coordinates [xA, yA] = [XA/WA, YA/WA] and the value ZA/WA 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 = [XA, YA, WA] and B = [XB, YB, WB].

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.

| improve this answer | |
  • $\begingroup$ also somewhat obvious, but still: any point on the AB edge will project onto the ab edge, and any point in the plane will project onto the line $\endgroup$ – elena Dec 30 '18 at 23:38
  • $\begingroup$ Hi Elena, Thanks a lot!. Your explanation really clear up some of my confusion. But I still don't fully don't understand the algorithm yet. Is there any relation between the plane's normal with the projected line's normal. I have updated my question to reflect this additional confusion. Please have a look at it. $\endgroup$ – kevinyu Dec 31 '18 at 2:48
  • $\begingroup$ Okay, now I can see that the plane normal is the line normal as well. But I am still confused as how we can substract the w component of the normal to get the outer triangle. $\endgroup$ – kevinyu Dec 31 '18 at 10:42
  • 1
    $\begingroup$ @kevinyu When moving of the plane happens, you already operate in the window space, as far as I understand. (a, b) · x + c = 0 is the general form of line equation in 2D, a b and c are just coefficients and x is a 2D point [x, y]. [a, b] is its normal, and c is the distance from [0, 0, 0] to the plane along the normal. Maybe take a line like 2x + y + 1 = 0. Draw a vector [2 cm, 1 cm], move along it from the center 1 cm and draw a perpendicular to it. And then try some points from that line, they will all satisfy the equation. So if you add more to the c - you'll move the line further. $\endgroup$ – elena Jan 3 '19 at 0:43
  • 1
    $\begingroup$ So you take .xy component of the plane to get the normal of the line. ( it is a bit incorrect to say that the normal of the plane is the normal of the line btw. It's rather the projection of the plane normal is the line normal). now your .xy is exactly the [a, b], the normal of the line, and you need to move along the normal hPixel times. $\endgroup$ – elena Jan 3 '19 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.