Dynamic AABB (Cthuga)

[oddrose]

Hi,
I was thinking about an Dynamic AABB implementation the other day and saw that it was put on the annotated roadmap for Ogre 1.7.
It says:

Skeletal animation bounding box updates

* One 'update' BB which covers the mesh at every animation point
* Dynamic AABB which updates based on bone extents, plus padding factor

First, is this under development?
If not, I thought (since I want this in my project) that I could start building one and if it turn out satisfactory, I would submit a patch.
I just have a question regarding the description above, and it's about the padding factor.

Is this padding intended to be per-bone or per-entity? (Or universal?)
If the answer is any of the two first I guess the data for this padding has to be stored somewhere in Ogre.
Depending on what accuracy is wanted the type of data and the place for it to be stored differs quite a bit.

For my dynamic AABB I've been thinking of a couple of ways to do it.

A) The system disregards any differences is the thickness of the body, i.e, one sets a per-entity padding factor and the AABB is calculated with respect to the bones's start and end points + padding factor.
On update the new positions for the bones are read and new maxs/mins for the AABB are set.

B) Padding factors are calculated per-bone according to the distance to the vertices that the bones influence. This is done at load time of the skeleton and mesh and the update will happen similar to A).

C) As B) but with two padding factors per bone, one at the end and one at the start. I guess parent end and child start would have to have the same padding factor or there could be some issues.

E) I have seen on several occasions BBs being calculated from capsules attached to the bones, kinda like a physical skeleton but just for updating the BB. I think this doesn't fit into the description "Padding factor" but I guess the result is somewhat like that of my C)-proposal. Also, it seems more like a physics engine than a render engine thing

Last, about the 'update' BB in the roadmap. If I understand this correctly, this is meant to set one single BB that fits every frame of every animation? So this would be calculated at load time?

[sinbad]

This has been on our TODO for a while but it's never been critical enough for anyone to actually tackle it yet. So yeah, we'd appreciate a patch if it's something you want to tackle.

To keep it as simple (and therefore cheap) as possible I envisaged that a single padding factor would be calculated from the vertices assigned to the bones, representing the maximum distance of that vertex from the bone. Note that there actually is no 'start' and 'end' of a bone, that's just how modellers display them, really they're just a position / orientation in space. This padding factor would be stored in the .mesh to avoid calculating it at runtime (an optional new chunk for backwards compatibility). Once a skeleton has been updated you'd simply need to make sure that the AABB sides were at least as far away from any derived bone position as this padding factor.

I don't think it's worth doing down the capsule / per-bone padding route. AABBs are rough anyway, and you really don't want to add any more complexity to the skeleton animation update than necessary. There should probably be an option not to modify the AABB dynamically, derived from whether (based on the preprocessing) the bones+padding actually end up going outside the static mesh AABB or not. Some tools (like the XSI exporter) make sure that the mesh AABB incorporates all keyframes of the mesh, not just the mesh at rest, which is much more efficient if the mesh is already localised within that AABB than trying to update it for all bones. It's not something we'd want to universally require.

[oddrose]

To keep it as simple (and therefore cheap) as possible I envisaged that a single padding factor would be calculated from the vertices assigned to the bones, representing the maximum distance of that vertex from the bone.

I take it that you mean that the padding factor should be the maximum of all per-bone vertex-bone-distance maximums?

Note that there actually is no 'start' and 'end' of a bone, that's just how modellers display them, really they're just a position / orientation in space.

Hehe, yeah, I feel like you have corrected me on this before and I keep making the same mistake. But yes, of course that's the case.

This padding factor would be stored in the .mesh to avoid calculating it at runtime (an optional new chunk for backwards compatibility).

Okay, that's sounds reasonable. The exporters would have to incorporate this but since it's only a float extra I think I'll be able to alter a mesh via the serializer for testing purposes. Or some other way.

[oddrose]

Hi again,
I messed around with this a bit and created a run-time edition of this functonality and, to begin with, without modifying the Ogre source. It works well and I wish I had a video to show, but I haven't got any screen capture software installed. (Recommendations are welcome).

