java-topology/docs/tickets/libgdx-0002-modelbuilder-rebuildreferences-array-contains.md

libgdx-0002: ModelBuilder.rebuildReferences — O(N²) Array.contains() inside node-part loop

Severity: HIGH File: gdx/src/com/badlogic/gdx/graphics/g3d/utils/ModelBuilder.java Line: 371–381 Status: PATCHED

Description

ModelBuilder.rebuildReferences() is the public static utility called after model construction to rebuild the model's flat materials, meshParts, and meshes arrays from the node hierarchy. For each NodePart of each Node (recursively), it calls Array.contains() three times — once each for model.materials, model.meshParts, and model.meshes.

Array.contains(value, identity) is a linear scan: O(M) where M is the current array size. With N node-parts and M accumulated distinct entries, total cost is O(N × M) — quadratic in the number of parts.

This is invoked from ModelBuilder.end() every time a model is built from parts, and is also exposed as a public API (ModelBuilder.rebuildReferences(Model)), making it a potential hotspot any time a user re-syncs model references.

Root Cause

// ModelBuilder.java:371-381
private static void rebuildReferences (final Model model, final Node node) {
    for (final NodePart mpm : node.parts) {
        if (!model.materials.contains(mpm.material, true))   // O(M) linear scan
            model.materials.add(mpm.material);
        if (!model.meshParts.contains(mpm.meshPart, true)) { // O(P) linear scan
            model.meshParts.add(mpm.meshPart);
            if (!model.meshes.contains(mpm.meshPart.mesh, true)) // O(X) linear scan
                model.meshes.add(mpm.meshPart.mesh);
            model.manageDisposable(mpm.meshPart.mesh);
        }
    }
    for (final Node child : node.getChildren())
        rebuildReferences(model, child);
}

Array<T>.contains(value, identity=true) iterates all elements with == comparison. No IdentityHashSet or ObjectSet is used for deduplication.

Fix

Build identity-based sets in the public rebuildReferences(Model) method and pass them into the recursive helper to replace O(N) contains() calls with O(1) set lookups.

public static void rebuildReferences (final Model model) {
    model.materials.clear();
    model.meshes.clear();
    model.meshParts.clear();
    // Identity sets for O(1) deduplication
    IdentityHashMap<Material, Boolean> matSeen = new IdentityHashMap<>();
    IdentityHashMap<MeshPart, Boolean> partSeen = new IdentityHashMap<>();
    IdentityHashMap<Mesh, Boolean> meshSeen = new IdentityHashMap<>();
    for (final Node node : model.nodes)
        rebuildReferences(model, node, matSeen, partSeen, meshSeen);
}

private static void rebuildReferences (final Model model, final Node node,
    IdentityHashMap<Material, Boolean> matSeen,
    IdentityHashMap<MeshPart, Boolean> partSeen,
    IdentityHashMap<Mesh, Boolean> meshSeen) {
    for (final NodePart mpm : node.parts) {
        if (matSeen.put(mpm.material, Boolean.TRUE) == null)       // O(1)
            model.materials.add(mpm.material);
        if (partSeen.put(mpm.meshPart, Boolean.TRUE) == null) {    // O(1)
            model.meshParts.add(mpm.meshPart);
            if (meshSeen.put(mpm.meshPart.mesh, Boolean.TRUE) == null) // O(1)
                model.meshes.add(mpm.meshPart.mesh);
            model.manageDisposable(mpm.meshPart.mesh);
        }
    }
    for (final Node child : node.getChildren())
        rebuildReferences(model, child, matSeen, partSeen, meshSeen);
}

Speedup

Node-parts	Materials	Before	After
500	50	25 000 comparisons	~500 ops
2 000	200	400 000 comparisons	~2 000 ops
10 000	1 000	10 000 000 comparisons	~10 000 ops

Estimated 50–1000x speedup for large model hierarchies (animated characters, skeletal meshes with many sub-meshes, procedurally-generated geometry).