gdalgorithms-list

Re: [Algorithms] portal engines in outdoor environments

[jason w. <jas...@po...>]

> That's not the performance hit. You are submitting tris like this:
>
> BeginChunk
> Draw tester tris
> EndChunk
> if ( previous chunk rendered )
> {
> Draw real tris
> }


Nope, think more like:
begin(indexed_array);
setboundshint(my_boundingvolume);
draw(my_iarray);
end(indexed_array);

it's handed off as a single, seperatable transaction.. the hint merely
allows the hardware to quickly reject the entire array *if* it's obvious
it's hidden.. I would think this happens fairly often, like when a character
model is behind a wall, for example.

So what you're not getting, is that the *if* is _not_ a blocking *if*. It's
just a hint.. the hardware can deal with the hint in many ways.. it's true
that it would work best in a heirarchical z pipeline, but it should still
work in the typical. How that z information gets relayed back to the
rejection block is an open question.. but I can think of several ways in a
typical architecture.. it's cacheing scanlines anyhow, so it could do
something like relay the maximal value for every 4 z's in the scanline being
unloaded from cache back to the rejection block, where the rejection block
has it's own low res local cache. The details of how this works could take
many different forms.. the point being is that you only need delayed z info,
and that having the hint processed on chip means that you can do it inside a
single frame instead of relying on a previous frame.

> The problem is that the if() is being done at the very start of the
pipeline
> (i.e. the AGP bus - any later and you lose most of the gain),

Nope.. you gain fill rate by reduced depth complexity. You could gain
effective polygon bandwidth as well.

 but it needs
> to know the results of the rasterisation & Z-test of all the pixels in the
> tester tris.

no.. it just quickly needs to know if any z in the bounded region is further
than the maximal value of the bounding volume.. or some similar conserative
heuristic.

> looooong pipe between the AGP bus and pixel rasterisation). So your
pipeline
> is going to be completely empty between those two points. That is a huge

nope.. the pipeline is going to be full with the previous array, unless it
was rejected and the chip didn't have the start of the next stream
prefetch... depending on now long it takes to get the start of the next
stream, that could trigger a stall, but I'm sure the bus access could be
designed in a way to cut that down to few cycles...

>
> You may be able to improve things by doing:
>
> for i = 0 to nObjects
> {
> BeginChunk(i)
> Draw tester tris
> EndChunk
> }
> for i = 0 to nObjects
> {
> If ( chunk(i) rendered )
> {
> Draw object i
> }
> }
>

Right, this is closer.. the key being that the if needs to be just a hint
instead, and that it's treated as a input to conservative estimation that
uses a delayed and lower detail copy of the z.

Another approach would be a pageing/tiling architecture like the bitboys
vapor ware (apparently) is. In this case, triangles are rasterized in a
checker pattern instead of a scanline pattern, where each page is some
reasonable size, like 32x32 or so. It's a no brainer to maintain range
values for each page, enabling very fast rejetion of a page as a triangle is
scan converted. Better yet, with the rejection in front of some higher level
surface tessilator or the T&L, it can quickly read a few range values and
discard an entire array or patch.

> But that is a lot of extra hardware to store all that chunk information,
> retrieve it and so on. Lots of complexity. There are three very nice
things
> about the frame-to-frame coherency scheme:
>
> (1) No extra fillrate hit. If the object is invisible, it's the same
> fillrate as your scheme. If the object is visible, then you still only
draw
> it once, not twice as with your scheme.

You misunderstood.. I never said anything about drawing anything. Just a
bounding volume hint, which is a very different thing. There's plenty of
existing work for converting a OBB to exact screen regions *very* quickly
without resorting to scan conversion/rasterization. We're only interested in
conservative values as well, since it's common for a character model to be
completely seperate from a set of wall polygons.

> (2) No extra triangles needed. OK, the bounding box is a pretty small
number
> of tris, but what if you wanted to do this scheme with lots of smallish
> object? Might get significant then.

again, it's a hint, not a set of triangles.. no added triangles.

> (3) (and this is the biggie) It is already supported by tons of existing,
> normal, shipped, out there hardware. Not some mystical future device.
Real,
> existing ones that you have probably used.

*very* true, very good point.

> > Maybe
> > the gain is reduce, when you think about how the rejection
> > means there are
> > skips in the flow from AGP RAM to the cards local
> > storage/instruction bus,
> > but as I understand it, that's all controled by DMA's from
> > the card anyhow,
> > so not a big deal.

> Huge deal if the delay is longer than a few tens of clock cycles. The AGP
> FIFOs are not very big, and bubbles of the sort of size you are talking
> about are not going to be absorbed by them. So for part of your frame, the
> AGP bus will be sitting idle. And if, as is happening, you are limited by
> AGP speed, that is going to hurt quite a lot.

as long as the gap in the pipeline as it starts fetching the next stream
after a rejection is shorter than the number of cycles it would have taken
to finish the rejected stream, you win. Considering that a cycle = 4
rasterized pixels or so, and that trinagles typically are 4-8x that, and
that arrays are typically 10 tris or more, I think it's not to much of a
worry. Unless it really does take 200 cycles of a ~150mhz part to set
up/redirect the dma.

> > It doesn't rely on frame2frame conherance (which I feel is often a bad
> > thing). Perhaps it would maybe be best with a heirarchical z system.
>
> Doesn't help - you still need to rasterise your pixels, which is a long
way
> down the pipe.

> What's wrong with frame-to-frame coherence? Remember, if there is a camera
> change or cut, the application can simply discard all the visibility info
it
> has and just draw everything, until it has vis information for the new
> camera position.

A couple things.. originally I didn't think this was a big deal, but later
changed... I think making assumptions is bad, and I definately think that
consistant framerate is more important than a high instantanious. Nothings
more annoying than jumping through a portal in a game to get dropped frames
for a few frames before it gets everything sorted out and cached and gets
back up to 60fps (or whatever the target is). Making the granularity of
rejection sub-frame should help avoid this... Also, when you're using an in
engine cinematic approach, it's really annoying when you get a dropped frame
every time the camera cuts.

> No no no. There is no way you could get the _hardware_ to reject state
> change info and texture downloads because of some internally fed-back
state.
> Drivers rely very heavily on persistent state, i.e. not having to send
state
> that doesn't change. If the driver now doesn't know whether the state
change
> info it sent actually made it to the chip's registers or not, that's just
> madness - the driver will go potty trying to figure out what it does and
> doesn't need to send over the bus. Ditto for downloading textures. Since
the
> driver can't know whether the hardware is going to reject the tris or not,
> it always has to do the texture downloads anyway. And if the hardware is
> doing the downloads instead (e.g. AGP or cached-AGP textures), then either
> solution works - the fast-Z-rejection of pixels means those textures never
> get fetched.

