[Algorithms] BSP bevelling

[Jorrit Rouwe]

Hello,

Does anyone have an efficient algorithm for generating the bevelling planes
for a BSP as described in "Dynamic Plane Shifting Traversal" by Stan Melax?
Preferably one that can dynamically generate the planes to save memory.

Currently, as a preprocessing step, I use the following algorithm:

- Go down the tree and keep track of all splitting planes and do the
following for each solid node:
- Check the angle between each pair of the accumulated planes and possibly
generate a bevelling plane (based on angle between the planes).
- Discard planes that do not touch a vertex of the convex volume the node
describes.
- I don't consider vertices that are not on the BSP boundary because they
would generate bevelling planes that have no effect when shifted.

It works, but in some cases it generates a few extra planes, and it is too
slow for realtime use (O(N^3) where N = number of splitting planes).

Jorrit.

Jorrit Rouwé | Programmer

Lost Boys Games | Prins Hendrikkade 139 | 1011AS Amsterdam The Netherlands
Tel: [phone] | Fax: [phone] | ***@games.lostboys.com
Amsterdam | Barcelona | Berlin | London | Madrid | Paris | San Francisco |
Warsaw | Zurich | www.games.lostboys.com

[Jay Stelly]

The bevel planes are the potential separating axes. You want to take the
cross product of each box edge with the BSP edges to find the bevel planes
for a box. For an ideal sphere or cylinder, it isn't possible to find the
exact planes as the collision manifold is a curved surface. So you could
approximate it with some of the planes that are tangent to the actual curved
surface. In that case, your collisions will be wrong (object will collide
too far away) where the object hits an edge of the BSP geometry, but you can
refine problem cases by more closely approximating the curved surface with
planes.

Jay

-----Original Message-----
Sent: Wednesday, December 12, 2001 1:35 AM
To: gdalgorithms
Subject: [Algorithms] BSP bevelling
Hello,
Does anyone have an efficient algorithm for generating the
bevelling planes
for a BSP as described in "Dynamic Plane Shifting Traversal"
by Stan Melax?
Preferably one that can dynamically generate the planes to
save memory.
- Go down the tree and keep track of all splitting planes and do the
- Check the angle between each pair of the accumulated planes
and possibly
generate a bevelling plane (based on angle between the planes).
- Discard planes that do not touch a vertex of the convex
volume the node
describes.
- I don't consider vertices that are not on the BSP boundary
because they
would generate bevelling planes that have no effect when shifted.
It works, but in some cases it generates a few extra planes,
and it is too
slow for realtime use (O(N^3) where N = number of splitting planes).
Jorrit.
Jorrit Rouwé | Programmer
Lost Boys Games | Prins Hendrikkade 139 | 1011AS Amsterdam
The Netherlands
Tel: [phone] | Fax: [phone] |
Amsterdam | Barcelona | Berlin | London | Madrid | Paris |
San Francisco |
Warsaw | Zurich | www.games.lostboys.com
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

[Melax, Stan]

Rather than checking every possible pair of planes
at the leaf, it would be beneficial if you could
get some representation of a convex polyhedron at
each leaf. (This would be the volume that is the
intersection of all the half spaces from the planes
from the rootnode along the path to the current leaf
in your tree.) The edges on this convex polyhedron
are the only ones you have to worry about when bevelling.


