KdTreeTraversal.c

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdint.h>
#include <stdlib.h>

typedef float Vec3 __attribute__((ext_vector_type(3)));

#define MAX_KD_NODES 1024

typedef size_t TriangleID;

typedef enum Axis {
    Axis_Xp,
    Axis_Xn,
    Axis_Yp,
    Axis_Yn,
    Axis_Zp,
    Axis_Zn
} Axis;

typedef struct KdNodes {
    struct {
        Vec3 split_pos;
        uint32_t children[2];
        Axis axis;
    } header[MAX_KD_NODES];
    struct {
        size_t count;
        Vec3* points;
    } content[MAX_KD_NODES];
} KdNodes;

size_t Traverse(KdNodes* nodes, Vec3 pos, size_t node) {
    do {
        Axis axis = nodes->header[node].axis;
        Vec3 split_pos = nodes->header[node].split_pos;
        uint32_t* children = nodes->header[node].children;

        Vec3 diff = split_pos - pos;

        int median;
        switch (axis) {
        case Axis_Xp: median = diff.x >= 0.0; break;
        case Axis_Xn: median = diff.x < 0.0; break;
        case Axis_Yp: median = diff.y >= 0.0; break;
        case Axis_Yn: median = diff.y < 0.0; break;
        case Axis_Zp: median = diff.z >= 0.0; break;
        case Axis_Zn: median = diff.z < 0.0; break;
        default: __builtin_unreachable();
        }

        if (children[0] == children[1]) return node;
        node = children[median];
    } while (1);
}