Ouch.. hadn't thought much about the driver related issues. However, *if*
state was constant accross a primative, it's not a problem. That would be a
big issue, but I don't think it's insurmountable.

So, maybe I'm foggy on some details.. but I still thing early rejection in
rasterization pipes is a *good thing*tm :).

RE: [Algorithms] portal engines in outdoor environments

[Tom F. <to...@mu...>]

> From: jason watkins [mailto:jas...@po...]
> 
> 
> > But _something_ still has to do the readback. The start of 
> the chips'
> > pipeline still needs to know the results at the framebuffer 
> end before it
> > can decide whether or not to start drawing the triangles. It doesn't
> matter
> > whether the CPU does it or some bit in the T&L section of 
> the chip - it's
> > the same issue - something has to wait for pixels to go 
> most of the way
> down
> > the rendering pipeline. And that's a performance lose.
> 
> Right, of course the rejection logic has to be able to read 
> the relavent
> z's. But, it doesn't have to read the most immediate state of 
> the z.. the
> state a few polygons ago will do fine for a conservative 
> rejection. So I
> don't see where a stall happens, or where there's a 
> performance lose.

That's not the performance hit. You are submitting tris like this:

BeginChunk
Draw tester tris
EndChunk
if ( previous chunk rendered )
{
	Draw real tris
}


The problem is that the if() is being done at the very start of the pipeline
(i.e. the AGP bus - any later and you lose most of the gain), but it needs
to know the results of the rasterisation & Z-test of all the pixels in the
tester tris. That rasterisation and Z-test is comparatively late in the
pipeline on a T&L device (it's early in the rasterisation, but there is a
looooong pipe between the AGP bus and pixel rasterisation). So your pipeline
is going to be completely empty between those two points. That is a huge
pipeline bubble, and if you're doing it more than one or twice a frame, you
are going to lose large amounts of performance.

You may be able to improve things by doing:

for i = 0 to nObjects
{
	BeginChunk(i)
	Draw tester tris
	EndChunk
}
for i = 0 to nObjects
{
	If ( chunk(i) rendered )
	{
		Draw object i
	}
}


But that is a lot of extra hardware to store all that chunk information,
retrieve it and so on. Lots of complexity. There are three very nice things
about the frame-to-frame coherency scheme:

(1) No extra fillrate hit. If the object is invisible, it's the same
fillrate as your scheme. If the object is visible, then you still only draw
it once, not twice as with your scheme.

(2) No extra triangles needed. OK, the bounding box is a pretty small number
of tris, but what if you wanted to do this scheme with lots of smallish
object? Might get significant then.

(3) (and this is the biggie) It is already supported by tons of existing,
normal, shipped, out there hardware. Not some mystical future device. Real,
existing ones that you have probably used.

> Maybe
> the gain is reduce, when you think about how the rejection 
> means there are
> skips in the flow from AGP RAM to the cards local 
> storage/instruction bus,
> but as I understand it, that's all controled by DMA's from 
> the card anyhow,
> so not a big deal.

Huge deal if the delay is longer than a few tens of clock cycles. The AGP
FIFOs are not very big, and bubbles of the sort of size you are talking
about are not going to be absorbed by them. So for part of your frame, the
AGP bus will be sitting idle. And if, as is happening, you are limited by
AGP speed, that is going to hurt quite a lot.

> It doesn't rely on frame2frame conherance (which I feel is often a bad
> thing). Perhaps it would maybe be best with a heirarchical z system.

Doesn't help - you still need to rasterise your pixels, which is a long way
down the pipe.

What's wrong with frame-to-frame coherence? Remember, if there is a camera
change or cut, the application can simply discard all the visibility info it
has and just draw everything, until it has vis information for the new
camera position.

> > Added to which, one of the growing bottlenecks is the AGP 
> bus, and doing
> it
> > this way doesn't help that at all.
> 
> Not directly, well.. not unless your primatives are so large that the
> rejection happens before the primative has entirely streamed 
> into the cards
> local FIFO or whatever. However, done right, it could 
> potencially reduce
> state changes or texture downloads, aleavating some bus 
> bandwidth.

No no no. There is no way you could get the _hardware_ to reject state
change info and texture downloads because of some internally fed-back state.
Drivers rely very heavily on persistent state, i.e. not having to send state
that doesn't change. If the driver now doesn't know whether the state change
info it sent actually made it to the chip's registers or not, that's just
madness - the driver will go potty trying to figure out what it does and
doesn't need to send over the bus. Ditto for downloading textures. Since the
driver can't know whether the hardware is going to reject the tris or not,
it always has to do the texture downloads anyway. And if the hardware is
doing the downloads instead (e.g. AGP or cached-AGP textures), then either
solution works - the fast-Z-rejection of pixels means those textures never
get fetched.

Far better is the delayed system, where the app can choose as well as using
lower-tri models, to force lower mipmap levels as well, to reduce texture
downloads. Or not, if that looks bad. This sort of decision MUST be left up
to the app of course, because there will alsways be cases where a shortcut
looks bad, and only the app can know whether they are acceptable in certain
cases or not.

[snip]

> Especially considering that we're quickly reaching the limits 
> of what fill
> rate can be supported by available memory technologies (at 
> the right price
> that is). And tho embeded dram seems to answer that, it and 
> other possible
> technologies haven't exactly materialized.

Right. But I've already pointed out that the delayed version uses _less_
fillrate than what you are proposing, not more, because the "tester" tris
are the same as the tris actually drawn.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

RE: [Algorithms] BSP-Primitive intersection testing

[Jay S. <Ja...@va...>]

> I think most of the people who
> bevel their BSP's just put the planes in heuristically (that's
> what Stan Melax describes, so far as I can tell).

Yeah, I just read his article.  That's definitely what Melax suggests.
Quake 2 definitely uses the same planes suggested by the separating axis
theorem.

> Obviously, you don't want to treat your whole BSP as a bunch of
> polyhedra and generate separating axes for all those polydra
> against the axial planes.  Off the top of my head, it seems that
> the correct local solution would be to bevel each vert by creating
> new planes on the vertex, with many normals : three from the AABB,
> and 3*n more from the axes of the AABB crossed with the normals
> of the planes that define that vertex in the BSP.  I think you only
> have to add planes which don't intersect the convex volume of the
> leaf you are adding them to.

