org.jcae.mesh.amibe.util
Class KdTree

java.lang.Object
  org.jcae.mesh.amibe.util.KdTree

public class KdTree
extends java.lang.Object

Quadtree structure to store 2D vertices. When adjacent relations have not yet been set, a quadtree is an efficient way to locate a point among a set of points and triangles.

Integer coordinates are used for two reasons: a better control on accuracy of geometrical operations, and simpler operations on vertex location because cells have power of two side length and bitwise operators can be used instead of floating point operations. The downside is that the conversion between double and integer coordinates must be known in advance, which is why constructor needs a bounding box as argument.

Each KdTree.Cell contains either vertices or four children nodes (some of them may be null). A cell can contain at most BUCKETSIZE vertices (default is 10). When this number is exceeded, the cell is splitted and vertices are stored in these children. On the contrary, when all vertices are removed from a cell, it is deleted. And when all children of a cell are null, this cell is removed.

Quadtree cells are very compact, they do not contain any locational information. It is instead passed to the KdTreeProcedure.action(Object, int, int[]) method. This design had been chosen for performance reasons on large meshes, and in practice it works very well because quadtrees are used for vertex location, and no neighbourhood information is needed.

Quadtree traversal is performed by the walk(KdTreeProcedure) method. Here is an example to collect all vertices in a list:

        public final class collectAllVerticesProcedure implements KdTreeProcedure
        {
                public Collection vertexList = new ArrayList();
                public final int action(Object o, int s, int [] i0)
                {
                        Cell self = (Cell) o;
                        if (self.nItems > 0)
                        {
                                for (int i = 0; i < self.nItems; i++)
                                        vertexList.add((Vertex) self.subCell[i]);
                        }
                        return KdTreeProcedure.OK;
                }
        }
 

This procedure is applied on all cells recursively in prefix order. If it returns KdTreeProcedure.ABORT, walk(KdTreeProcedure) aborts its processing immediately; KdTreeProcedure.OK return value means that processing can continue normally, and KdTreeProcedure.SKIPCHILD return value means that children nodes are skipped.

Distances between vertices can be computed either in Euclidian 2D space, or with a Riemannian metrics. This is controlled by the Mesh2D.pushCompGeom(int) method. Distances are computed in Euclidian 2D space when its argument is an instance of Calculus2D, and in Riemannian metrics (see Metric2D) when it is an instance of Calculus3D. By default, distances are computed in Euclidian 2D space.

In Euclidian 2D space, vertices which have a distance to a point p lower than d are contained in a circle centered at p with radius d. With Riemannian metrics, this circle becomes an ellipsis. This ellipsis is only determined by local properties of the surface at point p. If we already found a point V1 at a distance d1, vertices which belong to a quadtree cell not intersecting this ellipsis do not need to be considered.

Below is an algorithm to find the nearest vertex in the quadtree of a given point p:

1. Initialization: dmin=Double.MAX_VALUE, result=null
2. Traverse all quadtree cells.
   1. If this cell does not intersect the ellipsis centered at p of vertices at a distance lower than dmin, then skip this cell and its children.
   2. Otherwise, if this cell contains children nodes, do nothing so that processaing continues normally on children nodes.
   3. Otherwise, this cell contains vertices. For each vertex, compute its distance to p and update dmin and result if it is nearer than the current solution.

The implementation of getNearestVertex(Mesh, Vertex) has two differences:

• The starting point is computed by getNearVertex(Mesh, Vertex). This means that much more cells are skipped.
• The ellipsis is replaced by a circle enclosing it, to have simpler calculus. Using the real ellipsis could be tested though, it should also speed up this processing.

Nested Class Summary

class

KdTree.Cell

Field Summary

int	nCells Number of cells.
protected KdTree.Cell	root Root of the kd-tree.
double[]	x0 Conversion between double and integer coordinates.

Constructor Summary

KdTree(double[] bbox)
Create a new KdTree of the desired size.

KdTree(double[] bbox, int bucketsize)
Create a new KdTree of the desired size.

KdTree(int d)
Dummy constructor.

Method Summary

