__Homer__'s Journal

BSP and Beyond - Generating a Portal/Cell Graph from a Triangle Soup
42 comments
2 followers
26 entries
Advertisement
__Homer__
December 23, 2011
You wish, but you don't have the cahones
I went from -2 to -33 from a single post.
Well on track for my -666 !!!

In the meanwhile I've been quite busy, working on commercial projects.
I bet the people who voted me down have not even got a job in the industry !!
Vote me down more!! I need to reach my goal!
1,940 views
__Homer__
December 05, 2011
Wankers
Now my current score on this crap forum is minus 2 - after they agreed minus scored would not happen.
Can i reach - 666?

Yours Truly, for saying nothing more than the truth.
1,831 views
__Homer__
November 29, 2011
GCAP
I was invited to gcap - and stood around outside, hawking my wares like a whore, and it felt so right.
Thanks to all the people who stopped to play it!
1,507 views
__Homer__
October 29, 2011
Metal Clad Men On Horsies - With Sticks!
Announcing the upcoming IGF student division finalists, http://studentgame.caswal.com/Jousting/index.html
1,605 views
__Homer__
October 27, 2011
I like cheese and zombies and the rest is commercial in confidence
Today I got my fledgling newchool opengl engine launched.
It flapped around, at no stage did it fly, but it did not fall over, and it did not disgrace itself on the way out!
1,690 views
__Homer__
October 15, 2011
"Infinite" number of lights - breaking the hardware limits
It's a small blog mention @ http://www.asmcommunity.net/board/index.php?blog=751;sa=topic;id=51

Here I describe a way to breach regular hardware limits for the total number of lights, without sacrificing the minimum framerate, and while considering shadowcasting in the same step.
1,426 views
__Homer__
August 25, 2011
Bullet physics 0, game implementation stuff 1
So on another topic, I'm currently working on a game involving medieval jousting (yes, horsies, mounted by metal-clad men..) and we've glued some kinematic rigid bodies to various joints of our warriors (shields, lances, so forth).
I was happy to set up physics under Bullet to drive the kinematic bo…
1,948 views
__Homer__
June 22, 2011
Portals are almost correct too
Re-enabling the culling of portal polygons during their Clipping phase paid off - I am now detecting five portal quads are being eliminated during the search for 'true portals', and their geometry matches that of the inner box faces - I have eliminated my 'fake portals' correctly.
The sixth and fina…
1,197 views
__Homer__
June 20, 2011
STAGE ONE COMPLETE
I found a very fast way to get the results I was looking for in terms of dealing with the 'closed, unreachable space' in the test model (ie, the space inside the inner box).

I modified the ChoosePartitioningPlane function so that it will always return a plane from the input geometry, as long as ther…
1,332 views
__Homer__
June 20, 2011
A special case of a closed subspace
Wrapping my Line/Plane intersection tests in a simple Macro helped to make the case handlers for the triangle splitter more consistant and helped knock out the bugs.

I have been studying the logged output of my tree generator, and using that information to step through the same process in the 3D mod…
1,561 views
__Homer__
June 14, 2011
Almost Normal
Major bug located in my triangle-splitting implementation.
My algorithm for finding the intersection of a line segment (ie 'edge') and a plane expects the two endpoints of the line segments to be handed in a particular order, which I was not observing in all cases.
The result was that some child tria…
1,211 views
__Homer__
June 07, 2011
Progress Report
More bugfixes and improvements.
The ChooseSplittingPlane method no longer returns planes which don't partition the input set, and its heuristic has been changed to take note of the number of triangles split by a candidate plane.
A bunch of small code changes and bug fixes were made, some enumeration…
1,095 views
__Homer__
June 03, 2011
It's Not Too Late - to Clip it, Into Shape.
[subheading]Shave and a Haircut?[/subheading]
When a problem comes along, you must Clip it ;)

At this point, most of the BSP tree will no longer be of any use to us - our leaf nodes, which represent our convex subspaces, each contains a list of 'portal fragments', some of which are actually 'duds', w…
1,127 views
__Homer__
June 02, 2011
Improving the Partitioning Heuristic, and Marching On
The problems in the tree generator and portal generator seem to be fixed.
I am now able to discover all the convex subspaces, construct the portals as BFQ's and then 'shatter' them against one another.
However before I post the updated sourcecode, I need to eliminate a bunch of runtime tracing/debu…
1,127 views
__Homer__
May 31, 2011
Trials and Tribulations
I've decided to spend a few hours hardening the current codebase through a series of exhaustive tests apon the triangle splitting code in the tree generator - I seem to be getting unreliable results for some reason (occasionally the output is not the same) and I need to understand why this is so.

