Commits

Daniel K. O. committed f900152

started HashSpace

  • Participants
  • Parent commits c7e75cd

Comments (0)

Files changed (8)

File include/kode/Math.hpp

         }
 
 
+        /// \f$ = \lceil x \rceikl \f$
+        inline
+        Real ceil(Real x) noexcept
+        {
+            return std::ceil(x);
+        }
+
+
         inline
         Real fmod(Real x, Real y) noexcept
         {

File include/kode/collision/Geom.hpp

 #ifndef KODE_GEOM_H
 #define KODE_GEOM_H
 
+#include <cstdint>
+
 #include <kode/SimpleSignal++.hpp> // unmodified local copy
 
 #include <kode/Vector3.hpp>
         Vector3 offsetPosition = {0,0,0};
         Matrix3 offsetLocalAxes = Matrix3::Identity();
 
+        std::uint32_t category = 0xffffffff;
+        std::uint32_t filter   = 0xffffffff;
+
+        bool enabled = true;
 
         void rememberSpace(Space* p) noexcept;
         void forgetSpace() noexcept;
         bool rejectAABB(const AxisAlignedBox& box) const noexcept;
 
         inline
-        const Space* getSpace() const noexcept;
+        std::uint32_t getCategory() const noexcept;
+        inline
+        std::uint32_t setCategory(std::uint32_t cat) noexcept;
 
         inline
-        Space* getSpace() noexcept;
+        std::uint32_t getFilter() const noexcept;
+        inline
+        std::uint32_t setFilter(std::uint32_t fil) noexcept;
 
+        inline
+        bool isEnabled() const noexcept;
+        inline
+        void enable() noexcept;
+        inline
+        void disable() noexcept;
+
+        inline
+        const Space* getSpace() const noexcept;
+        inline
+        Space*       getSpace() noexcept;
 
         inline
         const Body* getBody() const noexcept;
-
         inline
-        Body* getBody() noexcept;
-
+        Body*       getBody() noexcept;
 
         inline
         const Vector3& getPosition() const noexcept;
-
-
         void setPosition(const Vector3& pos) noexcept;
         void setPosition(Real x, Real y, Real z) noexcept;
 
         inline
         Vector3 localPointToWorld(Real x, Real y, Real z) const noexcept;
 
-
         inline
         Vector3 worldPointToLocal(const Vector3& worldPoint) const noexcept;
         inline
         Vector3 worldPointToLocal(Real x, Real y, Real z) const noexcept;
 
-
         inline
         Vector3 localVectorToWorld(const Vector3& localVector) const noexcept;
         inline
         Vector3 localVectorToWorld(Real x, Real y, Real z) const noexcept;
 
-
         inline
         Vector3 worldVectorToLocal(const Vector3& worldVector) const noexcept;
         inline
     /*
      * Implementation of inline methods
      */
+
+    inline
+    std::uint32_t
+    Geom::getCategory() const noexcept
+    {
+        return category;
+    }
+
+
+    inline
+    std::uint32_t
+    Geom::setCategory(std::uint32_t cat) noexcept
+    {
+        std::uint32_t previous = category;
+        category = cat;
+        return previous;
+    }
+
+
+    inline
+    std::uint32_t
+    Geom::getFilter() const noexcept
+    {
+        return filter;
+    }
+
+
+    inline
+    std::uint32_t
+    Geom::setFilter(std::uint32_t fil) noexcept
+    {
+        std::uint32_t previous = filter;
+        filter = fil;
+        return previous;
+    }
+
+
+    inline
+    bool
+    Geom::isEnabled() const noexcept
+    {
+        return enabled;
+    }
+
+
+    inline
+    void
+    Geom::enable() noexcept
+    {
+        enabled = true;
+    }
+
+
+    inline
+    void
+    Geom::disable() noexcept
+    {
+        enabled = false;
+    }
+
+
     inline
     const Space*
     Geom::getSpace() const noexcept

File include/kode/collision/HashSpace.hpp

+/*
+   KODE Physics Library
+   Copyright 2013-2014 Daniel Kohler Osmari
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+*/
+
+#include <kode/collision/Space.hpp>
+
+namespace kode {
+
+    class HashSpace : public Space {
+
+    public:
+
+        void findPairs(const std::function<void(Geom&, Geom&)>& callback) override;
+
+    };
+
+}

File include/kode/collision/Makefile.am

     Collider.hpp \
     ContactPoint.hpp \
     Geom.hpp \
+    HashSpace.hpp \
     Plane.hpp \
     SimpleSpace.hpp \
     Sphere.hpp \

File include/kode/collision/Space.hpp

     class Geom;
 
     class Space {
-        std::vector<Geom*> geoms;
-
         Space* parent = nullptr;
 
     protected:
+        std::vector<Geom*> geoms;
+
         void rememberParent(Space* parent);
         void forgetParent();
 

File src/collision/HashSpace.cpp

+/*
+   KODE Physics Library
+   Copyright 2013-2014 Daniel Kohler Osmari
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+*/
+
+#include <unordered_map>
+#include <cstdint>
+#include <algorithm>
+#include <cmath>
+#include <vector>
+
+#include <kode/collision/HashSpace.hpp>
+
+#include <kode/AxisAlignedBox.hpp>
+#include <kode/collision/Geom.hpp>
+
+namespace kode {
+
+    namespace {
+
+        struct Key {
+            int32_t level;
+            int32_t x, y, z;
+        };
+
+
+        constexpr
+        bool
+        operator==(const Key& a, const Key& b) noexcept
+        {
+            return a.level == b.level
+                && a.x == b.x
+                && a.y == b.y
+                && a.z == b.z;
+        }
+
+
+        // some random prime numbers
+        constexpr uint32_t p1 = 458723501u;
+        constexpr uint32_t p2 = 885211753u;
+        constexpr uint32_t p3 = 2654435789u;
+        constexpr uint32_t p4 = 1785443183u;
+
+        struct Hasher {
+            size_t
+            operator()(const Key& key) const noexcept
+            {
+                std::hash<int32_t> h;
+                return 
+                    p1 * h(key.level) ^
+                    p2 * h(key.x) ^
+                    p3 * h(key.y) ^
+                    p4 * h(key.z);
+            }
+        };
+
+        struct Value {
+            
+            const Geom* geom;
+        };
+
+
+    
+        // return the `level' of an AABB. the AABB will be put into cells at this
+        // level - the cell size will be 2^level. the level is chosen to be the
+        // smallest value such that the AABB occupies no more than 8 cells, regardless
+        // of its placement. this means that:
+        //	size/2 < q <= size
+        // where q is the maximum AABB dimension.
+
+        inline
+        int32_t
+        findLevel (const AxisAlignedBox& box)
+        {
+            if (!box.isFinite())
+                return std::numeric_limits<int32_t>::max();
+
+            const Vector3 size = box.getSize();
+            const Real m = std::max({size.x, size.y, size.z});
+
+            // find level such that 0.5 * 2^level < q <= 2^level
+            int level;
+            std::frexp (m, &level);
+            return level;
+        }
+    }
+
+
+    void
+    HashSpace::findPairs(const std::function<void(Geom&, Geom&)>& callback)
+    {
+        if (geoms.size() < 2)
+            return;
+
+        std::vector<Geom*> big_geoms;
+        std::unordered_map<Key, Value, Hasher> table;
+        for (Geom* g : geoms) {
+            if (!g->isEnabled())
+                continue;
+            
+        }
+    }
+
+
+}

File src/collision/Makefile.am

     Collider.cpp \
     ContactPoint.cpp \
     Geom.cpp \
+    HashSpace.cpp \
     Plane.cpp \
     SimpleSpace.cpp \
     Space.cpp \

File src/collision/SimpleSpace.cpp

     void
     SimpleSpace::findPairs(const std::function<void(Geom&, Geom&)>& callback)
     {
-        std::vector<Geom*>& geoms = getGeoms();
-
         for (size_t i=0; i<geoms.size(); ++i) {
 
             const AxisAlignedBox& abox = geoms[i]->getAABB();