Before We Start

Scene Graphs, the topic of this blog post, is actually a setup for the rest of the “Fun with Functional Reactive Programming” series, but it has nothing to do with functional reactive programming. Just this once, I’ll stem off for a quick post, then get back on with the FRP series.

Concept

Any time I see a new phrase, I am suspicious. My first thought is “is the phrase actually some new concept or meaning, or is it carefully constructed camouflage for something really obvious?” I used to think “yikes! These new words must mean the Creator of the Phrase had profound insight and knowledge beyond my grasp. I didn’t sleep beneath the Monolith long enough, and now I’ll never understand!” Time and experience have taught me that there are far more novel ways of describing ordinary things than there are truly novel things. So odds are, you probably already “know” what an unfamiliar phrase means, even if you don’t “know” you know. It usually just takes a little brain grease to transform the unfamiliar into the familiar…The “Scene Graph” is no exception. Allow me to explain: a scene is a set of elements that define something to be rendered or drawn. A scene graph is a data structure used to describe the contents of a scene, as well as their dependencies, to efficiently declare how the scene should be composed and, eventually, rendered. If you’ve seen a movie or looked at a picture, or watched tv, or even seen a play, EVER in your life, you already know what a scene is. It’s a description of all the things needed to convey some information, usually visually, to the audience. Let’s look at an example….

Spoiler alert, if you haven’t seen Die Hard, Hans Gruber dies…hard. I think that’s where they got the inspiration for the title.

For instance, in Hans Gruber’s death scene “Hans Dies At the End”) in Die Hard, there are a few of important elements that compose the scene:

• Falling, hate-filled Hans Gruber.
• Shiny 9MM pistol.
• Fluttering bearer bonds.
• Street view from 30 stories up.
• Night-time lighting.

Given that, we can probably describe the scene [the actual falling shot] like so:

Hans Gruber Death Scene:
---Night-time lighting:
------In background:
---------Street view from 30 stories up
---------Fluttering bearer bonds
------In foreground:
---------Falling, hate-filled Hans Gruber:
------------In right hand:
---------------Shiny 9MM pistol

That is, more or less, how a scene in a scene graph looks. The nested description of elements define the scene, where certain elements may have significant meaning that transforms the scene for child elements further down. The graph portion of scene graph comes from the relations implied by the nesting of the elements, in that they “should” actually form a Directed Acyclic Graph (a tree, or a directed graph with no cycles, or a forest/collection of such trees). For instance, in our Hans Gruber scene, “Night-time lighting” happens up at the top or root of the scene description, and presumably influences the rest of the elements in the scene. For instance, the Shiny 9mm pistol may not be as shiny at night; maybe it only shine as Hans waves it near building lights as he’s falling. The implicit parent/child relation created by the nesting, combined with a smart director, can efficiently interpret the scene, and make it come to life for the camera. For drama folks, it’s just a scene. For Computer science folks, it’s just a DAG or a tree. The important point is that the scene-graph is a useful description of a potentially complex process (the visualization of Hans Gruber falling, in a night time environment, from 30 stories up).

Motivation

Why do I (we) need scene graphs? As I was building a GUI library for Clojure, I found myself drawing a lot of shapes and doing primitive animation. Most of this was implemented via Java interop, using primitive Java2D shape operations, which necessarily contracted an imperative feel from touching the Java2D graphics substrate. As a result, I began looking for ways to make things like composing and drawing shapes more descriptive, more functional, and inherently more friendly to Clojure. I wanted to be able to say something like….“draw a red ball at the center of the screen, with a black line shooting off of the ball at a 15 degree angle” and let the renderer infer all of the imperative instructions for me. Things like actually translating the coordinate system to draw the ball, then changing the color of the graphics context to red, then drawing the ball, then translating to blah…Even with functional Clojure wrappers, the drawing process was still pretty ugly, pulling me back toward the Dark Side. So I dipped back into my memory archives and did some extra research…