I'…
1,054 views
__Homer__
May 30, 2011
Shattering the Looking Glass
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 rema…
1,254 views
__Homer__
May 29, 2011
There's a fly in the ointment
I found a bunch more small bugs and fixed them, but I haven't posted the changes yet...
I've created a test geometry involving two boxes, one inside the other, with the outer box's normals pointing inwards.
The BSP generator can't handle it. That's not good.

The BSP generator has two big problems.
The …
953 views
__Homer__
May 28, 2011
The geometric representation of a Portal
[subheading]Portal Geometry[/subheading]

Portals begin life as a big fat planar quad, we already know this, we just don't know how to go about making them yet.
However, I am going to provide the sourcecode for the solution here and now. If you have questions, ask them.

And we don't know how to represe…
927 views
__Homer__
May 26, 2011
Multiple Materials and Kinda Deferred Rendering
[subheading]Tracking Multiple Materials during BSP Tree Generation[/subheading]
My mesh loader sorts the model's triangles (ie vertex indices) into attribute groups by material, that's why you'll see references to "Sorted Indices" in my sourcecode.
I'm happy to completely forget about tracking materi…
1,034 views
__Homer__
May 24, 2011
The fountain of sputum
[subheading]Keep them doggies movin'[/subheading]

Here's the goodies
Please forgive the organic nature of the code and do check periodically for an update!
The Leaf class currently consists only of a class def.. this is a work in progress. I may in fact decide to eliminate it after all.

I'm not very p…
1,238 views
__Homer__
May 24, 2011
Let's get a-crackalackin', it's crunch time.
[subheading]Organic Code Warning[/subheading]
The following sourcecode is subject to change without notice.
Expect that I will adjust and extend this code as I see fit.

Here you can find the Class Definitions for the BSPTree container class, and my two BSPNode classes.
There is a BSPNode class for inte…
1,277 views
__Homer__
May 11, 2011
Physics in a Cell and Portal universe
I have regretfully omitted to mention something quite important, although I did allude to it.
How do we track which subspace an entity is in at any given moment - and what happens if an entity is poking partly through a portal?

We can handle this two ways, but personally, I think it's helpful to mak…
839 views
__Homer__
May 09, 2011
Optimized portal rendering
[subheading]Regular Joe says:[/subheading]

[font="Arial"]Now we've done all our pre-processing, it's time to talk about the runtime stuff - actually rendering with this cell and portal graph.
We know that the cells in our world graph are convex, so we can safely assume that all surface geometry in th…
1,356 views
__Homer__
May 07, 2011
Portalize Me
[subheading]AVOID ILLEGAL POLYGONS[/subheading]
Just some quick notes regarding the 'splitting' of geometry during BSP tree generation...
Traditionally, BSP Tree Generator algorithms will actually physically split polygons into two new polygons, placing one in each child subspace.
The problem with thi…
1,285 views
__Homer__
April 27, 2011
But BSP is SOOOO OLD !
Relax.
We are not going to use BSP in the traditional way (ie, for implementing painters algorithm during rendering).
Rather we will use BSP as an intermediate tool for generating our cell and portal graph.
We are interested in discovering a set of convex subspaces and the 'holes' that connect them - …
1,083 views
__Homer__
April 13, 2011
Generating a Cell and Portal Graph from 'TriangleSoup'
This is my first Journal, so forgive me if I break any conventions.

[heading]What's this all about?[/heading]
As part of the requirements for 'Advanced Diploma in Professional Game Development (Programming Major)' second year, I am expected to spend something like 120 hours researching and developing…
1,525 views
Advertisement

Popular Blogs

shawnhar
Generalist
101 Entries
9 Followers
15 Entries
10 Followers
johnhattan
Programmer
1,277 Entries
47 Followers
ApochPiQ
Generalist
628 Entries
44 Followers
dgreen02
Generalist
338 Entries
56 Followers
Advertisement