3d spaces

1.0.0

A library implementing spatial query structures

Table of Contents

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:

(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.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:

Create a new package to hold your structure functions
Create a subtype of container
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

System Information

Version: 1.0.0

Dependencies:

Author: Yukari Hafner

License: zlib

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

Bug Tracker: https://github.com/shirakumo/3d-spaces/issues

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 OBJECT-COUNT
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 STRUCTURE
SPHERE
Source
No documentation provided.

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
&REST

Returns true if the given object is a container instance.

See CONTAINER (type)

EXTERNAL FUNCTION

FIND-REGION

OBJECTS
&REST

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
- &REST
Source
No documentation provided.

EXTERNAL FUNCTION

REGION-CONTAINS-P

OBJECT
REGION
&REST

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
&REST

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
&REST

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
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
SPHERE
- X
- Y
- Z
- R
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
SPHERE-RADIUS
- INSTANCE
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
(SETF SPHERE-RADIUS)
- VALUE
- INSTANCE
- &REST
Source
No documentation provided.

EXTERNAL GENERIC-FUNCTION

BOUNDING-BOX

OBJECT
&REST

Returns an axis-aligned bounding box for the object.

Returns two values, a VEC3 for the center, and a VEC3 for the
half-size of the box.

If unimplemented, this will return LOCATION and BSIZE of the object.

See BOUNDING-SPHERE
See ORIENTED-BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

BOUNDING-SPHERE

OBJECT
&REST

Returns a bounding sphereg for the object.

Returns two values, a VEC3 for the center, and a radius for the
sphere.

If unimplemented, this will return LOCATION and RADIUS of the object.

See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

BSIZE

OBJECT
&REST

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
See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX

EXTERNAL GENERIC-FUNCTION

CALL-WITH-ALL

FUNCTION
CONTAINER
&REST

Calls FUNCTION with every object contained in CONTAINER.

See DO-ALL
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CALL-WITH-CANDIDATES

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object which approximately overlaps REGION.

The region is coerced to a region via ENSURE-REGION.

FUNCTION *may* be called with any object contained in
CONTAINER. However, depending on the type of CONTAINER, the set of
objects with which FUNCTION is actually called is usually a moderate
superset of the objects that in CONTAINER that overlap REGION.

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

EXTERNAL GENERIC-FUNCTION

CALL-WITH-CONTAINED

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object contained in REGION.

The region is coerced to a region via ENSURE-REGION.
The function *will* be called with objects that lie entirely inside the
specified region. The function *may* be called with objects that
overlap but do not lie entirely inside the region. The function *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-INTERSECTING

FUNCTION
CONTAINER
RAY-ORIGIN
RAY-DIRECTION
&REST

Calls FUNCTION with every object that *may* intersect the ray.

It is up to you to implement the fine grained intersection test
between the ray and the object, this will only approximate the lookup
based on the container's internal acceleration structures.

Depending on the container, RAY-ORIGIN and RAY-DIRECTION should be
either VEC3s or VEC2s.

See DO-INTERSECTING
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CALL-WITH-OVERLAPPING

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object which overlaps REGION.

The region is coerced to a region via ENSURE-REGION.
The function *will* be called with objects that overlap the specified
region (including objects that lie entirely inside the region). The
function *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

CALL-WITH-PAIRS

FUNCTION
CONTAINER
&REST

Calls FUNCTION with all pairs of overlapping objects.

The function will be called with all pairs of objects that overlap
each other according to the container's internal bounding volume of
the objects.

It is up to you to implement the fine grained intersection test
between any two objects, this will only approximate the lookup based
on the container's internal acceleration structures.

See DO-PAIRS
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CHECK

CONTAINER
&REST

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
&REST

Clears the container and removes all objects from it.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

DESERIALIZE

CONTAINER
FILE
ID->OBJECT
&REST

Deserialize CONTAINER from FILE.

ID->OBJECT is called for every object that was added to the container
that was used to serialize to the given file. The function should
accept the strings that were previously returned by OBJECT->ID and
return the corresponding object.

It is expected that the size and location of the returned objects is
the same as it was when SERIALIZE was called. Or in other words, it is
still up to you to ensure object properties are persisted separately
or that the container is updated appropriately after deserialization.

Consequences are undefined if the function returns NIL, or the same
(EQ) object for two different (EQUAL) IDs, or returning different
objects for the same (EQUAL) IDS.

See SERIALIZE
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

ENSURE-REGION

OBJECT
&OPTIONAL
REGION
&REST

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
&REST

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

GROUP

OBJECT
&REST

Returns NIL or an arbitrary designator for the group of objects that the object is part of.

NIL indicates that the object is not part of any group.

Objects within a group, that is objects for which this function
returns an EQ value, are not considered as potential pairs by
CALL-WITH-PAIRS.

The primary use-case for this mechanism are higher-level objects that
are composed of primitive objects. In the context of collision
detection, the primitives that make up a higher-level object are not
supposed to collide with each other. Eliminating such pairs in
CALL-WITH-PAIRS based on the group is more efficient than having the
client do it and also allows additional optimizations in the
acceleration structure.

See CALL-WITH-PAIRS

EXTERNAL GENERIC-FUNCTION

LEAVE

OBJECT
CONTAINER
&REST

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
&REST

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
See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX
See BOUNDING-SPHERE

EXTERNAL GENERIC-FUNCTION

OBJECT-COUNT

CONTAINER
&REST

Computes the number of objects in the container.

Note that this is usually not a constant-time operation.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

ORIENTED-BOUNDING-BOX

OBJECT
&REST

Returns an oriented bounding box for the object.

Returns three values, a VEC3 for the center, a VEC3 for the half-size
of the box, and a quaternion for orienting the box.

If unimplemented, this will return LOCATION and BSIZE of the object,
and a unit quaternion.

See BOUNDING-SPHERE
See BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

RADIUS

OBJECT
&REST

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
See BOUNDING-SPHERE

EXTERNAL GENERIC-FUNCTION

REOPTIMIZE

CONTAINER
&KEY
LOCATION
BSIZE
CELL-SIZE
ROUNDS
&REST

Reoptimizes the container to fit its objects better.

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

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

SERIALIZE

CONTAINER
FILE
OBJECT->ID
&REST

Serialise CONTAINER to FILE.

OBJECT->ID is called for every object that was added to the container
during the serialisation process. Value returned from the function
must be a string.

Consequences are undefined if the function returns the same (EQUAL)
ID string for two different (EQ) objects, or returns different (EQUAL)
ID strings for the same (EQ) object.

See DESERIALIZE
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

UPDATE

OBJECT
CONTAINER
&REST

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
&REST

&BODY
BODY
&REST

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-CANDIDATES

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over objects that approximate overlap the region.

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

See CALL-WITH-CANDIDATES

EXTERNAL MACRO

DO-CONTAINED

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

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-INTERSECTING

ELEMENT
CONTAINER
RAY-ORIGIN
RAY-DIRECTION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over objects intersecting the ray.

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

See CALL-WITH-INTERSECTING

EXTERNAL MACRO

DO-OVERLAPPING

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

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

EXTERNAL MACRO

DO-PAIRS

A
B
CONTAINER
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over pairs of overlapping objects.

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

See CALL-WITH-PAIRS

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 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 OBJECT-COUNT
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 STRUCTURE
SPHERE
Source
No documentation provided.

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

BVH-INSERT

BVH
OBJECT
&REST

Fast track for ENTER.

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

EXTERNAL FUNCTION

BVH-LINES

BVH
&REST

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
&REST

Fast track for LEAVE.

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

EXTERNAL FUNCTION

BVH-UPDATE

BVH
OBJECT
&REST

Fast track for UPDATE.

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

EXTERNAL FUNCTION

CONTAINER-P

OBJECT
&REST

Returns true if the given object is a container instance.

See CONTAINER (type)

EXTERNAL FUNCTION

FIND-REGION

OBJECTS
&REST

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
MAKE-BVH
Source
```
Creates a fresh BVH2.

See BVH (type)
```
EXTERNAL FUNCTION
REGION
- X
- Y
- Z
- W
- H
- D
- &REST
Source
No documentation provided.

EXTERNAL FUNCTION

REGION-CONTAINS-P

OBJECT
REGION
&REST

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
&REST

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
&REST

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
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
SPHERE
- X
- Y
- Z
- R
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
SPHERE-RADIUS
- INSTANCE
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
(SETF SPHERE-RADIUS)
- VALUE
- INSTANCE
- &REST
Source
No documentation provided.

EXTERNAL GENERIC-FUNCTION

BOUNDING-BOX

OBJECT
&REST

Returns an axis-aligned bounding box for the object.

Returns two values, a VEC3 for the center, and a VEC3 for the
half-size of the box.

If unimplemented, this will return LOCATION and BSIZE of the object.

See BOUNDING-SPHERE
See ORIENTED-BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

BOUNDING-SPHERE

OBJECT
&REST

Returns a bounding sphereg for the object.

Returns two values, a VEC3 for the center, and a radius for the
sphere.

If unimplemented, this will return LOCATION and RADIUS of the object.

See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

BSIZE

OBJECT
&REST

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
See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX

EXTERNAL GENERIC-FUNCTION

CALL-WITH-ALL

FUNCTION
CONTAINER
&REST

Calls FUNCTION with every object contained in CONTAINER.

See DO-ALL
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CALL-WITH-CANDIDATES

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object which approximately overlaps REGION.

The region is coerced to a region via ENSURE-REGION.

FUNCTION *may* be called with any object contained in
CONTAINER. However, depending on the type of CONTAINER, the set of
objects with which FUNCTION is actually called is usually a moderate
superset of the objects that in CONTAINER that overlap REGION.

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

EXTERNAL GENERIC-FUNCTION

CALL-WITH-CONTAINED

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object contained in REGION.

The region is coerced to a region via ENSURE-REGION.
The function *will* be called with objects that lie entirely inside the
specified region. The function *may* be called with objects that
overlap but do not lie entirely inside the region. The function *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-INTERSECTING

FUNCTION
CONTAINER
RAY-ORIGIN
RAY-DIRECTION
&REST

Calls FUNCTION with every object that *may* intersect the ray.

It is up to you to implement the fine grained intersection test
between the ray and the object, this will only approximate the lookup
based on the container's internal acceleration structures.

Depending on the container, RAY-ORIGIN and RAY-DIRECTION should be
either VEC3s or VEC2s.

See DO-INTERSECTING
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CALL-WITH-OVERLAPPING

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object which overlaps REGION.

The region is coerced to a region via ENSURE-REGION.
The function *will* be called with objects that overlap the specified
region (including objects that lie entirely inside the region). The
function *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

CALL-WITH-PAIRS

FUNCTION
CONTAINER
&REST

Calls FUNCTION with all pairs of overlapping objects.

The function will be called with all pairs of objects that overlap
each other according to the container's internal bounding volume of
the objects.

It is up to you to implement the fine grained intersection test
between any two objects, this will only approximate the lookup based
on the container's internal acceleration structures.

See DO-PAIRS
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CHECK

CONTAINER
&REST

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
&REST

Clears the container and removes all objects from it.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

DESERIALIZE

CONTAINER
FILE
ID->OBJECT
&REST

Deserialize CONTAINER from FILE.

ID->OBJECT is called for every object that was added to the container
that was used to serialize to the given file. The function should
accept the strings that were previously returned by OBJECT->ID and
return the corresponding object.

It is expected that the size and location of the returned objects is
the same as it was when SERIALIZE was called. Or in other words, it is
still up to you to ensure object properties are persisted separately
or that the container is updated appropriately after deserialization.

Consequences are undefined if the function returns NIL, or the same
(EQ) object for two different (EQUAL) IDs, or returning different
objects for the same (EQUAL) IDS.

See SERIALIZE
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

ENSURE-REGION

OBJECT
&OPTIONAL
REGION
&REST

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
&REST

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

GROUP

OBJECT
&REST

Returns NIL or an arbitrary designator for the group of objects that the object is part of.

NIL indicates that the object is not part of any group.

Objects within a group, that is objects for which this function
returns an EQ value, are not considered as potential pairs by
CALL-WITH-PAIRS.

The primary use-case for this mechanism are higher-level objects that
are composed of primitive objects. In the context of collision
detection, the primitives that make up a higher-level object are not
supposed to collide with each other. Eliminating such pairs in
CALL-WITH-PAIRS based on the group is more efficient than having the
client do it and also allows additional optimizations in the
acceleration structure.

See CALL-WITH-PAIRS

EXTERNAL GENERIC-FUNCTION

LEAVE

OBJECT
CONTAINER
&REST

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
&REST

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
See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX
See BOUNDING-SPHERE

EXTERNAL GENERIC-FUNCTION

OBJECT-COUNT

CONTAINER
&REST

Computes the number of objects in the container.

Note that this is usually not a constant-time operation.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

ORIENTED-BOUNDING-BOX

OBJECT
&REST

Returns an oriented bounding box for the object.

Returns three values, a VEC3 for the center, a VEC3 for the half-size
of the box, and a quaternion for orienting the box.

If unimplemented, this will return LOCATION and BSIZE of the object,
and a unit quaternion.

See BOUNDING-SPHERE
See BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

RADIUS

OBJECT
&REST

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
See BOUNDING-SPHERE

EXTERNAL GENERIC-FUNCTION

REOPTIMIZE

CONTAINER
&KEY
LOCATION
BSIZE
CELL-SIZE
ROUNDS
&REST

Reoptimizes the container to fit its objects better.

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

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

SERIALIZE

CONTAINER
FILE
OBJECT->ID
&REST

Serialise CONTAINER to FILE.

OBJECT->ID is called for every object that was added to the container
during the serialisation process. Value returned from the function
must be a string.

Consequences are undefined if the function returns the same (EQUAL)
ID string for two different (EQ) objects, or returns different (EQUAL)
ID strings for the same (EQ) object.

See DESERIALIZE
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

UPDATE

OBJECT
CONTAINER
&REST

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
&REST

&BODY
BODY
&REST

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-CANDIDATES

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over objects that approximate overlap the region.

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

See CALL-WITH-CANDIDATES

EXTERNAL MACRO

DO-CONTAINED

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

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-INTERSECTING

ELEMENT
CONTAINER
RAY-ORIGIN
RAY-DIRECTION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over objects intersecting the ray.

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

See CALL-WITH-INTERSECTING

EXTERNAL MACRO

DO-OVERLAPPING

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

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

EXTERNAL MACRO

DO-PAIRS

A
B
CONTAINER
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over pairs of overlapping objects.

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

See CALL-WITH-PAIRS

ORG.SHIRAKUMO.FRAF.TRIAL.SPACE.QUADTREE

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 OBJECT-COUNT
See ENTER
See LEAVE
See UPDATE
See CALL-WITH-ALL
See CALL-WITH-CONTAINED
See CALL-WITH-OVERLAPPING

EXTERNAL STRUCTURE

QUADTREE

A spatial tree data structure in 2D similar to BVH2.

Each node of a quad-tree splits space into four equal sections that
intersect in the middle of the node's space. Each of these quarters
may be represented by a child-node or nothing each of which tries to
hold as few items as possible. If an item overlaps with the space of
multiple child nodes, it is not passed to any of them and kept in the
parent node.

The node automatically splits into sub-sections when an item count
threshold is met upon insertion and checks the need for rebalancing at
removal. Calling REOPTIMIZE manually will shuffle the tree around for
better search traversal, but it is not recommended as the searches are
should remain fast enough. Calling UPDATE will also rebalance the tree
automatically in previous and current space relative to the passed
object.

Like with BVH2, there is no limit to the area that the tree can span
and it may cover any arbitrary area. The tree will also automatically
expand as needed to fit all objects, but it will not contract.

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 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 STRUCTURE
SPHERE
Source
No documentation provided.

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
&REST

Returns true if the given object is a container instance.

See CONTAINER (type)

EXTERNAL FUNCTION

FIND-REGION

OBJECTS
&REST

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

MAKE-QUADTREE

Creates an empty QUADTREE for [0,0] to [100,100] coordinate space
with 1 as the minimum length of an edge and 1 as the threshold number
of items before the node is split.

See QUADTREE (type)
See MAKE-QUADTREE-AT

EXTERNAL FUNCTION

MAKE-QUADTREE-AT

LOCATION
SIZE
&KEY
MIN-SIZE
THRESHOLD
&REST

Creates an empty QUADTREE for the defined section of space with
wanted minimum node edge size (defaults to 1) and the item count
threshold before a node splits (defaults to 1).

See QUADTREE (type)
See MAKE-QUADTREE

EXTERNAL FUNCTION

QUADTREE-FIND-ALL

TREE
&OPTIONAL
VECTOR
&REST

Finds every object in the tree and pushes them into the passed
vector which is then returned.

See QUADTREE (type)

EXTERNAL FUNCTION

QUADTREE-FIND-CONTAINED

TREE
REGION
&OPTIONAL
VECTOR
&REST

Finds every object in the tree that is completely contained by
the passed region and pushes them into the vector which is then
returned.

The region is defined by a VEC4 where VX and VY represent the top-left
point of the region, and VZ and VW the bottom-right point of the
region.

See QUADTREE (type)
See QUADTREE-FIND-CONTAINED-IN
See QUADTREE-FIND-OVERLAPS

EXTERNAL FUNCTION

QUADTREE-FIND-CONTAINED-IN

TREE
LOCATION
SIZE
&OPTIONAL
VECTOR
&REST

Finds every object in the tree that is completely contained by
the passed region and pushes them into the vector which is then
returned.

The region is defined by a VEC2 where VX and VY represent the top-left
point of the region, and a second VEC2 where VX and VY are the width
and height respectively of the region.

See QUADTREE (type)
See QUADTREE-FIND-CONTAINED
See QUADTREE-FIND-OVERLAPS-IN

EXTERNAL FUNCTION

QUADTREE-FIND-FOR

TREE
OBJECT
&OPTIONAL
VECTOR
&REST

Finds every object in the tree that overlaps with the passed
object that holds location and size information to it.

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

See QUADTREE (type)
See QUADTREE-FIND-OVERLAPS-IN

EXTERNAL FUNCTION

QUADTREE-FIND-OVERLAPS

TREE
REGION
&OPTIONAL
VECTOR
&REST

Finds every object in the tree that overlaps with the passed
region and pushes them into the vector which is then returned.

The region is defined by a VEC4 where VX and VY represent the top-left
point of the region, and VZ and VW the bottom-right point of the
region.

See QUADTREE (type)
See QUADTREE-FIND-OVERLAPS-IN
See QUADTREE-FIND-CONTAINED

EXTERNAL FUNCTION

QUADTREE-FIND-OVERLAPS-IN

TREE
LOCATION
SIZE
&OPTIONAL
VECTOR
&REST

Finds every object in the tree that overlaps with the passed
region and pushes them into the vector which is then returned.

The region is defined by a VEC2 where VX and VY represent the top-left
point of the region, and a second VEC2 where VX and VY are the width
and height respectively of the region.

See QUADTREE (type)
See QUADTREE-FIND-OVERLAPS
See QUADTREE-FIND-CONTAINED-IN

EXTERNAL FUNCTION

QUADTREE-INSERT

TREE
OBJECT
&REST

Fast track for ENTER. If the passed object already exists in the
tree its holding node is updated.

See QUADTREE (type)
See QUADTREE-UPDATE
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:ENTER

EXTERNAL FUNCTION

QUADTREE-LINES

TREE
&REST

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
&REST

Fast track for LEAVE. The holder node's state is updated if
necessary.

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

EXTERNAL FUNCTION

QUADTREE-UPDATE

TREE
OBJECT
&REST

Fast track for UPDATE. Checks if the passed object's holding node
in the tree should be changed and updates it accordingly.

See QUADTREE (type)
See QUADTREE-INSERT
See QUADTREE-REMOVE
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:UPDATE

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

EXTERNAL FUNCTION

REGION-CONTAINS-P

OBJECT
REGION
&REST

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
&REST

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
&REST

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
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
SPHERE
- X
- Y
- Z
- R
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
SPHERE-RADIUS
- INSTANCE
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
(SETF SPHERE-RADIUS)
- VALUE
- INSTANCE
- &REST
Source
No documentation provided.

EXTERNAL GENERIC-FUNCTION

BOUNDING-BOX

OBJECT
&REST

Returns an axis-aligned bounding box for the object.

Returns two values, a VEC3 for the center, and a VEC3 for the
half-size of the box.

If unimplemented, this will return LOCATION and BSIZE of the object.

See BOUNDING-SPHERE
See ORIENTED-BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

BOUNDING-SPHERE

OBJECT
&REST

Returns a bounding sphereg for the object.

Returns two values, a VEC3 for the center, and a radius for the
sphere.

If unimplemented, this will return LOCATION and RADIUS of the object.

See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

BSIZE

OBJECT
&REST

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
See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX

EXTERNAL GENERIC-FUNCTION

CALL-WITH-ALL

FUNCTION
CONTAINER
&REST

Calls FUNCTION with every object contained in CONTAINER.

See DO-ALL
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CALL-WITH-CANDIDATES

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object which approximately overlaps REGION.

The region is coerced to a region via ENSURE-REGION.

FUNCTION *may* be called with any object contained in
CONTAINER. However, depending on the type of CONTAINER, the set of
objects with which FUNCTION is actually called is usually a moderate
superset of the objects that in CONTAINER that overlap REGION.

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

EXTERNAL GENERIC-FUNCTION

CALL-WITH-CONTAINED

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object contained in REGION.

The region is coerced to a region via ENSURE-REGION.
The function *will* be called with objects that lie entirely inside the
specified region. The function *may* be called with objects that
overlap but do not lie entirely inside the region. The function *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-INTERSECTING

FUNCTION
CONTAINER
RAY-ORIGIN
RAY-DIRECTION
&REST

Calls FUNCTION with every object that *may* intersect the ray.

It is up to you to implement the fine grained intersection test
between the ray and the object, this will only approximate the lookup
based on the container's internal acceleration structures.

Depending on the container, RAY-ORIGIN and RAY-DIRECTION should be
either VEC3s or VEC2s.

See DO-INTERSECTING
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CALL-WITH-OVERLAPPING

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object which overlaps REGION.

The region is coerced to a region via ENSURE-REGION.
The function *will* be called with objects that overlap the specified
region (including objects that lie entirely inside the region). The
function *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

CALL-WITH-PAIRS

FUNCTION
CONTAINER
&REST

Calls FUNCTION with all pairs of overlapping objects.

The function will be called with all pairs of objects that overlap
each other according to the container's internal bounding volume of
the objects.

It is up to you to implement the fine grained intersection test
between any two objects, this will only approximate the lookup based
on the container's internal acceleration structures.

See DO-PAIRS
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CHECK

CONTAINER
&REST

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
&REST

Clears the container and removes all objects from it.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

DESERIALIZE

CONTAINER
FILE
ID->OBJECT
&REST

Deserialize CONTAINER from FILE.

ID->OBJECT is called for every object that was added to the container
that was used to serialize to the given file. The function should
accept the strings that were previously returned by OBJECT->ID and
return the corresponding object.

It is expected that the size and location of the returned objects is
the same as it was when SERIALIZE was called. Or in other words, it is
still up to you to ensure object properties are persisted separately
or that the container is updated appropriately after deserialization.

Consequences are undefined if the function returns NIL, or the same
(EQ) object for two different (EQUAL) IDs, or returning different
objects for the same (EQUAL) IDS.

See SERIALIZE
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

ENSURE-REGION

OBJECT
&OPTIONAL
REGION
&REST

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
&REST

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

GROUP

OBJECT
&REST

Returns NIL or an arbitrary designator for the group of objects that the object is part of.

NIL indicates that the object is not part of any group.

Objects within a group, that is objects for which this function
returns an EQ value, are not considered as potential pairs by
CALL-WITH-PAIRS.

The primary use-case for this mechanism are higher-level objects that
are composed of primitive objects. In the context of collision
detection, the primitives that make up a higher-level object are not
supposed to collide with each other. Eliminating such pairs in
CALL-WITH-PAIRS based on the group is more efficient than having the
client do it and also allows additional optimizations in the
acceleration structure.

See CALL-WITH-PAIRS

EXTERNAL GENERIC-FUNCTION

LEAVE

OBJECT
CONTAINER
&REST

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
&REST

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
See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX
See BOUNDING-SPHERE

EXTERNAL GENERIC-FUNCTION

OBJECT-COUNT

CONTAINER
&REST

Computes the number of objects in the container.

Note that this is usually not a constant-time operation.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

ORIENTED-BOUNDING-BOX

OBJECT
&REST

Returns an oriented bounding box for the object.

Returns three values, a VEC3 for the center, a VEC3 for the half-size
of the box, and a quaternion for orienting the box.

If unimplemented, this will return LOCATION and BSIZE of the object,
and a unit quaternion.

See BOUNDING-SPHERE
See BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

RADIUS

OBJECT
&REST

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
See BOUNDING-SPHERE

EXTERNAL GENERIC-FUNCTION

REOPTIMIZE

CONTAINER
&KEY
LOCATION
BSIZE
CELL-SIZE
ROUNDS
&REST

Reoptimizes the container to fit its objects better.

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

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

SERIALIZE

CONTAINER
FILE
OBJECT->ID
&REST

Serialise CONTAINER to FILE.

OBJECT->ID is called for every object that was added to the container
during the serialisation process. Value returned from the function
must be a string.

Consequences are undefined if the function returns the same (EQUAL)
ID string for two different (EQ) objects, or returns different (EQUAL)
ID strings for the same (EQ) object.

See DESERIALIZE
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

UPDATE

OBJECT
CONTAINER
&REST

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
&REST

&BODY
BODY
&REST

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-CANDIDATES

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over objects that approximate overlap the region.

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

See CALL-WITH-CANDIDATES

EXTERNAL MACRO

DO-CONTAINED

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

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-INTERSECTING

ELEMENT
CONTAINER
RAY-ORIGIN
RAY-DIRECTION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over objects intersecting the ray.

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

See CALL-WITH-INTERSECTING

EXTERNAL MACRO

DO-OVERLAPPING

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

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

EXTERNAL MACRO

DO-PAIRS

A
B
CONTAINER
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over pairs of overlapping objects.

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

See CALL-WITH-PAIRS

ORG.SHIRAKUMO.FRAF.TRIAL.SPACE.GRID3

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 OBJECT-COUNT
See ENTER
See LEAVE
See UPDATE
See CALL-WITH-ALL
See CALL-WITH-CONTAINED
See CALL-WITH-OVERLAPPING

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 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 STRUCTURE
SPHERE
Source
No documentation provided.

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
&REST

Returns true if the given object is a container instance.

See CONTAINER (type)

EXTERNAL FUNCTION

FIND-REGION

OBJECTS
&REST

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

GRID-INSERT

OBJECT
GRID
&REST

Fast track for ENTER.

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

EXTERNAL FUNCTION

GRID-MOVE

GRID
LOCATION
&REST

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
&REST

Fast track for LEAVE.

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

EXTERNAL FUNCTION

GRID-RESIZE

GRID
&KEY
BSIZE
CELL-SIZE
&REST

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

See GRID (type)

EXTERNAL FUNCTION

GRID-UPDATE

OBJECT
GRID
&REST

Fast track for UPDATE.

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

EXTERNAL FUNCTION

MAKE-GRID

CELL-SIZE
&KEY
LOCATION
BSIZE
&REST

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)

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