The extra planes are the planes of the bounding box (unless the particular
leaf already has them) and the planes formed by the cross product of the
edges of each convex solid space and the edges of the AABB.  So the only
planes that bevel the verts are the axial aligned planes iff the solid
doesn't include those.  The other planes all bevel the edges (as the solid
is expanded).  I find it easier to visualize if I think of the BSP as a set
of discrete solid convex polyhedra.

If you computed the constructive planar solid of all of these planes (pushed
out for a particular AABB), it would be equivalent to the surface traced out
by the center of the AABB as you slide the AABB over the surface of the
convex solid - keeping the two in contact at all times.

> 
> For OBB's I guess you could store the information necessary to compute
> the extra planes in each leaf.  Then, after you descend the tree to
> the leaf, the extra planes implicitly exist in the tree at 
> that position,
> and are created based on the orientation of the OBB.  The information
> would need would be the vertices of the convex polyhedron which is the
> leaf, and the planes coincident with those vertices (right?). 
>  You could
> probably get that information implicitly from the BSP, but I'm 
> not enough
> of a BSP whiz to see how to do it quickly.

The problem here is that you need the faces & edges of the convex BSP
solids.  The BSP itself implies these edges, but you'd have to go through a
process like CSG to compute them.  I've done quite a bit of work with BSPs
and I can't think of a reasonable way to get the information from a general
BSP (other than CSG).  Then you'd have to cross those edges with the edges
of the OBB to generate the separating plane normals.

> 
> That is essentially equivalent to just sending the OBB to the 
> leaf, and
> then doing the normal OBB-polyhedron collision test, right?  The only
> difference is that you know you don't need to check the 
> separating axes
> defined by the normals of the polyhedra, because those have 
> already been
> done by walking down the BSP.

This sounds correct, although intuitively it seems likely that you could use
information from the BSP about which faces/edges of the solid touch empty
space to optimize away some of the tests, and beat the more general case.


Jay

Re: [Algorithms] Pixar patent

[jason w. <jas...@po...>]

Thankyou for chasing this down.. this patent has come up numerous times, and
it's nice to know pixar/tony's exact positoin on all this.

Re: [Algorithms] portal engines in outdoor environments

[jason w. <jas...@po...>]

> But _something_ still has to do the readback. The start of the chips'
> pipeline still needs to know the results at the framebuffer end before it
> can decide whether or not to start drawing the triangles. It doesn't
matter
> whether the CPU does it or some bit in the T&L section of the chip - it's
> the same issue - something has to wait for pixels to go most of the way
down
> the rendering pipeline. And that's a performance lose.

Right, of course the rejection logic has to be able to read the relavent
z's. But, it doesn't have to read the most immediate state of the z.. the
state a few polygons ago will do fine for a conservative rejection. So I
don't see where a stall happens, or where there's a performance lose. Maybe
the gain is reduce, when you think about how the rejection means there are
skips in the flow from AGP RAM to the cards local storage/instruction bus,
but as I understand it, that's all controled by DMA's from the card anyhow,
so not a big deal.

It doesn't rely on frame2frame conherance (which I feel is often a bad
thing). Perhaps it would maybe be best with a heirarchical z system.

> Added to which, one of the growing bottlenecks is the AGP bus, and doing
it
> this way doesn't help that at all.

Not directly, well.. not unless your primatives are so large that the
rejection happens before the primative has entirely streamed into the cards
local FIFO or whatever. However, done right, it could potencially reduce
state changes or texture downloads, aleavating some bus bandwidth. Hardware
seems to be moving to complexe primatives that take more local processing to
reduce to fragments anyhow, compressing the information that goes accross
the bus, and the more overhead is associated with each member primative of a
primative array, the more useful a rejection system like this becomes.

So I totally agree that what I suggest isn't a ready to impliment scheme
that should be in nVidia's next card, but I do think that early rejection of
polygon or higher level primatives is a good thing, something that hardware
should be moving toward. This is the same principle in use in the PVR series
of chips, and it certainly seems to work well enough in the dreamcast. I
don't think you should have to resort to the PVR's odd rendering interface
to get the gains of early rejection and deferred texturing tho, and I don't
see how hinting for early rejection can be a bad thing.

Especially considering that we're quickly reaching the limits of what fill
rate can be supported by available memory technologies (at the right price
that is). And tho embeded dram seems to answer that, it and other possible
technologies haven't exactly materialized.

Re: [Algorithms] Contact modeling (was: N-body processing)

[David B. <db...@bt...>]

> I didn't notice it, but you mentioned the face/face contact manifold,
which
> I do not detect. I only handle the four others, two of whom as degenerate
> cases. To make things clear I followed the Baraff's way, including how he
> deals with colliding & resting contacts.
>
> How do you detect the face/face case? It is useful? I guess it might be
> useful to handle the simple case of the cube falling vertically on the
> table...

Face/face contact detection isnt strictly necasery, things should work as
long as you detect all the other types of contact. The reason I detect
face/face contacts is that it can improve stability and provide more
sensible contact normals.

For example if you detect four point/point contacts for two cubes resting
exactly on top of each other, typicaly you would pick the average vertex
normals at the points(since a point/point contact is degenerate). A more
sensible choice is the normal of the contact face(top or bottom face of
cube).

The algorithm which I use to detect contact regions is basically a modified
polygon clipper which tracks features along the way... It outputs face/face
contacts just as easily as the other types.

David

http://www.dblack.btinternet.co.uk
ICQ #: 24402391
Mobile: (UK) 0778 7836188

[Algorithms] Contact modeling (was: N-body processing)

[Pierre T. <p.t...@wa...>]

> determining the contact manifold, which can be two points,  point and
edge,
> edge and edge, point and face or face and face. The contact manifold is
then
> used to determine the collision response.

I didn't notice it, but you mentioned the face/face contact manifold, which
I do not detect. I only handle the four others, two of whom as degenerate
cases. To make things clear I followed the Baraff's way, including how he
deals with colliding & resting contacts.

How do you detect the face/face case? It is useful? I guess it might be
useful to handle the simple case of the cube falling vertically on the
table...

Pierre

Re: [Algorithms] N-body processing

[Pierre T. <p.t...@wa...>]

> I just use a hash table, and a simple modulus hash key(with the polyhedra
> indexes), no performance problems with this and very easy to
> implement(especially when you use STL:-). Objects are stored in an
unsorted
> linked list off each hash entry.
> I don't use the pair table for anything other than caching closest feature
> pairs to improve performance.

Thanks David - as always you provide useful answers.

Re: [Algorithms] portal engines in outdoor environments

[Angel P. <ju...@bi...>]

