16 replies to this topic

[peterbone]

I've made a software renderer in delphi from scratch.
http://www.geocities...k/engine3d.html

It works well apart from occasionally faces that should be drawn behind are drawn in front. At the moment I'm calculating the distance of the center of the face from the camera. This sometimes produces incorrect results when faces are close together and if faces are different sizes. I'm assuming the faces are not actually intersecting.
Is there a way I can work out the exact order? I've tried thinking of ways envolving all the vertices around the face but nothing I can think of is full-proof.
Please help if you know the answer.
Thanks

Peter Bone

[Goz]

http://www.siggraph....ity/painter.htm

[peterbone]

Thanks. It's more complex than I'd hoped though!

[Reedbeta]

hidden surface removal is never easy

[peterbone]

This is annoying. I have to compare every polygon with every other polygon and test if they should be swapped! That must slow it down a lot. Has anyone got a better link for the same thing - that page doesn't explain very well and some code would be helpful. I was thinking about a z buffer but they're slow in a software renderer too.

Here's the program I'm working on.
http://atlas.walagat...rbone/rubix.zip

It's the internal faces overlapping the external faces as a layer rotates that's the problem - set the rotation speed to lowest in properties.

[Reedbeta]

peterbone said:

I have to compare every polygon with every other polygon and test if they should be swapped!

Use a sorting algorithm, silly! If polygon A is in front of B, and B is in front of C, then A is in front of C. So you can use quicksort or whatever and it will work fine.

[JSoftware]

http://hysteria.sk/~...ng/2/SBUFF2.TXT

could Span buffering be useful?

[Nils Pipenbrinck]

Zbuffer is not as slow as you might think.

If you start to have significant overdraw the z-test can actually speed things up.

[Nils Pipenbrinck]

bucketsort!

We had to sort polys on the ps1 (that's a 30Mhz CPU) and it was never much of a deal.

[Nick]

Just use a z-buffer. It isn't that slow.

But if you really want to take this renderer to a whole new performance level you should use assembly. I'm rendering some scenes originally meant for hardware rendering at 640x480 at 30 FPS or more... That's how powerful modern CPUs really are when using MMX/SSE instructions and the most advanced optimizations.

If you're not so concerned about performance, then just don't be concerned about it at all and use a good z-buffer implementation. In my experience it's always best to use the same techniques used by graphics hardware when in doubt. They really use poweful algorithms that are not so bad for software rendering either.

[peterbone]

Thanks. That's true, I'm using quicksort to sort my polygons anyway so I suppose I can just modify that with the added tests.
Thanks Nick, but I think I'll skip the z buffer for now - I think the polygon sorting method will be faster since I don't know how to write assembly. Are you the same Nick that helped me several times before? You told me I needed to do sub pixel accuracy and several other things. Thanks.
So no-one's got a link for the modified painters algorithm that explains in more detail? I'll try to find something in my university library.

So what did you think of my rubik's cube simulator? It was confusing to make but very satisfying. If anyone wants the Delphi code I'll send it to you.

[peterbone]

ok, I'm implementing a z buffer. I'm using a 32bit buffer and I'm trying to get the maximum precision out of it by normalizing the 1/z values between my near and far clipping planes but it doesn't work for some reason. here's how I calculate the values for each vertex:

ZFar := 987;
ZNear := 813;
a := (zFar + zNear) / (zFar - zNear);
b := 2 * zFar * zNear / (zNear - zFar);
Depth := Trunc((a + b / ViewPoint.Z) * High(Integer));

What's wrong with that? a + b / ViewPoint.Z should normalize it between -1 and 1 so multiplying by the largest possible integer (32bit) value should normalize in the range of the integer but it seems to be overflowing the integer. I got those equations from wikipedia but it doesn't show how they're derived.

[Nils Pipenbrinck]

how about:


znear := some small value
zFar := some very large value

Max_z_value_in_buffer = largest value representable in your zbuffer.

z: z of current pixel, should to be >= znear and <= zfar

zbufferval = Max_z_value_in_buffer * (z-znear)/ (zfar-znear)

[Nick]

Use a homogeneous projection matrix. After clipping, all your z-values will be between 0.0 and 1.0. Then do perspective correction by dividing by w. And please use only floating-point numbers for the first implementation, it will save you a lot of trouble. I ran your rubix demo and it looked insanely smooth. ;) So don't worry about performance at all untill the application is functionally finished (or it becomes unbearable to watch). This way you'll be able to add a lot more well working features, instead of losing tons of precious time on optimizations that don't work and make the code unmanageable. Keep up the good work! :yes:

[peterbone]

Thanks Nick. I think I know what the problem is. When the z values are stored in the form 1/z they can be linearly interpolated in the rasterizer. The equations I got from wikipedia do normalize between -1 and 1 but they store the values in the form A + 1/z where A is a constant. I think this means they can't be linearly interpolated correctly. I think I'm missing something. Anyway, Depth := Trunc(1000000000000 / ViewPoint.Z); works for now so I'll use that.
I know I shouldn't worry about optimization so much when it's already fast enough but I can't help the feeling that it could always be slightly faster!

