Binary Space Partitioning Trees

[Arce]

Whilst pondering the wonders of the universe, I stumbled upon a master thesis by Samuel Renta for Upsala University in Sweden. Apparently he's a lead programmer of the Portal Engine, and in his paper he shows in-depth the complete algorithm used in the Portal Engine to create binary partitioning trees using pseudo-code and moron-proof explanations.

The entire purpose of a partitioning tree when applied to a game is to divide a complex 3d polygon into a binary tree of triangles. This is done during pre-process time, and allows for extremely heightened draw times. From what I understand, this method was at one point thought obsolete as hardware acceleration became available, but is now being revisited by game developers. The downside to implementing this is that with a small number of nodes, the overhead memory is an exponential figure. But as the number of nodes increases, the overhead memory levels out, and eventually becomes a very insignificant figure for the amount of nodes. The speed of accessing any given node using the new BSP method described by Renta is log(log(n)), which is un-fucking-godly fast.

This method was originally used in Doom...I wonder how our good friend Rand() is doing? ;P

Anyway, I thought it was interesting. Nothing I'd ever have a need for using (I'm not creating high enough poly-count games with lighting effects that would require this type of advanced structuring) but I found it to be a pretty badass idea non-the-less.

So, here's the original thesis I speak of:

http://www.gamedev.net/reference/progra ... ee/bsp.pdf

and here's another one I found, more technical, on Partitioning Trees.

http://sibgrapi.sid.inpe.br/col/sid.inp ... er-bsp.pdf

Lemme know if anybody else here is intrigued by this. ;P

[MarauderIIC]

I've heard about the original method(?) before. Didn't RTFA you posted, but the place I heard about it was some documentary on Tomb Raider =)

[sparda]

Pretty fucking sweet indeed. I read a bit on BSP trees when I tried implementing a miniature ray-caster. I've yet to finish reading the whole thesis, but so far so good. Have you guys heard of sparse voxel octree? A little bastard by the name of John Carmack is inventing this data-structure. I just thought is was relevant, since the first user of BSP (in Doom) is at work again... Jesus, that guy is scary smart.

[avansc]

Pretty fucking sweet indeed. I read a bit on BSP trees when I tried implementing a miniature ray-caster. I've yet to finish reading the whole thesis, but so far so good. Have you guys heard of sparse voxel octree? A little bastard by the name of John Carmack is inventing this data-structure. I just thought is was relevant, since the first user of BSP (in Doom) is at work again... Jesus, that guy is scary smart.

yeah, the man is a legend. although i dont know of he created it. well maybe... i think he just combimed sparse matricies idea with octrees.

you said you were doing a ray-caster??? i did a ray-traced with shading, reflection, global illumination and so on for my senior design project. remembered that was a bitch, and slow as cow.