In the past I statically did this as a preprocessing
step and just added nodes to the tree. It was a pretty
elegant way of solving certain collision problems.
But this doesn't work when you add geomod (boolean operations)
which change the geometry on the fly (http://www.melax.com/csg).
When rewriting all the code and I decided to just
generates these planes dynamically now.
The (non-rotating) avatar/character/cylinder collision
with the envrionment seems pretty good. People
seem to be able to blow holes in walls and walk
through them without getting stuck by some "invisible force".
(I still have some bugs in my object-to-environment
collision detection). The point I wanted to make is
that doing the bevelling on the fly is a viable option.
Refer to Jay's post for determining which planes to
generate. Hmmm, i'm starting to babble. I'll just end
this posting now.


stan

-----Original Message-----
Sent: Wednesday, December 12, 2001 1:35 AM
To: gdalgorithms
Subject: [Algorithms] BSP bevelling
Hello,
Does anyone have an efficient algorithm for generating the
bevelling planes
for a BSP as described in "Dynamic Plane Shifting Traversal"
by Stan Melax?
Preferably one that can dynamically generate the planes to
save memory.
- Go down the tree and keep track of all splitting planes and do the
- Check the angle between each pair of the accumulated planes
and possibly
generate a bevelling plane (based on angle between the planes).
- Discard planes that do not touch a vertex of the convex
volume the node
describes.
- I don't consider vertices that are not on the BSP boundary
because they
would generate bevelling planes that have no effect when shifted.
It works, but in some cases it generates a few extra planes,
and it is too
slow for realtime use (O(N^3) where N = number of splitting planes).
Jorrit.
Jorrit Rouwé | Programmer
Lost Boys Games | Prins Hendrikkade 139 | 1011AS Amsterdam
The Netherlands
Tel: [phone] | Fax: [phone] |
Amsterdam | Barcelona | Berlin | London | Madrid | Paris |
San Francisco |
Warsaw | Zurich | www.games.lostboys.com
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

[Jorrit Rouwe]

First of all, thanks for the response.

* Stan: Are you computing these polyhedra on the fly? That seems very
expensive. Storing them in the solid nodes seems very expensive memory wise.

Assuming you only keep track of the polygons (no connectivity), you could
store a single polygon in every BSP node which will be the intersection
between the splitting plane and the convex volume of that node. But then you
would still have to clip these polygons to every subsequent splitting plane
along the path to get the correct representation in one of the solid leaf
nodes.
Not storing a polygon in every node would mean even more clipping.

After that every edge is exactly twice in the set of polygons, so you would
have to figure out a way to discard those duplicates. You could discard
edges of backfacing polygons I guess to reduce the number of possible edges
(is this true??), but that would not get all of them.

How does your algorithm work?

B.t.w. the csg demo is very cool!


* Jay: I understand the way you would generate all possible separating axis
for collision detection with a box. But unfortunately I'm working with
spheres right now.

Should I for example take all planes that are tangent to the surface of the
sphere and parallel to an edge of the polyhedron as possible separating
planes?

I don't quite get the refinement process you describe.

Jorrit.

[Charles Bloom]

The standard way to do Sphere-BSP collision detection is to query the
BSP with the Sphere's center, and push out all the planes by the radius
of the sphere. Of course, this is wrong, it over-estimates collisions
at any convex edge in the collision hull. Nonetheless, it works pretty
well in practice. You can improve it by adding bevel planes at any
convex joint.

Note that this differs from Jay's proposal of using a polygonal approximation
of the sphere and sending that down. In fact, I believe this is equivalent
to using a polygonal approximation of the sphere built by bounding it with
the planes which are in the leaf you end up checking against.

The best way to bevel the BSP for this operation is to take any convex
angle in the hull bigger than a certain tolerance (say, 280 degrees) and
add a plane which lies on that edge and bisects the angle. You only ever
need do this once (eg. it's not recursive), since a tolerance less than 180
is not needed.

Post by Jorrit Rouwe
* Jay: I understand the way you would generate all possible separating axis
for collision detection with a box. But unfortunately I'm working with
spheres right now.
Should I for example take all planes that are tangent to the surface of the
sphere and parallel to an edge of the polyhedron as possible separating
planes?
I don't quite get the refinement process you describe.

-------------------------------------------------------
Charles Bloom ***@cbloom.com http://www.cbloom.com

[Melax, Stan]

To do geomod (via bsp merging)...
Not only do I store the convex
polyhedron at each leaf, I also
store a convex polyhedron at
each interior node in the BSP.

Does it use a lot of memory?
Yeah, that might be an issue.
Its just a little demo.
I haven't used full BSP merging
in a real application or
game. Not yet anyway. :-)

I believe that the guys at
Volition (Red Faction) used
a very different approach
to geomod than what I did.
Like anything, there are
probably pros and cons for
each method.

Back on topic...
If you're just doing sphere
to environment collision
detection, you might be able to
get away with just storing a
few extra planes at the leaves.
It worked pretty good for mdk2.

BTW: I dont want to "push" BSP's on anyone.
For example, if you can bang off
a simple robust AABB implementation in a day,
and it does what you need, then why
not just use that? BSP algorithms can
be harder to understand and implement.
Every technology (BSP, aabb, obb,
loose octtree, etc.) has advantages and
disadvantages.
When deciding, ignore any religious based
arguments in favor of technical analysis.

-----Original Message-----
Sent: Thursday, December 13, 2001 4:12 AM
To: gdalgorithms
Subject: Re: [Algorithms] BSP bevelling
First of all, thanks for the response.
* Stan: Are you computing these polyhedra on the fly? That seems very
expensive. Storing them in the solid nodes seems very
expensive memory wise.
Assuming you only keep track of the polygons (no
connectivity), you could
store a single polygon in every BSP node which will be the
intersection
between the splitting plane and the convex volume of that
node. But then you
would still have to clip these polygons to every subsequent
splitting plane
along the path to get the correct representation in one of
the solid leaf
nodes.
Not storing a polygon in every node would mean even more clipping.
After that every edge is exactly twice in the set of
polygons, so you would
have to figure out a way to discard those duplicates. You
could discard
edges of backfacing polygons I guess to reduce the number of
possible edges
(is this true??), but that would not get all of them.
How does your algorithm work?
B.t.w. the csg demo is very cool!
* Jay: I understand the way you would generate all possible
separating axis
for collision detection with a box. But unfortunately I'm working with
spheres right now.
Should I for example take all planes that are tangent to the
surface of the
sphere and parallel to an edge of the polyhedron as possible
separating
planes?
I don't quite get the refinement process you describe.
Jorrit.
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

[Jorrit Rouwe]

Ok, now it all makes sense.

Until recently we were using a BSP in which we stored all polygons for
collision detection. For a level that took around 3MB which is way too much
on a PS2. Since about half of the geometry is made in our own CSG based
editor, I turned that data into a solid BSP. This reduces the memory
requirements from 3MB to 1MB. If we use the "hit the artists with a barbed
stick" approach and make them turn on the CSG flag on most brushes, and do
some obvious optimizations like compressing the plane equations in each BSP
node we could do with much less.

I'd rather have coded an AABBox tree or OBBox tree since it is much easier
and more fault tolerant, but I don't see how I could get the same memory
usage if I have to store the polygons. Our polygon BSP already stored the
polygons in 2D to reduce memory load, but that won't fly with the polysoup
you'll get in an AABBox tree node.

Obviously we could try to get the detail in the collision hulls down, that
would be OK for character collision, but we're also using them to create
decals and other eye candy. Another approach would be to stream collision
hulls from disk, but it has to be as small as possible anyway. We can do a
lot of computations on a small data set with a compact algorithm (i.e. maybe
compute the polyhedron of a BSP node on the fly), but only a few
computations with a large data set (data / instruction cache trashing kills
performance on the PS2).

A totally different question: You mention in your article that you use the
volume in each node during construction to minimize the cost of the BSP tree
(as described in Naylor's BSP tutorial). Are you recomputing the polyhedrons
(to determine the volume) for every possible splitting plane that you
consider? Or do you have an elegant approximation that works well? (I've
tried quite a few, but nothing so far beats simple balancing of polygons in
terms of runtime cost and doesn't increase the BSP building time by a factor
of 100).

Jorrit.

----- Original Message -----
From: "Melax, Stan" <***@ea.com>
To: "'Jorrit Rouwe'" <***@games.lostboys.com>; "gdalgorithms"
<gdalgorithms-***@lists.sourceforge.net>
Sent: Friday, December 14, 2001 1:50 AM
Subject: RE: [Algorithms] BSP bevelling

Post by Melax, Stan
To do geomod (via bsp merging)...
Not only do I store the convex
polyhedron at each leaf, I also
store a convex polyhedron at
each interior node in the BSP.
Does it use a lot of memory?
Yeah, that might be an issue.
Its just a little demo.
I haven't used full BSP merging
in a real application or
game. Not yet anyway. :-)
I believe that the guys at
Volition (Red Faction) used
a very different approach
to geomod than what I did.
Like anything, there are
probably pros and cons for
each method.
Back on topic...
If you're just doing sphere
to environment collision
detection, you might be able to
get away with just storing a
few extra planes at the leaves.
It worked pretty good for mdk2.
BTW: I dont want to "push" BSP's on anyone.
For example, if you can bang off
a simple robust AABB implementation in a day,
and it does what you need, then why
not just use that? BSP algorithms can
be harder to understand and implement.
Every technology (BSP, aabb, obb,
loose octtree, etc.) has advantages and
disadvantages.
When deciding, ignore any religious based
arguments in favor of technical analysis.

[Conor Stokes]

Post by Jorrit Rouwe
I'd rather have coded an AABBox tree or OBBox tree since it is much easier
and more fault tolerant, but I don't see how I could get the same memory
usage if I have to store the polygons. Our polygon BSP already stored the
polygons in 2D to reduce memory load, but that won't fly with the polysoup
you'll get in an AABBox tree node.

Well, AABB trees can reduce your storage, for example, you don't need to go
all the way down to a single aabb for triangle, usually you can go with a
minimum/maximum amount of triangles per node and make the tree that way.
Either way the storage isn't too bad. One of the worst models I've found for
making a AABB tree is the "bunny" model, because you have all that rough
surface detail close together. Which weighs in at about 4 megs. Then again,
I've used much higher triangle count, but smoother models (of high
resolution model sites) is the same or less. On very low res models (a few
hundred or thousand triangles) the memory usage is pretty small.