I have some questions regarding the implementation in Ogre however. First, we've been talking about a padding "factor". This would by definition mean a multiplication of a distance but I'm not sure that's what's intended. I guess you could calculate a factor like (distance bone->vertex)/(distance bone->root node) and MULTIPLY this with the (distance bone->root node) for every bone. The alternative is to just calculate the distance from the bone to the farthest vertex and then ADD that to the bone positions when checking for AABB boundaries. I think both are equally arbitrary towards the "non-max-distance" bones/vertices. The name "factor" is itself also part of why I'm asking since I have to name the variable something. If a factor, mBBPaddingFactor. If a distance, mBBPaddingDistance.

About the variable. I'm wondering where to put it. I guess I'll have to be in Ogre::Entity at some point to update the boundingBox, so should I store the padding value there as well?
I've been thinking about creating a method "Entity::updateBoundingBox(void)" which gets called either from Entity::updateAnimation or Entity::cacheBoneMatrices. I'm leaning towards the second since there already is a check for mFrameBonesLastUpdated there. Also it is tied specifically to changes in the skeleton.

I haven't got around to look at the serializing part of it yet, but I though I'd ask about this along the way.

[sinbad]

Fraps is usually a good choice for capture.

'Factor' was just a bad use of terminology on my part, it would be an additive amount.

I didn't see this being on Entity, only on Mesh, with Entity referencing it when updating. If there's a new 'update bounds' method, I'd make it specific such as updateAnimatedBounds or similar, so it's obvious under which circumstances it would be needed.

[oddrose]

Thanks for the reply. That seems reasonable. I will test with the trunk version in the week or weekend and look at the serializer if I get time.

[oddrose]

Hi again!
I looked at the MeshSerializer today and I think I know how I want to do the exporting / importing.
Basically I propose a new MeshChunkId, M_MESH_BOUNDS_ANIMATION_PADDING:

Code: Select all

M_MESH_BOUNDS = 0x9000,
    // float minx, miny, minz
    // float maxx, maxy, maxz
    // float radius
    M_MESH_BOUNDS_ANIMATION_PADDING = 0x9100
        // float padding

I am not entirely happy with the name of the new ChunkId since it doesn't say anything about the padding being from the bones to the mesh. I'd be happy to accept other proposals.

Allright, with the new chunkid in place we can define the serializing, and since it's just a float it's a pretty small change. To maintain backwards compability (like Sinbad proposed above) I think we should follow the pattern of other "sub chunks", e.g M_SUBMESH_NAME_TABLE_ELEMENT. So in MeshSerializerImpl::readBoundsInfo there would be something like:

Code: Select all

void MeshSerializerImpl::readBoundsInfo(DataStreamPtr& stream, Mesh* pMesh)
{
        Vector3 min, max;
        // float minx, miny, minz
        readFloats(stream, &min.x, 1);
        readFloats(stream, &min.y, 1);
        readFloats(stream, &min.z, 1);
        // float maxx, maxy, maxz
        readFloats(stream, &max.x, 1);
        readFloats(stream, &max.y, 1);
        readFloats(stream, &max.z, 1);
        AxisAlignedBox box(min, max);
        pMesh->_setBounds(box, true);
        // float radius
        float radius;
        readFloats(stream, &radius, 1);
        pMesh->_setBoundingSphereRadius(radius);

        if(!stream->eof)
        {
                streamID = readChunk(stream);
                if(streamID == M_MESH_BOUNDS_ANIMATION_PADDING )
                {
                        float padding;
                        readFloats(stream, &padding, 1);
                        pMesh->setBoundsAnimationPadding(padding);
                }
        }
}

Okay, so if we can read it, we might as well be able to write it. Since it's a padding amount it is logical to initialize the padding member as 0.0 in the constructor, so we might as well write whatever value is stored.

Code: Select all

