Reverse-engineer BSPs and Octrees
 

Well, after working on getting the majority of the .ter and .mod file formats reverse-engineered, I figure it's time to bite the bullet and figure out the last major part: the BSP/octree data. It is unsure whether they use BSP or an octree in the .ter files as of yet, so that's what we need to figure out first. I'll be honest, I don't know my ass from a hole in the ground about either, so I'll need some assistance on this one.

If anyone has any tips as to how to tell whether a BSP or octree is used, please let me know. Likewise, if there are any suggestions as to the potential structure of this data in the file, let me know please.

http://home.archshadow.com/~daeken/anguish.bin is a dump of the contents of ter_island.ter from anguish.eqg starting at 0x0de6 and ending at 0x13b1 (inclusive)
That should be the data storing the BSP or octree.

Happy Hacking,
Lord Daeken M. BlackBlade
(Cody Brocious)

Btw... here's a hex dump:


P.s.: Someone please for the love of $DIETY edit phpbb's css and make code areas use a fixed-width font so the formatting nightmare like above doesn't happen.

well I am assuming thisis really obvious to you, but maybe not...

BSP = 2
quadtree = 4
octree = 8

BSP trees split the world over plane boundaries into two subsections, which then get further divided, etc...
wheres quadtree split the world into quarters, which are each them subdivided into questers, etc... generally omitting the verticle dimention for things like maps. Finally octress split into 8 (quad tree divided in 3 space)

One other characteristic is that BSP trees require you to actually cut ploygons, so one polygon cannot span multiple nodes of the tree. This is not the case in a QT or OT, one polygone can cross into any number of subdivisions.

Another thing is a QT will generally store 4 floats, OT will store 6, and im not sure about BSP, but I think they store the plane, so 4. (

the basic point being that if you get a 2 branch tree: bsp, 4 branches: quad: 8 branches octree.

Sweet, thanks, I didn't really realize that before hehe

I'm still new to the whole idea of partitioning, whether BSPs, octrees, whatever, so any help is appreciated hehe.

Right now I'm trying to optimize the code a bit, and I'm making some progress.

Thanks again :)

I was just thinking about this...

Could we not just produce an octree ourselves the first time a zone is loaded and then cache it? It'd allow me to write the culling code and all now and then we can parse the data from the .ter file later.

Any input would be appreciated.

yes, you could most definately do that...
the big problem is that the tree caculation can be pretty heavy... it involves intersecting a triangle with a cube in 3 space.

I construct an quadtree for my map converter (azone) (which uses your s3d loader I think, your the freaku guy right?)... So you could use that as a foundation if you wanted. My triangle-cube code is fucked right now, but it does an OK job using simpler tasks (it gets too many tringles per node, so is sub-optimal, but it gets all that are in for sure).

Honestly, a quadtree might be at least a good start. The 3rd dimention isnt going to help a whole lot as far as polygon culling goes. expecially in wide-open zones.

And, you could easily extend my quadtree crap to calculate an octree.

Yea, already reading through your code hehe. And OpenEQ is the new name for FreakU, so yea I'm him hehe.