BGL_CRASH_OCTTREE

[Guest GerrishGray]

Does anyone understand exactly how to construct this structure from scratch (without the aid of gMax)? I have a vague understanding of octtree structures as a container for data about a 3D space, but it's not entirely clear how we use this in BGLC to construct a 'crash object'.For those not familiar with the concept, an 'octtree' splits a cubic space into eight smaller cells (like a 2x2x2 version of Rubic's cube) and then each cell can optionally be broken down into 8 sub-cells, and so on. Strangely, this command is omitted from the floating point SDK. But it probably wouldn't be explained clearly if it was there anyway!A typical example, based on the code for the Microsoft house, is

BGL_CRASH_START NoCrash, 19 ; where 19 is the ground radius of the objectBGL_CRASH_OCTTREE NoCrash ENUM16  20 ; Crash type UINT16  3  ; No. of nodes real4 -13.245075, 0.000000, -13.191063 ; x, y, z Origin of structure (m) real4  26.167517, 11.420476, 20.000067 ; width (x), height (y), depth (z) of structure (m) UINT16 1,2,2,3,3,3,3,3;; base offsets into node table, one for each top-level branch OCTTREE_NODE 0,255,0,255,255,255,255,255	 ; node 0 OCTTREE_NODE 254,255,254,255,254,255,254,255 ; node 1 OCTTREE_NODE 254,255,254,255,254,255,254,255 ; node 2NoCrash:BGL_RETURN

I have added comments for the bits I think I understand. On the base offsets line, I think the values given are 1 greater than the node number, thus 1 = node 0, etc.We know that the values in the node table are coded as follows:[ul][li]255 = full cell (this little cubic cell causes a crash)[/li][li]254 = empty cell (this one is empty and therefore there is no crash)[/li][li]1 etc. = offset into node table for further breakdown of this cell[/li][li]0 = ??? (cannot be a recursive entry into the node table, or this structure would be infinite ...)[/li][/ul]Please can anyone confirm whether the above is correct? If it is, the outstanding information is[ul][li]What is the spatial arrangement of the 8 entries at each node (i.e. which of the 8 cells is which in 3D space[/li][li]If we want to branch from one node to a lower level node, would we use the value '4' to go to node 3 etc. or does the value have to be relative to the current branch?[/li][li]What do those zero values mean in the node table?[/li][/ul]Any clever guy out there know the answers, or able to deduce them from testing in gMax and examining the .asm output? Any help would be greatly appreciated.ThanksGerrish

[Guest christian]

No real answers, but...>Please can >anyone confirm whether the above is correct? I think you have a pretty good understanding of it. It works exactly the same as a quadtree which is used for the LODs in the terrain, but obvioulsy is 3D, not 2D (hence 'oct', not 'quad')...>What is the spatial >arrangement of the 8 entries at each node (i.e. which of the >8 cells is which in 3D spaceDon't know :) An educated guess would be top first, than the cells facing 'north' (not really north, maybe 'behind' / 'further away'), left to right, if that makes sense. Any sensible programmer would do it like that, but you'll have to check that. Just make a few structures, that leave some cells out, and you'll see..>If we want to branch >from one node to a lower level node, would we use the value >'4' to go to node 3 etc. or does the value have to be >relative to the current branch?Are you sure about the 4 = 3 thing? It seems counterintuitive, but I have never checked. Anyway, the value should directly point to the lower level node, 4 = 3 as you wrote...>What do those zero >values mean in the node table?As I said I would have thought it maps directly 4 = 4 rather than 4 = 3, but never tested so you might be right in which case 0 really doesn't make any sense...Cheers, Christian

[Guest]

Hi there Gerrish let me get the old textbooks out and get back to you(You know voxels and the like). It's been a while but this could prove interesting!! In case any body is interested a octree is a 3Dmethod of representing how something occupies 3D space by basiclytakeing a 3D "box" and subdividing it into smaller "boxes" in otherwords it's a type of data structure used to discribe what you seeand where it is in our little vertual worlds. BTW Gerrish it might be nice to get together one day on yahoo or net meeting and yap LOL. Dan

[Guest GerrishGray]

Hi guysThanks for the replies.I gave this subject some further thought this afternoon and realised that the zero values in some nodes really may be recursive entries into the same node at the next level of detail. This cunning arrangement would allow sloping or curved surfaces and pointed shapes to be modelled to any required level of detail with no extra data space needed. The infinite recursion is terminated at the required LOD. Same sort of basis as a fractal. 'Eureka' he shouted (although I didn't actually run naked into the street ...)This would also answer the question about the base of the offsets - all offsets are relative to the current node, rather than being an 'absolute' node number. Zero is then instantly recognisable as the special recursive case.I don't think that the spatial sequence is necessarily 'logical' at all - as a computer science and programming professional who started life as an engineer, the sequence I might naturally adopt would be based on the right-handed Cartesian coordinate system, especially as the xyz coordinates of the 'origin' in the gMax example appear to be at the bottom front left of the cube. But the few illustrations I have seen of an octtree suggest otherwise, and the data in the nodes of the example also appear not to agree with that basis. I have not done enough research yet to discover whether there is a fixed convention for this, but I'll see what I can find out.As you suggest, Christian, some methodical experimentation with gMax, making different shaped objects and seeing how the crash octree varies, might be the only way to find out for sure - but I just wondered whether any keen gMax designer out there (Dan perhaps?) already had enough data to be able to work this out. I'm a lazy b...er when I think I might get away with restricting my contribution to the thinking bit and getting someone else to do the real work!!! After all, the thinking makes my poor old brain hurt and it needs time to rest ... I also wondered whether a certain geomatics expert of my acquaintance might know already ;-) ). On that theme, I'm going to try a bit more research first ... I suppose that I could also just play with the data from the example I have given and see which sequence creates what shape - but that will have to wait until I have met a pressing deadline on another project.CheersGerrish

[Guest]

Hi Gerrish I think you are on the right track in regards to the 0 value I am not sure but it looks like the crash octree might be some type of BSP (binary space partiton) I will look at the .bgl code fordifferent models I've done buildings,heads and things like bridgesand see what I notice. Like I have said before it's too bad we have to re-invent the weel all the time heck all I really want to do ismodel. But it seems I'm looking at code all the time(I do that enough at work!). Dan

[Guest GerrishGray]

Hi DanYes, you're right, an octtree is one type of BSP. The limited amount of research and reading I have been able to do suggests that I have probably hit the key in my guess at the recursive nature of the 0 values and, therefore, the use of relative offsets rather than absolute node numbers, although I still need to do some practical experimentation, and analysis of actual gMax octtrees, to confirm this. My reading also suggests that the use of Cartesian coordinates would, indeed, be normal as the basis for the spatial sequence of the values in each octet, but in practice I think there is no alternative but to do some methodical experimentation with gMax, as there don't seem to be any firmly established standards that I have yet seen. That will have to wait a little while because of my other pressing project(s), but if anyone can find out any more about how to construct a CRASH_OCTTREE in the meantime, so much the better.As you say, what a pity that we have to do all this work when MS could perfectly easily document everything properly in the first place, but that's just a fact of FS life! *IF* I can find the time, I will try to do the required documentation for them ... but it's a big 'if'!CheersGerrish