void MeshSerializerImpl::writeBoundsInfo(const Mesh* pMesh)
{
	// Usage Header
        unsigned long size = STREAM_OVERHEAD_SIZE;

        size += sizeof(float) * 7;
        writeChunkHeader(M_MESH_BOUNDS, size);

        // float minx, miny, minz
        const Vector3& min = pMesh->mAABB.getMinimum();
        const Vector3& max = pMesh->mAABB.getMaximum();
        writeFloats(&min.x, 1);
        writeFloats(&min.y, 1);
        writeFloats(&min.z, 1);
        // float maxx, maxy, maxz
        writeFloats(&max.x, 1);
        writeFloats(&max.y, 1);
        writeFloats(&max.z, 1);
        // float radius
        writeFloats(&pMesh->mBoundRadius, 1);

        // bounds animation padding
        size = STREAM_OVERHEAD_SIZE + sizeof(float);
        writeChunkHeader(M_MESH_BOUNDS_ANIMATION_PADDING, size);
        writeFloats(&pMesh->mBoundsAnimationPadding, 1);

}

I think this solution sounds reasonable, keeping the value inside of BoundsInfo, since it's information about the bounds=).

As you can tell from the above code I basically propose three additions to Ogre::Mesh:
A member: Real mBoundsAnimationPadding;
Getter/Setter: void setBoundsAnimationPadding(Real padding) / real getBoundsAnimationPadding(void)

