Text archives Help

---

Author: bigler
Date: Wed Apr  5 10:58:38 2006
New Revision: 1001

Added:
   trunk/Model/Groups/KDTree2.cc
   trunk/Model/Groups/KDTree2.h
Log:

Start of trimmed down version of KDTree using WaldTriangle
instersection stuff and pseudo code from Ingo.


Added: trunk/Model/Groups/KDTree2.cc
==============================================================================
--- (empty file)
+++ trunk/Model/Groups/KDTree2.cc       Wed Apr  5 10:58:38 2006
@@ -0,0 +1,138 @@
+/*
+  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/KDTree2.h>
+
+KDTree2::Triangle::Triangle(const Vector& _p1,
+                            const Vector& _p2,
+                            const Vector& _p3)
+{
+  box.reset();
+  box.extendByPoint(_p1);
+  box.extendByPoint(_p2);
+  box.extendByPoint(_p3);
+
+  Vector normal = Cross(_p2-_p1, _p3-_p1);
+  normal.normalize();
+
+  unsigned int n, u, v;
+
+  n = 0;
+  if ( Abs(normal[1]) > Abs(normal[n])) n = 1;
+  if ( Abs(normal[2]) > Abs(normal[n])) n = 2;
+
+  switch ( n ) {
+  case 0: u = 1; v = 2; break;
+  case 1: u = 2; v = 0; break;
+  default: u = 0; v = 1; break;
+  };
+
+  // copy to struct
+  k = n;
+  n_u = normal[u] / normal[k];
+  n_v = normal[v] / normal[k];
+  n_d = _p1[u] * n_u + _p1[v] * n_v + _p1[k];
+
+  float s;
+
+  c_nu = + _p2[v] - _p1[v];
+  c_nv = - _p2[u] + _p1[u];
+  c_d  = - (_p1[u] * c_nu + _p1[v] * c_nv);
+
+  s = 1.f / ( _p3[u] * c_nu + _p3[v] * c_nv + c_d );
+
+  c_nu *= s;
+  c_nv *= s;
+  c_d  *= s;
+
+  b_nu = + _p3[v] - _p1[v];
+  b_nv = - _p3[u] + _p1[u];
+  b_d  = - (_p1[u] * b_nu + _p1[v] * b_nv);
+
+  s = 1.f / ( _p2[u] * b_nu + _p2[v] * b_nv + b_d );
+
+  b_nu *= s;
+  b_nv *= s;
+  b_d  *= s;
+
+  n_k = normal[k];
+}
+
+// Inherited from PrimitiveCommon
+void
+KDTree2::intersect(const RenderContext& context, RayPacket& rays) const {
+  rays.normalizeDirections();
+  rays.computeInverseDirections();
+  rays.computeSigns();
+
+  RayTriIntersectUserData isectData;
+
+  for(int i=rays.begin();i<rays.end();i++) {
+
+    Real minDist, maxDist;
+
+    // Intersect the ray with the bounding box for the group.
+    if (Intersection::intersectAaBox( bbox,
+                                      minDist, maxDist,
+                                      rays.getRay(i),
+                                      rays.getSigns(i),
+                                      rays.getInverseDirection(i)))
+      {
+        // Determine the actual minimum distance.
+        minDist = SCIRun::Max( minDist, T_EPSILON );
+        maxDist = SCIRun::Min( maxDist, rays.getMinT(i) );
+
+        // Send the ray to the _intersect function.
+        isectData.rayHitTriIndex = -1;
+        isectData.duplicate = 0;
+        intersect_node( rootNode, rays, i, isectData, context, 
(float)minDist, (float)maxDist);
+
+      }
+  }
+}
+
+void
+KDTree2::computeNormal(const RenderContext& context, RayPacket &rays) const {
+  RayPacketData* data = rays.data;
+  for ( int ray = rays.begin(); ray < rays.end(); ray++ ) {
+    const Triangle& tri = 
triangles[rays.scratchpad<ScratchData>(ray).tri_index];
+    
+    const int axis = tri.k;
+    const int ku   = (axis==2)?0:k+1;
+    const int kv   = (axis==0)?2:k-1;
+    const flaot 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;
+  }
+  rays.setFlag(RayPacket::HaveUnitNormals);
+}
+
+
+

Added: trunk/Model/Groups/KDTree2.h
==============================================================================
--- (empty file)
+++ trunk/Model/Groups/KDTree2.h        Wed Apr  5 10:58:38 2006
@@ -0,0 +1,131 @@
+/*
+  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.
+*/
+
+#ifndef Manta_Groups_KDTree2_h
+#define Manta_Groups_KDTree2_h
+
+#include <Model/Primitives/PrimitiveCommon.h>
+#include <Core/Geometry/Vector.h>
+#include <Core/Geometry/Ray.h>
+
+namespace Manta {
+
+  class KDTree2 : public PrimitiveCommon {
+  public:
+    
+    struct Node {
+      union {
+        Node *left_son; // rigth_son = left_son+1;
+        int listBegin;
+      };
+      union {
+        float split; // internal
+        int listLen; // leaf
+      }
+      char type; // 0=x,1=y,z=2,leaf=3
+    };
+
+    class Triangle {
+    public:
+      Triangle() {}
+      Triangle(const Vector& _p1, const Vector& _p2, const Vector& _p3);
+      
+      float n_u;
+      float n_v;
+      float n_d;
+      unsigned int k;
+
+      float b_nu;
+      float b_nv;
+      float b_d;
+      float n_k;
+
+      float c_nu;
+      float c_nv;
+      float c_d;
+    };
+
+    struct ScratchData {
+      unsigned int tri_index;
+    };
+    
+    // Inherited from PrimitiveCommon
+    virtual void computeBounds(const PreprocessContext& /*context*/,
+                               BBox& bbox_in) const
+    {
+      bbox_in.extendByBox(bbox);
+    }
+      
+    virtual void intersect(const RenderContext& context,
+                           RayPacket& rays) const ;
+    virtual void computeNormal(const RenderContext& context,
+                               RayPacket &rays) const;    
+
+    // Returns 0 on success
+    int reserveTriangles(size_t num_tris_in) {
+      triangles = 
static_cast<Triangle*>(malloc(num_tris_in*sizeof(Triangle)));
+      if (triangles) {
+        num_tris = num_tris_in;
+        return 0;
+      } else {
+        return 1;
+      }
+    }
+        
+    // Returns 0 on success
+    int reserveTriangleIndices(size_t num_tri_indices_in) {
+      tri_indicies =
+        static_cast<Triangle*>(malloc(num_tri_indices_in*sizeof(Triangle)));
+      if (tri_indicies) {
+        num_tri_indices = num_tri_indices_in;
+        return 0;
+      } else {
+        return 1;
+      }
+    }
+
+    // Triangle list stuff
+    Triangle* triangles;
+    size_t num_tris;
+    unsigned int* tri_indices;
+    size_t num_tri_indices;
+
+
+    // Root node
+    Node* root_node;
+    
+    BBox bbox;
+
+  protected:
+    void intersect_node();
+
+  };
+  
+} // end namespace Manta
+
+#endif // Manta_Groups_KDTree2_h

---

• [MANTA] r1001 - trunk/Model/Groups, bigler, 04/05/2006

---

Archive powered by MHonArc 2.6.16.