Rasterizing 2d Triangle

Due to some texture optimization requirement i need to have a raster (size of the texture) and need to know exactly which pixels are used for the texture mapping of the mesh. So I have a boolean raster and just want to draw all the triangles (using their uv coordinates) to this raster. This is what I got so far:

``````    public void fillTriangleHalfSpace(boolean[][] raster, Vector2f v0, Vector2f v1, Vector2f v2) {
Vector2f l_v0 = new Vector2f((float) _width * v0.x, (float) _height * v0.y);
Vector2f l_v1 = new Vector2f((float) _width * v1.x, (float) _height * v1.y);
Vector2f l_v2 = new Vector2f((float) _width * v2.x, (float) _height * v2.y);

// Compute triangle bounding box
int minX = min(l_v0.x, l_v1.x, l_v2.x);
int minY = min(l_v0.y, l_v1.y, l_v2.y);
int maxX = max(l_v0.x, l_v1.x, l_v2.x);
int maxY = max(l_v0.y, l_v1.y, l_v2.y);

// Clip against screen bounds
minX = Math.max(minX, 0);
minY = Math.max(minY, 0);

// Rasterize
Vector2f p = Vector2f.ZERO.clone();
for (p.y = minY; p.y <= maxY; p.y++) {
for (p.x = minX; p.x <= maxX; p.x++) {
int bias0 = isTopLeft(l_v1, l_v2) ? 0 : -1;
int bias1 = isTopLeft(l_v2, l_v0) ? 0 : -1;
int bias2 = isTopLeft(l_v0, l_v1) ? 0 : -1;

// Determine barycentric coordinates
int w0 = orient2d(l_v1, l_v2, p) + bias0;
int w1 = orient2d(l_v2, l_v0, p) + bias1;
int w2 = orient2d(l_v0, l_v1, p) + bias2;

// If p is on or inside all edges, render pixel.
if (w0 >= 0 && w1 >= 0 && w2 >= 0) {
raster[(int) p.y][(int) p.x] = true;
}
}
}

}

static boolean isTopLeft(Vector2f a, Vector2f b) {
if(true)
return true;
// assuming a counter-clockwise triangle
// https://fgiesen.wordpress.com/2013/02/08/triangle-rasterization-in-practice/
if( a.y == b.y && b.x < a.x )
return true; // top edge

if( b.y > a.y )
return true; // left edge

return false;
}

static int orient2d(Vector2f a, Vector2f b, Vector2f c) {
return Math.round( (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) );
}
``````

Its working already quite ok, but when using the resulting texture on a model a get fine areas where the texture is missing. So I think i don’t do it exactly as a shader would do it. I read some documentation and found out that there is some definition about which face “owns” a pixel if its exactly on the edge of the triangle and did some test with it (this is the isTopLeft stuff, that is currently disabled) but it did not work out so far. If I change the implementation so that the whole bounding box gets rasterized everything is alright (from the visualization perspective), but I would prefer to have a correct solution.

I thought it might be a good idea to post it here, because someone might already faced a similar requirement and already found a good solution!

If not, I will continue reading some documentation and find a solution, just thought this would be a little bit easier