As to storing the polygons - you can store them seperately and use an array
of pointers/ids (thats pretty reasonable) or if you want to get fancy and
compress them, you can create a space local to an aabb node and quantitise
relative to that.

Post by Jorrit Rouwe
Obviously we could try to get the detail in the collision hulls down, that
would be OK for character collision, but we're also using them to create
decals and other eye candy. Another approach would be to stream collision
hulls from disk, but it has to be as small as possible anyway. We can do a
lot of computations on a small data set with a compact algorithm (i.e. maybe
compute the polyhedron of a BSP node on the fly), but only a few
computations with a large data set (data / instruction cache trashing kills
performance on the PS2).

I don't know why people insist on wanting to use BSPs for collision. A BSP
really does consume a large amount of memory and scales horribly.

AABB trees scale wonderfully and can be pretty good memory wise. I've done a
number of different AABB tree implementations at different places and for
different purposes and you can nearly always get a good result.

Conor Stokes

[Charles Bloom]

Ok, I know this is a dead horse, but I feel like we're
missing something terribly simple and effective. How
do the 3d RTS games do their terrain texturing? Ground
Control and the new game SWINE both have just beautiful
terrains. It looks like they're blending together a
bunch of tiled textures (along the lines of "splatting"),
in contrast to the technique that most of us have talked
about, which is auto-generating a single large texture
and then laying detail maps on that.


