spatial

-module(spatial@bvh).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/spatial/bvh.gleam").
-export(['query'/2, query_radius/3, query_all/1, count/1, bounds/1, from_items/2]).
-export_type([b_v_h/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(
    " Bounding Volume Hierarchy (BVH) for efficient spatial queries.\n"
    "\n"
    " BVH is a tree structure where each node contains a bounding box that\n"
    " encompasses all its children. Excellent for dynamic scenes and collision detection.\n"
).

-opaque b_v_h(JUA) :: {b_v_h_leaf,
        spatial@collider:internal_collider(),
        list({vec@vec3:vec3(float()), JUA})} |
    {b_v_h_node, spatial@collider:internal_collider(), b_v_h(JUA), b_v_h(JUA)}.

-file("src/spatial/bvh.gleam", 52).
-spec do_query(
    b_v_h(JUL),
    spatial@collider:internal_collider(),
    list({vec@vec3:vec3(float()), JUL})
) -> list({vec@vec3:vec3(float()), JUL}).
do_query(Bvh, Query_bounds, Acc) ->
    case Bvh of
        {b_v_h_leaf, Bounds, Items} ->
            case spatial@collider:intersects(Bounds, Query_bounds) of
                false ->
                    Acc;

                true ->
                    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
                    )
            end;

        {b_v_h_node, Bounds@1, Left, Right} ->
            case spatial@collider:intersects(Bounds@1, Query_bounds) of
                false ->
                    Acc;

                true ->
                    _pipe = Acc,
                    _pipe@1 = do_query(Left, Query_bounds, _pipe),
                    do_query(Right, Query_bounds, _pipe@1)
            end
    end.

-file("src/spatial/bvh.gleam", 48).
?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 BVH.\n"
).
-spec 'query'(b_v_h(JUH), spatial@collider:internal_collider()) -> list({vec@vec3:vec3(float()),
    JUH}).
'query'(Bvh, Query_bounds) ->
    do_query(Bvh, Query_bounds, []).

-file("src/spatial/bvh.gleam", 89).
?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(b_v_h(JUR), vec@vec3:vec3(float()), float()) -> list({vec@vec3:vec3(float()),
    JUR}).
query_radius(Bvh, Center, Radius) ->
    Half_extents = {vec3, Radius, Radius, Radius},
    Query_bounds = spatial@collider:box_from_center(Center, Half_extents),
    _pipe = 'query'(Bvh, Query_bounds),
    gleam@list:filter(
        _pipe,
        fun(Item_pair) ->
            {Pos, _} = Item_pair,
            vec@vec3f:distance(Center, Pos) =< Radius
        end
    ).

-file("src/spatial/bvh.gleam", 111).
-spec do_query_all(b_v_h(JVA), list({vec@vec3:vec3(float()), JVA})) -> list({vec@vec3:vec3(float()),
    JVA}).
do_query_all(Bvh, Acc) ->
    case Bvh of
        {b_v_h_leaf, _, Items} ->
            gleam@list:fold(
                Items,
                Acc,
                fun(Acc_inner, Item) -> [Item | Acc_inner] end
            );

        {b_v_h_node, _, Left, Right} ->
            _pipe = Acc,
            _pipe@1 = do_query_all(Left, _pipe),
            do_query_all(Right, _pipe@1)
    end.

-file("src/spatial/bvh.gleam", 107).
?DOC(
    " Query all items in the BVH.\n"
    "\n"
    " **Time Complexity**: O(n) where n is the total number of items.\n"
).
-spec query_all(b_v_h(JUW)) -> list({vec@vec3:vec3(float()), JUW}).
query_all(Bvh) ->
    do_query_all(Bvh, []).

-file("src/spatial/bvh.gleam", 131).
?DOC(
    " Count total items in the BVH.\n"
    "\n"
    " **Time Complexity**: O(n) where n is the total number of items.\n"
).
-spec count(b_v_h(any())) -> integer().
count(Bvh) ->
    _pipe = query_all(Bvh),
    erlang:length(_pipe).

-file("src/spatial/bvh.gleam", 137).
?DOC(" Get the root bounds of the BVH.\n").
-spec bounds(b_v_h(any())) -> spatial@collider:internal_collider().
bounds(Bvh) ->
    case Bvh of
        {b_v_h_leaf, Bounds, _} ->
            Bounds;

        {b_v_h_node, Bounds@1, _, _} ->
            Bounds@1
    end.

-file("src/spatial/bvh.gleam", 162).
-spec compute_bounds(list({vec@vec3:vec3(float()), any()})) -> spatial@collider:internal_collider().
compute_bounds(Items) ->
    Positions = gleam@list:map(Items, fun(Item) -> erlang:element(1, Item) end),
    Init_min = {vec3, 1.0e10, 1.0e10, 1.0e10},
    Init_max = {vec3, -1.0e10, -1.0e10, -1.0e10},
    {Min, Max} = gleam@list:fold(
        Positions,
        {Init_min, Init_max},
        fun(Acc, Pos) ->
            {Current_min, Current_max} = Acc,
            {{vec3,
                    gleam@float:min(
                        erlang:element(2, Current_min),
                        erlang:element(2, Pos)
                    ),
                    gleam@float:min(
                        erlang:element(3, Current_min),
                        erlang:element(3, Pos)
                    ),
                    gleam@float:min(
                        erlang:element(4, Current_min),
                        erlang:element(4, Pos)
                    )},
                {vec3,
                    gleam@float:max(
                        erlang:element(2, Current_max),
                        erlang:element(2, Pos)
                    ),
                    gleam@float:max(
                        erlang:element(3, Current_max),
                        erlang:element(3, Pos)
                    ),
                    gleam@float:max(
                        erlang:element(4, Current_max),
                        erlang:element(4, Pos)
                    )}}
        end
    ),
    Padding = 0.01,
    spatial@collider:box(
        {vec3,
            erlang:element(2, Min) - Padding,
            erlang:element(3, Min) - Padding,
            erlang:element(4, Min) - Padding},
        {vec3,
            erlang:element(2, Max) + Padding,
            erlang:element(3, Max) + Padding,
            erlang:element(4, Max) + Padding}
    ).

