wz

bhkMoppBvTreeShape

131 posts in this topic

Most of the data format of the MOPP could be decoded :) This is very incomplete and rushed at 2:18am, there's more to come.

 

First of all, to see the values discussed here, you need the following XML entry:

 

[syntax=xml]

Memory optimized partial polytope bounding volume tree shape (not an entity).

The shape.

The shape's material.

Unknown bytes, probably MOPP Header.

Unknown float, might be scale.

Number of bytes for MOPP data.

Corner of the object with min. coordinates.

Unknown. Can be interpreted as float inversely proportional to shape size.

The tree of bounding volume data.

[/syntax]

 

 

 

The data is arranged (Assembler-like) in entities as groups of bytes, where the first byte is a header with arbitrary data bytes to follow.

 

The known bytes are, together with the entity length (only the most frequent, I will add more from my notes tomorrow):

  • 0x10 to 0x20 4 bytes
    Seems to be the shape geometry, translation etc.
  • 0x26 to 0x28 3 bytes
    A dimension in relative measure. The MOPP data starts with these entities. 0x26 is X, 0x27 is Y and 0x28 is Z. First data byte is start, second is end. The value is relative to the longest side of the underlying shape (so the longest side will always have 0x2* 0x00 0xff ).
  • 0x30 to 0x4* 1 byte
    There entities seem to determine the tree nodes.

 

 

 

I wrote a small utility that helps in displaying blocks, I will put it up on SVN soon.

The output for the actual MOPP is this (one row is one entity):

----------------------------------------------------------------
| File:            meshes/dungeons/sewers/sewerroomfloor01.nif |
----------------------------------------------------------------
The file contains 1 bhkMoppBvTreeShapes.

 0001 | 0x28:    0    1                         Size Z
 0004 | 0x27:    0  255                         Size Y
 0007 | 0x26:    0  255                         Size X
 0010 | 0x18:  128  127    1
 0014 | 0x31:                                   Divisor #1 ?
 0015 | 0x30:                                   Divisor #0 ?

Edited by

Share this post


Link to post
Share on other sites

This post made no sense, said Shon, since I edited the one above. So I'd like to use this space to have a silent place all for myself.

Edited by

Share this post


Link to post
Share on other sites

Now the good news: You dont need a Mopp shape to use the PackedNiTriStripsShape!

Share this post


Link to post
Share on other sites

That is good news I think. I'm starting to rewrite collision support in max and planned to use the bhkListShape and these in that rewrite so this is good to know.

Share this post


Link to post
Share on other sites

I'd not even consider the listshapes. The Packed ones are much better suited, and generally used by Beth.

 

But I dont know how well complex meshes will perform without the bounding checks.

Share this post


Link to post
Share on other sites

Oh and taz, I hope you are using the reactor bodies and constraints for this :)

Share this post


Link to post
Share on other sites

Ok I am pretty sure now that the Unknown Vector is just an artifact that came from the Vector at the beginning of the Unknown Bytes 2 not recognized.

 

My guess is that the "Vertex Min" vector is the starting point of some kind of tree description.

Share this post


Link to post
Share on other sites

Initially probably not. At least I'll try to be compatible and reuse the same data if possible. Not all versions of max have reactor (I dont think anyway). Reactor is fairly closed and I find it difficult to get data from it and the SDK level (I would love to get the collision meshes it generates but I cannot find a way.)

 

