September 6, 2017

While working on my webgl library for purescript, puregl, I needed to develop a scene graph structure to keep track of spatial relations between objects in a scene, and update all their transformation matrices.

We can take as a simple model for a scene graph something like in the image below: one root node which represents the spatial origin, and the rest of the tree, consisting of nodes holding spatial properties like position, rotation, scale and the node’s transformation matrix.

Usually we need to update the scene graph at each frame for rendering it. For this, we must traverse the tree, accumulating the values of the transform matrices along the way, since the matrix for a given node depends on the values of the matrices of all the other nodes above which are connected to it — i.e., of al it’s parents.

This operation is similar to performing a `scan{l,r}`

on an `Array`

, but as we’ll see, it can’t really be obtained by a `Traversable`

instance on a tree structure.

So, we need a data structure that holds a value, and zero or more children of the same type. Taking inspiration from Haskell’s `Data.Tree`

, we can defin a a `Tree`

data type in purescript as:

```
newtype Tree a = Node { value :: a
, children :: Forest a
}
type Forest a = List (Tree a)
```

The `Node`

constructor accepts a `Record`

holding the node value
of a given type `a`

and a `List`

of other `Tree`

s representing
the `Node`

’s children, which we call a `Forest`

. A data structure like this is called a multi-way, or rose tree, which is simply a tree with a variable and non-limited number of branches per node.

To make things easier, we can define a tree-creation function `mkTree`

with an infix operator:

```
mkTree :: forall a. a -> Forest a -> Tree a
mkTree a cs = Node { value: a, children: cs }
infix 5 mkTree as |>
```

And now we can create a tree like this,

```
sampleTree :: Tree Int
sampleTree =
1 |>
(2 |> Nil)
: (3 |> Nil)
: (4 |>
(5 |> Nil)
: (6 |>
(7 |> Nil) : Nil)
: (8 |> Nil)
: Nil
)
: Nil
```

Of course we need to define some functions and operations on the `Tree`

data structure we created so it can be useful in any way. We can start by defining a `Functor`

instance, so we can map functions into our `Tree`

:

```
instance functorTree :: Functor Tree where
map f (Node { value: v, children: cs }) =
(f v) |> ((map <<< map) f cs)
```

To map a function `f`

into the tree, we create a new tree with value `f v`

, and map the `Tree`

’s map into the `List`

of children nodes, by using the composition `(map <<< map)`

.

This works nicely, but there is a problem: it’s not stack-safe; since it’s a non-tail-call-optimized recursive function it will occur in a stack overflow error depending on the number of children of a node and the depth of the tree. To circumvent this, we can rewrite our `Functor`

implementation using the `tailRec`

function defined in the `purescript-tailrec`

package:

```
tailRec :: forall a b. (a -> Step a b) -> a -> b
data Step a b = Loop a | Done b
```

The `tailRec`

function allows us to write a stack-safe recursive function by supplying it with a function `a -> Step a b`

which returns `Loop a`

to call the next step in the recursion, or `Done b`

when the loop is finished, returning the final value.

We can, then, replace the `(map <<< map)`

recursion in our code by two nested `tailRec`

calls as in:

```
instance functorTree :: Functor Tree where
map f (Node {value:v, children: c}) =
mkTree (f v) (tailRec go {current: c, result: Nil})
where
go {current: Nil, result: r} = Done r
go {current: c:cs, result: r} =
Loop { current: cs
, result: snoc r
(mkTree (f (nodeValue c))
(tailRec go { current: (nodeChildren c)
, result: Nil
}))
}
nodeValue :: forall a. Tree a -> a
nodeValue (Node r) = r.value
nodeChildren :: forall a. Tree a -> Forest a
nodeChildren (Node r) = r.children
```

We can see that it works by applying it to the `sampleTree`

defined above in the `repl`

:

```
> log $ showTree $ ((+) 1) <$> sampleTree)
2
|----> 3
|----> 4
|----> 5
|----> 6
|----> 7
|----> 8
|----> 9
```

We can define a handful of other instances, as you check out in the `source code`

. Since we have a `Traversable`

instance for our tree, we can perform, for instance, a `scanl`

on a tree:

```
> log $ showTree (scanl (\b a -> a + b) 0 sampleTree)
1
|----> 3
|----> 6
|----> 10
|----> 15
|----> 21
|----> 28
|----> 36
```

We can see that the `scanl`

treats sibling nodes the same way it would when applying it to an array, accumulating values in each node and applying the accumulated value to the next sibling. In fact it just keeps accumulating values in a breath-first order in the tree.

But, as mentioned earlier, in the case of a scene graph we are interested in accumulating the value of a transformation matrix so that the accumulated value is the same for all sibling nodes, and depends only on the parent values. A scan function that accumulates values like this can be written like:

```
scanTree :: forall a b. (a -> b -> b) -> b -> Tree a -> Tree b
scanTree f b n@(Node {value: x, children: xs}) =
let fb = f x b
in fb |> (tailRec go {b: fb, current: xs, final: Nil})
where
go :: _ -> Step _ (Forest b)
go {b: b', current: Nil, final: final} = Done final
go {b: b', current: c:cs, final: final} =
let fb' = f (nodeValue c) b'
in Loop {b: b', current: cs, final: snoc final (fb' |> tailRec go {b: fb', current: (nodeChildren c), final: Nil})}
```

Notice that the top-level loop passes the same value of `b`

to all sibling nodes, while the inner loop passes the value of `b`

updated at the current node for it’s children. So, when applying to the same `sampleTree`

, we get the result:

```
> log $ showTree (scanTree (\b a -> a + b) 0 sampleTree)
1
|----> 3
|----> 4
|----> 5
|----> 10
|----> 11
|----> 18
|----> 13
```

So, all the children of the `1`

node are incremented by `1`

; the children of node `5`

are incremented by `5`

and the child of node `11`

is incremented by `11`

.

The final step in using our tree structure for a scene graph would be to generalize the `scanTree`

function so that the accumulated value and the final tree type can be of different type. This way we can accumulate a `Matrix`

along the tree,
while returning a `Tree SceneDataType`

in the end.

We can achieve that by changing the function used for scanning from `a -> b -> b`

to `a -> b -> Accum b c`

, where

```
type Accum s a = { accum :: s, value :: a }
```

as defined in `Data.Traversable.Accum`

. This allows us to accumulate values of `b`

but return values of a different arbitrary type `c`

. By simply replacing this on the `scanTree`

definition and doing some small adjustments we arrive at

```
scanTreeAccum :: forall a b c. (a -> b -> Accum b c) -> b -> Tree a -> Tree c
scanTreeAccum f b n@(Node {value: x, children: xs}) =
let fb = f x b
in fb.value |> (tailRec go {b: fb.accum , current: xs, final: Nil})
where
go :: _ -> Step _ (Forest c)
go {b: b', current: Nil, final: final} = Done final
go {b: b', current: c:cs, final: final} =
let fb' = f (nodeValue c) b'
in Loop {b: b', current: cs, final: snoc final (fb'.value |> tailRec go {b: fb'.accum, current: (nodeChildren c), final: Nil})}
```

To test this let’s take a very simple model for a scene graph where each node holds only two variables, one holding it’s local position and the other it’s global position in the scene:

```
type SceneTree = Tree { localPos :: Number
, globalPos :: Number
}
scene :: SceneTree
scene =
{ localPos: 0.0, globalPos: 0.0 } |>
({ localPos: 1.0, globalPos: 0.0 } |> Nil)
: ({ localPos: 2.0, globalPos: 0.0 } |> Nil)
: ({ localPos: 3.0, globalPos: 0.0 } |>
({ localPos: 4.0, globalPos: 0.0 } |> Nil )
: ({ localPos: 5.0, globalPos: 0.0 } |>
({localPos: 6.0, globalPos: 0.0 } |> Nil)
: Nil
)
: ({ localPos: 7.0, globalPos: 0.0 } |> Nil)
: Nil
)
:Nil
```

Using the `scanTreeAccum`

method on the `scene`

above with the function

```
\{localPos: l, globalPos: g} b -> {accum: b + l, value: {localPos: l, globalPos: b + l} }
```

we get the following result:

```
> log $ showTree $ (\r -> (show r.globalPos)) <$> (scanTreeAccum (\{localPos: l, globalPos: g} b -> {accum: b + l, value: {localPos: l, globalPos: b + l} } ) 0.0 scene)
"0.0"
|----> "1.0"
|----> "2.0"
|----> "3.0"
|----> "7.0"
|----> "8.0"
|----> "14.0"
|----> "10.0"
```

where the global positions are printed in each node. As we can se, each node’s global position is correctly updated by using the values of the global positions of the parents.

Now we can update our tree and do some other neat operations on it. But to use as a scene graph there are still some things missing, like the ability to easily insert and delete nodes, relocate nodes, and move around different locations in the tree.

It turns out that when dealing with immutable tree structures these operations are not exactly trivial. To do this in a convenient manner we need to introduce an additional data structure, a `Zipper`

, which I’ll talk about in the next post.

As suggested by @chrislpenner, we can define an Tree structure
equivalent to the one defined above in purescript by using the `Cofree`

type from the `purescript-free`

package:

```
data Cofree f a = Cofree a (Lazy (f (Cofree f a)))
type Tree a = Cofree List a
```

With this definition we automatically gain access to all the instances already defined for the
`Cofree`

type, which cover all the ones we defined above, simplifying greatly our code.

Initially I used the `Cofree`

approach for the `purescript-tree`

package, but changed to a `Record`

wrapped in `newtype`

thinking the performance would be better. But, as Chris pointed, doing so may be a case of premature optimization. So, considering the gain in simplicity, I updated `purescript-tree`

to use `Cofree`

base trees, and let’s see in the future if performance will even be an issue.

written by danielfortes. tweet this.