A while back, during my first travels into functional programming land, I read the excellent book by Dr. Jon Harrop, F# for Scientists, hereafter known as F#fS. Disclaimer - F#fS is somewhat dated, although largely still entirely accurate. If you want the latest F# niceties or .Net 4.0 integration or VS2010 goodies, look at his other Technical computing stuff (which is really expensive), or the blogs. I still think, on the whole, that F#fS provides an incredible amount of technical computing goodies…in a - nearly - pure functional context, so it’s still a gem in my opinion. I’ve been using it for a lot of Clojure stuff, and continue to learn from it.

F#fS has a great section on using F# for interactive technical computing, particularly for visualization. Dr. Jon has a great section where he builds an interactive Direct3D renderer using F# algebraic data types (discriminated unions), and some slick functional code, in a ridiculously small amount of page space. He then goes on a rendering spree doing some really cool stuff with it. I’m not trying to advertise for Dr. Jon, but to illustrate where I first found out about scene graphs.

The renderer he built is based around a data structure [the scene graph], and some 3d rendering bits that eat the scene graph and turn into something that can be sprayed onto your monitor. Again, that’s basically what a scene graph does: it describes a scene so that the scene can be sprayed onto your monitor, likely using 2D or 3D hardware. The key here is that the scene graph is descriptive in nature. It’s also inherently a composite data structure….which means we can trivially compose primitive scenes with each other to create complex scenes. As Dr. Jon describes it, this facility is called Declarative Rendering, which is exactly what I wanted for my Clojure stuff. I wanted to be able to describe, or declare, what my drawing would look like, then let apply a renderer to the description, which would abstract away the “relatively” low-level Java2D (or possibly SVG or even HTML5 Canvas or OpenGL) calls for me.

Panning out a bit, it turns out that scene graphs are all the rage (and have been) for quite some time in the graphics industry. They’re new to me, but not new to the industry. In fact, Sun’s once-actively-developed Java 3d package, Java3D, is built around a 3d scene-graph implementation. You’ll find that many libraries these days use some form of a scene graph to handle rendering, because aside from the declarative utility that comes from them, you can encode other information like spatial relationships, to gain efficiency in the rendering process. For instance, if only a piece of a sub-graph of the scene graph needs to be modified and re-rendered, it’s unlikely that the entire screen would have to be redrawn. Scene graphs allow you to efficiently re-render things. Rather than blasting the entire screen every 60 frames per second (which might be entirely feasible for small scenes on mode hardware), you can smash a small subset of the pixels on an image buffer and quickly copy it for displaying on the hardware. This is “mo bettah,” especially if you have lots of static objects in your scene.

Clojure Implementation

This cljgui.scenegraph namespace extends the rendering model for drawing shapes into something a bit more robust. The idea is to allow declarative rendering. Note, there is quite a substantial library in cljgui.gui, which contains most of the primitive functions used to interact with Java2D, wrapped with Clojure.

(ns cljgui.scenegraph
  (:use [cljgui gui])
  (:import [java.awt AlphaComposite Graphics2D]))

(defprotocol IScene
  (draw [s g]))

(extend-protocol IScene
  nil
  (draw [s g] nil))

(defn render
  "Render scene onto graphics context g.  If scene is a primitive
   IShape, draw-shape from the IShape protocol is called, else draw
   from the IScene interface is called.  We use render as an auxillary
   function to allow us to differentiate between primitive shapes and
   composite scenes.  You will not see recursive calls to draw in any
   IScene's implementation of draw, but calls to render instead, which
   allows us to invoke draw-shape."
  [scene ^Graphics2D g]
  (if (satisfies? IShape scene)
      (draw-shape scene g)
      (draw scene g)))

We represent a scene as a nested datastructure (duh, this is lisp after all), using Clojure records. Records were chosen due to their speed, nice features, and the automatic ‘typing’ and inline protocol implementation. Each element of the scene graph will have one or more unique arguments for its specific role, with a final argument that consists of the “rest” of the scene, i.e. nil, or some other IScene.

