A library implementing spatial query structures

3d-spaces

# About 3D-Spaces
This library implements a number of spatial query data structures; structures that can answer spatial range queries for optimised lookup, particularly suited for games. Often this is used to implement a "broad phase search".

## How To
The library defines a core protocol which every structure (called a ``container``) must implement. Every container may also expose additional operations or properties, but it is not required to do so. The library //does not// provide any object implementations. Instead it is expected that you implement ``bounding-box`` and ``bounding-sphere`` or ``location``, ``bsize``, and ``radius`` for your objects to describe their bounding volumes, which the containers will then make use of.

The following shows a very basic use:

:: common lisp
(defclass box ()
  ((location :initarg :location :initform (vec 0 0 0) :accessor space:location)
   (bsize :initarg :bsize :initform (vec 0 0 0) :accessor space:bsize)))

(defun box (&optional (location (vec 0 0 0)) (bsize (vec 0 0 0)))
  (make-instance 'box :location location :bsize bsize))

(defvar *bvh2* (org.shirakumo.fraf.trial.space.bvh2:make-bvh))

(space:enter (box (vec 10 10 10) (vec 1 2 3)) *bvh2*)

(space:do-all (object *bvh2*)
  (print object))

(space:do-overlapping (object *bvh2* (space:region 0 0 0 11 11 11))
  (print object))

(space:do-contained (object *bvh2* (space:region 0 0 0 11 11 11))
  (print object))

(describe *bvh2*)

(space:clear *bvh2*)
::

Every container also implements "For"(https://shinmera.github.io/for)'s iteration protocol, allowing you to iterate over the containers in an opaque way.

## Supported Structures
The library supports the following structure types at this point:

- ``org.shirakumo.fraf.trial.space.bvh2:bvh``
  A 2D bounding volume hierarchy. You may want to occasionally use ``reoptimize`` to rebalance the tree. The BVH has no size constraints.
- ``org.shirakumo.fraf.trial.space.quadtree:quadtree``
  A 2D quadtree. The tree will automatically expand and resize as objects are added to it.
- ``org.shirakumo.fraf.trial.space.grid3:grid``
  A 3D grid. The grid will *not* expand or resize automatically, nor estimate a good grid cell size. It is up to you to specify these properties as suitable for your use case. You may however call ``reoptimize`` at any time to change the grid shape.
- ``org.shirakumo.fraf.trial.space.kd-tree:kd-tree``
  A kd-tree. The tree can be created for either, 1, 2, or 3 dimensional spaces. Since the kd-tree is specified on splitting planes, it has no bounded size.

Please see their respective packages for additional supported operations.

## New Structures
In order to add a new structure, you must:

1. Create a new package to hold your structure functions
2. Create a subtype of ``container``
3. Implement ``enter``, ``leave``, ``clear``, and ``call-with-overlapping``

And ideally you should also:

- Implement ``call-with-all``, ``call-with-candidates``, ``call-with-contained``, ``call-with-intersecting``
- Implement ``update``, ``check``, ``reoptimize``
- Implement ``serialize``, ``deserialize``
- Implement ``for:make-iterator``, ``for:step-functions``
- Implement ``print-object``, ``describe-object``


3d-spaces

Upstream URL

Author

Maintainer

License

3d-spaces

Version:

License:

Authors:

Maintainers:

Dependencies:

3d-spaces-test

Version:

License:

Authors:

Maintainers:

Dependencies:

Dependencies (9)

Dependents (0)