Finding Pixels within UV Coordinates

Question

I am building lightmaps for 3D models. My lightmap algorithm needs to determine which pixels( lumels ) within the lightmap texture fall within the boundary of a mesh face( triangle )...this process takes place for each mesh face...

I was using barycentric coordinate techniques to accomplish this task. It works for the most part...here is code:

bool PixelIsWithinBounds( const D3DXVECTOR2 &t0, 
                            const D3DXVECTOR2 &t1, 
                            const D3DXVECTOR2 &t2,
                            const D3DXVECTOR2 &pUV )
{
    // compute vectors
    D3DXVECTOR2 v0 = t1 - t0, 
        v1 = t2 - t0,
        v2 = pUV - t0;

    // do bounds test for each position
    float f00 = D3DXVec2Dot( &v0, &v0 );
    float f01 = D3DXVec2Dot( &v0, &v1 );
    float f11 = D3DXVec2Dot( &v1, &v1 );

    float f02 = D3DXVec2Dot( &v0, &v2 );
    float f12 = D3DXVec2Dot( &v1, &v2 );

    // Compute barycentric coordinates
    float invDenom = 1 / ( f00 * f11 - f01 * f01 );
    float fU = ( f11 * f02 - f01 * f12 ) * invDenom;
    float fV = ( f00 * f12 - f01 * f02 ) * invDenom;

    // Check if point is in triangle
    if( ( fU >= 0 ) && ( fV >= 0 ) && ( fU + fV <= 1 ) )
        return true;

    return false;
}

This function takes as input 3 UV coordinates( mesh face ) and a pixel UV coordinate. The problem with this method is that if the pixel is only partially covered by the face, the function returns false( because the pixel center does not ly within the triangle ). I could do overlap tests for each point on the triangle...I would like to know if there is a more efficient method...as this process takes place many times per generation of a lightmap...

...any ideas?

here is a screenshot showing the endpoint of a mesh face after lightmap generation...the corner of this face overlaps a pixel surface but doesn't overlap the pixel center...the algorithm left this pixel black( no light )...

EDIT: Shader code to dilate pixels

//--------------------------------------------------------------//
// Dilation Pass
//--------------------------------------------------------------//
PS_INPUT_Quad DilationPass_Vertex_Shader( VS_INPUT_Quad Input )
{
    PS_INPUT_Quad Output = ( PS_INPUT_Quad )0;

    Output.Position = mul( Input.Position, mOrtho );
    Output.UV = Input.UV;
    return Output;
}
float4 DilationPass_Pixel_Shader( PS_INPUT_Quad Input ) : COLOR0
{       
    float4 vC = tex2D( g_SamplerLightMap, Input.UV );
    if( vC.w != 0 )
        return vC;

    int nValidPixels = 0;   
    float4 vFinalColor = 0;
    for( int i = 0; i < 8; ++i )
    {
        float4 vNeighborColor = tex2D( g_SamplerLightMap, Input.UV + TexelKernel[ i ] );
        if( vNeighborColor.w == 0 )
            continue;

        //vFinalColor = ( length( vFinalColor ) > length( vNeighborColor ) ) ? vFinalColor : vNeighborColor;
        vFinalColor += vNeighborColor;
        nValidPixels++;
    }
    return vFinalColor / max( nValidPixels, 1 );
}

Answer 1

First of all, the process of finding the pixels that fall in a triangle is called rasterization. You might want to look up some articles on fast software rasterization, or better yet move the lightmap build process (or at least the rasterization part of it) to the GPU, as it'll be much, much faster.

There are two possible solutions to the problem of cracks in lightmaps. One solution is image-based. After rasterizing the triangles normally, apply a dilation filter using a pixel shader, to fill in the value of undrawn pixels with adjacent drawn ones. (You can use the alpha channel to easily keep track of which pixels were drawn.) Run a couple passes of this and it'll grow a couple-pixels-thick border around each patch in the lightmap.

The other possible solution is conservative rasterization (google it). That means rasterizing all pixels that touch a primitive, instead of just those whose center falls in the primitive. IIRC in a software rasterizer it's a fairly simple modification of the equations; GPU hardware rasterizers don't directly support it, but it can be simulated by expanding each triangle by one pixel (as shown in this article for example). This will have the side effect that previously-watertight adjacent triangles will now overlap, though, which can cause its own set of problems. I'd probably stick with the image-space method.