EXTERNAL FUNCTION

REGION-CONTAINS-P

OBJECT
REGION
&REST

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
&REST

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
&REST

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
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
SPHERE
- X
- Y
- Z
- R
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
SPHERE-RADIUS
- INSTANCE
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
(SETF SPHERE-RADIUS)
- VALUE
- INSTANCE
- &REST
Source
No documentation provided.

EXTERNAL GENERIC-FUNCTION

BOUNDING-BOX

OBJECT
&REST

Returns an axis-aligned bounding box for the object.

Returns two values, a VEC3 for the center, and a VEC3 for the
half-size of the box.

If unimplemented, this will return LOCATION and BSIZE of the object.

See BOUNDING-SPHERE
See ORIENTED-BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

BOUNDING-SPHERE

OBJECT
&REST

Returns a bounding sphereg for the object.

Returns two values, a VEC3 for the center, and a radius for the
sphere.

If unimplemented, this will return LOCATION and RADIUS of the object.

See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

BSIZE

OBJECT
&REST

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
See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX

EXTERNAL GENERIC-FUNCTION

CALL-WITH-ALL

FUNCTION
CONTAINER
&REST

Calls FUNCTION with every object contained in CONTAINER.

See DO-ALL
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CALL-WITH-CANDIDATES

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object which approximately overlaps REGION.

