From 242b87a5fb412f9006e4b7debc1408cf7ac83000 Mon Sep 17 00:00:00 2001 From: Daniel Karbach Date: Tue, 5 Jan 2016 12:44:57 +0100 Subject: [PATCH] improved ray/world collision a little --- src/geometry/primitive.hpp | 14 +++++++++++++ src/world/Chunk.hpp | 5 ++++- src/world/chunk.cpp | 10 ++++++++- src/world/world.cpp | 43 +++++++++++++++++++++++++++++--------- 4 files changed, 60 insertions(+), 12 deletions(-) diff --git a/src/geometry/primitive.hpp b/src/geometry/primitive.hpp index 72da847..b9f2187 100644 --- a/src/geometry/primitive.hpp +++ b/src/geometry/primitive.hpp @@ -4,6 +4,7 @@ #include #include #include +#include namespace blank { @@ -42,6 +43,19 @@ struct Ray { void Update() noexcept { inv_dir = 1.0f / dir; } + + /// get shortest distance of this ray's line to given point + float Distance(const glm::vec3 &point) const noexcept { + // d = |(x2-x1)×(x1-x0)|/|x2-x1| + // where x0 is point, and x1 and x2 are points on the line + // for derivation, see http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html + // x1 = orig + // x2-x1 = dir, which means |x2-x1| is 1.0 + return length(cross(dir, orig - point)); + } + float DistanceSquared(const glm::vec3 &point) const noexcept { + return length2(cross(dir, orig - point)); + } }; std::ostream &operator <<(std::ostream &, const Ray &); diff --git a/src/world/Chunk.hpp b/src/world/Chunk.hpp index 045f58d..6779414 100644 --- a/src/world/Chunk.hpp +++ b/src/world/Chunk.hpp @@ -144,6 +144,8 @@ public: /// get gravity for one unit mass at given point glm::vec3 GravityAt(const ExactLocation &) const noexcept; + /// check if given ray passes this chunk at all + /// given reference indicates the chunk offset of the ray in world space bool Intersection( const Ray &ray, const ExactLocation::Coarse &reference, @@ -153,12 +155,13 @@ public: } /// check if given ray intersects any block of this chunk - /// given reference indicated the chunk offset of the ray in world space + /// given reference indicates the chunk offset of the ray in world space bool Intersection( const Ray &, const ExactLocation::Coarse &reference, WorldCollision &) noexcept; + /// get all blocks intersecting given box bool Intersection( const AABB &box, const glm::mat4 &Mbox, diff --git a/src/world/chunk.cpp b/src/world/chunk.cpp index 596bcaf..97ec3e3 100644 --- a/src/world/chunk.cpp +++ b/src/world/chunk.cpp @@ -415,9 +415,17 @@ bool Chunk::Intersection( if (!type.collision || !type.shape) { continue; } + RoughLocation::Fine pos(x, y, z); + + // center of the blok relative to the ray + glm::vec3 relative_center(glm::vec3((position - reference) * ExactLocation::Extent() + pos) + 0.5f); + if (ray.DistanceSquared(relative_center) > 3.0f) { + continue; + } + float cur_dist; glm::vec3 cur_norm; - if (type.shape->Intersects(ray, ToTransform(reference, RoughLocation::Fine(x, y, z), idx), cur_dist, cur_norm)) { + if (type.shape->Intersects(ray, ToTransform(reference, pos, idx), cur_dist, cur_norm)) { if (cur_dist < coll.depth) { coll.block = idx; coll.depth = cur_dist; diff --git a/src/world/world.cpp b/src/world/world.cpp index b9d9db7..a12d86e 100644 --- a/src/world/world.cpp +++ b/src/world/world.cpp @@ -784,7 +784,7 @@ bool World::Intersection( const ExactLocation::Coarse &reference, WorldCollision &coll ) { - // only consider chunks of the idex closest to reference + // only consider chunks of the index closest to reference // this makes the ray not be infinite anymore (which means it's // actually a line segment), but oh well ChunkIndex *index = chunks.ClosestIndex(reference); @@ -794,15 +794,38 @@ bool World::Intersection( candidates.clear(); - // TODO: change this so the test starts at the chunk of the ray's - // origin and "walks" forward until it hits (actually casting - // the ray, so to say). if this performs well (at least, better - // than now), this could also qualify for the chunk test itself - // see Bresenham's line algo or something similar - for (Chunk *cur_chunk : *index) { - float cur_dist; - if (cur_chunk && cur_chunk->Intersection(ray, reference, cur_dist)) { - candidates.push_back({ cur_chunk, cur_dist }); + // maybe worht to try: + // change this so the test starts at the chunk of the ray's + // origin and "walks" forward until it hits (actually casting + // the ray, so to say). if this performs well (at least, better + // than now), this could also qualify for the chunk test itself + // see Bresenham's line algo or something similar + + ExactLocation ray_loc(reference, ray.orig); + ray_loc.Correct(); + + ExactLocation::Coarse begin(index->CoordsBegin()); + ExactLocation::Coarse end(index->CoordsEnd()); + + // ignore chunks that are bind the ray's origin + for (int i = 0; i < 3; ++i) { + if (ray.dir[i] >= 0.0f) { + begin[i] = ray_loc.chunk[i]; + } + if (ray.dir[i] <= 0.0f) { + end[i] = ray_loc.chunk[i] + 1; + } + } + + for (ExactLocation::Coarse pos(begin); pos.z < end.z; ++pos.z) { + for (pos.y = begin.y; pos.y < end.y; ++pos.y) { + for (pos.x = begin.x; pos.x < end.x; ++pos.x) { + Chunk *cur_chunk = index->Get(pos); + float cur_dist; + if (cur_chunk && cur_chunk->Intersection(ray, reference, cur_dist)) { + candidates.push_back({ cur_chunk, cur_dist }); + } + } } } -- 2.39.2