Iterating the octree while keeping track of the positive neighboring nodes

Question

Review context can be found here: 32x32x32 Units Octree With 15-Bit Voxels: Second Edition

The above question and the self answer include information such as the definition of the Octree and Node8 data structures, MAX_LEVEL, DATA_MASK, and FLAG_MASK macros, and an overall description of this system. They only include an octree_get() function to query a node at a given location and octree_set() function to set a node in a given location.

The only difference is that the base field of Octree is now in the beginning and not the end. But just for good measure I will include them here also:

#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <assert.h>
#include <stdio.h>
#define FLAG_MASK 0x8000
#define DATA_MASK 0x7FFF
#define MAX_LEVEL 5
#define node_to_set(ptr) ((Node8 *)((uintptr_t)(ptr)&-sizeof(Node8)))
typedef union Node2 {
    uint16_t x[2];
    uint32_t z;
} Node2;
typedef union Node4 {
    uint16_t x[4];
    Node2 z[2];
    uint64_t y;
} Node4;
typedef union Node8 {
    uint16_t x[8];
    Node2 z[4];
    Node4 y[2];
} Node8;
typedef union Ptr {
    union Ptr *p;
    uint64_t u;
} Ptr;
typedef struct Octree {
    uint16_t base, data_size, set_size;
    uint8_t data_alloc, set_alloc;
    Ptr data;
    Node8 set[];
} Octree;

The reason for the difference is so then an Octree pointer and the pointer to the base are the same and can be treated interchangeably. No need to initialize a new array with addresses of the base fields of the Octree pointers in octree_next because then octree_next can be used directly for this purpose.

---

I have created new code loosely based on the Iter() function in my even older question: 32x32x32 units octree, that supports 15-bit data units

I have taken this a step further. Instead of simply descending each branch and printing out the value of each node, the descent process involves recording all the neighbors. The code should print not only the value of each node (3 times), but also the value of the node immediately to the East of (positive X-axis), to the North of (positive Z-axis), and above (positive Y-axis) then current node.

I also included the xzy array to keep track of the spatial coordinates of the current node. More specifically, of the Southwest bottom corner of the node, where the North/East/upwards extent of the node is simply 32>>level. This is somewhat confusing, because in my previous question with the octree_get/octree_set() functions, level == 0 represents the bottom/most subdivided layer of the tree, and not the top/least subdivided layers.

Note: next in identifiers in the code refers to 'neighboring.' They have similar meanings and the former is easier to type. The function itself is called octree_render() because iterating the structure while keeping track of the neighboring nodes is the first step in actually rendering the voxels onscreen, because this is needed to find all the exposed voxel faces in the region. I am not at that point yet but I would like to make sure I have a solid foundation before continuing.

The first iteration runs unconditionally to make sure that the root node is processed. Then, if no descent has occurred (level is still 0), the loop is broken. When the loop is ascended (once index reaches zero and all descents have either not existed or already been handled), the level is checked before continuing, to avoid revisiting the same nodes infinity times.

