[In this reprinted #altdevblogaday in-depth piece, game programmer Simon Yeung looks at using software rasterizers for occlusion culling, and xplains the math behind the clipping of triangles.] Software rasterizers can be used for occlusion culling. Some games such as Killzone 3 use this to cull objects. So I decided to write one myself. The steps are first to transform vertices to homogenous coordinates, clip the triangles to the viewport, and then fill the triangles with interpolated parameters. Note that the clipping process should be done in homogenous coordinates before the perspective division, otherwise lots of the extra work is needed to clip the triangles properly. This post will explain why clipping should be done before the perspective division. Points in homogenous coordinates In our usual Cartesian Coordinate system, we can represent any points in 3D space in the form of (X, Y, Z). While in Homogenous coordinates, a redundant component w is added, which results in a form of (x, y, z, w). Multiplying any constant (except zero) to that 4-components vector still represents the same point in homogenous coordinates. To convert a homogenous point back to our usual Cartesian Coordinate, we would multiply a point in homogenous coordinates so that the w component is equals to one:
(x, y, z, w) -> (x/w , y/w , z/w, 1) -> (X, Y, Z)
In the following figure, we consider the x-w plane, a point (x, y, z, w) is transformed back to the usual Cartesian Coordinates (X, Y, Z) by projecting onto the w=1 plane:
figure 1. projecting point to w=1 plane |
The interesting point comes when the w component is equal to zero. Imagine the w component is getting smaller and smaller, approaching zero. The coordinates of point (x/w , y/w , z/w, 1) will getting larger and larger. When w is equal to zero, we can represent a point at infinity. Line Segments in Homogenous coordinates In Homogenous coordinates, we still can represent a line segment between two points P0= (x0, y0, z0, w0) and P1= (x1, y1, z1, w1) in parametric form:
L= P0 + t * (P1-P0), where t is within [0, 1]
Then we can get a line having the shape:
figure 2. internal line segment |
The projected line on w=1 is called internal line segment in the above case. But what if the coordinates of P0 and P1 having the coordinates where w0 < 0 and w1 > 0 ?
figure 3. external line segment |
In this case, it will result in the above figure, forming an external line segment. It is because the homogenous line segment has the form L= P0 + t * (P1-P0), when moving the parameter from t=0 to t= 1, since w0 < 0 and w1 > 0, there exists a point on the homogenous line where w=0. This point is at infinity when projected to the w=1 plane, where the projected line segment joining P0 and P1 passes through the point at infinity, forming an external line segment. The figure below shows how points are transformed before and after perspective projection and divided by w:
figure 4. region mapping |
The blue line shows the viewing frustum, nothing unusual for the region in front of the eye. The unusual things are the points behind the eye. After perspective transformation and projected to w=1 plane, those points are transformed in front of the eye too. So for line segment with one point in front of the eye and the other behind the eye, it would be transformed to the external line segment after the perspective division. Triangles in Homogenous coordinates In the last section, we know that there are internal and external line segments after the perspective division.Wwe also have internal and external triangles. The internal triangles are the one that we usually sees. The external triangles must be formed by 1 internal line segment and 2 external line segments:
figure 5. external triangle |
In the above figure, the shaded area represents the external triangle formed by the points P0, P1 and P2. These kind of external triangles may appear after the perspective projection transform. And this happens in our real world too:
In the left photo, it shows an external triangle with one of the triangle vertex far behind the camera, while the right photo shows the full view of the triangle, and the cross marks the position of the camera where the left photo is taken. Triangles clipping To avoid the case of external triangles, lines/triangles should be clipped in homogenous coordinates before being divided by the w-component. The homogenous point (x, y, z, w) will be tested with the following inequalities:
(-w <= x <= w) && —— inequality. 1
(-w <= y <= w) && —— inequality. 2
(-w <= z <= w ) && —— inequality. 3 w > 0 —— inequality. 4
(The z clipping plane inequality is 0 <= z <= w in the case for D3D, it depends on how the normalized device coordinates are defined.) Clipping by inequality 1,2,3 will effectively clip all points that with w < 0 because if w < 0, say w = -3:
No tags.
