/*
* Java port of Bullet (c) 2008 Martin Dvorak <jezek2@advel.cz>
*
* This source file is part of GIMPACT Library.
*
* For the latest info, see http://gimpact.sourceforge.net/
*
* Copyright (c) 2007 Francisco Leon Najera. C.C. 80087371.
* email: projectileman@yahoo.com
*
* This software is provided 'as-is', without any express or implied warranty.
* In no event will the authors be held liable for any damages arising from
* the use of this software.
*
* Permission is granted to anyone to use this software for any purpose,
* including commercial applications, and to alter it and redistribute it
* freely, subject to the following restrictions:
*
* 1. The origin of this software must not be misrepresented; you must not
* claim that you wrote the original software. If you use this software
* in a product, an acknowledgment in the product documentation would be
* appreciated but is not required.
* 2. Altered source versions must be plainly marked as such, and must not be
* misrepresented as being the original software.
* 3. This notice may not be removed or altered from any source distribution.
*/
package com.bulletphysics.extras.gimpact;
import com.bulletphysics.extras.gimpact.BoxCollision.AABB;
import com.bulletphysics.linearmath.VectorUtil;
import cz.advel.stack.Stack;
import javax.vecmath.Vector3f;
/**
*
* @author jezek2
*/
class BvhTree {
protected int num_nodes = 0;
protected BvhTreeNodeArray node_array = new BvhTreeNodeArray();
protected int _calc_splitting_axis(BvhDataArray primitive_boxes, int startIndex, int endIndex) {
Vector3f means = Stack.alloc(Vector3f.class);
means.set(0f, 0f, 0f);
Vector3f variance = Stack.alloc(Vector3f.class);
variance.set(0f, 0f, 0f);
int numIndices = endIndex - startIndex;
Vector3f center = Stack.alloc(Vector3f.class);
Vector3f diff2 = Stack.alloc(Vector3f.class);
Vector3f tmp1 = Stack.alloc(Vector3f.class);
Vector3f tmp2 = Stack.alloc(Vector3f.class);
for (int i=startIndex; i<endIndex; i++) {
primitive_boxes.getBoundMax(i, tmp1);
primitive_boxes.getBoundMin(i, tmp2);
center.add(tmp1, tmp2);
center.scale(0.5f);
means.add(center);
}
means.scale(1f / (float)numIndices);
for (int i=startIndex; i<endIndex; i++) {
primitive_boxes.getBoundMax(i, tmp1);
primitive_boxes.getBoundMin(i, tmp2);
center.add(tmp1, tmp2);
center.scale(0.5f);
diff2.sub(center, means);
VectorUtil.mul(diff2, diff2, diff2);
variance.add(diff2);
}
variance.scale(1f / (float)(numIndices - 1));
return VectorUtil.maxAxis(variance);
}
protected int _sort_and_calc_splitting_index(BvhDataArray primitive_boxes, int startIndex, int endIndex, int splitAxis) {
int splitIndex = startIndex;
int numIndices = endIndex - startIndex;
// average of centers
float splitValue = 0.0f;
Vector3f means = Stack.alloc(Vector3f.class);
means.set(0f, 0f, 0f);
Vector3f center = Stack.alloc(Vector3f.class);
Vector3f tmp1 = Stack.alloc(Vector3f.class);
Vector3f tmp2 = Stack.alloc(Vector3f.class);
for (int i = startIndex; i < endIndex; i++) {
primitive_boxes.getBoundMax(i, tmp1);
primitive_boxes.getBoundMin(i, tmp2);
center.add(tmp1, tmp2);
center.scale(0.5f);
means.add(center);
}
means.scale(1f / (float) numIndices);
splitValue = VectorUtil.getCoord(means, splitAxis);
// sort leafNodes so all values larger then splitValue comes first, and smaller values start from 'splitIndex'.
for (int i = startIndex; i < endIndex; i++) {
primitive_boxes.getBoundMax(i, tmp1);
primitive_boxes.getBoundMin(i, tmp2);
center.add(tmp1, tmp2);
center.scale(0.5f);
if (VectorUtil.getCoord(center, splitAxis) > splitValue) {
// swap
primitive_boxes.swap(i, splitIndex);
//swapLeafNodes(i,splitIndex);
splitIndex++;
}
}
// if the splitIndex causes unbalanced trees, fix this by using the center in between startIndex and endIndex
// otherwise the tree-building might fail due to stack-overflows in certain cases.
// unbalanced1 is unsafe: it can cause stack overflows
//bool unbalanced1 = ((splitIndex==startIndex) || (splitIndex == (endIndex-1)));
// unbalanced2 should work too: always use center (perfect balanced trees)
//bool unbalanced2 = true;
// this should be safe too:
int rangeBalancedIndices = numIndices / 3;
boolean unbalanced = ((splitIndex <= (startIndex + rangeBalancedIndices)) || (splitIndex >= (endIndex - 1 - rangeBalancedIndices)));
if (unbalanced) {
splitIndex = startIndex + (numIndices >> 1);
}
boolean unbal = (splitIndex == startIndex) || (splitIndex == (endIndex));
assert (!unbal);
return splitIndex;
}
protected void _build_sub_tree(BvhDataArray primitive_boxes, int startIndex, int endIndex) {
int curIndex = num_nodes;
num_nodes++;
assert ((endIndex - startIndex) > 0);
if ((endIndex - startIndex) == 1) {
// We have a leaf node
//setNodeBound(curIndex,primitive_boxes[startIndex].m_bound);
//m_node_array[curIndex].setDataIndex(primitive_boxes[startIndex].m_data);
node_array.set(curIndex, primitive_boxes, startIndex);
return;
}
// calculate Best Splitting Axis and where to split it. Sort the incoming 'leafNodes' array within range 'startIndex/endIndex'.
// split axis
int splitIndex = _calc_splitting_axis(primitive_boxes, startIndex, endIndex);
splitIndex = _sort_and_calc_splitting_index(primitive_boxes, startIndex, endIndex, splitIndex);
//calc this node bounding box
AABB node_bound = Stack.alloc(AABB.class);
AABB tmpAABB = Stack.alloc(AABB.class);
node_bound.invalidate();
for (int i=startIndex; i<endIndex; i++) {
primitive_boxes.getBound(i, tmpAABB);
node_bound.merge(tmpAABB);
}
setNodeBound(curIndex, node_bound);
// build left branch
_build_sub_tree(primitive_boxes, startIndex, splitIndex);
// build right branch
_build_sub_tree(primitive_boxes, splitIndex, endIndex);
node_array.setEscapeIndex(curIndex, num_nodes - curIndex);
}
public void build_tree(BvhDataArray primitive_boxes) {
// initialize node count to 0
num_nodes = 0;
// allocate nodes
node_array.resize(primitive_boxes.size()*2);
_build_sub_tree(primitive_boxes, 0, primitive_boxes.size());
}
public void clearNodes() {
node_array.clear();
num_nodes = 0;
}
public int getNodeCount() {
return num_nodes;
}
/**
* Tells if the node is a leaf.
*/
public boolean isLeafNode(int nodeindex) {
return node_array.isLeafNode(nodeindex);
}
public int getNodeData(int nodeindex) {
return node_array.getDataIndex(nodeindex);
}
public void getNodeBound(int nodeindex, AABB bound) {
node_array.getBound(nodeindex, bound);
}
public void setNodeBound(int nodeindex, AABB bound) {
node_array.setBound(nodeindex, bound);
}
public int getLeftNode(int nodeindex) {
return nodeindex + 1;
}
public int getRightNode(int nodeindex) {
if (node_array.isLeafNode(nodeindex + 1)) {
return nodeindex + 2;
}
return nodeindex + 1 + node_array.getEscapeIndex(nodeindex + 1);
}
public int getEscapeNodeIndex(int nodeindex) {
return node_array.getEscapeIndex(nodeindex);
}
public BvhTreeNodeArray get_node_pointer() {
return node_array;
}
}