Culling animated models.

[mre4ce]

While the accessor min/max for POSITION can be used to cull a static mesh, there appears to be no good way to cull an animated mesh. To cull animated meshes I ended up adding:

skin.jointGeometryMins
skin.jointGeometryMaxs

These are accessors to arrays of GL_FLOAT VEC3 with for each joint the local space mins/maxs of all vertices that are influenced by the joint. Using affine joint transforms, it is not particularly computationally intensive to calculate the global space mins/maxs for each joint.

typedef struct
{
    float x;
    float y;
    float z;
} Vector3f_t;

// Column-major 4x4 matrix
typedef struct
{
    float m[4][4];
} Matrix4x4f_t;

static void Matrix4x4f_TransformBounds( Vector3f_t * resultMins, Vector3f_t * resultMaxs, const Matrix4x4f_t * matrix, const Vector3f_t * mins, const Vector3f_t * maxs )
{
    assert( Matrix4x4f_IsAffine( matrix, 1e-4f ) );

    const Vector3f_t center = { ( mins->x + maxs->x ) * 0.5f, ( mins->y + maxs->y ) * 0.5f, ( mins->z + maxs->z ) * 0.5f };
    const Vector3f_t extents = { maxs->x - center.x, maxs->y - center.y, maxs->z - center.z };
    const Vector3f_t newCenter =
    {
        matrix->m[0][0] * center.x + matrix->m[1][0] * center.y + matrix->m[2][0] * center.z + matrix->m[3][0],
        matrix->m[0][1] * center.x + matrix->m[1][1] * center.y + matrix->m[2][1] * center.z + matrix->m[3][1],
        matrix->m[0][2] * center.x + matrix->m[1][2] * center.y + matrix->m[2][2] * center.z + matrix->m[3][2]
    };
    const Vector3f_t newExtents =
    {
        fabsf( extents.x * matrix->m[0][0] ) + fabsf( extents.y * matrix->m[1][0] ) + fabsf( extents.z * matrix->m[2][0] ),
        fabsf( extents.x * matrix->m[0][1] ) + fabsf( extents.y * matrix->m[1][1] ) + fabsf( extents.z * matrix->m[2][1] ),
        fabsf( extents.x * matrix->m[0][2] ) + fabsf( extents.y * matrix->m[1][2] ) + fabsf( extents.z * matrix->m[2][2] )
    };
    Vector3f_Sub( resultMins, &newCenter, &newExtents );
    Vector3f_Add( resultMaxs, &newCenter, &newExtents );
}

Accumulating the mins/maxs for all joints of a skin is trivial.

I chose AABBs as bounding volumes because of their simplicity.

You could use spheres but you would still have to offset them from the joints to accurately contain the geometry (imagine a car driving around attached to a single joint that is not centered inside the car). It is also unclear what to do with a sphere that is attached to a joint with non-uniform scaling.

You could use OBBs as bounding volumes but in my experience OBBs tend to add complexity and a lot of extra math for small culling gains. Non-uniform scaling of OBBs is also non-trivial.

At the end of the day culling is a trade between CPU and GPU usage. Spending a lot of time on the CPU is usually ill-advised.

[lexaknyazev]

Does this effectively require 1:1:1 skin-mesh-animation binding, or do you accumulate over all existing combinations?

[mre4ce]

This is animation independent. It just uses the joint/node transforms and they can be modified manually/programmatically as well. That's part of the reason I chose this approach as opposed to storing precalculated bounds per animation key frame, which would not only consume a lot of space but also doesn't account for animation blending or manually/programmatically changing the joint transforms.

There also does not need to be a 1:1 mapping between a skin and mesh. If multiple meshes use the same skin then the local mins/maxs per joint just need to include all vertices that are influenced by the joint. The downside is that if you calculate the total bounds per skin then you may end up with a larger bounds per mesh because it may include joints/vertices that do not affect the particular mesh. I don't think this is a big problem though because having multiple meshes per skin is probably not all that common and when it does happen, the meshes typically are part of the same "model" so it's fine to use a single bounds for all "surfaces" of that "model".

