-
sparker
thiago
Manta Interactive Ray Tracer Development Mailing List
Text archives Help
- From: abe@sci.utah.edu
- To: manta@sci.utah.edu
- Subject: [MANTA] r541 - in branches/itanium2: Interface Model/Groups
- Date: Mon, 12 Sep 2005 17:02:41 -0600 (MDT)
Author: abe
Date: Mon Sep 12 17:02:38 2005
New Revision: 541
Added:
branches/itanium2/Model/Groups/FrustumKDTree.cc
branches/itanium2/Model/Groups/FrustumKDTree.h
Modified:
branches/itanium2/Interface/RayPacket.h
branches/itanium2/Model/Groups/CMakeLists.txt
branches/itanium2/Model/Groups/KDTree.cc
branches/itanium2/Model/Groups/KDTree.h
Log:
Initial commit for structure outline of Frustum-KDTree intersection code.
A Model/Groups/FrustumKDTree.cc
A Model/Groups/FrustumKDTree.h
M Interface/RayPacket.h
M Model/Groups/KDTree.cc
M Model/Groups/KDTree.h
M Model/Groups/CMakeLists.txt
Modified: branches/itanium2/Interface/RayPacket.h
==============================================================================
--- branches/itanium2/Interface/RayPacket.h (original)
+++ branches/itanium2/Interface/RayPacket.h Mon Sep 12 17:02:38 2005
@@ -28,7 +28,10 @@
// HaveFrame = 0x100,
HaveNormals = 0x200,
HaveUnitNormals = 0x300,
- HaveInverseDirections = 0x800 };
+
+ HaveInverseDirections = 0x800, // signMask and inverseDirection
computed.
+ ConstantDirections = 0xc00 // All of the rays
have the same signMask
+ };
inline RayPacket(RayPacketData& data, int size, int depth, int flags);
@@ -47,6 +50,9 @@
int getFlags() const {
return flags;
}
+
+ bool getFlags( int flag ) const { return (flags & flag) ==
flag; };
+
int setFlags(int new_flags)
{
flags = new_flags;
@@ -86,11 +92,14 @@
Color ambientLight;
Color light;
- double importance; // for ray pruning
+ double importance; // for ray pruning
int shadowBegin, shadowEnd;
int whichEye;
- int signMask[3]; // This is set at the same time as inverse direction.
+
+ // Mask describing ray direction, 0==negative
1==positive
+ // This is set at the same time as inverse direction.
+ int signMask[3];
};
const Element& get(int which) const {
Modified: branches/itanium2/Model/Groups/CMakeLists.txt
==============================================================================
--- branches/itanium2/Model/Groups/CMakeLists.txt (original)
+++ branches/itanium2/Model/Groups/CMakeLists.txt Mon Sep 12 17:02:38
2005
@@ -12,10 +12,11 @@
Groups/TransparentKDTree.cc
Groups/KDTreeLoader.h
Groups/KDTreeLoader.cc
+ Groups/FrustumKDTree.h
+ Groups/FrustumKDTree.cc
Groups/PsiGammaTable.cc
Groups/PsiGammaTable.h
Groups/VolumeGrid.h
Groups/varray.h
-# Groups/Grid.h
-# Groups/Grid.cc
+
)
Added: branches/itanium2/Model/Groups/FrustumKDTree.cc
==============================================================================
--- (empty file)
+++ branches/itanium2/Model/Groups/FrustumKDTree.cc Mon Sep 12 17:02:38
2005
@@ -0,0 +1,163 @@
+/*
+ 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"),
+ to deal in the Software without restriction, including without limitation
+ 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
+ THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ DEALINGS IN THE SOFTWARE.
+ */
+
+#include <Model/Groups/FrustumKDTree.h>
+
+#include <limits>
+using std::numeric_limits;
+
+#include <Model/Intersections/Plane.h>
+
+using namespace Manta;
+using namespace Kdtree;
+
+/////////////////////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////////////////////
+// PACKET FRUSTRUM PACKET FRUSTRUM PACKET FRUSTRUM PACKET FRUSTRUM PACKET
+/////////////////////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////////////////////
+
+// 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 ) {
+
+ // Assume that all rays have a common origin.
+ frustum_origin = rays.get(0).ray.origin();
+
+
/////////////////////////////////////////////////////////////////////////////
+ // Choose a plane to intersect all of the rays with based on the
direction
+ // of the rays.
+ Point plane_point;
+ Vector plane_normal;
+
+ for (int i=0;i<3;++i) {
+ int signMask = rays.get(0).signMask[i];
+
+ // Compute the plane point and normal.
+ plane_point [i] = (2.0 * signMask) - 1.0; // signMask[i]
now in {-1,1}
+ plane_normal[i] = plane_point[i] * 0.577350;
+ }
+
+
/////////////////////////////////////////////////////////////////////////////
+ // Compute the axes of a coordinate system on the plane.
+ Vector plane_u, plane_v;
+
+ // Project x and y axis to the plane (plane normal is never either x
or y).
+ plane_u = (Vector(1,0,0) - (plane_normal * Dot( Vector(1,0,0),
plane_normal ) ) );
+ plane_u.normalize();
+
+ plane_v = (Vector(0,1,0) - (plane_normal * Dot( Vector(0,1,0),
plane_normal ) ) );
+ plane_v.normalize();
+
+
/////////////////////////////////////////////////////////////////////////////
+ // Find min and max corners of bounding frustum intersected with all
rays in
+ // packet.
+ 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() );
+
+ for (int i=0;i<rays.getSize();++i) {
+ const RayPacket::Element &e = rays.get(i);
+
+ // Intersect the ray with the plane.
+ Real t;
+ Intersection::intersectPlane( plane_point, plane_normal, t,
e.ray );
+
+ // Compute intersection point in world coords.
+ Vector i_vec( e.ray.origin() + (e.ray.direction() * t) );
+ i_vec = i_vec - (Vector)plane_point;
+
+ // Determine the intersection point in plane coordinates.
+ Point2 p;
+ p[0] = Dot( i_vec, plane_u );
+ p[1] = Dot( i_vec, plane_v );
+
+ // Check p against the bounds.
+ for (int j=0;j<2;++j) {
+ if (p[j] < min[j]) min[j] = p[j];
+ 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])) - frustum_origin;
+ frustum_bound[1] = (plane_point + (plane_u * max[0]) + (plane_v *
min[1])) - frustum_origin;
+ frustum_bound[2] = (plane_point + (plane_u * max[0]) + (plane_v *
max[1])) - frustum_origin;
+ frustum_bound[3] = (plane_point + (plane_u * min[0]) + (plane_v *
max[1])) - frustum_origin;
+}
+
+
+/////////////////////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////////////////////
+// FRUSTRUM KD TREE FRUSTRUM KD TREE FRUSTRUM KD TREE FRUSTRUM KD TREE FR
+/////////////////////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////////////////////
+
+/////////////////////////////////////////////////////////////////////////
+// Create a frustum from a ray packet, and intersect with the kdtree.
+void FrustumKDTree::packet_intersect(const RenderContext& context, RayPacket
&rays ) {
+
+ ///////////////////////////////////////////////////////////////////////
+ // Check to make sure the ray packet is big enough and has the
correct flags set.
+ 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, KDTreeInternalNode *node, PacketFrustum &frustum ) {
+
+ return INTERSECT_BOTH;
+}
+
+/////////////////////////////////////////////////////////////////////////
+// Intersect the specified frustum with a leaf.
+FrustumKDTree::IntersectCase FrustumKDTree::frustum_leaf_intersect(const
RenderContext& context, KDTreeLeafNode *node, PacketFrustum &frustum ) {
+
+ return INTERSECT_BOTH;
+}
+
Added: branches/itanium2/Model/Groups/FrustumKDTree.h
==============================================================================
--- (empty file)
+++ branches/itanium2/Model/Groups/FrustumKDTree.h Mon Sep 12 17:02:38
2005
@@ -0,0 +1,125 @@
+/*
+ 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"),
+ to deal in the Software without restriction, including without limitation
+ 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
+ THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ DEALINGS IN THE SOFTWARE.
+ */
+
+#ifndef __FRUSTUMKDTREE_H__
+#define __FRUSTUMKDTREE_H__
+
+#include <MantaTypes.h>
+#include <Interface/RayPacket.h>
+#include <Model/Groups/KDTree.h>
+
+namespace Manta {
+
+ namespace Kdtree {
+
+
/////////////////////////////////////////////////////////////////////////////
+
/////////////////////////////////////////////////////////////////////////////
+ // PACKET FRUSTUM PACKET FRUSTUM PACKET FRUSTUM PACKET
FRUSTUM PACKET
+
/////////////////////////////////////////////////////////////////////////////
+
/////////////////////////////////////////////////////////////////////////////
+
+ // 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.
+
+ public:
+ // Create a frustum around the specified ray packet.
Assumes all rays
+ // have common origin and all rays are in the same
hemisphere.
+ 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_ )
+ {
+ frustum_bound[0] = bound0_;
+ frustum_bound[1] = bound1_;
+ frustum_bound[2] = bound2_;
+ frustum_bound[3] = bound3_;
+ }
+
+ // Accessors.
+ const Point &origin() const { return
frustum_origin; };
+ const Vector &bound( int i ) const { return
frustum_bound[i]; };
+ };
+
+
/////////////////////////////////////////////////////////////////////////////
+
/////////////////////////////////////////////////////////////////////////////
+ // FRUSTUM KD TREE FRUSTUM KD TREE FRUSTUM KD TREE FRUSTUM
KD TREE FR
+
/////////////////////////////////////////////////////////////////////////////
+
/////////////////////////////////////////////////////////////////////////////
+
+ // This class implements a kdtree traversal where the
frustrum of a ray packet
+ // is first intersected with the kdtree before individual
rays are intersected
+ // with the tree.
+
+ class FrustumKDTree : public KDTree {
+ protected:
+
/////////////////////////////////////////////////////////////////////////
+ // Create a frustum from a ray packet, and intersect
with the kdtree.
+ void packet_intersect(const RenderContext& context,
RayPacket &rays );
+
+
/////////////////////////////////////////////////////////////////////////
+ // 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_BOTH = 0x3 };
+
+ // Intersect the specified frustrum with an internal
node.
+ IntersectCase frustum_node_intersect(const
RenderContext& context, KDTreeInternalNode *node, PacketFrustum &frustum );
+
+ // Intersect the specified frustrum with a leaf.
+ IntersectCase frustum_leaf_intersect(const
RenderContext& context, KDTreeLeafNode *node, PacketFrustum &frustum );
+
+ public:
+
/////////////////////////////////////////////////////////////////////////
+ // Create a FrustrumKDTree which data may be loaded
into.
+ FrustumKDTree( Material *material_ ) : KDTree(
material_ ) { };
+
+ // Use data owned by another kdtree.
+ FrustumKDTree( KDTree *kdtree_, Material *material_ )
: KDTree( kdtree_, material_ ) { }
+
+ // Intersection method -- Intersect frustrum with
kdtree then call
+ // KDTree::intersect.
+ virtual void intersect(const RenderContext& context,
RayPacket& rays) const;
+ };
+
+ };
+
+};
+
+#endif
+
+
+
+
Modified: branches/itanium2/Model/Groups/KDTree.cc
==============================================================================
--- branches/itanium2/Model/Groups/KDTree.cc (original)
+++ branches/itanium2/Model/Groups/KDTree.cc Mon Sep 12 17:02:38 2005
@@ -157,7 +157,7 @@
// Send the ray to the _intersect function.
isectData.rayHitTriIndex = -1;
- _intersect( &e.ray, e, isectData, context,
(float)minDist, (float)maxDist);
+ intersect_node( rootNode, &e.ray, e, isectData,
context, (float)minDist, (float)maxDist);
}
}
@@ -182,14 +182,16 @@
// Traversal Stack Entry.
struct TravStackEntry {
- KDTreeNode* node; //8 bytes
+ 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, const RenderContext &context,
-
float minDist, float maxDist) const
+void KDTree::intersect_node( KDTreeNode *startNode,
+ const Ray* ray, RayPacket::Element &e,
+ RayTriIntersectUserData &isectData,
+ const RenderContext &context,
+
float minDist, float maxDist) const
{
// Keep a stack of entry and exit positions into the traversal nodes.
@@ -201,11 +203,10 @@
bool foundIntersection = false;
int tmp;
-
// Initialize the first two entries on the stack.
entryPos = 0;
- nearNode = rootNode;
- travStack[0].node = rootNode;
+ nearNode = startNode;
+ travStack[0].node = startNode;
travStack[0].prev = 1;
// Check for the case that the minimum intersection point is behind
the origin.
@@ -219,6 +220,7 @@
while (travStack[entryPos].prev) {
// Traverse down until we find a leaf node.
+ #pragma swp
while (nearNode && nearNode->isInternal()) {
// Determine the axis and the split point.
Modified: branches/itanium2/Model/Groups/KDTree.h
==============================================================================
--- branches/itanium2/Model/Groups/KDTree.h (original)
+++ branches/itanium2/Model/Groups/KDTree.h Mon Sep 12 17:02:38 2005
@@ -255,22 +255,33 @@
// The Kdtree::load(...) function is used to load
data into the kdtree.
friend int Manta::Kdtree::load( KDTree *kdtree, const
char *filename, int np );
- private:
+ protected:
BBox bbox;
-
KDTreeNode *rootNode;
-
+
+ private:
VArray<int> *triIndices;
VArray<Triangle> *tris;
Vectorf *normals;
- private:
+ protected:
+ // Copy data pointers from another kdtree. (Used by
derived classes.)
+ KDTree( KDTree *kdtree_, Material *material_ ) :
+ PrimitiveCommon( material_ ),
+ rootNode( kdtree_->rootNode ), triIndices(
kdtree_->triIndices ),
+ tris( kdtree_->tris ), normals(
kdtree_->normals ) { bbox.extendByBox( bbox ); };
+
// This method intersects a list of triangles with
the ray.
int intersectTriangles(const Ray* ray, unsigned int
listBegin, int listSize, float maxDist, void *userData, const RenderContext
&context) const;
- // This method is called by the above method with a
hansong ray.
- void _intersect(const Ray* ray, RayPacket::Element
&e, RayTriIntersectUserData &isectData, const RenderContext &context, float
_minDist=-1, float _maxDist=-1) const;
-
+ // 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;
+
public:
// Constructor.
KDTree( Material *material_ ) : PrimitiveCommon(
material_ ) { };
@@ -282,7 +293,7 @@
};
// Primitive Interface.
- void intersect (const RenderContext& context,
RayPacket& rays) const;
+ virtual void intersect(const RenderContext& context,
RayPacket& rays) const;
void computeNormal (const RenderContext& context,
RayPacket& rays) const;
void computeBounds (const PreprocessContext
&context, BBox &box_ ) const { box_.extendByBox( bbox ); }
void computeBounds ( BBox &box_ ) const {
box_.extendByBox( bbox ); }
- [MANTA] r541 - in branches/itanium2: Interface Model/Groups, abe, 09/12/2005
Archive powered by MHonArc 2.6.16.