----------------------------------------------------
Charles Bloom ***@cbloom.com www.cbloom.com

[Niklas Hansson]

This post might be inappropriate. Click to display it.

[jason zhang]

Anyone had looked at the terrain generator World Construction Set
from http://www.3dnature.com ?
It is claimed they build a opengl renderer and can get the terrain
run in real time.
I'm wondering how we can use it in games.

----- Original Message -----
From: "Niklas Hansson" <***@massive.se>
To: <gdalgorithms-***@lists.sourceforge.net>
Sent: Tuesday, December 18, 2001 9:36 PM
Subject: Re: [Algorithms] terrain texturing (redux)

Post by Niklas Hansson
I can't answer with certainty for SWINE but from the texture swapping
problems and nice scaling to higher resolutions I think they simple
makes the splatting as a preprocessor pass and then just uses one big
texture with a chunked loading. This should work especially nice as you
have a very limited camera in that game.
For Ground Control however I can tell you exactly what we do as I
designed that terrain rendering model some 4 years ago.
The basis for ground control is a very simple tile system just like in a
2d game like warcraft. wood tiles to grass that tiles to sand etc (with
some minor differences) this is the base texture. To color it we used a
precalced per vertex raytracning to create what we call a color map
which the graphicans play around with. Then that map is scaled to non
linear ( I think it was quadratic scale) to create more visible
highlights of lighting. (originally we did this with a 2 pass operation
due to that voodoo1 was the only 3d card at that time but we tweaked
around to get something pretty much alike out of it in 1 tmu). Added to
this we used what I then we used a detail texture with modeludex2
blending to create bumps and shadow sin the terrain. This created the
illusion of a much higher resolution than we really had.
I have played around quite a bit with some terrain rendering since then
and the answer to me is pretty much what is the platform. Splatting is
good when you have insane amounts of texture memory as you can get a
higher texture resolution than with the 1 big texture. So if you do the
combining in real-time or preprocess is imho pretty much up to the
target platform. On Pc for example I think splattign is pretty much out
as rendering the terrain that many times will kill the CPU.
While for example on game cube with 8 tmus I would definitely doing a
real-time compositioning system.
/Niklas

Post by Charles Bloom
Ok, I know this is a dead horse, but I feel like we're
missing something terribly simple and effective. How
do the 3d RTS games do their terrain texturing? Ground
Control and the new game SWINE both have just beautiful
terrains. It looks like they're blending together a
bunch of tiled textures (along the lines of "splatting"),
in contrast to the technique that most of us have talked
about, which is auto-generating a single large texture
and then laying detail maps on that.
----------------------------------------------------
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

--
/Niklas Hansson
Software Engineer
Massive Entertainment AB
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalg

[Pierre Terdiman]

Post by Jorrit Rouwe
For a level that took around 3MB which is way too much
on a PS2.

3Mb, but for how many triangles ?
Good AABB-trees use between ~10 and 20 bytes/triangle. I have a version
going down to roughly ~6 to ~9 bytes/triangle, after which it becomes hard
to do better (assuming complete trees, down to 1 triangle/node).

Post by Jorrit Rouwe
In practice, how does the collision detection speed of the BSP methods
compare to AABB and OBB?

I'd also be interested in some figures here.... Unfortunately that's a place
where the implementation has a direct impact on performance, so naive speed
comparisons might be misleading. I suspect both structures provide similar
gains, all in all.

What I love about AABB trees is they're extremely versatile.

Pierre

[Jorrit Rouwe]

Post by Pierre Terdiman
3Mb, but for how many triangles ?

In the order of 100k I believe, but I'm home right now so I can't get the
exact figure. This number is not the optimal you could get with a polygon
BSP since there is no compression in that implementation (except for storing
the polys in 2d). I didn't continue with optimizing this BSP for memory
since I felt that not storing polygons would in the end give me the best
compression possible.

Post by Pierre Terdiman
Good AABB-trees use between ~10 and 20 bytes/triangle. I have a version
going down to roughly ~6 to ~9 bytes/triangle, after which it becomes hard
to do better (assuming complete trees, down to 1 triangle/node).

I'd be really interested in seeing how you managed 6-9 bytes per triangle.
This would put it on a par with a good SolidBSP implementation.

Post by Pierre Terdiman

Post by Chris Cammack
In practice, how does the collision detection speed of the BSP methods
compare to AABB and OBB?

I'm working on an AABB tree implementation right now to compare it's
efficiency with BSP's, so I'll get back with that if I'm done.

For the SolidBSP vs PolygonBSP: I have a class that creates a tree and then
converts it to either a solid BSP or a polygon BSP. Below are the results
for a simple mesh (random cubes/spheres/cones etc.) that I made in MAX.

