BSP and Scaline APgorithm

I suppose this thread was miss named, its not the scanline algorithm i''m interested in. I was confused on the termonology for a second.

Hi!

I suppose I know what you mean.

You mean, for you know the correct order to draw the polygons
using a bsp tree, you can draw only the first few
closest polygons that are really visible from current
viewing point at current viewing angle, such that the
last polygon drawn projects onto the last few screen-pixels that
are undrawn yet. And when all pixels of the screen are
drawn at least once, none of the remaining map polygons
could be visible, since every of them is _behind_
and covered by the drawn polygons, which are all closer
to the viewer.

Right?

Well, that would mean to count all not yet drawn pixels,
and, if this is zero, quit drawing.
I can''t imagine there''s a "glGetDrawnpixels()".


But, there is a similar idea, which I''m quite
"fascinated" of, called "BEAM TREES"
(and which I''m going to implement, when I have the time...)

This is definately what you''re looking for!!
It''s a second "little" bsp-tree, not created
during pre-processing, but rather during run time.
It keeps track of how much area of the screen is
undrawn, and when everything of the screen is drawn, you can
quit drawing.
The idea is, when you''ve drawn the first polygon onto the
blank screen, a beam is traced from viewing point
along the edges of that polygon, as if you cut a fat slice
out of the viewing frustrum. That beam is a "black hole"
:-), no more available for drawing.
Polygons drawn after this, are _clipped_ against that beam
(thus no need
for z-buffering, which speeds things up! well,
at least no z-compares, only writes, if you want to
z-buffer moving objects later...),
and more beams that cut more from the "view
pyramid" away are added to the tree, until the entire
frustrum is a "black hole".

John Carmack used this approach first, in original Quake,
but then came up with the PVS, which was much faster,
and provided a almost constant frame rate in all positions
of the map.

The problem of beam trees is, that they''re only suitable
for indoor scenes, with not _too_ large rooms where you
can look 300 yards far or so, for there are so many polygons
to clip and draw, until the screen gets filled entirely.
and seeing through windows
to the sky is also bad, since then all polygons in the
viewing frustrum have to be clipped, the screen will
never get filled with world polygons on such part of the
screen.

But If you''re planning to do an indoor game, well,
beam tree might work fine, at least better than in
original quake, where carmack had only _software_ renderer!!
A few polygons and a little overdraw more cause
a software renderer to break down, well, with today''s
graphics hardware this is not the case, I think.

(it seems that many game developers do not care
about efficient implementations. there are so many games out
that look much worse than QuakeIII, but have same
system requirements ;-)


Well, explanations about beams trees can be found
in "abrash.pdf", unfortunately I forgot where I found
it.
Search for it with an ftp file searching engine,
and, if the first chapter is "inside quake" or so,
then it''s the right one.


Well, it''s only 313 kilobytes, is it possible to upload
somewhere, at gamedev.net, or just post or something?
(never tried, don''t even know how to include bitmaps
into my post...)
However, if possible somehow, I would post it.


Sound''s interesting?
hope my post was at least a little useful.

the unshaven bastard

THANKS!!!!

Great Post! I''ll look into Beam Trees and PVS on google and see what they are. Really thanks for clarifying it!

He who said money was the root of all evil knew little of the nature of money and less about the nature of man.