This is the 3d-spaces Reference Manual, version 1.0.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Feb 26 14:29:06 2024 GMT+0.
The main system appears first, followed by any subsystem dependency.
3d-spacesA library implementing spatial query structures
Yukari Hafner <shinmera@tymoon.eu>
Yukari Hafner <shinmera@tymoon.eu>
(GIT https://github.com/shirakumo/3d-spaces.git)
zlib
1.0.0
documentation-utils (system).
3d-math (system).
trivial-extensible-sequences (system).
for (system).
package.lisp (file).
toolkit.lisp (file).
protocol.lisp (file).
bvh2.lisp (file).
quadtree.lisp (file).
grid3.lisp (file).
kd-tree.lisp (file).
documentation.lisp (file).
Files are sorted by type and then listed depth-first from the systems components trees.
3d-spaces/3d-spaces.asd3d-spaces/package.lisp3d-spaces/toolkit.lisp3d-spaces/protocol.lisp3d-spaces/bvh2.lisp3d-spaces/quadtree.lisp3d-spaces/grid3.lisp3d-spaces/kd-tree.lisp3d-spaces/documentation.lisp3d-spaces/toolkit.lisppackage.lisp (file).
3d-spaces (system).
clamp (function).
ensure-function (function).
3d-spaces/protocol.lisptoolkit.lisp (file).
3d-spaces (system).
bsize (generic function).
call-with-all (generic function).
call-with-candidates (generic function).
call-with-contained (generic function).
call-with-intersecting (generic function).
call-with-overlapping (generic function).
check (generic function).
clear (generic function).
container (structure).
container-p (function).
deserialize (generic function).
do-all (macro).
do-candidates (macro).
do-contained (macro).
do-intersecting (macro).
do-overlapping (macro).
ensure-region (generic function).
enter (generic function).
find-region (function).
leave (generic function).
location (generic function).
make-load-form (method).
make-load-form (method).
object-count (generic function).
print-object (method).
print-object (method).
radius (generic function).
region (function).
region (structure).
region-contains-p (function).
region-overlaps-p (function).
region-size (reader).
(setf region-size) (writer).
reoptimize (generic function).
serialize (generic function).
sphere (function).
sphere (structure).
sphere-radius (reader).
(setf sphere-radius) (writer).
update (generic function).
%region (function).
%sphere (function).
+ray-intersection-scan-extent+ (constant).
describe-tree (function).
dserialize (method).
ray-intersects-box-p (function).
ray-scan-region (function).
region-varr3 (function).
(setf region-varr3) (function).
sphere-varr3 (function).
(setf sphere-varr3) (function).
with-region (macro).
3d-spaces/bvh2.lispprotocol.lisp (file).
3d-spaces (system).
bvh (structure).
bvh-insert (function).
bvh-lines (function).
bvh-remove (function).
bvh-update (function).
call-with-all (method).
call-with-contained (method).
call-with-overlapping (method).
check (method).
clear (method).
describe-object (method).
enter (method).
leave (method).
make-bvh (function).
make-iterator (method).
print-object (method).
reoptimize (method).
step-functions (method).
step-functions (method).
update (method).
%make-bvh-node (function).
better-fit (function).
bvh-iterator (structure).
bvh-iterator-bvh (reader).
(setf bvh-iterator-bvh) (writer).
bvh-iterator-region (reader).
(setf bvh-iterator-region) (writer).
bvh-node (structure).
bvh-node-d (reader).
(setf bvh-node-d) (writer).
bvh-node-l (reader).
(setf bvh-node-l) (writer).
bvh-node-o (reader).
(setf bvh-node-o) (writer).
bvh-node-p (reader).
(setf bvh-node-p) (writer).
bvh-node-r (reader).
(setf bvh-node-r) (writer).
bvh-node-varr4 (function).
(setf bvh-node-varr4) (function).
bvh-refit (function).
bvh-root (reader).
(setf bvh-root) (writer).
bvh-table (reader).
(setf bvh-table) (writer).
cost (function).
make-bvh-iterator (function).
make-bvh-node-for (function).
node-contains-p (function).
node-contains-p* (function).
node-cost (function).
node-find-best-reinsertion-position (function).
node-fit (function).
node-insert (function).
node-overlaps-p (function).
node-priority (function).
node-refit (function).
node-refit-object (function).
node-reinsert-to-best (function).
node-remove (function).
node-remove-and-reinsert (function).
node-sibling (function).
node-split (function).
node-sub-p (function).
node-transfer (function).
perimiter-heuristic (function).
set-depth (function).
3d-spaces/quadtree.lispbvh2.lisp (file).
3d-spaces (system).
call-with-all (method).
call-with-contained (method).
call-with-overlapping (method).
check (method).
clear (method).
describe-object (method).
enter (method).
leave (method).
make-iterator (method).
make-quadtree (function).
make-quadtree-at (function).
print-object (method).
quadtree (structure).
quadtree-find-all (function).
quadtree-find-contained (function).
quadtree-find-contained-in (function).
quadtree-find-for (function).
quadtree-find-overlaps (function).
quadtree-find-overlaps-in (function).
quadtree-insert (function).
quadtree-lines (function).
quadtree-remove (function).
quadtree-update (function).
reoptimize (method).
step-functions (method).
update (method).
%%make-quadtree-node (function).
%make-quadtree-node (function).
%region-contains-p (function).
%region-overlaps-p (function).
ensure-child-nodes (function).
for-node-active-children (macro).
for-node-children (macro).
make-object-vector (function).
make-quadtree-iterator (function).
node-active-children (function).
node-active-children-p (function).
node-active-p (function).
node-check-activity (function).
node-children (function).
node-clear (function).
node-clear-objects (function).
node-direction (function).
node-direction* (function).
node-empty-p (function).
node-extend (function).
node-find (function).
node-find-all (function).
node-increase-depth (function).
node-insert (function).
node-insert-extend (function).
node-pop-objects (function).
node-push-objects-into (function).
node-remove (function).
node-remove-children (function).
node-reorder (function).
node-set-min-size (function).
node-set-threshold (function).
node-split (function).
quadtree-iterator (structure).
quadtree-iterator-contain-p (reader).
(setf quadtree-iterator-contain-p) (writer).
quadtree-iterator-region (reader).
(setf quadtree-iterator-region) (writer).
quadtree-iterator-tree (reader).
(setf quadtree-iterator-tree) (writer).
quadtree-node (structure).
quadtree-node-active-p (reader).
(setf quadtree-node-active-p) (writer).
quadtree-node-bottom-left (reader).
(setf quadtree-node-bottom-left) (writer).
quadtree-node-bottom-right (reader).
(setf quadtree-node-bottom-right) (writer).
quadtree-node-depth (reader).
(setf quadtree-node-depth) (writer).
quadtree-node-min-size (reader).
(setf quadtree-node-min-size) (writer).
quadtree-node-objects (reader).
(setf quadtree-node-objects) (writer).
quadtree-node-parent (reader).
(setf quadtree-node-parent) (writer).
quadtree-node-threshold (reader).
(setf quadtree-node-threshold) (writer).
quadtree-node-top-left (reader).
(setf quadtree-node-top-left) (writer).
quadtree-node-top-right (reader).
(setf quadtree-node-top-right) (writer).
quadtree-node-varr4 (function).
(setf quadtree-node-varr4) (function).
quadtree-root (reader).
(setf quadtree-root) (writer).
quadtree-table (reader).
(setf quadtree-table) (writer).
region-contains-area-p (function).
region-contains-object-p (function).
region-overlaps-area-p (function).
region-overlaps-object-p (function).
with-node-children (macro).
3d-spaces/grid3.lispquadtree.lisp (file).
3d-spaces (system).
bsize (method).
call-with-all (method).
call-with-candidates (method).
call-with-contained (method).
call-with-intersecting (method).
call-with-overlapping (method).
clear (method).
enter (method).
grid (structure).
grid-insert (function).
grid-move (function).
grid-remove (function).
grid-resize (function).
grid-update (function).
leave (method).
location (method).
make-grid (function).
print-object (method).
reoptimize (method).
update (method).
%make-grid (function).
%with-grid-coordinates (macro).
grid-cell (reader).
(setf grid-cell) (writer).
grid-d (reader).
(setf grid-d) (writer).
grid-data (reader).
(setf grid-data) (writer).
grid-h (reader).
(setf grid-h) (writer).
grid-location (reader).
(setf grid-location) (writer).
grid-table (reader).
(setf grid-table) (writer).
grid-w (reader).
(setf grid-w) (writer).
with-nesting (macro).
3d-spaces/kd-tree.lispgrid3.lisp (file).
3d-spaces (system).
call-with-all (method).
call-with-intersecting (method).
call-with-overlapping (method).
call-with-overlapping (method).
clear (method).
describe-object (method).
enter (method).
kd-tree (structure).
kd-tree-call-with-nearest (function).
kd-tree-insert (function).
kd-tree-k-nearest (function).
kd-tree-nearest (function).
kd-tree-remove (function).
leave (method).
make-kd-tree (function).
print-object (method).
print-object (method).
reoptimize (method).
%make-kd-tree (function).
%visit-bbox (function).
%visit-sphere (function).
kd-tree-dimensions (reader).
(setf kd-tree-dimensions) (writer).
kd-tree-max-depth (reader).
(setf kd-tree-max-depth) (writer).
kd-tree-root (reader).
(setf kd-tree-root) (writer).
kd-tree-split-size (reader).
(setf kd-tree-split-size) (writer).
make-node (function).
node (structure).
node-axis (reader).
(setf node-axis) (writer).
node-children (reader).
(setf node-children) (writer).
node-far (reader).
(setf node-far) (writer).
node-near (reader).
(setf node-near) (writer).
node-position (reader).
(setf node-position) (writer).
node-tree-depth (reader).
(setf node-tree-depth) (writer).
recompute-subtree (function).
split-node (function).
split-node-axis (function).
sqrdist (function).
transfer-node (function).
visit-bbox (function).
visit-sphere (function).
with-array (macro).
3d-spaces/documentation.lispkd-tree.lisp (file).
3d-spaces (system).
Packages are listed by definition order.
org.shirakumo.fraf.trial.spaceorg.shirakumo.fraf.trial.space.bvh2org.shirakumo.fraf.trial.space.kd-treeorg.shirakumo.fraf.trial.space.grid3org.shirakumo.fraf.trial.space.quadtreeorg.shirakumo.fraf.trial.spacecommon-lisp.
org.shirakumo.fraf.math.
bsize (generic function).
call-with-all (generic function).
call-with-candidates (generic function).
call-with-contained (generic function).
call-with-intersecting (generic function).
call-with-overlapping (generic function).
check (generic function).
clear (generic function).
container (structure).
container-p (function).
deserialize (generic function).
do-all (macro).
do-candidates (macro).
do-contained (macro).
do-intersecting (macro).
do-overlapping (macro).
ensure-region (generic function).
enter (generic function).
find-region (function).
leave (generic function).
location (generic function).
location (slot).
object-count (generic function).
radius (generic function).
region (function).
region (structure).
region (slot).
region (slot).
region-contains-p (function).
region-overlaps-p (function).
region-size (reader).
(setf region-size) (writer).
reoptimize (generic function).
serialize (generic function).
sphere (function).
sphere (structure).
sphere-radius (reader).
(setf sphere-radius) (writer).
update (generic function).
%region (function).
%sphere (function).
+ray-intersection-scan-extent+ (constant).
clamp (function).
describe-tree (function).
dserialize (generic function).
ensure-function (function).
ray-intersects-box-p (function).
ray-scan-region (function).
region-varr3 (function).
(setf region-varr3) (function).
sphere-varr3 (function).
(setf sphere-varr3) (function).
with-region (macro).
org.shirakumo.fraf.trial.space.bvh2common-lisp.
org.shirakumo.fraf.math.
org.shirakumo.fraf.trial.space.
bvh (structure).
bvh-insert (function).
bvh-lines (function).
bvh-remove (function).
bvh-update (function).
make-bvh (function).
%make-bvh-node (function).
better-fit (function).
bvh-iterator (structure).
bvh-iterator-bvh (reader).
(setf bvh-iterator-bvh) (writer).
bvh-iterator-region (reader).
(setf bvh-iterator-region) (writer).
bvh-node (structure).
bvh-node-d (reader).
(setf bvh-node-d) (writer).
bvh-node-l (reader).
(setf bvh-node-l) (writer).
bvh-node-o (reader).
(setf bvh-node-o) (writer).
bvh-node-p (reader).
(setf bvh-node-p) (writer).
bvh-node-r (reader).
(setf bvh-node-r) (writer).
bvh-node-varr4 (function).
(setf bvh-node-varr4) (function).
bvh-refit (function).
bvh-root (reader).
(setf bvh-root) (writer).
bvh-table (reader).
(setf bvh-table) (writer).
cost (function).
make-bvh-iterator (function).
make-bvh-node-for (function).
node-contains-p (function).
node-contains-p* (function).
node-cost (function).
node-find-best-reinsertion-position (function).
node-fit (function).
node-insert (function).
node-overlaps-p (function).
node-priority (function).
node-refit (function).
node-refit-object (function).
node-reinsert-to-best (function).
node-remove (function).
node-remove-and-reinsert (function).
node-sibling (function).
node-split (function).
node-sub-p (function).
node-transfer (function).
perimiter-heuristic (function).
set-depth (function).
org.shirakumo.fraf.trial.space.kd-treecommon-lisp.
org.shirakumo.fraf.math.
org.shirakumo.fraf.trial.space.
kd-tree (structure).
kd-tree-call-with-nearest (function).
kd-tree-insert (function).
kd-tree-k-nearest (function).
kd-tree-nearest (function).
kd-tree-remove (function).
make-kd-tree (function).
%make-kd-tree (function).
%visit-bbox (function).
%visit-sphere (function).
kd-tree-dimensions (reader).
(setf kd-tree-dimensions) (writer).
kd-tree-max-depth (reader).
(setf kd-tree-max-depth) (writer).
kd-tree-root (reader).
(setf kd-tree-root) (writer).
kd-tree-split-size (reader).
(setf kd-tree-split-size) (writer).
make-node (function).
node (structure).
node-axis (reader).
(setf node-axis) (writer).
node-children (reader).
(setf node-children) (writer).
node-far (reader).
(setf node-far) (writer).
node-near (reader).
(setf node-near) (writer).
node-position (reader).
(setf node-position) (writer).
node-tree-depth (reader).
(setf node-tree-depth) (writer).
recompute-subtree (function).
split-node (function).
split-node-axis (function).
sqrdist (function).
transfer-node (function).
visit-bbox (function).
visit-sphere (function).
with-array (macro).
org.shirakumo.fraf.trial.space.grid3common-lisp.
org.shirakumo.fraf.math.
org.shirakumo.fraf.trial.space.
grid (structure).
grid-insert (function).
grid-move (function).
grid-remove (function).
grid-resize (function).
grid-update (function).
make-grid (function).
%make-grid (function).
%with-grid-coordinates (macro).
grid-cell (reader).
(setf grid-cell) (writer).
grid-d (reader).
(setf grid-d) (writer).
grid-data (reader).
(setf grid-data) (writer).
grid-h (reader).
(setf grid-h) (writer).
grid-location (reader).
(setf grid-location) (writer).
grid-table (reader).
(setf grid-table) (writer).
grid-w (reader).
(setf grid-w) (writer).
with-nesting (macro).
org.shirakumo.fraf.trial.space.quadtreecommon-lisp.
org.shirakumo.fraf.math.
org.shirakumo.fraf.trial.space.
make-quadtree (function).
make-quadtree-at (function).
quadtree (structure).
quadtree-find-all (function).
quadtree-find-contained (function).
quadtree-find-contained-in (function).
quadtree-find-for (function).
quadtree-find-overlaps (function).
quadtree-find-overlaps-in (function).
quadtree-insert (function).
quadtree-lines (function).
quadtree-remove (function).
quadtree-update (function).
%%make-quadtree-node (function).
%make-quadtree-node (function).
%region-contains-p (function).
%region-overlaps-p (function).
ensure-child-nodes (function).
for-node-active-children (macro).
for-node-children (macro).
make-object-vector (function).
make-quadtree-iterator (function).
node-active-children (function).
node-active-children-p (function).
node-active-p (function).
node-check-activity (function).
node-children (function).
node-clear (function).
node-clear-objects (function).
node-direction (function).
node-direction* (function).
node-empty-p (function).
node-extend (function).
node-find (function).
node-find-all (function).
node-increase-depth (function).
node-insert (function).
node-insert-extend (function).
node-pop-objects (function).
node-push-objects-into (function).
node-remove (function).
node-remove-children (function).
node-reorder (function).
node-set-min-size (function).
node-set-threshold (function).
node-split (function).
quadtree-iterator (structure).
quadtree-iterator-contain-p (reader).
(setf quadtree-iterator-contain-p) (writer).
quadtree-iterator-region (reader).
(setf quadtree-iterator-region) (writer).
quadtree-iterator-tree (reader).
(setf quadtree-iterator-tree) (writer).
quadtree-node (structure).
quadtree-node-active-p (reader).
(setf quadtree-node-active-p) (writer).
quadtree-node-bottom-left (reader).
(setf quadtree-node-bottom-left) (writer).
quadtree-node-bottom-right (reader).
(setf quadtree-node-bottom-right) (writer).
quadtree-node-depth (reader).
(setf quadtree-node-depth) (writer).
quadtree-node-min-size (reader).
(setf quadtree-node-min-size) (writer).
quadtree-node-objects (reader).
(setf quadtree-node-objects) (writer).
quadtree-node-parent (reader).
(setf quadtree-node-parent) (writer).
quadtree-node-threshold (reader).
(setf quadtree-node-threshold) (writer).
quadtree-node-top-left (reader).
(setf quadtree-node-top-left) (writer).
quadtree-node-top-right (reader).
(setf quadtree-node-top-right) (writer).
quadtree-node-varr4 (function).
(setf quadtree-node-varr4) (function).
quadtree-root (reader).
(setf quadtree-root) (writer).
quadtree-table (reader).
(setf quadtree-table) (writer).
region-contains-area-p (function).
region-contains-object-p (function).
region-overlaps-area-p (function).
region-overlaps-object-p (function).
with-node-children (macro).
Definitions are sorted by export status, category, package, and then by lexicographic order.
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
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
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
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
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
Fast track for ENTER.
See BVH (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:ENTER
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)
Fast track for LEAVE.
See BVH (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:LEAVE
Fast track for UPDATE.
See BVH (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:UPDATE
Returns true if the given object is a container instance.
See CONTAINER (type)
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)
Fast track for ENTER.
See GRID (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:ENTER
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)
Fast track for LEAVE.
See GRID (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:LEAVE
Resizes the grid to the specified half-size and cell size.
See GRID (type)
Fast track for UPDATE.
See GRID (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:UPDATE
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)
Fast track for ENTER.
See KD-TREE (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:ENTER
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)
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)
Fast track for LEAVE.
See KD-TREE (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:LEAVE
Creates a fresh BVH2.
See BVH (type)
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)
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)
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
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
Finds every object in the tree and pushes them into the passed
vector which is then returned.
See QUADTREE (type)
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
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
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
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
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
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
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)
Fast track for LEAVE. The holder node’s state is updated if
necessary.
See QUADTREE (type)
See ORG.SHIRAKUMO.FRAF.TRIAL.SPACE:LEAVE
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
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)
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)
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)
size.
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
Calls FUNCTION with every object contained in CONTAINER.
See DO-ALL
See CONTAINER (type)
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)
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)
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)
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)
Checks the container for validity.
Signals an error if there are problems with the container’s internal
invariants.
See CONTAINER (type)
Clears the container and removes all objects from it.
See CONTAINER (type)
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)
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)
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)
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)
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
Computes the number of objects in the container.
Note that this is usually not a constant-time operation.
See CONTAINER (type)
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
Reoptimizes the container to fit its objects better.
Each container type may accept specific arguments to control the
optimization.
See CONTAINER (type)
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)
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)
quadtree-node) stream) ¶bvh-iterator)) ¶for-iterator.
quadtree-iterator)) ¶for-iterator.
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
org.shirakumo.fraf.trial.space.bvh2::bvh-node
(org.shirakumo.fraf.trial.space.bvh2::%make-bvh-node (make-array 4 :element-type (quote single-float) :initial-element 0.0) 0 nil nil nil nil)
hash-table
(make-hash-table :test (quote eq))
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
structure-object.
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)
org.shirakumo.fraf.math.vectors:vec3
(org.shirakumo.fraf.math.vectors:vec 0 0 0)
(unsigned-byte 32)
0
(unsigned-byte 32)
0
(unsigned-byte 32)
0
single-float
0.0
simple-vector
#()
hash-table
(make-hash-table :test (quote eq))
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)
(unsigned-byte 8)
0
(unsigned-byte 8)
0
(unsigned-byte 8)
0
org.shirakumo.fraf.trial.space.kd-tree::node
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
org.shirakumo.fraf.trial.space.quadtree::quadtree-node
(org.shirakumo.fraf.trial.space.quadtree::%make-quadtree-node 0.0 0.0 100.0 100.0 0 1 1 nil nil nil nil nil)
hash-table
(make-hash-table :test (quote eq))
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
vec3.
org.shirakumo.fraf.math.vectors:vec3
vec3.
single-float
0.0
bvh.
d.
l.
o.
p.
r.
cell.
data.
root.
axis.
near.
tree.
root.
vec4.
(unsigned-byte 16)
0
(or null org.shirakumo.fraf.trial.space.bvh2::bvh-node)
(or null org.shirakumo.fraf.trial.space.bvh2::bvh-node)
(or null org.shirakumo.fraf.trial.space.bvh2::bvh-node)
structure-object.
(or null org.shirakumo.fraf.trial.space.kd-tree::node)
(or null org.shirakumo.fraf.trial.space.kd-tree::node)
(and (vector t) (not simple-vector))
(make-array 0 :adjustable t :fill-pointer t)
(unsigned-byte 8)
0
common-lisp.
single-float
0.0
(unsigned-byte 8)
0
vec4.
(unsigned-byte 32)
0
(unsigned-byte 16)
1
(unsigned-byte 16)
1
(or null org.shirakumo.fraf.trial.space.quadtree::quadtree-node)
(or null org.shirakumo.fraf.trial.space.quadtree::quadtree-node)
(or null org.shirakumo.fraf.trial.space.quadtree::quadtree-node)
(or null org.shirakumo.fraf.trial.space.quadtree::quadtree-node)
(or null org.shirakumo.fraf.trial.space.quadtree::quadtree-node)
boolean
(vector t)
(org.shirakumo.fraf.trial.space.quadtree::make-object-vector)
| Jump to: | %
(
B C D E F G K L M N O P Q R S T U V W |
|---|
| Jump to: | %
(
B C D E F G K L M N O P Q R S T U V W |
|---|
| Jump to: | +
A B C D F H L M N O P R S T W |
|---|
| Jump to: | +
A B C D F H L M N O P R S T W |
|---|
| Jump to: | 3
B C D F G K N O P Q R S T |
|---|
| Jump to: | 3
B C D F G K N O P Q R S T |
|---|