> .. is a hopeless proposition, I think.  I'd just like you
> guys to check my reasoning before I give up.  Consider,
> for example, a building placed on a landscape.  The goal
> is to construct portals so that when you stand on one
> side of the building, you can't see the other.  If the
> player is constrained to stay on the ground, this is
> easy enough, it's really a 2d occlusion problem, and you
> need 8 portals (two * 4 faces of a square in 2d; two portals
> cuz you need one on each side of a face of the square,
> parrallel to that face) which splits the universe into 9
> zones (8 outside and one inside the occluding cube).
> 
> However, if we have a plain cube in 3d and the player can
> go anywhere around it, we need 48 portals !! (8 for each of
> the 6 faces on the cube).  Now if you have two cubes near
> eachother, you need massive numbers of portals, and they
> must all not intersect with eachother or other geometry.
> This quickly becomes unworkable.

Actually these will be just 12 portals - 4 on the ground plane,
4 on the roof plane and 4 vertical ones. And 6 cells.

The main problem with portalized outdoors is that a portal may be split
into many tiny pieces while it is traversed through the other portals.

Look at the first screenshot at
http://thegeleto.tripod.com/sshots/
and you'll see what I mean.

Consider this picture:
   __________________
  |                  |
  |   Portal A       |
  |                  x1__________________
  |                  |                  |
  |                  |   Portal B       |
  |   _______________|_____________     |
  |  |               |             |    |
  |  |           Portal C          |    |
  |  |               |             |    |
  |  |     Ca        |     Cb      |    |
  |  |               |             |    |
  |  |_______________|_____________|    |
  |                  |                  |
  |__________________x2_________________|

Portals A and B are two adjacent coplanar portals sharing same
edge (x1-x2). Portal C is behind these 2 portals and is split in 2
pieces - Ca and Cb.

The ordinary portal traversal algho will work like this:

-- Create the frustum for portal A.
-- Clip C to this frustum , crete a new frustum from the clipped portal
-- Recurse further through the new frustum
-- Create the frustum for portal B.
-- Clip C to this frustum , crete a new frustum
-- Recurse further through the new frustum

The key to fixing the problem with the many splits is an algho that will work
like this:
-- Create the frustum for portal A : Fa
-- Store the portal edge x1-x2 with the frustum Fa
-- Clip C to this frustum (Fa) , crete a new frustum from the clipped portal :Fac
-- Clip the stored in Fa edge x1-x2 to the new frustum (Fac) and store it in that
frustum. (when clipping the case when x1-x2 lies on a plane will be considered
as if it is in front of the plane )
-- DONT recurse further through the new frustum but rather store it
  inside C
-- Create the frustum for portal B : Fb
-- Store the portal edge x2-x1 with the frustum Fb
-- Clip C to this frustum (Fb) , crete a new frustum from the clipped portal :Fbc
 -- Clip the stored in Fb edge x2-x1 to the new frustum (Fbc) and store it in that
frustum. (when clipping the case when x2-x1 lies on a plane will be considered
as if it is in front of the plane )
-- Clip all edges stored in Fac(currently stored inside C) to Fbc and all edges
stored in Fbc to Fac (when clipping the case when an edge lies on a plane will
be considered as if it is BEHIND the plane!!! )
-- If there are no edges stored in Fac and Fbc (as is in this case because they
were clipped ) - try to merge Fac and Fbc (succesfully in this case) in one
frustum - Fc
-- Recurse further through Fc

While this algho is a lot more complicated it will decrease the portal splitting
in portalized outdoors quite a lot.
I have not tried it yet, and there probably will be many gotchas.

> I think something like a "real-time" occcluder (shadow volumes,
> etc.) is the only hope for outdoors.

You can use a structure of cells connected with occulders instead of portals.
As you traverse the cells you can put these occulders in a beam tree after
clipping them to that tree. To make things faster you can put inside the
beam tree only edges shared by 2 polygons one of which is backface culled
and the other isn't. At each cell the beam tree will be used to determine the
visible polygons. The process ends when there are no edges left in the beam
tree. It's a good optimization the remove the beam tree nodes that contain no
edges (after the clipping to a new occulder these edges were removed) when
possible (this will not be possible when both node->front and node->back
are not NULL). So if this optimization is used - the process will end when the
beam tree collapses (e.g. all nodes are deleted). This beam-tree approach
can be easily combined with conventional portals.
But this sounds too complicated to me and probably it won't be faster than the
above portal approach.

With both alghos you will have to deal with too many portals/occulders.


> --------------------------------------
> Charles Bloom           www.cbloom.com
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] portal engines in outdoor environments

[Tom F. <to...@mu...>]

But _something_ still has to do the readback. The start of the chips'
pipeline still needs to know the results at the framebuffer end before it
can decide whether or not to start drawing the triangles. It doesn't matter
whether the CPU does it or some bit in the T&L section of the chip - it's
the same issue - something has to wait for pixels to go most of the way down
the rendering pipeline. And that's a performance lose.

Added to which, one of the growing bottlenecks is the AGP bus, and doing it
this way doesn't help that at all.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: jason watkins [mailto:jas...@po...]
> Sent: 18 August 2000 21:24
> To: gda...@li...
> Subject: Re: [Algorithms] portal engines in outdoor environments
> 
> 
> Better would be a pipeline that allows you to specify some 
> sort of simple
> bounding volume for each primative (ie, each index array, 
> display list,
> whatever). You could build these volumes with no overhead in 
> most games, and
> providing hardware with the hint would allow it to estimate 
> if the entire
> primative is obscured, in which case it simply skips the 
> entire primative.
> 
> This would require finer grained primatives.. which I guess 
> is sort of on
> the out in these geforce days... but I do imagine that for arrays of
> moderate size, in the 100's of trys, that the driver buffers 
> and is already
> looking at the next set. So, it's not exactly a perfect 
> solution, but it
> seems a relatively simple feature, and avoids the necessity 
> of a readback to
> application level.
[snip]

RE: [Algorithms] portal engines in outdoor environments

[Tom F. <to...@mu...>]

Though this is synchronous - you cannot queue results up, so you need to
wait for the pipe to empty before getting the result, and can't do anything
in the meantime. Which is the whole point of _delayed_ Z-visible - you can
draw a frame with hundreds of objects being vis-checked, and then a frame or
two later you read all those results (while the next frame, with more vis
checks, is being rendered).

Unless you can send multiple vis requests down the pipe and read them as
they come out, you'll be stalling the hardware and software waiting for your
results, which rather removes the point of using it for higher frame rates!

