[c++] Bug In 3d

[Clyde]

Hi,

I've converted a 3d thang ive been working on over from freebasic to cpp.

There's a weird drawing bug with the triangles at certain points as it rotates.

I'm scratching my brain cell as to how to fix it.  In basic, it works a charm.

So it got me thinking that it's to do with how floats are dealt with and rounding issues.
Should it be up or down, or even involve precision?  And which bits, the scanline and / or draw triangle bits;  there's some stuff in global - maths, that might be of use.

Thanks for your help and being a super star,
Clyde.

[LittleWhite]

Hello,

My guess is : float precision.
Exactly the Hellfire's message : http://www.dbfinteractive.com/forum/index.php?topic=6280.msg81875#msg81875

Try to do test between two floats using an epsilon (like 0.0005 or even less). These "special" tests should be inserted in the render function (the one selecting if a pixel should be drawn or not).

[CoDeMaN]

Tested and seems to work fine my end

[LittleWhite]

Note : I tested the .exe that you gave. I could recompile since I don't have Visual Studio nor Windows (and I am a bit lazy at rebooting the machine ). So, I started your .exe using Wine (which is a kind of of Windows emulator for Linux) and it worked very well, I did not see any bug.
But this make me think that the precision problem needs to be look at. Little tip : I have a 64 bits machine. Maybe the bug is visible only on 32 bits machines ?

[Clyde]

Thanks for testing and the reply much appreciated, but it's still there. My machine is also 64 bit.

I did think maybe that tinyptcd3d might have something to do with it. but I don't think so.

This rounding / precision issue if all very new to me; especially in CPP as my early stuff was done in basic languages,
which I've not really had to worry about what floats get upto behind the scenes. So any help is greatly appreciated!
And I don't know what or how to do an epsilon test.

The only sort of rounding with floats to ints, i've done are the usual int_value=(float)( flt_value+0.05f);
I did try with a smaller values like 0.0005f, with the left and right x position in the scanline function but that didn't cure it.

Cheers!

[Canopy]

i tried it as well.. however didn't recompile.

the exe in the package was fine, and the main thing i noticed were the different colours from your screenshot?


the only thing i could see is that maybe you still don't quite get what was explained elsewhere about pointers to classes, but there isn't an issue with the way it was being done apart from a memory leak at the end of the function and a too large value being passed to the B component of an RGB macro.

is the only code you've changed within the main cpp file? i dont know from looking at the project what is yours, and what pre-existed in tinyptc

[Clyde]

Thanks for your time and taking a look.

It didn't recompile? That's interesting.

The stuff to do with the tinyptc equivalent that Jim kindly knocked up, are: the the header and cpp file for tinyptc_ext and the cpp for tinyptcd3d

[hellfire]

The included .exe is slightly different and doesn't show the problem well.
I recompiled your project and saw the problem (just as your screenshot).

At first I thought it's just wrong rounding of the left & right end of a scanline (which it is, too).
But it turned out to be mainly a depth precision problem.
Z values don't interpolated linearly across your triangle, so the interpolated z is simply wrong.
And as all your edges overlap by (at least) one pixel, you get heavy z-fighting on the edges.