void octree_render(const Octree *const octree, const Octree *const octree_next[const static 3]) {
    const uint16_t **next_ptr = (const uint16_t **)octree_next, *next_stack[MAX_LEVEL][3];
    const Node8 *set_ptr = (const Node8 *)octree, *set_stack[MAX_LEVEL];
    unsigned level = 0, index = 0, index_stack[MAX_LEVEL], xzy[3] = {0};
    for (;;) {
        for (;;) {
            const unsigned node = set_ptr->x[index];
            if (node&FLAG_MASK && level < MAX_LEVEL) {
                set_stack[level] = set_ptr;
                set_ptr += node&DATA_MASK;
                index_stack[level] = index;
                index = 7;
                memcpy(next_stack+(level++), next_ptr, sizeof(*next_stack));
                goto update;
            }
            for (unsigned dim = 2;; --dim) {
                printf("%d %d %d\n", node, *next_ptr[dim], xzy[dim]);
                if (!dim)
                    break;
            }
            if (!index)
                break;
            --index;
        update:
            for (uint_fast8_t dim = (index&1)<<(index>>1&1);; --dim) {
// The weird expression that dim is initialized to makes sure that only the values that have to be updated are updated
// The X values have to be updated twice as often as the Z values, which have to be updated twice as often as the Y values
                xzy[dim] ^= 32>>level;
                const unsigned bit = 1<<dim;
                const uint16_t *const next_dim = next_stack[level-1][dim];
                next_ptr[dim] = index&bit ?
                    *next_dim&0x8000 // The neighboring node is in the neighboring set
                    ? // The next set has to be descended
                        (node_to_set(next_dim)+(*next_dim&0x7FFF))->x+(index&~bit)
                        : next_dim
                    : set_ptr->x+(index|bit); // The neighboring node is in the current set
                if (!dim)
                    break;
            }
        }
    done:
        if (!level)
            break;
        if (!(index = index_stack[--level]))
            goto done;
        --index;
        set_ptr = set_stack[level];
        memcpy(next_ptr, next_stack+level, sizeof(*next_stack));
        goto update;
    }
}

I have tested the function and it gives expected results for several test cases including this one:

Octree *octree = memset(malloc(sizeof(Octree)), 0, sizeof(Octree));
octree = octree_set(octree, 1, 1, 0, 0);
octree = octree_set(octree, 2, 2, 0, 0);
Octree *blank = &(Octree){0};
octree_render(octree, (const Octree *const []){blank, blank, blank});
free(octree);

Some concerns:

• Spaghetti code: I find my code difficult to follow due to the nested loops and goto statements, but this is the only way I figured out how to achieve the logic that does not involve any redundant tests. Is there a clearer way to express the loop logic? If goto is still needed that is OK but its current state seems unnecessarily complex.

• How can I avoid having to modify octree_next (as pointed to by next_ptr) and how can I avoid having to use memcpy to copy data to and from next_ptr and next_stack? There should be a way to change next_ptr to reference the top of next_stack somehow but I could not get that to work out. (The initial value it points to might (?) not be needed after the first iteration).

Answer 1

General Observations

The code seems to be getting worse rather than improving. It isn't clear that you are following any of the advice you have been given before. I would like to down vote this question because you haven't been using the advice but I won't.

Reuse of variable names such as dim is confusing and can lead to programming errors.

Avoid Goto

The use of goto will by definition lead to spaghetti code. Use functions instead. The update code is one function, the done is another function which seems to call the update function.

There are occasions where a goto can't be avoided in the C programming language, but this is only true in error handling. I have written more than 100000 line of C code professionally and there were less than 10 gotos in that code.

Make the Code More Readable

This has been mentioned in the previous 2 versions (version 1 and version 2) of this question. You still haven't made the code more readable.

There should be white space between every operator and operand. Instead of

            if (node&FLAG_MASK && level < MAX_LEVEL) {
                set_stack[level] = set_ptr;
                set_ptr += node&DATA_MASK;
                index_stack[level] = index;
                index = 7;
                memcpy(next_stack+(level++), next_ptr, sizeof(*next_stack));
                goto update;
            }

using spaces as necessary:

            if (node & FLAG_MASK && level < MAX_LEVEL) {
                set_stack[level] = set_ptr;
                set_ptr += node & DATA_MASK;
                index_stack[level] = index;
                index = 7;
                memcpy(next_stack + (level++), next_ptr, sizeof(*next_stack));
                goto update;
            }

Magic Numbers

The code introduces new Magic Numbers, 7 in the code above and 2 in the code below:

            for (unsigned dim = 2;; --dim) {
                printf("%d %d %d\n", node, *next_ptr[dim], xzy[dim]);
                if (!dim)
                    break;
            }

and even more magic numbers here

                xzy[dim] ^= 32>>level;
                const unsigned bit = 1<<dim;
                const uint16_t *const next_dim = next_stack[level-1][dim];
                next_ptr[dim] = index&bit ?
                    *next_dim&0x8000 // The neighboring node is in the neighboring set
                    ? // The next set has to be descended
                        (node_to_set(next_dim)+(*next_dim&0x7FFF))->x+(index&~bit)
                        : next_dim
                    : set_ptr->x+(index|bit); // The neighboring node is in the current set