Apart from that, it's the same idea.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Bernd Kreimeier [mailto:bk...@lo...]
> Sent: 18 August 2000 20:31
> To: gda...@li...
> Subject: RE: [Algorithms] portal engines in outdoor environments
> 
> 
> John Ratcliff writes:
>  > If you had the ability to ask questions of the zbuffer 
> like "is this
>  > bounding volume visable?" (yes/no) in an extremely high 
> speed fashion then
>  > you could do gross culling on an object by object basis 
> using the zbuffer
>  > contents during the render stage.  Some of the old 
> spanbuffer software
>  > renderers could do this, because it was a fairly cheap 
> question to ask,
>  > especially relative to the time it took to software render 
> an entire 3d
>  > model.
>  > 
>  > But, since you can't ask zbuffers these kinds of questions 
> it's a moot
>  > point.
> 
> 
> http://oss.sgi.com/projects/ogl-sample/registry/HP/occlusion_test.txt
> 
> Brian Paul mentioned that he is going to add that to Mesa
> using the Glide GR_STATS counters. I have no idea which Win32
> drivers offer this extension.

RE: [Algorithms] portal engines in outdoor environments

[Tom F. <to...@mu...>]

We're talking two or three frames at most, and usually one to two I would
expect. If a device is buffering any more than this, then the display is
going to be lagging beind the input so much that the game becomes very hard
to play (for a good illustration, try running Half-Life in D3D mode on an
nVidia card - grrrrr).

And you always have to render _something_ - that's how you get your
visibility info back! True, you could possibly render using a ZERO:ONE blend
mode, but I don't think it will save you all that much fillrate, and it will
pop in a very grim way.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: gl [mailto:gl...@nt...]
> Sent: 18 August 2000 19:28
> To: gda...@li...
> Subject: Re: [Algorithms] portal engines in outdoor environments
> 
> 
> 
> As I understand it, the idea with delayed z-testing is that 
> whilst it's
> horribly slow to get 'did this primitive I just tried to 
> render get totally
> z-rejected?' feedback from the card instantly (due to deep 
> pipelining going
> on), it's reasonable to get that info back a few frames late without
> stalling anything.
> 
> The idea is to have that info determine your objects' LOD, 
> ie. you render
> your object with a low LOD by default, unless you find out 
> that thing is now
> visible, when you can bump up the tri count.  As the data is 
> delayed, there
> will be a change from low to hi LOD, but as we're only 
> talking a few frames
> (I believe), this shouldn't be all that noticable.  Note that 
> you can't
> simply avoid drawing the object, due to the delay - 
> otherwise, it would
> suddenly appear, a few frames later than it should.
> 
> In fact, my contention is that if it's only as little as two or three
> frames, the higher rates you run at, the less significant the 
> delay gets, to
> the point were you probably don't even see the LOD pop, or 
> you might not
> even need to render until you're told it's there.
> 
> Tom, how many frames exactly would we be talking about?
> --
> gl

Re: [Algorithms] BSP-Primitive intersection testing

[Angel P. <ju...@bi...>]

You can just test the individual polygons of the mesh ( a low
LOD representation of your model ) against the BSP tree.
It's quite fast and very simple to do.

And there's fast and easy (although not quite trivial) way to find
the intersection shape and the normals at each vertex in that
shape of the 2 colliding objects. Tell me if you need more info
on this.

You can speed this algho by first doing a quick test just with the
vertices of the mesh.

Here's the code:

bool CBSPNode::PolygonColiides( CPolygon &P )
{
 CBSPNode *Node=this;
 while( 1 )
 {
  int side = P.PlaneSide( Node->SplitPlane );
  switch( side )
  {
  case SIDE_Front:
   {
    if( Node->Front==NULL )
     retrun false;//no collision
    Node=Node->Front;
   }
  case SIDE_Behind:
   {
    if( Node->Back==NULL )
     retrun true;//collision
    Node=Node->Back;
   }
  case SIDE_Intersect:
   {
    CPolygon FrontP, BackP;
    P.Split( Node->SplitPlane, FrontP, BackP );

    if( Node->Front!=NULL && Node->Front->PolygonCollides( FrontP ) )
      return true;//collision

    if( Node->Back==NULL || Node->Back->PolygonCollides( BackP ) )
      return true;//collision

    return false;//no collision
   }
  }
 }
}


> 
> Is there a fast and correct way to ask a BSP if it
> intersects with a primitive (AABB or sphere, for example) ?
> 
> The context of this question is the traditional hack
> which all the BSP-based games used.  They use a collision
> detection scheme where they take a primitive, and send it
> down the tree as if it were a point, but shift the BSP planes
> by the radius of the primitive in the direction of the
> plane's normal.  The problem with this test is that it just
> doesn't work near corners where planes intersect.  Many
> people are under the false impression that if you put
> extra "cap" planes on your leaves it will fix the problem,
> and while it certainly greatly decreases the error (because
> the error is roughly proportional to the angle difference
> of the joint, so adding more planes at a joint smooths out
> the error), the problem does remain.
> 
> Of course, you can test an AABB against a BSP exactly by sending
> the polygons of the AABB down the bsp tree and doing the full
> polygon clipping shish-poo-bah, but that seems a rather expensive
> way to an AABB-in-region test.
> 
> Using "cap planes" the error can be controlled, and you can
> make sure that the error is conservative (returns more
> intersections) so perhaps that's the best solution - be approximate.
> 
> --------------------------------------
> Charles Bloom           www.cbloom.com
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Triangle area.

[Eric L. <le...@C4...>]

> This is something very simple (I think)... I need the fastest way to find
> the area of a triangle.

For an arbitrary triangle expressed by three points in space, P1, P2, and
P3, the area is given by

    area = 0.5 * Magnitude(CrossProduct(P2 - P1, P3 - P1));

-- Eric Lengyel

Re: [Algorithms] portal engines in outdoor environments

[Conor S. <cs...@tp...>]

I happen to agree. I'm with John Ratcliff on this though. A precomputed
system. I think I've actually come up with a decent system, that takes LoD
etc into account. This is the problem with precalc'd vis on current systems.

Firstly, the minimum occlusion zone after LoD, is the convex shell of the
bottom of the landscape occluder. Fairly easy.

