A retained-mode 3D engine (like a scene graph built out of nodes with an id, a transform, a visibility flag, and a list of children -- the shape of three.js's Object3D tree) keeps its live scene alive across frames rather than rebuilding it from scratch every time. When a new DESCRIPTION of the scene arrives -- loaded from a file, produced by a declarative layer on top, whatever the source -- the engine shouldn't discard its tree and rebuild it; it should compute the MINIMAL set of updates needed to bring the old tree in line with the new one, and apply just those.

Implement diff_scene_graph(old_tree, new_tree), returning a list of ops:

• ("add", node_id, parent_id, transform, visible) -- a node present in new_tree but not old_tree.
• ("remove", node_id) -- a node present in old_tree but not new_tree.
• ("update_transform", node_id, new_transform) -- present in both, but its transform differs.

Each node is {"id": ..., "transform": ..., "visible": ..., "children": [...]}. Nodes are matched between the two trees BY ID, not by position in the children list -- walk both trees together, keyed by id. Assume a node's id never moves to a different parent between the two trees.

Example

old = {"id": "root", "transform": (0,0,0), "visible": True, "children": [
    {"id": "a", "transform": (0,0,0), "visible": True, "children": []},
]}
new = {"id": "root", "transform": (0,0,0), "visible": True, "children": [
    {"id": "a", "transform": (5,0,0), "visible": True, "children": []},
    {"id": "b", "transform": (1,1,1), "visible": True, "children": []},
]}
diff_scene_graph(old, new)
# -> [("update_transform", "a", (5,0,0)), ("add", "b", "root", (1,1,1), True)]

Constraints

• Identical trees produce an empty op list -- no false positives.
• Removing an internal node implicitly removes every one of its descendants -- each of them gets its own ("remove", ...) op.
• Adding a subtree produces an ("add", ...) op for every node in it, each carrying ITS OWN immediate parent's id (a grandchild's parent_id is its direct parent, not the root).
• A node whose transform is unchanged produces no op for that node, even if a sibling elsewhere in the tree did change.

Real-world grounding

• three.js's Object3D is the retained-mode node shape this exercise's tree models: an id, a visible flag, a transform, and a children array mutated via add()/remove(): src/core/Object3D.js. Note this file is the persistent node structure being reconciled onto -- three.js itself mutates that structure directly via imperative calls rather than diffing two whole trees, so the diffing ALGORITHM here is the general reconciliation problem any retained-mode renderer faces when scene state is produced by something other than direct imperative calls (a file loader, a declarative layer, a network sync), not a literal port of a three.js source file.

A production version of this would also need to handle reparenting (a node moving to a different parent) as an explicit "move" op rather than this exercise's out-of-scope assumption that parents never change, and would likely diff visible as its own op type alongside transform.