The region is coerced to a region via ENSURE-REGION.

FUNCTION *may* be called with any object contained in
CONTAINER. However, depending on the type of CONTAINER, the set of
objects with which FUNCTION is actually called is usually a moderate
superset of the objects that in CONTAINER that overlap REGION.

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

EXTERNAL GENERIC-FUNCTION

CALL-WITH-CONTAINED

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object contained in REGION.

The region is coerced to a region via ENSURE-REGION.
The function *will* be called with objects that lie entirely inside the
specified region. The function *may* be called with objects that
overlap but do not lie entirely inside the region. The function *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-INTERSECTING

FUNCTION
CONTAINER
RAY-ORIGIN
RAY-DIRECTION
&REST

Calls FUNCTION with every object that *may* intersect the ray.

It is up to you to implement the fine grained intersection test
between the ray and the object, this will only approximate the lookup
based on the container's internal acceleration structures.

Depending on the container, RAY-ORIGIN and RAY-DIRECTION should be
either VEC3s or VEC2s.

See DO-INTERSECTING
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CALL-WITH-OVERLAPPING

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object which overlaps REGION.

The region is coerced to a region via ENSURE-REGION.
The function *will* be called with objects that overlap the specified
region (including objects that lie entirely inside the region). The
function *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

CALL-WITH-PAIRS