When I simply do "pos_z= 1.0f/z" in edge::setup_pos, the problem gets much better.
(That's because 1/z is linear after the perspective divide)
The rest of the problem comes from missing sub-pixel accuracy (have a look over here).

[Canopy]

It didn't recompile? That's interesting.

noo! i didn't do it

[Clyde]

Thanks heaps for taking a look and for your time, it's great.

I thought I was interpolating the z values of the triangle in the scanline routine. I must of missed that when converting.

Which bits are missing sub pixel accuracy? The draw triangle and / or scanline stuff.  I did have leftx - 0.05f, and rightx + 0.05f,
and the float to ints as +0.05f. but that made things worse when I did that.

And I'm not really sure if to round them up ( +0.05f ) or down ( -0.05f ) or even if to use higher values; as suggested by LittleWhite.
There was a precision function that I found on the net, that I included in global - maths.

Huge thanks,
Clyde.

[hellfire]

I'm not really sure if to round them up ( +0.05f ) or down ( -0.05f ) or even if to use higher values

Plain c has only two ways to perform rounding.
Using "ceil" always rounds up (when the fractional part is > .0)

Code: [Select]

int i= (int) ceil( f );
Using "floor" always rounds down (thus removes the fractional part):

Code: [Select]

int i= (int) floor( f );
When doing a simple integer-cast (that's what you're doing at the moment), you're rounding down:

Code: [Select]

float f= ...;
int i= (int)f;
When filling polygons I always found it convenient to address the upper left of a pixel, assuming a pixel ranges from [0.0 ... 1.0[.
But when rounding down, this position can move *outside* of the triangle (compare here: by rounding up the upper left of a pixel is always inside the triangle).
If you imagine some simple gradient interpolation ranging from 0..255 inside your triangle, you suddenly have to deal with values outside of the triangle, values going negative and other terrible things.
So I always round up.
Alternatively you can look at the pixel centers but it makes things just more complicated...

Which bits are missing sub pixel accuracy?

Let's assume you're drawing a triangle which consists of three floating point vertices v1 (top), v2 (middle), v3 (bottom).
So when you start drawing at the top (v1), the left and right edges have both the same x-coordinate (v1.x) and the current y-position is some floating point value v1.y.
For this particular scanline there's nothing to draw because the length of the scanline is 0 (left == right).
Now we have to progress to the next (integer!) scanline.
So instead of just adding the y-deltas to get to the next scanline, we just add as much as is necessary to reach the next integer y.

And when drawing a scanline, it's exactly the same principle:
The scanline starts at some floating point x coordinate but the first pixel you're plotting is at the next integer coordinate. So you just add a fraction of your scanline-deltas to reach the first actual pixel.


That being said you never really need floating point precision in screen space.
Simply convert all your coordinates down to integer in the projection stage and just leave a reasonable amount of extra bits for sub-pixel precision.
This way you get all the fractional-part math with a bit of shifts and bit-masking.

[Clyde]

Thank You so much for all the pointers!!

Time to try this out

edit - Have made a new version of draw_triangle, and it's a heck of a lot better now.
I wanted to check if I've implemented and put the ceilf(s) in the right places, or even the right function.

In the scanline function at the moment, rather that casting a float to an integer; I've used: (int)ceilf(float_variable);

Thanks again!!

-Clyde.

[hellfire]

You're now rounding every possible value to integer - that's a little bit over the top.
Instead you want to find the floating point values of z, r,g,b,a, u,v for a given integer pixel position x,y.
So first of all you calculate the deltas for the left and right side of your polygon without any rounding:

Code: [Select]

// left side: v1 .. v2
// right side: v1 .. v3

// calculate left side deltas
float left_height= v2->y - v1->y;
float left_dx = (v2->x - v1->x) / left_height;
float left_dz = (v2->z - v1->z) / left_height;
float left_du = (v2->u - v1->u) / left_height;
float left_dv = (v2->v - v1->v) / left_height;

// calculate right side deltas
float right_height= v3->y - v1->y;
float right_dx = (v3->x - v1->x) / right_height;
float right_dz = (v3->z - v1->z) / right_height;
float right_du = (v3->u - v1->u) / right_height;
float right_dv = (v3->v - v1->v) / right_height;

Using these deltas you go from the top vertex v1 down to the next integer scanline:

Code: [Select]

// step to next integer scanline
float stepy= ceilf(v1->y) - v1->y;

// update left side
float left_x = v1->x + stepy * left_dx;
float left_z = v1->z + stepy * left_dz;
float left_u = v1->u + stepy * left_du;
float left_v = v1->v + stepy * left_dv;

// update right side
float right_x = v1->x + stepy * right_dx;
float right_z = v1->z + stepy * right_dz;
float right_u = v1->u + stepy * right_du;
float right_v = v1->v + stepy * right_dv;
(you've got to do that again for either left or right once you've reached v2)

Now you've got a set of values for your left and right side and calculate the deltas to interpolate across the scanline:

Code: [Select]

float deltaz= (right_z - delta_z) / (right_x - left_x);
float deltau= (right_u - delta_u) / (right_x - left_x);
float deltav= (right_v - delta_v) / (right_x - left_x);

Now use these deltas to find the next integer x for the current scanline:

Code: [Select]

int x1= (int)ceilf(left_x);
int x2= (int)ceilf(right_x);
float stepx= x1 - left_x;
float z= left_z + stepx * deltaz;
float u= left_u + stepx * deltau;
float v= left_v + stepx * deltav;

And draw the scanline:

Code: [Select]

for (int x=x1; x<x2; x++)
{
   if (z < zbuffer[x])
   {
      zbuffer[x]= z;
      screenbuffer[x]= ...;
   }
   z+= deltaz;
   u+= deltau;
   v+= deltav;
}

Then update the left & right set of values to get to the next scanline:

Code: [Select]

left_x += left_dx;
left_z += left_dz;
left_u += left_du;
left_v += left_dv;

right_x += right_dx;
right_z += right_dz;
right_u += right_du;
right_v += right_dv;


[Clyde]

That looks really great Dude!! And thanks for the response

I haven't tried that out yet, as I can see I'm going to have to rewrite part of this. The fiddling around with using and not using ceilf hasn't quite cured it. I thought I had for a second, but with a texture on the cube it was only disguising the bug. It is a bit of a shame it's misbehaving.

With your guides above,  the delta parts will replace the stuff under the top, mid, bottom sorting? And then the deltaz, deltau etc in a new scanline?

Thanks again for all of your help!!! *