# 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

```java
// 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.

```java
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).