With that said, you could store the jointGeometryMins/jointGeometryMaxs on a mesh. But then you could store the skin.jointNames on the mesh as well. The existence of "skins" seems to be to be able to have a single joint array for multiple meshes. Culling per skin also allows you to not update the joint array if the skin is not in the view frustum. This is worth considering when you use a uniform buffer to store the joint matrices (which I am). Nobody wants to limit the number of joints per mesh by the maximum number of individual uniforms.

Maybe there are other good reasons to have separate skins but I'd be perfectly happy getting rid of skins and storing the relevant properties directly on a mesh. If skins are kept then it may be better to have a mesh reference a skin as opposed to having a node reference one skin and potentially multiple meshes. I also have found no use for listing "skeletons" per node but that's getting off topic.

[lexaknyazev]

Please, correct me if I'm wrong:
for each joint you apply inverseBindMatrix (and skeleton node transform?) to affected vertices, and store such "sub"-bounding box in skin.jointGeometryMins/Maxs arrays?

[mre4ce]

In the converter (fbx2gltf) I first skin each vertex just like you would on the GPU. Then for each vertex I transform the skinned vertex into the local space of the joints that influence the vertex and add these local space positions to the mins/maxs of the joints. In other words, for each vertex I do the following:

FbxVector4 fbxPosition;
int jointIndices[MAX_WEIGHTS];
float jointWeights[MAX_WEIGHTS];

FbxMatrix skinningMatrix;
for ( int i = 0; i < MAX_WEIGHTS; i++ )
{
    skinningMatrix += globalNodeTransform[jointIndices[i]] * inverseBindMatrices[jointIndices[i]] * bindShapeMatrix * jointWeights[i];
}
const FbxVector4 globalPosition = skinningMatrix.MultNormalize( fbxPosition );
for ( int i = 0; i < MAX_WEIGHTS; i++ )
{
    if ( jointWeights[i] > 0.0f )
    {
        const FbxVector4 localPosition = globalNodeTransform[jointIndices[i]].Inverse().MultNormalize( globalPosition );
        jointGeometryMins[jointIndices[i]].x = min( jointGeometryMins[jointIndices[i]].x, (float)localPosition[0] );
        jointGeometryMins[jointIndices[i]].y = min( jointGeometryMins[jointIndices[i]].y, (float)localPosition[1] );
        jointGeometryMins[jointIndices[i]].z = min( jointGeometryMins[jointIndices[i]].z, (float)localPosition[2] );
        jointGeometryMaxs[jointIndices[i]].x = max( jointGeometryMaxs[jointIndices[i]].x, (float)localPosition[0] );
        jointGeometryMaxs[jointIndices[i]].y = max( jointGeometryMaxs[jointIndices[i]].y, (float)localPosition[1] );
        jointGeometryMaxs[jointIndices[i]].z = max( jointGeometryMaxs[jointIndices[i]].z, (float)localPosition[2] );
    }
}

At run-time I do the following:

for ( int i = 0; i < scene->skinCount; i++ )
{
    GltfSkin_t * skin = &scene->skins[i];

    Vector3f_Set( &skin->mins, FLT_MAX );
    Vector3f_Set( &skin->maxs, -FLT_MAX );
    for ( int j = 0; j < skin->jointCount; j++ )
    {
        Vector3f_t jointMins;
        Vector3f_t jointMaxs;
        Matrix4x4f_TransformBounds( &jointMins, &jointMaxs, &skin->joints[j].node->globalTransform, &skin->jointGeometryMins[j], &skin->jointGeometryMaxs[j] );
        Vector3f_Min( &skin->mins, &skin->mins, &jointMins );
        Vector3f_Max( &skin->maxs, &skin->maxs, &jointMaxs );
    }
}

As you pointed out previously, you can do this per skin (which I am doing here) or you can do this for different subsets of joints.

[lexaknyazev]

As I can see from the code above, current skinning indirection does more harm than good:

1. The same skin could be used with different meshes (you've already mentioned drawbacks).
2. The same skin could be used with different meshes with different skeletons hierarchies (with different node transforms, even worse boundaries uncertainty).
3. Existing of jointNames adds more complexity without any clear benefits (also see Tightening up skinning #624 (comment)).

[mre4ce]

Sharing a "skin" among multiple meshes isn't necessarily bad and allows you to share a single joint array (or uniform buffer). Multiplying with the inverseBindMatrices and updating a uniform buffer isn't free after all. However, I would get rid of the "skin" and "skeletons" references on nodes and just have a mesh directly reference a skin. I would also get rid of the "jointName" on nodes and directly reference the nodes that transform the mesh. As far as I'm concerned any node can be part of any skeleton.

Anyway, as for culling animated meshes, this is just one idea. While I need a solution right now, there may be other/better solutions?

[lexaknyazev]

Sharing a "skin" among multiple meshes isn't necessarily bad and allows you to share a single joint array (or uniform buffer). Multiplying with the inverseBindMatrices and updating a uniform buffer isn't free after all.

Isn't this more like an implementation issue than a spec one?
Currently, skin consists of a bindShapeMatrix, an inverseBindMatrices accessor, and a jointNames array. However skin "instance" also needs an array of skeleton's root nodes. If multiple meshes have the same skin, but different skeletons, you still need to update uniform buffer because of different globalNodeTransforms.

In theory, jointNames allow asset to have different "versions" of the skeleton tree for the same skin (and switch them with the value of skeletons property), but does runtime asset format need to support such a rare case? To avoid IBM data duplication, different skins could use the same accessor anyway.

Also it's not quite clear, why do we have skeletons as an array, considering that its elements must be top-level nodes. I could think of sophisticated re-usage of skeleton subtrees, but is it a widely supported technique?

With all your feedback, let's evaluate the following schema changes:

• move skin property from nodeto mesh, and store skin object directly to prevent its unintended re-usage;
• remove top-level skins;
• remove skeletons property from node;
• rename jointNames to joints and use global IDs;
• maybe also remove bindShapeMatrix.

Here's an example:

{
    "meshes": {
        "Cylinder-mesh": {
            "primitives": [{
                "attributes": {
                    "JOINT": "accessor_40",
                    "NORMAL": "accessor_20",
                    "POSITION": "accessor_18",
                    "WEIGHT": "accessor_37"
                },
                "indices": "accessor_16"
            }],
            "skin": {
                "inverseBindMatrices": "IBM_accessor",
                "joints": [
                    "Bone",
                    "Bone_001"
                ],
                "jointGeometryMins": "mins_accessor",
                "jointGeometryMaxs": "maxs_accessor"
            }
        }
    },
    "nodes": {
        "Bone": {
            "children": [
                "Bone_001"
            ],
            "rotation": [
                0.70474,
                0,
                0,
                0.709465
            ],
            "translation": [
                0, -3.15606e-007, -4.18033
            ]
        },
        "Bone_001": {
            "rotation": [
                0.00205211,
                9.94789e-008,
                0.000291371,
                0.999998
            ],
            "translation": [
                0,
                4.18717,
                0
            ]
        },
        "Cylinder": {
            "meshes": [
                "Cylinder-mesh"
            ]
        }
    }
}

This approach eliminates a couple of not-so-obvious issues, such as:

• scope of jointName, mixing skeleton trees with each other;
• inability to attach several skinned meshes to one node.

I can see only one (for now) major drawback here:
what if we need two (or more) instances of the same mesh, but with different animations? Since animation.channel.target must use skeleton node ID, such animation affects all mesh instances simultaneously. Maybe some kind of "skeleton instancing" could help here.

[mre4ce]

You raise a very good point about playing different animations on different instances of the same mesh. The logical thing to do would be to use two separate sub-trees and two skins. However, that means you cannot reference the skin from the mesh. So maybe we should list a (mesh,skin) pair on a node? Note that this is singular. Do we need to be able to list multiple meshes on a single node? Afaik the FBX format doesn't support this for instance. Every node has a single attribute (mesh, camera, light etc.)

[lexaknyazev]

Sorry for the delay,

Do we need to be able to list multiple meshes on a single node?

The only use case I can think of: "augmentation" of a mesh with other mesh (character outfit upgrade?) Of course, it could be replaced with one more node.

So maybe we should list a (mesh,skin) pair on a node?

If we move skin out of mesh, jointGeometryMins/Maxs won't be linked explicitly with a particular mesh, and preserving data consistency will be more difficult.

So maybe we should move them out of mesh too:

{
    "meshes": {
        "Cylinder-mesh": {
            "primitives": [{
                "attributes": {
                    "JOINT": "accessor_40",
                    "NORMAL": "accessor_20",
                    "POSITION": "accessor_18",
                    "WEIGHT": "accessor_37"
                },
                "indices": "accessor_16"
            }]
        }
    },
    "skins": {
        "skin_01": {
            "inverseBindMatrices": "IBM_accessor",
            "joints": [
                "Bone",
                "Bone_001"
            ]
        }
    },
    "nodes": {
        "Bone": {
            "children": [
                "Bone_001"
            ],
            "rotation": [
                0.70474,
                0,
                0,
                0.709465
            ],
            "translation": [
                0, -3.15606e-007, -4.18033
            ]
        },
        "Bone_001": {
            "rotation": [
                0.00205211,
                9.94789e-008,
                0.000291371,
                0.999998
            ],
            "translation": [
                0,
                4.18717,
                0
            ]
        },
        "Cylinder": {
            "meshes": [
                "Cylinder-mesh"
            ],
            "skin": "skin_01",
            "bounds": {
                "jointGeometryMins": "mins_accessor",
                "jointGeometryMaxs": "maxs_accessor"
            }
        }
    }
}

node.bounds could be extended with more information later: there was a discussion on that: #507.

[mre4ce]

It seems "inverseBindMatrices", "jointGeometryMins" and "jointGeometryMaxs" are inherently tied to a specific mesh (you can't use them with a different mesh anyway). So what about leaving those on the mesh (and get rid of "bindShapeMatrix") and having a skin that just lists an array of joints allowing a single mesh to be mapped to multiple sub-skeletons.

Does COLLADA support multiple meshes per node?

[lexaknyazev]

Does COLLADA support multiple meshes per node?

Yes, but we don't have to do the same in glTF, imho.

It seems "inverseBindMatrices", "jointGeometryMins" and "jointGeometryMaxs" are inherently tied to a specific mesh (you can't use them with a different mesh anyway). So what about leaving those on the mesh (and get rid of "bindShapeMatrix")

+1 for tying them with mesh; bindShapeMatrix is almost useless in such case.

having a skin that just lists an array of joints allowing a single mesh to be mapped to multiple sub-skeletons

Can we re-use joint-tree with different meshes? Otherwise there's no need in a skin object with just one property joints.

Also we should state all reqs on the elements of joints array, such as:

• no duplicates (?)
• joints.length == ibm_accessor.count (?)

[pjcozzi]

@lexaknyazev is it reasonable to scope these skinning changes for 1.0.1? If we're going to make breaking changes - and it sounds like we should - I would like to do them soon so we minimize impact on the forming software ecosystem.

@mre4ce it is perfectly valid for you to put jointGeometryMins and jointGeometryMaxs in a skins.extras property and then have your engine know to look for them. However, I do agree that this ultimately needs to be part of the core spec in some form. I have known about the potential problem for years, but, perhaps surprisingly, it has never manifested itself in Cesium due to the typical camera angles and coarse bounding volumes. Since this GitHub issue has moved to core skins, can we open a separate issue for this? Also, is it OK to push post 1.0.1 to control the scope?

[lexaknyazev]

@lexaknyazev is it reasonable to scope these skinning changes for 1.0.1? If we're going to make breaking changes - and it sounds like we should - I would like to do them soon so we minimize impact on the forming software ecosystem.

Absolutely reasonable, current skinning indirection isn't perfect.

[pjcozzi]

Absolutely reasonable, current skinning indirection isn't perfect.

Sounds good, I defer to you and @mre4ce here - our skinning experts!

[pjcozzi]

CC #624, "Tightening up skinning"

[mre4ce]

@pjcozzi, you mention ".extras". Why is there a ".extras" field when using JSON you can just add arbitrary names directly on the object? While using ".extras" may avoid name conflicts with existing members, it doesn't avoid name conflicts between different extensions.

[lexaknyazev]

Why is there a ".extras" field when using JSON you can just add arbitrary names directly on the object? While using ".extras" may avoid name conflicts with existing members, it doesn't avoid name conflicts between different extensions.

extras is intended for per-application usage, not per-feature or per-vendor. So you can safely add any fields to it (or use extras as an array or even as field itself). This prevents conflicts with existing members, existing optional members, and also possible future members.

[pjcozzi]

@lexaknyazev is right; the main intention was to forward compatibility. Perhaps somewhat overkill, I think it is a safe practice that doesn't overly bloat the JSON and perhaps even nicely adds to the separation of concerns.

[pjcozzi]

@lexaknyazev changes for 1.1 for this issue are up to you and @mre4ce. I doubt I will provide much value here.

[lexaknyazev]

Example in the comment above implies following schema changes from glTF 1.0:

• removal of node.jointName;
• renaming of skin.jointNames to skin.joints, that array contains IDs of nodes;
• removal of node.skeletons, since skin references nodes directly

@amwatson @mre4ce
Is it something that we should make in the upcoming glTF 1.1 (not glTF Next) release to simplify implementations and reduce existing indirection?

Other possible approach to tighten skinning is to add restrictions from #624 (comment) and #624 (comment):

• skeleton tree must contain only skeleton nodes. No node from non-skeleton tree can contain jointName;
• top-level skeleton node must be top-level glTF node;
• jointName is skeleton-tree scoped;
• colliding jointNames from two or more referenced skeletons aren't allowed.

[donmccurdy]

AFAIK this is resolved in glTF 2.0, with a few remaining issues that are being addressed elsewhere.

[Selmar]

I don't feel like the original question has been addressed at all. It seems to me that, currently, to do culling of animated nodes, the same process as mentioned in the original post has to be applied?

[lexaknyazev]

You're right. The issue is more about culling rather than tightening the spec.
We'd need an extension to store pre-computed bounding boxes.

[scurest]

While the accessor min/max for POSITION can be used to cull a static mesh, there appears to be no good way to cull an animated mesh.

For what it's worth, the accessor min/max for POSITION gives only a bounding box, not necessarily the tightest one (unless indices is omitted), which you would presumably want for culling.

(Lazy way of computing min/max: append [-3.4028235e38, -3.4028235e38, -3.4028235e38, +3.4028235e38, +3.4028235e38, +3.4028235e38] to the end of your POSITION array and give min: [-3.4028235e38, -3.4028235e38, -3.4028235e38], max: [+3.4028235e38, +3.4028235e38, +3.4028235e38] in the accessor. Don't change your indices. Less perversely, some files with multiple meshes/primitives put all their vertex positions in one accessor and all the meshes use that same accessor just with different indices (I know the Sketchup exporter did, see ksons/gltf-blender-importer#29 (comment)) so there is only one min/max for the accessor but there would be multiple bounding boxes for the different models.)

It is a more minor point, but for a mesh with multiple primitives or with morph targets you'd need to do some computation to find out what the whole mesh's bounding box is.

So even for a static mesh, there isn't really a good bounding box.

---

For representing bounding volumes for a mesh instance, a really simple idea is to use a "standard volume" in the space of some node created for that purpose, eg. the node that instantiates the mesh just has to say in an extension "the unit cube in the space of node X is my bounding box". Everything else would be normal glTF: for an AABB you just set the translation on X to min and the scale to max-min; to animate the bounding box you just animate these properties like normal.

[pjcozzi]

Closing as duplicate with #507 (comment).

Proposals are very welcome. Feel free to re-open if you have a proposal.