Recursive algorithm implementing the processing of a 3-dimensional space using the octree decomposition with OpenMP thread parallelization pragmas.

octree.c

/**
 * This is free and unencumbered software released into the public domain.
 *
 * Anyone is free to copy, modify, publish, use, compile, sell, or
 * distribute this software, either in source code form or as a compiled
 * binary, for any purpose, commercial or non-commercial, and by any
 * means.
 *
 * In jurisdictions that recognize copyright laws, the author or authors
 * of this software dedicate any and all copyright interest in the
 * software to the public domain. We make this dedication for the benefit
 * of the public at large and to the detriment of our heirs and
 * successors. We intend this dedication to be an overt act of
 * relinquishment in perpetuity of all present and future rights to this
 * software under copyright law.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 *
 * For more information, please refer to <https://unlicense.org>
 */

#include "octree.h"

uint32_t process_cube(size_vec3_t cube_offset)
{
    return 1;
}

uint32_t expand_cube(uint32_t grid_size, uint32_t depth, size_vec3_t cube_offset)
{
    uint32_t total_cubes = 0;

    if (1 == (grid_size >> depth)) {
        return process_cube(cube_offset);
    }

    uint32_t new_depth = depth + 1;
    uint32_t new_edge_size = grid_size >> new_depth;

    if (0 == new_edge_size) {
        return 0;
    }

    for (int i = 0; i < 8; i++) {
#pragma omp task shared(total_cubes)
        {
            size_vec3_t new_cube_offset = {0};
            for (int j = 0; j < 3; j++) {
                new_cube_offset.values[j] = cube_offset.values[j] + (new_edge_size * ((i >> j) & 1));
            }
            total_cubes += expand_cube(grid_size, new_depth, new_cube_offset);
        }
    }

#pragma omp taskwait
    return total_cubes;
}

uint32_t build_cubes(size_t grid_size)
{
    uint32_t total_cubes = 0;
    size_vec3_t starting_offset = {0};

#pragma omp parallel
    {
#pragma omp master
        {
            total_cubes = expand_node(grid_size, 0, starting_offset);
        }
    }

    return total_cubes;
}

octree.h

/**
 * This is free and unencumbered software released into the public domain.
 *
 * Anyone is free to copy, modify, publish, use, compile, sell, or
 * distribute this software, either in source code form or as a compiled
 * binary, for any purpose, commercial or non-commercial, and by any
 * means.
 *
 * In jurisdictions that recognize copyright laws, the author or authors
 * of this software dedicate any and all copyright interest in the
 * software to the public domain. We make this dedication for the benefit
 * of the public at large and to the detriment of our heirs and
 * successors. We intend this dedication to be an overt act of
 * relinquishment in perpetuity of all present and future rights to this
 * software under copyright law.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 *
 * For more information, please refer to <https://unlicense.org>
 */

#ifndef OCTREE_H_
#define OCTREE_H_

#include <stdlib.h>

typedef unsigned int uint32_t;

typedef struct {
    union {
        struct {
            size_t x;
            size_t y;
            size_t z;
        };
        size_t values[3];
    };
} size_vec3_t;

uint32_t process_cube(size_vec3_t cube_offset);
uint32_t expand_cube(uint32_t grid_size, uint32_t depth, size_vec3_t cube_offset);
uint32_t build_cubes(uint32_t grid_size);

#endif // OCTREE_H_