FUNCTION
CONTAINER
&REST

Calls FUNCTION with all pairs of overlapping objects.

The function will be called with all pairs of objects that overlap
each other according to the container's internal bounding volume of
the objects.

It is up to you to implement the fine grained intersection test
between any two objects, this will only approximate the lookup based
on the container's internal acceleration structures.

See DO-PAIRS
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CHECK

CONTAINER
&REST

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
&REST

Clears the container and removes all objects from it.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

DESERIALIZE

CONTAINER
FILE
ID->OBJECT
&REST

Deserialize CONTAINER from FILE.

ID->OBJECT is called for every object that was added to the container
that was used to serialize to the given file. The function should
accept the strings that were previously returned by OBJECT->ID and
return the corresponding object.

It is expected that the size and location of the returned objects is
the same as it was when SERIALIZE was called. Or in other words, it is
still up to you to ensure object properties are persisted separately
or that the container is updated appropriately after deserialization.

Consequences are undefined if the function returns NIL, or the same
(EQ) object for two different (EQUAL) IDs, or returning different
objects for the same (EQUAL) IDS.

See SERIALIZE
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

ENSURE-REGION

OBJECT
&OPTIONAL
REGION
&REST

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
&REST

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

GROUP

OBJECT
&REST

Returns NIL or an arbitrary designator for the group of objects that the object is part of.