Also there would have to be something like an updateAnimatedBounds function. As of now the entities bounds are only updated (from the meshes' bounds) when they are requested with getBoundingBox (?). If I understand correctly, updateAnimation happens to all subEntity as well as the parent Entity before they are rendered? So the entities/subentities would only have to be responsible for their own mesh? This would mean that from the updateAnimation method or the cacheBoneMatrices method, you could call something like Mesh::updateAnimatedBounds which would set the new bounds for that particular mesh/submesh. When Entity::getBoundingBox is called, the parent entity will merge all bounds and return the full bounding box.

If this is correct, most of the infrastructure is already in place and I would only have to update the meshes' bounds?

Another thing, if people don't want they're bounding boxes updated there would have to be a flag to set somewhere. Should it be stored in the mesh object as well or in the entity?

[sinbad]

Sounds generally fine - I would make the chunk more specific as you say, maybe M_MESH_SKELETAL_BOUNDS_PADDING instead.

There's a potential bug in the reading of the data though, if you read a chunk and it's not the type you were expecting, you should back up the stream so that something else can process it, like this:

Code: Select all

            if (!stream->eof())
            {
                // Backpedal back to start of stream
                stream->skip(-STREAM_OVERHEAD_SIZE);
            }

The new StreamSeriazlier class makes nuances like this a bit easier but it wasn't worth rewriting the MeshSerializer at this stage to use it.

Also, you should increment the mesh version number so that it's easy to know when this data has been considered or not. When reading a previous version mesh, the serializer should automatically calculate this factor dynamically if there's a skeleton since it will be missing otherwise. Once upgraded the mesh will include the data already of course.

The danger though, that I just considered, is that Mesh generally can be loaded independently of Skeleton - there's a relatively light link between them and exporters typically will happily write the Mesh without ever actually hooking up the Skeleton to it physically (just setting the name link). In this case of course, you can't calculate this padding value without also having the Skeleton fully available. This makes the automatic upgrade to include this data trickier than it was before...

[oddrose]

There's a potential bug in the reading of the data though, if you read a chunk and it's not the type you were expecting, you should back up the stream so that something else can process it, like this:

Yeah, I almost knew this would come up, I saw this in some of the other serializer methods but wasn't sure what it was doing, but now I definitely get it.

Also, you should increment the mesh version number so that it's easy to know when this data has been considered or not. When reading a previous version mesh, the serializer should automatically calculate this factor dynamically if there's a skeleton since it will be missing otherwise. Once upgraded the mesh will include the data already of course.

Yea, that sounds good, does 1.42 sound ok? (current is 1.41)...it's not that big a change. Since we're planning to support old meshes with a whole other procedure, I guess I'll create a sub class for the 1.41 versions read/writeBoundsInfo methods. Or maybe not, depending on from where the calculateAnimatedBoundsPadding() or whatever will get called. (see discussion about the incomplete skeleton).

The danger though, that I just considered, is that Mesh generally can be loaded independently of Skeleton - there's a relatively light link between them and exporters typically will happily write the Mesh without ever actually hooking up the Skeleton to it physically (just setting the name link). In this case of course, you can't calculate this padding value without also having the Skeleton fully available. This makes the automatic upgrade to include this data trickier than it was before...

Yupp, I've been thinking about this too. What do you mean by "before"? Before this implementation or before you considered this problem?

Isn't this a problem that lies somewhere else though? As long as the name link is set, pMesh->setSkeletonName(skelName); will get called in the serializer and the skeleton will be loaded. If there's an error in the loading procedure the "Unable to load skeleton, ..., this mesh will not be animated" error will be logged? I mean, if the skeleton isn't attached to the mesh or if the skeleton is entirely missing, the mesh won't have any interraction with the skeleton whatsoever, will it? If that's the case, no bounds will have to be updated and therefore no padding will have to be calculated.
I think this eventuality should cause the mesh to set the flag regarding whether to update the bounds to false and the padding amount won't matter.

I'm sorry if I misunderstand you, but perhaps you could clearify what would go wrong?

[sinbad]

Isn't this a problem that lies somewhere else though? As long as the name link is set, pMesh->setSkeletonName(skelName); will get called in the serializer and the skeleton will be loaded. If there's an error in the loading procedure the "Unable to load skeleton, ..., this mesh will not be animated" error will be logged? I mean, if the skeleton isn't attached to the mesh or if the skeleton is entirely missing, the mesh won't have any interraction with the skeleton whatsoever, will it? If that's the case, no bounds will have to be updated and therefore no padding will have to be calculated.
I think this eventuality should cause the mesh to set the flag regarding whether to update the bounds to false and the padding amount won't matter.

I'm sorry if I misunderstand you, but perhaps you could clearify what would go wrong?

The problem is that it becomes a persistent problem. Previously if the Skeleton was not available, it had no effect on the content of the .mesh file, it just meant you couldn't animate it in real-time - which is of no consequence for processing tools. With this change, you can't fully process the Mesh successfully with tools (e.g. XMLConverter) unless the Skeleton is also available.

If you're trying to upgrade the Mesh, it won't work unless you also have the Skeleton avaliable since you won't be able to calculate the padding value. You either have to fail (do not upgrade), or ignore it (which means the padding value will be set to some incorrect value, which the next time the Mesh is loaded, you won't be able to tell that it's not correct and that you should be recalculating it when the Skeleton becomes available).

Also just for saving, forever more when serializing the mesh you really have to have access to the Skeleton to be able to complete that field correctly. This is a new requirement and will probably break most exporters, or at the least make them behave incorrectly (writing a dummy value into that slot).

The only other option is to not write that new chunk even with the new serializer if the Skeleton is not available, meaning that you have to calculate it on demand until such time that you re-serialize the Mesh with the Skeleton available. That's probably the least of all evils but it does change the rules on Mesh serialization a bit and is prone to error.

[oddrose]

Indeed.

I'm not satisfied with where this is going really. For now it seems there are more cons to storing the data in the .mesh than pros.
I know calculating the padding at startup causes extra load time but if the feature is semi-supported in the .mesh I think it'll become confusing to the user.

I'll have to think on this some more. I'm having a hard time imagining how this would work without having access to the skeleton at upgrade time though.
What irritates me a little is that the padding, when in the mesh file, has nothing to do with the skeleton, as the other data, so I really want to find a solution that works with the .mesh-format.

[sinbad]

It's things like this that keep putting this one on the back burner. It sounds fairly easy at first, but in practice there's a few niggles - I'm interested to hear your thoughts / suggestions - it'll probably be a compromise in the end.

[oddrose]

If you're trying to upgrade the Mesh, it won't work unless you also have the Skeleton avaliable since you won't be able to calculate the padding value. You either have to fail (do not upgrade), or ignore it (which means the padding value will be set to some incorrect value, which the next time the Mesh is loaded, you won't be able to tell that it's not correct and that you should be recalculating it when the Skeleton becomes available).

I don't agree with you here. I think the options are:
A) Original file has padding calculated: keep padding
B) Original file has padding unset: leave unset

I made a chart over the possible outcomes and included it below. The check if the skeleton is available below the processing instances are mean to represent a check within the instance. So for the exporter, the check below it determines if the exporter should calculate the padding or not. According to this (maybe optimistic?) chart, every outcome gives a correct value for the padding except in one case where the mesh won't be animated anyway.

