[Q] Shadow Volumes, BSP, and HSR
James Edward Russell
>not be possible to compute a "shadow volume" for each polygon
>and determine if the next polygon to be rendered is within it?
>If it is entirely within the shadow volume, then it is NOT visible
>and does not have to be rendered. If it is only partialy within
>the SV then it can be *clipped* to the previous poly's SV,
>and only have it's visible parts drawn. That would make for
>a "perfect" 3-D engine with *no overdraw*. Right?
Very true, but the problem is that you have to traverse the BSP tree
in order to get the front to back order (since SVBSP trees MUST be
made by inserting nodes front to back WRT light source), then you have
to build an SVBSP tree which isn't too difficult for a 2D BSP tree,
but gets fiddly with 3D. Building the tree for EVERY frame may prove
to be a very large part of your raster time, and that doesn't include
the process of clipping the original BSP tree to the view volume.
You are correct though, it would make a perfect view with no overdraw.
But don't assume that overdraw is bad. It only becomes inefficient when
the plane is large and a large number of operations have to be performed
per pixel (such as Phong illumination/shading w/o fwd diff.)
Jeff Lander
>I don't like overdraw, sorted spans, or PVS lists. To damn complex
>and slow.
You need to read "Front to back Display of BSP trees" Dan Gordon
and Shuhong Chen in IEEE CG&A Sep 1991.
You get no overdraw, with only the same complexity of the AET of
concave polygon scan conversion.
But remember that BSP have overdraw as one of its major drawback.
You have to process hidden polygons no matter what, even if you do
not "draw" them. If you are really focusing on overdraw, use another
method of HSR and sorting.
Jeff
--
===============================================================
Jeff Lander Game Development for
Accent Media Productions Sega Saturn, Sony PSX
je...@accentmedia.com PC and Mac CD Rom
http://www.accentmedia.com/~jeffl
Tim Sweeney
> not be possible to compute a "shadow volume" for each polygon
> and determine if the next polygon to be rendered is within it?
> If it is entirely within the shadow volume, then it is NOT visible
> and does not have to be rendered. If it is only partialy within
> the SV then it can be *clipped* to the previous poly's SV,
> and only have it's visible parts drawn. That would make for
> a "perfect" 3-D engine with *no overdraw*. Right?
I coded this and the major problems are:
1. The shadow volume BSP's become very lopsided, so processing an
additional polygon becomes more of an O(n) operation than an O(log n)
operation.
2. You'll get cracks between adjacent polys unless you incorporate logic
to build a seamless SVBS mesh (a slow and operation).
3. Building the SVBSP requires taking the sqrt() of the difference of
two numbers which is (A) slow, and (B) numerically unstable. Given the
number of times you have to do this per frame, the speed and precision
problems are killer.
-Tim
Bretton Wade
# 3. Building the SVBSP requires taking the sqrt() of the difference of
# two numbers which is (A) slow, and (B) numerically unstable. Given the
# number of times you have to do this per frame, the speed and precision
# problems are killer.
Where exactly do you need to take the sqrt?
miguel
>
> I am working on a 3-D game engine similar to Quake or Prey.
> I don't like overdraw, sorted spans, or PVS lists. To damn complex
> and slow.
>
> run super-fast. I haven't coded anything for this theory yet, but I
> will get around to it... :)
>
> I would like any and all feedback on it. Will it work? Is it a piece
> of junk? Could it be possible to make the fastest 3-D engine
> ever with it?
>
> Ok, Well, here it goes:
>
> If you have a 3-D BSP tree, and you walk it front-to-back, would it
> not be possible to compute a "shadow volume" for each polygon
> and determine if the next polygon to be rendered is within it?
> If it is entirely within the shadow volume, then it is NOT visible
> and does not have to be rendered. If it is only partialy within
> the SV then it can be *clipped* to the previous poly's SV,
> and only have it's visible parts drawn. That would make for
> a "perfect" 3-D engine with *no overdraw*. Right?
>
Though my experience with BSP trees is limited, I'm
pretty sure that would work. But your data
structures would be pretty hard to manage.
miguel
Tim Sweeney
> # two numbers which is (A) slow, and (B) numerically unstable. Given the
> # number of times you have to do this per frame, the speed and precision
> # problems are killer.
>
> Where exactly do you need to take the sqrt?
To generate a BSP which I could clip world polygons by, I built a solid 3D BSP
by forming a set of partitioning planes for each visible polygon. Each
partitioning plane contained the viewpoint and the line comprising the polygon's
side. You just do this for all polygons in the world, in front-to-back order, until
the screen is completely solid. To build those planes from a point and a line, I took
a cross product, and normalized it. (In retrospect, I think this would have worked without
the normalization - DOH!) :) The numerical instability came from sliver polygons, where
most of the precision was lost during the cross product. This problem could have probably
been overcome, as well as cracking, and optimization, but my view volume renderer was
abyssimally slow in complex areas compared to simpler methods, so I didn't spend much
time before moving on to other methods.
Regarding convolving the world with a sphere in order to simplify collision, that's a
great idea. You could also convolve the world with a cube and end up with
all-polygon geometry.
-Tim
Alexander Berg
Hi. Regarding the "shadow volumes" check out the Weiler Atherton hidden
surface removal algorithm... it produces non-overlapping output in a
method similar to what you describe.
Alex Berg