Scenekit: Performance of SCNNode octrees/quadtrees vs all in root level

Question

To represent terrain in a SceneKit game, I have around 20k SCNNodes structured in a hierarchy, similar to an octree or quadtree. This tree isn't balanced - some branches have far more great(*n)-grandchildren than others.

How much extra time is SceneKit spending to get at individual SCNNodes for physics, rendering, adding/deleting nodes etc. compared to if they were all flat at the root level? Does it have to do lots of extra work to traverse the entire height of the tree just to iterate or perform a random access, or is it just not a significant overhead? (Maybe it's clever enough to have structured the nodes itself in advance?)

I'm not asking how a graphics engine might theoretically handle this. I'm asking what SceneKit actually does.

Edit: just in case it's putting people off answering this... I don't need exact numbers of how much time SceneKit takes, obviously that's device-dependent anyway. I just want to know if it's a significant proportion of time. Has anyone had experience of trying both approaches and comparing, or switching from one to the other and noticing whether there was a significant difference?

Thanks for your help.

Answer 1

I am also looking into this as my scene is starting to pack serious amount of nodes, but here's my take:

When you call the node.childNode(withName: String, recursively: true), this means the implementation uses some form of balanced or non balanced tree, take your pick between a binary tree, a-b tree b+ tree (in the case one node has multiple child nodes beyond a certain threshold), you will end up mostly with a log|n| complexity depending on whether you want to insert delete or search a tree structure. the AVL tree usually keeps the most used nodes up the hierarchy so you get less computation.

Just looking at the quad tree or R tree structures, they also probably have log|n| complexity since we're talking going into iterative sub quadrants of the root quadrant.

It would be good to know what kind of actual structure you got in terms of child nodes to see what best strategy to take.

On a side note, what prompts your terrain to have 20 k ndoes? aAre you attaching a node per bezier point or vertex on your terrain to do some morphing?