Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

zyzzy

How can a Z-Buffer be faster than painters algorithm?

This topic is 6924 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

How can a Z-Buffer possibly be faster than painters algorithm? My tutorial says it is when there are many polygons. The actual drawing is just setting a byte so I can''t understand why overdraw is so slow!

Share this post


Link to post
Share on other sites
Advertisement
z-buffers are often hardware supported, and it''s a much simpler test than painters algorithm, not to mention it''s always CORRECT (aside from accuracy issues), unlike the painter''s algorithm.


#pragma DWIM // Do What I Mean!
~ Mad Keith ~
**I use Software Mode**

Share this post


Link to post
Share on other sites
It''s true that Painter''s algorithm only fiddles with half as many bytes (just video memory, as compared to both video memory and the buffer). However, Painter''s algorithm has the additional overhead of sorting the polygons as well as blitting. Which makes rendering an O(n log n) operation, as compared to z-buffering which makes rendering an O(n) operation, (admittedly with a high constant factor). However it doesn''t take too many polygons for the log n to dominate the constant factors in z-buffering. So, it''s not the overdraw that''s slow, it''s the sort that''s slow.

Share this post


Link to post
Share on other sites

Whether Z-buffer is faster/slower than painters algorithm depends what kind of polygon-filler you use. Here''s a little example:

I render 128 cubes (no rotation, only travels in depth), results as frame per secondes per polygon type:
z-sorting z-buffer
flat: 51 32
gouraud: 28 25
affine texture: 29 26
perspective corr. texture: 23 25 (finally faster!)

As you can see, it all depends on how complex the texture routines are. If you''re going to use lighting, z-buffer will be MUCH faster than z-sorting.

Oh, and if you use z-sorting&z-buffer at the same time, you''ll get the same as when using z-buffer only (well, at least that was what happened with my test program).


-my 2 cents-

Share this post


Link to post
Share on other sites
Oops, I didn''t read the documents well enough
The algorithm which was used in my test was not a z-buffer but a scan-line oriented system which can see which polygon is the nearest. So I tested again, but now with a real Z-buffer. It wasn''t worth trying, I only got about 17 frames per second. Guess it was a slow implementation, because z-buffer should be faster than painters algorithm (or at least I think it should be).

-my 2 cents-

Share this post


Link to post
Share on other sites
If texture adressing takes more time than testing the z-buffer it will be faster to render front-to-back with z-buffer, than rendering back-to-front without z-buffer. This because you don''t access the textures more times than there are pixels on the screen.

If the polygons are unsorted then the z-buffer can be faster, but it may also be slower. It will be slower if the majority of the polygons are in front of previous rendered polygons. But if you have many polygons statistics say that half of the pixels rendered will be behind previously rendered pixels, which means that you only do texture adressing half as much as with the painter''s algorithm.

It all comes down to if the texture adressing time outweights z-buffer testing time, which it usually does. Especially if you have bilinear filtering, texture blending, mip mapping, bumpmapping, etc, etc.

- WitchLord

Share this post


Link to post
Share on other sites
sicrane - um, there are sorting algorithms ranging from O(n) to O(n^2).. what made you pick n log n?

And when will people stop abusing big-O?

-goltrpoat



--
Float like a butterfly, bite like a crocodile.

Share this post


Link to post
Share on other sites
There''s no general case sorting algorithm that runs in O(n). Any such sorting algorithms impose restrictions on the input set of data. However, there are at least a few good sorts that run in O(n log n), most famous being quick-sort. I''m assuming that you would choose the most optimal algorithm for your sort, which is why I didn''t list O(n^2). Cases where O(n^2) runs faster than O(n log n) is when constant terms dominate the running time, i.e. not for large n. And I don''t think I was abusing big O notation.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!