Here's my line rasterizing code. Got any speed ups?

scanpointer := @Scanlines[y][ScanStart];

depthpointer := @DepthBuf[y][ScanStart];

for x := ScanStart to ScanEnd do begin

  if D > depthpointer^ then begin

    Scanpointer^ := RGB;

    depthpointer^ := D;

  end;

  Inc(scanpointer);

  Inc(depthpointer);

  Inc(D, Ddx);

end;

Also, what's the best way to clear my z buffer? It's a 2d dynamic array. I've seen reference to using MemSet but Delphi doesn't seem to have that. At the moment I'm using optimized rasterizing code.

[Nick]

peterbone said:

The equations I got from wikipedia do normalize between -1 and 1 but they store the values in the form A + 1/z where A is a constant. I think this means they can't be linearly interpolated correctly.

Indeed. But Z = (A + B * z) / w does interpolate linearly (with w = z for perspective projection). You can choose A and B in such a way that Z is in the [0, 1] range between the near and far clipping plane. Typically A is close to 1 and B is close to 0 so the formula is almost Z = 1 / z.

This is exactly what a homogeneous projection matrix does in Direct3D (or OpenGL):

[w 0   0   0]

[0 h   0   0]

[0 0   Q   1]

[0 0 -Q*Zn 0]


with Q = Zf / (Zf - Zn)

You can see that A = -Q*Zn and B = Q. Also note how we get w = z in the last column. Now the nicest thing about having this in matrix form is that you can multiply it with the model and view transform matrices, and get the whole transformation from model space to clip space in just one matrix!

Quote

I think I'm missing something. Anyway, Depth := Trunc(1000000000000 / ViewPoint.Z); works for now so I'll use that.

I assume that's floating-point? Because that number is out of range for a 32-bit integer. I still seriously suggest to use floating-point numbers everywhere anyway...

Quote

I know I shouldn't worry about optimization so much when it's already fast enough but I can't help the feeling that it could always be slightly faster!

I know the feeling all too well, but it very often turns out to be a waste of time. Several years ago I made the mistake of spending several weeks on some 10% optimization. Then I wanted a new feature and had to rewrite it all (i.e. throw it away). And the next day I found a 20% optimization with an algorithmic improvement. So please don't make the same mistake and just write nice clean reusable code. Once it's done, mark that version with your source control as the last clean version, and then just optimize with whatever low-level trick you can find. Just remember, "premature optimization is the root of all evil" - Donald Knuth. Note that your software has to be mature before optimizations are no longer entirely evil.

Quote

Here's my line rasterizing code. Got any speed ups?
...

Looks optimized to me, but allow me to use it to clarify my point. If your compiler is any good, that code executes in 10 clock cycles per pixel. With a low-end 1 GHz CPU, 640x480 screen and crazy 10x overdraw, that still gives us over 300 FPS! For that rubix game, 10 FPS should be plenty... So you can see there is lots of extra processor power you can so something more useful with than drawing extra frames. I'm thinking about a shiny rubix cube reflecting the environment. :worthy:

To get there, you'll need many extra features like diffuse lighting, texture mapping and alpha blending. If you try to optimize everything from the start, you will end up with spaghetti code that becomes unmanageable and you will either end up rewriting everything several times or just never finish it. If on the other hand you forget about optimizations for a while, this can be achieved in a couple weeks tops. And if it's not fast enough it will only take a day to optimize the real bottlenecks with only a fraction of your code made less manageable.

But even if you're not interested in a shiny rubix, I hope it's clear now that any optimization at this point is a waste of time. There is absolutely no reason to make it faster than it already is.

And if you're really still interested in a direct answer: Yes it can be optimized, by using assembly with MMX instructions. But it should be clear by now that this would make the code totally unmanageable at this point. You need to go in the other direction, even if that means less optimizations, because it doesn't matter.

Quote

Also, what's the best way to clear my z buffer? It's a 2d dynamic array. I've seen reference to using MemSet but Delphi doesn't seem to have that. At the moment I'm using optimized rasterizing code.

Just use a nested loop that clears one line at a time. It should be almost identical to how you clear the color buffer.

[peterbone]

Thanks a lot for all that. Unfortunately I'm not using matrices at all for my transformations and I don't know what w is. I assume it's something to do with quaternions but I'm not using them either (I know it's lame).

That Depth equation is fixed point integer. It doesn't overflow because the the z values are always > about 800 or something.

I want my programs to work on slow computers too. On my 2GHz pc it uses up over 50% of the processor when on full screen.

I think I'll give the shiny cube a miss but it does have diffuse lighting. Maybe you didn't notice because the difference in intensity isn't much.

I'm clearing my colour buffer using the windows fillrect routine since it's a bitmap. It's slightly faster than anything I can write. Maybe I'll make my z-buffer a 32 bit bitmap too.

Thanks for all your help and someone should correct wikipedia or add to it to make those equations make sense.