Parsing scene tree with Python

Coding
,
#1

Hello, devs!

I have a 3D scene tree represented as a hash map (JSON file). Is it possible to perform some tree operations with default Python tools or do I need to build (or use an existing library) a tree data structure?

tree

For example, I need to know if “B” is a parent of “H”. I can recursively traverse the tree and find “H” node, but how can I start getting parents of a node I found (even if I had “parent” attribute with a string name of a parent node)?

scene_data = {
    "hierarchy": {
        "A": {
            "properties": {
                "metadata": {}
            },
            "children": {
                "B": {
                    "properties": {
                        "metadata": {}
                    },
                    "children": {
                        "D": {
                            "properties": {
                                "metadata": {}
                            },
                            "children": {
                                "H": {
                                    "properties": {
                                        "metadata": {}
                                    },
                                    "children": {}
                                }
                            }
                        },
                        "E": {
                            "properties": {
                                "metadata": {}
                            },
                            "children": {
                                "I": {
                                    "properties": {
                                        "metadata": {}
                                    },
                                    "children": {}
                                }
                            }
                        }
                    }
                },
                "C": {
                    "properties": {
                        "metadata": {}
                    },
                    "children": {
                        "F": {
                            "properties": {
                                "metadata": {}
                            },
                            "children": {}
                        },
                        "G": {
                            "properties": {
                                "metadata": {}
                            },
                            "children": {}
                        }
                    }
                }
            }
        }
    }
}

def traverse_tree(node):

    for node_name, node_data in node.iteritems():

        if node_name == 'H':
            print 'Node Found!'

        traverse_tree(node_data['children'])


traverse_tree(scene_data['hierarchy'])
#2

Admittedly, I haven’t build a tree node from scratch but I have used one with django-mptt.
https://django-mptt.readthedocs.io/en/latest/

It’s specific to Django framework but perhaps you can find some insight in implementing it on your own project.

1 Like
#3

Your storage method (ie. json), and your internal representation (nodes, multiple dictionaries, etc…) certainly don’t have to match.
So when you read the json file, you could build a flat lookup table. Like this:

{
    'A': {'children': ['B', 'C']},
    'B': {'children': ['D', 'E']},
    'C': {'children': ['F', 'G']},
    'D': {'children': ['H']},
    'E': {'children': ['I']},
    'F': {'children': []},
    'G': {'children': []},
}

This way, you have access to each object by name without having to walk a tree each time, but you can still easily access object children.

Then, you could also programmatically add a ‘parent’ key to the dicts the first time you read through it. I wouldn’t store that data in the .json file itself because the two values could get out of sync if somebody edits the file by hand.

But personally, I would just make some kind of Node class with parent/children properties instead of using dictionaries.

2 Likes
#4

That was my initial idea, I just wanted to be sure that I am not building functionality that already exists in Python dictionaries. Initially, I was making the tree from JSON in Maya and then I was able to parse nodes with PyMel getParent(), getChildren() etc. Now I need to avoid the tree creation step.