Each structure corresponds to an operation on the scene context, which under the hood, is a transformation applied to the mutable Java2D graphics object that the scene is being rendered to. The scene itself is merely a structure, that is traversed depth-first when called by render with a graphics object as an arg. Since we’re dealing with a mutable Java2D graphics context under the hood, which is essentially a state machine, the rendering implementations for each element of the scene graph are careful to ‘undo’ their operations on the graphics object after rendering themselves and their children. This keeps the rendering context effectively immutable, and keps the declared structure of the scene consistent.

As we traverse the directed acyclic graph that describes the scene, any path in the graph describes an ordered list of transforms to apply to any graphics context, with leaf or terminal nodes resulting in actual rendered images or shapes. Since each node in the graph is an IScene, all nodes have a unified interpretation of draw from the IScene protocol, and we can draw the entire scene (traverse the graph in order, drawing each node as we go) by calling our render function on the root node of the scene.

Note - this implementation is somewhat lacking for high-performance apps like 2D games or million-point animated data plots, because it’s NOT leveraging all of the effeciencies of scene-graphs. Future versions will include spatial information in the scene graph to allow us to query and update (re-render) only portions of the scene that have changed. This ends up being drastically more efficient and scaleable. For our purposes, on mode hardware the current implementation is fast enough and can handle fairly complex scenes instantaneously. For games or demand scientific visualization (particularly with Java2D’s slooow alpha blending), we’d need to render the scene graph to alternative graphics contexts as well, basically OpenGL. There are several nice libraries for this, including PulpCore, Slick2D, JOGL, LWJGL, and LibGDX.

Color allows us to change the color of the scene, which modifies the color of any shapes being drawn. After the child scenes are drawn, the color context reverts to its previous state.

(defrecord color [colorkey scene]
  IScene
  (draw [s g]
    (let [clr (get-current-color g)]
      (do (set-gui-color g (get-gui-color colorkey))
          (render scene g)
          (set-gui-color g clr))))
  IShape
  (draw-shape [s g] (draw s g)))

Translation defines a relative 2D translation. All children will be affected by the x/y coordinate shift. As with color, once child scenes are rendered, the graphics context is reset to its pre-translated state by applying an inverse translation to the graphics context.

(defrecord translation [x y scene]
  IScene
  (draw [s g]
    (do (translate-xy g (int x) (int y))
        (render scene g)
        (translate-xy g (int (negate x)) (int (negate y)))))
  IShape
  (draw-shape [s g] (draw s g)))

Rotation defines a relative 2D rotation to the scene. It has a single arg, theta, which defines, in radians, the angle of rotation. All child scenes are affected by the rotated context of the scene, and the rotation is inverted after children are rendered.

(defrecord rotation [theta scene]
  IScene
  (draw [s g]
    (do (rotate-xy g theta)
        (render scene g)
        (rotate-xy g (* -1 theta))))
  IShape
  (draw-shape [s g] (draw s g)))

Fade changes the alpha blending of the scene, defined by the argument alpha. Alpha values range between 0.0 (transparent) and 1.0 (opaque).

(defrecord fade [alpha scene]
  IScene
  (draw [s g]
    (let [^AlphaComposite ac (get-composite g)]
       (do (set-composite g (make-alphacomposite alpha))
           (render scene g)
           (set-composite g ac))))
  IShape
  (draw-shape [s g] (draw s g)))

Scales the scene in two dimensions. xscale and yscale are typical linear scaling factors (i.e. numbers that coordinates get multiplied by).

(defrecord scale [xscale yscale scene]
  IScene
  (draw [s g]
    (do (scale-xy g (double xscale) (double yscale))
        (render scene g)
        (scale-xy g (double (/ 1  xscale)) (double (/ 1  yscale)))))
  IShape
  (draw-shape [s g] (draw s g)))

Define a helper function for handling composite scenes, this will come into play shortly.