NIL indicates that the object is not part of any group.

Objects within a group, that is objects for which this function
returns an EQ value, are not considered as potential pairs by
CALL-WITH-PAIRS.

The primary use-case for this mechanism are higher-level objects that
are composed of primitive objects. In the context of collision
detection, the primitives that make up a higher-level object are not
supposed to collide with each other. Eliminating such pairs in
CALL-WITH-PAIRS based on the group is more efficient than having the
client do it and also allows additional optimizations in the
acceleration structure.

See CALL-WITH-PAIRS

EXTERNAL GENERIC-FUNCTION

LEAVE

OBJECT
CONTAINER
&REST

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
&REST

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
See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX
See BOUNDING-SPHERE

EXTERNAL GENERIC-FUNCTION

OBJECT-COUNT

CONTAINER
&REST

Computes the number of objects in the container.

Note that this is usually not a constant-time operation.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

ORIENTED-BOUNDING-BOX

OBJECT
&REST

Returns an oriented bounding box for the object.

Returns three values, a VEC3 for the center, a VEC3 for the half-size
of the box, and a quaternion for orienting the box.

If unimplemented, this will return LOCATION and BSIZE of the object,
and a unit quaternion.

See BOUNDING-SPHERE
See BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

RADIUS

OBJECT
&REST

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
See BOUNDING-SPHERE

