Lift maximum scene graph depth

I just stumbled over this gem in TempVars.java:

/** * Maximum tree depth .. 32 levels?? */ public final Spatial[] spatialStack = new Spatial[32];
Whenever somebody hits this, we’d get the same back-and-forth of a call for help, finding the issue, raising the limit.
I notice it’s easy to get rid of this limitation: The only place where it’s used is in Spatial.checkDoTransform, and there, it can be trivially replaced by recursing up the parent chain.

checkDoTransform claims it’s doing that to improve efficiency, but I doubt it. It’s trading a recursive no-argument call (i.e. two stack writes, one stack read, all in the same RAM cacheline) with an indexed heap write (filling the array), and indexed heap read (reading the array), and two local variable updates (i++ and j–). Plus there’s the overhead of accessing a thread-local variable (going through a hashmap) and requiring far more bytecode (loading CPU cache).

Am I overlooking something?

1 Like

I think the problem is that the update worldTransform at the end has to be applied from parent to children.
That’s why the hierarchy is flatten in an array from child to parent and then iterated backward to apply transforms…

That said…this could be done in a recursive call indeed. It Would be cleaner, not sure if it would be faster ( @pspeed what do you think recursive calls vs flat array iterating?)

Do you have an issue regarding this (like a scene graph with more than 32 levels) or is it for the sake of cleanliness?

1 Like

I don’t have any depth issues currently, no.
I’m not sure I’ll ever run into them; it’s hard to tell, I’m in exploratory design and can’t predict what the final product will need.

I can imagine various scenarios though.
One would be a model exporter that, for some reason only known to its author, tends to generate deeply nested models.
Another would be CAD. Imagine a factory model that goes right down to the millimeter screw. Throw in parts lists for aggregates, and the depth could increase pretty quickly.
Parts lists in general are feared for their nesting depth :slight_smile: . Explosion drawings might be built with additional levels for connection lines and general structuring, so the number of levels might be higher by a factor of 2 or 3 than the actual nesting level of the parts lists.
I could also imagine that people might want to fiddle with the tree structure to optimize collision checking.
Oh, and there’s a situation where the number of simultanously visible levels is really unbounded: Mandelbrot and Julia sets, zoomed in to a place where some large-scale and some arbitrarily small-scale structure touch. That’s going to be a very, very narrow tree, but the depth is limited only by the zoom factor that the user chose.

I’m pretty sure most if not all of these scenarios have a workaround, mostly even easy ones.
But not needing a workaround in the first place is always better than needing an easy one.
Besides, it’s surprising behaviour. Nothing in the scene graph docs say that there’s a depth limit, and if there were, people would overlook it because it’s so unexpected.
And it’s an easy fix :slight_smile:

1 Like

I just stumbled over this, too, while digging into jme3 scene graph. I have no problems with the nesting depth limited to 32, but I think it should be documented and it should fail more gracefully than “ArrayIndexOutOfBoundsException” (see test case below).

[java]
package mygame;

import com.jme3.app.SimpleApplication;
import com.jme3.scene.Node;

public class Main extends SimpleApplication
{
private Node innerNode;

public static void main(String[] args)
{
Main app = new Main();
app.start();
}

@Override
public void simpleInitApp()
{
innerNode = rootNode;
for (int i = 0; i < 33; i++)
{
Node child = new Node();
innerNode.attachChild(child);
innerNode = child;
}
}

@Override
public void simpleUpdate(float tpf)
{
innerNode.move(1f, 1f, 1f);
innerNode.getWorldTranslation();
}
}
[/java]

I think the 32 depth limit is a hardware limitation, where th3 GL_MODELVIEW matrix stack could only hold 32 matrices. That’s what my old opengl book wrote anyways

No, as @toolforger already mentioned, it’s because of a limitation in TempVars.java:
[java]
/**
* Maximum tree depth … 32 levels??
*/
public final Spatial[] spatialStack = new Spatial[32];
[/java]

This leads to “crash boom bang” here.

GL matrix stack stuff is supposed to be in the renderer implementation. It might become an issue after this one is fixed, but no idea.

right, I was saying why I think they gave it a value of 32. Idk if it is an issue anymore with modern hardware