(defn- sequential-draw
  "Draw all scenes in s sequentially, onto g."
  [s ^Graphics2D g]
  (loop [coll s]
    (if-let [scn (first coll)]
      (do
        (render (first coll) g)
        (recur (rest coll))))))

We make vectors, lists, and sequences look like composite scenes by extending the IScene protocol to them, and using sequential draw for their implementation of draw. This really cleans up the calling code and makes the scenegraphs look cleaner.

(extend-protocol IScene
  clojure.lang.PersistentVector
  (draw [s g] (sequential-draw s g))

  clojure.lang.PersistentList
  (draw [s g] (sequential-draw s g))

  clojure.lang.LazySeq
  (draw [s g] (sequential-draw s g)))

Examples

Now some code. One convention that might throw you for a loop if you’re not familiar with it, is the use of -> before a symbol to indicate the function is a constructor. This is an idiom chosen by the Clojure folks, I believe it had some roots in Lisp communities as well. The reason I mention it, is that you will see things like (->translation 20 20 blah) show up, when we never defined ->translation. When we use defrecord to define records, as of Clojure 1.3, records get some extra goodies to make them even more useful. One of the goodies is a namespace-qualified constructor function, which is the record symbol prefixed by ->. This makes it trivial to import Clojure 1.3 records into other namespaces, or to construct them on the fly. Plus, it’s understood by the Clojure reader, so the expression (->translation 20 20 blah) can be read and evaluated into a translation record, and trivially serialized/de-serialized….I feel that it reinforces the idea that we’re building a structure (the scene graph) out of the records. I adopt the -> prefix for other non-record constructor functions in my code as well, for consistency. Note, this is NOT to be confused with the -> threading macro, which reads (-> arg (fn [arg] (println arg)))