BSPCreator: Created in 0.1 seconds, 920 input polygons, 1431 output polygons
in 798 nodes with 403 planes, min depth 5, max depth 52
PolygonBSP: Memory load 66912 bytes (72.7 bytes/triangle)
SolidBSP: Memory load 19164 bytes (20.8 bytes/triangle)
PolygonBSP: LineIntersect cost 21.8 (unit cost per node)
SolidBSP: IsInSolid cost 8.8, LineIntersect cost 30.8 (unit cost per node)

Both classes have approximately the same structure and use no compression at
all so they should be comparable speed wise.

The cost is determined by taking a random line segment within the bounding
box for the BSP and measuring the number of nodes that are touched (averaged
over 10000 lines in both cases). I used line segments since they are the
most used intersection test in our game (corona's, line of sight for the AI,
bullets, etc.).

You can see that the PolygonBSP touches fewer nodes (21.8 vs 30.8) but I use
the CPU cycle counter to determine the number of cycles spent during the
10000 lines and I get a factor of 1.1-1.2 in favor of the SolidBSP. So I
think we can say that SolidBSP's perform approximately the same as
PolygonBSP's.

The IsInSolid test of a SolidBSP is also very interesting, since we can use
it for example to let particle systems do simple collision. In terms of CPU
cycles it was approx. 6 times faster than a line intersection test.

Storage requirements for this simple test differ a factor 3 as I already
pointed out in earlier posts.

Jorrit

[Pierre Terdiman]

Post by Jorrit Rouwe
I'm working on an AABB tree implementation right now to compare it's
efficiency with BSP's, so I'll get back with that if I'm done.

If you're interested, I have made a public one available here:
www.codercorner.com/Opcode.htm

Not the most compressed/optimized you can get, but after all it was just a
quick test (search the list archives for more info).

Post by Jorrit Rouwe
I'd be really interested in seeing how you managed 6-9 bytes per triangle.
This would put it on a par with a good SolidBSP implementation.

Basically you start from the 11-bytes version in Game Programming Gems 2,
then get rid of the fat. Gomez noticed what I used to call "tree coherence"
(a node's AABB shares a lot of planes with its parent), but didn't use that
knowledge to the max, since he still stores 6 values for two nodes. The
reason why he did that is clear (although left unsaid) : nodes have a
constant size, which is easier to deal with. So, I simply used nodes of
non-constant size, discarding absolutely all redundant values [hence the
rough 6-to-9 bytes, the exact number depends on meshes].

There are actually a lot of other and maybe better ways to compress AABB
trees, but it's probably not worth it.

Post by Jorrit Rouwe
You can see that the PolygonBSP touches fewer nodes (21.8 vs 30.8) but I use
the CPU cycle counter to determine the number of cycles spent during the
10000 lines

Agreed, the number of nodes is almost irrelevant, especially with fuzzy
overlap tests. We must trust the cycles.

Post by Jorrit Rouwe
The IsInSolid test of a SolidBSP is also very interesting, since we can use
it for example to let particle systems do simple collision. In terms of CPU
cycles it was approx. 6 times faster than a line intersection test.

I think that's one of the things where BSP's are great : particles :) You
get a notion of volume you simply lack big time with AABB-trees...

Pierre

[Jay Stelly]

Post by Jorrit Rouwe
* Jay: I understand the way you would generate all possible
separating axis
for collision detection with a box. But unfortunately I'm working with
spheres right now.
Should I for example take all planes that are tangent to the
surface of the
sphere and parallel to an edge of the polyhedron as possible
separating
planes?
I don't quite get the refinement process you describe.

The problem is that there are an infinite number of separating planes for a
sphere. If you think of the collision surface as an object, it's a curved
surface. In fact, it's a Minkowski sum of the sphere and the BSP. (Think of
it as the object that is formed by sweeping the center of the sphere through
every solid point in the BSP. If the BSP were a simple cube, this object
would be larger in every direction by the sphere's radius, so all of the
corners and edges would be rounded.)

You could compute the necessary planes dynamically, but that's not really a
pure BSP method anymore - it's more of a hybrid. For example, you could use
a BSP to mark out a conservative volume in which the sphere may intersect
each edge, and then do a sphere or capsule vs. edge test when your collision
query intersects those volumes. There are several other exact solutions to
the problem.

In my previous post, I was pointing out that you can get a conservative
solution by storing an approximate Minkowski sum using a polyhedron
(approximating the surface by using some of the potential separating
planes). The more finely you tessellate this polyhedron, the more accurate
it would be. Since it's still a polyhedron, you could then represent it
completely with a BSP and apply BSP-based algorithms to it. Also, the
surface is only curved within one sphere radius of a point or edge, it's
exact everywhere else - that should give you a better idea of the potential
error in the approximation.


Jay

[Gribb, Gil]

You say you are concerned about memory, yet a bsp will shatter your polygons
anyway, increasing the polygon load on the whole system, including memory.
-Gil

