Manual: Spaces

From KODE Wiki
Jump to: navigation, search
This article is part
of the KODE Manual
Install and Use
Quick Tutorial
API Reference

Spaces keep track of a collection of geoms to perform efficient broad-phase collision detection. The broad-phase tests take only the axis-aligned bounding boxes into consideration.


The Space class is the base for all other spaces.

class Space {
    // ...

    enum class Type {

    Type getType() const noexcept;

    Space() = default;
    virtual ~Space() noexcept;

    Space(const Space& other) = delete;
    Space& operator=(const Space& other) = delete;

    std::uint32_t getCategory() const noexcept;
    void setCategory(std::uint32_t cat) noexcept;

    std::uint32_t getFilter() const noexcept;
    void setFilter(std::uint32_t fil) noexcept;

    virtual void add(Geom& g);
    virtual void remove(Geom& g);

    void add(Space& child);
    void remove(Space& child);

    const Space* getParent() const noexcept;
          Space* getParent()       noexcept;

    const std::vector<Geom*>& getGeoms() const noexcept;
          std::vector<Geom*>& getGeoms()       noexcept;

    const std::vector<Space*>& getChildren() const noexcept;
          std::vector<Space*>& getChildren()       noexcept;

    // ...

Note that spaces are not copyable.

Like geoms, spaces can have collision categories and filters to avoid generating collisions between unwanted pairs.

Note: DO NOT modify the vectors returned by getGeoms() and getChildren().

Collision Queries[edit]

class Space {
    // ...

    virtual void findPairs(const std::function<void(Geom&,Geom&)>& callback);

    virtual void findPairs(Geom& g, const std::function<void(Geom&,Geom&)>& callback);

    virtual void findPairs(Space& s, const std::function<void(Geom&,Geom&)>& callback);

    // ...

The callable object (function pointer, functor or lambda) object callbackwill be invoked for each pair of potentially colliding geoms.

  • The first form check all possible collisions that might exist inside a space.
  • The second form tests its own geoms (and its nested spaces' geoms) against the argument.
  • The third form tests its own geoms (and its nested spaces' geoms) against the argument.

Note that broad-phase collision tests involving different spaces might not be as fast as having everything inside a single space.


class HashSpace : public Space {
    // ...

    void setLimits(int min, int max);
    std::pair<int,int> getLimits() const noexcept; // default: -3, 20

    // ...

The HashSpace class implements spatial hashing to find colliding pairs of geoms.

The implicit multi-resolution grid has cells sized from 2^\text{min} to 2^\text{max}, where min and max are the limits set by calling setLimits().

Note: do not set the low limit to less than \log_2 \text{maxDist} - 31 (where maxDist is the maximum distance an object will be from the origin), otherwise the grid coordinates might overflow and collisions will be missed altogether.

This space is particularly effective when most geoms are moving.


class QuadTreeSpace : public Space {
    // ...
    enum class Split { XY, XZ, ZY };

    QuadTreeSpace(Split m);

     // other methods not yet implemented

    // ..

The QuadTree class implements a quadtree.


Not yet implemented.


class SimpleSpace : public Space {
    // nothing special

The SimpleSpace class implements a quadratic pairwise test: every geom is tested against every other. This space is faster than any spatial data structure when there are too few geoms (typically up to 32 or 64 geoms).