(defn paint-scene
  "Passes the scene's renderer as the drawing function for a
   paintpanel from cljgui.gui, and displays the paintpanel on an empty
   frame."
  ([height width scene]
   (display (empty-frame) (paintpanel height width #(render scene %))))
  ([scene] (paint-scene 500 500 scene)))

(defn simplescene
  "Draws a rudimentary scene across a canvas dimensioned by width and
   height.  The scene has a white background, with a red circle drawn
   in the center, and a black line drawn from the circle radiating out
   about 20 units length."
  [width height]
  (let [lineball
        (->color :white
          [(->rectangle :white 0 0 width height)
           (->translation (halve width) (halve height)
             [(->circle :red -20 -20 20 20)
              (->translation 12 12
                (->rotation (* 3 (/ Math/PI 4))
                  (->line  :black 0 0 0 20) ))])])]
    (paint-scene width height lineball)))

When (simplescene) is evaluated, it produces a new JFrame (window or form) with our simple drawing, as expected:

Note how the scene follows from the description of the scene graph:

The scene is white, containing a composite of a white rectangle, which spans the canvas, which has another scene on top of it. This scene is a translation from the original origin (the top left of the canvas) to the center of the canvas, with a 40 unit radius red circle as a child, and another scene as a child. The other child scene has an additional translation which moves it down and to the right by 12 units evenly relative to the transformed origin, composed with a 135 degree (³⁄₄ PI) rotation, of a 20-unit length black line that “would” have been drawn horizontally from left to right. The result is a red circle with a line sticking out of it.

Next, we’ll build some functions that allow us to draw complicated scenes programmatically, and show how we can easily inline functions that return scenes into our scene graph. We’ll try to draw a spirograph.

(defn ->local-point
  "Create a small circular 'point' of radius = size, relative to an
   origin at (0,0)"
  [color size]
  (->circle color (negate size) (negate size) size size))

(defn ->faded-plot
  "Creates a local-point, colored by color, faded by alpha, and
   translated to an absolute position at (x,y)"
  [color x y alpha]
  (->fade alpha
    (->translation x y
       (->local-point color 20))))

(defn spirograph
  "Creates a scene of n circular points plotted in what appears to be
   a spiraling trajectory.  color determines the points' color,
   stepsize determines how the distance between steps in the
   trajectory function, which either contracts [for small sizes] or
   expands [for larger sizes] the spread of the points.  growthf
   determines how fast the radius of the spiral grows as a function of
   time (if user supplies (fn [t] 1.0) then only a circle is
   rendered).  direction describes whether the spiral appears to
   originate from the edge of the screen, zooming toward the center,
   or vice versa.  plotf is the renderer for each coordinate of the
   spiral, typically faded points."
  [n width & {:keys [color stepsize growthf direction plotf]
              :or {color :red
                   stepsize (/ Math/PI 4)
                   growthf (fn [t] (* 1.10 t))
                   direction :positive
                   plotf ->faded-plot}}]
  (let [halfwidth (halve width)
        get-step (fn [t] (if (= 0 t) 0
                   (/ t stepsize)))
        scale-factor (if (> (growthf n) halfwidth)
                         (/  halfwidth (growthf n))
                         1.0)
        samples (let [s (take n (iterate (fn [t] (+ stepsize t)) 0))] ;weak
                  (if (= direction :positive)
                      s
                      (reverse s)))
        alpha  (fn [t] (- 1 (/ (get-step t) n)))
        radius (fn [t] (growthf (/ t stepsize)))
        coords (fn [xorigin yorigin]
                 (let [stepxy
                       (fn [t]
                         (let [r (radius t)]
                           [(+ xorigin (* r (Math/cos t)))
                            (+ yorigin (* r (Math/sin t)))]))]
                   (map #(conj (stepxy %) %) samples)))
        pointstream (for [[x y t] (coords 0 0)]
                      (plotf color x y (alpha t)))]
    (->translation halfwidth halfwidth
      (->scale scale-factor scale-factor pointstream))))

Notice the return value of spirograph: it’s a scene. We’ve written a function that generates a set of n points internally, converts them to faded plots (which are also scenes) and translates and scales them to the parameters supplied by the user. pointstream is where the magic happens, where we turn our parametrically generated x,y,alpha triples into faded plots using plotf (in this case, the default value is the ->faded-plot function). The end result is a composite scene that should draw n points spiraling either away from or toward the center of the screen, with some cool fading effect applied as a function of time.

Finally, a way to visualize our spirograph and check out different parameters:

(defn demo
  "Renders a spirograph with a user-defined background color, particle count,
   stepsize, growthrate, etc.  This lets us create different spirals and view
   them interactively."
  [& {:keys [width background n stepsize growthrate direction] :or
       {width 500
        background :black
        n 100
        stepsize 0.2
        growthrate 1.1
        direction :negative}}]
  (paint-scene
width width
  [(->rectangle background 0 0 width width)
   (spirograph n width :stepsize stepsize
               :direction direction
               :growthf (fn [t] (* growthrate t)))]))

Notice how we composed the spirograph scene with a simple black background scene. We didn’t put in any background parameters in the spirograph function, because it wasn’t necessary. We just spliced the background into a composite scene and rendered the spirograph on top of it (to get the cool alpha blending effect). I find that the compositional nature of scene graphs really fits well with functional nature of Clojure, and has facilitated a lot of code re-use and flexible definition of scenes.

Here are various versions of the demo:

This was a useful, if lengthy detour, from functional reactive programming. I wanted to introduce the concept of scene graphs, and how I’ve been using them in my Clojure graphics work. I replaced all of my calls in the original functional reactive animation demo to use scenegraphs, and did not want to skip over them. Keep in mind, my scene graph implementation is relatively lacking, and consequently inefficient. Thankfully, most of the rendering I’m doing is at the level where I can be inefficient and let the gross power of the hardware make up for it. I eventually plan to port the underlying Java2D stuff to something more hardware accelerated (probably one of the OpenGL platforms for Java). Too bad Penumbra (a very nice Clojure OpenGL wrapper) fell out of development. It doesn’t quite work with Clojure 1.3, and is no longer being maintained.

Next time: I get back to functional reactive programming and making circles fly about the screen!