java-topology/docs/tickets/libgdx-0001-model-loadnode-nested-linear-scan.md

libgdx-0001: Model.loadNode — O(N²) nested for-loop string-ID lookup during model load

Severity: HIGH File: gdx/src/com/badlogic/gdx/graphics/g3d/Model.java Line: 190–210 Status: PATCHED

Description

Model.loadNode() is called for every node when loading a 3D model. For each ModelNodePart of each node, it scans the full meshParts array to find a matching meshPartId (string comparison) and then scans the full materials array to find a matching materialId (string comparison).

When a model has P node-parts, M mesh-parts, and T materials, the total cost is O(P × (M + T)) — quadratic in total element count.

The libGDX developers have already identified this: a // FIXME create temporary maps for faster lookup? comment appears on line 188, directly above the offending code.

Root Cause

// Model.java:188-210
// FIXME create temporary maps for faster lookup?
if (modelNode.parts != null) {
    for (ModelNodePart modelNodePart : modelNode.parts) {
        MeshPart meshPart = null;
        Material meshMaterial = null;

        if (modelNodePart.meshPartId != null) {
            for (MeshPart part : meshParts) {                         // O(M) per node-part
                if (modelNodePart.meshPartId.equals(part.id)) {
                    meshPart = part;
                    break;
                }
            }
        }

        if (modelNodePart.materialId != null) {
            for (Material material : materials) {                     // O(T) per node-part
                if (modelNodePart.materialId.equals(material.id)) {
                    meshMaterial = material;
                    break;
                }
            }
        }
    }
}

meshParts and materials are Array<T> (libGDX's dynamic array) — O(N) linear scan. No lookup maps are built before processing nodes.

Fix

Build HashMap<String, MeshPart> and HashMap<String, Material> once before iterating nodes, then use O(1) map lookups inside the loop.

// Build lookup maps once before loadNodes loop
Map<String, MeshPart> meshPartById = new HashMap<>();
for (MeshPart part : meshParts) meshPartById.put(part.id, part);

Map<String, Material> materialById = new HashMap<>();
for (Material mat : materials) materialById.put(mat.id, mat);

// Inside loadNode:
if (modelNodePart.meshPartId != null)
    meshPart = meshPartById.get(modelNodePart.meshPartId);         // O(1)

if (modelNodePart.materialId != null)
    meshMaterial = materialById.get(modelNodePart.materialId);     // O(1)

Speedup

Node-parts	MeshParts + Materials	Before	After
100	50	5 000 comparisons	~100 lookups
1 000	200	200 000 comparisons	~1 000 lookups
5 000	500	2 500 000 comparisons	~5 000 lookups

Estimated 50–500x speedup for complex models (character models, level geometry with many meshes and material variants). Converts model load time from O(N²) to O(N).