Rasterization Rules and States

Question

This thread directly concerns lightmap generation; however, indirectly, the rasterization of polygons by the GPU.

I am currently generating lightmaps using a pixel shader. To the shader I send 3 lightmap UV coordinates per mesh face. Those UV coordinates are directly rendered onto a lightmap texture( by setting the lightmap as the render target ). The vertex shader looks like this:

// ---------------------------------------------------------------
// Vertex Declaration
// ---------------------------------------------------------------
struct VS_INPUT_Std
{
    float4 Position : POSITION0;
    float3 Normal : NORMAL0;
    float2 tUV : TEXCOORD0; // diffuse UV coordinates
    float2 lUV : TEXCOORD1; // lightmap UV coordinates
};
//--------------------------------------------------------------//
// LightMap Pass
//--------------------------------------------------------------//
PS_INPUT_Std LightMapPass_Vertex_Shader( VS_INPUT_Std Input )
{
    PS_INPUT_Std Output = ( PS_INPUT_Std )0;

    Output.Position = float4( ( Input.lUV.x * 2 ) - 1, ( Input.lUV.y * -2 ) + 1, 0, 1 );
    Output.Normal = mul( Input.Normal, mW );
    Output.Pos3 = mul( Input.Position, mW );
    Output.tUV = Input.tUV;
    Output.lUV = Input.lUV;
    return Output;
}

The pixel shader returns a color based on light contribution. The result of the lightmap generation for this test mesh looks like this:

The light for this scene is floating in the center of the room...

The problem is that the lightmap has 'cracks' due to the rasterization of polygons by the GPU. It appears as though that for a given face lightmap pixels are not included during rasterization because their pixel centers do not fall within the bounds of the face's UV coordinates despite the fact that the face overlaps those pixels. As a result a black( unset ) pixel is rendered and effectively blackens the diffuse color of the mesh during texture modulation. Here is a screenshot:

Here is a screenshot of an auxiliary window which shows both the lightmap and a selected mesh face. This is generated by rendering the UV coordinates of the mesh face over a screen quad of the lightmap:

As you can see, the mesh face( green ) extends beyond the pixels rendered during generation of the lightmap. It seems as though those pixels were excluded during rasterization. Most of the problem faces are narrow in dimension. I thought that I could fix this by increasing the size of the lightmap, however, this doesn't always work...

Here is the entire lightmap:

Can I change a rasterization state to allow pixels under certain conditions?

EDIT: Lightmap and Deferred Shading Cube Pics

Answer 1

The lightmap shouldnt be dissasociated from the vertex information.

if the vertices are lined up to display no cracks and no rounding errors coming from the CPU (i.e. object positions + vertex positions interpolation) they they won't let anything through, the edges have to be aligned and no triangle intersections.

If the mesh doesnt have cracks, nothing will.

Answer 2

Conservative rasterization is a fix for this problem. Thanks to Nathan Reed's comments, in preparation for the generation of a lightmap, I dilate the uv coordinates and recalculate they're associated positions based on the dilation.

For each triangle:

1. Compose an array of edges in uv space.

2. For each edge:

   a. Compute the cross product using the edge direction vector and a point that lies on the edge. The resulting vector is the edge's normal(It should face away from the triangle, perpendicular to the edge direction vector)

   b. Compute the edge center position in uv space.

   c. Translate the edge center position along the edge normal by a distance of a half pixel(or desired dilation amount in uv space...it should definitely be a value between 0 and 1).

3. After all edges have been translated, calculate the intersection points between each edge to determine the new uv coordinates for the triangle.

4. Adjust the triangle's position data. Each position should be dilated as well.
5. The dilation of triangles with acute angles may cause too great a change in the uv coordinates. You should calculate an axis-aligned bounding box for the original triangle in uv space. Then dilate the AABB by the same amount as the triangle. When computing the lightmaps just make sure that the uv coordinates lie within the AABB, if not then discard the pixel.

Here is code in c++:

struct VertexData
{
D3DXVECTOR3 position;
D3DXVECTOR3 normal;
D3DXVECTOR2 uv;
};

struct MeshData
{
// vertex data
VertexData* vertices;

// index data
int* indices;

// attribute data
int* attributes;

// face count
int ncFaces;
};

// mesh data contains vertex data, index data, face count...
MeshData* pMeshData = GetMeshData();

// face count
int ncFaces = data.ncFaces

// dilation amount for my use is a half-pixel
D3DXVECTOR2 vHalfPixel( 0.5f / ( float )LightMapWidth, 0.5f / ( float )LightMapHeight );

for(int iFace = 0; iFace < 3 * ncFaces; iFace += 3)
{

// edge uv coordinates
D3DXVECTOR3 vUV[3];

// edge normals in uv space
D3DXVECTOR3 vEdgeNormal[3];

// edge center positions in uv space
D3DXVECTOR3 vEdgeCenter[3];

// distance of edge normal from origin
float fD[3]; 

// axis-aligned bounding box in uv space
D3DXVECTOR4 vAABB;

// vertices for the current triangle(face)
VertexData vertices[]
{
pMeshData->vertices[pMeshData->indices[iFace + 0]],
pMeshData->vertices[pMeshData->indices[iFace + 1]],
pMeshData->vertices[pMeshData->indices[iFace + 2]],
}

// store original vertex data
VertexData originalVertices[3];
memcpy(originalVertices, vertices, 3 * sizeof(VertexData));

// place each uv coordinate in a 3 component vector for cross product calculation
memset( vUV, 1, 3 * sizeof( D3DXVECTOR3) );
memcpy( &vUV[ 0 ], &vertices[ 0 ].uv, sizeof( D3DXVECTOR2 ) );
memcpy( &vUV[ 1 ], &vertices[ 1 ].uv, sizeof( D3DXVECTOR2 ) );
memcpy( &vUV[ 2 ], &vertices[ 2 ].uv, sizeof( D3DXVECTOR2 ) );

// compute edge direction vectors
D3DXVec3Normalize( &vEdgeNormal[ 0 ], &( vUV[ 1 ] - vUV[ 0 ] ) );
D3DXVec3Normalize( &vEdgeNormal[ 1 ], &( vUV[ 2 ] - vUV[ 1 ] ) );
D3DXVec3Normalize( &vEdgeNormal[ 2 ], &( vUV[ 0 ] - vUV[ 2 ] ) );

// dilate each of the 3 edges that make up the triangle
for( UINT j = 0; j < 3; ++j )
{
// compute edge normal( perpendicular to edge )
D3DXVec3Cross( &vEdgeNormal[ j ], &vEdgeNormal[ j ], &vUV[ j ] );

// set z component to 0( we're only interested in 2D vectors )
vEdgeNormal[ j ].z = 0;

// normalize edge normal
D3DXVec3Normalize( &vEdgeNormal[ j ], &vEdgeNormal[ j ] );

// compute distance from origin
fD[ j ] = -D3DXVec3Dot( &vEdgeNormal[ j ], &vUV[ j ] );

// get edge center point
vEdgeCenter[ j ] = fD[ j ] * vEdgeNormal[ j ];

// translate edge center
vEdgeCenter[ j ].x += vEdgeNormal.x * vHalfPixel.x;
vEdgeCenter[ j ].y += vEdgeNormal.y * vHalfPixel.y;

// calc new dist from origin
fD[ j ] = -D3DXVec3Dot( &( -vEdgeNormal[ j ] ), &vEdgeCenter[ j ] );

// compose plane
vEdgeNormal[ j ] = D3DXVECTOR3( vEdgeNormal[ j ].x, vEdgeNormal[ j ].y, fD[ j ] );
}

// compute intersection points
D3DXVec3Cross( &vUV[ 0 ], &vEdgeNormal[ 2 ], &vEdgeNormal[ 0 ] );
vertices[ 0 ].vUV = *( D3DXVECTOR2* )&vUV[ 0 ] / vUV[ 0 ].z;

D3DXVec3Cross( &vUV[ 1 ], &vEdgeNormal[ 0 ], &vEdgeNormal[ 1 ] );
vertices[ 1 ].vUV = *( D3DXVECTOR2* )&vUV[ 1 ] / vUV[ 1 ].z;

D3DXVec3Cross( &vUV[ 2 ], &vEdgeNormal[ 1 ], &vEdgeNormal[ 2 ] );
vertices[ 2 ].vUV = *( D3DXVECTOR2* )&vUV[ 2 ] / vUV[ 2 ].z;

// adjust vertex position to account for uv offset
for( UINT j = 0; j < 3; ++j )
vertices[ j ].position = UVPOS( originalVertices[ 0 ]->position, originalVertices[ 1 ]->position, originalVertices[ 2 ]->position, originalVertices[ 0 ]->uv, originalVertices[ 1 ]->uv, originalVertices[ 2 ]->uv, *( D3DXVECTOR2* )&vertices[ j ].vUV );

// initialize aabb
vAABB.x = vertices[ 0 ]->uv.x;
vAABB.y = vertices[ 0 ]->uv.y;
vAABB.z = vertices[ 0 ]->uv.x;
vAABB.w = vertices[ 0 ]->uv.y;

// determine aabb
for( UINT j = 1; j < 3; ++j )
{
vAABB.x = min( vAABB.x, vertices[ j ]->uv.x );
vAABB.y = min( vAABB.y, vertices[ j ]->uv.y );
vAABB.z = max( vAABB.z, vertices[ j ]->uv.x );
vAABB.w = max( vAABB.w, vertices[ j ]->uv.y );
}

// adjust aabb by dilation amount
vAABB.x -= vHalfPixel.x;
vAABB.y -= vHalfPixel.y;
vAABB.z += vHalfPixel.x;
vAABB.w += vHalfPixel.y;

// clamp AABB
vAABB.x = Clamp( vAABB.x, 0.0f, 1.0f );
vAABB.y = Clamp( vAABB.y, 0.0f, 1.0f );
vAABB.z = Clamp( vAABB.z, 0.0f, 1.0f );
vAABB.w = Clamp( vAABB.w, 0.0f, 1.0f );
}

