prefuse.util.force
Class NBodyForce

java.lang.Object
  prefuse.util.force.AbstractForce
      prefuse.util.force.NBodyForce

All Implemented Interfaces:

Force

public class NBodyForce
extends AbstractForce

Force function which computes an n-body force such as gravity, anti-gravity, or the results of electric charges. This function implements the the Barnes-Hut algorithm for efficient n-body force simulations, using a quad-tree with aggregated mass values to compute the n-body force in O(N log N) time, where N is the number of ForceItems.

The algorithm used is that of J. Barnes and P. Hut, in their research paper A Hierarchical O(n log n) force calculation algorithm, Nature, v.324, December 1986. For more details on the algorithm, see one of the following links --

• James Demmel's UC Berkeley lecture notes
• Description of the Barnes-Hut algorithm
• Joshua Barnes' recent implementation

Author:

jeffrey heer

Nested Class Summary

static class	NBodyForce.QuadTreeNode Represents a node in the quadtree.
static class	NBodyForce.QuadTreeNodeFactory Helper class to minimize number of object creations across multiple uses of the quadtree.

Field Summary

static int	BARNES_HUT_THETA
static float	DEFAULT_DISTANCE
static float	DEFAULT_GRAV_CONSTANT
static float	DEFAULT_MAX_DISTANCE
static float	DEFAULT_MAX_GRAV_CONSTANT
static float	DEFAULT_MAX_THETA
static float	DEFAULT_MIN_DISTANCE
static float	DEFAULT_MIN_GRAV_CONSTANT
static float	DEFAULT_MIN_THETA
static float	DEFAULT_THETA
static int	GRAVITATIONAL_CONST
static int	MIN_DISTANCE

Fields inherited from class prefuse.util.force.AbstractForce

maxValues, minValues, params

Constructor Summary

NBodyForce()
Create a new NBodyForce with default parameters.

NBodyForce(float gravConstant, float minDistance, float theta)
Create a new NBodyForce.

Method Summary

void	clear() Clears the quadtree of all entries.
void	getForce(ForceItem item) Calculates the force vector acting on the given item.
protected java.lang.String[]	getParameterNames()
void	init(ForceSimulator fsim) Initialize the simulation with the provided enclosing simulation.
void	insert(ForceItem item) Inserts an item into the quadtree.
boolean	isItemForce() Returns true.

Methods inherited from class prefuse.util.force.AbstractForce

getForce, getMaxValue, getMinValue, getParameter, getParameterCount, getParameterName, isSpringForce, setMaxValue, setMinValue, setParameter

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_GRAV_CONSTANT

public static final float DEFAULT_GRAV_CONSTANT

See Also:

Constant Field Values

DEFAULT_MIN_GRAV_CONSTANT

public static final float DEFAULT_MIN_GRAV_CONSTANT

See Also:

Constant Field Values

DEFAULT_MAX_GRAV_CONSTANT

public static final float DEFAULT_MAX_GRAV_CONSTANT

See Also:

Constant Field Values

DEFAULT_DISTANCE

public static final float DEFAULT_DISTANCE

See Also:

Constant Field Values

DEFAULT_MIN_DISTANCE

public static final float DEFAULT_MIN_DISTANCE

See Also:

Constant Field Values

DEFAULT_MAX_DISTANCE

public static final float DEFAULT_MAX_DISTANCE

See Also:

Constant Field Values

DEFAULT_THETA

public static final float DEFAULT_THETA

See Also:

Constant Field Values

DEFAULT_MIN_THETA

public static final float DEFAULT_MIN_THETA

See Also:

Constant Field Values

DEFAULT_MAX_THETA

public static final float DEFAULT_MAX_THETA

See Also:

Constant Field Values

GRAVITATIONAL_CONST

public static final int GRAVITATIONAL_CONST

See Also:

Constant Field Values

MIN_DISTANCE

public static final int MIN_DISTANCE

See Also:

Constant Field Values

BARNES_HUT_THETA

public static final int BARNES_HUT_THETA

See Also:

Constant Field Values

Constructor Detail

NBodyForce

public NBodyForce()

Create a new NBodyForce with default parameters.

NBodyForce

public NBodyForce(float gravConstant,
                  float minDistance,
                  float theta)

Create a new NBodyForce.

Parameters:

gravConstant - the gravitational constant to use. Nodes will attract each other if this value is positive, and will repel each other if it is negative.

minDistance - the distance within which two particles will interact. If -1, the value is treated as infinite.

theta - the Barnes-Hut parameter theta, which controls when an aggregated mass is used rather than drilling down to individual item mass values.

Method Detail

isItemForce

public boolean isItemForce()

Returns true.

Specified by:

isItemForce in interface Force

Overrides:

isItemForce in class AbstractForce

Returns:

true if this force function processes Force instances

See Also:

Force.isItemForce()

getParameterNames

protected java.lang.String[] getParameterNames()

Specified by:

getParameterNames in class AbstractForce

See Also:

AbstractForce.getParameterNames()

clear

public void clear()

Clears the quadtree of all entries.

init

public void init(ForceSimulator fsim)

Initialize the simulation with the provided enclosing simulation. After this call has been made, the simulation can be queried for the n-body force acting on a given item.

Specified by:

init in interface Force

Overrides:

init in class AbstractForce

Parameters:

fsim - the enclosing ForceSimulator

insert

public void insert(ForceItem item)

Inserts an item into the quadtree.

Parameters:

item - the ForceItem to add.

Throws:

java.lang.IllegalStateException - if the current location of the item is outside the bounds of the quadtree

getForce

public void getForce(ForceItem item)

Calculates the force vector acting on the given item.

Specified by:

getForce in interface Force

Overrides:

getForce in class AbstractForce

Parameters:

item - the ForceItem for which to compute the force

See Also:

Force.getForce(prefuse.util.force.ForceItem)