# Finding Pixels within UV Coordinates

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

Output.Position = mul( Input.Position, mOrtho );
Output.UV = Input.UV;
return Output;
}
{
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 );
}


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.

• i'm trying to implement dilation filter now using pixel shader...If i'm rendering to the lightmap( RT USAGE later saved to file ) how can I access and set adjacent pixels...I was dilating in software but after your suggestion all is done on GPU...Would you mind describing this technique? I've read and understand the concept of dilating an image... Sep 24 '13 at 21:52
• @P.Avery The dilation needs to be done in a separate pass after the lightmap is rendered. For each pixel you gather the neighbors, average the valid ones (excluding undrawn pixels) and output that. It's very similar to doing a Gaussian blur or suchlike. Sep 24 '13 at 22:03
• Sounds like this technique requires a copy of the lightmap...The way I have set it up is that the lightmap is the render target...I can't sample from and render to the lightmap at the same time...Is there a method you'd suggest other than a copy of the lightmap? Sep 24 '13 at 22:07
• @P.Avery You have to render from the lightmap to another render target. So it requires two render targets, yes. That's the case for any kind of image postprocessing. Sep 24 '13 at 22:32
• @P.Avery Make sure you're excluding undrawn pixels from the average correctly. Only average over the number of drawn pixels you actually found when you samples the neighbors. If you look at the lightmap, the drawn pixels should grow outward and fill up the seams without getting darker or brighter. Sep 25 '13 at 0:38