http://www.zshare.net/download/arauna_k ... 0-rar.html
>>>> End of update, the rest of my post is still relevant <<<<
Sorry about the dll mess; it's using the Arauna library which is linked to fmod and some other things, I didn't try to remove those dependencies.
About the tool:
It expects obj files (I generate them using Deep Exploration, but it should work on all obj files), and spits out a text file containing the kd-tree. File format:
First line: n%i, where %i is the number of kd-tree nodes.
Subsequent lines: The kd-tree nodes; first character is eiter 'L' for a leaf, or the split axis; then a float that represents the split plane position, and finally the 'left' and 'right' node index. Leaf nodes have two different numbers: The first number is the first primitive stored in the leaf, the second number is the primitive count for the leaf. These indices point to the 'object list', which is stored in the file after the nodes.
Object list: A list of primitive indices used in the leafs. The indices in the object list point to primitives in the obj file, with one big huge catch: Degenerate prims are NOT counted.
Degenerates: Arauna detects degenerates and skips them using the following method:
- Code: Select all
bool Primitive::Degenerate() const
{
float d1 = (m_Vertex[1]->GetPos() - m_Vertex[0]->GetPos()).Length();
float d2 = (m_Vertex[2]->GetPos() - m_Vertex[1]->GetPos()).Length();
float d3 = (m_Vertex[0]->GetPos() - m_Vertex[2]->GetPos()).Length();
return ((d1 < EPSILON) || (d2 < EPSILON) || (d3 < EPSILON));
}
where EPSILON is defined as 0.0001f.
The resulting kd-trees are tested and working in my own code. I load the tree using the following code:
- Code: Select all
void KdTree::Load( char* a_File )
{
FILE* f = fopen( "kdtree.txt", "r" );
char buffer[512];
if (f)
{
fgets( buffer, 500, f );
unsigned int nodes;
sscanf( buffer, "n%i", &nodes );
KdTreeNode* node = new KdTreeNode[nodes];
for ( unsigned int i = 0; i < nodes; i++ )
{
fgets( buffer, 500, f );
if (!strncmp( buffer, "dummy", 5 ))
{
// dummy node, ignore
}
else if (buffer[0] == 'L')
{
// leaf node
int first, count;
sscanf( buffer, "L p1:%i c:%i", &first, &count );
node[i].SetLeft( 0 );
node[i].SetObjList( first, count );
node[i].SetLeaf( true );
}
else
{
// interior node
int left;
char caxis;
float split;
sscanf( buffer, "%c|%f %i<>", &caxis, &split, &left );
node[i].SetLeaf( false );
node[i].SetLeft( &node[left] ); // automatically sets right to node[left + 1]
node[i].SetSplitPos( split );
node[i].SetAxis( caxis - 'X' );
}
}
m_Root = &node[0];
fgets( buffer, 500, f );
unsigned int olsize;
sscanf( buffer, "o%i", &olsize );
m_ObjList = new Primitive*[olsize];
for ( unsigned int i = 0; i < olsize; i++ )
{
fgets( buffer, 500, f );
unsigned int pidx;
sscanf( buffer, "%i", &pidx );
m_ObjList[i] = (Primitive*)Scene::GetPrimitive( pidx );
}
}
}
One note: The 'right' node index is not loaded from the file, it is always 'left + 1'. This is because you are supposed to allocate kd-tree nodes in pairs.
This should do the job.
The kd-tree compiler has one experimental function: The kd-tree optimization. I walk the tree, and for each pair of leafs, I calculate the cost of these leafs and their parent, and undo splits if the split didn't help. For Sponza, this deletes a lot of nodes and also brings the average number of primitives per leaf to a much higher number, so I suspect there is a bug...
I plan to release new versions of this tool in the future, probably with more command line parameters to tweak trees and to influence some behavior (like the optimization).
The aim of this tool is to ease the work of new ray tracer coders; the kd-tree is a tricky thing to get right, and this compiler / builder 'just works'. Also, the tool may be used to make ray tracer performance comparison more objective.
- Jacco.
I haven't benchmarked but it's a good idea.
thanks for the commend