// This method takes as input:
// Triangle position data
// Triangle uv coordinates
// and a test uv coordinate(tx)
// The position data and uv coordinates are used to determine the position of the test uv coordinate with respect to the triangle
// the calculations in this method were found online a number of years ago and I can't right now reference the source...my apologies
D3DXVECTOR3 UVPOS( const D3DXVECTOR3 &v1, // tri position 1
                          const D3DXVECTOR3 &v2, // tri position 2
                          const D3DXVECTOR3 &v3, // tri position 3
                          const D3DXVECTOR2 &t1, // tri uv 1
                          const D3DXVECTOR2 &t2, // tri uv 2
                          const D3DXVECTOR2 &t3, // tri uv 3
                          const D3DXVECTOR2 &tx ) // test uv coordinate
{
    float i;
    float s;
    float t;
    D3DXVECTOR3 r;
    i = 1 / ( ( t2.x - t1.x ) * ( t3.y - t1.y ) - ( t2.y - t1.y ) * ( t3.x - t1.x ) );
    s = i * ( ( t3.y - t1.y ) * ( tx.x - t1.x ) - ( t3.x - t1.x ) * ( tx.y - t1.y ) );
    t = i * ( -( t2.y - t1.y ) * ( tx.x - t1.x ) + ( t2.x - t1.x ) * ( tx.y - t1.y ) );
    r.x = v1.x + s * ( v2.x - v1.x ) + t * ( v3.x - v1.x );
    r.y = v1.y + s * ( v2.y - v1.y ) + t * ( v3.y - v1.y );
    r.z = v1.z + s * ( v2.z - v1.z ) + t * ( v3.z - v1.z );
    return r;
}