[C++] [software rasterizer] Triangle rasterizer gaps

[spitfire]

I have gaps between the triangles and I don't know why, guidance would be appreciated. I am using fixed point integers.

Code: [Select]


void Rasterizer::triangle( textureTriangle2D & tri )
{
float temp;
int slopeLeft;
int slopeRight;

//sort top to bottom
//y is 0 at top of screen
if ( tri.y1 > tri.y3 )
{
SWAP( tri.y1, tri.y3, temp );
SWAP( tri.x1, tri.x3, temp );
}

if ( tri.y1 > tri.y2 )
{
SWAP( tri.y1, tri.y2, temp );
SWAP( tri.x1, tri.x2, temp );
}

if ( tri.y2 > tri.y3 )
{
SWAP( tri.y2, tri.y3, temp );
SWAP( tri.x2, tri.x3, temp );
}

//height of top and bottom half of triangle
float topHeight = tri.y2 - tri.y1;
float bottomHeight = tri.y3 - tri.y2;

slopeRight = floor( ((tri.x2 - tri.x1) * 65536) / topHeight );
slopeLeft = floor( ((tri.x3 - tri.x1) * 65536) / (topHeight + bottomHeight) );

int x1, x2, y1;
x1 = floor( tri.x1 * 65536 );
x2 = x1;
y1 = floor( tri.y1 );

int currentLocation = width * y1;
int clip;

//flat bottom triangle
if ( topHeight >= 1.0)
{
int h = floor(topHeight);
if (tri.x2 > tri.x1)
flatBottomTriangle( x1, slopeLeft, x2, slopeRight, h, currentLocation );
else
flatBottomTriangle(x2, slopeRight, x1, slopeLeft, h, currentLocation);
}
}

 void flatBottomTriangle(int x1, int slopeLeft, int x2, int slopeRight, float height, int currentLocation)
{
int runLength = 0;
currentLocation += (x1 + slopeLeft) >> 16;

do
{
x1 += slopeLeft;
x2 += slopeRight;

runLength = ( x2 - x1 ) >> 16;
while ( runLength-- > 0 )
{
screenBuffer[ currentLocation+runLength ] = 255;
}

currentLocation += width - (x1>>16); //go to next line at x = 0
currentLocation += (x1+slopeLeft) >> 16; //x1 accumulates slopeleft (important when < 1)
}
while( --height > 0  );
}



[Jim]

The gaps are caused by different rounding happening to the same point (or a copy of it) depending if it's a top, middle or bottom point.  The rounding needs always to be the same.
Alternatively, you are rendering one too few scanlines or one too few points in each span.
Exactly where that is in your code, sorry I don't know

I typed that, and then I saw your image.  Unless the points on the small triangles are actually shared with the big triangle (and the big triangle is actually chopped into three) there's absolutely no guarantee of no gaps.

Jim

[spitfire]

Thanks Jim. I've solved the problem, which I think has to do with the absolute value rule |a+b| >= |a| + |b|

My scanline was basically going from x1>>16 to
(x1 >> 16) + ((x2 - x1) >> 16)
but this can be less than  the intended x2 >> 16

[spitfire]

I'm still working on this but I wanted to show some progress since it took me so long to get here.
If it crashes please let me know what your system specs are.

[hellfire]

Works fine in fullscreen mode.
In window mode it just shows a completely white screen.
In 640x480 it crashed once but refused to do that again.
Maybe a rare case where 1.0/(v2.y-v1.y) gets INF ?
The texels look a bit shaky, maybe the interpolation is lacking a bit of precision or sub-pixel accuracy.
My system: Intel I7, Nvidia, Windows7 64Bit.

[spitfire]

Thanks Hellfire. Weird about the white screen, I don't know what causes that. The backbuffer is initialised to black.
Yeah those texture accuracy issues are turning me grey before my time

[hellfire]

Yeah those texture accuracy issues are turning me grey before my time

One typical reason for shaky texture-coordinates is missing sub-pixel correction.
If you have a look at this image, the interpolated positions along the edge differ significantly from the rounded integer pixel position that's actually being drawn to.
If you take that into account, your textures will be become much more stable.

