Created
March 24, 2021 11:32
-
-
Save RealNeGate/1f600a424b3760ebd4c05532ada9edfe to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment