Lost in space

The following blog entry is a bunch of my own thoughts regarding a 3D engine I’m writting.

Foreword

It’s been a while now I’ve been trying to represent a 3D scene the proper way. I’ve found dozens of solutions, but still none of them is likely to be as proper nor accurate as I’d like to. The problem is actually quite simple: a 3D scene is composed of several objects. You can encounter two types of objects:

• value-semantic object
• entity-semantic object

A value object is an object you can think of by its value. For instance, money, color, position, a file configuration, and so on.
An entity object is an object you cannot think of by it its value. It’s a whole unique object. The simplest example is you. A human. Even if we find a way to make perfect clones, two perfect similar humans remain different. We also capture this concept in programming.

Now, what are 3D scene’s objects? Let’s select of few you could encounter in almost all engines:

• a vertex
• a mesh, which is a bunch of vertices with primitives construction information
• a shader
• a material, which holds a sharable shader
• a model, which is a mesh associated to a material
• a light
• entities, that bind any value to space information (position, orientation and scale, for instance)

As you might guess, some objects in the above non-comprehensive list of scene objects are value-semantics, others are entity-semantic. A vertex is obviously a value. A mesh could be both depending on how you design your scene. In my way, it’s an entity. So is a shader, a material, a model and a light. Funny things, scene entities are values since they link an entity-semantics object to space information, which is value.

With all that said, how would you link objects between each other?

The simple way: identifiers

My first thought was a simple one: let’s introduce a higher-order type called ID:

newtype ID a = ID Int deriving (Eq,Ord,Show)

It’s a phantom type in order to know what we are refering to. ID :: Mesh refers to a Mesh. So, we can use our new identifiers type to add indirection in our types:

data Mesh = Mesh {- … -}
data Material = Material {- … -}
data Model = Model (ID Mesh) (ID Material)

That requires us to be able to generate names. I came up with a simple solution to do so:

class Identify a m where
  ident :: a -> m (ID a)
  reify :: ID a -> m a
  imod  :: ID a -> (a -> a) -> m ()

This typeclass is a bit like MonadState on steroids since it adds indirection. Then, given your own monad based on SatetT, you could do something like:

instance Identify Mesh MySceneMonad where
  ident = {- … -}
  reify = {- … -}
  imod  = {- … -}

instance Identify Material MySceneMonad where
  {- … -}

instance Identify Model MySceneMonad where
  {- … -}

foo :: MySceneMonad (ID Model)
foo = do
  msh <- ident $ Mesh {- … -}
  mat <- ident $ Material {- … -}
  ident $ Model msh mat

However, this suffers from some issues. First, the implementation of the ID supply is in your hand. If you do it wrong, everything will
just go… wrong. Furthermore, IDs are escapable. What would happen to if you escape an identifier and reify in another monad?

getID :: MySceneMonad (ID Mesh)
getID = ident $ Mesh {- … -}

foo = do
    mshid <- runMySceneMonad getID defaultState
    runMySceneMonad $ reify mshid -- oops!

The less simple way: AST

An AST would be great to represent our scene. We could find at the top objects which have the less dependencies, and at the bottom the
more dependent objects. Let’s try to write down the AST for a few objects only:

data E a
  = V a
  | Let (E a) (Scope () E a)
  | Lam (Scope () E a)
  | E a :@ E a
  | LitShader Shader
  | LitMesh Mesh
  | LitMaterial Material
  | LitModel Model
    deriving (Eq,Show)

Shader, Mesh, Material and Model would only care about core features. So you don’t find a Shader in the implementation of a Material
since the link is done through the AST. But in our case, how? We could use the Let constructor, let’s try out:

Let (LitShader shaderDef) (LitMaterial materialDef)

As you can see, that is stupid. The normal form of that expression discards the shader and turns into LitMaterial materialDef. I see here a
solution: we need a special branch in the AST to represent link. Let’s add that into our E expression type only for shaders:

WithShader :: E a -> E a -> E a

So we can do:

WithShader (LitShader shaderDef) (LitMaterial materialDef)

Notice we could even write:

WithShader (V "myShaderDef") {- any expression using that shader -}

Now I see another issue: the first expression is untyped. We could write this, it’d be perfectly valid:

WithShader (LitMaterial materialDef) (V "oshit")

And even V "myShaderDef is untyped. So we’re hitting ourselves in the foot with such an AST. We could, though, think it’s perfectly legit
and write a typechecker that would validate an AST for us, like:

typecheck :: E a -> Either ASTError (E a)

The harder way: AST via GADT

We don’t want typecheck, it’ll complicate the way we use an AST. So let’s turn E into a GADT.

data E :: * -> * -> * where
  V :: a -> E l a
  Let :: E l a -> Scope () (E l) a -> E q a
  Lam :: Scope () (E l) a -> E q a
  Apply :: E l a -> E q b -> E l a
  LitShader :: Shader -> E Shader a
  LitMesh :: Mesh -> E Mesh a
  LitMaterial :: Material -> E Material a
  LitModel :: Model -> E Model a

But now, go and try to make that a monad. You won’t be able to, since it’s not. Even less an applicative functor, so not foldable nor
traversable. I think that solution is the more complicated, the more obfuscated, and the more… solution, in the end!

The hope solution: typeclass

Typeclasses could save us all, since the interpreters could be the typeclass implementation. Let’s turn the GADT into a typeclass:

class AST expr where
  var :: a -> expr l a
  let_ :: expr l a -> a -> expr q a -> expr q a
  -- and so on and so forth

This is nice, I like that way of doing, even more than data, because we can let the compiler choose the best type for us (or force it).
An AST would be something like this:

ast :: (AST e) => e l a

But unfortunately, we have the same problem as GADT: writing a proper implementation will be… writing the same madness GADT…

So?

So… I still don’t know. I’m looking for alternatives. Up to know, I believe the ID solution is my shortest way to get things done. I’m open
to better solutions, because it might have plenty.