EXTERNAL GENERIC-FUNCTION

REOPTIMIZE

CONTAINER
&KEY
LOCATION
BSIZE
CELL-SIZE
ROUNDS
&REST

Reoptimizes the container to fit its objects better.

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

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

SERIALIZE

CONTAINER
FILE
OBJECT->ID
&REST

Serialise CONTAINER to FILE.

OBJECT->ID is called for every object that was added to the container
during the serialisation process. Value returned from the function
must be a string.

Consequences are undefined if the function returns the same (EQUAL)
ID string for two different (EQ) objects, or returns different (EQUAL)
ID strings for the same (EQ) object.

See DESERIALIZE
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

UPDATE

OBJECT
CONTAINER
&REST

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
&REST

&BODY
BODY
&REST

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-CANDIDATES

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over objects that approximate overlap the region.

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

See CALL-WITH-CANDIDATES

EXTERNAL MACRO

DO-CONTAINED

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

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-INTERSECTING

ELEMENT
CONTAINER
RAY-ORIGIN
RAY-DIRECTION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over objects intersecting the ray.

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

See CALL-WITH-INTERSECTING

EXTERNAL MACRO

DO-OVERLAPPING

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

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

EXTERNAL MACRO

DO-PAIRS

A
B
CONTAINER
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over pairs of overlapping objects.

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