I use a vertical c-buffer style implementation, with back to front sorting,
similar to Fredo Durand's precalculated occlusion using extend projections
(although, you
could use height intersections of extreme stabbing lines). I then store the
minimum height visible for each node, and make a sort of collapsed balanced
binary tree, which can be sorted by height. Storage is fairly compact (each
node in the tree only contains newly visible objects for that node. The ones
below it are used to find the other information. The tree is split into
nodes between the lowest height of the current visibility node.

For 16*16 sized grid nodes per visibility node, the storage is below 100k in
most instances. (Note, this method is also quickest lower to the ground, and
is slightly
conservative, but accurate enough).

This method should do fairly well in most reasonable cases.

Conor Stokes


>
> .. is a hopeless proposition, I think.  I'd just like you
> guys to check my reasoning before I give up.  Consider,
> for example, a building placed on a landscape.  The goal
> is to construct portals so that when you stand on one
> side of the building, you can't see the other.  If the
> player is constrained to stay on the ground, this is
> easy enough, it's really a 2d occlusion problem, and you
> need 8 portals (two * 4 faces of a square in 2d; two portals
> cuz you need one on each side of a face of the square,
> parrallel to that face) which splits the universe into 9
> zones (8 outside and one inside the occluding cube).
>
> However, if we have a plain cube in 3d and the player can
> go anywhere around it, we need 48 portals !! (8 for each of
> the 6 faces on the cube).  Now if you have two cubes near
> eachother, you need massive numbers of portals, and they
> must all not intersect with eachother or other geometry.
> This quickly becomes unworkable.
>
> I think something like a "real-time" occcluder (shadow volumes,
> etc.) is the only hope for outdoors.
>
> --------------------------------------
> Charles Bloom           www.cbloom.com
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] Pixar patent

[Corrinne Y. <cor...@ho...>]

-- The following is _on topic_, not an argument against patent! :)

-- Spoke to Tony and Tony.

-- 1. Tony De Rose (the guy on the patent) says that subdivision itself is
extremely old, and that it is not patented in anyway, and they had not and
will not ever patent subdivision itself.

-- 2. He also said what the patent was applied for was _not_ the obvious
texture coordinates interpolation, nor were it straight from the 1998
SIGGRAPH paper (it is work in extension), and yes the paper did cover an
efficient tex gen interpolation, and that is _not_ what he patented (but his
extension).

-- 3. The extension he developed then patented is in his opinion too time
consumingly overkill for interactive apps anyway, and it is safe for all of
us to use subdivision, and it is safe for all of us to do tex gen
interpolation.

-- 4. Even then, he is more than happy to share his work, in subsequent
SIGGRAPH papers formally, or before then, just explain the mechanism to me
and Tony (A) (then I post it here), after they are off crunch mode (probably
on some nifty Pixar short films or other cool things :D ). And that _if_
game app programmers do find any interactive use for this, that Pixar as a
company has no problem licensing even this particular technique out for free
to us.

-- Now I am only a programmer and not a lawyer, so I don't know how the
above (what Tony De Rose says) correlates to the patents below.

-- But since I am a programmer and not a lawyer, I am very much looking
forward of the (describedly more convoluted) tex gen description and
explanation which is an extension of his 98 SIGGRAPH paper. When he would
tell me and explain the whole thing to me, I don't know yet. :(

Corrinne




----- Original Message -----
From: "Peter Warden" <Pet...@vi...>
To: <gda...@li...>
Sent: Tuesday, August 08, 2000 5:18 AM
Subject: [Algorithms] Pixar patent


> For anybody else who's interested, the patent number is 6,037,949, and you
> can look at the patent at http://www.uspto.gov/patft/index.html

[Algorithms] Triangle area.

[Oscar B. <tr...@te...>]

Hi,

This is something very simple (I think)... I need the fastest way to
find the area of a triangle.

Thanks,

Oscar.

RE: [Algorithms] BSP-Primitive intersection testing

[Charles B. <cb...@cb...>]

Hi Jay,

Hmm, you are of course correct that you can use separating-axis,
I'd never thought of that way; I think most of the people who
bevel their BSP's just put the planes in heuristically (that's
what Stan Melax describes, so far as I can tell).

Obviously, you don't want to treat your whole BSP as a bunch of
polyhedra and generate separating axes for all those polydra
against the axial planes.  Off the top of my head, it seems that
the correct local solution would be to bevel each vert by creating
new planes on the vertex, with many normals : three from the AABB,
and 3*n more from the axes of the AABB crossed with the normals
of the planes that define that vertex in the BSP.  I think you only
have to add planes which don't intersect the convex volume of the
leaf you are adding them to.

For OBB's I guess you could store the information necessary to compute
the extra planes in each leaf.  Then, after you descend the tree to
the leaf, the extra planes implicitly exist in the tree at that position,
and are created based on the orientation of the OBB.  The information
would need would be the vertices of the convex polyhedron which is the
leaf, and the planes coincident with those vertices (right?).  You could
probably get that information implictly from the BSP, but I'm not enough
of a BSP whiz to see how to do it quickly.

That is essentially equivalent to just sending the OBB to the leaf, and
then doing the normal OBB-polyhedron collision test, right?  The only
difference is that you know you don't need to check the separating axes
defined by the normals of the polyhedra, because those have already been
done by walking down the BSP.

At 05:03 PM 8/18/2000 -0700, you wrote:
>I'm not sure what errors you are talking about.  If you apply the separating
>axis theorem, you can compute all of the necessary separating axes to
>determine intersection.  As long as you "bevel" using the entire set of
>planes, this will be as correct as the separating axis theorem.  Unless
>there is something I misunderstand about this (I'd love to learn something
>new), it's possible to exactly detect intersection between a BSP and an AABB
>using this method.  Also, as long as all of your BSP doesn't rotate, and the
>world axes are constant, it should be possible to precalcuate all of the
>separating planes.  Obviously for OBBs or rotated BSPs, you'll have to
>calculate the separating planes at runtime as they are dependent on the
>coordinate systems involved.
>
>Charles, I don't understand your description of the "cap planes" problem
>below.  To the best of my understanding, these "cap planes" or "bevels" must
>coincide exactly with the planes given by the separating axis theorem -
>since they are the surface of the manifold of collision.  After all, a
>closed BSP tree is equivalent to a collection of convex polyhedra (each
>solid leaf is one of these), and you can certainly use the separating axis
>theorem to collide AABBs with those polyhedra treated as individual objects,
>so why is this different?
>

--------------------------------------
Charles Bloom           www.cbloom.com

RE: [Algorithms] BSP-Primitive intersection testing

[Feltman, H. <Fe...@se...>]

You're right, the BSP itself can't be used for AABB using the
plane expansion method because during expansion, the
planes would intersect and cause all kinds of problems.

Quake1 used pre-expanded "hulls"; take all the brushes,
expand the planes according to the current AABBox size,
add axial planes which aren't in the brush already (you refer
to these as "cap-planes"?) , and re-compile a BSP. Quake1
only had 3 hull sizes: one for the players bbox, one for large
monsters, and the BSP itself used for bullets (lines).
To trace an AABB through this new world only requires tracing a
line so you can see how fast this method really is.