I planned on creating modifiers and helper objects to manage most of the work. I have initial support for the simple types bhkBoxShape, bhkSphereShape, and bhkCapsuleShape for the really simple stuff. (Box already had some support as well as Sphere but I'm some of that).

Share this post


Link to post
Share on other sites

You should also include ConvexVerticesShape, as this is preferred (by Beth) over PackedShapes for convex models. And easy to do!

Share this post


Link to post
Share on other sites

I compared two almost equal shapes:

 

mopp2li8.th.png

 

I'm too tired now, please draw the conclusions :D

Share this post


Link to post
Share on other sites

Well no comment as this I probably need to spend equal time with this. Looks nearly random to me. Have you tried looking at the values as shorts or floats or doubles? When I scan through the data with hex workshop it seems that there are more floats than the ones you located but not many so its unlikely. Could they be using the short scaling factor instead of floats like they did in bsplines? I realize we have byte that controls the size and makes it all work but anyway.

 

BTW, I have a business trip for the next week so I'm probably going to be out of contact for the week.

Share this post


Link to post
Share on other sites

Too bad :(

 

I checked it in all forms. My guess were floats too, discernable from the ~192 at the fourth byte, but those are just randomly there. Other files dont have a single sane float in them.

 

Oh, and look at this nice little thing:

 

mopp3hf9.th.png

Share this post


Link to post
Share on other sites

Ah I see the analogy to the BSpline now. I had the same guess, but could not find a hint for now. I will try to plot the points.

 

Edit: I doubt the bytes2 are referring to (byte, byte, byte) points. The resulting shape for the floor looks weird.

Share this post


Link to post
Share on other sites

Free 56k access at the hotel. Yeah. I'm paying $220 a night and they cant provide free high speed? :/

 

On the plane I was reading Eberly's 3d game engine design (better than The Devil Wears Prada i think) and he went into a little detail but not much over OBB's but did describe them and I suppose that wild magic has some source for it but since this is not native nif it probably wont match any data structures.

 

I now realize that those will probably not be floats but a some sort of search tree. Given the that its memory optimized means it will probably be difficult to figure out the algorithm from just the data.

 

This structure sounds pretty much a requirement for any complex shapes to minimize real performance issues.

 

Can I assume that you tested the convex shape by removing the OBB and just using the shape?

Share this post


Link to post
Share on other sites

Yes, you can assume this. It works, but I did not do any timings on complex objects (I used the testinghall room elements).

 

I think the Unknown Float in there is scale. It would fit the other shapes, and the behavior the Nifs show when you change the value support this as well. Could not find a really suitable test object though.

 

And I doubt it is really raw MOPP data in there (remember, MOPP is Havok stuff, not Beths). Hint one is that there is one readable vector inside, and then I think any optimization / compression would lead to more drastically different byte arrays than whats seen on the pic I posted above.

 

The book you mention might shed some light on the issue since I never found any literature dealing with polytopes for collision detection.

Share this post


Link to post
Share on other sites

You are at the university. How's your library there? There are several articles listed in on the OBB trees in the book. There isn't much regarding the text in the book itself but wildmagic source/documentation is available at http://www.geometrictools.com/Documentation.html. In case you were not aware, Eberly was the chief architect for NetImmerse engine design so his code would probably tend to match what Gamebryo looks like in general internally. Again doesn't help much with the mopp but perhaps its similar.

Share this post


Link to post
Share on other sites

We're mostly specialized on the classical lectures, and very mathematic. I doubt I find much literature, of course I could try to talk them into ordering something.

Share this post


Link to post
Share on other sites

After looking at the byte array a little I have assumed that packed means actual compression but I dont recognize any byte sequences like 0x78 for zip. The bytes are fairly well distributed except for 0x00, 0x26, 0x27, 0x28. 0x4, 0x2, 0x1, 0x5B, 0x37 are runner ups that seem to show up in most of the character distributions that I ran.

 

I'd be generally surprised if they use a real compression algorithm for just this especially if its used at run time.

 

Nothing in the wildmagic source for bounded volume trees seemed like an obvious match to me.

Share this post


Link to post
Share on other sites

I beleive there is typically a Axis Aligned Bounding Box in the begining of the tree wich looks like 0x2600ff, which is x axis, min bound, max bound

the axis aligned box is scaled to fit that cluster of level or model geometry

 

Similarily there are OBB's in the tree 0x1000ff##

0x10 is axis x, other axis are above 0x12 not sure where they are defined.

0x00ff is min and max much like bounding slabs

0x## is the offset to next node I beleive right node the left node I belive directly follows the definition

 

0x30 if it points to that is triangle 1

0x31 is triangle 2 ...

hopefuly that helps but these are just really good guesses

Share this post


Link to post
Share on other sites

Sounds like a promising theory...

 

wz, what do you think? Might it be possible to try to visualize the data this way in NifSkope to see if it comes up with something that looks plausible?

Share this post


Link to post
Share on other sites

I think there is an inherit problem to decoding this format.

Because it is memory optimized the tree will never look the same.

A first step would be trying to recognize all the elements first then see how they are used.

Share this post


Link to post
Share on other sites

The MOPP is *not* the same even for two identical objects. It surely has a Bounding Volume, hence the *Bv*.

 

But it also is ordered in a tree structure, to make collision more efficient, I'd guess it's a binary tree that descends into ever finer parts of the collision mesh.

 

I will write down all my findings later today. There's a few things we do know about bhkMoppBvTreeShapes at least :)

 

Edit: Too bad you came up with that today. A few more days, and I might have come up with the format out of the blue. The 3DS importer brought me back into it, and so far, the work was going fine :D

Share this post


Link to post
Share on other sites

Since I cant write it down in detail today, I have the top-level of the mopp (the root of the tree) worked out, and the leaves need some checks if my theories are consistent with the nifs we are given.

Share this post


Link to post
Share on other sites

I think you are right about it beaing a Binary tree.

Those bounding slabs are typically a node. They do one of two things

 

A. bound a single convex triangle or a group of coplanar triangles that form a convex polygonal faces.

 

B. act as a splitting plane giving overlapping distances to enclose two seperate groups of triangles.

 

Sometimes after a split like that the will give AABB to refine that child node. the odd thing is they don't always bound on all axis. They may be relying on the parent nodes bounding box and just updating that plane.

 

It is like they are giving the minimum amount of information so that at runtime they build a bigger tree in memorey and can quickly raycast against it.

Share this post


Link to post
Share on other sites

I got the data format done at least. There's still much guessing what the values mean, though. I am short on time (I keep a notebook with the bytes with me ^^) but I have a spreadsheet started to explain the format.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now