16 files changed, 891 insertions, 0 deletions

diff --git a/src/scene/camera.c b/src/scene/camera.c
new file mode 100644
index 0000000..fcfc496
--- /dev/null
+++ b/src/scene/camera.c
@@ -0,0 +1,18 @@
+#include <gfx/scene.h>
+
+#include "memory.h"
+
+#include <assert.h>
+#include <math/camera.h>
+
+Camera* gfx_make_camera(void) {
+  Camera* camera = mem_alloc_camera();
+  return camera;
+}
+
+void gfx_destroy_camera(Camera** camera) {
+  assert(camera);
+  if (*camera) {
+    mem_free_camera(camera);
+  }
+}
diff --git a/src/scene/light.c b/src/scene/light.c
new file mode 100644
index 0000000..4233330
--- /dev/null
+++ b/src/scene/light.c
@@ -0,0 +1,39 @@
+#include "light_impl.h"
+
+#include "memory.h"
+
+#include <cassert.h>
+#include <error.h>
+
+static void make_environment_light(
+    Light* light, const EnvironmentLightDesc* desc) {
+  assert(light);
+  assert(desc);
+  light->type                        = EnvironmentLightType;
+  light->environment.environment_map = desc->environment_map;
+}
+
+Light* gfx_make_light(const LightDesc* desc) {
+  assert(desc);
+
+  Light* light = mem_alloc_light();
+
+  switch (desc->type) {
+  case EnvironmentLightType:
+    make_environment_light(light, &desc->light.environment);
+    break;
+  default:
+    log_error("Unhandled light type");
+    gfx_destroy_light(&light);
+    return 0;
+  }
+
+  return light;
+}
+
+void gfx_destroy_light(Light** light) {
+  assert(light);
+  if (*light) {
+    mem_free_light(light);
+  }
+}
diff --git a/src/scene/light_impl.h b/src/scene/light_impl.h
new file mode 100644
index 0000000..3191a50
--- /dev/null
+++ b/src/scene/light_impl.h
@@ -0,0 +1,20 @@
+#pragma once
+
+#include <gfx/scene.h>
+
+/// An environment light.
+typedef struct EnvironmentLight {
+  const Texture* environment_map;
+  const Texture* irradiance_map;              // Renderer implementation.
+  const Texture* prefiltered_environment_map; // Renderer implementation.
+  int max_reflection_lod; // Mandatory when prefiltered_environment_map is
+  // given.
+} EnvironmentLight;
+
+/// A scene light.
+typedef struct Light {
+  LightType type;
+  union {
+    EnvironmentLight environment;
+  };
+} Light;
diff --git a/src/scene/material.c b/src/scene/material.c
new file mode 100644
index 0000000..9fe6c1b
--- /dev/null
+++ b/src/scene/material.c
@@ -0,0 +1,24 @@
+#include "material_impl.h"
+
+#include "memory.h"
+
+static void material_make(Material* material, const MaterialDesc* desc) {
+  assert(material);
+  assert(desc);
+  assert(desc->num_uniforms < GFX_MAX_UNIFORMS_PER_MATERIAL);
+  material->alpha_mode   = desc->alpha_mode;
+  material->alpha_cutoff = desc->alpha_cutoff;
+  material->num_uniforms = (int8_t)desc->num_uniforms;
+  for (int i = 0; i < desc->num_uniforms; ++i) {
+    material->uniforms[i] = desc->uniforms[i];
+  }
+}
+
+Material* gfx_make_material(const MaterialDesc* desc) {
+  assert(desc);
+  Material* material = mem_alloc_material();
+  material_make(material, desc);
+  return material;
+}
+
+void gfx_destroy_material(Material** material) { mem_free_material(material); }
diff --git a/src/scene/material_impl.h b/src/scene/material_impl.h
new file mode 100644
index 0000000..488ffc7
--- /dev/null
+++ b/src/scene/material_impl.h
@@ -0,0 +1,13 @@
+#pragma once
+
+#include <gfx/scene.h>
+#include <gfx/sizes.h>
+
+typedef struct ShaderProgram ShaderProgram;
+
+typedef struct Material {
+  AlphaMode     alpha_mode;
+  float         alpha_cutoff;
+  int8_t        num_uniforms;
+  ShaderUniform uniforms[GFX_MAX_UNIFORMS_PER_MATERIAL];
+} Material;
diff --git a/src/scene/mesh.c b/src/scene/mesh.c
new file mode 100644
index 0000000..770c3fb
--- /dev/null
+++ b/src/scene/mesh.c
@@ -0,0 +1,26 @@
+#include "mesh_impl.h"
+
+#include <gfx/scene.h>
+
+#include "memory.h"
+
+#include <cassert.h>
+
+static void mesh_make(Mesh* mesh, const MeshDesc* desc) {
+  assert(mesh);
+  assert(desc);
+  assert(desc->geometry);
+  assert(desc->material);
+  assert(desc->shader);
+  mesh->geometry = desc->geometry;
+  mesh->material = desc->material;
+  mesh->shader   = desc->shader;
+}
+
+Mesh* gfx_make_mesh(const MeshDesc* desc) {
+  Mesh* mesh = mem_alloc_mesh();
+  mesh_make(mesh, desc);
+  return mesh;
+}
+
+void gfx_destroy_mesh(Mesh** mesh) { mem_free_mesh(mesh); }
diff --git a/src/scene/mesh_impl.h b/src/scene/mesh_impl.h
new file mode 100644
index 0000000..c7e2211
--- /dev/null
+++ b/src/scene/mesh_impl.h
@@ -0,0 +1,11 @@
+#pragma once
+
+typedef struct Geometry      Geometry;
+typedef struct Material      Material;
+typedef struct ShaderProgram ShaderProgram;
+
+typedef struct Mesh {
+  const Geometry* geometry;
+  const Material* material;
+  ShaderProgram*  shader; // TODO: Move this back to Material?
+} Mesh;
diff --git a/src/scene/model.c b/src/scene/model.c
new file mode 100644
index 0000000..1bd0112
--- /dev/null
+++ b/src/scene/model.c
@@ -0,0 +1,45 @@
+#include "model_impl.h"
+
+#include <gfx/scene.h>
+
+#include "memory.h"
+
+#include <assert.h>
+
+Model* gfx_make_model(const SceneNode* root) {
+  assert(root);
+
+  Model* model = mem_alloc_model();
+  model->root  = mem_get_node_index(root);
+  return model;
+}
+
+void gfx_del_model(Model** model) {
+  assert(model);
+
+  if (*model) {
+    SceneNode* root = mem_get_node((*model)->root);
+    gfx_destroy_node(&root);
+    *model = 0;
+  }
+}
+
+Anima* gfx_get_model_anima(Model* model) {
+  assert(model);
+
+  SceneNode* root = mem_get_node(model->root);
+  if (gfx_get_node_type(root) == AnimaNode) {
+    return gfx_get_node_anima_mut(root);
+  } else {
+    return 0;
+  }
+}
+
+const SceneNode* gfx_get_model_root(const Model* model) {
+  assert(model);
+  return mem_get_node(model->root);
+}
+
+SceneNode* gfx_get_model_root_mut(Model* model) {
+  return (SceneNode*)gfx_get_model_root(model);
+}
diff --git a/src/scene/model_impl.h b/src/scene/model_impl.h
new file mode 100644
index 0000000..72cd0ab
--- /dev/null
+++ b/src/scene/model_impl.h
@@ -0,0 +1,16 @@
+#pragma once
+
+#include <gfx/scene.h>
+
+#include "memory.h"
+
+/// Model.
+typedef struct Model {
+  node_idx root;
+} Model;
+
+/// Create a new model.
+Model* gfx_make_model(const SceneNode* root);
+
+/// Destroy the model.
+void gfx_del_model(Model**);
diff --git a/src/scene/node.c b/src/scene/node.c
new file mode 100644
index 0000000..0004d27
--- /dev/null
+++ b/src/scene/node.c
@@ -0,0 +1,352 @@
+#include "node_impl.h"
+
+#include "animation_impl.h"
+#include "memory.h"
+#include "object_impl.h"
+#include "render/llr_impl.h"
+#include "scene_graph.h"
+
+#include "gfx_assert.h"
+
+#include <gfx/scene.h>
+
+#include <cstring.h>
+#include <log/log.h>
+
+static void scene_node_make(SceneNode* node) {
+  assert(node);
+  node->type      = LogicalNode;
+  node->transform = mat4_id();
+}
+
+SceneNode* gfx_make_node(void) {
+  SceneNode* node = mem_alloc_node();
+  scene_node_make(node);
+  return node;
+}
+
+SceneNode* gfx_make_anima_node(Anima* anima) {
+  assert(anima);
+  SceneNode* node = gfx_make_node();
+  node->type      = AnimaNode;
+  node->anima     = mem_get_anima_index(anima);
+  return node;
+}
+
+SceneNode* gfx_make_camera_node(Camera* camera) {
+  assert(camera);
+  SceneNode* node = gfx_make_node();
+  node->type      = CameraNode;
+  node->camera    = mem_get_camera_index(camera);
+  return node;
+}
+
+SceneNode* gfx_make_light_node(Light* light) {
+  assert(light);
+  SceneNode* node = gfx_make_node();
+  node->type      = LightNode;
+  node->light     = mem_get_light_index(light);
+  return node;
+}
+
+SceneNode* gfx_make_model_node(Model* model) {
+  assert(model);
+  SceneNode* node = gfx_make_node();
+  node->type      = ModelNode;
+  node->model     = mem_get_model_index(model);
+  return node;
+}
+
+SceneNode* gfx_make_object_node(SceneObject* object) {
+  assert(object);
+  SceneNode* node = gfx_make_node();
+  node->type      = ObjectNode;
+  node->object    = mem_get_object_index(object);
+  return node;
+}
+
+/// Frees the node's resource.
+static void free_node_resource(SceneNode* node) {
+  assert(node);
+
+  switch (node->type) {
+  case AnimaNode: {
+    Anima* anima = mem_get_anima(node->anima);
+    gfx_destroy_anima(&anima);
+    return;
+  }
+  case CameraNode: {
+    Camera* camera = mem_get_camera(node->camera);
+    gfx_destroy_camera(&camera);
+    return;
+  }
+  case LightNode: {
+    Light* light = mem_get_light(node->light);
+    gfx_destroy_light(&light);
+    return;
+  }
+  case ModelNode: {
+    return; // Model data is owned by the asset cache.
+  }
+  case ObjectNode: {
+    SceneObject* object = mem_get_object(node->object);
+    gfx_destroy_object(&object);
+    return;
+  }
+  case LogicalNode: {
+    return; // Logical nodes have no resource.
+  }
+  }
+  FAIL("unhandled node type");
+}
+
+static void destroy_node_rec(SceneNode* node) {
+  assert(node);
+
+  // First child.
+  if (node->child.val) {
+    destroy_node_rec(mem_get_node(node->child));
+  }
+
+  // Right sibling.
+  if (node->next.val) {
+    destroy_node_rec(mem_get_node(node->next));
+  }
+
+  free_node_resource(node);
+  mem_free_node(&node);
+}
+
+void gfx_destroy_node(SceneNode** node) {
+  assert(node);
+  if (*node) {
+    // Since the node and the whole hierarchy under it gets destroyed, there is
+    // no need to individually detach every node from its hierarchy. We can
+    // simply detach the given node and then destroy it and its sub-hierarchy.
+    TREE_REMOVE(*node);
+    destroy_node_rec(*node);
+    *node = 0;
+  }
+}
+
+// TODO: Think more about ownership of nodes and resources. Should this function
+//  even exist?
+void gfx_del_node(node_idx index) {
+  assert(index.val);
+  SceneNode* node = mem_get_node(index);
+  assert(node);
+  // TODO: Should destroy children recursively?
+  TREE_REMOVE(node);
+  mem_free_node(&node);
+}
+
+NodeType gfx_get_node_type(const SceneNode* node) {
+  assert(node);
+  return node->type;
+}
+
+#define NODE_GET(node, field, expected_type) \
+  {                                          \
+    assert(node);                            \
+    assert(node->type == expected_type);     \
+    return mem_get_##field(node->field);     \
+  }
+
+const Anima* gfx_get_node_anima(const SceneNode* node) {
+  NODE_GET(node, anima, AnimaNode);
+}
+
+Anima* gfx_get_node_anima_mut(SceneNode* node) {
+  NODE_GET(node, anima, AnimaNode);
+}
+
+const Camera* gfx_get_node_camera(const SceneNode* node) {
+  NODE_GET(node, camera, CameraNode);
+}
+
+Camera* gfx_get_node_camera_mut(SceneNode* node) {
+  NODE_GET(node, camera, CameraNode);
+}
+
+const Light* gfx_get_node_light(const SceneNode* node) {
+  NODE_GET(node, light, LightNode);
+}
+
+Light* gfx_get_node_light_mut(SceneNode* node) {
+  NODE_GET(node, light, LightNode);
+}
+
+const Model* gfx_get_node_model(const SceneNode* node) {
+  NODE_GET(node, model, ModelNode);
+}
+
+Model* gfx_get_node_model_mut(SceneNode* node) {
+  NODE_GET(node, model, ModelNode);
+}
+
+const SceneObject* gfx_get_node_object(const SceneNode* node) {
+  NODE_GET(node, object, ObjectNode);
+}
+
+SceneObject* gfx_get_node_object_mut(SceneNode* node) {
+  NODE_GET(node, object, ObjectNode);
+}
+
+const SceneNode* gfx_get_node_parent(const SceneNode* node) {
+  assert(node);
+  return mem_get_node(node->parent);
+}
+
+SceneNode* gfx_get_node_parent_mut(SceneNode* node) {
+  assert(node);
+  return mem_get_node(node->parent);
+}
+
+const SceneNode* gfx_get_node_child(const SceneNode* node) {
+  assert(node);
+  if (node->child.val) {
+    return mem_get_node(node->child);
+  } else {
+    return 0;
+  }
+}
+
+SceneNode* gfx_get_node_child_mut(SceneNode* node) {
+  return (SceneNode*)gfx_get_node_child(node);
+}
+
+const SceneNode* gfx_get_node_sibling(const SceneNode* node) {
+  assert(node);
+  if (node->next.val) {
+    return mem_get_node(node->next);
+  } else {
+    return 0;
+  }
+}
+
+SceneNode* gfx_get_node_sibling_mut(SceneNode* node) {
+  return (SceneNode*)gfx_get_node_sibling(node);
+}
+
+mat4 gfx_get_node_transform(const SceneNode* node) {
+  assert(node);
+  return node->transform;
+}
+
+mat4 gfx_get_node_global_transform(const SceneNode* node) {
+  assert(node);
+  mat4     transform    = node->transform;
+  node_idx parent_index = node->parent;
+  while (parent_index.val != 0) {
+    const SceneNode* parent = mem_get_node(parent_index);
+    transform               = mat4_mul(parent->transform, transform);
+    parent_index            = parent->parent;
+  }
+  return transform;
+}
+
+void gfx_set_node_parent(SceneNode* child, SceneNode* parent_node) {
+  assert(child);
+  // Parent can be null.
+  SET_PARENT(child, parent_node);
+}
+
+void gfx_set_node_transform(SceneNode* node, const mat4* transform) {
+  assert(node);
+  assert(transform);
+  node->transform = *transform;
+}
+
+void gfx_set_node_position(SceneNode* node, const vec3* position) {
+  assert(node);
+  assert(position);
+  mat4_set_v3(&node->transform, *position);
+}
+
+void gfx_set_node_rotation(SceneNode* node, const quat* rotation) {
+  assert(node);
+  assert(rotation);
+  mat4_set_3x3(&node->transform, mat4_from_quat(*rotation));
+}
+
+void gfx_set_node_rotation_mat(SceneNode* node, const mat4* rotation) {
+  assert(node);
+  assert(rotation);
+  mat4_set_3x3(&node->transform, *rotation);
+}
+
+static const char* get_node_type_str(NodeType type) {
+  switch (type) {
+  case LogicalNode:
+    return "LogicalNode";
+  case AnimaNode:
+    return "AnimaNode";
+  case CameraNode:
+    return "CameraNode";
+  case LightNode:
+    return "LightNode";
+  case ModelNode:
+    return "ModelNode";
+  case ObjectNode:
+    return "ObjectNode";
+  }
+  FAIL("Unhandled node type");
+  return "";
+}
+
+static void log_node_hierarchy_rec(const SceneNode* node, const sstring* pad) {
+  assert(node);
+  assert(pad);
+
+  LOGI(
+      "%s%s (%u)", sstring_cstr(pad), get_node_type_str(node->type),
+      mem_get_node_index(node).val);
+
+  // Log the children.
+  if (node->child.val) {
+    const sstring new_pad = sstring_concat_cstr(*pad, "  ");
+    log_node_hierarchy_rec(mem_get_node(node->child), &new_pad);
+  }
+
+  // Then log the siblings.
+  if (node->next.val) {
+    log_node_hierarchy_rec(mem_get_node(node->next), pad);
+  }
+}
+
+void gfx_log_node_hierarchy(const SceneNode* node) {
+  const sstring pad = sstring_make("");
+  log_node_hierarchy_rec(node, &pad);
+}
+
+static SceneNode* clone_scene_rec(const SceneNode* node) {
+  assert(node);
+
+  SceneNode* copy = mem_alloc_node();
+  *copy           = *node; // Shallow clone of the node's resource.
+
+  if (node->child.val) {
+    SceneNode* child      = mem_get_node(node->child);
+    SceneNode* child_copy = clone_scene_rec(child);
+    copy->child           = mem_get_node_index(child_copy);
+    child_copy->parent    = mem_get_node_index(copy);
+  }
+
+  if (node->next.val) {
+    SceneNode* next      = mem_get_node(node->next);
+    SceneNode* next_copy = clone_scene_rec(next);
+    copy->next           = mem_get_node_index(next_copy);
+    next_copy->prev      = mem_get_node_index(copy);
+  }
+
+  return copy;
+}
+
+SceneNode* gfx_clone_scene_shallow(const SceneNode* node) {
+  assert(node);
+  // Must be a root node; not allowed to have siblings.
+  assert(!node->prev.val);
+  assert(!node->next.val);
+
+  return clone_scene_rec(node);
+}
diff --git a/src/scene/node_impl.h b/src/scene/node_impl.h
new file mode 100644
index 0000000..9e65588
--- /dev/null
+++ b/src/scene/node_impl.h
@@ -0,0 +1,40 @@
+#pragma once
+
+#include <gfx/scene.h>
+
+#include "../types.h"
+
+#include <math/camera.h>
+#include <math/mat4.h>
+
+/// Scene node.
+///
+/// The SceneNode owns its cameras, objects, lights and child nodes. These
+/// together form a strict tree hierarchy and not a more general DAG.
+typedef struct SceneNode {
+  NodeType type;
+  union {
+    anima_idx  anima;
+    camera_idx camera;
+    light_idx  light;
+    model_idx  model;
+    object_idx object;
+  };
+  mat4     transform; // Transformation for this node and its children.
+  node_idx parent;    // Parent SceneNode.
+  node_idx child;     // First child SceneNode.
+  node_idx next;      // Next sibling SceneNode.
+  node_idx prev;      // Previous sibling SceneNode.
+} SceneNode;
+
+/// Recursively destroy a node given its index but without destroying the node
+/// resources.
+///
+/// The node and its children are removed from the scene graph.
+///
+/// This function is for the library's internal use only.
+void gfx_del_node(node_idx);
+
+/// Return a shallow clone of the scene rooted at the given node.
+/// The given node must have no siblings (must be a root node).
+SceneNode* gfx_clone_scene_shallow(const SceneNode*);
diff --git a/src/scene/object.c b/src/scene/object.c
new file mode 100644
index 0000000..ac86b39
--- /dev/null
+++ b/src/scene/object.c
@@ -0,0 +1,80 @@
+#include "object_impl.h"
+
+#include <gfx/core.h>
+
+#include "memory.h"
+#include "render/llr_impl.h"
+#include "scene/mesh_impl.h"
+#include "scene/node_impl.h"
+
+#include <assert.h>
+
+static aabb3 calc_object_aabb(const SceneObject* object) {
+  assert(object);
+
+  bool  first = true;
+  aabb3 box;
+
+  mesh_link_idx ml = object->mesh_link;
+  while (ml.val) {
+    const MeshLink* mesh_link = mem_get_mesh_link(ml);
+    const mesh_idx  mi        = mesh_link->mesh;
+    if (mi.val) {
+      const Mesh* mesh     = mem_get_mesh(mi);
+      const aabb3 mesh_box = gfx_get_geometry_aabb(mesh->geometry);
+      if (first) {
+        box   = mesh_box;
+        first = false;
+      } else {
+        box = aabb3_sum(box, mesh_box);
+      }
+    }
+    ml = mesh_link->next;
+  }
+
+  return box;
+}
+
+static void add_object_mesh(SceneObject* object, Mesh* mesh) {
+  assert(object);
+  assert(mesh);
+
+  MeshLink* link    = mem_alloc_mesh_link();
+  link->mesh        = mem_get_mesh_index(mesh);
+  link->next        = object->mesh_link;
+  object->mesh_link = mem_get_mesh_link_index(link);
+}
+
+SceneObject* gfx_make_object(const ObjectDesc* desc) {
+  assert(desc);
+
+  SceneObject* object = mem_alloc_object();
+  for (size_t i = 0; i < desc->num_meshes; ++i) {
+    add_object_mesh(object, desc->meshes[i]);
+  }
+  object->box = calc_object_aabb(object);
+  return object;
+}
+
+void gfx_destroy_object(SceneObject** object) {
+  assert(object);
+  if (*object) {
+    mem_free_object(object);
+  }
+}
+
+void gfx_set_object_skeleton(SceneObject* object, const Skeleton* skeleton) {
+  assert(object);
+  assert(skeleton);
+  object->skeleton = mem_get_skeleton_index(skeleton);
+}
+
+const Skeleton* gfx_get_object_skeleton(const SceneObject* object) {
+  assert(object);
+  return (object->skeleton.val == 0) ? 0 : mem_get_skeleton(object->skeleton);
+}
+
+aabb3 gfx_get_object_aabb(const SceneObject* object) {
+  assert(object);
+  return object->box;
+}
diff --git a/src/scene/object_impl.h b/src/scene/object_impl.h
new file mode 100644
index 0000000..345d615
--- /dev/null
+++ b/src/scene/object_impl.h
@@ -0,0 +1,23 @@
+#pragma once
+
+#include <gfx/scene.h>
+
+#include "../types.h"
+
+typedef struct MeshLink {
+  mesh_idx      mesh;
+  mesh_link_idx next; // Next MeshLink in the list.
+} MeshLink;
+
+/// Scene object.
+///
+/// A SceneObject does not own its Meshes, and they are instead shared for
+/// re-use. The SceneObject consequently embeds a list of MeshLinks as opposed
+/// to a list of Meshes. The MeshLinks define a list of Meshes, which can be
+/// different for each SceneObject. Each SceneObject may then have a unique list
+/// of Meshes, and the Meshes are re-used.
+typedef struct SceneObject {
+  mesh_link_idx mesh_link; /// First MeshLink in the list.
+  skeleton_idx  skeleton;  /// 0 for static objects.
+  aabb3         box;
+} SceneObject;
diff --git a/src/scene/scene.c b/src/scene/scene.c
new file mode 100644
index 0000000..52ddb58
--- /dev/null
+++ b/src/scene/scene.c
@@ -0,0 +1,31 @@
+#include "scene_impl.h"
+
+#include "memory.h"
+#include "node_impl.h"
+
+#include <assert.h>
+
+Scene* gfx_make_scene(void) {
+  Scene* scene = mem_alloc_scene();
+  scene->root  = mem_get_node_index(gfx_make_node());
+  return scene;
+}
+
+void gfx_destroy_scene(Scene** scene) {
+  assert(scene);
+  if (*scene) {
+    SceneNode* node = mem_get_node((*scene)->root);
+    gfx_destroy_node(&node);
+    mem_free_scene(scene);
+  }
+}
+
+const SceneNode* gfx_get_scene_root(const Scene* scene) {
+  assert(scene);
+  return mem_get_node(scene->root);
+}
+
+SceneNode* gfx_get_scene_root_mut(Scene* scene) {
+  assert(scene);
+  return (SceneNode*)gfx_get_scene_root(scene);
+}
diff --git a/src/scene/scene_graph.h b/src/scene/scene_graph.h
new file mode 100644
index 0000000..36c3a98
--- /dev/null
+++ b/src/scene/scene_graph.h
@@ -0,0 +1,144 @@
+/// Functions for list manipulation.
+#pragma once
+
+#include "memory.h"
+
+// NOTE: SceneMemory guarantees that index 0 can be regarded as an invalid
+// index.
+
+#define MEM_GET(INDEX)                  \
+  _Generic(                             \
+      (INDEX),                          \
+      camera_idx: mem_get_camera,       \
+      material_idx: mem_get_material,   \
+      mesh_idx: mem_get_mesh,           \
+      mesh_link_idx: mem_get_mesh_link, \
+      node_idx: mem_get_node,           \
+      object_idx: mem_get_object,       \
+      scene_idx: mem_get_scene)(INDEX)
+
+#define MEM_GET_INDEX(ITEM)                \
+  _Generic(                                \
+      (ITEM),                              \
+      Camera *: mem_get_camera_index,      \
+      Material *: mem_get_material_index,  \
+      Mesh *: mem_get_mesh_index,          \
+      MeshLink *: mem_get_mesh_link_index, \
+      SceneNode *: mem_get_node_index,     \
+      SceneObject *: mem_get_object_index, \
+      Scene *: mem_get_scene_index)(ITEM)
+
+/// Assert the list node invariant.
+///
+/// - A node does not point to itself.
+#if NDEBUG
+#define ASSERT_LIST_NODE_INVARIANT(ITEM)
+#else
+#define ASSERT_LIST_NODE_INVARIANT(ITEM)              \
+  {                                                   \
+    const gfx_idx item_idx = MEM_GET_INDEX(ITEM).val; \
+    assert((ITEM)->prev.val != item_idx);             \
+    assert((ITEM)->next.val != item_idx);             \
+  }
+#endif
+
+/// Assert the tree node invariant.
+///
+/// - A node does not point to itself.
+/// - The node's left and right siblings cannot be equal, unless both are 0.
+/// - The node's left/right sibling cannot be its child, unless both are 0.
+/// - The node's parent cannot be the node's child or sibling, unless it's 0.
+/// - If the node has a parent and the node is the leftmost sibling, then the
+///   parent's child is the node.
+#define ASSERT_TREE_NODE_INVARIANT(ITEM)                            \
+  {                                                                 \
+    const gfx_idx item_idx = MEM_GET_INDEX(ITEM).val;               \
+    assert((ITEM)->prev.val != item_idx);                           \
+    assert((ITEM)->next.val != item_idx);                           \
+    if ((ITEM)->prev.val) {                                         \
+      assert((ITEM)->prev.val != (ITEM)->next.val);                 \
+    }                                                               \
+    if ((ITEM)->child.val) {                                        \
+      assert((ITEM)->child.val != (ITEM)->prev.val);                \
+      assert((ITEM)->child.val != (ITEM)->next.val);                \
+    }                                                               \
+    assert((ITEM)->parent.val != item_idx);                         \
+    if ((ITEM)->parent.val && !(ITEM)->prev.val) {                  \
+      assert((ITEM)->parent.val != (ITEM)->prev.val);               \
+      assert((ITEM)->parent.val != (ITEM)->next.val);               \
+      const __typeof__(ITEM) item_parent = MEM_GET((ITEM)->parent); \
+      assert(item_parent->child.val == item_idx);                   \
+    }                                                               \
+  }
+
+/// Prepend an item to a list.
+/// Modify HEAD_INDEX to equal the index of the new head.
+#define LIST_PREPEND(HEAD_INDEX, ITEM)               \
+  (ITEM)->next = HEAD_INDEX;                         \
+  if (HEAD_INDEX.val) {                              \
+    __typeof__(ITEM) old_head = MEM_GET(HEAD_INDEX); \
+    old_head->prev            = MEM_GET_INDEX(ITEM); \
+  }                                                  \
+  HEAD_INDEX = MEM_GET_INDEX(ITEM);                  \
+  ASSERT_LIST_NODE_INVARIANT(ITEM);
+
+/// Disconnect an item from its siblings.
+#define LIST_REMOVE(ITEM)                                  \
+  if ((ITEM)->prev.val) {                                  \
+    __typeof__(ITEM) prev_sibling = MEM_GET((ITEM)->prev); \
+    prev_sibling->next            = (ITEM)->next;          \
+  }                                                        \
+  if ((ITEM)->next.val) {                                  \
+    __typeof__(ITEM) next_sibling = MEM_GET((ITEM)->next); \
+    next_sibling->prev            = (ITEM)->prev;          \
+  }                                                        \
+  (ITEM)->prev.val = 0;                                    \
+  (ITEM)->next.val = 0;                                    \
+  ASSERT_LIST_NODE_INVARIANT(ITEM);
+
+/// Set the child's parent.
+///
+/// The hierarchy is a strict tree hierarchy and a parent node points to its
+/// first/leftmost child only. To add a new child, the new child becomes the
+/// leftmost node in the list of siblings, the one that the parent then points
+/// to.
+///
+/// The child is also completely disconnected from its previous hierarchy. This
+/// is because siblings in a hierarchy must all point to the same parent.
+#define SET_PARENT(CHILD, PARENT)                                         \
+  assert(CHILD);                                                          \
+  assert(CHILD != PARENT);                                                \
+  ASSERT_TREE_NODE_INVARIANT(CHILD);                                      \
+  ASSERT_TREE_NODE_INVARIANT(PARENT);                                     \
+  TREE_REMOVE(CHILD); /* Disconnect CHILD from its previous hierarchy. */ \
+  if (PARENT) {                                                           \
+    LIST_PREPEND((PARENT)->child, CHILD);                                 \
+    (CHILD)->parent = MEM_GET_INDEX(PARENT);                              \
+  } else {                                                                \
+    (CHILD)->parent.val = 0;                                              \
+  }                                                                       \
+  ASSERT_TREE_NODE_INVARIANT(CHILD);                                      \
+  if (PARENT) {                                                           \
+    ASSERT_TREE_NODE_INVARIANT(PARENT);                                   \
+  }
+
+/// Remove an item from its hierarchy.
+///
+/// The item is disconnected from its parents and siblings. The hierarchy rooted
+/// under the item remains intact.
+#define TREE_REMOVE(ITEM)                                                     \
+  assert(ITEM);                                                               \
+  if ((ITEM)->parent.val) {                                                   \
+    /* The parent points only to its first/leftmost child. If this item is */ \
+    /* the leftmost sibling, then we need to rewire the parent to point to */ \
+    /* the next sibling to keep the parent connected to its children. */      \
+    __typeof__(ITEM)       parent       = MEM_GET((ITEM)->parent);            \
+    const __typeof__(ITEM) parent_child = MEM_GET(parent->child);             \
+    if (parent_child == ITEM) {                                               \
+      assert((ITEM)->prev.val == 0);                                          \
+      parent->child = (ITEM)->next;                                           \
+    }                                                                         \
+  }                                                                           \
+  (ITEM)->parent.val = 0;                                                     \
+  LIST_REMOVE(ITEM); /* Disconnect ITEM from its siblings. */                 \
+  ASSERT_TREE_NODE_INVARIANT(ITEM);
diff --git a/src/scene/scene_impl.h b/src/scene/scene_impl.h
new file mode 100644
index 0000000..ad2e892
--- /dev/null
+++ b/src/scene/scene_impl.h
@@ -0,0 +1,9 @@
+#pragma once
+
+#include <gfx/scene.h>
+
+#include "../types.h"
+
+typedef struct Scene {
+  node_idx root;
+} Scene;