Quake2 stores the brushes themselves for real-time expansion
(any AABB size is accommodated).

The current project I'm working on uses realtime-expanded-
rotated-convex-brush-collision-detection, It's definitely a very
simple and fast method.

-Hamilton

Hamilton Feltman
SEGA[WOW/ARCADE]
www.sega.com/alienfront

> -----Original Message-----
> From:	Charles Bloom [SMTP:cb...@cb...]
> Sent:	Friday, August 18, 2000 3:44 PM
> To:	gda...@li...
> Subject:	[Algorithms] BSP-Primitive intersection testing
> 
> 
> Is there a fast and correct way to ask a BSP if it
> intersects with a primitive (AABB or sphere, for example) ?
> 
> The context of this question is the traditional hack
> which all the BSP-based games used.  They use a collision
> detection scheme where they take a primitive, and send it
> down the tree as if it were a point, but shift the BSP planes
> by the radius of the primitive in the direction of the
> plane's normal.  The problem with this test is that it just
> doesn't work near corners where planes intersect.  Many
> people are under the false impression that if you put
> extra "cap" planes on your leaves it will fix the problem,
> and while it certainly greatly decreases the error (because
> the error is roughly proportional to the angle difference
> of the joint, so adding more planes at a joint smooths out
> the error), the problem does remain.
> 
> Of course, you can test an AABB against a BSP exactly by sending
> the polygons of the AABB down the bsp tree and doing the full
> polygon clipping shish-poo-bah, but that seems a rather expensive
> way to an AABB-in-region test.
> 
> Using "cap planes" the error can be controlled, and you can
> make sure that the error is conservative (returns more
> intersections) so perhaps that's the best solution - be approximate.
> 
> --------------------------------------
> Charles Bloom           www.cbloom.com
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] N-body processing

[David B. <db...@bt...>]

> Now, my concern is this: how do I track the possible colliding pairs? How
do
> I store them? How do I handle them? For the moment Adam seems to be the
only
> one who actually understood the problem: that's why he introduced the
sparse
> matrices.


I just use a hash table, and a simple modulus hash key(with the polyhedra
indexes), no performance problems with this and very easy to
implement(especially when you use STL:-). Objects are stored in an unsorted
linked list off each hash entry.
I don't use the pair table for anything other than caching closest feature
pairs to improve performance.

When you actually detect that there has been a collision, i.e. the closest
distance algo returns something smaller than your epsilon. You need to look
at the features(verts, edges or faces) surrounding the closest points and
determine if they are as close to each other as the closest points. This is
determining the contact manifold, which can be two points,  point and edge,
edge and edge, point and face or face and face. The contact manifold is then
used to determine the collision response.

David

http://www.dblack.btinternet.co.uk
ICQ #: 24402391
Mobile: (UK) 0778 7836188

RE: [Algorithms] BSP-Primitive intersection testing

[Jay S. <Ja...@va...>]

I'm not sure what errors you are talking about.  If you apply the separating
axis theorem, you can compute all of the necessary separating axes to
determine intersection.  As long as you "bevel" using the entire set of
planes, this will be as correct as the separating axis theorem.  Unless
there is something I misunderstand about this (I'd love to learn something
new), it's possible to exactly detect intersection between a BSP and an AABB
using this method.  Also, as long as all of your BSP doesn't rotate, and the
world axes are constant, it should be possible to precalcuate all of the
separating planes.  Obviously for OBBs or rotated BSPs, you'll have to
calculate the separating planes at runtime as they are dependent on the
coordinate systems involved.

NOTE: I haven't read the articles mentioned below, so when I say "this
method" I'm talking about the plane shifting method in general.  Also, this
doesn't apply to spheres because the manifold of collision (is there a term
for this?) does not have planar surfaces.

Charles, I don't understand your description of the "cap planes" problem
below.  To the best of my understanding, these "cap planes" or "bevels" must
coincide exactly with the planes given by the separating axis theorem -
since they are the surface of the manifold of collision.  After all, a
closed BSP tree is equivalent to a collection of convex polyhedra (each
solid leaf is one of these), and you can certainly use the separating axis
theorem to collide AABBs with those polyhedra treated as individual objects,
so why is this different?

Jay

> -----Original Message-----
> From: Charles Bloom [mailto:cb...@cb...]
> Sent: Friday, August 18, 2000 4:30 PM
> To: gda...@li...
> Subject: Re: [Algorithms] BSP-Primitive intersection testing
> 
> 
> 
> That's a good writeup of the approximate method which I describe,
> where the error can be limited by bevelling corners, but never
> eliminated.
> 
> For historical accuracy, I believe that method was known to Naylor
> and all the old-school BSP gurus.  I heard a story that Carmack came
> up with the plane-shifting trick for Quake and was delighted with
> himself, and then one of the old computer graphics guys pointed
> out that they'd been doing it for years...
> 
> At 04:04 PM 8/18/2000 -0700, you wrote:
> >This is a paper that supposedly deals with that issue (by 
> plane shifting;
> >you probably have seen it already), but I haven't read it thoroughly:
> >
> >http://www.cs.ualberta.ca/~melax/bsp/
> >
> >In a way, I'm dealing with the same problem, because I want 
> to do a full
> >simulation of rigid bodies in a bsp tree based world.  I 
> don't want to
> >pass every point down the bsp tree, but a spherical bounding 
> volume might
> >cull enough rigid bodies to make it okay.
> >
> >Will
> >
> >----
> >Will Portnoy
> >http://www.cs.washington.edu/homes/will
> >
> >On Fri, 18 Aug 2000, Charles Bloom wrote:
> >
> >> 
> >> Is there a fast and correct way to ask a BSP if it
> >> intersects with a primitive (AABB or sphere, for example) ?
> >> 
> >> The context of this question is the traditional hack
> >> which all the BSP-based games used.  They use a collision
> >> detection scheme where they take a primitive, and send it
> >> down the tree as if it were a point, but shift the BSP planes
> >> by the radius of the primitive in the direction of the
> >> plane's normal.  The problem with this test is that it just
> >> doesn't work near corners where planes intersect.  Many
> >> people are under the false impression that if you put
> >> extra "cap" planes on your leaves it will fix the problem,
> >> and while it certainly greatly decreases the error (because
> >> the error is roughly proportional to the angle difference
> >> of the joint, so adding more planes at a joint smooths out
> >> the error), the problem does remain.
> >> 
> >> Of course, you can test an AABB against a BSP exactly by sending
> >> the polygons of the AABB down the bsp tree and doing the full
> >> polygon clipping shish-poo-bah, but that seems a rather expensive
> >> way to an AABB-in-region test.
> >> 
> >> Using "cap planes" the error can be controlled, and you can
> >> make sure that the error is conservative (returns more
> >> intersections) so perhaps that's the best solution - be 
> approximate.
> >> 
> >> --------------------------------------
> >> Charles Bloom           www.cbloom.com
> >> 

