-
sparker
thiago
Manta Interactive Ray Tracer Development Mailing List
Text archives Help
- From: abe@sci.utah.edu
- To: manta@sci.utah.edu
- Subject: [MANTA] r863 - in trunk: Interface Model/Groups
- Date: Tue, 24 Jan 2006 18:05:23 -0700 (MST)
Author: abe
Date: Tue Jan 24 18:05:23 2006
New Revision: 863
Modified:
trunk/Interface/RayPacket.h
trunk/Model/Groups/KDTree.h
trunk/Model/Groups/VerticalKDTree.cc
trunk/Model/Groups/VerticalKDTree.h
Log:
More updates to Vertical kdtree traversal. We only have one bug left to solve.
M Model/Groups/VerticalKDTree.cc
M Model/Groups/VerticalKDTree.h
M Model/Groups/KDTree.h
Added getSignMask method to obtain a bit mask representing the ray sign
direction.
M Interface/RayPacket.h
Modified: trunk/Interface/RayPacket.h
==============================================================================
--- trunk/Interface/RayPacket.h (original)
+++ trunk/Interface/RayPacket.h Tue Jan 24 18:05:23 2006
@@ -312,6 +312,14 @@
return data->signs[sign][which];
}
+ // Return a bit mask representing the sign directions of the ray.
+ int getSignMask(int which) {
+ return
+ (data->signs[0][which]) |
+ (data->signs[1][which] << 1) |
+ (data->signs[2][which] << 2);
+ }
+
// Hit information
void resetHits() {
for(int i=rayBegin;i<rayEnd;i++){
@@ -338,6 +346,7 @@
}
bool hit(int which, Real t, const Material* matl, const Primitive* prim,
const TexCoordMapper* tex) {
+
if(t < T_EPSILON)
return false;
if(t < data->minT[which]){
Modified: trunk/Model/Groups/KDTree.h
==============================================================================
--- trunk/Model/Groups/KDTree.h (original)
+++ trunk/Model/Groups/KDTree.h Tue Jan 24 18:05:23 2006
@@ -198,9 +198,8 @@
(hasLeftChild()?this+internal.left+1:this+internal.left) : 0;
}
- KDTreeNode *getChild( short int i ) {
- return this + internal.left +
- (i & ((internal.flags&KDNODE_LEFT_CHILD_MASK) >> 3));
+ KDTreeNode* getChild( short int i ) {
+ return (i) ? right() : left();
};
float split() const { return internal.split; }
Modified: trunk/Model/Groups/VerticalKDTree.cc
==============================================================================
--- trunk/Model/Groups/VerticalKDTree.cc (original)
+++ trunk/Model/Groups/VerticalKDTree.cc Tue Jan 24 18:05:23 2006
@@ -162,41 +162,87 @@
rays.normalizeDirections();
rays.computeInverseDirections();
rays.computeSigns();
-
- // Mask to keep track of which rays are valid.
- Mask valid_mask( Mask::False );
- // Iterate over sub groups of rays.
- for(int which=rays.begin();which<rays.end();which+=TraversalPacketSize) {
+ // Find runs of rays with the same direction signs.
+ for(int i = rays.begin();i<rays.end();){
- Real minDist[TraversalPacketSize];
- Real maxDist[TraversalPacketSize];
+ int sign = rays.getSignMask( i );
+ int end = i+1;
- // Compute min and max distance for the kdtree.
- for (int p=0;(p<TraversalPacketSize)&&((which+p)<rays.end());++p) {
-
- // Intersect the ray with the bounding box for the group.
- valid_mask[p] = Intersection::intersectAaBox( bbox,
- minDist[p],
- maxDist[p],
- rays.getRay(which+p),
- rays.getSigns(which+p),
-
rays.getInverseDirection(which+p));
+ // Find the end of the run.
+ while(end < rays.end() && (rays.getSignMask(end)==sign))
+ end++;
+ // Create a sub packet.
+ RayPacket subPacket(rays, i, end);
+
+ // Set the constant sign flag.
+ subPacket.resetFlag( RayPacket::HaveSigns );
+
+ subPacket.computeSigns();
+ assert( subPacket.getFlag( RayPacket::ConstantSigns ) );
+
+
///////////////////////////////////////////////////////////////////////////
+ // Make sure that the traversal packet starts with an index that is
+ // TraversalPacketSize aligned.
+ int which = subPacket.begin();
+ int p_start = (which % TraversalPacketSize);
+
+ // Set which to be TraversalPacketSize aligned.
+ // The un-used rays are already set to false.
+ which -= p_start;
+
+
////////////////////////////////////////////////////////////////////////////
+ // Iterate over sub groups of rays.
+ for(;which<subPacket.end();which+=TraversalPacketSize) {
+
+ Real minDist[TraversalPacketSize];
+ Real maxDist[TraversalPacketSize];
+
+ Mask valid_mask( Mask::False );
-
- // Determine the actual minimum distance.
- minDist[p] = SCIRun::Max( minDist[p], (float)T_EPSILON );
- maxDist[p] = SCIRun::Min( maxDist[p], (float)rays.getMinT(which+p) );
- }
+ // Compute min and max distance for the kdtree.
+ for (int
p=p_start;(p<TraversalPacketSize)&&((which+p)<subPacket.end());++p) {
- // Check to see if a traversal is necessary.
- if (any(valid_mask)) {
+ assert(getMaterial());
+
+ // Intersect the ray with the bounding box for the group.
+ valid_mask[p] = Intersection::intersectAaBox( bbox,
+ minDist[p],
+ maxDist[p],
+
subPacket.getRay(which+p),
+
subPacket.getSigns(which+p),
+
subPacket.getInverseDirection(which+p));
+#if 0
+ if (p_start && valid_mask[p]) {
+ subPacket.scratchpad<ScratchPadInfo>(which+p).payload =
Color(RGB(1,0,0));
+
assert(rays.hit(which+p,T_EPSILON*8,getMaterial(),this,(TexCoordMapper *)1));
+ }
+#endif
+
+ // Determine the actual minimum distance.
+ minDist[p] = SCIRun::Max( minDist[p], T_EPSILON );
+ maxDist[p] = SCIRun::Min( maxDist[p], subPacket.getMinT(which+p) );
+ }
- // Intersect the subpacket with the tree.
- intersect_node( context, valid_mask, rays, which, minDist, maxDist );
- }
+ // Check to see if a traversal is necessary.
+ if (any(valid_mask)) {
+ // Make sure that the vector operations won't overflow the ray
packet.
+ assert( (which+TraversalPacketSize) <= RayPacket::MaxSize );
+
+ // Intersect the subpacket with the tree.
+ intersect_node( context, valid_mask, subPacket, which, p_start,
minDist, maxDist );
+ }
+
+ // Returned to alignment for additional rays in the packet.
+ p_start = 0;
+
+ }
+
+
///////////////////////////////////////////////////////////////////////////
+ // Find the next run.
+ i=end;
}
}
@@ -207,18 +253,17 @@
///////////////////////////////////////////////////////////////////////////////
// Traversal Stack Entry.
-struct TravStackEntry {
- float t[TraversalPacketSize];
- KDTreeNode* node; // 8 bytes(64 bit builds), 4 bytes(32 bit builds)
- int prev; // 4 bytes
- int padding;
-
+struct Stack {
+ __declspec(align(16)) float t_near[TraversalPacketSize];
+ __declspec(align(16)) float t_far [TraversalPacketSize];
+ KDTreeNode* node;
};
void VerticalKDTree::intersect_node( const RenderContext &context,
const Mask &valid_mask,
RayPacket &rays,
int which,
+ int p_start,
float minDist[TraversalPacketSize],
float maxDist[TraversalPacketSize] )
const
{
@@ -227,140 +272,132 @@
// Stack pointers.
KDTreeNode *nearNode = rootNode;
KDTreeNode *farNode;
- int entryPos = 0;
- int exitPos = 1;
/////////////////////////////////////////////////////////////////////////////
// Keep a stack of entry and exit positions into the traversal nodes.
- __declspec(align(128)) TravStackEntry travStack[128];
+ Stack stack[128];
+ int stack_index = 1;
- // Initialize the first two entries on the stack.
- travStack[entryPos].node = rootNode;
- travStack[entryPos].prev = 1;
-
- // Check for the case that the minimum intersection point is behind
- // the origin.
+ // Initialize the stack.
for (int p=0;p<TraversalPacketSize;++p) {
- travStack[entryPos].t[p] = SCIRun::Max( 0.0f, minDist[p] );
- }
-
- travStack[exitPos].node = NULL;
- travStack[exitPos].prev = 0;
-
- for (int p=0;p<TraversalPacketSize;++p) {
- travStack[exitPos].t[p] = maxDist[p];
+ stack[1].t_near[p] = minDist[p];
+ stack[1].t_far [p] = maxDist[p];
}
+ // Start at the root.
+ stack[1].node = rootNode;
+
/////////////////////////////////////////////////////////////////////////////
// Mask to keep track of rays that still need to find closest
intersections.
Mask active_mask = valid_mask;
-
- while (travStack[entryPos].prev) {
- // Traverse down until we find a leaf node.
-#ifndef __sgi
-#pragma swp
-#endif
- while (nearNode && nearNode->isInternal()) {
-
- // Determine the axis and the split point.
- int axis = nearNode->axis();
- float split = nearNode->split();
-
- // Find where along the axis the ray enters and exits.
- float entry_axis[TraversalPacketSize];
- float exit_axis [TraversalPacketSize];
+ // Process nodes on the stack.
+ while (stack_index) {
+
+
///////////////////////////////////////////////////////////////////////////
+ // Pop off the node on top of the stack.
+ KDTreeNode *node = stack[stack_index].node;
+
+ float t_near[TraversalPacketSize];
+ float t_far [TraversalPacketSize];
+
+ // Copy t_near and t_far from the stack.
+ for (int p=0;p<TraversalPacketSize;++p) {
+ t_near[p] = stack[stack_index].t_near[p];
+ t_far [p] = stack[stack_index].t_far [p];
+ }
+
+ // Pop stack.
+ stack_index--;
+
+ /////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////
+ // Traverse down to a leaf.
+ while (node && node->isInternal()) {
+
+ // Obtain axis and split point.
+ const int axis = node->axis();
+ const float split = node->split();
+
+ // Identify near_index and far_index.
+ assert( rays.getFlag( RayPacket::ConstantSigns ) );
+
+ const int near_index = rays.getSign(which+p_start,axis);
+ const int far_index = (1 - near_index);
+
/////////////////////////////////////////////////////////////////////////
+ // Compute t_split.
+ float t_split[TraversalPacketSize];
for (int p=0;p<TraversalPacketSize;++p) {
- if (active_mask[p]) {
- entry_axis[p] =
- travStack[entryPos].t[p] *
- rays.getDirection(which+p,axis) +
- rays.getOrigin (which+p,axis);
-
- exit_axis[p] =
- travStack[exitPos].t[p] *
- rays.getDirection(which+p,axis) +
- rays.getOrigin (which+p,axis);
- }
+ t_split[p] = (split - rays.getOrigin(which+p,axis)) *
+ rays.getInverseDirection(which+p,axis);
}
/////////////////////////////////////////////////////////////////////////
- // Check to see which side of the split the ray enters first.
- // if (entryPos_coord_on_axis <= split) {
+ // Classify the case.
Mask cmp_result;
- set_lte( cmp_result, entry_axis, split );
- if (any( cmp_result )) {
+ set_lte( cmp_result, t_far, t_split );
+ if (all( active_mask, cmp_result)) {
///////////////////////////////////////////////////////////////////////
- // Check to see if entry and exit are on the
- // same side of the split.
- // if (exitPos_coord_on_axis <= split) {
- set_lte( cmp_result, exit_axis, split );
- if (all( active_mask, cmp_result )) {
-
-
/////////////////////////////////////////////////////////////////////
- // Case "A"
-
- // Same side of the split, so the original interval is ok.
- nearNode = nearNode->left();
- continue;
- }
+ // Case I: "Near Only"
-
///////////////////////////////////////////////////////////////////////
- // Case "B"
+ // Update the current node.
+ node = node->getChild( near_index );
+
+ // Copy t_split to t_far.
+ for (int p=0;p<TraversalPacketSize;++p) {
+ t_far[p] = t_split[p];
+ }
- // Otherwise update the near and far nodes, and then update
- // the interval below.
- farNode = nearNode->right();
- nearNode = nearNode->left();
+ // No stack operations.
+ continue;
}
- else {
- // Check to see if entry and exit are on the same side.
- // if (exitPos_coord_on_axis >= split) {
- set_gte( cmp_result, exit_axis, split );
- if (all(active_mask, cmp_result)) {
+ set_gte( cmp_result, t_near, t_split );
+ if (all( active_mask, cmp_result)) {
-
/////////////////////////////////////////////////////////////////////
- // Case "C"
+
///////////////////////////////////////////////////////////////////////
+ // Case II: "Far Only"
- nearNode = nearNode->right();
- continue;
+ // Update the current node.
+ node = node->getChild( far_index );
+
+ // Copy t_split to t_far.
+ for (int p=0;p<TraversalPacketSize;++p) {
+ t_near[p] = t_split[p];
}
-
/////////////////////////////////////////////////////////////////////..
- // Case "D"
-
- // Update otherwise.
- farNode = nearNode->left();
- nearNode = nearNode->right();
+ // No stack operations.
+ continue;
}
/////////////////////////////////////////////////////////////////////////
- // Update location on the traversal stack.
- int tmp = exitPos;
+ // Otherwise:
+
+ // Case III "Both" -- Push far node on stack.
+ stack_index++;
+ stack[stack_index].node = node->getChild( far_index );
- // ??? Increment to an unused node ???
- if (++exitPos == entryPos) ++exitPos;
+ // Copy t_split and t_far to the stack.
+ for (int p=0;p<TraversalPacketSize;++p) {
+ stack[stack_index].t_near[p] = t_split[p];
+ stack[stack_index].t_far [p] = t_far[p];
+ }
- // Update the far node.
- // Specify a new exit node.
- travStack[exitPos].node = farNode;
- travStack[exitPos].prev = tmp;
-
- // Compute t value for exit position.
+ // Update the current node.
+ node = node->getChild( near_index );
+
+ // Copy t_split to t_far.
for (int p=0;p<TraversalPacketSize;++p) {
- travStack[exitPos].t[p] =
- (split - rays.getOrigin(which+p,axis)) *
- rays.getInverseDirection(which+p,axis);
+ t_far[p] = t_split[p];
}
}
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
// Check to see if we found a non-empty leaf node.
- if (nearNode) {
+ if (node) {
/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////
@@ -369,8 +406,8 @@
intersectTriangles(intersect_packet,
rays,
which,
- nearNode->listBegin(),
- nearNode->listSize());
+ node->listBegin(),
+ node->listSize());
// IntersectPacket::hit_mask[p] must reflect triangleindex >= 0
@@ -419,13 +456,12 @@
}
/////////////////////////////////////////////////////////////////////
+ /////////////////////////////////////////////////////////////////////
// Check to see if the hit is inside the current cell.
- // if (rays.getMinT(which) <= travStack[exitPos].t)
- // break
-
+
// Update the active_mask.
Mask cmp_result;
- set_gt( cmp_result, &rays.getMinT(which), travStack[exitPos].t );
+ set_gt( cmp_result, &rays.getMinT(which), stack[stack_index].t_far );
// And the active mask with the result of the comparsion.
// (only pay attention to bits which are both active and passed the
comparsion )
@@ -433,13 +469,10 @@
// Check to see if any rays are active any longer.
if (none(active_mask)) {
+
+ // Done with this packet.
break;
}
-
- // Move to the next
- entryPos = exitPos;
- exitPos = travStack[exitPos].prev;
- nearNode = travStack[entryPos].node;
}
}
Modified: trunk/Model/Groups/VerticalKDTree.h
==============================================================================
--- trunk/Model/Groups/VerticalKDTree.h (original)
+++ trunk/Model/Groups/VerticalKDTree.h Tue Jan 24 18:05:23 2006
@@ -91,15 +91,15 @@
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
- static inline void set_lte( Mask &result, float
vec[TraversalPacketSize], float scalar ) {
+ static inline void set_lte( Mask &result, float
vec0[TraversalPacketSize], float vec1[TraversalPacketSize] ) {
for (int p=0;p<TraversalPacketSize;++p) {
- result[p] = (vec[p] <= scalar);
+ result[p] = (vec0[p] <= vec1[p]);
}
}
- static inline void set_gte( Mask &result, float
vec[TraversalPacketSize], float scalar ) {
+ static inline void set_gte( Mask &result, float
vec0[TraversalPacketSize], float vec1[TraversalPacketSize] ) {
for (int p=0;p<TraversalPacketSize;++p) {
- result[p] = (vec[p] >= scalar);
+ result[p] = (vec0[p] >= vec1[p]);
}
}
@@ -240,14 +240,10 @@
const Mask &valid_mask,
RayPacket &rays,
int which,
+ int p_start,
float minDist[TraversalPacketSize],
float maxDist[TraversalPacketSize] ) const;
- void intersect_node( KDTreeNode *startNode,
- RayPacket& rays, int which,
- RayTriIntersectUserData &isectData,
- const RenderContext &context,
- float minDist, float maxDist) const;
};
- [MANTA] r863 - in trunk: Interface Model/Groups, abe, 01/24/2006
Archive powered by MHonArc 2.6.16.
