-
sparker
thiago
Manta Interactive Ray Tracer Development Mailing List
Text archives Help
- From: abe@sci.utah.edu
- To: manta@sci.utah.edu
- Subject: [MANTA] r1208 - trunk/Model/Groups
- Date: Fri, 6 Oct 2006 14:34:24 -0600 (MDT)
Author: abe
Date: Fri Oct 6 14:34:24 2006
New Revision: 1208
Modified:
trunk/Model/Groups/Build_Approx_cc.cc
trunk/Model/Groups/Build_OnLogn_cc.cc
trunk/Model/Groups/Build_OnLogn_cc.h
trunk/Model/Groups/KDTreeDyn.cc
trunk/Model/Groups/KDTreeDyn.h
Log:
Incremental change still trying to fix onlogn build.
M Groups/Build_OnLogn_cc.h
M Groups/KDTreeDyn.cc
M Groups/KDTreeDyn.h
M Groups/Build_Approx_cc.cc
M Groups/Build_OnLogn_cc.cc
Modified: trunk/Model/Groups/Build_Approx_cc.cc
==============================================================================
--- trunk/Model/Groups/Build_Approx_cc.cc (original)
+++ trunk/Model/Groups/Build_Approx_cc.cc Fri Oct 6 14:34:24 2006
@@ -82,9 +82,11 @@
const Real ends_area = extent_dim0 * extent_dim1 * 2;
const Real cross_section = (extent_dim0 + extent_dim1) * 2;
+ const Real node_area_inv = (Real)1.0 / node_bounds.computeArea();
+
/////////////////////////////////////////////////////////////////////////////
// Determine how many candidates to use.
- Integer total_candidates = (Integer)cbrtf((float)geometry.size());
+ Integer total_candidates = (Integer)cbrtf((float)indices.size());
/////////////////////////////////////////////////////////////////////////////
// Initialize counters.
@@ -131,12 +133,15 @@
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 left_probability =
+ ((candidate_split - interval0) * cross_section + ends_area) *
node_area_inv;
+
+ const Real right_probability =
+ ((interval1 - candidate_split) * cross_section + ends_area) *
node_area_inv;
const Real cost =
- (Real)(left_side[i])*(left_area) +
- (Real)(right_side[i])*(right_area);
+ (left_probability) *((Real)(left_side[i])) +
+ (right_probability)*((Real)(right_side[i]));
// Check to see if this is the new min.
if (cost < result.cost) {
@@ -181,7 +186,7 @@
// Is there a conditional/ increment instruction?
#if 1
- if (bound0 < plane.split)
+ if (bound0 <= plane.split)
left_index_list[left_count++] = index;
if (bound1 > plane.split)
@@ -190,7 +195,7 @@
left_index_list [left_count] = index;
right_index_list[right_count] = index;
- if (bound0 < plane.split)
+ if (bound0 <= plane.split)
left_count++;
if (bound1 > plane.split)
@@ -334,7 +339,7 @@
// 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,
@@ -342,6 +347,7 @@
frame->bounds,
axis,
result );
+
// Check for the minimum cost.
if (result.cost < plane.cost) {
plane = result;
@@ -354,7 +360,7 @@
///////////////////////////////////////////////////////////////////////
// Check to see if the heuristic is improving anything.
- const Real parent_cost = frame->bounds.computeArea() *
(Real)frame->index_list.size();
+ const Real parent_cost = (Real)frame->index_list.size();
// Compare split cost with that of not splitting.
if (plane.cost > parent_cost*cost_threshold) {
@@ -424,6 +430,8 @@
// Compute SAH quality.
Real sah_cost = kdtree->computeSAHCost();
+
+ kdtree->max_depth = max_leaf_size;
std::cerr << "Build information: " << std::endl
<< "max_depth " << max_depth << " (threshold " <<
depth_threshold << ")" << std::endl
@@ -435,7 +443,7 @@
<< "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;
+ << "tree cost " << sah_cost << std::endl;
}
Modified: trunk/Model/Groups/Build_OnLogn_cc.cc
==============================================================================
--- trunk/Model/Groups/Build_OnLogn_cc.cc (original)
+++ trunk/Model/Groups/Build_OnLogn_cc.cc Fri Oct 6 14:34:24 2006
@@ -169,29 +169,6 @@
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
-void find_bbox_candidates( const BoundsList &bounds,
- IndexedCandidateList &candidates );
-
-void find_sah_split_all_axes( const int &total_triangles,
- const IndexedCandidateList &candidates,
- const BBox &node_bounds,
- SplitPlane &result );
-
-void classify_candidates( const SplitPlane &result,
- const IndexedCandidateList &candidates,
- BoundsClassificationList &class_list/*,
- Integer
&left_side,
- Integer
&right_side */);
-
-void splice_indices( const IndexList &source,
- BoundsClassificationList &class_map, // Updates left
and right child index mapping.
- IndexList &left_index_list,
- IndexList &right_index_list );
-
-void splice_candidates( const IndexedCandidateList &source,
- const BoundsClassificationList &class_map,
- IndexedCandidateList &left_candidates,
- IndexedCandidateList &right_candidates );
@@ -225,7 +202,7 @@
const unsigned int axis_flag = AxisX+d;
// Check to see if the box is planar in this dimension.
- if ((box[1][d] - box[0][d]) < T_EPSILON) {
+ if (box[1][d] == box[0][d]) {
// Add a planar candidate.
candidates[count++] = IndexedCandidate( box[0][d], i, Planar |
axis_flag );
@@ -264,7 +241,10 @@
void find_sah_split_all_axes( const int &total_triangles,
const IndexedCandidateList &candidates,
const BBox &node_bounds,
+ const Real parent_area_inv,
+ const Real traversal_cost,
SplitPlane &result
+
)
{
// Candidate list must be sorted and contain candidates from all axes.
@@ -352,16 +332,24 @@
(c_split - node_bounds[0][c_axis]) * cross_section[c_axis] +
ends_area[c_axis];
const Real right_area =
(node_bounds[1][c_axis] - c_split) * cross_section[c_axis] +
ends_area[c_axis];
+
+ const Real left_probability = left_area * parent_area_inv;
+ const Real right_probability = right_area * parent_area_inv;
+
+ ASSERT( left_probability <= 1.0 );
+ ASSERT( right_probability <= 1.0 );
// Compute SAH cost twice, once with the planar triangles on the left
and once
// with the planar triangles on the right.
const Real left_planar_cost =
- left_area * ((Real)N_left[c_axis] + (Real)N_planar[c_axis]) +
- right_area * (Real)N_right[c_axis];
+ left_probability * ((Real)N_left[c_axis] + (Real)N_planar[c_axis]) +
+ right_probability * (Real)N_right[c_axis] +
+ traversal_cost;
const Real right_planar_cost =
- right_area * ((Real)N_right[c_axis] + (Real)N_planar[c_axis]) +
- left_area * (Real)N_left[c_axis];
+ right_probability * ((Real)N_right[c_axis] + (Real)N_planar[c_axis]) +
+ left_probability * (Real)N_left[c_axis] +
+ traversal_cost;
// Update min cost.
if (left_planar_cost < result.cost) {
@@ -415,6 +403,7 @@
// Reset counters.
int both = class_list.size(); // All _trianges_ classified as both.
+
Integer left_side = 0;
Integer right_side = 0;
@@ -430,26 +419,28 @@
// If the right bound is less than the split, then the triangle is
// only on the left side.
if (candidates[i].bound() == RightBound &&
- candidates[i].split <= result.split) {
+ candidates[i].split < result.split) {
- class_list[index].side = LeftOnly;
-
- // Update count.
- left_side ++;
- both --;
+ // Update count, once per triangle.
+ if (class_list[index].side == Both) {
+ left_side ++;
+ both --;
+ class_list[index].side = LeftOnly;
+ }
}
// If the left bound is greater than the split, then the triangle
// is only on the right side.
else if ((candidates[i].bound() == LeftBound) &&
- (candidates[i].split >= result.split)) {
+ (candidates[i].split > result.split)) {
- class_list[index].side = RightOnly;
-
- right_side ++;
- both --;
+ if (class_list[index].side == Both) {
+ right_side ++;
+ both --;
+ class_list[index].side = RightOnly;
+ }
}
-
+
else if (candidates[i].bound() == Planar) {
// If the planar candidate is less than the split plane, or if it's
on
@@ -458,10 +449,12 @@
if ((candidates[i].split < result.split) || // OR
((candidates[i].split == result.split) && (result.planar ==
LeftSide))) {
- class_list[index].side = LeftOnly;
+ if (class_list[index].side == Both) {
+ left_side ++;
+ both --;
+ }
- left_side ++;
- both --;
+ class_list[index].side = LeftOnly;
}
// If the planar candidate is greater than the split plane, or if
it's on
@@ -469,20 +462,21 @@
else if ((candidates[i].split > result.split) || // OR
((candidates[i].split == result.split) && (result.planar ==
RightSide))) {
- class_list[index].side = RightOnly;
+ if (class_list[index].side == Both) {
+ right_side ++;
+ both --;
+ }
- right_side ++;
- both --;
+ class_list[index].side = RightOnly;
}
- }
+ }
}
}
// Increment each side by the both count.
- if (both > 0) {
- right_side += both;
- left_side += both;
- }
+ ASSERT( both >= 0 );
+ right_side += both;
+ left_side += both;
}
///////////////////////////////////////////////////////////////////////////////
@@ -522,6 +516,8 @@
class_map[i].right = right_index_list.size();
right_index_list.push_back( source[i] );
break;
+ default:
+ ASSERT(false);
};
}
@@ -560,7 +556,7 @@
break;
case RightOnly:
right_candidates.push_back( candidate );
- right_candidates.back().index = c.right;
+ right_candidates.back().index = c.right;
break;
case Both:
left_candidates.push_back( candidate );
@@ -594,6 +590,7 @@
Integer total_leaves = 0;
Integer total_indices = 0;
Integer cost_trigger = 0;
+ Real total_leaf_cost = 0.0;
/////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////
@@ -671,6 +668,7 @@
max_leaf_size = SCIRun::Max( max_leaf_size, frame->index_list.size()
);
++total_leaves;
++total_nodes;
+ total_leaf_cost += frame->bounds.computeArea() *
(Real)frame->index_list.size();
// Delete the frame.
delete frame;
@@ -685,16 +683,19 @@
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
+ const Real parent_cost = /*frame->bounds.computeArea() * */
(Real)frame->index_list.size();
+
// Invoke n log n SAH.
SplitPlane plane;
find_sah_split_all_axes( frame->index_list.size(),
frame->candidates,
frame->bounds,
+ (Real)1.0 / frame->bounds.computeArea(),
+ kdtree->traversal_cost,
plane );
///////////////////////////////////////////////////////////////////////
// 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) {
@@ -781,16 +782,20 @@
// Compute SAH quality.
Real sah_cost = kdtree->computeSAHCost();
-
+
+ kdtree->max_depth = max_leaf_size;
+
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
+ << "avg_leaf_cost " << (total_leaf_cost)/((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
+ << "traversal_cost " << kdtree->traversal_cost << std::endl
<< "build time " << (end_time-start_time) << "s" << std::endl
<< "tree quality " << sah_cost << std::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 Oct 6 14:34:24 2006
@@ -59,6 +59,9 @@
// Build methods.
void build( KDTreeType *kdtree ) throw(SCIRun::Exception&);
+
+ protected:
+
///////////////////////////////////////////////////////////////////////////
};
};
Modified: trunk/Model/Groups/KDTreeDyn.cc
==============================================================================
--- trunk/Model/Groups/KDTreeDyn.cc (original)
+++ trunk/Model/Groups/KDTreeDyn.cc Fri Oct 6 14:34:24 2006
@@ -33,6 +33,8 @@
#include <Model/Readers/IW.h>
#include <MantaTypes.h>
+
+
#include <Core/Math/MiscMath.h>
#include <Core/Geometry/Vector.h>
@@ -52,7 +54,7 @@
///////////////////////////////////////////////////////////////////////////////
KDTreeDyn::KDTreeDyn(Material* material_in)
- : PrimitiveCommon( material_in ), root_node( 0 ), root_offset( 0 )
+ : PrimitiveCommon( material_in ), root_node( 0 ), root_offset( 0 ),
traversal_cost( 2.0 )
{
}
@@ -182,6 +184,7 @@
if (rays.hit(which, minT, getMaterial(), this, getTexCoordMapper()))
{
ScratchData sd;
sd.tri_index = hit_tri;
+ sd.depth = node->listLen; // (sptr - stack);
rays.scratchpad<ScratchData>(which) = sd;
}
}
@@ -217,9 +220,9 @@
const int kv = (axis==0)?2:axis-1;
const float mult = tri.n_k;
- data->normal[axis][ray] = mult;
- data->normal[ku][ray] = mult * tri.n_u;
- data->normal[kv][ray] = mult * tri.n_v;
+ data->normal[axis][ray] = -mult;
+ data->normal[ku][ray] = -mult * tri.n_u;
+ data->normal[kv][ray] = -mult * tri.n_v;
}
rays.setFlag(RayPacket::HaveUnitNormals);
}
@@ -233,8 +236,6 @@
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.
@@ -264,8 +265,7 @@
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
-void
-KDTreeDynTexture::mapValues(Packet<Color>& results,
+void KDTreeDynTexture::mapValues(Packet<Color>& results,
const RenderContext&,
RayPacket& rays) const
{
@@ -276,3 +276,31 @@
}
}
+KDTreeDynDepthTexture::KDTreeDynDepthTexture( const RegularColorMap
&color_map_ ) :
+ color_map( color_map_ ) { }
+
+void KDTreeDynDepthTexture::mapValues(Packet<Color>& results,
+ const RenderContext&,
+ RayPacket& rays) const
+{
+
+ // Color map based on depth in the kdtree.
+ for ( int ray = rays.begin(); ray < rays.end(); ++ray) {
+
+ const KDTreeDyn *kdtree = dynamic_cast<const KDTreeDyn *>(
rays.getHitPrimitive( ray ) );
+
+ ASSERT(kdtree);
+
+ // Obtain the max depth for this kdtree.
+ const Real max_depth = kdtree->max_depth;
+
+ const KDTreeDyn::ScratchData &scratch =
+ rays.scratchpad<KDTreeDyn::ScratchData>( ray );
+
+ const Real depth = (Real)scratch.depth / (Real)max_depth;
+
+ // Look up a color in a colormap.
+ results.set( ray, color_map.normalized( depth ) );
+
+ }
+}
Modified: trunk/Model/Groups/KDTreeDyn.h
==============================================================================
--- trunk/Model/Groups/KDTreeDyn.h (original)
+++ trunk/Model/Groups/KDTreeDyn.h Fri Oct 6 14:34:24 2006
@@ -38,7 +38,7 @@
#include <Interface/Parameters.h>
#include <SCIRun/Core/Util/Assert.h>
-
+#include <Core/Color/RegularColorMap.h>
#include <vector>
@@ -92,6 +92,7 @@
struct KDTreeDyn_ScratchData {
unsigned int tri_index;
+ unsigned int depth; // Depth of the intersected triangle.
};
/////////////////////////////////////////////////////////////////////////////
@@ -133,9 +134,15 @@
BBox bbox; // Bounds of the whole kdtree.
+ // Cost of traversing an interior node.
+ Real traversal_cost;
+
// Cost of the whole tree.
Real computeSAHCost() {
return computeSAHCost_helper( &node_list[root_offset], bbox ); }
+
+ // Stored stat's
+ unsigned int max_depth;
#ifndef SWIG
// Build interface.
@@ -201,7 +208,19 @@
};
+
+
+ class KDTreeDynDepthTexture: public Texture<Color> {
+ public:
+ KDTreeDynDepthTexture( const RegularColorMap &color_map_ );
+
+ virtual void mapValues(Packet<Color>& results,
+ const RenderContext&,
+ RayPacket& rays) const;
+ private:
+ RegularColorMap color_map;
+ };
} // end namespace Manta
- [MANTA] r1208 - trunk/Model/Groups, abe, 10/06/2006
Archive powered by MHonArc 2.6.16.
