Reverse-engineer BSPs and Octrees

[daeken_bb]

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)

[daeken_bb]

Btw... here's a hex dump:

00000000: 0000 0000 0000 0000 4a00 0000 0200 0000  ........J.......
00000010: 1700 0000 0200 0000 0500 0000 3900 0000  ............9...
00000020: 0200 0000 2900 0000 0100 0000 5b00 0000  ....).......[...
00000030: a700 0000 0200 0000 7300 0000 0200 0000  ........s.......
00000040: 6100 0000 9600 0000 0200 0000 8500 0000  a...............
00000050: 0200 0000 b800 0000 0501 0000 0200 0000  ................
00000060: d000 0000 0200 0000 be00 0000 f400 0000  ................
00000070: 0200 0000 e200 0000 0300 0000 1601 0000  ................
00000080: 6601 0000 0200 0000 3101 0000 0200 0000  f.......1.......
00000090: 1f01 0000 5501 0000 0200 0000 4301 0000  ....U.......C...
000000a0: 0400 0000 7701 0000 c501 0000 0200 0000  ....w...........
000000b0: 9201 0000 0200 0000 8101 0000 b401 0000  ................
000000c0: 0200 0000 a401 0000 0500 0000 d601 0000  ................
000000d0: 2902 0000 0200 0000 f401 0000 0200 0000  )...............
000000e0: e201 0000 1802 0000 0200 0000 0602 0000  ................
000000f0: 0600 0000 3a02 0000 8d02 0000 0200 0000  ....:...........
00000100: 5802 0000 0200 0000 4602 0000 7c02 0000  X.......F...|...
00000110: 0200 0000 6a02 0000 0700 0000 9e02 0000  ....j...........
00000120: f102 0000 0200 0000 bc02 0000 0200 0000  ................
00000130: aa02 0000 e002 0000 0200 0000 ce02 0000  ................
00000140: 0800 0000 0203 0000 5503 0000 0200 0000  ........U.......
00000150: 2003 0000 0200 0000 0e03 0000 4403 0000   ...........D...
00000160: 0200 0000 3203 0000 0900 0000 6603 0000  ....2.......f...
00000170: b703 0000 0200 0000 8203 0000 0200 0000  ................
00000180: 7003 0000 a603 0000 0200 0000 9403 0000  p...............
00000190: 0a00 0000 c803 0000 1904 0000 0200 0000  ................
000001a0: e403 0000 0200 0000 d203 0000 0804 0000  ................
000001b0: 0200 0000 f603 0000 0b00 0000 2a04 0000  ............*...
000001c0: 7b04 0000 0200 0000 4604 0000 0200 0000  {.......F.......
000001d0: 3404 0000 6a04 0000 0200 0000 5804 0000  4...j.......X...
000001e0: 0c00 0000 8c04 0000 dd04 0000 0200 0000  ................
000001f0: a804 0000 0200 0000 9604 0000 cc04 0000  ................
00000200: 0200 0000 ba04 0000 0d00 0000 ee04 0000  ................
00000210: 3f05 0000 0200 0000 0a05 0000 0200 0000  ?...............
00000220: f804 0000 2e05 0000 0200 0000 1c05 0000  ................
00000230: 0e00 0000 5005 0000 a105 0000 0200 0000  ....P...........
00000240: 6c05 0000 0200 0000 5a05 0000 9005 0000  l.......Z.......
00000250: 0200 0000 7e05 0000 0f00 0000 b205 0000  ....~...........
00000260: 0306 0000 0200 0000 ce05 0000 0200 0000  ................
00000270: bc05 0000 f205 0000 0200 0000 e005 0000  ................
00000280: 1000 0000 1406 0000 6506 0000 0200 0000  ........e.......
00000290: 3006 0000 0200 0000 1e06 0000 5406 0000  0...........T...
000002a0: 0200 0000 4206 0000 1100 0000 7606 0000  ....B.......v...
000002b0: c506 0000 0200 0000 9206 0000 0200 0000  ................
000002c0: 8006 0000 b406 0000 0200 0000 a406 0000  ................
000002d0: 1200 0000 d606 0000 2707 0000 0200 0000  ........'.......
000002e0: f206 0000 0200 0000 e006 0000 1607 0000  ................
000002f0: 0200 0000 0407 0000 1300 0000 3807 0000  ............8...
00000300: 8a07 0000 0200 0000 5407 0000 0200 0000  ........T.......
00000310: 4207 0000 7907 0000 0200 0000 6607 0000  B...y.......f...
00000320: 1400 0000 9b07 0000 ed07 0000 0200 0000  ................
00000330: b707 0000 0200 0000 a507 0000 dc07 0000  ................
00000340: 0200 0000 c907 0000 1500 0000 fe07 0000  ................
00000350: 4f08 0000 0200 0000 1a08 0000 0200 0000  O...............
00000360: 0808 0000 3e08 0000 0200 0000 2c08 0000  ....>.......,...
00000370: 1600 0000 6008 0000 b108 0000 0200 0000  ....`...........
00000380: 7c08 0000 0200 0000 6a08 0000 a008 0000  |.......j.......
00000390: 0200 0000 8e08 0000 1700 0000 c208 0000  ................
000003a0: 1309 0000 0200 0000 de08 0000 0200 0000  ................
000003b0: cc08 0000 0209 0000 0200 0000 f008 0000  ................
000003c0: 1800 0000 2409 0000 7509 0000 0200 0000  ....$...u.......
000003d0: 4009 0000 0200 0000 2e09 0000 6409 0000  @...........d...
000003e0: 0200 0000 5209 0000 1900 0000 8609 0000  ....R...........
000003f0: d709 0000 0200 0000 a209 0000 0200 0000  ................
00000400: 9009 0000 c609 0000 0200 0000 b409 0000  ................
00000410: 1a00 0000 e809 0000 390a 0000 0200 0000  ........9.......
00000420: 040a 0000 0200 0000 f209 0000 280a 0000  ............(...
00000430: 0200 0000 160a 0000 1b00 0000 4a0a 0000  ............J...
00000440: 9b0a 0000 0200 0000 660a 0000 0200 0000  ........f.......
00000450: 540a 0000 8a0a 0000 0200 0000 780a 0000  T...........x...
00000460: 1c00 0000 ac0a 0000 fd0a 0000 0200 0000  ................
00000470: c80a 0000 0200 0000 b60a 0000 ec0a 0000  ................
00000480: 0200 0000 da0a 0000 1d00 0000 0e0b 0000  ................
00000490: 5f0b 0000 0200 0000 2a0b 0000 0200 0000  _.......*.......
000004a0: 180b 0000 4e0b 0000 0200 0000 3c0b 0000  ....N.......<...
000004b0: 1e00 0000 700b 0000 c20b 0000 0200 0000  ....p...........
000004c0: 8d0b 0000 0200 0000 7a0b 0000 b10b 0000  ........z.......
000004d0: 0200 0000 9f0b 0000 1f00 0000 d30b 0000  ................
000004e0: 1b0c 0000 0200 0000 e80b 0000 0200 0000  ................
000004f0: da0b 0000 0a0c 0000 0200 0000 fa0b 0000  ................
00000500: 2000 0000 2c0c 0000 7b0c 0000 0200 0000   ...,...{.......
00000510: 450c 0000 0200 0000 330c 0000 6a0c 0000  E.......3...j...
00000520: 0200 0000 570c 0000 2100 0000 8c0c 0000  ....W...!.......
00000530: d90c 0000 0200 0000 a60c 0000 0200 0000  ................
00000540: 960c 0000 c80c 0000 0200 0000 b80c 0000  ................
00000550: 2200 0000 ea0c 0000 bb0d 0000 0900 0000  "...............
00000560: 060d 0000 0200 0000 f00c 0000 240d 0000  ............$...
00000570: 0200 0000 180d 0000 410d 0000 0200 0000  ........A.......
00000580: 350d 0000 570d 0000 0000 0000 7c14 2e3e  5...W.......|..>
00000590: 660d 0000 0000 0000 0000 2041 760d 0000  f......... Av...
000005a0: 0300 0000 1500 00ff 850d 0000 0300 0000  ................
000005b0: 171e 00ff 940d 0000 0000 0000 feff ff3e  ...............>
000005c0: a80d 0000 0300 0000 ffff ffff            ............

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.

[fathernitwit]

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.

[daeken_bb]

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

[daeken_bb]

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.

[fathernitwit]

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.

[daeken_bb]

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