[flightcrank]

I also have gaps in a triangle rasterizer i wrote. ill try mimicing the co-ords from your pic and see what i get.

i think the gaps are caused by rounding errors. I cast from floats to ints. so for example if an x value is "3.9" it gets cut to just 3. perhaps its the same in your version.

[spitfire]

It still wobbles a bit at the edges of the sphere but if you look at the green dots which are the floored coordinates coming in, the texture is following them. I'm not sure if it can be made more stable?

I did add your suggestion
               real xfrac = x1 - floor(x1);
               tv = (v1*textureHeight) -(xfrac*vSlope);
               tu = (u1*textureWidth) -(xfrac*uSlope);
               tz = z1 - (xfrac*zSlope);

[spitfire]

Well I see that there are definitely still incorrect wobbles.
I think the problem is that I need to adjust the coordinates in the y direction aswel to compensate for the flooring.
But this is more difficult. In the attached image, if I just go backwards using the slopes for the top left point, they end up crossing over and giving me two points. What I want is the texture coordinate at the top left corner of that pixel, but first I need to determine which direction is up in the texture and the rate of change from the corner of the ideal triangle to the corner of the feasible triangle in texture space. Not sure how to do that.

I've never seen rasterizer tutorials talk about these details though so maybe my approach is wrong or I'm missing something else?

Also in the attached picture the red pixel confuses me. I tried manually drawing the squared according to top left rule and right edge - 1 to prevent overlapping.
But for the red pixel it is the right most pixel -1 of the purple triangle and also the left most edge of the green one.

Code: [Select]