You're right that it becomes persistent though. If you don't have the skeleton available for the upgrader, you will have to calculate the padding every time you load the mesh.
But to put the padding in the .mesh you will have to have the skeleton available at some point.
I guess an implicit upgrade (You calculate the padding at the first load and write it to the .mesh) is possible but not preferable.

Also, if you know a better way to do these charts than in Word, please let me know...I've heard VS should be able to do it, but I didn't find it at this moment so I used what I knew worked.

[sinbad]

I quite like Dia for diagrams like this.

Yes, you're right, although it does mean you need another variable on Mesh to indicate whether the padding has been calculated or not, or use a control value (-1 or something) to indicate that it's not valid. Otherwise you don't know whether the value (assuming it's just a Real) is valid or not when you're just looking at a Mesh outside of the load context.

[oddrose]

I quite like Dia for diagrams like this.

Yes, you're right, although it does mean you need another variable on Mesh to indicate whether the padding has been calculated or not, or use a control value (-1 or something) to indicate that it's not valid. Otherwise you don't know whether the value (assuming it's just a Real) is valid or not when you're just looking at a Mesh outside of the load context.

Thanks for the tip!

I agree with you in part. I meant, though, that the padding should only BE in file if it is correctly calculated. So in the exporter, if the skeleton is not present, don't write the padding real to the file. Same goes for all the other instances. So the presence of the real itself is indicator that the padding is calculated. Basically, take any situation that involves writing a faulty padding and instead don't make sure it is not in the file.

I'm not sure if this violates some rules regarding the mesh file format. I mean, this solution basically says that all possible data in one file version is not required to be in a file of that version. However, since the importer determines the version of the file from the header and not from the file contents, the problem is more a design philosophy aspect than a practical matter.

I would prefer to avoid control values since the mesh in theory could have bounds inside the bone bounds...I'm not sure how this would be calculated though...since it depends on whether the mesh is closed or not. It's hard to explain but imagine bones outside of a body and you get what I'm talking about. Maybe we'll look past that case for now.

[sinbad]

I agree with you in part. I meant, though, that the padding should only BE in file if it is correctly calculated. So in the exporter, if the skeleton is not present, don't write the padding real to the file. Same goes for all the other instances. So the presence of the real itself is indicator that the padding is calculated. Basically, take any situation that involves writing a faulty padding and instead don't make sure it is not in the file.

Yeah I know, but my point was that once the Mesh has been loaded, and you don't have the file anymore, you need to have a record in the in-memory Mesh to tell you whether the new member variable (which is just a Real) is the result of genuine information that has been loaded / calculated or not. Remember that Meshes can be constructed in code too, or converted from other sources, and that if you load a Mesh which doesn't have this information you need to remember that fact somewhere, otherwise you'll never know if you need to trigger the calculation or not. You can't just rely on dealing with it once at the point of loading from a .mesh file.

I would prefer to avoid control values since the mesh in theory could have bounds inside the bone bounds...I'm not sure how this would be calculated though...since it depends on whether the mesh is closed or not. It's hard to explain but imagine bones outside of a body and you get what I'm talking about. Maybe we'll look past that case for now.

I prefer explicit flags to control values too - but -1 would be usable at a push because I assumed we were talking about storing an absolute distance, which could never be negative.

[oddrose]

Yeah I know, but my point was that once the Mesh has been loaded, and you don't have the file anymore, you need to have a record in the in-memory Mesh to tell you whether the new member variable (which is just a Real) is the result of genuine information that has been loaded / calculated or not. Remember that Meshes can be constructed in code too, or converted from other sources, and that if you load a Mesh which doesn't have this information you need to remember that fact somewhere, otherwise you'll never know if you need to trigger the calculation or not. You can't just rely on dealing with it once at the point of loading from a .mesh file.

Oh, you're right of course. Okay then I think I'll start building now if my schedule lets me. I'll use -1 as a control value for now.
Except for this last discussion I will follow the plan I presented above.

Thanks a lot for your help to get here!