From bd57f345ed9dbed1d81683e48199626de2ea9044 Mon Sep 17 00:00:00 2001 From: 3gg <3gg@shellblade.net> Date: Fri, 27 Jun 2025 10:18:39 -0700 Subject: Restructure project --- src/scene/scene_graph.h | 138 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 138 insertions(+) create mode 100644 src/scene/scene_graph.h (limited to 'src/scene/scene_graph.h') diff --git a/src/scene/scene_graph.h b/src/scene/scene_graph.h new file mode 100644 index 0000000..a26f828 --- /dev/null +++ b/src/scene/scene_graph.h @@ -0,0 +1,138 @@ +/// 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. +#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); \ + } + +/// 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); -- cgit v1.2.3