-
sparker
thiago
Manta Interactive Ray Tracer Development Mailing List
Text archives Help
- From: bigler@sci.utah.edu
- To: manta@sci.utah.edu
- Subject: [MANTA] r547 - branches/itanium2/Model/Groups
- Date: Tue, 13 Sep 2005 14:41:30 -0600 (MDT)
Author: bigler
Date: Tue Sep 13 14:41:30 2005
New Revision: 547
Modified:
branches/itanium2/Model/Groups/FrustumKDTree.cc
branches/itanium2/Model/Groups/FrustumKDTree.h
Log:
More text formatting. Removed trailing whitespace.
Changed frustum_leaf_intersect to take a BBox instead of a
KDTreeLeafNode. Fleshed out the implementation of the
frustum_leaf_intersect.
Modified: branches/itanium2/Model/Groups/FrustumKDTree.cc
==============================================================================
--- branches/itanium2/Model/Groups/FrustumKDTree.cc (original)
+++ branches/itanium2/Model/Groups/FrustumKDTree.cc Tue Sep 13 14:41:30
2005
@@ -1,11 +1,11 @@
/*
For more information, please see: http://software.sci.utah.edu
-
+
The MIT License
-
+
Copyright (c) 2005
Scientific Computing and Imaging Institue, University of Utah
-
+
License for the specific language governing rights and limitations under
Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the "Software"),
@@ -13,10 +13,10 @@
the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:
-
+
The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.
-
+
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
@@ -41,7 +41,7 @@
/////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////
-// Create a frustum around the specified ray packet. Assumes all rays
+// Create a frustum around the specified ray packet. Assumes all rays
// have common origin and all rays have a common direction.
PacketFrustum::PacketFrustum( const RayPacket &rays ) {
@@ -106,7 +106,7 @@
else if (p[j] > max[j]) max[j] = p[j];
}
}
-
+
/////////////////////////////////////////////////////////////////////////////
// Transform bounding corners into world vectors.
frustum_bound[0] = ((plane_point + (plane_u * min[0]) + (plane_v *
min[1])) -
@@ -134,32 +134,33 @@
///////////////////////////////////////////////////////////////////////
// Check to make sure the ray packet is big enough and has the
// correct flags set.
- if ((rays.getSize() == 1) ||
- (!rays.getFlags( RayPacket::ConstantOrigin )) ||
+ if ((rays.getSize() == 1) ||
+ (!rays.getFlags( RayPacket::ConstantOrigin )) ||
(!rays.getFlags( RayPacket::ConstantDirections ))) {
-
+
// If not call normal kdtree ray intersect.
KDTree::intersect( context, rays );
return;
}
-
+
// Create a packet bounding frustum and intersect it with the tree.
PacketFrustum frustum( rays );
-
+
///////////////////////////////////////////////////////////////////////
// Intersect the frustum down the kdtree.
-
-
+
+
}
/////////////////////////////////////////////////////////////////////////
// Intersect the specified frustum with an internal node.
-FrustumKDTree::IntersectCase FrustumKDTree::frustum_node_intersect(const
RenderContext& context,
- const
KDTreeNode *node,
- const
PacketFrustum &frustum,
- const
BBox &node_bounds )
+FrustumKDTree::IntersectCase
+FrustumKDTree::frustum_node_intersect(const RenderContext& context,
+ const KDTreeNode *node,
+ const PacketFrustum &frustum,
+ const BBox &node_bounds )
{
typedef PointT<float,2> Point2f;
typedef PointT<float,3> Point3f;
@@ -168,7 +169,7 @@
// Determine the split plane direction.
unsigned int axis = node->axis();
-
+
// Determine the axes of the split plane.
unsigned int plane_axis[2];
plane_axis[0] = (axis+1)%3;
@@ -176,38 +177,39 @@
/////////////////////////////////////////////////////////////////////////////
// Find the edges of the intersection of the node_bounds with split plane.
- Real min_edge[2]; // position of edges: ad, ab -- min edges for plane axis
0,1
- Real max_edge[2]; // position of edges: dc, bc -- max edges for plane axis
0,1
+ Real min_edge[2]; // position of edges: ad,ab -- min edges for plane axis
0,1
+ Real max_edge[2]; // position of edges: dc,bc -- max edges for plane axis
0,1
for (int i=0;i<2;++i) {
min_edge[i] = node_bounds[0][plane_axis[i]];
max_edge[i] = node_bounds[1][plane_axis[i]];
}
-
+
/////////////////////////////////////////////////////////////////////////////
// Intersect each of the frustum bounding rays with the split plane.
-
+
// Find the n and f, the max and min 2D intersection points on the split
// plane.
Point2 n(-FLT_MAX,-FLT_MAX);
Point2 f( FLT_MAX, FLT_MAX);
-
+
for (int i=0;i<4;++i) {
// Intersection pt = origin + (t)(direction)
Point pt = frustum.origin();
-
+
// t = dot((point-origin),normal) / dot(direction,normal)
// Determine dn (1/ray direction)
Real direction_rcp = 1.0 / frustum.bound(i)[axis];
-
+
// Compute the necessary component of ao = (plane point - origin)
Real t = ((Real)node->split() - frustum.origin()[axis]) * direction_rcp;
-
+
// Compute the intersection point.
pt += (frustum.bound(i)*t);
-
- // Compute the 2D bounds on the plane. --- CAN WE USE FMIN and FMAX
instr's for this?
- for (int j=0;j<2;++j) {
+
+ // Compute the 2D bounds on the plane. --- CAN WE USE FMIN and
+ // FMAX instr's for this?
+ for (int j=0;j<2;++j) {
n[j] = SCIRun::Max( n[j], pt[plane_axis[j]] );
f[j] = SCIRun::Min( f[j], pt[plane_axis[j]] );
}
@@ -215,20 +217,21 @@
/////////////////////////////////////////////////////////////////////////////
// For each axis, check the node bounds edges against n and f.
-
+
// First check for overlap.
bool above[2];
above[0] = (f[0] < max_edge[0]);
above[1] = (f[1] < max_edge[1]);
-
- if ( ((n[0] > min_edge[0]) && !above[0]) || ((n[1] > min_edge[1]) &&
!above[1]) )
+
+ if ( ((n[0] > min_edge[0]) && !above[0]) ||
+ ((n[1] > min_edge[1]) && !above[1]) )
return INTERSECT_BOTH;
// Determine A and B child -- A is closer to the frustum origin.
unsigned int A_child = INTERSECT_MAX;
unsigned int B_child = INTERSECT_MIN;
unsigned int result = INTERSECT_NONE;
-
+
if (frustum.origin()[axis] < node->split()) {
A_child = INTERSECT_MIN;
B_child = INTERSECT_MAX;
@@ -239,10 +242,10 @@
/////////////////////////////////////////////////////////////////////////////
// Check for each plane axis direction.
for (int i=0;i<2;++i) {
-
+
// Frustum intersection above node.
if (above[i]) {
-
+
// Case "A+"
if (frustum.direction(plane_axis[i])==1) {
result &= A_child;
@@ -251,12 +254,12 @@
else {
result &= B_child;
}
-
+
}
-
+
// Frustum intersection below node.
else {
-
+
// Case "B+"
if (frustum.direction(plane_axis[i])==1) {
result &= B_child;
@@ -267,15 +270,76 @@
}
}
}
-
+
// Return the result.
return (IntersectCase)result;
}
/////////////////////////////////////////////////////////////////////////
-// Intersect the specified frustum with a leaf.
-FrustumKDTree::IntersectCase FrustumKDTree::frustum_leaf_intersect(const
RenderContext& context, KDTreeLeafNode *node, PacketFrustum &frustum ) {
+// Intersect the specified frustum with a leaf. This is basically a
+// glorified bounding box test that takes into consideration 4 rays
+// (the edges of the frustum) instead of 1. It does produce some
+// false positives, but it should never generate false negatives.
+bool FrustumKDTree::frustum_leaf_intersect(const RenderContext& context,
+ PacketFrustum &frustum,
+ const BBox& leaf_bounds ) {
+ Vector entry[4];
+ Vector exit[4];
+ // frustrum.direction() is 0 for negative directions, 1 for zero/positive.
+ Point bb_min(leaf_bounds[1-frustum.direction(0)].x(),
+ leaf_bounds[1-frustum.direction(1)].y(),
+ leaf_bounds[1-frustum.direction(2)].z());
+ Point bb_max(leaf_bounds[ frustum.direction(0)].x(),
+ leaf_bounds[ frustum.direction(1)].y(),
+ leaf_bounds[ frustum.direction(2)].z());
+ for(unsigned int i = 0; i < 4; ++i) {
+ entry[i] = ((bb_min - frustum.origin()) / frustum.bound(i));
+ exit[i] = ((bb_max - frustum.origin()) / frustum.bound(i));
+ }
+
+ //////////////////////////////////////////////////
+ // The XY plane
+
+ // Test case #1, min(y_entry) > max(x_exit)
+ Real min_y_entry = entry[0].y();
+ Real max_x_exit = exit[0].x();
+ for(unsigned int i = 1; i < 4; ++i) {
+ if (entry[i].y() < min_y_entry) min_y_entry = entry[i].y();
+ if ( exit[i].x() > max_x_exit ) max_x_exit = exit[i].x();
+ }
+ if (min_y_entry > max_x_exit) return false;
+
+ // Test case #2, min(x_entry) > max(y_exit)
+ Real min_x_entry = entry[0].x();
+ Real max_y_exit = exit[0].y();
+ for(unsigned int i = 1; i < 4; ++i) {
+ if (entry[i].x() < min_x_entry) min_x_entry = entry[i].x();
+ if ( exit[i].y() > max_y_exit ) max_y_exit = exit[i].y();
+ }
+ if (min_x_entry > max_y_exit) return false;
+
+ //////////////////////////////////////////////////
+ // The XZ plane
+
+ // Test case #3, min(z_entry) > max(x_exit)
+ // Test case #4, min(x_entry) > max(z_exit)
+ Real min_z_entry = entry[0].z();
+ Real max_z_exit = exit[0].z();
+ for(unsigned int i = 1; i < 4; ++i) {
+ if (entry[i].z() < min_z_entry) min_z_entry = entry[i].z();
+ if ( exit[i].z() > max_z_exit ) max_z_exit = exit[i].z();
+ }
+ if (min_z_entry > max_x_exit) return false;
+ if (min_x_entry > max_z_exit) return false;
+
+ //////////////////////////////////////////////////
+ // The YZ plane
+
+ // Test case #5, min(z_entry) > max(y_exit)
+ // Test case #6, min(y_entry) > max(z_exit)
+ if (min_z_entry > max_y_exit) return false;
+ if (min_y_entry > max_z_exit) return false;
- return INTERSECT_BOTH;
+ return true;
}
Modified: branches/itanium2/Model/Groups/FrustumKDTree.h
==============================================================================
--- branches/itanium2/Model/Groups/FrustumKDTree.h (original)
+++ branches/itanium2/Model/Groups/FrustumKDTree.h Tue Sep 13 14:41:30
2005
@@ -1,11 +1,11 @@
/*
For more information, please see: http://software.sci.utah.edu
-
+
The MIT License
-
+
Copyright (c) 2005
Scientific Computing and Imaging Institue, University of Utah
-
+
License for the specific language governing rights and limitations under
Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the "Software"),
@@ -13,10 +13,10 @@
the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:
-
+
The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.
-
+
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
@@ -59,11 +59,10 @@
PacketFrustum( const RayPacket &rays );
// Create a frustum given a common origin and four bounding vectors.
- PacketFrustum( const Point &origin_, const Vector &bound0_,
- const Vector &bound1_,
- const Vector &bound2_,
- const Vector &bound3_ ) :
- frustum_origin( origin_ )
+ PacketFrustum( const Point &origin_,
+ const Vector &bound0_, const Vector &bound1_,
+ const Vector &bound2_, const Vector &bound3_ ) :
+ frustum_origin( origin_ )
{
frustum_bound[0] = bound0_;
frustum_bound[1] = bound1_;
@@ -100,20 +99,20 @@
// Intersect the specified frustrum with the kdtree.
enum IntersectCase { INTERSECT_NONE = 0x0, // Cannot be determined by
// basic tests.
- INTERSECT_MIN = 0x1,
- INTERSECT_MAX = 0x2,
+ INTERSECT_MIN = 0x1,
+ INTERSECT_MAX = 0x2,
INTERSECT_BOTH = 0x3 };
// Intersect the specified frustrum with an internal node.
- IntersectCase frustum_node_intersect(const RenderContext& context,
- const KDTreeNode *node,
- const PacketFrustum &frustum,
+ IntersectCase frustum_node_intersect(const RenderContext& context,
+ const KDTreeNode *node,
+ const PacketFrustum &frustum,
const BBox &node_bounds );
// Intersect the specified frustrum with a leaf.
- IntersectCase frustum_leaf_intersect(const RenderContext& context,
- KDTreeLeafNode *node,
- PacketFrustum &frustum );
+ bool frustum_leaf_intersect(const RenderContext& context,
+ PacketFrustum &frustum,
+ const BBox& leaf_bounds );
public:
/////////////////////////////////////////////////////////////////////////
@@ -125,7 +124,7 @@
KDTree( kdtree_, material_ )
{ }
- // Intersection method -- Intersect frustrum with kdtree then call
+ // Intersection method -- Intersect frustrum with kdtree then call
// KDTree::intersect.
virtual void intersect(const RenderContext& context, RayPacket& rays)
const;
};
- [MANTA] r547 - branches/itanium2/Model/Groups, bigler, 09/13/2005
Archive powered by MHonArc 2.6.16.
