com.threerings.tudey.space
Class HashSpace

java.lang.Object
  com.threerings.tudey.space.Space
      com.threerings.tudey.space.HashSpace

public class HashSpace
extends Space

A space that uses a hybrid spatial hashing/quadtree scheme to store elements.

Nested Class Summary

protected class	HashSpace.InternalNode<T extends SpaceObject> An internal node with (up to) four children.
protected class	HashSpace.LeafNode<T extends SpaceObject> A leaf node.
protected class	HashSpace.Node<T extends SpaceObject> Represents a node in a quadtree.

Field Summary

protected Rect	_bounds The bounds of the roots (does not include the oversized objects).
protected Coord	_coord A reusable coord object for queries.
protected HashMap<Coord,HashSpace.Node<SpaceElement>>	_elements The top level element nodes.
protected float	_granularity The size of the root nodes.
protected List<HashSpace.InternalNode>	_internalNodePool A pool of internal nodes to reuse.
protected List<HashSpace.LeafNode>	_leafNodePool A pool of leaf nodes to reuse.
protected int	_levels The (maximum) number of tree levels.
protected Coord	_maxCoord The maximum coordinate.
protected Coord	_minCoord The minimum coordinate.
protected ArrayList<SpaceElement>	_oversizedElements Oversized elements.
protected Vector2f	_pt Reusable location vector.
protected Rect	_rect A reusable rect.
protected int	_visit The visit counter.

Fields inherited from class com.threerings.tudey.space.Space

_disposed, _result

Constructor Summary

HashSpace(float granularity, int levels)
Creates a new hash space.

Method Summary

protected <T extends SpaceObject> void	add(HashMap<Coord,HashSpace.Node<T>> roots, ArrayList<T> oversized, T object) Adds the specified object to the provided map.
protected <T extends SpaceObject> void	addBounds(Coord coord, HashSpace.Node<T> node) Adds the bounds of the specified coordinate/node mapping.
protected <T extends SpaceObject> void	addBounds(HashMap<Coord,HashSpace.Node<T>> roots) Adds the bounds of the specified roots.
protected void	addToSpatial(SpaceElement element) Adds an element to the space's spatial data structure.
protected boolean	areOversized(Rect bounds) Determines whether the specified bounds qualify as "oversized" with respect to the scene granularity.
void	boundsDidChange(SpaceElement element) Notes that the specified space element's bounds have changed.
void	boundsWillChange(SpaceElement element) Notes that the specified space element's bounds are about to change.
protected <T extends SpaceObject> HashSpace.Node<T>	createRoot(int x, int y) Creates a root node for the specified coordinates.
void	getElements(Rect bounds, Collection<SpaceElement> results) Retrieves all space elements whose bounds intersect the provided region.
protected <T extends SpaceObject> HashSpace.InternalNode<T>	getFromInternalNodePool(int levels) Obtains an internal node through the pool.
protected <T extends SpaceObject> HashSpace.LeafNode<T>	getFromLeafNodePool() Obtains a leaf node through the pool.
protected <T extends SpaceObject> HashSpace.Node<T>	getFromNodePool(int levels) Returns an internal or leaf node from the pool as appropriate for the number of remaining levels.
protected <T extends SpaceObject> void	getIntersecting(HashMap<Coord,HashSpace.Node<T>> roots, ArrayList<T> oversized, Rect bounds, Collection<T> results) Adds all objects from the provided map that intersect the given bounds to the specified results list.
void	getIntersecting(Shape shape, com.google.common.base.Predicate<? super SpaceElement> filter, Collection<SpaceElement> results) Retrieves all space elements that intersect the provided shape.
SpaceElement	getIntersection(Ray2D ray, Vector2f location, com.google.common.base.Predicate<? super SpaceElement> filter) Checks for an intersection between the provided ray and the contents of the space.
protected int	getLevel(Rect bounds) Returns the level for the supplied bounds.
protected void	recomputeBounds() Recomputes the bounds of the roots.
protected <T extends SpaceObject> void	remove(HashMap<Coord,HashSpace.Node<T>> roots, ArrayList<T> oversized, T object) Removes the specified object from the provided map.
protected void	removeFromSpatial(SpaceElement element) Removes an element from the space's spatial data structure.

Methods inherited from class com.threerings.tudey.space.Space

add, dispose, getIntersecting, getIntersecting, getIntersecting, getIntersection, getIntersection, remove

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

_granularity

protected float _granularity

The size of the root nodes.

_levels

protected int _levels

The (maximum) number of tree levels.

_elements

protected HashMap<Coord,HashSpace.Node<SpaceElement>> _elements

The top level element nodes.

_oversizedElements

protected ArrayList<SpaceElement> _oversizedElements

Oversized elements.

_bounds

protected Rect _bounds