See CALL-WITH-PAIRS

ORG.SHIRAKUMO.FRAF.TRIAL.SPACE.KD-TREE

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 OBJECT-COUNT
See ENTER
See LEAVE
See UPDATE
See CALL-WITH-ALL
See CALL-WITH-CONTAINED
See CALL-WITH-OVERLAPPING

EXTERNAL STRUCTURE

KD-TREE

A k-dimensional tree

This is not a fully generalised implementation and is restricted to
either 1, 2, or 3 dimensions. You can also specify the maximum tree
depth and default splitting size to optimise the tree structure.

See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:CONTAINER
See MAKE-KD-TREE
See KD-TREE-INSERT
See KD-TREE-REMOVE
See KD-TREE-NEAREST
See KD-TREE-K-NEAREST
See KD-TREE-CALL-WITH-NEAREST
See QUADTREE (type)

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 STRUCTURE
SPHERE
Source
No documentation provided.

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
&REST

Returns true if the given object is a container instance.

See CONTAINER (type)

EXTERNAL FUNCTION

FIND-REGION

OBJECTS
&REST

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

KD-TREE-CALL-WITH-NEAREST

FUNCTION
LOCATION
TREE
&REST

Iteratively find the nearest objects to a location

Calls FUNCTION with objects that iteratively lie closer to the
LOCATION and that object's current squared distance to the target
location. The FUNCTION must return a new radius to use to narrow the
search.

See KD-TREE-NEAREST
See KD-TREE-K-NEAREST
See KD-TREE (type)

EXTERNAL FUNCTION

KD-TREE-INSERT

OBJECT
TREE
&REST

Fast track for ENTER.