boolean	add(Vertex v) Add a vertex to the kd-tree.
double[]	center() Return the coordinates of the center of the grid.
void	double2int(double[] p, int[] i) Transform double coordinates into integer coordinates.
java.util.Collection<Vertex>	getAllVertices(int capacity) Return a collection of all vertices.
int	getMaxLevel()
Vertex	getNearestVertex(Mesh mesh, Vertex v) Return the nearest vertex stored in this Octree.
Vertex	getNearestVertexDebug(Mesh mesh, Vertex v) Slow implementation of getNearestVertex(Mesh, Vertex).
Vertex	getNearVertex(Mesh mesh, Vertex v) Return a stored element of the Octree which is near from a given vertex.
void	int2double(int[] i, double[] p) Transform integer coordinates into double coordinates.
void	remove(Vertex v) Remove a vertex from the kd-tree.
void	setup(double[] bbox) Computes x0 adapted to this bounding box.
boolean	walk(KdTreeProcedure proc) Perform an action on all cells in prefix order.

Methods inherited from class java.lang.Object

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

Field Detail

root

protected final KdTree.Cell root

Root of the kd-tree.

nCells

public int nCells

Number of cells.

x0

public final double[] x0

Conversion between double and integer coordinates.

Constructor Detail

KdTree

public KdTree(int d)

Dummy constructor. This instance must be properly initialised by calling setup(double[]) before putting elements into it.

Parameters:

d - dimension (2 or 3)

KdTree

public KdTree(double[] bbox)

Create a new KdTree of the desired size.

Parameters:

bbox - coordinates of bottom-left vertex and upper-right vertices

KdTree

public KdTree(double[] bbox,
              int bucketsize)

Create a new KdTree of the desired size.

Parameters:

bbox - coordinates of bottom-left vertex and upper-right vertices

bucketsize - bucket size

Method Detail

setup

public final void setup(double[] bbox)

Computes x0 adapted to this bounding box.

Parameters:

bbox - coordinates of bottom-left vertex and upper-right vertices

double2int

public void double2int(double[] p,
                       int[] i)

Transform double coordinates into integer coordinates.

Parameters:

p - double coordinates

i - integer coordinates

int2double

public void int2double(int[] i,
                       double[] p)

Transform integer coordinates into double coordinates.

Parameters:

i - integer coordinates

p - double coordinates

center

public double[] center()

Return the coordinates of the center of the grid.

Returns:

the coordinates of the center of the grid.

add

public boolean add(Vertex v)

Add a vertex to the kd-tree.

Parameters:

v - the vertex being added.

Returns:

true if cell was full and had to be split, false otherwise.

remove

public void remove(Vertex v)

Remove a vertex from the kd-tree.

Parameters:

v - the vertex being removed.

getAllVertices

public java.util.Collection<Vertex> getAllVertices(int capacity)

Return a collection of all vertices.

Parameters:

capacity - initial capacity of the Collection.

Returns:

a collection containing all vertices.

walk

public final boolean walk(KdTreeProcedure proc)

Perform an action on all cells in prefix order. The procedure is applied to the root cell, then recursively to its children. If it returns -1, processing aborts immediately and false is returned. If the procedure returns 1, cell children are not processed.

Parameters:

proc - procedure to apply on each cell.

Returns:

true if all cells have been traversed, false otherwise.

See Also:

KdTreeProcedure

getNearVertex

public final Vertex getNearVertex(Mesh mesh,
                                  Vertex v)

Return a stored element of the Octree which is near from a given vertex. The algorithm is simplistic: the leaf which would contains this node is retrieved. If it contains vertices, the nearest one is returned (vertices in other leaves may of course be nearer). Otherwise the nearest vertex from sibling children is returned. The returned vertex is a good starting point for getNearestVertex(Mesh, Vertex).

Parameters:

v - the node to check.

Returns:

a near vertex.

getNearestVertex

public final Vertex getNearestVertex(Mesh mesh,
                                     Vertex v)

Return the nearest vertex stored in this Octree.

Parameters:

v - the node to check.

Returns:

the nearest vertex.

getNearestVertexDebug

public Vertex getNearestVertexDebug(Mesh mesh,
                                    Vertex v)

Slow implementation of getNearestVertex(Mesh, Vertex). This method should be called only for debugging purpose.

Parameters:

v - the vertex to check.

Returns:

the nearest vertex.

getMaxLevel

public final int getMaxLevel()