SceneGraph traversal in Haskell

Question

I want to implement a simple SceneGraph in Haskell using Data.Tree consisting of Transform and Shape nodes. In a SceneGraph the spatial transformation is accumulated while traversing and applied to the shape for rendering.

type Transform = Vector2 Double
data Shape     = Circle Double | Square Double
data SceneNode = XFormNode Transform | ShapeNode Shape

Say we have a scene with an object which is moved to the right and consisting of a Square at bottom and a Circle on top

^
|
|  ()
|  []
0----->

I came up with this tree definition:

let tree = Node (XFormNode (vector2 10 0))
                [Node (ShapeNode (Square 10)) []
                ,Node (XFormNode (vector2 0 10))
                      [Node (ShapeNode (Circle 10)) []]
                ]

The rendering would be something like this:

render :: Position2 -> Shape -> IO ()
render p (Circle r) = drawCircle p r
render p (Square a) = drawSquare p a

My questions are:

1) How do you define a traverse function, which accumulates the transformation and calls the render tasks?

2) How do you avoid making the traverse IO?

3) Is there a shorter version to define this tree? All but the first Node definition and all empty subForests are actually superfluous.

Thank you!

Answer 1

I like to represent trees as monadic lists with an underlying list monad. if this sentence is confusing, just look at the code:

import Control.Applicative (liftA2)
import Control.Monad.ListT (ListT) -- "List" in hackage
import Data.List.Class (cons, joinL, lastL, scanl) -- "List" in hackage
import Data.Monoid (mempty)
import Data.Tensor (Vector2 (..)) -- "Tensor" in hackage
import Prelude hiding (scanl)

type Transform = Vector2 Double
data Shape     = Circle Double | Square Double deriving Show
data SceneNode = XFormNode Transform | ShapeNode Shape deriving Show

tree :: ListT [] SceneNode
tree
    = cons (XFormNode (Vector2 10 0))
    $ joinL
        [ cons (ShapeNode (Square 10)) mempty
        , cons (XFormNode (Vector2 0 10)) $ cons (ShapeNode (Circle 10)) mempty
        ]

traverseStep :: (Transform, SceneNode) -> SceneNode -> (Transform, SceneNode)
traverseStep (ta, _) n@(XFormNode tb) = (liftA2 (+) ta tb, n)
traverseStep (t, _) n = (t, n)

ghci> lastL $ scanl traverseStep (Vector2 0 0, XFormNode (Vector2 0 0)) tree
[ (Vector2 10.0 0.0,  ShapeNode (Square 10.0))
, (Vector2 10.0 10.0, ShapeNode (Circle 10.0))
]

These trees differ from those in Data.Tree in that:

• You can use the existing functions for monads and lists (like scanl) for these.

• They can be monadic

  • For example a directory structure tree can be an IO-monadic tree which is generated as you iterate over it. Its type would be ListT (ListT IO) FilePath. See http://github.com/yairchu/generator/blob/master/ListTree/src/System/Directory/ListTree.hs for this example
• Leafs and nodes with 0 children are different things. This might make sense in some situations (for example to differentiate an empty directory from a file)
  • cons x mempty is a leaf, and cons x (joinL []) is a node with 0 children.

Answer 2

Paradoxically, Data.Tree is not used very often in Haskell because defining a custom tree type is so easy. In your case, I would implement the scene graph (tree) as follows:

type Transform = Vector2 Double
data Shape     = Circle Double | Square Double
data Scene     = Transform Transform [Scene] | Shape Shape

Your example becomes

example :: Scene
example = Transform (vector2 10 0)
                    [ Shape (Square 10)
                    , Transform (vector2 0 10) [Shape (Circle 10)]
                    ]

This answers point 3.

To traverse the tree, use recursion:

render :: Position2 -> Scene -> IO ()
render p (Transform v scenes) = mapM_ (render (p+v)) scenes
render p (Shape (Circle r))   = drawCircle p r
render p (Shape (Square a))   = drawSquare p a

There are more generic traversals available, for instance in Data.Traversable, but they are more "uniform". In short, using recursion on trees is perfectly fine.

Concering point 2, there is nothing much you can do once you decide that circles and squares should be rendered in the IO monad.