See KD-TREE (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:ENTER

EXTERNAL FUNCTION

KD-TREE-K-NEAREST

K
LOCATION
TREE
&KEY
TEST
&REST

Find the K nearest objects to a location

You may also specify TEST, which should be a function of one argument
that returns true if the candidate object passed in should be
considered a neighbour or not.

Returns two values:
- A simple-vector of size K containing the nearest objects in order
  of nearest to farthest.
- A counter of how many entries in the vector are set.

See KD-TREE-NEAREST
See KD-TREE-CALL-WITH-NEAREST
See KD-TREE (type)

EXTERNAL FUNCTION

KD-TREE-NEAREST

LOCATION
TREE
&KEY
TEST
MAX-RADIUS
&REST

Find the nearest object to a location

You may also specify REJECT to ensure that the object you're searching
a nearest neighbour to isn't itself selected.

If MAX-RADIUS is specified, the closest candidate is only returned if
it is within MAX-RADIUS to the location.

See KD-TREE-K-NEAREST
See KD-TREE-CALL-WITH-NEAREST
See KD-TREE (type)

EXTERNAL FUNCTION

KD-TREE-REMOVE

OBJECT
TREE
&REST

Fast track for LEAVE.

See KD-TREE (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:LEAVE

EXTERNAL FUNCTION

MAKE-KD-TREE

&KEY
DIMENSIONS
SPLIT-SIZE
MAX-DEPTH
&REST

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 KD-TREE (type)

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

EXTERNAL FUNCTION

REGION-CONTAINS-P

OBJECT
REGION
&REST

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
&REST

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
&REST

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
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
SPHERE
- X
- Y
- Z
- R
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
SPHERE-RADIUS
- INSTANCE
- &REST
Source
No documentation provided.
EXTERNAL FUNCTION
(SETF SPHERE-RADIUS)
- VALUE
- INSTANCE
- &REST
Source
No documentation provided.

EXTERNAL GENERIC-FUNCTION

BOUNDING-BOX

OBJECT
&REST

Returns an axis-aligned bounding box for the object.

Returns two values, a VEC3 for the center, and a VEC3 for the
half-size of the box.

If unimplemented, this will return LOCATION and BSIZE of the object.

See BOUNDING-SPHERE
See ORIENTED-BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

BOUNDING-SPHERE

OBJECT
&REST

Returns a bounding sphereg for the object.

Returns two values, a VEC3 for the center, and a radius for the
sphere.

If unimplemented, this will return LOCATION and RADIUS of the object.

See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

BSIZE

OBJECT
&REST

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
See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX

EXTERNAL GENERIC-FUNCTION

CALL-WITH-ALL

FUNCTION
CONTAINER
&REST

Calls FUNCTION with every object contained in CONTAINER.

See DO-ALL
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CALL-WITH-CANDIDATES

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object which approximately overlaps REGION.

The region is coerced to a region via ENSURE-REGION.

FUNCTION *may* be called with any object contained in
CONTAINER. However, depending on the type of CONTAINER, the set of
objects with which FUNCTION is actually called is usually a moderate
superset of the objects that in CONTAINER that overlap REGION.

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

EXTERNAL GENERIC-FUNCTION

CALL-WITH-CONTAINED

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object contained in REGION.

The region is coerced to a region via ENSURE-REGION.
The function *will* be called with objects that lie entirely inside the
specified region. The function *may* be called with objects that
overlap but do not lie entirely inside the region. The function *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-INTERSECTING

FUNCTION
CONTAINER
RAY-ORIGIN
RAY-DIRECTION
&REST

Calls FUNCTION with every object that *may* intersect the ray.

It is up to you to implement the fine grained intersection test
between the ray and the object, this will only approximate the lookup
based on the container's internal acceleration structures.

Depending on the container, RAY-ORIGIN and RAY-DIRECTION should be
either VEC3s or VEC2s.

See DO-INTERSECTING
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CALL-WITH-OVERLAPPING

FUNCTION
CONTAINER
REGION
&REST

Calls FUNCTION with every object which overlaps REGION.

The region is coerced to a region via ENSURE-REGION.
The function *will* be called with objects that overlap the specified
region (including objects that lie entirely inside the region). The
function *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

CALL-WITH-PAIRS

FUNCTION
CONTAINER
&REST

Calls FUNCTION with all pairs of overlapping objects.

The function will be called with all pairs of objects that overlap
each other according to the container's internal bounding volume of
the objects.

It is up to you to implement the fine grained intersection test
between any two objects, this will only approximate the lookup based
on the container's internal acceleration structures.

See DO-PAIRS
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

CHECK

CONTAINER
&REST

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
&REST

Clears the container and removes all objects from it.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

DESERIALIZE

CONTAINER
FILE
ID->OBJECT
&REST

Deserialize CONTAINER from FILE.

ID->OBJECT is called for every object that was added to the container
that was used to serialize to the given file. The function should
accept the strings that were previously returned by OBJECT->ID and
return the corresponding object.

It is expected that the size and location of the returned objects is
the same as it was when SERIALIZE was called. Or in other words, it is
still up to you to ensure object properties are persisted separately
or that the container is updated appropriately after deserialization.

Consequences are undefined if the function returns NIL, or the same
(EQ) object for two different (EQUAL) IDs, or returning different
objects for the same (EQUAL) IDS.

See SERIALIZE
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

ENSURE-REGION

OBJECT
&OPTIONAL
REGION
&REST

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
&REST

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

GROUP

OBJECT
&REST

Returns NIL or an arbitrary designator for the group of objects that the object is part of.

NIL indicates that the object is not part of any group.

Objects within a group, that is objects for which this function
returns an EQ value, are not considered as potential pairs by
CALL-WITH-PAIRS.

The primary use-case for this mechanism are higher-level objects that
are composed of primitive objects. In the context of collision
detection, the primitives that make up a higher-level object are not
supposed to collide with each other. Eliminating such pairs in
CALL-WITH-PAIRS based on the group is more efficient than having the
client do it and also allows additional optimizations in the
acceleration structure.

See CALL-WITH-PAIRS

EXTERNAL GENERIC-FUNCTION

LEAVE

OBJECT
CONTAINER
&REST

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
&REST

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
See BOUNDING-BOX
See ORIENTED-BOUNDING-BOX
See BOUNDING-SPHERE

EXTERNAL GENERIC-FUNCTION

OBJECT-COUNT

CONTAINER
&REST

Computes the number of objects in the container.

Note that this is usually not a constant-time operation.

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

ORIENTED-BOUNDING-BOX

OBJECT
&REST

Returns an oriented bounding box for the object.

Returns three values, a VEC3 for the center, a VEC3 for the half-size
of the box, and a quaternion for orienting the box.

If unimplemented, this will return LOCATION and BSIZE of the object,
and a unit quaternion.

See BOUNDING-SPHERE
See BOUNDING-BOX
See LOCATION
See BSIZE

EXTERNAL GENERIC-FUNCTION

RADIUS

OBJECT
&REST

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
See BOUNDING-SPHERE

EXTERNAL GENERIC-FUNCTION

REOPTIMIZE

CONTAINER
&KEY
LOCATION
BSIZE
CELL-SIZE
ROUNDS
&REST

Reoptimizes the container to fit its objects better.

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

See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

SERIALIZE

CONTAINER
FILE
OBJECT->ID
&REST

Serialise CONTAINER to FILE.

OBJECT->ID is called for every object that was added to the container
during the serialisation process. Value returned from the function
must be a string.

Consequences are undefined if the function returns the same (EQUAL)
ID string for two different (EQ) objects, or returns different (EQUAL)
ID strings for the same (EQ) object.

See DESERIALIZE
See CONTAINER (type)

EXTERNAL GENERIC-FUNCTION

UPDATE

OBJECT
CONTAINER
&REST

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
&REST

&BODY
BODY
&REST

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-CANDIDATES

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over objects that approximate overlap the region.

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

See CALL-WITH-CANDIDATES

EXTERNAL MACRO

DO-CONTAINED

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

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-INTERSECTING

ELEMENT
CONTAINER
RAY-ORIGIN
RAY-DIRECTION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over objects intersecting the ray.

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

See CALL-WITH-INTERSECTING

EXTERNAL MACRO

DO-OVERLAPPING

ELEMENT
CONTAINER
REGION
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

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

EXTERNAL MACRO

DO-PAIRS

A
B
CONTAINER
&OPTIONAL
RESULT
&REST

&BODY
BODY
&REST

Convenience macro to iterate over pairs of overlapping objects.

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

See CALL-WITH-PAIRS