Shattering the Looking Glass

Published May 30, 2011
Advertisement
Things seem to be going well.
The BSP Tree generator now successfully processes the 'box in a box' model into a bunch of convex subspaces and creates the Portals, intializing their geometry with Big Fat Quads.

I have implemented a full triangle-splitting BSP Tree generator, however I intend to remain true to my original plan.. when the BSP Tree has been generated, I will convert my Triangle structs back into simple references (indices) to original triangles. This will allow me to avoid interpolating vertex components other than position (currently I do bother to interpolate for position, normal, uv) when creating new vertices whenever a visible triangle is split during tree creation, it will also allow me to discard all junk vertices, indices, etc that were produced as a byproduct of full triangle splitting, and go back to the original input geometry only - which is lucky because my mesh class already uploaded that to hardware before I got hold of it, lol.

[subheading]In case of emergency, break glass...[/subheading]
The next step is to Shatter the portals.
As outlined, this involves splitting our Big Fat Quads against all the splitting planes that we used in our tree, and keeping all the output polygons irrespective of what side of a splitting plane they fall on, and even what shape they are.
Since we began with a convex portal geometry, and only bisected it, we know that all the fragments will be convex too.
We also know that they are 'flat' since the portals were originally constructed apon planes.... all the fragments in a given portal will remain coplanar.

The geometric requirements for portals are different for those of the visible triangles we processed thus far.
For this reason, two new classes (Polygon and Portal) have been introduced.
Unless something else blows up, I will post an update of the sourcecode today :)

Here is a picture of the Box in a Box model for anyone who struggles with visualizing something like that.
0 likes 3 comments

Comments

Ng
Just let me see if I got this right: at first you wanted to avoid splitting polygons, etc. Then you ran into issues with that part and decided to split. But then new bugs were found that proved the splitting still unnecessary but you went ahead with it anyway, right? So the original idea of NOT splitting still works, right?

A future implementation I'm planning with some of my base libs would try to avoid the splitting, because that's a very nice idea, you know :).

Anyway, keep it up, it's getting better by the day!
May 30, 2011 06:15 PM
__Homer__
Yes - We ALWAYS want to avoid splitting polygons - in a subsequent post I talk about how we can achieve that.

I know for a fact that the original idea still works, because I have seen it implemented in a relatively recent kind of physics collision detection, where we construct our 3D objects as 'brushes', which are BSP-Tree representations of convex primitives, or concave shapes created by performing boolean operations apon other brushes... this is called constructive solid geometry, it's closely related stuff.

In those examples, we can take any non-animated mesh object and construct its "internal" BSP Tree - which maps the solid space inside the body, and is mainly interested in convex sets of triangles that point AWAY from one another.. To perform a collision test, we walk both trees at once, testing the bounding geometry of one node against the splitting plane of the other, until we reach the leaf nodes, where we can perform a minimal number of triangle/triangle tests.

Anyway, I know that I can get back to that, when I am finished, I can throw away my renderable Triangle objects that I collected in my Leaf nodes, and replace each with one (or three, if I am stupid) indices into the original set of triangles.It is for that reason that I have tagged my triangle fragments with the identity of the original triangle from which they were sliced.
June 03, 2011 09:53 AM
__Homer__
My current thought about internal bsp trees for physics collision detection, something I won't breach during this project, is that we should actually be aiming to construct a minimal tree of tetrahedrons that fill the body volume.
Then we can bastardize the GJK/EPA algorithm to detect collision/find deepest penetration vector.
June 03, 2011 10:04 AM
You must log in to join the conversation.
Don't have a GameDev.net account? Sign up!
Advertisement