1 files changed, 144 insertions, 0 deletions
diff --git a/src/scene/scene_graph.h b/src/scene/scene_graph.h
new file mode 100644
index 0000000..0b1f7d0
--- /dev/null
+++ b/src/scene/scene_graph.h
@@ -0,0 +1,144 @@
+/// Functions for list manipulation.
+#pragma once
+#include "scene_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),                              \
+      SceneCamera *: 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_graph.h b/src/scene/scene_graph.h new file mode 100644 index 0000000..0b1f7d0 --- /dev/null +++ b/src/scene/scene_graph.h
@@ -0,0 +1,144 @@
	1	/// Functions for list manipulation.
	2	#pragma once
	3
	4	#include "scene_memory.h"
	5
	6	// NOTE: SceneMemory guarantees that index 0 can be regarded as an invalid
	7	// index.
	8
	9	#define MEM_GET(INDEX) \
	10	_Generic( \
	11	(INDEX), \
	12	camera_idx: mem_get_camera, \
	13	material_idx: mem_get_material, \
	14	mesh_idx: mem_get_mesh, \
	15	mesh_link_idx: mem_get_mesh_link, \
	16	node_idx: mem_get_node, \
	17	object_idx: mem_get_object, \
	18	scene_idx: mem_get_scene)(INDEX)
	19
	20	#define MEM_GET_INDEX(ITEM) \
	21	_Generic( \
	22	(ITEM), \
	23	SceneCamera *: mem_get_camera_index, \
	24	Material *: mem_get_material_index, \
	25	Mesh *: mem_get_mesh_index, \
	26	MeshLink *: mem_get_mesh_link_index, \
	27	SceneNode *: mem_get_node_index, \
	28	SceneObject *: mem_get_object_index, \
	29	Scene *: mem_get_scene_index)(ITEM)
	30
	31	/// Assert the list node invariant.
	32	///
	33	/// - A node does not point to itself.
	34	#if NDEBUG
	35	#define ASSERT_LIST_NODE_INVARIANT(ITEM)
	36	#else
	37	#define ASSERT_LIST_NODE_INVARIANT(ITEM) \
	38	{ \
	39	const gfx_idx item_idx = MEM_GET_INDEX(ITEM).val; \
	40	assert((ITEM)->prev.val != item_idx); \
	41	assert((ITEM)->next.val != item_idx); \
	42	}
	43	#endif
	44
	45	/// Assert the tree node invariant.
	46	///
	47	/// - A node does not point to itself.
	48	/// - The node's left and right siblings cannot be equal, unless both are 0.
	49	/// - The node's left/right sibling cannot be its child, unless both are 0.
	50	/// - The node's parent cannot be the node's child or sibling, unless it's 0.
	51	/// - If the node has a parent and the node is the leftmost sibling, then the
	52	/// parent's child is the node.
	53	#define ASSERT_TREE_NODE_INVARIANT(ITEM) \
	54	{ \
	55	const gfx_idx item_idx = MEM_GET_INDEX(ITEM).val; \
	56	assert((ITEM)->prev.val != item_idx); \
	57	assert((ITEM)->next.val != item_idx); \
	58	if ((ITEM)->prev.val) { \
	59	assert((ITEM)->prev.val != (ITEM)->next.val); \
	60	} \
	61	if ((ITEM)->child.val) { \
	62	assert((ITEM)->child.val != (ITEM)->prev.val); \
	63	assert((ITEM)->child.val != (ITEM)->next.val); \
	64	} \
	65	assert((ITEM)->parent.val != item_idx); \
	66	if ((ITEM)->parent.val && !(ITEM)->prev.val) { \
	67	assert((ITEM)->parent.val != (ITEM)->prev.val); \
	68	assert((ITEM)->parent.val != (ITEM)->next.val); \
	69	const __typeof__(ITEM) item_parent = MEM_GET((ITEM)->parent); \
	70	assert(item_parent->child.val == item_idx); \
	71	} \
	72	}
	73
	74	/// Prepend an item to a list.
	75	/// Modify HEAD_INDEX to equal the index of the new head.
	76	#define LIST_PREPEND(HEAD_INDEX, ITEM) \
	77	(ITEM)->next = HEAD_INDEX; \
	78	if (HEAD_INDEX.val) { \
	79	__typeof__(ITEM) old_head = MEM_GET(HEAD_INDEX); \
	80	old_head->prev = MEM_GET_INDEX(ITEM); \
	81	} \
	82	HEAD_INDEX = MEM_GET_INDEX(ITEM); \
	83	ASSERT_LIST_NODE_INVARIANT(ITEM);
	84
	85	/// Disconnect an item from its siblings.
	86	#define LIST_REMOVE(ITEM) \
	87	if ((ITEM)->prev.val) { \
	88	__typeof__(ITEM) prev_sibling = MEM_GET((ITEM)->prev); \
	89	prev_sibling->next = (ITEM)->next; \
	90	} \
	91	if ((ITEM)->next.val) { \
	92	__typeof__(ITEM) next_sibling = MEM_GET((ITEM)->next); \
	93	next_sibling->prev = (ITEM)->prev; \
	94	} \
	95	(ITEM)->prev.val = 0; \
	96	(ITEM)->next.val = 0; \
	97	ASSERT_LIST_NODE_INVARIANT(ITEM);
	98
	99	/// Set the child's parent.
	100	///
	101	/// The hierarchy is a strict tree hierarchy and a parent node points to its
	102	/// first/leftmost child only. To add a new child, the new child becomes the
	103	/// leftmost node in the list of siblings, the one that the parent then points
	104	/// to.
	105	///
	106	/// The child is also completely disconnected from its previous hierarchy. This
	107	/// is because siblings in a hierarchy must all point to the same parent.
	108	#define SET_PARENT(CHILD, PARENT) \
	109	assert(CHILD); \
	110	assert(CHILD != PARENT); \
	111	ASSERT_TREE_NODE_INVARIANT(CHILD); \
	112	ASSERT_TREE_NODE_INVARIANT(PARENT); \
	113	TREE_REMOVE(CHILD); /* Disconnect CHILD from its previous hierarchy. */ \
	114	if (PARENT) { \
	115	LIST_PREPEND((PARENT)->child, CHILD); \
	116	(CHILD)->parent = MEM_GET_INDEX(PARENT); \
	117	} else { \
	118	(CHILD)->parent.val = 0; \
	119	} \
	120	ASSERT_TREE_NODE_INVARIANT(CHILD); \
	121	if (PARENT) { \
	122	ASSERT_TREE_NODE_INVARIANT(PARENT); \
	123	}
	124
	125	/// Remove an item from its hierarchy.
	126	///
	127	/// The item is disconnected from its parents and siblings. The hierarchy rooted
	128	/// under the item remains intact.
	129	#define TREE_REMOVE(ITEM) \
	130	assert(ITEM); \
	131	if ((ITEM)->parent.val) { \
	132	/* The parent points only to its first/leftmost child. If this item is */ \
	133	/* the leftmost sibling, then we need to rewire the parent to point to */ \
	134	/* the next sibling to keep the parent connected to its children. */ \
	135	__typeof__(ITEM) parent = MEM_GET((ITEM)->parent); \
	136	const __typeof__(ITEM) parent_child = MEM_GET(parent->child); \
	137	if (parent_child == ITEM) { \
	138	assert((ITEM)->prev.val == 0); \
	139	parent->child = (ITEM)->next; \
	140	} \
	141	} \
	142	(ITEM)->parent.val = 0; \
	143	LIST_REMOVE(ITEM); /* Disconnect ITEM from its siblings. */ \
	144	ASSERT_TREE_NODE_INVARIANT(ITEM);