Post by Jorrit Rouwe
Ok, now it all makes sense.
Until recently we were using a BSP in which we stored all polygons for
collision detection. For a level that took around 3MB which
is way too much
on a PS2. Since about half of the geometry is made in our own
CSG based
editor, I turned that data into a solid BSP. This reduces the memory
requirements from 3MB to 1MB. If we use the "hit the artists
with a barbed
stick" approach and make them turn on the CSG flag on most
brushes, and do
some obvious optimizations like compressing the plane
equations in each BSP
node we could do with much less.
I'd rather have coded an AABBox tree or OBBox tree since it
is much easier
and more fault tolerant, but I don't see how I could get the
same memory
usage if I have to store the polygons. Our polygon BSP
already stored the
polygons in 2D to reduce memory load, but that won't fly with
the polysoup
you'll get in an AABBox tree node.
Obviously we could try to get the detail in the collision
hulls down, that
would be OK for character collision, but we're also using
them to create
decals and other eye candy. Another approach would be to
stream collision
hulls from disk, but it has to be as small as possible
anyway. We can do a
lot of computations on a small data set with a compact
algorithm (i.e. maybe
compute the polyhedron of a BSP node on the fly), but only a few
computations with a large data set (data / instruction cache
trashing kills
performance on the PS2).
A totally different question: You mention in your article
that you use the
volume in each node during construction to minimize the cost
of the BSP tree
(as described in Naylor's BSP tutorial). Are you recomputing
the polyhedrons
(to determine the volume) for every possible splitting plane that you
consider? Or do you have an elegant approximation that works
well? (I've
tried quite a few, but nothing so far beats simple balancing
of polygons in
terms of runtime cost and doesn't increase the BSP building
time by a factor
of 100).
Jorrit.
----- Original Message -----
Sent: Friday, December 14, 2001 1:50 AM
Subject: RE: [Algorithms] BSP bevelling

Post by Melax, Stan
To do geomod (via bsp merging)...
Not only do I store the convex
polyhedron at each leaf, I also
store a convex polyhedron at
each interior node in the BSP.
Does it use a lot of memory?
Yeah, that might be an issue.
Its just a little demo.
I haven't used full BSP merging
in a real application or
game. Not yet anyway. :-)
I believe that the guys at
Volition (Red Faction) used
a very different approach
to geomod than what I did.
Like anything, there are
probably pros and cons for
each method.
Back on topic...
If you're just doing sphere
to environment collision
detection, you might be able to
get away with just storing a
few extra planes at the leaves.
It worked pretty good for mdk2.
BTW: I dont want to "push" BSP's on anyone.
For example, if you can bang off
a simple robust AABB implementation in a day,
and it does what you need, then why
not just use that? BSP algorithms can
be harder to understand and implement.
Every technology (BSP, aabb, obb,
loose octtree, etc.) has advantages and
disadvantages.
When deciding, ignore any religious based
arguments in favor of technical analysis.

_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

[Jorrit Rouwe]

Post by Gribb, Gil
You say you are concerned about memory, yet a bsp will shatter your polygons
anyway, increasing the polygon load on the whole system, including memory.
-Gil

In the polygon BSP we're only clipping the polygons during BSP tree
building. When we convert the BSP to its final representation we throw away
all clipped polygons and just reference the original ones with an index.
This way we don't generate any extra polygons (but we do have to store them
since the graphics sub system has everything in DMA mangled form).

In the solid BSP we don't store polygons at all, just an array of planes and
for every node an index in that array (there is quite a lot of plane
sharing).

Jorrit.

[Jorrit Rouwe]

Post by Pierre Terdiman
Basically you start from the 11-bytes version in Game Programming Gems 2,
then get rid of the fat. Gomez noticed what I used to call "tree

coherence"

Post by Pierre Terdiman
(a node's AABB shares a lot of planes with its parent), but didn't use

that

Post by Pierre Terdiman
knowledge to the max, since he still stores 6 values for two nodes. The
reason why he did that is clear (although left unsaid) : nodes have a
constant size, which is easier to deal with. So, I simply used nodes of
non-constant size, discarding absolutely all redundant values [hence the
rough 6-to-9 bytes, the exact number depends on meshes].

Ok, so you're not counting the actual triangles! In our case even the PS2
programmers don't know where the vertices are anymore ;-) Parsing DMA lists
doesn't seem like fun, so I have to store my triangles somehow.

B.t.w. In your code, why do you encapsulate all bounding boxes of the tree
(FIND_MAX_VALUES)? I would just use the bounding box of the root for
quantization. Or am I missing something?

Jorrit.

[Pierre Terdiman]

Post by Jorrit Rouwe
Ok, so you're not counting the actual triangles!

No, I'm not. The usual deal on PC is also to have a copy of them in system
memory, either compressed or not. That copy is shared by everything needing
access to the actual vertices & faces, so that's why I don't count them as
part of the bytes used by the collision detection.

If memory is scarce we can directly read the vertex buffers anyway. Reading
from AGP is slow, but it's very easy to do.

Post by Jorrit Rouwe
B.t.w. In your code, why do you encapsulate all bounding boxes of the tree
(FIND_MAX_VALUES)? I would just use the bounding box of the root for
quantization. Or am I missing something?

Nope, you're right, the root node is enough. I just didn't notice it (I was
in a rush I guess....:)

Pierre

[Charles Bloom]

This post might be inappropriate. Click to display it.

[Chris Cammack]

Jorrit, did your collision detection get faster after you switched from
polygon BSPs to solid BSPs?

I've never built one, but the only disadvantage I can think of to using
solid BSPs rather than polygon BSPs is that collisions won't return material
properties. Are there any others?

In practice, how does the collision detection speed of the BSP methods
compare to AABB and OBB?

Chris

Post by Jorrit Rouwe
In the polygon BSP we're only clipping the polygons during BSP tree
building. When we convert the BSP to its final representation we
throw away
all clipped polygons and just reference the original ones with an index.
This way we don't generate any extra polygons (but we do have to
store them
since the graphics sub system has everything in DMA mangled form).
In the solid BSP we don't store polygons at all, just an array of
planes and
for every node an index in that array (there is quite a lot of plane
sharing).
Jorrit.