[Algorithms] BSP-Primitive intersection testing

[Bernd K. <bk...@lo...>]

Charles Bloom writes:
 > Using "cap planes" the error can be controlled, and you can
 > make sure that the error is conservative (returns more
 > intersections) so perhaps that's the best solution - be approximate.

I can also see benefit in decoupling rendering geometry 
detail from collision geometry. Esp. with hardware T&L 
you don't want the CPU to have to push the same scene
geometry. Then there's POV-dependend dynamic LOD in 
multi-POV/player. If hardware support for tesselation 
should hit us, it'll be even worse.

                                         b.

Re: [Algorithms] BSP-Primitive intersection testing

[Charles B. <cb...@cb...>]

That's a good writeup of the approximate method which I describe,
where the error can be limited by bevelling corners, but never
eliminated.

For historical accuracy, I believe that method was known to Naylor
and all the old-school BSP gurus.  I heard a story that Carmack came
up with the plane-shifting trick for Quake and was delighted with
himself, and then one of the old computer graphics guys pointed
out that they'd been doing it for years...

At 04:04 PM 8/18/2000 -0700, you wrote:
>This is a paper that supposedly deals with that issue (by plane shifting;
>you probably have seen it already), but I haven't read it thoroughly:
>
>http://www.cs.ualberta.ca/~melax/bsp/
>
>In a way, I'm dealing with the same problem, because I want to do a full
>simulation of rigid bodies in a bsp tree based world.  I don't want to
>pass every point down the bsp tree, but a spherical bounding volume might
>cull enough rigid bodies to make it okay.
>
>Will
>
>----
>Will Portnoy
>http://www.cs.washington.edu/homes/will
>
>On Fri, 18 Aug 2000, Charles Bloom wrote:
>
>> 
>> Is there a fast and correct way to ask a BSP if it
>> intersects with a primitive (AABB or sphere, for example) ?
>> 
>> The context of this question is the traditional hack
>> which all the BSP-based games used.  They use a collision
>> detection scheme where they take a primitive, and send it
>> down the tree as if it were a point, but shift the BSP planes
>> by the radius of the primitive in the direction of the
>> plane's normal.  The problem with this test is that it just
>> doesn't work near corners where planes intersect.  Many
>> people are under the false impression that if you put
>> extra "cap" planes on your leaves it will fix the problem,
>> and while it certainly greatly decreases the error (because
>> the error is roughly proportional to the angle difference
>> of the joint, so adding more planes at a joint smooths out
>> the error), the problem does remain.
>> 
>> Of course, you can test an AABB against a BSP exactly by sending
>> the polygons of the AABB down the bsp tree and doing the full
>> polygon clipping shish-poo-bah, but that seems a rather expensive
>> way to an AABB-in-region test.
>> 
>> Using "cap planes" the error can be controlled, and you can
>> make sure that the error is conservative (returns more
>> intersections) so perhaps that's the best solution - be approximate.
>> 
>> --------------------------------------
>> Charles Bloom           www.cbloom.com
>> 
>> 
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>> 
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
--------------------------------------
Charles Bloom           www.cbloom.com

Re: [Algorithms] BSP-Primitive intersection testing

[Will P. <wi...@cs...>]

This is a paper that supposedly deals with that issue (by plane shifting;
you probably have seen it already), but I haven't read it thoroughly:

http://www.cs.ualberta.ca/~melax/bsp/

In a way, I'm dealing with the same problem, because I want to do a full
simulation of rigid bodies in a bsp tree based world.  I don't want to
pass every point down the bsp tree, but a spherical bounding volume might
cull enough rigid bodies to make it okay.

Will

----
Will Portnoy
http://www.cs.washington.edu/homes/will

On Fri, 18 Aug 2000, Charles Bloom wrote:

> 
> Is there a fast and correct way to ask a BSP if it
> intersects with a primitive (AABB or sphere, for example) ?
> 
> The context of this question is the traditional hack
> which all the BSP-based games used.  They use a collision
> detection scheme where they take a primitive, and send it
> down the tree as if it were a point, but shift the BSP planes
> by the radius of the primitive in the direction of the
> plane's normal.  The problem with this test is that it just
> doesn't work near corners where planes intersect.  Many
> people are under the false impression that if you put
> extra "cap" planes on your leaves it will fix the problem,
> and while it certainly greatly decreases the error (because
> the error is roughly proportional to the angle difference
> of the joint, so adding more planes at a joint smooths out
> the error), the problem does remain.
> 
> Of course, you can test an AABB against a BSP exactly by sending
> the polygons of the AABB down the bsp tree and doing the full
> polygon clipping shish-poo-bah, but that seems a rather expensive
> way to an AABB-in-region test.
> 
> Using "cap planes" the error can be controlled, and you can
> make sure that the error is conservative (returns more
> intersections) so perhaps that's the best solution - be approximate.
> 
> --------------------------------------
> Charles Bloom           www.cbloom.com
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

[Algorithms] BSP-Primitive intersection testing

[Charles B. <cb...@cb...>]

Is there a fast and correct way to ask a BSP if it
intersects with a primitive (AABB or sphere, for example) ?

The context of this question is the traditional hack
which all the BSP-based games used.  They use a collision
detection scheme where they take a primitive, and send it
down the tree as if it were a point, but shift the BSP planes
by the radius of the primitive in the direction of the
plane's normal.  The problem with this test is that it just
doesn't work near corners where planes intersect.  Many
people are under the false impression that if you put
extra "cap" planes on your leaves it will fix the problem,
and while it certainly greatly decreases the error (because
the error is roughly proportional to the angle difference
of the joint, so adding more planes at a joint smooths out
the error), the problem does remain.

Of course, you can test an AABB against a BSP exactly by sending
the polygons of the AABB down the bsp tree and doing the full
polygon clipping shish-poo-bah, but that seems a rather expensive
way to an AABB-in-region test.

Using "cap planes" the error can be controlled, and you can
make sure that the error is conservative (returns more
intersections) so perhaps that's the best solution - be approximate.

--------------------------------------
Charles Bloom           www.cbloom.com