-
sparker
thiago
Manta Interactive Ray Tracer Development Mailing List
Text archives Help
- From: abe@sci.utah.edu
- To: manta@sci.utah.edu
- Subject: [MANTA] r430 - branches/itanium2/Model/Groups
- Date: Tue, 12 Jul 2005 22:43:53 -0600 (MDT)
Author: abe
Date: Tue Jul 12 22:43:50 2005
New Revision: 430
Modified:
branches/itanium2/Model/Groups/kdtree.cc
Log:
Pulled some more performance out of kdtree.cc and added some comments. Total
improvement is now 1.55x.
M kdtree.cc
Benchmark I am using is: dplace -c 12-48 bin/manta -np 32 -scene
"lib/libscene_boeing777.so( -file /dev/shm/Boeing777.v3c1 -np 32 -cutting
default )" -camera "pinhole( -eye 312.31 -315.671 199.735 -lookat 280.305
98.0706 184.652 -up 0.0256952 -0.337005 0.941152 -fov 60 )" -ui null
-imagedisplay null -bench 10 10
Modified: branches/itanium2/Model/Groups/kdtree.cc
==============================================================================
--- branches/itanium2/Model/Groups/kdtree.cc (original)
+++ branches/itanium2/Model/Groups/kdtree.cc Tue Jul 12 22:43:50 2005
@@ -27,12 +27,13 @@
int intersect_triangle3_edge( const float orig[3],
const float dir[3],
-
const float
vert0[3], const float vert1[3], const float vert2[3],
+
const float
vert0[3],
float *t, float *u,
float *v,
const float *edge1,
const float *edge2);
-int intersectTriangle3Edge(const Vectorf &direction, const Pointf &origin,
const Triangle &tri,
-
float &t, float &u,
float &v );
+int intersectTriangle3Edge(const Vectorf &direction, const Pointf &origin,
+ const Vectorf &edge1, Vectorf &edge2, Pointf &p0,
+
float &t, float &u, float &v );
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
@@ -591,13 +592,15 @@
// Intersect the ray with all the triangles.
int listEnd = listBegin+listSize;
+
+ #pragma swp
for (i = listBegin; i < listEnd; i++) {
int triIdx = triIndices->get(i);
Triangle &tri = tris->get(triIdx);
float t, u, v;
- if (intersectTriangle3Edge( direction, origin, tri, t, u, v
)) {
- // if(intersect_triangle3_edge( &origin, &direction, &tri[0],
&tri[1], &tri[2], &t, &u, &v, &tri.edge1, &tri.edge2 )) {
+ // if (intersectTriangle3Edge( direction, origin, tri.edge1,
tri.edge2, tri[0], t, u, v )) {
+ if(intersect_triangle3_edge( &origin, &direction, &tri[0],
&t, &u, &v, &tri.edge1, &tri.edge2 )) {
// Check to see if the t value is closer.
if (t < maxDist) {
@@ -621,14 +624,6 @@
}
}
-// Traversal Stack Entry.
-struct TravStackEntry {
- KDTreeNode* node; //8 bytes
- float t; // 4 bytes
-
// float point[3]; // 4*3=12 bytes
- int prev; // 4 bytes
-};
-
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
// This is the Manta interface method.
@@ -679,23 +674,35 @@
}
}
-
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
// This function performs the KD-Tree Traversal.
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
+
+// Traversal Stack Entry.
+struct TravStackEntry {
+ KDTreeNode* node; //8 bytes
+ float t; // 4 bytes
+
// float point[3]; // 4*3=12 bytes
+ int prev; // 4 bytes
+};
+
void KDTree::_intersect(const Ray* ray, RayPacket::Element &e,
RayTriIntersectUserData &isectData,
float minDist, float maxDist) const
{
+ // Keep a stack of entry and exit positions into the traversal nodes.
TravStackEntry travStack[128];
+
KDTreeNode *nearNode, *farNode;
float split;
int axis, entryPos, exitPos;
bool foundIntersection = false;
int tmp;
+
+ // Initialize the first two entries on the stack.
entryPos = 0;
nearNode = travStack[entryPos].node = rootNode;
travStack[entryPos].prev = 1;
@@ -708,44 +715,59 @@
while (travStack[entryPos].prev) {
+ // Traverse down until we find a leaf node.
while (nearNode && nearNode->isInternal()) {
+ // Determine the axis and the split point.
axis = nearNode->axis();
split = nearNode->split();
+ // Find where along the axis the ray enters and
exits.
float entryPos_coord_on_axis = ray->origin()[axis] +
- travStack[entryPos].t*ray->direction()[axis];
+
travStack[entryPos].t*ray->direction()[axis];
+
float exitPos_coord_on_axis = ray->origin()[axis] +
- travStack[exitPos].t*ray->direction()[axis];
+
travStack[exitPos].t*ray->direction()[axis];
+ // Check to see which side of the split the ray
enters first.
if (entryPos_coord_on_axis <= split) {
+ // Check to see if entry and exit are on the
+ // same side of the split.
if (exitPos_coord_on_axis <= split) {
+ // Same side of the split, so the
original interval is ok.
nearNode = nearNode->left();
continue;
}
+ // Otherwise update the near and far nodes,
and then update
+ // the interval below.
farNode = nearNode->right();
nearNode = nearNode->left();
}
else {
+ // Check to see if entry and exit are on the
same side.
if (exitPos_coord_on_axis >= split) {
nearNode = nearNode->right();
continue;
}
+ // Update otherwise.
farNode = nearNode->left();
nearNode = nearNode->right();
}
+ // Update location on the traversal stack.
tmp = exitPos;
+
+ // ??? Increment to an unused node ???
if (++exitPos == entryPos) ++exitPos;
+ // Specify a new exit node.
travStack[exitPos].node = farNode;
-
- travStack[exitPos].t = (split - ray->origin()[axis])*
- e.inverseDirection[axis];
+ travStack[exitPos].t = (split - ray->origin()[axis])*
e.inverseDirection[axis];
travStack[exitPos].prev = tmp;
}
+ // Check to see if we found a leaf node.
if (nearNode) {
// Intersect the ray with a list of triangles.
@@ -763,6 +785,7 @@
}
}
+ // Move to the next
entryPos = exitPos;
exitPos = travStack[exitPos].prev;
nearNode = travStack[entryPos].node;
@@ -867,7 +890,7 @@
}
inline int intersect_triangle3_edge(const float orig[3], const float dir[3],
-
const float
vert0[3], const float vert1[3], const float vert2[3],
+
const float
vert0[3],
float *t,
float *u, float *v, const float *edge1, const float *edge2 )
{
// float edge1[3], edge2[3];
@@ -924,7 +947,8 @@
return 1;
}
-int intersectTriangle3Edge(const Vectorf &direction, const Pointf &origin,
const Triangle &tri,
+int intersectTriangle3Edge(const Vectorf &direction, const Pointf &origin,
+ const Vectorf &edge1, Vectorf &edge2, Pointf &p0,
float &t, float &u, float &v )
{
@@ -935,19 +959,19 @@
// Vectorf edge2 = ( tri.edge2 );
/* begin calculating determinant - also used to calculate U parameter
*/
- pvec = Cross( direction, tri.edge2 );
+ pvec = Cross( direction, edge2 );
// CROSS(pvec, dir, edge2);
/* if determinant is near zero, ray lies in plane of triangle */
// det = DOT(edge1, pvec);
- float det = Dot( tri.edge1, pvec );
+ float det = Dot( edge1, pvec );
/* calculate distance from vert0 to ray origin */
// SUB(tvec, orig, vert0);
- tvec = origin - tri[0];
+ tvec = origin - p0;
- qvec = Cross( tvec, tri.edge1 );
+ qvec = Cross( tvec, edge1 );
// CROSS(qvec, tvec, edge1);
/* calculate U parameter */
@@ -982,7 +1006,7 @@
float inv_det = 1.0f / det;
- t = (Dot( tri.edge2, qvec ) * inv_det);
+ t = (Dot( edge2, qvec ) * inv_det);
u = (uu * inv_det);
v = (vv * inv_det);
- [MANTA] r430 - branches/itanium2/Model/Groups, abe, 07/12/2005
Archive powered by MHonArc 2.6.16.
