<p>I'm not sure what exactly you mean by </p>

<blockquote>
  <p>how to visualize a plane that use w value as one of this coordinates</p>
</blockquote>

<p>but here's a sketch that will, hopefully, clarify this sentence:</p>

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

<p>I've used uppercase letters for clip-space, and lowercase letters for window space.</p>

<p><a href="https://i.sstatic.net/SHOvp.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/SHOvp.png" alt="plane through 3D points that project onto a 2D screen"></a></p>

<p>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<sub>A</sub>, Y<sub>A</sub>, Z<sub>A</sub>, W<sub>A</sub>] coordinates. After projection it will have coordinates [x<sub>A</sub>, y<sub>A</sub>] = [X<sub>A</sub>/W<sub>A</sub>, Y<sub>A</sub>/W<sub>A</sub>] and the value Z<sub>A</sub>/W<sub>A</sub> 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.</p>

<p>Now we have point A = [X<sub>A</sub>, Y<sub>A</sub>, W<sub>A</sub>] and B = [X<sub>B</sub>, Y<sub>B</sub>, W<sub>B</sub>].</p>

<p>The projected point <strong>a</strong> will lie on the line that connects [0, 0, 0] and A.
Point <strong>b</strong> 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 <a href="https://en.wikipedia.org/wiki/Normal_(geometry)" rel="nofollow noreferrer">here</a> and <a href="https://en.wikipedia.org/wiki/Cross_product" rel="nofollow noreferrer">here</a>.</p>

<p>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 <strong>ab</strong> (and vice versa).</p>

<p>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.</p>

<p>I hope I cleared it up for you a bit.</p>

CC BY-SA 4.0
2018-12-30T23:38:54.260Z
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
elena
CC BY-SA 4.0
2018-12-31T02:48:23.607Z
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.
kevinyu
CC BY-SA 4.0
2018-12-31T10:42:08.563Z
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.
kevinyu
CC BY-SA 4.0
2019-01-03T00:43:27.103Z
@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.
elena
CC BY-SA 4.0
2019-01-03T00:44:28.683Z
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.
elena
CC BY-SA 4.0
2018-12-30T22:44:41.340Z
2018-12-30T23:45:28.957Z
2018-12-30T23:45:28.957Z
elena
<p>I am trying to implement conservative voxelization as part of real time GI in my hobby rendering engine. I find this <a href="https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter42.html" rel="nofollow noreferrer">article</a> 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</p>

<blockquote>
  <p>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</p>
  
  <p>ax c + by c + cw c = 0  a(xw c ) + b (yw c ) + cw c ) + cw c = 0  ax +
  by + c = 0</p>
  
  <p>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.</p>
</blockquote>

<p>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</p>

<pre><code>// 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);
</code></pre>

<p>Again, I still don't understand why this is true. </p>

<p>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.</p>

<pre><code>// 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]);
</code></pre>

<p>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)</p>

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

<global-illumination><rasterizer><voxelization>
Comprehensive explanation of conservative rasterization algorithm
kevinyu
# Comprehensive explanation of conservative rasterization algorithm

(Asked by: username_0 on 2018-12-30)

I am trying to implement conservative voxelization as part of real time GI in my hobby rendering engine. I find this [article](https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter42.html) 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 ?

**Tags:** global-illumination, rasterizer, voxelization


---

## 1 answers

### Answer by username_1 on 2018-12-30. Score: 5 | Accepted answer

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](https://i.sstatic.net/SHOvp.png)](https://i.sstatic.net/SHOvp.png)

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](https://en.wikipedia.org/wiki/Normal_(geometry)) and [here](https://en.wikipedia.org/wiki/Cross_product).

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.

> **Comments:**
> **username_1**: 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  
> **username_0**: Hi username_1, 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.  
> **username_0**: 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.  
> **username_1**: @username_0 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.  
> **username_1**: 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.  

---