void Rasterizer::textureTriangleFloat(textureTriangle2D & tri)
{
real temp;
real slopeLeft;
real slopeRight;
real ul, vl, ur, vr, zl, zr, u1, v1, u2, v2, z1, z2;
real x1, x2, y1, y2, y3, h;
real currentLocation;
real clip;

//sort top to bottom
//y is 0 at top of screen
if (tri.y1 > tri.y3)
{
SWAP(tri.z1, tri.z3, temp);
SWAP(tri.y1, tri.y3, temp);
SWAP(tri.x1, tri.x3, temp);
SWAP(tri.u1, tri.u3, temp);
SWAP(tri.v1, tri.v3, temp);
}

if (tri.y1 > tri.y2)
{
SWAP(tri.z1, tri.z2, temp);
SWAP(tri.y1, tri.y2, temp);
SWAP(tri.x1, tri.x2, temp);
SWAP(tri.u1, tri.u2, temp);
SWAP(tri.v1, tri.v2, temp);
}

if (tri.y2 > tri.y3)
{
SWAP(tri.z2, tri.z3, temp);
SWAP(tri.y2, tri.y3, temp);
SWAP(tri.x2, tri.x3, temp);
SWAP(tri.u2, tri.u3, temp);
SWAP(tri.v2, tri.v3, temp);
}

//height of top and bottom half of triangle
real topHeight = tri.y2 - tri.y1;
real bottomHeight = tri.y3 - tri.y2;

y1 = floor(tri.y1);
y2 = floor(tri.y2);
y3 = floor(tri.y3);
real pixelheight = y3 - y1;
real pixeltop = y2 - y1;
slopeRight = ((floor(tri.x2) - floor(tri.x1))) / pixeltop;
slopeLeft = ((floor(tri.x3) - floor(tri.x1))) / pixelheight;

ul = (((tri.u3 / tri.z3) - (tri.u1 / tri.z1))) / pixelheight;//
vl = (((tri.v3 / tri.z3) - (tri.v1 / tri.z1))) / pixelheight;//
zl = (((1.0f / tri.z3) - (1.0f / tri.z1))) / pixelheight;//

ur = (((tri.u2 / tri.z2) - (tri.u1 / tri.z1))) / pixeltop;//
vr = (((tri.v2 / tri.z2) - (tri.v1 / tri.z1))) / pixeltop;//
zr = (((1.0f / tri.z2) - (1.0f / tri.z1))) / pixeltop;//


//real yfrac =   tri.y1-y1 ;
x1 = tri.x1 ;//+ yfrac*ul;
x2 = tri.x1 ;//+ yfrac*ur;
;//
u1 = (tri.u1 / tri.z1) ;// -(ul*yfrac);
v1 = (tri.v1 / tri.z1) ;// -(vl*yfrac);
z1 = (1.0f / tri.z1) ;// -(zl*yfrac);
u2 = (tri.u1 / tri.z1) ;// - (ur*yfrac);
v2 = (tri.v1 / tri.z1) ;// - (vr*yfrac);
z2 = (1.0f / tri.z1) ;// - (zr*yfrac);

real uOffset = 0;
real vOffset = 0;
real uOffset2 = 0;
real vOffset2 = 0;
real zOffset = 0;
real zOffset2 = 0;

currentLocation = (pitch * y1);
h = y2 - y1; //floor(topHeight);
if (h > 0)
{
if (slopeRight > slopeLeft)
{
triangleFloat(x1, slopeLeft, x2, slopeRight, h, currentLocation, u1 + uOffset, u2 + uOffset2, ul, ur, zl, z1 + zOffset, v1 + vOffset, v2 + vOffset2, vl, vr, zr, z2 + zOffset2);

}
else
triangleFloat(x2, slopeRight, x1, slopeLeft, h, currentLocation, u2 + uOffset2, u1 + uOffset, ur, ul, zr, z2 + zOffset2, v2 + vOffset2, v1 + vOffset, vr, vl, zl, z1 + zOffset);
}

bottom half code removed...
}
__forceinline void triangleFloat(real x1, real slopeLeft, real x2, real slopeRight, real height, real currentLocation, real u1, real u2, real ul, real ur, real zl, real z1, real v1, real v2, real vl, real vr, real zr, real z2)
{
int index, endex;
real tu = 0, tv = 0, tz = 0;
real textureIndex = 0;
real uSlope = 0, vSlope = 0, zSlope = 0;
do
{
if (floor(x2 - x1) > 0)
{
uSlope = ((u2 - u1)*textureWidth) / ((x2)-(x1));
vSlope = ((v2 - v1)*textureHeight) / ((x2)-(x1));
zSlope = (z2 - z1) / ((x2) - (x1));
}

real xfrac = x1 - floor(x1);
tv = (v1*textureHeight) -(xfrac*vSlope);
tu = (u1*textureWidth) -(xfrac*uSlope);
tz = z1 -(xfrac*zSlope);

index = currentLocation;
index += floor(x1);
endex = currentLocation+floor(x2);

while (index < endex)
{
real div1 = tu / tz;
real div2 = tv / tz;
int  t1, t2;
floorToInt(&t1, div1);
t1 %= textureWidth;
floorToInt(&t2, div2 );
t2 %= textureHeight;

screenBuffer[index] = texture[t1 + textureWidth*t2];

tu += uSlope;
tv += vSlope;
tz += zSlope;
index++;
}

x1 += slopeLeft;
x2 += slopeRight;
u1 += ul;
v1 += vl;
u2 += ur;
v2 += vr;
z1 += zl;
z2 += zr;
currentLocation += pitch;
} while (--height > 0);
}


[hellfire]

Sorry for the late reply, Spitfire.
What's missing right now is the vertical sub-pixel correction.
Here is an image for illustration:


Here I'm always rounding up (somewhat easier because you always increment values).
This might look a bit counter intuitive but the empty pixels on the left side are filled by the right side of an adjacent triangle.