The bounds of the roots (does not include the oversized objects).

_minCoord

protected Coord _minCoord

The minimum coordinate.

_maxCoord

protected Coord _maxCoord

The maximum coordinate.

_visit

protected int _visit

The visit counter.

_coord

protected Coord _coord

A reusable coord object for queries.

_rect

protected Rect _rect

A reusable rect.

_pt

protected Vector2f _pt

Reusable location vector.

_internalNodePool

protected List<HashSpace.InternalNode> _internalNodePool

A pool of internal nodes to reuse.

_leafNodePool

protected List<HashSpace.LeafNode> _leafNodePool

A pool of leaf nodes to reuse.

Constructor Detail

HashSpace

public HashSpace(float granularity,
                 int levels)

Creates a new hash space.

Parameters:

granularity - the size of the top-level cells.

levels - the (maximum) number of quadtree levels.

Method Detail

getIntersection

public SpaceElement getIntersection(Ray2D ray,
                                    Vector2f location,
                                    com.google.common.base.Predicate<? super SpaceElement> filter)

Description copied from class: Space

Checks for an intersection between the provided ray and the contents of the space.

Specified by:

getIntersection in class Space

location - a vector to populate with the location of the intersection, if any.

filter - a predicate to use in filtering the results of the test.

Returns:

a reference to the first element intersected by the ray, or null for none.

getIntersecting

public void getIntersecting(Shape shape,
                            com.google.common.base.Predicate<? super SpaceElement> filter,
                            Collection<SpaceElement> results)

Description copied from class: Space

Retrieves all space elements that intersect the provided shape.

Specified by:

getIntersecting in class Space

results - a collection to hold the results of the search.

getElements

public void getElements(Rect bounds,
                        Collection<SpaceElement> results)

Description copied from class: Space

Retrieves all space elements whose bounds intersect the provided region.

Specified by:

getElements in class Space

results - a list to hold the results of the search.

boundsWillChange

public void boundsWillChange(SpaceElement element)

Description copied from class: Space

Notes that the specified space element's bounds are about to change. Will be followed by a call to Space.boundsDidChange(SpaceElement) when the change has been effected.

Overrides:

boundsWillChange in class Space

boundsDidChange

public void boundsDidChange(SpaceElement element)

Description copied from class: Space

Notes that the specified space element's bounds have changed.

Overrides:

boundsDidChange in class Space

addToSpatial

protected void addToSpatial(SpaceElement element)

Description copied from class: Space

Adds an element to the space's spatial data structure.

Specified by:

addToSpatial in class Space

removeFromSpatial

protected void removeFromSpatial(SpaceElement element)

Description copied from class: Space

Removes an element from the space's spatial data structure.

Specified by:

removeFromSpatial in class Space

add

protected <T extends SpaceObject> void add(HashMap<Coord,HashSpace.Node<T>> roots,
                                           ArrayList<T> oversized,
                                           T object)

Adds the specified object to the provided map.

remove

protected <T extends SpaceObject> void remove(HashMap<Coord,HashSpace.Node<T>> roots,
                                              ArrayList<T> oversized,
                                              T object)

Removes the specified object from the provided map.

areOversized

protected boolean areOversized(Rect bounds)

Determines whether the specified bounds qualify as "oversized" with respect to the scene granularity.

getIntersecting

protected <T extends SpaceObject> void getIntersecting(HashMap<Coord,HashSpace.Node<T>> roots,
                                                       ArrayList<T> oversized,
                                                       Rect bounds,
                                                       Collection<T> results)

Adds all objects from the provided map that intersect the given bounds to the specified results list.

getLevel

protected int getLevel(Rect bounds)

Returns the level for the supplied bounds.

createRoot

protected <T extends SpaceObject> HashSpace.Node<T> createRoot(int x,
                                                               int y)

Creates a root node for the specified coordinates.

recomputeBounds

protected void recomputeBounds()

Recomputes the bounds of the roots.

addBounds

protected <T extends SpaceObject> void addBounds(HashMap<Coord,HashSpace.Node<T>> roots)

Adds the bounds of the specified roots.

addBounds

protected <T extends SpaceObject> void addBounds(Coord coord,
                                                 HashSpace.Node<T> node)

Adds the bounds of the specified coordinate/node mapping.

getFromNodePool

protected <T extends SpaceObject> HashSpace.Node<T> getFromNodePool(int levels)

Returns an internal or leaf node from the pool as appropriate for the number of remaining levels.

getFromInternalNodePool

protected <T extends SpaceObject> HashSpace.InternalNode<T> getFromInternalNodePool(int levels)

Obtains an internal node through the pool.

getFromLeafNodePool

protected <T extends SpaceObject> HashSpace.LeafNode<T> getFromLeafNodePool()

Obtains a leaf node through the pool.