Package org.web3d.util.spatial

Class GridTrianglePartition

java.lang.Object

org.web3d.util.spatial.GridTrianglePartition

All Implemented Interfaces:

SpatialPartition

public class GridTrianglePartition
extends Object
implements SpatialPartition

A spatial structure using a grid pattern and triangle objects.

Version:

$Id: $

Author:

Alan Hudson

Field Summary

Fields

Modifier and Type	Field	Description
int	cellsFilled	How many cells have been filled by inserts
int	numInserts

Constructor Summary

Constructors

Constructor	Description
GridTrianglePartition(double voxelSize, int numVoxelsPerSide, int numTris)	Constructor.

Method Summary

Modifier and Type	Method	Description
protected void	calcBoundsForTriangle(Triangle tri, float[] min, float[] max)	Calculate a bounding box for a triangle.
void	clear()	Clear the structure of all data.
protected void	fillCells(int[] min, int[] max, Triangle tri)	Fill in the grid given a box of grid coordinates.
protected void	fillCellsExact(int[] min, int[] max, Triangle tri)	Fill in the grid given a box of grid coordinates.
void	findBoundsForTriangle(Triangle tri, int[] minCoords, int[] maxCoords)	Check the general interface contract in superclass method Geometry.doVoxelization.
int	findGridCoordsFromWorldCoords(float coord)	Find voxel grid coordinates for a given world coordinate
void	findGridCoordsFromWorldCoords(float[] coords, int[] pos)	Find voxel grid coordinates for a given world coordinate
void	findVoxelInWorldCoords(int x, int y, int z, float[] pos)	Find voxel world coordinates for a given voxel coordinate.
int[]	getObjects(int[] min, int[] max)	Gets the objects in the specified region.
int[]	getObjects(Region region)	Gets the objects in the specified region.
float[]	getTriangle(int id)	Get the triangle mapping for an id.
String	gridCountsToString()	Return the grid counts in strin form.
void	insert(Triangle[] tris, boolean useBounds)	Insert an array of Triangles.
void	insert(Triangle tri, boolean useBounds)	Insert an object into the structure.
boolean	intersectsTriangle(Vec3DDouble a, Vec3DDouble b, Vec3DDouble c, float[] pos)	Does triangle overlap a voxel.
void	printStats()

Methods inherited from class java.lang.Object

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

Field Details

cellsFilled

public int cellsFilled

How many cells have been filled by inserts

numInserts

public int numInserts

Constructor Details

GridTrianglePartition

public GridTrianglePartition(double voxelSize,
 int numVoxelsPerSide,
 int numTris)

Constructor.

Parameters:

voxelSize - The size of each voxel in meters.

numVoxelsPerSide - The number of voxels in each axis. Must be even.

numTris -

Method Details

clear

public void clear()

Clear the structure of all data.

Specified by:

clear in interface SpatialPartition

getObjects

public int[] getObjects(Region region)

Gets the objects in the specified region. Any object which is contained or overlaps the region will be returned. Objects exactly on a voxel boundary shall be returned in all touching regions.

Specified by:

getObjects in interface SpatialPartition

Parameters:

region - The region of interest.

Returns:

objs The list of triangles

getObjects

public int[] getObjects(int[] min,
 int[] max)

Gets the objects in the specified region. Any object which is contained or overlaps the region will be returned. Objects exactly on a voxel boundary shall be returned in all touching regions.

Parameters:

min - The min grid cell location

max - The max grid cell location

Returns:

The objects or null if none

getTriangle

public float[] getTriangle(int id)

Get the triangle mapping for an id.

Parameters:

id -

Returns:

insert

public void insert(Triangle tri,
 boolean useBounds)

Insert an object into the structure.

Parameters:

tri - The triangle

useBounds - Should the bounds be used instead of the exact object.

insert

public void insert(Triangle[] tris,
 boolean useBounds)

Insert an array of Triangles.

Parameters:

tris - The triangles

useBounds - Should the bounds be used instead of the exact object.

calcBoundsForTriangle

protected void calcBoundsForTriangle(Triangle tri,
 float[] min,
 float[] max)

Calculate a bounding box for a triangle.

Parameters:

tri -

min - The array to fill in the min bounds

max - The array to fill in the max bounds

findGridCoordsFromWorldCoords

public void findGridCoordsFromWorldCoords(float[] coords,
 int[] pos)

Find voxel grid coordinates for a given world coordinate

Parameters:

coords - The world coordinates

pos - The position in the grid, preallocate to 3. // * @return The grid coords, x,y,z

findGridCoordsFromWorldCoords

public int findGridCoordsFromWorldCoords(float coord)

Find voxel grid coordinates for a given world coordinate

Parameters:

coord - The world coordinates // * param pos The position in the grid, preallocate to 3.

Returns:

The grid coords, x,y,z

findVoxelInWorldCoords

public void findVoxelInWorldCoords(int x,
 int y,
 int z,
 float[] pos)

Find voxel world coordinates for a given voxel coordinate.

Parameters:

x - The x coord

y - The y coord

z - The z coord

pos - The returned position, preallocate to 3

fillCells

protected void fillCells(int[] min,
 int[] max,
 Triangle tri)

Fill in the grid given a box of grid coordinates.

Parameters:

min - The min bounds in cell coords

max - The max bounds in cell coords

tri -

fillCellsExact

protected void fillCellsExact(int[] min,
 int[] max,
 Triangle tri)

Fill in the grid given a box of grid coordinates.

Parameters:

min - The min bounds in cell coords

max - The max bounds in cell coords

tri -

gridCountsToString

public String gridCountsToString()

Return the grid counts in strin form.

Returns:

The grid counts

printStats

public void printStats()

findBoundsForTriangle

public void findBoundsForTriangle(Triangle tri,
 int[] minCoords,
 int[] maxCoords)

Check the general interface contract in superclass method Geometry.doVoxelization. Current method follows the voxelization algorithm strategy proposed in [DACH2000], but actual implementation only accounts for binary voxels. It is spected that with few changes, this algorithm manages the scalar (multivalued) voxel case for antialiased voxelization.

intersectsTriangle

public boolean intersectsTriangle(Vec3DDouble a,
 Vec3DDouble b,
 Vec3DDouble c,
 float[] pos)

Does triangle overlap a voxel. From paper: Fast 3D Triangle-Box Overlap Testing TODO: this paper mentions having errors with long thin polygons

Parameters:

a - first triangle coordinate

b - second triangle coordinate

c - third triangle coordinate

pos - The voxel center position