diff options
| -rw-r--r-- | editor/tests/raycast-test.cpp | 337 | ||||
| -rw-r--r-- | src/chunk.hpp | 17 | ||||
| -rw-r--r-- | src/collision.hpp | 21 | ||||
| -rw-r--r-- | src/raycast-diag.hpp | 26 | ||||
| -rw-r--r-- | src/raycast.cpp | 321 | ||||
| -rw-r--r-- | src/raycast.hpp | 34 |
6 files changed, 411 insertions, 345 deletions
diff --git a/editor/tests/raycast-test.cpp b/editor/tests/raycast-test.cpp index c814269d..e6799de4 100644 --- a/editor/tests/raycast-test.cpp +++ b/editor/tests/raycast-test.cpp @@ -5,102 +5,18 @@ #include "../imgui-raii.hpp" #include "src/critter.hpp" #include "src/world.hpp" -#include "src/RTree-search.hpp" +#include "src/raycast-diag.hpp" #include <cinttypes> #include <array> #include <vector> -#include <Corrade/Containers/StructuredBindings.h> -#include <Magnum/Math/Functions.h> -#include <Magnum/Math/Vector2.h> #include <Magnum/Math/Color.h> namespace floormat::tests { namespace { -using namespace imgui; - -template<typename T> constexpr inline auto tile_size = Math::Vector2<T>{iTILE_SIZE2}; -template<typename T> constexpr inline auto chunk_size = Math::Vector2<T>{TILE_MAX_DIM} * tile_size<T>; - -using RTree = std::decay_t<decltype(*std::declval<struct chunk>().rtree())>; -using Rect = typename RTree::Rect; - -template<class T> constexpr inline T sign_(auto&& x) { - constexpr auto zero = std::decay_t<decltype(x)>{0}; - return T(x > zero) - T(x < zero); -} - -constexpr Vector2 pt_to_vec(point from, point pt) -{ - auto V = Vector2{}; - V += (Vector2(pt.chunk()) - Vector2(from.chunk())) * chunk_size<float>; - V += (Vector2(pt.local()) - Vector2(from.local())) * tile_size<float>; - V += (Vector2(pt.offset()) - Vector2(from.offset())); - return V; -} - -struct aabb_result -{ - float tmin; - bool result; -}; - -template<typename T> -std::array<uint8_t, 2> ray_aabb_signs(Math::Vector2<T> ray_dir_inv_norm) -{ - bool signs[2]; - for (unsigned d = 0; d < 2; ++d) - signs[d] = std::signbit(ray_dir_inv_norm[d]); - return { signs[0], signs[1] }; -} - -// https://tavianator.com/2022/ray_box_boundary.html -// https://www.researchgate.net/figure/The-slab-method-for-ray-intersection-detection-15_fig3_283515372 -aabb_result ray_aabb_intersection(Vector2 ray_origin, Vector2 ray_dir_inv_norm, - std::array<Vector2, 2> box_minmax, std::array<uint8_t, 2> signs) -{ - using Math::min; - using Math::max; - - float tmin = 0, tmax = 16777216; - - for (unsigned d = 0; d < 2; ++d) - { - auto bmin = box_minmax[signs[d]][d]; - auto bmax = box_minmax[!signs[d]][d]; - float dmin = (bmin - ray_origin[d]) * ray_dir_inv_norm[d]; - float dmax = (bmax - ray_origin[d]) * ray_dir_inv_norm[d]; - - tmin = max(dmin, tmin); - tmax = min(dmax, tmax); - } - - return { tmin, tmin < tmax }; -} - -struct bbox -{ - point center; - Vector2ui size; -}; - -struct diag_s -{ - std::vector<bbox> path{}; - Vector2 V, dir, dir_inv_norm; - Vector2ui size; - //unsigned short_steps, long_steps; - float tmin; -}; - -struct result_s -{ - point from, to, collision; - collision_data collider; - bool has_result : 1 = false, - success : 1 = false; -}; +using namespace floormat::imgui; +using namespace floormat::rc; struct pending_s { @@ -109,52 +25,6 @@ struct pending_s bool exists : 1 = false; }; -struct chunk_neighbors -{ - chunk* array[3][3]; -}; - -auto get_chunk_neighbors(class world& w, chunk_coords_ ch) -{ - chunk_neighbors nbs; - for (int j = 0; j < 3; j++) - for (int i = 0; i < 3; i++) - nbs.array[i][j] = w.at(ch + Vector2i(i - 1, j - 1)); - return nbs; -} - -constexpr Vector2i chunk_offsets[3][3] = { - { - { -chunk_size<int>.x(), -chunk_size<int>.y() }, - { -chunk_size<int>.x(), 0 }, - { -chunk_size<int>.x(), chunk_size<int>.y() }, - }, - { - { 0, -chunk_size<int>.y() }, - { 0, 0 }, - { 0, chunk_size<int>.y() }, - }, - { - { chunk_size<int>.x(), -chunk_size<int>.y() }, - { chunk_size<int>.x(), 0 }, - { chunk_size<int>.x(), chunk_size<int>.y() }, - }, -}; -//static_assert(chunk_offsets[0][0] == Vector2i(-1024, -1024)); -//static_assert(chunk_offsets[2][0] == Vector2i(1024, -1024)); - -template<typename T> -constexpr bool within_chunk_bounds(Math::Vector2<T> p0, Math::Vector2<T> p1) -{ - constexpr auto max_bb_size = Math::Vector2<T>{T{0xff}, T{0xff}}; - constexpr auto half_bb = (max_bb_size + Math::Vector2{T{1}}) / T{2}; - constexpr auto start = -half_bb, end = chunk_size<T> + half_bb; - - return !(start.x() > p1.x() || end.x() < p0.x() || - start.y() > p1.y() || end.y() < p0.y()); -} -template bool within_chunk_bounds<int>(Math::Vector2<int> p0, Math::Vector2<int> p1); - void print_coord(auto&& buf, Vector3i c, Vector2i l, Vector2i p) { std::snprintf(buf, std::size(buf), "(ch %dx%d) <%dx%d> {%dx%d px}", c.x(), c.y(), l.x(), l.y(), p.x(), p.y()); @@ -181,203 +51,11 @@ void do_column(StringView name) ImGui::TableNextColumn(); } -template<bool EnableDiagnostics> -result_s do_raycasting(std::conditional_t<EnableDiagnostics, diag_s*, std::nullptr_t> diag, - app& a, point from, point to, object_id self) -{ - result_s result; - if constexpr(EnableDiagnostics) - fm_assert(diag != nullptr); - fm_assert(from.chunk3().z == to.chunk3().z); - - using Math::max; - using Math::min; - using Math::abs; - using Math::ceil; - - constexpr float eps = 1e-6f; - constexpr float inv_eps = 1/eps; - constexpr int fuzz = 2; - constexpr auto fuzz2 = 0.5f; - - result.has_result = false; - - auto& w = a.main().world(); - auto V = pt_to_vec(from, to); - auto ray_len = V.length(); - auto dir = V.normalized(); - - if (abs(dir.x()) < eps && abs(dir.y()) < eps) [[unlikely]] - dir = {eps, eps}; - - unsigned long_axis, short_axis; - - if (abs(dir.y()) > abs(dir.x())) - { - long_axis = 1; - short_axis = 0; - } - else - { - long_axis = 0; - short_axis = 1; - } - - auto long_len = max(1u, (unsigned)ceil(abs(V[long_axis]))), - short_len = max(1u, (unsigned)ceil(abs(V[short_axis]))); - auto nsteps = 1u; - nsteps = max(nsteps, (short_len+tile_size<unsigned>.x()-1)/tile_size<unsigned>.x()); - nsteps = max(nsteps, (long_len+chunk_size<unsigned>.x()-1)/chunk_size<unsigned>.x()); - auto size_ = Vector2ui{}; - size_[short_axis] = (short_len+nsteps*2-1) / nsteps; - size_[long_axis] = (long_len+nsteps-1) / nsteps; - - auto dir_inv_norm = Vector2( - abs(dir.x()) < eps ? std::copysign(inv_eps, dir.x()) : 1 / dir.x(), - abs(dir.y()) < eps ? std::copysign(inv_eps, dir.y()) : 1 / dir.y() - ); - auto signs = ray_aabb_signs(dir_inv_norm); - - result = { - .from = from, - .to = to, - .collision = {}, - .collider = { - .tag = (uint64_t)collision_type::none, - .pass = (uint64_t)pass_mode::pass, - .data = ((uint64_t)1 << collision_data_BITS)-1, - }, - .has_result = true, - .success = false, - }; - if constexpr(EnableDiagnostics) - { - *diag = { - .V = V, - .dir = dir, - .dir_inv_norm = dir_inv_norm, - .size = size_, - .tmin = 0, - }; - diag->path.clear(); - diag->path.reserve(nsteps+1); - } - - float min_tmin = FLT_MAX; - bool b = true; - - //Debug{} << "------"; - for (unsigned k = 0; b && k <= nsteps; k++) - { - auto pos_ = ceil(abs(V * (float)k/(float)nsteps)); - auto pos = Vector2i{(int)std::copysign(pos_.x(), V.x()), (int)std::copysign(pos_.y(), V.y())}; - auto size = size_; - - if (k == 0) - { - for (auto axis : { long_axis, short_axis }) - { - auto sign = sign_<int>(V[axis]); - pos[axis] += (int)(size[axis]/4) * sign; - size[axis] -= size[axis]/2; - } - } - else if (k == nsteps) - { - constexpr auto add = (tile_size<unsigned>.x()+1)/2, - min_size = tile_size<unsigned>.x() + add; - if (size[long_axis] > min_size) - { - auto sign = sign_<int>(V[long_axis]); - auto off = (int)(size[long_axis]/2) - (int)add; - fm_debug_assert(off >= 0); - pos[long_axis] -= off/2 * sign; - size[long_axis] -= (unsigned)off; - } - } - - pos -= Vector2i(fuzz); - size += Vector2ui(fuzz)*2; - - Vector2 origin; - min_tmin = FLT_MAX; - b = true; - - const auto do_check_collider = [&](uint64_t data, const Rect& r) - { - auto x = std::bit_cast<collision_data>(data); - if (x.data == self || x.pass == (uint64_t)pass_mode::pass) - return; - //Debug{} << "item" << x.data << Vector2(r.m_min[0], r.m_min[1]) << Vector2(r.m_max[0], r.m_max[1]); - auto ret = ray_aabb_intersection(origin, dir_inv_norm, - {{{r.m_min[0]-fuzz2, r.m_min[1]-fuzz2}, - {r.m_max[0]+fuzz2, r.m_max[1]+fuzz2}}}, - signs); - if (!ret.result) - return; - if (ret.tmin > ray_len) [[unlikely]] - return; - if (ret.tmin < min_tmin) [[likely]] - { - min_tmin = ret.tmin; - result.collision = object::normalize_coords(from, Vector2i(dir * min_tmin)); - result.collider = x; - b = false; - } - }; - - auto center = object::normalize_coords(from, pos); - - if constexpr(EnableDiagnostics) - diag->path.push_back(bbox{center, size}); - - auto last_ch = from.chunk3(); - auto nbs = get_chunk_neighbors(w, from.chunk3()); - - if (center.chunk3() != last_ch) [[unlikely]] - { - last_ch = center.chunk3(); - nbs = get_chunk_neighbors(w, center.chunk3()); - } - - auto pt = Vector2i(center.local()) * tile_size<int> + Vector2i(center.offset()); - - for (int i = 0; i < 3; i++) - { - for (int j = 0; j < 3; j++) - { - auto* c = nbs.array[i][j]; - if (!c) - continue; - auto* r = c->rtree(); - auto off = chunk_offsets[i][j]; - auto pt0 = pt - Vector2i(size/2), pt1 = pt0 + Vector2i(size); - auto pt0_ = pt0 - off, pt1_ = pt1 - off; - auto [fmin, fmax] = Math::minmax(Vector2(pt0_)-Vector2(fuzz2), Vector2(pt1_)+Vector2(fuzz2)); - if (!within_chunk_bounds(fmin, fmax)) continue; - auto ch_off = (center.chunk() - from.chunk() + Vector2i(i-1, j-1)) * chunk_size<int>; - origin = Vector2((Vector2i(from.local()) * tile_size<int>) + Vector2i(from.offset()) - ch_off); - //Debug{} << "search" << fmin << fmax << Vector3i(c->coord()); - r->Search(fmin.data(), fmax.data(), [&](uint64_t data, const Rect& r) { - do_check_collider(data, r); - return true; - }); - } - } - } - if constexpr(EnableDiagnostics) - diag->tmin = b ? 0 : min_tmin; - result.success = b; - return result; -} - -} // namespace - struct raycast_test : base_test { - result_s result; + raycast_result_s result; pending_s pending; - diag_s diag; + raycast_diag_s diag; ~raycast_test() noexcept override; @@ -400,7 +78,6 @@ struct raycast_test : base_test return true; } } - return false; } @@ -579,13 +256,15 @@ struct raycast_test : base_test fm_warn("raycast: wrong Z value"); return; } - result = do_raycasting<true>(&diag, a, pending.from, pending.to, pending.self); + result = raycast_with_diag(diag, a.main().world(), pending.from, pending.to, pending.self); } } }; raycast_test::~raycast_test() noexcept = default; +} // namespace + Pointer<base_test> tests_data::make_test_raycast() { return Pointer<raycast_test>{InPlaceInit}; } } // namespace floormat::tests diff --git a/src/chunk.hpp b/src/chunk.hpp index 6833ab03..75fe4bc7 100644 --- a/src/chunk.hpp +++ b/src/chunk.hpp @@ -5,6 +5,7 @@ #include "src/RTree-fwd.h" #include "global-coords.hpp" #include "wall-defs.hpp" +#include "collision.hpp" #include <type_traits> #include <array> #include <Corrade/Containers/Array.h> @@ -20,22 +21,6 @@ struct object_proto; class tile_iterator; class tile_const_iterator; -enum class collision : unsigned char { - view, shoot, move, -}; - -enum class collision_type : unsigned char { - none, object, scenery, geometry, -}; - -constexpr inline size_t collision_data_BITS = 60; - -struct collision_data final { - uint64_t tag : 2; - uint64_t pass : 2; - uint64_t data : collision_data_BITS; -}; - struct chunk final { friend struct tile_ref; diff --git a/src/collision.hpp b/src/collision.hpp new file mode 100644 index 00000000..e5605f4e --- /dev/null +++ b/src/collision.hpp @@ -0,0 +1,21 @@ +#pragma once + +namespace floormat { + +enum class collision : unsigned char { + view, shoot, move, +}; + +enum class collision_type : unsigned char { + none, object, scenery, geometry, +}; + +constexpr inline size_t collision_data_BITS = 60; + +struct collision_data final { + uint64_t tag : 2; + uint64_t pass : 2; + uint64_t data : collision_data_BITS; +}; + +} // namespace floormat diff --git a/src/raycast-diag.hpp b/src/raycast-diag.hpp new file mode 100644 index 00000000..12d027bb --- /dev/null +++ b/src/raycast-diag.hpp @@ -0,0 +1,26 @@ +#pragma once +#include "raycast.hpp" +#include <Corrade/Containers/Array.h> + +namespace floormat::detail_rc { + +struct bbox +{ + point center; + Vector2ui size; +}; + +} // namespace floormat::detail_rc + +namespace floormat::rc { + +struct raycast_diag_s +{ + Array<floormat::detail_rc::bbox> path{}; + Vector2 V, dir, dir_inv_norm; + Vector2ui size; + //unsigned short_steps, long_steps; + float tmin; +}; + +} // namespace floormat::rc diff --git a/src/raycast.cpp b/src/raycast.cpp new file mode 100644 index 00000000..bdd348fb --- /dev/null +++ b/src/raycast.cpp @@ -0,0 +1,321 @@ +#include "raycast-diag.hpp" +#include "pass-mode.hpp" +#include "src/world.hpp" +#include "src/object.hpp" +#include "src/RTree-search.hpp" +#include <float.h> +#include <Corrade/Containers/StructuredBindings.h> +#include <Corrade/Containers/GrowableArray.h> +#include <Magnum/Math/Functions.h> +#include <Magnum/Math/Vector2.h> + +namespace floormat::rc { + +namespace { + +template<typename T> constexpr inline auto tile_size = Math::Vector2<T>{iTILE_SIZE2}; +template<typename T> constexpr inline auto chunk_size = Math::Vector2<T>{TILE_MAX_DIM} * tile_size<T>; + +using floormat::detail_rc::bbox; +using RTree = std::decay_t<decltype(*std::declval<struct chunk>().rtree())>; +using Rect = typename RTree::Rect; + +template<class T> constexpr inline T sign_(auto&& x) { + constexpr auto zero = std::decay_t<decltype(x)>{0}; + return T(x > zero) - T(x < zero); +} + +constexpr Vector2 pt_to_vec(point from, point pt) +{ + auto V = Vector2{}; + V += (Vector2(pt.chunk()) - Vector2(from.chunk())) * chunk_size<float>; + V += (Vector2(pt.local()) - Vector2(from.local())) * tile_size<float>; + V += (Vector2(pt.offset()) - Vector2(from.offset())); + return V; +} + +struct aabb_result +{ + float tmin; + bool result; +}; + +template<typename T> +std::array<uint8_t, 2> ray_aabb_signs(Math::Vector2<T> ray_dir_inv_norm) +{ + bool signs[2]; + for (unsigned d = 0; d < 2; ++d) + signs[d] = std::signbit(ray_dir_inv_norm[d]); + return { signs[0], signs[1] }; +} + +// https://tavianator.com/2022/ray_box_boundary.html +// https://www.researchgate.net/figure/The-slab-method-for-ray-intersection-detection-15_fig3_283515372 +aabb_result ray_aabb_intersection(Vector2 ray_origin, Vector2 ray_dir_inv_norm, + std::array<Vector2, 2> box_minmax, std::array<uint8_t, 2> signs) +{ + using Math::min; + using Math::max; + + float tmin = 0, tmax = 16777216; + + for (unsigned d = 0; d < 2; ++d) + { + auto bmin = box_minmax[signs[d]][d]; + auto bmax = box_minmax[!signs[d]][d]; + float dmin = (bmin - ray_origin[d]) * ray_dir_inv_norm[d]; + float dmax = (bmax - ray_origin[d]) * ray_dir_inv_norm[d]; + + tmin = max(dmin, tmin); + tmax = min(dmax, tmax); + } + + return { tmin, tmin < tmax }; +} + +struct chunk_neighbors +{ + chunk* array[3][3]; +}; + +auto get_chunk_neighbors(class world& w, chunk_coords_ ch) +{ + chunk_neighbors nbs; + for (int j = 0; j < 3; j++) + for (int i = 0; i < 3; i++) + nbs.array[i][j] = w.at(ch + Vector2i(i - 1, j - 1)); + return nbs; +} + +constexpr Vector2i chunk_offsets[3][3] = { + { + { -chunk_size<int>.x(), -chunk_size<int>.y() }, + { -chunk_size<int>.x(), 0 }, + { -chunk_size<int>.x(), chunk_size<int>.y() }, + }, + { + { 0, -chunk_size<int>.y() }, + { 0, 0 }, + { 0, chunk_size<int>.y() }, + }, + { + { chunk_size<int>.x(), -chunk_size<int>.y() }, + { chunk_size<int>.x(), 0 }, + { chunk_size<int>.x(), chunk_size<int>.y() }, + }, +}; +//static_assert(chunk_offsets[0][0] == Vector2i(-1024, -1024)); +//static_assert(chunk_offsets[2][0] == Vector2i(1024, -1024)); + +template<typename T> +constexpr bool within_chunk_bounds(Math::Vector2<T> p0, Math::Vector2<T> p1) +{ + constexpr auto max_bb_size = Math::Vector2<T>{T{0xff}, T{0xff}}; + constexpr auto half_bb = (max_bb_size + Math::Vector2{T{1}}) / T{2}; + constexpr auto start = -half_bb, end = chunk_size<T> + half_bb; + + return !(start.x() > p1.x() || end.x() < p0.x() || + start.y() > p1.y() || end.y() < p0.y()); +} +template bool within_chunk_bounds<int>(Math::Vector2<int> p0, Math::Vector2<int> p1); + +template<bool EnableDiagnostics> +raycast_result_s do_raycasting(std::conditional_t<EnableDiagnostics, raycast_diag_s&, std::nullptr_t> diag, + world& w, point from, point to, object_id self) +{ + raycast_result_s result; + fm_assert(from.chunk3().z == to.chunk3().z); + + using Math::max; + using Math::min; + using Math::abs; + using Math::ceil; + + constexpr float eps = 1e-6f; + constexpr float inv_eps = 1/eps; + constexpr int fuzz = 2; + constexpr auto fuzz2 = 0.5f; + + result.has_result = false; + + auto V = pt_to_vec(from, to); + auto ray_len = V.length(); + auto dir = V.normalized(); + + if (abs(dir.x()) < eps && abs(dir.y()) < eps) [[unlikely]] + dir = {eps, eps}; + + unsigned long_axis, short_axis; + + if (abs(dir.y()) > abs(dir.x())) + { + long_axis = 1; + short_axis = 0; + } + else + { + long_axis = 0; + short_axis = 1; + } + + auto long_len = max(1u, (unsigned)ceil(abs(V[long_axis]))), + short_len = max(1u, (unsigned)ceil(abs(V[short_axis]))); + auto nsteps = 1u; + nsteps = max(nsteps, (short_len+tile_size<unsigned>.x()-1)/tile_size<unsigned>.x()); + nsteps = max(nsteps, (long_len+chunk_size<unsigned>.x()-1)/chunk_size<unsigned>.x()); + auto size_ = Vector2ui{}; + size_[short_axis] = (short_len+nsteps*2-1) / nsteps; + size_[long_axis] = (long_len+nsteps-1) / nsteps; + + auto dir_inv_norm = Vector2( + abs(dir.x()) < eps ? std::copysign(inv_eps, dir.x()) : 1 / dir.x(), + abs(dir.y()) < eps ? std::copysign(inv_eps, dir.y()) : 1 / dir.y() + ); + auto signs = ray_aabb_signs(dir_inv_norm); + + result = { + .from = from, + .to = to, + .collision = {}, + .collider = { + .tag = (uint64_t)collision_type::none, + .pass = (uint64_t)pass_mode::pass, + .data = ((uint64_t)1 << collision_data_BITS)-1, + }, + .has_result = true, + .success = false, + }; + if constexpr(EnableDiagnostics) + { + diag = { + .V = V, + .dir = dir, + .dir_inv_norm = dir_inv_norm, + .size = size_, + .tmin = 0, + }; + arrayResize(diag.path, 0); + arrayReserve(diag.path, nsteps+1); + } + + float min_tmin = FLT_MAX; + bool b = true; + + //Debug{} << "------"; + for (unsigned k = 0; b && k <= nsteps; k++) + { + auto pos_ = ceil(abs(V * (float)k/(float)nsteps)); + auto pos = Vector2i{(int)std::copysign(pos_.x(), V.x()), (int)std::copysign(pos_.y(), V.y())}; + auto size = size_; + + if (k == 0) + { + for (auto axis : { long_axis, short_axis }) + { + auto sign = sign_<int>(V[axis]); + pos[axis] += (int)(size[axis]/4) * sign; + size[axis] -= size[axis]/2; + } + } + else if (k == nsteps) + { + constexpr auto add = (tile_size<unsigned>.x()+1)/2, + min_size = tile_size<unsigned>.x() + add; + if (size[long_axis] > min_size) + { + auto sign = sign_<int>(V[long_axis]); + auto off = (int)(size[long_axis]/2) - (int)add; + fm_debug_assert(off >= 0); + pos[long_axis] -= off/2 * sign; + size[long_axis] -= (unsigned)off; + } + } + + pos -= Vector2i(fuzz); + size += Vector2ui(fuzz)*2; + + Vector2 origin; + min_tmin = FLT_MAX; + b = true; + + const auto do_check_collider = [&](uint64_t data, const Rect& r) + { + auto x = std::bit_cast<collision_data>(data); + if (x.data == self || x.pass == (uint64_t)pass_mode::pass) + return; + //Debug{} << "item" << x.data << Vector2(r.m_min[0], r.m_min[1]) << Vector2(r.m_max[0], r.m_max[1]); + auto ret = ray_aabb_intersection(origin, dir_inv_norm, + {{{r.m_min[0]-fuzz2, r.m_min[1]-fuzz2}, + {r.m_max[0]+fuzz2, r.m_max[1]+fuzz2}}}, + signs); + if (!ret.result) + return; + if (ret.tmin > ray_len) [[unlikely]] + return; + if (ret.tmin < min_tmin) [[likely]] + { + min_tmin = ret.tmin; + result.collision = object::normalize_coords(from, Vector2i(dir * min_tmin)); + result.collider = x; + b = false; + } + }; + + auto center = object::normalize_coords(from, pos); + + if constexpr(EnableDiagnostics) + arrayAppend(diag.path, bbox{center, size}); + + auto last_ch = from.chunk3(); + auto nbs = get_chunk_neighbors(w, from.chunk3()); + + if (center.chunk3() != last_ch) [[unlikely]] + { + last_ch = center.chunk3(); + nbs = get_chunk_neighbors(w, center.chunk3()); + } + + auto pt = Vector2i(center.local()) * tile_size<int> + Vector2i(center.offset()); + + for (int i = 0; i < 3; i++) + { + for (int j = 0; j < 3; j++) + { + auto* c = nbs.array[i][j]; + if (!c) + continue; + auto* r = c->rtree(); + auto off = chunk_offsets[i][j]; + auto pt0 = pt - Vector2i(size/2), pt1 = pt0 + Vector2i(size); + auto pt0_ = pt0 - off, pt1_ = pt1 - off; + auto [fmin, fmax] = Math::minmax(Vector2(pt0_)-Vector2(fuzz2), Vector2(pt1_)+Vector2(fuzz2)); + if (!within_chunk_bounds(fmin, fmax)) continue; + auto ch_off = (center.chunk() - from.chunk() + Vector2i(i-1, j-1)) * chunk_size<int>; + origin = Vector2((Vector2i(from.local()) * tile_size<int>) + Vector2i(from.offset()) - ch_off); + //Debug{} << "search" << fmin << fmax << Vector3i(c->coord()); + r->Search(fmin.data(), fmax.data(), [&](uint64_t data, const Rect& r) { + do_check_collider(data, r); + return true; + }); + } + } + } + if constexpr(EnableDiagnostics) + diag.tmin = b ? 0 : min_tmin; + result.success = b; + return result; +} + +} // namespace + +raycast_result_s raycast(world& w, point from, point to, object_id self) +{ + return do_raycasting<false>(nullptr, w, from, to, self); +} + +raycast_result_s raycast_with_diag(raycast_diag_s& diag, world& w, point from, point to, object_id self) +{ + return do_raycasting<true>(diag, w, from, to, self); +} + +} // namespace floormat::rc diff --git a/src/raycast.hpp b/src/raycast.hpp new file mode 100644 index 00000000..acdddd33 --- /dev/null +++ b/src/raycast.hpp @@ -0,0 +1,34 @@ +#pragma once +#include "src/object-id.hpp" +#include "src/collision.hpp" +#include "src/point.hpp" + +namespace floormat { + +class world; + +} // namespace floormat + +namespace floormat::rc { + +struct raycast_diag_s; + +struct raycast_result_s +{ + point from, to, collision; + collision_data collider; + bool has_result : 1 = false, + success : 1 = false; +}; + +[[nodiscard]] raycast_result_s raycast(world& w, point from, point to, object_id self); +[[nodiscard]] raycast_result_s raycast_with_diag(raycast_diag_s& diag, world& w, point from, point to, object_id self); + +} // namespace floormat::rc + +namespace floormat { + +using floormat::rc::raycast; +using floormat::rc::raycast_with_diag; + +} // namespace floormat |