[p***@playstation.sony.com]

It is possible to handle surface properties with collision BSPs, although
you really have to think of them as volume properties (which may actually
be more usefull, depending on your game). Basically you collect all the
exposed surfaces in a leaf, and add planes to subdivide, until you only
have one type per leaf, then store the type in the leaf data.

I think the main advantage of collision BPSs is that, unlike simple spatial
indicies of polygon soups, you can perform ad-hoc spatial queries, which
can help you make your collision extremely robust. Anyone who's had to fix
'falling through the cracks in the world' type problems should appreciate
that.

The main disadvantage is their difficulty of preparation. Complex meshes,
and subtle curves, can cut really badly if naive algorithms are used,
leading to accuracy problems, which can manifest as mis-classified leaves
(invisible walls, walk through walls), or sticky surfaces. Plus there's the
additional artist time spent sealing models.

In terms of data compression, good BPS structures can easily be in the same
ballpark as good polygon soup representations, with similar cache coherency
issues.

Unfortunately I don't have comparable implemenations at the moment. My BSP
system takes output from Max, and runs on a PSX, while our poly-soup system
takes output from Maya, and runs on a PS2. That said, my gut feeling is
that the line queries that both games used would run at similar speeds.

Cheers,
Phil





"Chris Cammack" <***@n-space.com>
Sent by: To:
gdalgorithms-list-***@lists.sourc <gdalgorithms-***@lists.sourceforge.net>
eforge.net cc:
Subject: RE: [Algorithms] BSP bevelling

12/14/2001 10:17 AM






Jorrit, did your collision detection get faster after you switched from
polygon BSPs to solid BSPs?

I've never built one, but the only disadvantage I can think of to using
solid BSPs rather than polygon BSPs is that collisions won't return
material
properties. Are there any others?

In practice, how does the collision detection speed of the BSP methods
compare to AABB and OBB?

Chris

Post by Jorrit Rouwe
In the polygon BSP we're only clipping the polygons during BSP tree
building. When we convert the BSP to its final representation we
throw away
all clipped polygons and just reference the original ones with an index.
This way we don't generate any extra polygons (but we do have to
store them
since the graphics sub system has everything in DMA mangled form).
In the solid BSP we don't store polygons at all, just an array of
planes and
for every node an index in that array (there is quite a lot of plane
sharing).
Jorrit.

[Jay Stelly]

Post by Charles Bloom
The standard way to do Sphere-BSP collision detection is to query the
BSP with the Sphere's center, and push out all the planes by
the radius
of the sphere. Of course, this is wrong, it over-estimates collisions
at any convex edge in the collision hull. Nonetheless, it
works pretty
well in practice. You can improve it by adding bevel planes at any
convex joint.
Note that this differs from Jay's proposal of using a
polygonal approximation
of the sphere and sending that down. In fact, I believe this
is equivalent
to using a polygonal approximation of the sphere built by
bounding it with
the planes which are in the leaf you end up checking against.

I was trying to suggest using a finite number of bevel planes at each
point/edge chosen from the set of potential separating axes. But I was also
trying to illustrate a way of visualizing the exact solution, so maybe it