Starting at the top vertex you have to trace the edges to the next scanline (that's where the red dot is).
From there you've got to find the next whole pixel (green horizontal line to the blue dot) - that's what you're already doing.

[spitfire]

Thank you for your patience with me Hellfire
I've finally found out what I was doing wrong. I was indeed adjusting the x coordinate per scanline, but I hadn't adjusted the initial x coordinates of the 3 vertices .

When I round the initial y coordinate to the next whole number I need to move the x coordinate by the rate it changes over that fractional y distance. After that I can start tracking the edges and only then round x up to the next whole number for each new scanline.

float yfrac = ceil(tri.y1) - tri.y1;
x1 = tri.x1 + yfrac*slopeLeft;
x2 = tri.x1 + yfrac*slopeRight;

x1 and x2  are the top tip of the triangle I was thinking of as one point, but they can be far apart if the triangle is wide.

[spitfire]

.

[spitfire]

This is just a ramble.

So it was working fine but then I wanted to change the rounding convention from ceiling to floor, because that was how I originally intended to do it and couldn't see a reason why it shouldn't work. But I can't figure out how to make it work. I'm going to assume its actually impossible.

When rounding values up to the next whole number there is the advantage that you are sliding down the existing triangle edges as you jump to the whole number. But if you go backwards with a floor the triangle doesn't even exist there for the first coordinate!

Whats worse is at the second vertex, if the second and third vertices are less than 1 pixel away from each other in the y direction, you cant follow the slope of that line back to get to the integer boundary because it send you far off the triangle. I could change the fill convention to bottom right, but then I would still have to use ceiling to step down the edges of the first coordinate anyway.

[spitfire]

So I found and fixed another problem. I had gaps at midpoints in triangle due to accumulation error. In fact I saw gaps because I was
using multiply to get an accurate value halfways through the triangle, but this then was inconsistent with the way pixels had been plotted up to that point.
So I just use the accumulated inaccurate value now and everything aligns nicely.

I also removed a d3d9x lib dependency
Did Frustrum/near clipping
fixed a strafe issue by using camera U vector to move left/right instead of trig
Started adding mipmaps

But I have another problem now. In the fixed point version the triangle goes screwy if I get too close to it. So I assume I'm running out of integer resolution. I'm shifting by 65536 for all the fixed point number but then by another 1024 for the 1/z coordinates because they didn't have enough resolution. I wonder if that's causing this

[Stonemonkey]

hey there spitfire good work so far, something to think about, the slopes along each scanline are constant over the whole triangle.

to take it even further, no matter which way round the triangle is you can calculate the initial scanline values off the long (v1-v3) edge. Meaning you only ever need to calculate the slopes for v1-v3 once and the scanline slopes once per triangle.

[spitfire]

Hey thanks Stonemonkey. Thanks for the tip, I think I'm doing that already.



I finally fixed it. What a milestone for me! The texture mapping is working correctly now in floating point and fixed point mode.

The last problem with the messed up picture I posted was because I was multiplying my u,v coordinates in fixed point with the texture width/height before interpolating and it was leading to overflow of the 32 bits. Now I leave the maximum values at 1<<30 (in fixed point) and then divide by the texture size instead of multiply, so theres no overflow. I actually do a bit shift so its even faster. Then I just scale it when I convert back from fixed point to integer.

The other tricky thing was adding 0.5 to the final texture coordinate in this scaled fixed point format ( ((FIXED_POINT_MAX/textureWidth)/2) / (FIXED_POINT_MAX/textureWidth) ), because without it texels are selected right on the edge of a texel. That leads to bouncing texel edges because the  original coordinate of an individual texel may be something like 0.00003,0.00001 (uv coordinates) and certian floating point values cant be represented accurately in binary. Selecting from the middle of the texel by adding 0.5 (texture coordinates) to everything gives it 0.5 texels of breathing room to be inaccurate

Now I wish I had a nice lightmapped model to show it off with. It's a bit faster too now, I'm getting 170 fps in 640x480.

[hellfire]

Looks fine!
But it's a little bit disturbing that the startup dialog offers a resolution of 0x0 and also picks it as the default value.
Of course it crashes when you actually use that resolution

[spitfire]

Oops, I guess you don't have 640x480 native mode

[Stonemonkey]

Hey thanks Stonemonkey. Thanks for the tip, I think I'm doing that already.

ok, i only saw the code in reply #9 where you're calculating uslope,vslope,zslope before each scanline, have you changed that since then?