-
sparker
thiago
Manta Interactive Ray Tracer Development Mailing List
Text archives Help
- From: abe@sci.utah.edu
- To: manta@sci.utah.edu
- Subject: [MANTA] r1197 - in trunk: Model/Groups SwigInterface
- Date: Fri, 29 Sep 2006 03:12:26 -0600 (MDT)
Author: abe
Date: Fri Sep 29 03:12:25 2006
New Revision: 1197
Added:
trunk/Model/Groups/Build_Approx_cc.cc
trunk/Model/Groups/Build_Approx_cc.h
Modified:
trunk/Model/Groups/Build_OnLogn_cc.cc
trunk/Model/Groups/Build_OnLogn_cc.h
trunk/Model/Groups/CMakeLists.txt
trunk/Model/Groups/KDTreeDyn.cc
trunk/Model/Groups/KDTreeDyn.h
trunk/SwigInterface/kdtreedyn.py
trunk/SwigInterface/manta.i
Log:
Added approximate sweep build. Uses a variable number of split candidates.
A Model/Groups/Build_Approx_cc.cc
A Model/Groups/Build_Approx_cc.h
M Model/Groups/CMakeLists.txt
M SwigInterface/manta.i
Added command line option to select builder:
python ../SwigInterface/kdtreedyn.py -f /home/sci/abe/models/bowl.obj
--builder=Build_Approx_cc
M SwigInterface/kdtreedyn.py
Added function to compute tree cost based on SAH.
M Model/Groups/KDTreeDyn.cc
M Model/Groups/KDTreeDyn.h
Incremental bug fixes.
M Model/Groups/Build_OnLogn_cc.h
M Model/Groups/Build_OnLogn_cc.cc
Added: trunk/Model/Groups/Build_Approx_cc.cc
==============================================================================
--- (empty file)
+++ trunk/Model/Groups/Build_Approx_cc.cc Fri Sep 29 03:12:25 2006
@@ -0,0 +1,442 @@
+/*
+ For more information, please see: http://software.sci.utah.edu
+
+ The MIT License
+
+ Copyright (c) 2005-2006
+ Scientific Computing and Imaging Institute, 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/Build_Approx_cc.h>
+
+#include <SCIRun/Core/Math/MinMax.h>
+#include <SCIRun/Core/Thread/Time.h>
+
+#include <limits>
+#include <iostream>
+#include <iomanip>
+
+using namespace std;
+using namespace SCIRun;
+using namespace Manta;
+
+namespace Approx_cc_file {
+
+
///////////////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////////
+ // Split Plane
+
///////////////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////////
+
+ struct SplitPlane {
+ Real cost;
+ Real split;
+ Integer axis;
+ Integer left_side; // Amount of geometry on either side.
+ Integer right_side;
+ };
+
+
///////////////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////////
+ // Find a split plane along a specified axis.
+
///////////////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////////
+
+ // This method finds the best split along the given axis. The individual
splits
+ // are computed using a delta computed as: interval / cubed_root(
geometry.size() )
+
+ void find_approx_split( const BoundsList &geometry,
+ const IndexList &indices,
+ const BBox &node_bounds,
+ const unsigned int &axis,
+ SplitPlane &result )
+ {
+
+
/////////////////////////////////////////////////////////////////////////////
+ // Precompute extents and cross section area for each dimension.
+
+ const int dim0 = (axis+1)%3;
+ const int dim1 = (axis+2)%3;
+ const Real extent_dim0 = node_bounds[1][dim0] - node_bounds[0][dim0];
+ const Real extent_dim1 = node_bounds[1][dim1] - node_bounds[0][dim1];
+
+ const Real ends_area = extent_dim0 * extent_dim1 * 2;
+ const Real cross_section = (extent_dim0 + extent_dim1) * 2;
+
+
/////////////////////////////////////////////////////////////////////////////
+ // Determine how many candidates to use.
+ Integer total_candidates = (Integer)cbrtf((float)geometry.size());
+
+
/////////////////////////////////////////////////////////////////////////////
+ // Initialize counters.
+ vector<Integer> left_side ( total_candidates );
+ vector<Integer> right_side( total_candidates );
+
+ memset( &left_side[0], 0, total_candidates*sizeof(Integer) );
+ memset( &right_side[0], 0, total_candidates*sizeof(Integer) );
+
+
/////////////////////////////////////////////////////////////////////////////
+ // Iterate over the geometry
+
+ const Real interval0 = node_bounds[0][axis];
+ const Real interval1 = node_bounds[1][axis];
+ const Real delta = (interval1 - interval0) / (Real)total_candidates;
+
+ for (int index=0;index<indices.size();++index) {
+
+ const BBox &bounds = geometry[ indices[index] ];
+ const Real &bounds_min = bounds[0][axis];
+ const Real &bounds_max = bounds[1][axis];
+
+ Real candidate_split = interval0;
+
+ // Iterate over the candidates.
+ for (int i=0;i<total_candidates;++i) {
+
+ // Check the left and right split candidates.
+ left_side[i] += ((bounds_min <= candidate_split));
+ right_side[i] += ((bounds_max > candidate_split));
+
+ // Increment the split plane.
+ candidate_split += delta;
+ }
+ }
+
+
/////////////////////////////////////////////////////////////////////////////
+ // Compute cost of each split candidate.
+
+ // Initialize cost.
+ result.cost = std::numeric_limits<Real>::max();
+
+ // Iterate back over the candidates.
+ Real candidate_split = interval0;
+ for (int i=0;i<total_candidates;++i) {
+
+ const Real left_area = (candidate_split - interval0) * cross_section
+ ends_area;
+ const Real right_area = (interval1 - candidate_split) * cross_section
+ ends_area;
+
+ const Real cost =
+ (Real)(left_side[i])*(left_area) +
+ (Real)(right_side[i])*(right_area);
+
+ // Check to see if this is the new min.
+ if (cost < result.cost) {
+ result.cost = cost;
+ result.split = candidate_split;
+ result.left_side = left_side[i];
+ result.right_side = right_side[i];
+ }
+
+ // Increment the split location.
+ candidate_split += delta;
+ }
+
+ result.axis = axis;
+ }
+
+
///////////////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////////
+ // Splice Indices.
+
///////////////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////////
+
+ void splice_indices( const BoundsList &geometry,
+ const IndexList &source,
+ const SplitPlane &plane,
+ IndexList &left_index_list,
+ IndexList &right_index_list )
+ {
+
+ left_index_list.resize( plane.left_side );
+ right_index_list.resize( plane.right_side );
+
+ Integer left_count = 0;
+ Integer right_count = 0;
+
+ for (int i=0;i<source.size();++i) {
+
+ const Integer &index = source[i];
+
+ const Real &bound0 = geometry[index][0][plane.axis];
+ const Real &bound1 = geometry[index][1][plane.axis];
+
+ // Is there a conditional/ increment instruction?
+#if 1
+ if (bound0 < plane.split)
+ left_index_list[left_count++] = index;
+
+ if (bound1 > plane.split)
+ right_index_list[right_count++] = index;
+#else
+ left_index_list [left_count] = index;
+ right_index_list[right_count] = index;
+
+ if (bound0 < plane.split)
+ left_count++;
+
+ if (bound1 > plane.split)
+ right_count++;
+#endif
+ }
+ }
+
+
///////////////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////////
+ // Build frame.
+
///////////////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////////
+ struct Frame {
+ Frame( const BBox &bounds_, NodeOffset node_, Integer depth_ ) :
+ bounds( bounds_ ),
+ node( node_ ),
+ depth( depth_ ) { };
+
+ IndexList index_list; // Array of global face indices.
+
+ BBox bounds; // Node bounds.
+ NodeOffset node; // Index offset of allocated node.
+ Integer depth; // Depth.
+
+ // (Rely on "index_list.size()" instead.)
+ // Integer size; // Total number of bounding boxes (not
# candidates)
+ };
+
+};
+
+///////////////////////////////////////////////////////////////////////////////
+///////////////////////////////////////////////////////////////////////////////
+// APPROX BUILD APPROX BUILD APPROX BUILD APPROX BUILD APPROX BUILD
APPROX
+///////////////////////////////////////////////////////////////////////////////
+///////////////////////////////////////////////////////////////////////////////
+
+
+
+void Build_Approx_cc::build( KDTreeDyn *kdtree ) throw (SCIRun::Exception&)
{
+
+ using namespace Approx_cc_file;
+
+ Real start_time = Time::currentSeconds();
+
+ const BoundsList &bounds_list = kdtree->bounds_list;
+
+ Integer max_depth = 0;
+ Integer max_leaf_size = 0;
+ Integer total_nodes = 0;
+ Integer total_leaves = 0;
+ Integer total_indices = 0;
+ Integer cost_trigger = 0;
+
+
/////////////////////////////////////////////////////////////////////////////
+
/////////////////////////////////////////////////////////////////////////////
+ // Initialize Build Stack
+
/////////////////////////////////////////////////////////////////////////////
+
/////////////////////////////////////////////////////////////////////////////
+
+ vector<Frame *> build_stack;
+ build_stack.reserve( depth_threshold+1 );
+
+
/////////////////////////////////////////////////////////////////////////////
+ // Add the root node to the build stack.
+
+ // Allocate the root stack frame.
+ const NodeOffset root_offset = kdtree->allocateNodePair();
+ Frame *root_frame = new Frame( kdtree->bbox,
+ root_offset,
+ 0 );
+
+ // Copy inital indices into root frame's index_list.
+ root_frame->index_list.resize( bounds_list.size() );
+ for (int i=0;i<bounds_list.size();++i) {
+ root_frame->index_list[i] = i;
+ }
+
+
/////////////////////////////////////////////////////////////////////////////
+ // Push the root frame on the stack.
+ build_stack.push_back( root_frame );
+
+
/////////////////////////////////////////////////////////////////////////////
+
/////////////////////////////////////////////////////////////////////////////
+ // Build Loop
+
/////////////////////////////////////////////////////////////////////////////
+
/////////////////////////////////////////////////////////////////////////////
+ while (build_stack.size()) {
+
+ // Get the next frame off the stack.
+ Frame *frame = build_stack.back();
+ build_stack.pop_back();
+
+ bool break_out = false;
+
+ // Drill down until a leaf is found.
+ while (1) {
+
+
///////////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////
+ // Create a Leaf.
+
///////////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////
+ if ((frame->index_list.size() < leaf_threshold) || // Condition: Leaf
threshold.
+ (frame->depth >= depth_threshold) || // Condition: Depth
threshold.
+ (break_out)
+ ) {
+
+
+
///////////////////////////////////////////////////////////////////////
+ // Set leaf fields.
+ KDTreeDyn::Node &leaf = kdtree->getNode(frame->node);
+
+ // Copy the index list.
+ leaf.listBegin = kdtree->allocateLeafList( frame->index_list );
+ leaf.listLen = frame->index_list.size();
+ leaf.type = KDTreeType::LeafType;
+
+ // DEBUG
+ leaf.size = leaf.listLen;
+
+ // Update stats
+ total_indices += frame->index_list.size();
+ max_leaf_size = SCIRun::Max( max_leaf_size, frame->index_list.size()
);
+ ++total_leaves;
+ ++total_nodes;
+
+ // Delete the frame.
+ delete frame;
+
+ break;
+ }
+ else {
+
+
///////////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////
+ // Find the best split.
+
///////////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////////
+
+ // Check each axis.
+ SplitPlane plane;
+ plane.cost = std::numeric_limits<Real>::max();
+
+ for (unsigned int axis=0;axis<3;++axis) {
+ SplitPlane result;
+ find_approx_split( bounds_list,
+ frame->index_list,
+ frame->bounds,
+ axis,
+ result );
+ // Check for the minimum cost.
+ if (result.cost < plane.cost) {
+ plane = result;
+ }
+ }
+
+
///////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////
+
+ // Check to see if the heuristic is improving anything.
+ const Real parent_cost = frame->bounds.computeArea() *
(Real)frame->index_list.size();
+
+ // Compare split cost with that of not splitting.
+ if (plane.cost > parent_cost*cost_threshold) {
+
+ cost_trigger++;
+
+ // Make a leaf instead.
+ break_out = true;
+ continue;
+ }
+
+
///////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////
+ // Allocate two children.
+
///////////////////////////////////////////////////////////////////////
+
///////////////////////////////////////////////////////////////////////
+
+ NodeOffset left_child_offset = kdtree->allocateNodePair();
+
+ // Update parent pointer.
+ KDTreeType::Node &parent_node = kdtree->getNode( frame->node );
+
+ parent_node.size = frame->index_list.size();
+ parent_node.leftOffset = left_child_offset;
+
+ // Allocate a new Stack frame for the right child.
+ Frame *left_frame = new Frame( frame->bounds, left_child_offset,
frame->depth+1 );
+ Frame *right_frame = new Frame( frame->bounds, left_child_offset+1,
frame->depth+1 );
+
+
///////////////////////////////////////////////////////////////////////
+ // Splice indices. Add mapping from parent index list to child index
list(s)
+ splice_indices( bounds_list,
+ frame->index_list,
+ plane,
+ left_frame->index_list,
+ right_frame->index_list );
+
+
///////////////////////////////////////////////////////////////////////
+
+ // Set the node split and axis fields.
+ parent_node.split = plane.split;
+ parent_node.type = plane.axis;
+
+ // Update the bounds of both child frames.
+ left_frame->bounds[1][plane.axis] = plane.split;
+ right_frame->bounds[0][plane.axis] = plane.split;
+
+ // Push the right frame on the stack.
+ build_stack.push_back( right_frame );
+
+ // Delete the old build frame.
+ Frame *old = frame;
+ frame = left_frame;
+ delete old;
+
+ // Update stats.
+ total_nodes += 2;
+ max_depth = SCIRun::Max( max_depth, frame->depth );
+
+ } // End if leaf else.
+
+ } // End drill down until a leaf.
+
+ } // End build stack loop.
+
+ Real end_time = Time::currentSeconds();
+
+ // Compute SAH quality.
+ Real sah_cost = kdtree->computeSAHCost();
+
+ std::cerr << "Build information: " << std::endl
+ << "max_depth " << max_depth << " (threshold " <<
depth_threshold << ")" << std::endl
+ << "max_leaf_size " << max_leaf_size << " (threshold " <<
leaf_threshold << ")" << std::endl
+ << "avg_leaf_size " <<
((Real)total_indices)/((Real)total_leaves) << std::endl
+ << "total_nodes " << total_nodes << std::endl
+ << "total_leaves " << total_leaves << std::endl
+ << "total_indices " << total_indices << std::endl
+ << "total faces " << kdtree->triangles.size() << std::endl
+ << "cost_threshold " << cost_trigger << std::endl
+ << "build time " << (end_time-start_time) << "s" << std::endl
+ << "tree quality " << sah_cost << std::endl;
+}
+
+
+
Added: trunk/Model/Groups/Build_Approx_cc.h
==============================================================================
--- (empty file)
+++ trunk/Model/Groups/Build_Approx_cc.h Fri Sep 29 03:12:25 2006
@@ -0,0 +1,65 @@
+#ifndef BUILD_APPROX_CC__H
+#define BUILD_APPROX_CC__H
+
+/*
+ For more information, please see: http://software.sci.utah.edu
+
+ The MIT License
+
+ Copyright (c) 2005-2006
+ Scientific Computing and Imaging Institute, 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 <MantaTypes.h>
+#include <Core/Geometry/BBox.h>
+
+#include <Model/Groups/KDTreeDyn.h>
+#include <SCIRun/Core/Exceptions/Exception.h>
+
+
+namespace Manta {
+
+ // Class containing build method.
+ class Build_Approx_cc {
+ public:
+ typedef KDTreeDyn KDTreeType;
+
+ enum { MaxCandidates = 8 };
+
+ // Thresholds.
+ int leaf_threshold;
+ int depth_threshold;
+ Real cost_threshold;
+
+ // Constructors.
+ Build_Approx_cc( int leaf_threshold_, int depth_threshold_, Real
cost_threshold_ ) :
+ leaf_threshold( leaf_threshold_ ),
+ depth_threshold( depth_threshold_ ),
+ cost_threshold( cost_threshold_ ) { }
+
+ // Build methods.
+ void build( KDTreeType *kdtree ) throw(SCIRun::Exception&);
+ };
+};
+
+#endif
+
Modified: trunk/Model/Groups/Build_OnLogn_cc.cc
==============================================================================
--- trunk/Model/Groups/Build_OnLogn_cc.cc (original)
+++ trunk/Model/Groups/Build_OnLogn_cc.cc Fri Sep 29 03:12:25 2006
@@ -50,6 +50,8 @@
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
+namespace OnLogn_cc_file {
+
// Flags to indicate if area of related triangle should be
// added/subtracted to left or right sum.
enum {
@@ -570,7 +572,7 @@
}
}
-
+};
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
@@ -580,6 +582,8 @@
void Build_OnLogn_cc::build( KDTreeDyn *kdtree ) throw (SCIRun::Exception&)
{
+ using namespace OnLogn_cc_file;
+
Real start_time = Time::currentSeconds();
const BoundsList &bounds_list = kdtree->bounds_list;
@@ -775,6 +779,9 @@
Real end_time = Time::currentSeconds();
+ // Compute SAH quality.
+ Real sah_cost = kdtree->computeSAHCost();
+
std::cerr << "Build information: " << std::endl
<< "max_depth " << max_depth << " (threshold " <<
depth_threshold << ")" << std::endl
<< "max_leaf_size " << max_leaf_size << " (threshold " <<
leaf_threshold << ")" << std::endl
@@ -784,11 +791,12 @@
<< "total_indices " << total_indices << std::endl
<< "total faces " << kdtree->triangles.size() << std::endl
<< "cost_threshold " << cost_trigger << std::endl
- << "build time " << (end_time-start_time) << "s" <<
std::endl;
+ << "build time " << (end_time-start_time) << "s" << std::endl
+ << "tree quality " << sah_cost << std::endl;
}
-
+namespace OnLogn_cc_file {
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
@@ -837,3 +845,4 @@
cerr << endl;
}
}
+};
Modified: trunk/Model/Groups/Build_OnLogn_cc.h
==============================================================================
--- trunk/Model/Groups/Build_OnLogn_cc.h (original)
+++ trunk/Model/Groups/Build_OnLogn_cc.h Fri Sep 29 03:12:25 2006
@@ -1,3 +1,7 @@
+
+#ifndef BUILD_ONLOGN_CC__H
+#define BUILD_ONLOGN_CC__H
+
/*
For more information, please see: http://software.sci.utah.edu
@@ -58,3 +62,4 @@
};
};
+#endif
Modified: trunk/Model/Groups/CMakeLists.txt
==============================================================================
--- trunk/Model/Groups/CMakeLists.txt (original)
+++ trunk/Model/Groups/CMakeLists.txt Fri Sep 29 03:12:25 2006
@@ -8,6 +8,8 @@
SET (Manta_Groups_SRCS
+ Groups/Build_Approx_cc.h
+ Groups/Build_Approx_cc.cc
Groups/Build_OnLogn_cc.h
Groups/Build_OnLogn_cc.cc
Groups/Load_OBJ_KDTreeDyn.h
Modified: trunk/Model/Groups/KDTreeDyn.cc
==============================================================================
--- trunk/Model/Groups/KDTreeDyn.cc (original)
+++ trunk/Model/Groups/KDTreeDyn.cc Fri Sep 29 03:12:25 2006
@@ -202,7 +202,7 @@
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
-// TRIANGLE IW TEMPLATE TRIANGLE IW TEMPLATE TRIANGLE IW TEMPLATE
TRIANGLE I
+// COMPUTE NORMAL COMPUTE NORMAL COMPUTE NORMAL COMPUTE NORMAL COMPUTE
NORM
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
@@ -222,6 +222,39 @@
data->normal[kv][ray] = mult * tri.n_v;
}
rays.setFlag(RayPacket::HaveUnitNormals);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+///////////////////////////////////////////////////////////////////////////////
+// COMPUTE SAH COST COMPUTE SAH COST COMPUTE SAH COST COMPUTE SAH COST
COMP
+///////////////////////////////////////////////////////////////////////////////
+///////////////////////////////////////////////////////////////////////////////
+
+
+Real KDTreeDyn::computeSAHCost_helper( KDTreeDyn_Node *node, const BBox
&bounds ) {
+
+ // Cost of traversing an interior node.
+ const static Real traversal_cost = 1.0;
+
+ if (node->type==KDTreeDyn::LeafType) {
+ // Compute the cost.
+ return 1.0 + bounds.computeArea() * (Real)node->listLen;
+ }
+ else {
+ // Compute the child bounds.
+ BBox left_bounds = bounds;
+ left_bounds[1][node->type] = node->split;
+
+ BBox right_bounds = bounds;
+ right_bounds[0][node->type] = node->split;
+
+ // Return the cost of traversing this node
+ // plus the cost of the children.
+ return
+ traversal_cost +
+ computeSAHCost_helper( &getNode( node->leftOffset ), left_bounds ) +
+ computeSAHCost_helper( &getNode( node->leftOffset+1 ), right_bounds );
+ }
}
Modified: trunk/Model/Groups/KDTreeDyn.h
==============================================================================
--- trunk/Model/Groups/KDTreeDyn.h (original)
+++ trunk/Model/Groups/KDTreeDyn.h Fri Sep 29 03:12:25 2006
@@ -132,6 +132,10 @@
}
BBox bbox; // Bounds of the whole kdtree.
+
+ // Cost of the whole tree.
+ Real computeSAHCost() {
+ return computeSAHCost_helper( &node_list[root_offset], bbox ); }
#ifndef SWIG
// Build interface.
@@ -175,6 +179,8 @@
void intersect_node( const Node* start_node, RayPacket& rays, int which,
float minDist, float maxDist) const;
+ Real computeSAHCost_helper( KDTreeDyn_Node *node, const BBox &bounds );
+
struct Stack {
const Node* node;
float far;
Modified: trunk/SwigInterface/kdtreedyn.py
==============================================================================
--- trunk/SwigInterface/kdtreedyn.py (original)
+++ trunk/SwigInterface/kdtreedyn.py Fri Sep 29 03:12:25 2006
@@ -28,8 +28,6 @@
def initialize_scene( frame, engine ):
-
-
###########################################################################
# Create basic scene with background.
scene = manta_new( Scene() )
@@ -47,6 +45,12 @@
scene.setLights(lights)
###########################################################################
+ # Create an empty scene.
+ world = manta_new( Group() )
+ scene.setObject( world )
+ engine.setScene( scene )
+
+
###########################################################################
# Load in the model data.
red = manta_new(Phong(Color(RGBColor(0.6, 0, 0)),
@@ -69,15 +73,15 @@
except AttributeError,e:
print "Could not find builder class: " + builder_name
return scene
+
+ print "Using builder: " + builder_name
# Construct the builder.
builder = builder_class( leaf_threshold,
depth_threshold,
cost_threshold )
- # Add the kdtree to the scene.
- world = manta_new( Group() )
-
+ # Execute the build.
try:
builder.build( kdtree )
except Exception,e:
@@ -91,10 +95,6 @@
# sphere = manta_new(Sphere(red, Vector(0,0,1.2), 1.0))
# world.add(sphere)
- # Add the scene to manta.
- scene.setObject( world )
- engine.setScene( scene )
-
# Create the explorer.
global explorer
explorer = KDTreeDynFrame( frame, frame.engine, kdtree )
@@ -127,7 +127,7 @@
def main():
- global file_name, leaf_threshold, depth_threshold, refinement_threshold,
cost_threshold
+ global file_name, leaf_threshold, depth_threshold, refinement_threshold,
cost_threshold, builder_name
# Default options.
num_workers = 1
@@ -139,7 +139,7 @@
"n:f:b:",
["np=",
"file=",
- "build=",
+ "builder=",
"leaf_threshold=",
"depth_threshold=",
"cost_threshold=" ] )
Modified: trunk/SwigInterface/manta.i
==============================================================================
--- trunk/SwigInterface/manta.i (original)
+++ trunk/SwigInterface/manta.i Fri Sep 29 03:12:25 2006
@@ -467,11 +467,13 @@
#include <Model/Groups/KDTreeDyn.h>
#include <Model/Groups/Load_OBJ_KDTreeDyn.h>
#include <Model/Groups/Build_OnLogn_cc.h>
+#include <Model/Groups/Build_Approx_cc.h>
%}
%include <Model/Groups/KDTreeDyn.h>
%include <Model/Groups/Load_OBJ_KDTreeDyn.h>
%include <Model/Groups/Build_OnLogn_cc.h>
+%include <Model/Groups/Build_Approx_cc.h>
/////////////////////////////////////////////////
// GLM.
- [MANTA] r1197 - in trunk: Model/Groups SwigInterface, abe, 09/29/2006
Archive powered by MHonArc 2.6.16.
