Author:ptrace
Comitter:ptrace
Date:2026-05-04 01:06:15 UTC
diff --git a/src/main.jai b/src/main.jai
index 6d88628..170e051 100644
--- a/src/main.jai
+++ b/src/main.jai
@@ -5,6 +5,8 @@
#import "Print_Vars";
#import "raylib";
#load "tree_viz.jai";
/*
@@ -42,6 +44,11 @@ rects := Rectangle.[
{ 30.0, -70.0, 9.0, 16.0 },
];
tree: [..]int;
bvs: [..]Aabb;
camera: Camera2D;
color_choice := Color.[
ORANGE,
YELLOW,
@@ -49,23 +56,26 @@ color_choice := Color.[
BLUE,
];
NODE_INTERNAL :: -6;
NODE_ROOT :: -9;
NODE_INTERNAL :: -7;
NODE_EMPTY :: -1;
DRAW_BV :: true;
SCREEN_WIDTH :: 1920;
SCREEN_HEIGHT :: 1080;
TREE_VIEW :: true;
Aabb :: struct {
upper_bound: Vector2;
lower_bound: Vector2;
}
Tree :: struct {
data: [..]int;
}
Node :: struct {
parent: int = NODE_EMPTY;
left: int = NODE_EMPTY;
@@ -73,119 +83,242 @@ Node :: struct {
}
#if false main :: () {
#if true main :: () {
#if MEMORY_DEBUGGER_ENABLED defer report_memory_leaks();
log("Hello, Sailor!");
camera: Camera2D;
camera.offset = { 400.0, 300.0 };
camera.zoom = 1.0;
SetTraceLogLevel(.LOG_NONE);
SetConfigFlags(.FLAG_MSAA_4X_HINT);
InitWindow(800, 600, "Template");
InitWindow(SCREEN_WIDTH, SCREEN_HEIGHT, "Template");
defer CloseWindow();
SetTargetFPS(60);
for rects array_add(*bvs, make_aabb(it));
log_vars(bvs.count-1);
array_add(*tree, NODE_INTERNAL, 0, 1);
log_vars(tree);
for i: 2..bvs.count-1 {
// Find sibling
id := find_best_sibling(i);
// log_vars(id);
// Insert
tree_split_node(id, i);
// log_vars(tree);
// Refit
}
bounds: Treev_Bounds;
#if TREE_VIEW then treev_init(tree, *bounds);
{
using bounds;
camera.zoom = fit_zoom;
camera.offset = { SCREEN_WIDTH / 2.0, SCREEN_HEIGHT / 2.0 };
camera.target = { (min.x + max.x) / 2.0, (min.y + max.y) / 2.0 };
}
drag_start: Vector2;
dragging: bool;
push_allocator(temp);
while !WindowShouldClose() {
if IsMouseButtonPressed(.LEFT) {
drag_start = GetMousePosition();
dragging = true;
}
if IsMouseButtonReleased(.LEFT) then dragging = false;
if dragging {
current := GetMousePosition();
camera.target.x -= (current.x - drag_start.x) / camera.zoom;
camera.target.y -= (current.y - drag_start.y) / camera.zoom;
drag_start = current;
}
wheel := GetMouseWheelMove();
if wheel != 0.0 {
mouse_screen := GetMousePosition();
before := Vector2.{
camera.target.x + (mouse_screen.x - camera.offset.x) / camera.zoom,
camera.target.y + (mouse_screen.y - camera.offset.y) / camera.zoom
};
camera.zoom *= (1.0 + wheel * 0.1);
if camera.zoom < 0.1 then camera.zoom = 0.1;
if camera.zoom > 5.0 then camera.zoom = 5.0;
camera.target.x = before.x - (mouse_screen.x - camera.offset.x) / camera.zoom;
camera.target.y = before.y - (mouse_screen.y - camera.offset.y) / camera.zoom;
}
BeginDrawing();
defer EndDrawing();
ClearBackground({ 42, 42, 60, 255 });
gx: s32;
while gx < SCREEN_WIDTH {
DrawLine(gx, 0, gx, SCREEN_HEIGHT, { 255,255,255,12 });
gx += 40;
}
gy: s32;
while gy < SCREEN_HEIGHT {
DrawLine(0, gy, SCREEN_WIDTH, gy, { 255,255,255,12 });
gy += 40;
}
{
BeginMode2D(camera);
defer EndMode2D();
// box1 := make_aabb(rects[0]);
// box2 := make_aabb(rects[1]);
// u := aabb_bv_union(box1, box2);
// Make AABBs
aabbs: [..]Aabb;
for rects array_add(*aabbs, make_aabb(it));
for rects DrawRectangleLinesEx(
it,
1.0,
color_choice[it_index % color_choice.count]
);
// sleep_milliseconds(500);
#if TREE_VIEW then treev_draw();
}
#if TREE_VIEW then treev_screen_draw();
DrawFPS(10, 10);
DrawText(TextFormat("Frame Time: %f s", GetFrameTime()), 10, 30, 20, WHITE);
DrawText(TextFormat("Frame Time: % s", GetFrameTime()), 10, 40, 20, WHITE);
reset_temporary_storage();
}
} else main :: () {
log("Offline");
tree: Tree;
array_add(*tree.data, 100);
array_add(*tree.data, 110);
array_add(*tree.data, 120);
array_add(*tree.data, 111);
array_add(*tree.data, 112);
array_add(*tree.data, 121);
array_add(*tree.data, 122);
for rects array_add(*bvs, make_aabb(it));
log_vars(bvs.count-1);
log_vars(tree.data);
array_add(*tree, NODE_INTERNAL, 0, 1);
log_vars(tree);
t := tree_access_node(tree, 0);
log_vars(t);
for i: 2..bvs.count-1 {
// Find sibling
id := find_best_sibling(i);
log_vars(id);
tree_split_node(*tree, 2, 400, 401);
log_vars(tree.data);
// Insert
tree_split_node(id, i);
log_vars(tree);
t = tree_access_node(tree, 2);
log_vars(t);
// Refit
}
log("-------------------");
log_vars(tree);
// tree_debug_view();
}
/** Continue:
- Refit
- Rotate
- Collapse
*/
find_best_sibling :: (id: int) -> id: int {
candidate := bvs[id];
best_sa := FLOAT32_INFINITY;
best_sibling := -1;
for tree {
if it == NODE_INTERNAL || it == NODE_EMPTY continue;
sa := aabb_get_sa(bvs[it], candidate);
if sa < best_sa {
best_sa = sa;
best_sibling = it_index;
}
}
return best_sibling;
}
tree_split_node :: (tree: *Tree, index: int, left: int, right: int) {
i_left := 2 * index + 1;
i_right := 2 * index + 2;
tree_split_node :: (index: int, left: int) {
i_left, i_right := tree_get_ids(index);
while tree.data.count <= i_right {
array_add(*tree.data, NODE_EMPTY);
while tree.count <= i_right {
array_add(*tree, NODE_EMPTY);
}
tree.data[i_left] = left;
tree.data[i_right] = right;
tree.data[index] = NODE_INTERNAL;
// tree.data[index] becomes an internal node — refit its bounding volume
tree[i_left] = left;
tree[i_right] = tree[index];
tree[index] = NODE_INTERNAL;
// tree.data[index] -> refit bv
}
tree_access_node :: (tree: Tree, index: int) -> Node {
tree_access_node :: (index: int) -> Node {
node: Node;
i_left := 2 * index + 1;
i_right := 2 * index + 2;
i_parent := cast(int)floor((index - 1.0) / 2.0);
i_left, i_right, i_parent := tree_get_ids(index);
for int.[i_left, i_right] {
if it > tree.data.count return node;
if it > tree.count return node;
}
node.left = tree.data[i_left];
node.right = tree.data[i_right];
node.parent = ifx i_parent < 0 then NODE_ROOT else tree.data[i_parent];
left := tree[i_left];
right := tree[i_right];
node.left = left;
node.right = right;
node.parent = ifx i_parent < 0 then NODE_INTERNAL else tree[i_parent];
return node;
}
tree_get_ids :: (index: int) -> (left: int, right: int, parent: int) {
i_left := 2 * index + 1;
i_right := 2 * index + 2;
i_parent := cast(int)floor((index - 1.0) / 2.0);
return i_left, i_right, i_parent;
}
tree_get_parent_from_id :: (id: int) -> int {
// even == right; odd == left
lr := ifx (id % 2 == 0) then 2 else 1;
index := (id - lr) / 2;
return index;
}
/* TODO: check this! */
// tree_refit :: (tree: *Tree, index: int) {
// while index > 0 {
// i_left := 2 * index + 1;
// i_right := 2 * index + 2;
// i_parent := cast(int)floor((index - 1.0) / 2.0);
// // Refit this node to enclose both children
// tree.data[index] = aabb_bv_union(
// tree.data[i_left],
// tree.data[i_right]
// );
// index = i_parent;
// }
// // Refit the root (index 0) separately, since the while loop stops before it
// i_left := 1;
// i_right := 2;
// tree.data[0] = aabb_bv_union(
// tree.data[i_left],
// tree.data[i_right]
// );
// }
tree_debug_view :: () {
for tree {
node := tree_access_node(it_index);
if (node.parent == NODE_EMPTY) then continue;
log_vars(it_index, node.parent, node.left, node.right);
// log_vars(it, node.parent, bvs[node.left], bvs[node.right]);
}
}
make_aabb :: (rect: Rectangle) -> Aabb {
@@ -218,3 +351,9 @@ aabb_bv_union :: (a: Aabb, b: Aabb) -> Aabb {
return c;
}
aabb_get_sa :: (a: Aabb, b: Aabb) -> float {
un := aabb_bv_union(a, b);
sa := aabb_bv_compute_surface_area(un);
return sa;
}
diff --git a/src/tree_viz.jai b/src/tree_viz.jai
new file mode 100644
index 0000000..29a543a
--- /dev/null
+++ b/src/tree_viz.jai
@@ -0,0 +1,482 @@
Treev_Bounds :: struct {
min, max: Vector2;
fit_zoom: float = 1.0;
}
treev_init :: (t: [..]int, bounds: *Treev_Bounds) {
tree = array_copy(t);
tree_size = tree.count;
assign_positions(0, xx PADDING, xx (SCREEN_WIDTH - PADDING), 0);
// for i: 0..node_count-1 log_vars(nodes[i]);
min, max: Vector2;
min.x = nodes[0].x - NODE_RADIUS;
max.x = nodes[0].x + NODE_RADIUS;
min.y = nodes[0].y - NODE_RADIUS;
max.y = nodes[0].y + NODE_RADIUS;
for i: 1..node_count-1 {
if nodes[i].x - NODE_RADIUS < min.x then min.x = nodes[i].x - NODE_RADIUS;
if nodes[i].x + NODE_RADIUS > max.x then max.x = nodes[i].x + NODE_RADIUS;
if nodes[i].y - NODE_RADIUS < min.y then min.y = nodes[i].y - NODE_RADIUS;
if nodes[i].y + NODE_RADIUS > max.y then max.y = nodes[i].y + NODE_RADIUS;
}
tree_w := max.x - min.x;
tree_h := max.y - min.y;
zoom_x := (SCREEN_WIDTH * 0.90) / tree_w;
zoom_y := (SCREEN_HEIGHT * 0.90) / tree_h;
fit_zoom := ifx zoom_x < zoom_y then zoom_x else zoom_y;
bounds.min = min;
bounds.max = max;
bounds.fit_zoom = fit_zoom;
}
treev_draw :: () {
mouse := GetMousePosition();
mouse_world := GetScreenToWorld2D(mouse, camera);
for i: 0..node_count-1 {
n := nodes[i];
idx_left := 2 * n.index + 1;
idx_right := 2 * n.index + 2;
found_l, lc := find_node(idx_left);
found_r, rc := find_node(idx_right);
if found_l {
DrawLineEx(
{ n.x, n.y }, { lc.x, lc.y }, 2.0, { 100, 180, 255, 160 }
);
}
if found_r {
DrawLineEx(
{ n.x, n.y }, { rc.x, rc.y }, 2.0, { 255, 140, 100, 160 }
);
}
tn_x := cast(s32, n.x);
tn_y := cast(s32, n.y);
is_internal := n.value == NODE_INTERNAL;
glow := ifx is_internal
then Color.{ 80, 160, 255, 60 }
else Color.{ 80, 255, 160, 60 };
DrawCircle(tn_x, tn_y, NODE_RADIUS + 6.0, glow);
fill := ifx is_internal
then Color.{ 30, 60, 120, 255 }
else Color.{ 30, 110, 70, 255 };
if CheckCollisionPointCircle(mouse_world, { n.x, n.y }, NODE_RADIUS) {
fill += Color.{ 30, 30, 30, 0 };
}
DrawCircle(tn_x, tn_y, xx NODE_RADIUS, fill);
border := ifx is_internal
then Color.{ 100, 180, 255, 255 }
else Color.{ 80, 255, 160, 255 };
DrawCircleLines(tn_x, tn_y, xx NODE_RADIUS, border);
label := ifx is_internal then "N" else tprint("%", n.value);
label_c := to_c_string(label);
fs := cast(s32, FONT1_SIZE);
tw := MeasureTextEx(GetFontDefault(), label_c, FONT1_SIZE, 1);
DrawText(
label_c,
xx (tn_x - tw.x / 2),
xx (tn_y - tw.y / 2),
FONT1_SIZE,
WHITE
);
idx_label := to_c_string(tprint("[%]", n.index));
sw := MeasureTextEx(GetFontDefault(), idx_label, FONT2_SIZE, 1);
DrawText(
idx_label,
xx (tn_x - sw.x / 2),
xx (tn_y - (NODE_RADIUS * 2)),
FONT2_SIZE,
{ 180, 180, 180, 180 }
);
}
}
treev_screen_draw :: () {
info := to_c_string(tprint("Nodes %", node_count));
DrawText(
info,
SCREEN_WIDTH - MeasureText(info, 14) - 16,
SCREEN_HEIGHT - 24,
14,
{ 160, 160, 200, 220 }
);
mouse := GetMousePosition();
for i: 0..node_count-1 {
n := nodes[i];
n_screen := GetWorldToScreen2D({ n.x, n.y }, camera);
if CheckCollisionPointCircle(mouse, n_screen, NODE_RADIUS * camera.zoom) {
text := tooltip_text(n);
tooltip(mouse, text);
}
}
}
#scope_file
tree: []int;
tree_size: int;
nodes: [NODES_MAX]Treev_Node;
node_count: int;
NODES_MAX :: 128;
NODE_RADIUS :: 28;
FONT1_SIZE :: 34;
FONT2_SIZE :: 16;
LEVEL_GAP_Y :: 160;
LEVEL_GAP_X :: 2;
PADDING :: 60;
Treev_Node :: struct {
index: int;
value: int;
x, y: float;
depth: int;
}
Range :: struct {
left: float;
right: float;
}
get_depth :: (idx: int) -> int {
d: int;
while idx > 0 {
idx = (idx - 1) / 2;
d += 1;
}
return d;
}
subtree_width :: (idx: int) -> int {
if idx >= tree_size || tree[idx] == NODE_EMPTY then return 0;
return 1 + subtree_width(2 * idx + 1) + subtree_width(2 * idx + 2);
}
assign_positions :: (idx: int, left: float, right: float, depth: int) {
if idx >= tree_size || tree[idx] == NODE_EMPTY return;
cx := (left + right) / 2.0;
cy := 80.0 + depth;
if node_count < NODES_MAX {
nodes[node_count].index = idx;
nodes[node_count].value = tree[idx];
nodes[node_count].x = cx * LEVEL_GAP_X;
nodes[node_count].y = cy * LEVEL_GAP_Y;
nodes[node_count].depth = depth;
node_count += 1;
}
mid := (left + right) / 2.0;
assign_positions(2 * idx + 1, left, mid, depth + 1);
assign_positions(2 * idx + 2, mid, right, depth + 1);
}
find_node :: (idx: int) -> (found: bool, node: Treev_Node) {
for nodes {
if it.index == idx return true, it;
}
return false, {};
}
tooltip_text :: (tvn: Treev_Node) -> string {
node_type: string;
bv_upper: string;
bv_lower: string;
sa_info: string;
if tvn.index == 0 {
node_type = "Root Node";
} else {
if tvn.value == {
case NODE_EMPTY; node_type = "Empty Node";
case NODE_INTERNAL;
node_type = "Internal Node";
case;
node_type = "Child Node";
bv := bvs[tvn.value];
bv_upper = tprint("\nBV Upper Bound: %", bv.upper_bound);
bv_lower = tprint("\nBV Lower Bound: %", bv.lower_bound);
sa := aabb_bv_compute_surface_area(bv);
sa_info = tprint("\nSurface Area: %", sa);
}
}
sb: String_Builder;
print_to_builder(*sb, "Type: %\n", node_type);
print_to_builder(*sb, "Index: %\n", tvn.index);
append(*sb, bv_upper);
append(*sb, bv_lower);
append(*sb, sa_info);
text := builder_to_string(*sb);
return text;
}
tooltip :: (mouse: Vector2, text: string) {
update_text_render :: () #expand {
array_reset_keeping_memory(*`codepoints);
array_reset_keeping_memory(*`offsets);
`rect_padded = rect;
`rect_padded.x += PADDING;
`rect_padded.y += PADDING;
`rect_padded.width -= PADDING;
`text_height = wrap_text(
GetFontDefault(),
to_c_string(`text),
*`codepoints,
*`offsets,
`rect_padded,
`FONT_SIZE,
`SPACING,
`MY_COLOR
);
}
BACKGROUND :: Color.{ 34, 31, 45, 242 };
OFFSET :: Vector2.{ 24.0, 33.0 };
LINES :: Color.{ 99, 90, 122, 240 };
FONT_SIZE :: 20.0;
SPACING :: 4.0;
PADDING :: 16.0;
MY_COLOR :: WHITE;
rect: Rectangle;
rect.x = mouse.x + OFFSET.x;
rect.y = mouse.y + OFFSET.y;
rect.width = #run 14.0 * 34;
rect.height = #run PADDING * 1.5;
codepoints: [..]s32;
offsets: [..]Vector2;
rect_padded: Rectangle;
text_height: float;
update_text_render();
rect.height += text_height;
screen_w := cast(float) GetScreenWidth();
screen_h := cast(float) GetScreenHeight();
if rect.x + rect.width > screen_w
rect.x = mouse.x - OFFSET.x - rect.width;
if rect.y + rect.height > screen_h
rect.y = mouse.y - OFFSET.y - rect.height;
update_text_render();
DrawRectangleRounded(rect, 0.1, 6, BACKGROUND);
DrawRectangleRoundedLinesEx(rect, 0.1, 6, 1.0, LINES);
draw_text(
GetFontDefault(),
codepoints,
offsets,
FONT_SIZE,
SPACING,
MY_COLOR
);
}
/** C R E D I T
Original proc `wrap_text` is from:
- @Raysan (Original Author), https://github.com/raysan5
- @ahmedqarmout2 (Jai Adoption), https://github.com/ahmedqarmout2
*/
wrap_text :: (
font: Font,
text: *u8,
codepoints: *[..]s32,
offsets: *[..]Vector2,
rec: Rectangle,
font_size: float,
spacing: float,
tint: Color,
word_wrap: bool = true
)
-> text_height: float
{
length: s32 = cast(s32)TextLength(text);
text_offset_y: float = 0.0;
text_offset_x: float = 0.0;
scale_factor: float = font_size / cast(float)font.baseSize;
my_enum :: enum { MEASURE_STATE :: 0; DRAW_STATE :: 1; }
state: my_enum = ifx word_wrap then .MEASURE_STATE else .DRAW_STATE;
start_line: s32 = -1; // Index where to begin drawing (where a line begins)
end_line: s32 = -1; // Index where to stop drawing (where a line ends)
lastk: s32 = -1; // Holds last value of the character position
i: s32 = 0;
k: s32 = 0;
while i < length {
defer i += 1;
defer k += 1;
codepoint_byte_count: s32 = 0;
codepoint: s32 = GetCodepoint(*text[i], *codepoint_byte_count);
index: s32 = GetGlyphIndex(font, codepoint);
if codepoint == 0x3f then codepoint_byte_count = 1;
i += (codepoint_byte_count - 1);
glyph_width: float = 0;
if codepoint != #char "\n" {
glyph_width = ifx (font.glyphs[index].advanceX == 0)
then font.recs[index].width * scale_factor
else font.glyphs[index].advanceX * scale_factor;
if (i + 1 < length) glyph_width = glyph_width + spacing;
}
if (state == .MEASURE_STATE) {
if codepoint == #char " "
|| codepoint == #char "\t"
|| codepoint == #char "\n"
then end_line = i;
if text_offset_x + glyph_width > rec.width {
end_line = ifx (end_line < 1) then i else end_line;
if i == end_line then end_line -= codepoint_byte_count;
if (start_line + codepoint_byte_count) == end_line
then end_line = (i - codepoint_byte_count);
state = ifx (state == .MEASURE_STATE) then .DRAW_STATE else .MEASURE_STATE;
}
else if i + 1 == length
{
end_line = i;
state = ifx (state == .MEASURE_STATE) then .DRAW_STATE else .MEASURE_STATE;
}
else if codepoint == #char "\n"
{
state = ifx (state == .MEASURE_STATE) then .DRAW_STATE else .MEASURE_STATE;
}
if state == .DRAW_STATE {
text_offset_x = 0;
i = start_line;
glyph_width = 0;
tmp: s32 = lastk;
lastk = k - 1;
k = tmp;
}
} else {
if codepoint == #char "\n" {
if !word_wrap {
text_offset_y += (font.baseSize + font.baseSize / 2) * scale_factor;
text_offset_x = 0;
}
} else {
if !word_wrap && text_offset_x + glyph_width > rec.width {
text_offset_y += (font.baseSize + font.baseSize / 2) * scale_factor;
text_offset_x = 0;
}
if codepoint != #char " " && codepoint != #char "\t" {
array_add(codepoints, codepoint);
array_add(offsets, { rec.x + text_offset_x, rec.y + text_offset_y });
}
}
if word_wrap && i == end_line {
text_offset_y += (font.baseSize + font.baseSize / 2) * scale_factor;
text_offset_x = 0;
start_line = end_line;
end_line = -1;
glyph_width = 0;
k = lastk;
state = ifx (state == .MEASURE_STATE) then .DRAW_STATE else .MEASURE_STATE;
}
}
if text_offset_x != 0 || codepoint != #char " " then text_offset_x += glyph_width;
}
return text_offset_y;
}
draw_text :: (
font: Font,
codepoints: [..]s32,
offsets: [..]Vector2,
font_size: float,
spacing: float,
tint: Color
) {
assert(codepoints.count == offsets.count);
for codepoints {
x := offsets[it_index].x;
y := offsets[it_index].y;
DrawTextCodepoint(
font,
it,
{ x, y },
font_size,
tint
);
}
}
operator + :: (a: Color, b: Color) -> Color {
c: Color = ---;
c.r = a.r + b.r;
c.g = a.g + b.g;
c.b = a.b + b.b;
c.a = a.a + b.a;
return c;
}