-file("src/spatial/bvh.gleam", 193).
-spec merge_bounds(
    spatial@collider:internal_collider(),
    spatial@collider:internal_collider()
) -> spatial@collider:internal_collider().
merge_bounds(A, B) ->
    {Min_a@1, Max_a@1} = case A of
        {box, Min_a, Max_a} -> {Min_a, Max_a};
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"spatial/bvh"/utf8>>,
                        function => <<"merge_bounds"/utf8>>,
                        line => 194,
                        value => _assert_fail,
                        start => 5411,
                        'end' => 5452,
                        pattern_start => 5422,
                        pattern_end => 5448})
    end,
    {Min_b@1, Max_b@1} = case B of
        {box, Min_b, Max_b} -> {Min_b, Max_b};
        _assert_fail@1 ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"spatial/bvh"/utf8>>,
                        function => <<"merge_bounds"/utf8>>,
                        line => 195,
                        value => _assert_fail@1,
                        start => 5455,
                        'end' => 5496,
                        pattern_start => 5466,
                        pattern_end => 5492})
    end,
    spatial@collider:box(
        {vec3,
            gleam@float:min(
                erlang:element(2, Min_a@1),
                erlang:element(2, Min_b@1)
            ),
            gleam@float:min(
                erlang:element(3, Min_a@1),
                erlang:element(3, Min_b@1)
            ),
            gleam@float:min(
                erlang:element(4, Min_a@1),
                erlang:element(4, Min_b@1)
            )},
        {vec3,
            gleam@float:max(
                erlang:element(2, Max_a@1),
                erlang:element(2, Max_b@1)
            ),
            gleam@float:max(
                erlang:element(3, Max_a@1),
                erlang:element(3, Max_b@1)
            ),
            gleam@float:max(
                erlang:element(4, Max_a@1),
                erlang:element(4, Max_b@1)
            )}
    ).

-file("src/spatial/bvh.gleam", 211).
-spec split_items(list({vec@vec3:vec3(float()), JVS})) -> {list({vec@vec3:vec3(float()),
        JVS}),
    list({vec@vec3:vec3(float()), JVS})}.
split_items(Items) ->
    Bounds = compute_bounds(Items),
    Center = spatial@collider:center(Bounds),
    Size = spatial@collider:size(Bounds),
    Axis = case (erlang:element(2, Size) >= erlang:element(3, Size)) andalso (erlang:element(
        2,
        Size
    )
    >= erlang:element(4, Size)) of
        true ->
            0;

        false ->
            case erlang:element(3, Size) >= erlang:element(4, Size) of
                true ->
                    1;

                false ->
                    2
            end
    end,
    {Left, Right} = gleam@list:partition(
        Items,
        fun(Item) ->
            {Pos, _} = Item,
            case Axis of
                0 ->
                    erlang:element(2, Pos) < erlang:element(2, Center);

                1 ->
                    erlang:element(3, Pos) < erlang:element(3, Center);

                _ ->
                    erlang:element(4, Pos) < erlang:element(4, Center)
            end
        end
    ),
    case {Left, Right} of
        {[], _} ->
            Mid = erlang:length(Items) div 2,
            {gleam@list:take(Items, Mid), gleam@list:drop(Items, Mid)};

        {_, []} ->
            Mid = erlang:length(Items) div 2,
            {gleam@list:take(Items, Mid), gleam@list:drop(Items, Mid)};

        {_, _} ->
            {Left, Right}
    end.

-file("src/spatial/bvh.gleam", 146).
-spec build_bvh(list({vec@vec3:vec3(float()), JVL}), integer()) -> b_v_h(JVL).
build_bvh(Items, Max_leaf_size) ->
    case erlang:length(Items) =< Max_leaf_size of
        true ->
            Bounds = compute_bounds(Items),
            {b_v_h_leaf, Bounds, Items};

        false ->
            {Left_items, Right_items} = split_items(Items),
            Left = build_bvh(Left_items, Max_leaf_size),
            Right = build_bvh(Right_items, Max_leaf_size),
            Bounds@1 = merge_bounds(bounds(Left), bounds(Right)),
            {b_v_h_node, Bounds@1, Left, Right}
    end.

-file("src/spatial/bvh.gleam", 34).
?DOC(
    " Create a new BVH from a list of positioned items.\n"
    "\n"
    " Uses Surface Area Heuristic (SAH) for optimal splits.\n"
    "\n"
    " **Time Complexity**: O(n log n) where n is the number of items.\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " let items = [\n"
    "   #(vec3.Vec3(0.0, 0.0, 0.0), \"item1\"),\n"
    "   #(vec3.Vec3(10.0, 0.0, 0.0), \"item2\"),\n"
    " ]\n"
    " let bvh = bvh.from_items(items, max_leaf_size: 4)\n"
    " ```\n"
).
-spec from_items(list({vec@vec3:vec3(float()), JUC}), integer()) -> {ok,
        b_v_h(JUC)} |
    {error, nil}.
from_items(Items, Max_leaf_size) ->
    case Items of
        [] ->
            {error, nil};

        _ ->
            {ok, build_bvh(Items, Max_leaf_size)}
    end.