-
sparker
thiago
Manta Interactive Ray Tracer Development Mailing List
Text archives Help
- From: abe@sci.utah.edu
- To: manta@sci.utah.edu
- Subject: [MANTA] r543 - branches/itanium2/Model/Groups
- Date: Tue, 13 Sep 2005 02:17:38 -0600 (MDT)
Author: abe
Date: Tue Sep 13 02:17:37 2005
New Revision: 543
Modified:
branches/itanium2/Model/Groups/FrustumKDTree.cc
branches/itanium2/Model/Groups/FrustumKDTree.h
branches/itanium2/Model/Groups/KDTree.h
Log:
Initial (rough and untested) version of frustum-internal node intersection
function.
M Model/Groups/FrustumKDTree.cc
M Model/Groups/FrustumKDTree.h
M Model/Groups/KDTree.h
Modified: branches/itanium2/Model/Groups/FrustumKDTree.cc
==============================================================================
--- branches/itanium2/Model/Groups/FrustumKDTree.cc (original)
+++ branches/itanium2/Model/Groups/FrustumKDTree.cc Tue Sep 13 02:17:37
2005
@@ -28,9 +28,8 @@
#include <Model/Groups/FrustumKDTree.h>
-#include <limits>
-using std::numeric_limits;
-
+#include <SCIRun/Core/Math/MinMax.h>
+#include <float.h>
#include <Model/Intersections/Plane.h>
using namespace Manta;
@@ -80,8 +79,8 @@
typedef VectorT<Real, 2> Vector2;
typedef PointT <Real, 2> Point2;
- Vector2 min( std::numeric_limits<Real>::max(),
std::numeric_limits<Real>::max() );
- Vector2 max( -std::numeric_limits<Real>::max(),
-std::numeric_limits<Real>::max() );
+ Vector2 min( FLT_MAX, FLT_MAX );
+ Vector2 max( -FLT_MAX, -FLT_MAX );
for (int i=0;i<rays.getSize();++i) {
const RayPacket::Element &e = rays.get(i);
@@ -141,7 +140,7 @@
///////////////////////////////////////////////////////////////////////
// Intersect the frustum down the kdtree.
-
+
}
@@ -149,9 +148,120 @@
/////////////////////////////////////////////////////////////////////////
// Intersect the specified frustum with an internal node.
-FrustumKDTree::IntersectCase FrustumKDTree::frustum_node_intersect(const
RenderContext& context, KDTreeInternalNode *node, PacketFrustum &frustum ) {
+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;
+
+ typedef PointT<Real,2> Point2;
+
+ // 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;
+ plane_axis[1] = (axis+2)%3;
+
+
/////////////////////////////////////////////////////////////////////////////
+ // 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
+
+ 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) {
+ n[j] = SCIRun::Max( n[j], pt[plane_axis[j]] );
+ f[j] = SCIRun::Min( f[j], pt[plane_axis[j]] );
+ }
+ }
+
+
/////////////////////////////////////////////////////////////////////////////
+ // 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]) )
+ return INTERSECT_BOTH;
- 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;
+ }
+
+ // Do we need to check both plane axis?
+
+
/////////////////////////////////////////////////////////////////////////////
+ // 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;
+ }
+ // Case "B-"
+ else {
+ result &= B_child;
+ }
+
+ }
+
+ // Frustum intersection below node.
+ else {
+
+ // Case "B+"
+ if (frustum.direction(plane_axis[i])==1) {
+ result &= B_child;
+ }
+ // Case "A-"
+ else {
+ result &= A_child;
+ }
+ }
+ }
+
+ // Return the result.
+ return (IntersectCase)result;
}
/////////////////////////////////////////////////////////////////////////
Modified: branches/itanium2/Model/Groups/FrustumKDTree.h
==============================================================================
--- branches/itanium2/Model/Groups/FrustumKDTree.h (original)
+++ branches/itanium2/Model/Groups/FrustumKDTree.h Tue Sep 13 02:17:37
2005
@@ -46,9 +46,10 @@
// Container for a bounding frustum about a ray packet.
class PacketFrustum {
private:
- Point frustum_origin; // Common origin.
- Vector frustum_bound[4]; // Four vectors which bound
the frustum.
-
+ Point frustum_origin; // Common origin.
+ Vector frustum_bound[4]; // Four vectors
which bound the frustum.
+ unsigned int frustum_direction[3]; // All rays in
frustum must have the same direction.
+
public:
// Create a frustum around the specified ray packet.
Assumes all rays
// have common origin and all rays are in the same
hemisphere.
@@ -70,6 +71,9 @@
// Accessors.
const Point &origin() const { return
frustum_origin; };
const Vector &bound( int i ) const { return
frustum_bound[i]; };
+
+ // Direction, sign mask of all bounding rays assumed to be the same.
+ unsigned int direction( int i ) const { return frustum_direction[i]; };
};
/////////////////////////////////////////////////////////////////////////////
@@ -83,7 +87,8 @@
// with the tree.
class FrustumKDTree : public KDTree {
- protected:
+ // protected:
+ public:
/////////////////////////////////////////////////////////////////////////
// Create a frustum from a ray packet, and intersect
with the kdtree.
void packet_intersect(const RenderContext& context,
RayPacket &rays );
@@ -96,7 +101,10 @@
INTERSECT_BOTH = 0x3 };
// Intersect the specified frustrum with an internal
node.
- IntersectCase frustum_node_intersect(const
RenderContext& context, KDTreeInternalNode *node, 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 );
Modified: branches/itanium2/Model/Groups/KDTree.h
==============================================================================
--- branches/itanium2/Model/Groups/KDTree.h (original)
+++ branches/itanium2/Model/Groups/KDTree.h Tue Sep 13 02:17:37 2005
@@ -171,14 +171,14 @@
KDTreeInternalNode internal;
KDTreeLeafNode leaf;
- bool hasLeftChild() { return internal.flags &
KDNODE_LEFT_CHILD_MASK; }
- bool hasRightChild() { return internal.flags &
KDNODE_RIGHT_CHILD_MASK; }
+ bool hasLeftChild() const { return internal.flags &
KDNODE_LEFT_CHILD_MASK; }
+ bool hasRightChild() const { return internal.flags &
KDNODE_RIGHT_CHILD_MASK; }
KDTreeNode* left() { return
hasLeftChild()?this+internal.left : NULL; }
KDTreeNode* right() { return hasRightChild()?
(hasLeftChild()?this+internal.left+1:this+internal.left) : 0; }
- float split() { return internal.split; }
- bool isInternal() { return internal.flags &
KDNODE_INTERNAL_MASK; }
- unsigned int axis() { return internal.flags &
KDNODE_AXIS_MASK; }
+ float split() const { return internal.split; }
+ bool isInternal() const { return internal.flags &
KDNODE_INTERNAL_MASK; }
+ unsigned int axis() const { return internal.flags &
KDNODE_AXIS_MASK; }
unsigned int listBegin() { return leaf.listBegin; }
unsigned int listSize() { return leaf.listLen; }
@@ -276,11 +276,11 @@
// This method is called to intersect a single ray
with the kdtree.
// void _intersect(const Ray* ray, RayPacket::Element
&e, RayTriIntersectUserData &isectData, const RenderContext &context, float
_minDist=-1, float _maxDist=-1) const;
- void KDTree::intersect_node( KDTreeNode *startNode,
- const Ray* ray, RayPacket::Element &e,
- RayTriIntersectUserData &isectData,
- const RenderContext &context,
- float minDist, float maxDist) const;
+ void intersect_node( KDTreeNode *startNode,
+ const Ray* ray, RayPacket::Element &e,
+ RayTriIntersectUserData &isectData,
+ const RenderContext &context,
+ float minDist, float maxDist) const;
public:
// Constructor.
- [MANTA] r543 - branches/itanium2/Model/Groups, abe, 09/13/2005
Archive powered by MHonArc 2.6.16.
