From 3f186ba1570f61d8cc5a1b8cdbb4c1d5f18bd848 Mon Sep 17 00:00:00 2001 From: 3gg <3gg@shellblade.net> Date: Sat, 7 Jan 2023 13:28:02 -0800 Subject: Let scene loader create logical nodes for other unhandled nodes; fix scene graph node wiring. --- gfx/include/gfx/scene/node.h | 5 +- gfx/src/scene/node.c | 62 ++++++++++++---- gfx/src/scene/node_impl.h | 18 +++-- gfx/src/scene/scene_graph.h | 173 ++++++++++++++++++++++++++++++------------- gfx/src/scene/scene_impl.h | 2 +- gfx/src/scene/scene_memory.c | 32 ++++---- gfx/src/scene/scene_memory.h | 12 +-- gfx/src/scene/types.h | 6 +- gfx/src/util/scene.c | 27 ++++--- gltfview/src/game.c | 2 + 10 files changed, 226 insertions(+), 113 deletions(-) diff --git a/gfx/include/gfx/scene/node.h b/gfx/include/gfx/scene/node.h index 736ff21..a09bdbc 100644 --- a/gfx/include/gfx/scene/node.h +++ b/gfx/include/gfx/scene/node.h @@ -2,7 +2,7 @@ #include -typedef struct Light Light; +typedef struct Light Light; typedef struct SceneCamera SceneCamera; typedef struct SceneObject SceneObject; @@ -43,3 +43,6 @@ void gfx_set_node_position(SceneNode*, const vec3* position); /// Set the node's rotation. void gfx_set_node_rotation(SceneNode*, const mat4* rotation); + +/// Log the node's hierarchy. +void gfx_log_node_hierarchy(const SceneNode*); diff --git a/gfx/src/scene/node.c b/gfx/src/scene/node.c index 7d7f69f..ee2f169 100644 --- a/gfx/src/scene/node.c +++ b/gfx/src/scene/node.c @@ -6,11 +6,14 @@ #include "scene_graph.h" #include "scene_memory.h" +#include +#include + #include static void scene_node_make(SceneNode* node) { assert(node); - node->type = LogicalNode; + node->type = LogicalNode; node->transform = mat4_id(); } @@ -29,8 +32,8 @@ SceneNode* gfx_make_camera_node(SceneCamera* camera) { if (!node) { return 0; } - node->type = CameraNode; - node->camera = mem_get_camera_index(camera); + node->type = CameraNode; + node->camera = mem_get_camera_index(camera); camera->parent = mem_get_node_index(node); return node; } @@ -41,8 +44,8 @@ SceneNode* gfx_make_light_node(Light* light) { if (!node) { return 0; } - node->type = LightNode; - node->light = mem_get_light_index(light); + node->type = LightNode; + node->light = mem_get_light_index(light); light->parent = mem_get_node_index(node); return node; } @@ -53,8 +56,8 @@ SceneNode* gfx_make_object_node(SceneObject* object) { if (!node) { return 0; } - node->type = ObjectNode; - node->object = mem_get_object_index(object); + node->type = ObjectNode; + node->object = mem_get_object_index(object); object->parent = mem_get_node_index(node); return node; } @@ -63,36 +66,40 @@ void gfx_destroy_node(SceneNode** node) { assert(node); assert(*node); - // Destroy the node's resources. - // Camera. + // Destroy the node's resource. if ((*node)->type == CameraNode) { SceneCamera* camera = mem_get_camera((*node)->camera); - camera->parent.val = 0; // Avoid recursive call into gfx_destroy_node(). + camera->parent.val = 0; // Avoid call into gfx_del_node(). gfx_destroy_camera(&camera); - } - // TODO: free light. - // Object. - if ((*node)->type == ObjectNode) { + } else if ((*node)->type == LightNode) { + Light* light = mem_get_light((*node)->light); + light->parent.val = 0; // Avoid call into gfx_del_node(). + gfx_destroy_light(&light); + } else if ((*node)->type == ObjectNode) { SceneObject* object = mem_get_object((*node)->object); - object->parent.val = 0; // Avoid recursive call into gfx_destroy_node(). + object->parent.val = 0; // Avoid call into gfx_del_node(). gfx_destroy_object(&object); } + // TODO: Should destroy children recursively? TREE_REMOVE(*node); mem_free_node(node); } +// 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); } void gfx_set_node_parent(SceneNode* child, SceneNode* parent) { assert(child); - assert(parent); + // Parent can be null. SET_PARENT(child, parent); } @@ -113,3 +120,26 @@ void gfx_set_node_rotation(SceneNode* node, const mat4* rotation) { assert(rotation); mat4_set_3x3(&node->transform, *rotation); } + +static void log_node_hierarchy_rec(const SceneNode* node, const sstring* pad) { + assert(node); + assert(pad); + + LOGD("%sNode (%u)", sstring_cstring(pad), 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); +} diff --git a/gfx/src/scene/node_impl.h b/gfx/src/scene/node_impl.h index ce3b769..f4aea79 100644 --- a/gfx/src/scene/node_impl.h +++ b/gfx/src/scene/node_impl.h @@ -8,9 +8,9 @@ /// Scene node type. typedef enum NodeType { + LogicalNode, CameraNode, LightNode, - LogicalNode, ObjectNode } NodeType; @@ -22,17 +22,19 @@ typedef struct SceneNode { NodeType type; union { camera_idx camera; - light_idx light; + light_idx light; 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. + 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; -/// Destroy a node given its index. +/// Destroy a node given its index without destroying its resource. /// /// The node is conveniently removed from the scene graph. +/// +/// This function is for the library's internal use only. void gfx_del_node(node_idx); diff --git a/gfx/src/scene/scene_graph.h b/gfx/src/scene/scene_graph.h index b9b3a14..93d2e38 100644 --- a/gfx/src/scene/scene_graph.h +++ b/gfx/src/scene/scene_graph.h @@ -3,65 +3,136 @@ #include "scene_memory.h" -// Note that SceneMemory guarantees that index 0 can be regarded as an invalid +// 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 \ +#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 * \ +#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) -#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); - -#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; \ +/// 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); \ } -#define SET_PARENT(CHILD, PARENT) \ - assert(CHILD); \ - if (CHILD->parent.val) { \ - LIST_REMOVE(CHILD); \ - } \ - if (parent) { \ - LIST_PREPEND(PARENT->CHILD, CHILD); \ +/// 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); \ + } \ } -#define TREE_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; \ - } \ - if ((ITEM)->parent.val) { \ - MEM_GET((ITEM)->parent)->child.val = 0; \ +/// 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/gfx/src/scene/scene_impl.h b/gfx/src/scene/scene_impl.h index e0c25bf..e6544dd 100644 --- a/gfx/src/scene/scene_impl.h +++ b/gfx/src/scene/scene_impl.h @@ -5,7 +5,7 @@ #include "types.h" typedef struct Scene { - node_idx root; + node_idx root; scene_idx next; scene_idx prev; } Scene; diff --git a/gfx/src/scene/scene_memory.c b/gfx/src/scene/scene_memory.c index cd4a79c..7355ad2 100644 --- a/gfx/src/scene/scene_memory.c +++ b/gfx/src/scene/scene_memory.c @@ -26,19 +26,19 @@ DEF_MEMPOOL(scene_pool, Scene, GFX_MAX_NUM_SCENES) /// /// Holds memory pools for every type of scene object. typedef struct SceneMemory { - camera_pool cameras; - light_pool lights; - material_pool materials; - mesh_pool meshes; + camera_pool cameras; + light_pool lights; + material_pool materials; + mesh_pool meshes; mesh_link_pool mesh_links; - node_pool nodes; - object_pool objects; - scene_pool scenes; + node_pool nodes; + object_pool objects; + scene_pool scenes; } SceneMemory; static SceneMemory mem; -#define ALLOC_DUMMY(POOL) \ +#define ALLOC_DUMMY(POOL) \ assert(mempool_get_block_index(POOL, mempool_alloc(POOL)) == 0) void scene_mem_init() { @@ -67,13 +67,13 @@ void scene_mem_destroy() {} // Memory allocation. SceneCamera* mem_alloc_camera() { return mempool_alloc(&mem.cameras); } -Light* mem_alloc_light() { return mempool_alloc(&mem.lights); } -Material* mem_alloc_material() { return mempool_alloc(&mem.materials); } -Mesh* mem_alloc_mesh() { return mempool_alloc(&mem.meshes); } -MeshLink* mem_alloc_mesh_link() { return mempool_alloc(&mem.mesh_links); } -SceneNode* mem_alloc_node() { return mempool_alloc(&mem.nodes); } +Light* mem_alloc_light() { return mempool_alloc(&mem.lights); } +Material* mem_alloc_material() { return mempool_alloc(&mem.materials); } +Mesh* mem_alloc_mesh() { return mempool_alloc(&mem.meshes); } +MeshLink* mem_alloc_mesh_link() { return mempool_alloc(&mem.mesh_links); } +SceneNode* mem_alloc_node() { return mempool_alloc(&mem.nodes); } SceneObject* mem_alloc_object() { return mempool_alloc(&mem.objects); } -Scene* mem_alloc_scene() { return mempool_alloc(&mem.scenes); } +Scene* mem_alloc_scene() { return mempool_alloc(&mem.scenes); } // Memory free. void mem_free_camera(SceneCamera** camera) { @@ -127,8 +127,8 @@ light_idx mem_get_light_index(const Light* light) { return (light_idx){.val = mempool_get_block_index(&mem.lights, light)}; } material_idx mem_get_material_index(const Material* material) { - return (material_idx){.val = - mempool_get_block_index(&mem.materials, material)}; + return (material_idx){ + .val = mempool_get_block_index(&mem.materials, material)}; } mesh_idx mem_get_mesh_index(const Mesh* mesh) { return (mesh_idx){.val = mempool_get_block_index(&mem.meshes, mesh)}; diff --git a/gfx/src/scene/scene_memory.h b/gfx/src/scene/scene_memory.h index dff5bd8..b0fa73c 100644 --- a/gfx/src/scene/scene_memory.h +++ b/gfx/src/scene/scene_memory.h @@ -3,14 +3,14 @@ #include "types.h" -typedef struct Light Light; -typedef struct Material Material; -typedef struct Mesh Mesh; -typedef struct MeshLink MeshLink; +typedef struct Light Light; +typedef struct Material Material; +typedef struct Mesh Mesh; +typedef struct MeshLink MeshLink; typedef struct SceneCamera SceneCamera; -typedef struct SceneNode SceneNode; +typedef struct SceneNode SceneNode; typedef struct SceneObject SceneObject; -typedef struct Scene Scene; +typedef struct Scene Scene; /// Initialize scene memory. /// diff --git a/gfx/src/scene/types.h b/gfx/src/scene/types.h index 2863ac7..1c52991 100644 --- a/gfx/src/scene/types.h +++ b/gfx/src/scene/types.h @@ -6,9 +6,9 @@ typedef uint16_t gfx_idx; // Strongly-typed indices. -#define DEF_STRONG_INDEX(TYPE_NAME) \ - typedef struct TYPE_NAME##_idx { \ - gfx_idx val; \ +#define DEF_STRONG_INDEX(TYPE_NAME) \ + typedef struct TYPE_NAME##_idx { \ + gfx_idx val; \ } TYPE_NAME##_idx; DEF_STRONG_INDEX(camera) diff --git a/gfx/src/util/scene.c b/gfx/src/util/scene.c index 35d6dd0..87d775c 100644 --- a/gfx/src/util/scene.c +++ b/gfx/src/util/scene.c @@ -779,8 +779,8 @@ static bool load_meshes( /// This function ignores the many scenes and default scene of the glTF spec /// and instead just loads all nodes into a single gfx Scene. static void load_nodes( - const cgltf_data* data, Gfx* gfx, SceneNode* root_node, - SceneObject** objects, SceneCamera** cameras, SceneNode** nodes) { + const cgltf_data* data, SceneNode* root_node, SceneObject** objects, + SceneCamera** cameras, SceneNode** nodes) { // Note that with glTF 2.0, nodes do not form a DAG / scene graph but a // disjount union of strict trees: // @@ -793,8 +793,6 @@ static void load_nodes( // This matches the gfx library implementation, where every node can have at // most one parent. assert(data); - // TODO: gfx not needed? - assert(gfx); assert(root_node); assert(objects); assert(cameras); @@ -841,7 +839,13 @@ static void load_nodes( nodes[n] = gfx_make_camera_node(cameras[next_camera]); ++next_camera; } else { - continue; // TODO: implementation for missing node types. + // TODO: implementation for missing node types. + // Create a vanilla SceneNode for unhandled node types for the sake of + // being able to complete the hierarchy. Otherwise, wiring nodes in pass 2 + // fails. + LOGW("Unhandled node type, creating vanilla SceneNode for hierarchy " + "completeness"); + nodes[n] = gfx_make_node(); } assert(nodes[n]); @@ -868,10 +872,11 @@ static void load_nodes( } gfx_set_node_transform(nodes[n], &transform); - // By default, set nodes as children of the root node. The second pass will - // properly set the parent of the relevant nodes, and leave the root node as - // the parent for top-level nodes. - gfx_set_node_parent(nodes[n], root_node); + // If this is a top-level node in the glTF scene, set its parent to the + // given root node. + if (!node->parent) { + gfx_set_node_parent(nodes[n], root_node); + } } // SceneNode. // Second pass: wire nodes together to build the hierarchy. @@ -883,7 +888,7 @@ static void load_nodes( const cgltf_size child_index = parent->children[c] - data->nodes; assert(child_index < data->nodes_count); SceneNode* child_scene_node = nodes[child_index]; - + assert(child_scene_node); gfx_set_node_parent(child_scene_node, parent_scene_node); } } @@ -982,7 +987,7 @@ static bool load_scene( goto cleanup; } - load_nodes(data, gfx, root_node, scene_objects, scene_cameras, scene_nodes); + load_nodes(data, root_node, scene_objects, scene_cameras, scene_nodes); return true; diff --git a/gltfview/src/game.c b/gltfview/src/game.c index 224200d..93755e7 100644 --- a/gltfview/src/game.c +++ b/gltfview/src/game.c @@ -121,6 +121,8 @@ static bool load_scene( return false; } + gfx_log_node_hierarchy(gfx_get_scene_root(game->scene)); + return true; } -- cgit v1.2.3