0#import "Basic"()(
1 MEMORY_DEBUGGER = MEMORY_DEBUGGER_ENABLED
2);
3#import "Math";
4#import "Print_Vars";
5#import "raylib";
7#load "rect_cut.jai";
8#load "gui.jai";
9#load "input.jai";
10#load "tooltip.jai";
11#load "state.jai";
12#load "vtree.jai";
13#load "htree.jai";
14#load "cells.jai";
18/** Ideas / Todo
20 - Different font
21 - Hot reload a binary dump
22 - Update the binary dump
23 - Generic approach for other types of info data in the tooltip
24 - Smooth zoom (maybe)
25 - Second option for visualizing the tree -> https://en.wikipedia.org/wiki/Hyperbolic_tree
27*/
30rects := Rectangle.[
31 { -200.0, -160.0, 40.0, 45.0 },
32 { -140.0, -100.0, 25.0, 25.0 },
33 { -7.0, 60.0, 70.0, 50.0 },
34 { 55.0, 75.0, 25.0, 25.0 },
35 { -180.0, 40.0, 45.0, 25.0 },
36 { 120.0, 20.0, 9.0, 16.0 },
37 { 10.0, 35.0, 25.0, 15.0 },
38 { -80.0, 100.0, 21.0, 32.0 },
39 { 30.0, -70.0, 9.0, 16.0 },
40];
42tree: [..]int;
43bvs: [..]Aabb;
45mode: Mode;
46gui_feature: Gui_Feature;
47camera: Camera2D;
49frame_time: float;
51mouse_screen: Vector2;
52mouse_world: Vector2;
54color_choice := Color.[
55 ORANGE,
56 YELLOW,
57 GREEN,
58 BLUE,
59];
62NODES_MAX :: 256;
64NODE_ROOT :: -9;
65NODE_INTERNAL :: -7;
66NODE_EMPTY :: -1;
68COLOR_NODE_ROOT :: Color.{ 138, 62, 81, 255 };
69COLOR_NODE_INTERNAL :: Color.{ 30, 60, 120, 255 };
70COLOR_NODE_EMPTY :: #run COLOR_BACKGROUND + { 10, 10, 10, 0 };
71COLOR_NODE_VALUE :: Color.{ 30, 110, 70, 255 };
73COLOR_BACKGROUND :: Color.{ 42, 42, 60, 255 };
74COLOR_HIGHLIGHT0 :: Color.{ 30, 30, 30, 0 };
75COLOR_HIGHLIGHT1 :: Color.{ 70, 70, 70, 0 };
76COLOR_HIGHLIGHT2 :: Color.{ 110, 110, 110, 0 };
77COLOR_CELLS_BORDER :: #run COLOR_BACKGROUND + COLOR_HIGHLIGHT1;
78COLOR_CELLS_BORDER_HIGHLIGHT :: #run COLOR_CELLS_BORDER + COLOR_HIGHLIGHT1;
80DRAW_BV :: true;
82SCREEN_WIDTH :: 1920;
83SCREEN_HEIGHT :: 1080;
86TREE_VIEW :: true;
90Aabb :: struct {
91 upper_bound: Vector2;
92 lower_bound: Vector2;
93}
95Node :: struct {
96 parent: int = NODE_EMPTY;
97 left: int = NODE_EMPTY;
98 right: int = NODE_EMPTY;
99}
101Statistics :: struct {
102 nodes: int;
103 children: int;
104 empty: int;
105 total: int;
106}
109#if true main :: () {
110 #if MEMORY_DEBUGGER_ENABLED defer report_memory_leaks();
112 SetTraceLogLevel(.LOG_NONE);
113 SetConfigFlags(.FLAG_MSAA_4X_HINT);
116 tree_build();
118 tree_copy := array_copy(tree);
119 log_vars(tree_copy);
121 stats_vtree: Statistics;
122 stats_htree: Statistics;
123 stats_cells: Statistics;
125 vtree_init(tree_copy, *stats_vtree);
126 htree_init(tree_copy, *stats_htree);
127 cells_init(tree_copy, *stats_cells);
129 state_cells: State; {
130 using state_cells;
131 id = .CELLS;
132 camera = cells_fit_zoom();
133 }
135 state_htree: State; {
136 using state_htree;
137 id = .HYPER_TREE;
138 camera = htree_fit_zoom();
139 }
141 state_vtree: State; {
142 using state_vtree;
143 id = .TRAD_TREE;
144 camera = vtree_fit_zoom();
145 }
148 state_init(mode, state_vtree, state_htree, state_cells);
149 gui_init();
152 InitWindow(SCREEN_WIDTH, SCREEN_HEIGHT, "Template");
153 defer CloseWindow();
155 SetTargetFPS(60);
157 push_allocator(temp);
158 while !WindowShouldClose() {
159 frame_time = GetFrameTime();
160 mouse_screen = GetMousePosition();
161 mouse_world = GetScreenToWorld2D(mouse_screen, camera);
163 input();
165 BeginDrawing();
166 defer EndDrawing();
168 ClearBackground(COLOR_BACKGROUND);
170 gx: s32;
171 while gx < SCREEN_WIDTH {
172 DrawLine(gx, 0, gx, SCREEN_HEIGHT, { 255, 255, 255, 12 });
173 gx += 40;
174 }
175 gy: s32;
176 while gy < SCREEN_HEIGHT {
177 DrawLine(0, gy, SCREEN_WIDTH, gy, { 255, 255, 255, 12 });
178 gy += 40;
179 }
181 {
182 BeginMode2D(camera);
183 defer EndMode2D();
185 if mode == {
186 case .TRAD_TREE; vtree_draw_2d();
187 case .HYPER_TREE; htree_draw_2d();
188 case .CELLS; cells_draw_2d();
189 }
191 input_draw_selection();
192 }
194 gui_draw_screen();
196 if mode == {
197 case .TRAD_TREE; vtree_draw_screen(*stats_vtree);
198 case .HYPER_TREE; htree_draw_screen(*stats_htree);
199 case .CELLS; cells_draw_screen(*stats_cells);
200 }
202 DrawFPS(10, 10);
203 DrawText(TextFormat("Frame Time: % s", frame_time), 10, 40, 20, WHITE);
204 DrawText(TextFormat("Mouse (World): %", mouse_world), 10, 80, 20, WHITE);
205 DrawText(TextFormat("Mouse (Screen): %", mouse_screen), 10, 120, 20, WHITE);
208 reset_temporary_storage();
209 }
210} else main :: () {
211 log("Offline");
213 tree_build();
215 log("-------------------");
216 log_vars(tree);
217 //! tree_debug_view();
218}
220tree_build :: () {
221 for rects array_add(*bvs, make_aabb(it));
222 log_vars(bvs.count-1);
224 array_add(*tree, NODE_INTERNAL, 0, 1);
226 for i: 2..bvs.count-1 {
227 // Find sibling
228 id := find_best_sibling(i);
229 // log_vars(id);
231 // Insert
232 tree_split_node(id, i);
233 //! log_vars(tree);
236 // Refit
237 }
238}
240tree_split_node :: (index: int, left: int) {
241 i_left, i_right := tree_get_ids(index);
243 while tree.count <= i_right {
244 array_add(*tree, NODE_EMPTY);
245 }
247 tree[i_left] = left;
248 tree[i_right] = tree[index];
249 tree[index] = NODE_INTERNAL;
250 //! tree.data[index] -> refit bv
251}
253find_best_sibling :: (id: int) -> id: int {
254 candidate := bvs[id];
256 best_sa := FLOAT32_INFINITY;
257 best_sibling := -1;
259 for tree {
260 if it == NODE_INTERNAL || it == NODE_EMPTY continue;
262 sa := aabb_get_sa(bvs[it], candidate);
264 if sa < best_sa {
265 best_sa = sa;
266 best_sibling = it_index;
267 }
268 }
270 return best_sibling;
271}
273tree_access_node :: (index: int) -> Node {
274 node: Node;
276 i_left, i_right, i_parent := tree_get_ids(index);
278 for int.[i_left, i_right] {
279 if it > tree.count return node;
280 }
282 left := tree[i_left];
283 right := tree[i_right];
285 node.left = left;
286 node.right = right;
287 node.parent = ifx i_parent < 0 then NODE_INTERNAL else tree[i_parent];
288 return node;
289}
291tree_get_ids :: (index: int) -> (left: int, right: int, parent: int) {
292 i_left := 2 * index + 1;
293 i_right := 2 * index + 2;
294 i_parent := cast(int)floor((index - 1.0) / 2.0);
296 return i_left, i_right, i_parent;
297}
299tree_get_parent_from_id :: (id: int) -> int {
300 //! even == right; odd == left
301 lr := ifx (id % 2 == 0) then 2 else 1;
302 index := (id - lr) / 2;
303 return index;
304}
306/* TODO: check this! */
308//! tree_refit :: (tree: *Tree, index: int) {
309//! while index > 0 {
310//! i_left := 2 * index + 1;
311//! i_right := 2 * index + 2;
312//! i_parent := cast(int)floor((index - 1.0) / 2.0);
314//! // Refit this node to enclose both children
315//! tree.data[index] = aabb_bv_union(
316//! tree.data[i_left],
317//! tree.data[i_right]
318//! );
320//! index = i_parent;
321//! }
323//! // Refit the root (index 0) separately, since the while loop stops before it
324//! i_left := 1;
325//! i_right := 2;
326//! tree.data[0] = aabb_bv_union(
327//! tree.data[i_left],
328//! tree.data[i_right]
329//! );
330//! }
333tree_debug_view :: () {
334 for tree {
335 node := tree_access_node(it_index);
336 if (node.parent == NODE_EMPTY) then continue;
337 log_vars(it_index, node.parent, node.left, node.right);
338 //! log_vars(it, node.parent, bvs[node.left], bvs[node.right]);
339 }
340}
343make_aabb :: (rect: Rectangle) -> Aabb {
344 a: Aabb;
345 a.upper_bound = { rect.x, rect.y };
346 a.lower_bound = { rect.x + rect.width , rect.y + rect.height };
347 return a;
348}
350aabb_draw :: (a: Aabb) {
351 #if !DRAW_BV return;
352 rect := Rectangle.{
353 a.upper_bound.x,
354 a.upper_bound.y,
355 a.lower_bound.x - a.upper_bound.x,
356 a.lower_bound.y - a.upper_bound.y
357 };
358 DrawRectangleLinesEx(rect, 1.0, RED);
359}
361aabb_bv_compute_surface_area :: (a: Aabb) -> float {
362 d := a.upper_bound - a.lower_bound;
363 return 2.0 * (d.x * d.y);
364}
366aabb_bv_union :: (a: Aabb, b: Aabb) -> Aabb {
367 c: Aabb;
368 c.upper_bound = min(a.upper_bound, b.upper_bound);
369 c.lower_bound = max(a.lower_bound, b.lower_bound);
370 return c;
371}
373aabb_get_sa :: (a: Aabb, b: Aabb) -> float {
374 un := aabb_bv_union(a, b);
375 sa := aabb_bv_compute_surface_area(un);
376 return sa;
377}
380operator + :: (a: Color, b: Color) -> Color {
381 c: Color = ---;
382 c.r = clamp(a.r + b.r, 0, U8_MAX);
383 c.g = clamp(a.g + b.g, 0, U8_MAX);
384 c.b = clamp(a.b + b.b, 0, U8_MAX);
385 c.a = clamp(a.a + b.a, 0, U8_MAX);
386 return c;
387}
389operator - :: (a: Color, b: Color) -> Color {
390 c: Color = ---;
391 c.r = clamp(a.r - b.r, 0, U8_MAX);
392 c.g = clamp(a.g - b.g, 0, U8_MAX);
393 c.b = clamp(a.b - b.b, 0, U8_MAX);
394 c.a = clamp(a.a - b.a, 0, U8_MAX);
395 return c;
396}
index : binary-tree
---