3d spaces

1.0.0

A library implementing spatial query structures

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 location and bsize or radius for your objects to describe their bounding volumes, which the containers will then make use of.

The following shows a very basic use:

(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'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.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.quadtree:quadtree
A 2D quadtree. The tree will automatically expand and resize as objects are added to it.
org.shirakumo.fraf.trial.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.

Please see their respective packages for additional supported operations.

System Information

Version: 1.0.0

Dependencies:

Author: Nicolas Hafner

License: zlib

Homepage: https://shirakumo.github.io/3d-spaces/

Sources: https://github.com/shirakumo/3d-spaces.git

Definition Index

ORG.SHIRAKUMO.FRAF.TRIAL.SPACE

No documentation provided.

EXTERNAL STRUCTURE

CONTAINER

Supertype for all containers.

All container types must implement the following functions in addition
to implementing the iteration protocol of FOR (meaning you can use
FOR:OVER to iterate over a container as well).

See CONTAINER-P
See CHECK
See CLEAR
See REOPTIMIZE
See ENTER
See LEAVE
See UPDATE
See CALL-WITH-ALL
See CALL-WITH-CONTAINED
See CALL-WITH-OVERLAPPING

EXTERNAL STRUCTURE

REGION

Encompasses an axis-aligned region.

This is a VEC3, wherein the coordinates designate the "bottom left"
corner of the region and its SIZE designates the width height and
depth of the region.

NOTE: The region, unlike is required of other objects, does not keep
the data as center and half-size. However, it does implement LOCATION
and BSIZE to provide those quantities as defined.

See 3D-VECTORS:VEC3 (type)
See REGION-SIZE
See FIND-REGION
See REGION-OVERLAPS-P
See REGION-CONTAINS-P

EXTERNAL BINDING

UPDATE

Iterates over a generic sequence using an ITERATOR, with var being symbol macro to the current item.

You may SETF the var to update the item in the sequence, if the underlying iterator
supports doing so.

Potentially accepts arbitrary arguments, depending on which iterator is selected
for the respective object.

See FOR-ITERATOR:MAKE-ITERATOR

EXTERNAL FUNCTION

CONTAINER-P

OBJECT

Returns true if the given object is a container instance.

See CONTAINER (type)

EXTERNAL FUNCTION

FIND-REGION

OBJECTS

Returns a region that encompasses all objects passed as tightly as possible.

Every object must implement a method for at least LOCATION and BSIZE.

See REGION (type)

EXTERNAL FUNCTION
REGION
- X
- Y
- Z
- W
- H
- D
Source
No documentation provided.

EXTERNAL FUNCTION

REGION-CONTAINS-P

OBJECT
REGION

Returns true if the region entirely contains the object's axis aligned bounding box.

The object must implement a method for at least LOCATION and BSIZE.

See REGION (type)

EXTERNAL FUNCTION

REGION-OVERLAPS-P

OBJECT
REGION

Returns true if the region overlaps with the object's axis aligned bounding box.

The object must implement a method for at least LOCATION and BSIZE.

See REGION (type)

EXTERNAL FUNCTION

REGION-SIZE

INSTANCE

Accesses the region's size.

NOTE: unlike BSIZE, this is the *full size* and not a half-size.

See 3D-VECTORS:VEC3 (type)
See REGION (type)

EXTERNAL FUNCTION
(SETF REGION-SIZE)
- VALUE
- INSTANCE
Source
No documentation provided.

EXTERNAL GENERIC-FUNCTION

BSIZE

OBJECT

Returns a vec2 or vec3 representing the  half-size of the object's axis-aligned bounding box.

Users should extend this function with methods to provide the correct
value for their own object representations.

See LOCATION
See RADIUS

EXTERNAL GENERIC-FUNCTION

CALL-WITH-ALL

FUNCTION
CONTAINER

Calls FUNCTION with every object contained in the container.

See DO-ALL
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CALL-WITH-CONTAINED

FUNCTION
CONTAINER
REGION

Calls FUNCTION with every object contained in REGION.

The region is coerced to a region via ENSURE-REGION.
The function *may* be called with objects that overlap the specified
region, but *will not* be called with objects that lie entirely
outside the region.

See DO-CONTAINED
See ENSURE-REGION
See REGION (type)
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CALL-WITH-OVERLAPPING

FUNCTION
CONTAINER
REGION

Calls FUNCTION with every object contained in REGION.

The region is coerced to a region via ENSURE-REGION.
The function *will* be called with all objects that overlap the
specified region, and *will not* be called with objects that lie
entirely outside the region.

See DO-OVERLAPPING
See ENSURE-REGION
See REGION (type)
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CHECK

CONTAINER

Checks the container for validity.

Signals an error if there are problems with the container's internal
invariants.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CLEAR

CONTAINER

Clears the container and removes all objects from it.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

ENSURE-REGION

OBJECT
&OPTIONAL
REGION

Coerces the object to a REGION instance.

If the optional region is passed, the data in that region is updated
instead of creating a new region instance.

See REGION (type)

EXTERNAL GENERIC-FUNCTION

ENTER

OBJECT
CONTAINER

Adds objects to the container.

You may pass an object or a sequence of objects.
Passing a sequence may be more efficient that passing the objects
individually.

Entering the same object twice is safe.

Every object must implement a method for at least LOCATION and BSIZE.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

LEAVE

OBJECT
CONTAINER

Removes an object from the container.

You may pass an object or a sequence of objects.
Passing a sequence may be more efficient that passing the objects
individually.

Removing the same object twice is safe.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

LOCATION

OBJECT

Returns a vec2 or vec3 representing the center of the object.

Users should extend this function with methods to provide the correct
value for their own object representations.

See BSIZE
See RADIUS

EXTERNAL GENERIC-FUNCTION

RADIUS

OBJECT

Returns a single-float representing the radius of the object's bounding sphere.

Users should extend this function with methods to provide the correct
value for their own object representations.

If no method is provided it is computed automatically from the BSIZE.

See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

REOPTIMIZE

CONTAINER
&KEY
LOCATION
BSIZE
CELL-SIZE
ROUNDS

Reoptimizes the container to fit its objects better.

Each container type may accept specific arguments to control the
opitimization.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

UPDATE

OBJECT
CONTAINER

Updates the objects in the container.

You may pass an object or a sequence of objects.
Passing a sequence may be more efficient that passing the objects
individually.

You should call this function whenever the position or bounding size
of the object changes. If you do not notify the container of changes
like this, range queries may not give correct results.

Calling UPDATE on an object that is not currently in the container has
undefined consequences.

See CONTAINER (type)

EXTERNAL MACRO

DO-ALL

ELEMENT
CONTAINER
&OPTIONAL
RESULT

&BODY
BODY

Convenience macro to iterate over all objects in the container.

Returns the RETURN value, and executes BODY in a BLOCK NIL context.

See CALL-WITH-ALL

EXTERNAL MACRO

DO-CONTAINED

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT

&BODY
BODY

Convenience macro to iterate over objects contained in the region.

Returns the RETURN value, and executes BODY in a BLOCK NIL context.

See CALL-WITH-CONTAINED

EXTERNAL MACRO

DO-OVERLAPPING

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT

&BODY
BODY

Convenience macro to iterate over objects overlapping the region.

Returns the RETURN value, and executes BODY in a BLOCK NIL context.

See CALL-WITH-OVERLAPPING

ORG.SHIRAKUMO.FRAF.TRIAL.SPACE.BVH2

No documentation provided.

EXTERNAL STRUCTURE

BVH

A binary Bounding Volume Hierarchy in 2D.

Each node in the tree is represented by an axis aligned bounding box
and may either contain a single object or two child nodes.

The tree does not automatically rebalance when objects move and may
not be optimal after all objects are inserted. Calling REOPTIMIZE will
attempt to shuffle the tree around for better search traversal
time. It is recommended to call REOPTIMIZE with :ROUNDS 10 or similar,
to optimise the tree after first building it.

There is no limit to the area that the tree can span and no canonical
center to it. The tree will automatically expand and contract as
needed to fit all objects.

See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:CONTAINER
See MAKE-BVH
See BVH-INSERT
See BVH-REMOVE
See BVH-UPDATE
See BVH-LINES

EXTERNAL FUNCTION

BVH-INSERT

BVH
OBJECT

Fast track for ENTER.

See BVH (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:ENTER

EXTERNAL FUNCTION

BVH-LINES

BVH

Debug function.

Returns a list of lists where every two entries constitute a
line. Each entry is made up of a VEC3 for its position and a VEC4 for
its color.

The lines draw up the BVH nodes with the colour corresponding to the
node depth.

See BVH (type)

EXTERNAL FUNCTION

BVH-REMOVE

BVH
OBJECT

Fast track for LEAVE.

See BVH (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:LEAVE

EXTERNAL FUNCTION

BVH-UPDATE

BVH
OBJECT

Fast track for UPDATE.

See BVH (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:UPDATE

EXTERNAL FUNCTION
MAKE-BVH
Source
```
Creates a fresh BVH2.

See BVH (type)
```

ORG.SHIRAKUMO.FRAF.TRIAL.SPACE.QUADTREE

No documentation provided.

EXTERNAL STRUCTURE

QUADTREE


See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:CONTAINER
See MAKE-QUADTREE
See MAKE-QUADTREE-AT
See QUADTREE-INSERT
See QUADTREE-REMOVE
See QUADTREE-UPDATE
See QUADTREE-FIND-ALL
See QUADTREE-FIND-OVERLAPS
See QUADTREE-FIND-OVERLAPS-IN
See QUADTREE-FIND-CONTAINED
See QUADTREE-FIND-CONTAINED-IN
See QUADTREE-FIND-FOR
See QUADTREE-LINES

EXTERNAL FUNCTION
MAKE-QUADTREE
Source
```
See QUADTREE (type)
```
EXTERNAL FUNCTION
MAKE-QUADTREE-AT
- LOCATION
- SIZE
- &KEY
- MIN-SIZE
- THRESHOLD
Source
```
See QUADTREE (type)
```
EXTERNAL FUNCTION
QUADTREE-FIND-ALL
- TREE
- &OPTIONAL
- VECTOR
Source
```
See QUADTREE (type)
```
EXTERNAL FUNCTION
QUADTREE-FIND-CONTAINED
- TREE
- REGION
- &OPTIONAL
- VECTOR
Source
```
See QUADTREE (type)
```
EXTERNAL FUNCTION
QUADTREE-FIND-CONTAINED-IN
- TREE
- LOCATION
- SIZE
- &OPTIONAL
- VECTOR
Source
```
See QUADTREE (type)
```
EXTERNAL FUNCTION
QUADTREE-FIND-FOR
- TREE
- OBJECT
- &OPTIONAL
- VECTOR
Source
```
See QUADTREE (type)
```
EXTERNAL FUNCTION
QUADTREE-FIND-OVERLAPS
- TREE
- REGION
- &OPTIONAL
- VECTOR
Source
```
See QUADTREE (type)
```
EXTERNAL FUNCTION
QUADTREE-FIND-OVERLAPS-IN
- TREE
- LOCATION
- SIZE
- &OPTIONAL
- VECTOR
Source
```
See QUADTREE (type)
```

EXTERNAL FUNCTION

QUADTREE-INSERT

TREE
OBJECT

Fast track for ENTER.

See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:ENTER

EXTERNAL FUNCTION

QUADTREE-LINES

TREE

Debug function.

Returns a list of lists where every two entries constitute a
line. Each entry is made up of a VEC3 for its position and a VEC4 for
its color.

The lines draw up the quadtree nodes with the colour corresponding to
the node depth.

See QUADTREE (type)

EXTERNAL FUNCTION

QUADTREE-REMOVE

TREE
OBJECT

Fast track for LEAVE.

See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:LEAVE

EXTERNAL FUNCTION

QUADTREE-UPDATE

TREE
OBJECT

Fast track for UPDATE.

See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:UPDATE

ORG.SHIRAKUMO.FRAF.TRIAL.SPACE.GRID3

No documentation provided.

EXTERNAL STRUCTURE

GRID

A uniform bounded grid in 3D.

This is one of the simplest possible spatial structures, with
constant-time insertion, and in the general case constant-time removal
and update.

However, the structure does not automatically tune itself and ensuring
good performance requires user input. Specifically, the search time
performance is very sensitive to the cell size. Too coarse and too many
objects need to be searched. Too fine and a lot of space is wasted and
objects may be missed for fine searches.

If an object is bigger than the cell size, it may be missed for
certain searches, as the search only guarantees finding the objects in
the immediate neighbourhood of a cell.

The implementation here uses a dense array, meaning it requires
at least W*H*D+N storage.

You can update all properties of the grid, with REOPTIMIZE or
GRID-RESIZE and GRID-MOVE. Doing so is equivalent to creating a new
grid and inserting all previous entities into it. If REOPTIMIZE is
called without any arguments, the grid will recenter and refit itself
to the computed ideal bounds for all contained objects and the cell
size will adjust itself to be as big as the largest object (if any).

Thus it can be a valid strategy to just create a grid, insert all your
objects, and then call REOPTIMIZE to determine the best parameters.

Objects that are outside the grid's limits will simply be clamped to
the nearest cell within the grid. Beware of degenerating performance
if your objects do not fit within the grid's size.

See QUADTREE (type)

EXTERNAL FUNCTION

GRID-INSERT

OBJECT
GRID

Fast track for ENTER.

See GRID (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:ENTER

EXTERNAL FUNCTION

GRID-MOVE

GRID
LOCATION

Moves the grid's center to the specified location.

Note that this will not change the grid's half-size or cell size.

See GRID (type)

EXTERNAL FUNCTION

GRID-REMOVE

OBJECT
GRID

Fast track for LEAVE.

See GRID (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:LEAVE

EXTERNAL FUNCTION

GRID-RESIZE

GRID
&KEY
BSIZE
CELL-SIZE

Resizes the grid to the specified half-size and cell size.

See GRID (type)

EXTERNAL FUNCTION

GRID-UPDATE

OBJECT
GRID

Fast track for UPDATE.

See GRID (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:UPDATE

EXTERNAL FUNCTION

MAKE-GRID

CELL-SIZE
&KEY
LOCATION
BSIZE

Creates a new grid.

If no LOCATION is passed, it is centered at the origin. If no BSIZE is
passed, it is sized to a half-size of 100 in every direction.

See GRID (type)