TLDR: This post is long

by baggers

OK so it's that time again, write-up time.

Where were we?

So last week I left off with the compiler spitting out good code. This was super cool as it was now possible to write shaders that used spaces.

The first part of the week was bug hunting and fixing. I extended the pull-g function to that you can now pull the code not only from compiled pipelines but also from individual gpu functions.

I looked at some of the recent code I wrote to make the space on gpu feature work and realized it was written by some kind of twisted madman so that got cleaned up a bit. The way it applied changes to the AST was plain wrong.

I added a pass so that if you write something daft like

(in some-space
  (in some-space

Then it will strip the redundant in block.


After that it was time to think about how these should be used. Of course we have in blocks, but there were questions like:

  • What happens if you try to pass a type like position or space (that don't exist at runtime) from one shader stage to another?
  • Can these kind of types be used in gpu-structs?
  • Should stages have an implicit space?
  • If you pass up a position as a uniform, where does it's space come from?

Questions like this have been taking a lot of time to sort out. It's one of those funny things that, when the language doesn't limit you and your goal is 'the best' programming experience, then any of hundreds of crazy solutions are possible so choosing becomes harder.

One possibility was to make space a first class concept in cepl, so all gpu-arrays and such would have a space. That would mean that I could have the terrain vertex data in a gpu-array in world space. e.g.

 (make-gpu-array terrain-data :type 'terrain-vert :space world-space)

and then the vertex shader could technically look like this

 (defun-g terrain-vertex-shader ((vert terrain-vert))
   (values (pos vert)
           (normal vert)
           (uv vert)))

Now! because the vertex shader implicitly takes place in clip space and cepl knows that the vert data is in world-space then it could add the world->clip space transforms for you.

This sounds kinda awesome, and with cepl I can totally make this work... but I decided against it. Why? Well because it bakes a certain use-case into a data-structure, here is a simple example where it breaks down.

I have the data for a bush, I will instance this a thousand times across a landscape, each tree will have a different model->world transform. At this point what is the space associated with the bush data doing? It's not needed yet it's 'attached' to the data.

An hour of wrangling around that idea made it seem like this idea just added complexity so, for now at least, it's out.

A few more ideas ending up in a similar place. Namely:

cepl, in some places, is reaching the limit of how much it can help without becoming an engine.

this is an interesting feeling in itself and one I'm happy to struggle with. You can find many project that didn't know when to stop and pollute their cool clean solution with overreaching ideas that should have been separate libraries.

So after all that I decided the healthiest thing was to leave that for a bit and focus on the cpu side of the space feature.


This turned out to be super easy to get working. I already had a bunch of code done so I just fixed some bugs and suddenly the get-transform function was working.

get-transform takes two spaces and gives you the transform between them. When my shader compiler finds positions moving between two spaces (let's say x & y) it adds a uniform called x-to-y and passes up the result of (get-transform x y).

So suddenly that worked. Because brains are fucking stupid I found it rather anticlimactic and didn't get the buzz you might expect. FUCK YOU BRAIN. I am used to this happening to myself and others so no biggie (seriously folks, if this happens to you it's not weird!).

What may have played into that feeling was some weird nagging feeling that I had something wrong with my concept of how spaces should be organized. I didn't get any info from my brain on what the something was though.. good job brain :D

Fuck it, dive back in

The only thing to do was to go back to the books and look at the gpu-pipeline and matrix transforms again and again.

There is a quote I have seen attributed to Douglas Adams

Writing is easy. You only need to stare at a blank piece of paper until your forehead bleeds

Sounds like a quote that belongs on this site :D It was certainly relevant in this case.

So I stared. And eventually I could see what the problem was.

I have assumed that all spaces have one parent. Turns out I had conflated hierarchical and non-hierarchical relationships

Sounds weird but I can explain.

The whole point of making a space graph rather than a scene graph was to avoid the idea that game entities would be part of the graph, which I believe is a massive code-smell.

I want only spaces to be in the graph, so far so good.

I define my spaces with some transforms relative to a parent space. Seems OK. But is it? I realized I ran into some issues when looking at the eye-space to clip-space relationship.

There isn't a clear parent. Changing the position of the eye (game camera) doesn't transform clip-space in the way moving a table affects the objects on the table. Also defining eye-space as a child of clip space feels weird.

What I had was what I'm calling a non-hierarchical relationship. There is a valid transform between them but it isn't defined in terms of a parent-child relationship. Examples of hierarchical things like arms and hands, where moving the arm moves the hand.

So what I want now is:

  • lots of space-trees, which are hierarchical. They are defined in a parent-child way and are great for character limbs, foliage branches etc.
  • non-hierarchical relationships between the root nodes of those space-trees.

Nothing new under the sun

So is this special? Nope :) It more my journey than something totally new. The first part of the definition from Wikipedia says

A tree node (in the overall tree structure of the scene graph) may have many children but often only a single parent

but later clarifies:

It also happens that in some scene graphs, a node can have a relation to any node including itself, or at least an extension that refers to another node.

OpenSceneGraph has multiple parents...which to me sounds like a bit of a terminology mistake, what does a spatial hierarchy with many parents mean?

Also having graph pointers sounds scary, they would have to be quite strict in what they can do..and if they have strict behavior then surely there can be a better term.

Some other engines avoid the issue somewhat by keeping the scene graph to the hierarchical stuff and let the subject of clip-space and such be a concern of shaders. My brief look a Unity seems to suggest this approach.

Whilst that last one avoids confusion at first it feels like you kind of only defer the issue to another part of the code-base. I would hope we could come up with some analogy in code that extends across these domains. This may not be as easy at first but should be simpler in the end.

Get back to coding

That realization has only happened in the last few hours so I still need to chew on it. Maybe model space is a child of clip-space and this is all just confusion and wank, maybe I'm missing something else.

Whichever way it turns out this is feeling closer to the solution than it was and that's enough to earn it's place in this long ass post.


p.s. I guess one summary for all this is that even when understanding a topic like spaces is fairly easy, designing a pleasing api around it can still be hard.

Last Edited on Sun Jan 10 2016 15:54:45 GMT-0500 (EST)

ferris commented

Hahaha, what a fun read! I hadn't considered any of the runtime-only use cases of the spaces feature, that was pretty interesting on its own. Cool to see some more insight on various types of scene graphs too. Also, I totally get that "oh it just worked" feeling all the time - it's bittersweet but still pretty rad :D

on Sun Jan 10 2016 16:28:31 GMT-0500 (EST)

baggers commented

Cheers dude! :)

on Sun Jan 10 2016 18:02:48 GMT-0500 (EST)

Zach Harvest commented

I wish I could say something educated about this. However I cannot. Nice write up tho! :P

on Mon Jan 11 2016 12:02:31 GMT-0500 (EST)