Dry Code

The best way to reduce code duplication is to use functions for the repetitive code.

Prefer Braces { and } Around Single Statements in if or loops

Some programmers consider this a style issue, but it makes it much easier to read and maintain the code if each in an if, else or loop block is embedded within braces. Extending the functionality of these statements can be problematic when the braces are not used. For a more in depth discussion of this see the first 2 answers on this Stack Overflow question. As one of the answers points out this is true in all C like languages (C, C++, C#, JavaScript, Java, etc.). I have worked at multiple companies where this was required in the coding standard and flagged during code reviews.

Declare the Variables as Needed

A recommended programming practice to declare the variable as needed. In C the language doesn't provide a default initialization of the variable so variables should be initialized as part of the declaration. For readability and maintainability each variable should be declared and initialized on its own line.

    const uint16_t **next_ptr = (const uint16_t **)octree_next;
    const uint16_t *next_stack[MAX_LEVEL][3];
    const Node8 *set_ptr = (const Node8 *)octree;
    const Node8 *set_stack[MAX_LEVEL];
    unsigned level = 0;
    unsigned index = 0;
    unsigned index_stack[MAX_LEVEL]
    unsigned xzy[3] = {0};

Answer 2

Using the right tool for the job

When I first wrote this, I insisted on using an iterative approach, because I was rote taught that iteration is faster than recursion. However, an octree is a recursive data structure by nature. Using actual recursion instead of iteration-emulated recursion reflects the structure of the octree much more cleanly. All the really convoluted loop logic complete with goto statements can be avoided entirely, and the resulting code is much shorter, and the underlying logic is much easier to see.

I have also, as suggested, added spacing between all binary arithmetic operators.

A possible implementation of this for my purposes looks like this (untested):

struct Scope {
    void *const buf;
    unsigned count;
    uint_fast16_t node;
    uint_fast8_t dim, quad_level, xzy[3], level;
};
static void quad_render(struct Scope *const scope, const uint16_t *ptr) {
    // TODO: Emit vertices for quads
    printf("%d %d %d\n", scope->node, *ptr, scope->xzy[dim]);
}
struct Next {
    const uint16_t *ptr[3];
};
static void cube_render(struct Scope *const scope, const uint16_t *restrict ptr, struct Next next) {
    if (*ptr & FLAG_MASK && scope->level) {
        ptr = enter(ptr)->x;
        uint_fast8_t mask[3];
        for (uint_fast8_t dim = 0; dim < 3; ++dim)
            mask[dim] = *next.ptr[dim] & FLAG_MASK ? next.ptr[dim] = enter(next.ptr[dim])->x, (1 << dim) ^ 7 : 0;
        --scope->level;
        for (uint_fast8_t i = 0; i < 8; ++i) {
            cube_render(scope, ptr + i, (struct Next){
                i & 1 ? next.ptr[0] + (i & mask[0]) : ptr + (i | 1),
                i & 2 ? next.ptr[1] + (i & mask[1]) : ptr + (i | 2),
                i & 4 ? next.ptr[2] + (i & mask[2]) : ptr + (i | 4)
            });
            scope->xzy[0] ^= 1 << scope->level;
            scope->xzy[1] ^= (i & 1) << scope->level;
            scope->xzy[2] ^= ((i & 3) == 3) << scope->level;
        }
        ++scope->level;
        return;
    }
    for (scope->node = *ptr, scope->dim = 0, scope->quad_level = scope->level; scope->dim < 3; ++scope->dim)
        quad_render(scope, next.ptr[scope->dim]);
}
void octree_render(const Octree *const restrict octree, const Octree *const next[const restrict static 3]) {
    struct Scope scope = { /* ... */ };
    cube_render(&scope, &octree->base, (struct Next){&next[0]->base, &next[1]->base, &next[2]->base});
}