Post by Charles Bloom
The best way to bevel the BSP for this operation is to take any convex
angle in the hull bigger than a certain tolerance (say, 280
degrees) and
add a plane which lies on that edge and bisects the angle.
You only ever
need do this once (eg. it's not recursive), since a tolerance
less than 180
is not needed.

is a case of what I proposed, but you've chosen one specific bevel plane.
This is still approximate and conservative for the same reasons you mention
above, but it's very close as you say so for many applications it will be
just fine. e.g. In a 2D sweep with circles against a 90 degree edge. There
will be a small area (equivalent to the difference between one quadrant of
an octagon and one quadrant of a circle) that is solid that shouldn't be
solid. This isn't much space. The larger potential problem is with the
normal: there are only three possible planes to hit, so if your collision
response depends on the contact normal, it will be heavily quantized when
hitting edges. But you could mark the bevel planes and compute a better
normal when you hit them. But that is almost equivalent to an exact
solution to the problem:

I haven't needed to solve this problem, so I haven't implemented this, but
it seems to me that the problem could be solved exactly by doing the
following (again in 2D):
For each solid leaf, store the list of verts on the solid. You can still
add the bevel planes as above as it may reduce the number of times you do
the following...
When a sphere trace/query hits the solid leaf:

for each vert
compute separating axis *
push a plane out from the vert by r along that normal vector
if that plane lies on the surface of the minkowski sum **
clip the point/ray to that plane

This should give you an exact collision between the sphere and the BSP with
the proper contact normal. For 3D you need to enumerate the edges as well
as the verts as you must bevel both. If you're doing some kind of
simulation of the sphere, this is probably useful. For rough collision
approximations like game characters who don't behave as spheres this is most
likely overkill. Note that you can use the same optimization Charles
mentions above - if you know that a vert/edge lies at a concave part of the
solid, you don't need to bevel. Spheres will hit one of the face planes
instead (i.e. the minkowski sum is not curved here).

* For points, this is a unit vector from the solid leaf vert in the
direction of the point query. For ray traces it's a unit vector from the
solid leaf vert in the direction of the nearest point on the ray to the
solid leaf vert. Essentially, you're folding in a line-swept-sphere
intersection algorithm.

** You must test to see if the plane lies on the surface because it may just
cut away solid space from the leaf (like if you're on the opposite side of
the solid from a vert, the plane will be "inside" the solid). The easiest
way to test this that I can think of at the moment is to see that all verts
connected to this vert/edge lie behind the plane (since the leaf is convex
it's sufficient to test only the adjacent verts). So for a rectangular
solid leaf in 2D, you'd have to test up to 2 adjacent verts to be sure.


Jay

PS - This list needs a whiteboard :)

[c***@playstation.sony.com]

Post by Jay Stelly
** You must test to see if the plane lies on the surface because it may

just

Post by Jay Stelly
cut away solid space from the leaf (like if you're on the opposite side of
the solid from a vert, the plane will be "inside" the solid). The easiest
way to test this that I can think of at the moment is to see that all

verts

Post by Jay Stelly
connected to this vert/edge lie behind the plane (since the leaf is convex
it's sufficient to test only the adjacent verts). So for a rectangular
solid leaf in 2D, you'd have to test up to 2 adjacent verts to be sure.

This test won't work as it's not taking into account that the vertices have
been grown by the sphere radius.

For the 2D case, if the vertex is V, the point we're testing is P, and the
neighboring vertices to V are U and W, the extra bevelling test would only
have to be done when:

dot(P-V,U-V) < 0 && dot(P-V,W-V) < 0

This is equivalent to testing if the point P is in a Voronoi vertex feature
region of the convex polygon.

In 3D, the problem becomes rather more complicated than it is in 2D as you
also have to do a (different) bevelling test when the point is in a Voronoi
edge feature region. Additionally, both vertex and edge regions are of a
much higher complexity (not to mention there's more of them too).


Christer Ericson
Sony Computer Entertainment, Santa Monica

[Jon Watte]

Post by Charles Bloom
I know we've done this before, but I've got to go back to it;
why exactly are vertex buffers AGP ? Is it just to avoid having
changes sitting in the cache that aren't written through to main
memory?

AGP is specified with a much looser coherency model, so that the
memory controller ("north bridge") can provide *MUCH* more efficient
access to blocks of memory through DMA than with regular mapped
memory. It basically has to do with hardware/bussing, and the un-
cachedness happens to be a side effect. (AGP also has its own mini-
TLB system, when seen from the bus, and some other nifty features).

Now, I'm not a hardware guy, so at this point the details start to
get fuzzy (not to mention the low-level details are actually guarded
by AGP forum membership fees) but people I trust have told me the
underlying reasons (below that) are sound, so I abide by that.

Cheers,

/ h+

[Jay Stelly]

Post by Jay Stelly
The easiest

Post by Jay Stelly
way to test this that I can think of at the moment is to see that all

verts

Post by Jay Stelly
connected to this vert/edge lie behind the plane (since the

leaf is convex

Post by Jay Stelly
it's sufficient to test only the adjacent verts). So for a

rectangular

Post by Jay Stelly
solid leaf in 2D, you'd have to test up to 2 adjacent verts

to be sure.
This test won't work as it's not taking into account that the
vertices have
been grown by the sphere radius.

Of course. I was thinking the test was being done before you expanded the
plane out by the radius, but that's not what I wrote :) The vertices are
never moved though - you just use the original verts. But the original vert
you're bevelling has to lie on the plane when you do the test. Then you
move the plane constant out (or the dot products in) by r. And when I say
adjacent verts I mean the adjacent verts on the convex solid leaf, not the
BSP - if that wasn't obvious before.

Jay

[Alex Clarke]

Post by Charles Bloom
I'm really thinking of this in terms of the XBox where I do get
such low-level control, and it would be nice to not have to duplicate
my verts for the CPU and GPU to both read.

On the XBox you might as well keep your VB in cached memory. After writing
to
the VB you'll have to do a wbinvd to maintain CPU / GPU coherance.
The cost of one wbinvd per frame seems quite acceptiable in my tests.

Alex Clarke, Programmer
Argonaut Games PLC