Current section
Files
Jump to
Current section
Files
src/spatial@octree.erl
-module(spatial@octree).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/spatial/octree.gleam").
-export([new/2, 'query'/2, query_radius/3, query_all/1, count/1, bounds/1, remove/3, insert/3]).
-export_type([octree/1, octree_children/1]).
-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.
?MODULEDOC(
" Octree spatial partitioning data structure.\n"
"\n"
" An octree divides 3D space into 8 octants recursively, enabling efficient\n"
" spatial queries for nearby objects.\n"
).
-opaque octree(KXQ) :: {octree_node,
spatial@collider:internal_collider(),
integer(),
list({vec@vec3:vec3(float()), KXQ}),
gleam@option:option(octree_children(KXQ))}.
-type octree_children(KXR) :: {octree_children,
octree(KXR),
octree(KXR),
octree(KXR),
octree(KXR),
octree(KXR),
octree(KXR),
octree(KXR),
octree(KXR)}.
-file("src/spatial/octree.gleam", 54).
?DOC(
" Create a new empty octree.\n"
"\n"
" ## Parameters\n"
" - `bounds`: The spatial region this octree covers (must be a Box)\n"
" - `capacity`: Maximum items per node before subdividing (typically 8-16)\n"
"\n"
" ## Example\n"
" ```gleam\n"
" let bounds = collider.box(\n"
" min: vec3.Vec3(-100.0, -100.0, -100.0),\n"
" max: vec3.Vec3(100.0, 100.0, 100.0),\n"
" )\n"
" let tree = octree.new(bounds, capacity: 8)\n"
" ```\n"
).
-spec new(spatial@collider:internal_collider(), integer()) -> octree(any()).
new(Bounds, Capacity) ->
{octree_node, Bounds, Capacity, [], none}.
-file("src/spatial/octree.gleam", 147).
-spec do_query(
octree(KYG),
spatial@collider:internal_collider(),
list({vec@vec3:vec3(float()), KYG})
) -> list({vec@vec3:vec3(float()), KYG}).
do_query(Tree, Query_bounds, Acc) ->
case Tree of
{octree_node, Bounds, _, Items, Children} ->
case spatial@collider:intersects(Bounds, Query_bounds) of
false ->
Acc;
true ->
Acc@1 = gleam@list:fold(
Items,
Acc,
fun(Acc_inner, Item_pair) ->
{Pos, _} = Item_pair,
case spatial@collider:contains_point(
Query_bounds,
Pos
) of
true ->
[Item_pair | Acc_inner];
false ->
Acc_inner
end
end
),
case Children of
none ->
Acc@1;
{some,
{octree_children,
Bottom_nw,
Bottom_ne,
Bottom_sw,
Bottom_se,
Top_nw,
Top_ne,
Top_sw,
Top_se}} ->
_pipe = Acc@1,
_pipe@1 = do_query(Bottom_nw, Query_bounds, _pipe),
_pipe@2 = do_query(Bottom_ne, Query_bounds, _pipe@1),
_pipe@3 = do_query(Bottom_sw, Query_bounds, _pipe@2),
_pipe@4 = do_query(Bottom_se, Query_bounds, _pipe@3),
_pipe@5 = do_query(Top_nw, Query_bounds, _pipe@4),
_pipe@6 = do_query(Top_ne, Query_bounds, _pipe@5),
_pipe@7 = do_query(Top_sw, Query_bounds, _pipe@6),
do_query(Top_se, Query_bounds, _pipe@7)
end
end
end.
-file("src/spatial/octree.gleam", 143).
?DOC(
" Query all items within a collider region.\n"
"\n"
" **Time Complexity**: O(log n + k) average case where k is the number of results.\n"
" Worst case O(n) if query region covers entire tree.\n"
).
-spec 'query'(octree(KYC), spatial@collider:internal_collider()) -> list({vec@vec3:vec3(float()),
KYC}).
'query'(Tree, Query_bounds) ->
do_query(Tree, Query_bounds, []).
-file("src/spatial/octree.gleam", 199).
?DOC(
" Query all items within a radius of a point.\n"
"\n"
" **Time Complexity**: O(log n + k) average case where k is the number of results.\n"
).
-spec query_radius(octree(KYM), vec@vec3:vec3(float()), float()) -> list({vec@vec3:vec3(float()),
KYM}).
query_radius(Tree, Center, Radius) ->
Half_extents = {vec3, Radius, Radius, Radius},
Query_bounds = spatial@collider:box_from_center(Center, Half_extents),
Radius_sq = Radius * Radius,
_pipe = 'query'(Tree, Query_bounds),
gleam@list:filter(
_pipe,
fun(Item_pair) ->
{Pos, _} = Item_pair,
spatial_ffi:distance_squared(Center, Pos) =< Radius_sq
end
).
-file("src/spatial/octree.gleam", 224).
-spec do_query_all(octree(KYV), list({vec@vec3:vec3(float()), KYV})) -> list({vec@vec3:vec3(float()),
KYV}).
do_query_all(Tree, Acc) ->
case Tree of
{octree_node, _, _, Items, Children} ->
Acc@1 = gleam@list:fold(
Items,
Acc,
fun(Acc_inner, Item) -> [Item | Acc_inner] end
),
case Children of
none ->
Acc@1;
{some,
{octree_children,
Bottom_nw,
Bottom_ne,
Bottom_sw,
Bottom_se,
Top_nw,
Top_ne,
Top_sw,
Top_se}} ->
_pipe = Acc@1,
_pipe@1 = do_query_all(Bottom_nw, _pipe),
_pipe@2 = do_query_all(Bottom_ne, _pipe@1),
_pipe@3 = do_query_all(Bottom_sw, _pipe@2),
_pipe@4 = do_query_all(Bottom_se, _pipe@3),
_pipe@5 = do_query_all(Top_nw, _pipe@4),
_pipe@6 = do_query_all(Top_ne, _pipe@5),
_pipe@7 = do_query_all(Top_sw, _pipe@6),
do_query_all(Top_se, _pipe@7)
end
end.
-file("src/spatial/octree.gleam", 220).
?DOC(
" Query all items in the octree (useful for iteration).\n"
"\n"
" **Time Complexity**: O(n) where n is the total number of items.\n"
).
-spec query_all(octree(KYR)) -> list({vec@vec3:vec3(float()), KYR}).
query_all(Tree) ->
do_query_all(Tree, []).
-file("src/spatial/octree.gleam", 263).
?DOC(
" Count total items in the octree.\n"
"\n"
" **Time Complexity**: O(n) where n is the total number of items.\n"
).
-spec count(octree(any())) -> integer().
count(Tree) ->
_pipe = query_all(Tree),
erlang:length(_pipe).
-file("src/spatial/octree.gleam", 269).
?DOC(" Get the bounds of the octree.\n").
-spec bounds(octree(any())) -> spatial@collider:internal_collider().
bounds(Tree) ->
case Tree of
{octree_node, Bounds, _, _, _} ->
Bounds
end.
-file("src/spatial/octree.gleam", 277).
-spec subdivide(octree(KZF)) -> octree(KZF).
subdivide(Tree) ->
case Tree of
{octree_node, Bounds, Capacity, _, _} ->
{Min@1, Max@1} = case Bounds of
{box, Min, Max} -> {Min, Max};
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"spatial/octree"/utf8>>,
function => <<"subdivide"/utf8>>,
line => 281,
value => _assert_fail,
start => 8401,
'end' => 8443,
pattern_start => 8412,
pattern_end => 8434})
end,
Center = spatial@collider:center(Bounds),
Bottom_nw = new(
{box,
Min@1,
{vec3,
erlang:element(2, Center),
erlang:element(3, Center),
erlang:element(4, Center)}},
Capacity
),
Bottom_ne = new(
{box,
{vec3,
erlang:element(2, Center),
erlang:element(3, Min@1),
erlang:element(4, Min@1)},
{vec3,
erlang:element(2, Max@1),
erlang:element(3, Center),
erlang:element(4, Center)}},
Capacity
),
Bottom_sw = new(
{box,
{vec3,
erlang:element(2, Min@1),
erlang:element(3, Min@1),
erlang:element(4, Center)},
{vec3,
erlang:element(2, Center),
erlang:element(3, Center),
erlang:element(4, Max@1)}},
Capacity
),
Bottom_se = new(
{box,
{vec3,
erlang:element(2, Center),
erlang:element(3, Min@1),
erlang:element(4, Center)},
{vec3,
erlang:element(2, Max@1),
erlang:element(3, Center),
erlang:element(4, Max@1)}},
Capacity
),
Top_nw = new(
{box,
{vec3,
erlang:element(2, Min@1),
erlang:element(3, Center),
erlang:element(4, Min@1)},
{vec3,
erlang:element(2, Center),
erlang:element(3, Max@1),
erlang:element(4, Center)}},
Capacity
),
Top_ne = new(
{box,
{vec3,
erlang:element(2, Center),
erlang:element(3, Center),
erlang:element(4, Min@1)},
{vec3,
erlang:element(2, Max@1),
erlang:element(3, Max@1),
erlang:element(4, Center)}},
Capacity
),
Top_sw = new(
{box,
{vec3,
erlang:element(2, Min@1),
erlang:element(3, Center),
erlang:element(4, Center)},
{vec3,
erlang:element(2, Center),
erlang:element(3, Max@1),
erlang:element(4, Max@1)}},
Capacity
),
Top_se = new({box, Center, Max@1}, Capacity),
{octree_node,
Bounds,
Capacity,
[],
{some,
{octree_children,
Bottom_nw,
Bottom_ne,
Bottom_sw,
Bottom_se,
Top_nw,
Top_ne,
Top_sw,
Top_se}}}
end.
-file("src/spatial/octree.gleam", 416).
-spec remove_from_child(
spatial@collider:internal_collider(),
octree_children(KZM),
vec@vec3:vec3(float()),
fun((KZM) -> boolean())
) -> octree_children(KZM).
remove_from_child(_, Children, Position, Predicate) ->
case Children of
{octree_children,
Bottom_nw,
Bottom_ne,
Bottom_sw,
Bottom_se,
Top_nw,
Top_ne,
Top_sw,
Top_se} ->
{octree_children,
remove(Bottom_nw, Position, Predicate),
remove(Bottom_ne, Position, Predicate),
remove(Bottom_sw, Position, Predicate),
remove(Bottom_se, Position, Predicate),
remove(Top_nw, Position, Predicate),
remove(Top_ne, Position, Predicate),
remove(Top_sw, Position, Predicate),
remove(Top_se, Position, Predicate)}
end.
-file("src/spatial/octree.gleam", 106).
?DOC(
" Remove an item from the octree.\n"
"\n"
" Removes the first occurrence of an item at the given position.\n"
"\n"
" **Time Complexity**: O(n) worst case as it recursively checks all nodes, \n"
" but typically O(h) where h is the tree height for sparse trees.\n"
).
-spec remove(octree(KXY), vec@vec3:vec3(float()), fun((KXY) -> boolean())) -> octree(KXY).
remove(Tree, Position, Predicate) ->
case Tree of
{octree_node, Bounds, _, Items, Children} ->
case spatial@collider:contains_point(Bounds, Position) of
false ->
Tree;
true ->
New_items = gleam@list:filter(
Items,
fun(Item_pair) ->
{Pos, Item} = Item_pair,
Is_at_position = vec@vec3f:distance(Pos, Position) < 0.0001,
Matches_predicate = Predicate(Item),
not (Is_at_position andalso Matches_predicate)
end
),
New_children = case Children of
none ->
none;
{some, Octants} ->
{some,
remove_from_child(
Bounds,
Octants,
Position,
Predicate
)}
end,
{octree_node,
erlang:element(2, Tree),
erlang:element(3, Tree),
New_items,
New_children}
end
end.
-file("src/spatial/octree.gleam", 359).
-spec insert_into_child(
spatial@collider:internal_collider(),
octree_children(KZI),
vec@vec3:vec3(float()),
KZI
) -> octree_children(KZI).
insert_into_child(Parent_bounds, Children, Position, Item) ->
case Children of
{octree_children,
Bottom_nw,
Bottom_ne,
Bottom_sw,
Bottom_se,
Top_nw,
Top_ne,
Top_sw,
Top_se} ->
Center = spatial@collider:center(Parent_bounds),
case {erlang:element(2, Position) < erlang:element(2, Center),
erlang:element(3, Position) < erlang:element(3, Center),
erlang:element(4, Position) < erlang:element(4, Center)} of
{true, true, true} ->
{octree_children,
insert(Bottom_nw, Position, Item),
erlang:element(3, Children),
erlang:element(4, Children),
erlang:element(5, Children),
erlang:element(6, Children),
erlang:element(7, Children),
erlang:element(8, Children),
erlang:element(9, Children)};
{false, true, true} ->
{octree_children,
erlang:element(2, Children),
insert(Bottom_ne, Position, Item),
erlang:element(4, Children),
erlang:element(5, Children),
erlang:element(6, Children),
erlang:element(7, Children),
erlang:element(8, Children),
erlang:element(9, Children)};
{true, true, false} ->
{octree_children,
erlang:element(2, Children),
erlang:element(3, Children),
insert(Bottom_sw, Position, Item),
erlang:element(5, Children),
erlang:element(6, Children),
erlang:element(7, Children),
erlang:element(8, Children),
erlang:element(9, Children)};
{false, true, false} ->
{octree_children,
erlang:element(2, Children),
erlang:element(3, Children),
erlang:element(4, Children),
insert(Bottom_se, Position, Item),
erlang:element(6, Children),
erlang:element(7, Children),
erlang:element(8, Children),
erlang:element(9, Children)};
{true, false, true} ->
{octree_children,
erlang:element(2, Children),
erlang:element(3, Children),
erlang:element(4, Children),
erlang:element(5, Children),
insert(Top_nw, Position, Item),
erlang:element(7, Children),
erlang:element(8, Children),
erlang:element(9, Children)};
{false, false, true} ->
{octree_children,
erlang:element(2, Children),
erlang:element(3, Children),
erlang:element(4, Children),
erlang:element(5, Children),
erlang:element(6, Children),
insert(Top_ne, Position, Item),
erlang:element(8, Children),
erlang:element(9, Children)};
{true, false, false} ->
{octree_children,
erlang:element(2, Children),
erlang:element(3, Children),
erlang:element(4, Children),
erlang:element(5, Children),
erlang:element(6, Children),
erlang:element(7, Children),
insert(Top_sw, Position, Item),
erlang:element(9, Children)};
{false, false, false} ->
{octree_children,
erlang:element(2, Children),
erlang:element(3, Children),
erlang:element(4, Children),
erlang:element(5, Children),
erlang:element(6, Children),
erlang:element(7, Children),
erlang:element(8, Children),
insert(Top_se, Position, Item)}
end
end.
-file("src/spatial/octree.gleam", 62).
?DOC(
" Insert an item at a position into the octree.\n"
"\n"
" **Time Complexity**: O(h + c) where h is the tree height (typically O(log n)) \n"
" and c is the node capacity when subdivision occurs. Average case O(log n).\n"
).
-spec insert(octree(KXU), vec@vec3:vec3(float()), KXU) -> octree(KXU).
insert(Tree, Position, Item) ->
case Tree of
{octree_node, Bounds, Capacity, Items, Children} ->
case spatial@collider:contains_point(Bounds, Position) of
false ->
Tree;
true ->
case Children of
none ->
New_items = [{Position, Item} | Items],
case erlang:length(New_items) > Capacity of
false ->
{octree_node,
erlang:element(2, Tree),
erlang:element(3, Tree),
New_items,
erlang:element(5, Tree)};
true ->
Subdivided = subdivide(Tree),
gleam@list:fold(
New_items,
Subdivided,
fun(Acc, Item_pair) ->
{Pos, It} = Item_pair,
insert(Acc, Pos, It)
end
)
end;
{some, Octants} ->
New_children = insert_into_child(
Bounds,
Octants,
Position,
Item
),
{octree_node,
erlang:element(2, Tree),
erlang:element(3, Tree),
erlang:element(4, Tree),
{some, New_children}}
end
end
end.