WebSVN – gelsvn – Diff – /trunk/src/Geometry/BSPTree.cpp

       delete_node(node->right);
     delete node;
+  }
   void BSPTree::subdivide_node(BSPNode &node, BBox &bbox,
-                   unsigned int level,
+                               unsigned int level,
-                   vector<ISectTri*>& objects,
+                               vector<ISectTri*>& objects,
-                   vector<TriAccel*>& tri_objects)
+                               vector<TriAccel*>& tri_objects)
+  {
     const int TESTS = 2;
     if (objects.size()<=max_objects || level==max_level)
+    {
       node.id = all_objects.size();
       node.count = objects.size();
       for(unsigned int i = 0; i < objects.size(); ++i)
+      {
-    all_objects.push_back(objects[i]);
+        all_objects.push_back(objects[i]);
-    all_triaccel.push_back(tri_objects[i]);
+        all_triaccel.push_back(tri_objects[i]);
+      }
+    }
     else
+    {
       bool right_zero=false;
       double min_cost=CGLA::BIG;
       int new_pos = -1;
       for(i=0;i<3;i++)
+      {
-    for(int k=1;k<TESTS;k++)
+        for(int k=1;k<TESTS;k++)
-    {
+        {
-      BBox left_bbox = bbox;
+          BBox left_bbox = bbox;
-      BBox right_bbox = bbox;
+          BBox right_bbox = bbox;
-      double center = (bbox.max_corner[i]- bbox.min_corner[i])*(double)k/(double)TESTS + bbox.min_corner[i];
+          double center = (bbox.max_corner[i]- bbox.min_corner[i])*(double)k/(double)TESTS + bbox.min_corner[i];
-      node.plane = center;
+          node.plane = center;
-      left_bbox.max_corner[i] = center;
+          left_bbox.max_corner[i] = center;
-      right_bbox.min_corner[i] = center;
+          right_bbox.min_corner[i] = center;
-      // Try putting the triangles in the left and right boxes
+          // Try putting the triangles in the left and right boxes
-      int left_count = 0;
+          int left_count = 0;
-      int right_count = 0;
+          int right_count = 0;
-      for(unsigned int j=0;j<objects.size();j++)
+          for(unsigned int j=0;j<objects.size();j++)
-      {
+          {
-        ISectTri* tri = objects[j];
+            ISectTri* tri = objects[j];
-        left_count += left_bbox.intersect_triangle(*tri);
+            left_count += left_bbox.intersect_triangle(*tri);
-        right_count += right_bbox.intersect_triangle(*tri);
+            right_count += right_bbox.intersect_triangle(*tri);
-      }
+          }
-      //double len = bbox.max_corner[i] - bbox.min_corner[i];
+          //double len = bbox.max_corner[i] - bbox.min_corner[i];
-      double cost = left_count*left_bbox.area() + right_count*right_bbox.area(); // - len*len;
+          double cost = left_count*left_bbox.area() + right_count*right_bbox.area(); // - len*len;
-      if(cost < min_cost)
+          if(cost < min_cost)
-      {
+          {
-        min_cost = cost;
+            min_cost = cost;
-        new_axis = i;
+            new_axis = i;
-        new_pos = k;
+            new_pos = k;
-        right_zero = (right_count==0);
+            right_zero = (right_count==0);
-        left_zero = (left_count==0);
+            left_zero = (left_count==0);
-      }
+          }
-    }
+        }
+      }
       node.axis_leaf = new_axis;
       left_node->axis_leaf = static_cast<unsigned char>(-1);
       right_node->axis_leaf = static_cast<unsigned char>(-1);
       double center = size*(double)new_pos/(double)TESTS + bbox.min_corner[node.axis_leaf];
       double diff = f_eps < size/8.0 ? f_eps : size/8.0;
       if (left_zero)
+      {
-    // Find min position of all triangle vertices and place the center there
+        // Find min position of all triangle vertices and place the center there
-    center = bbox.max_corner[node.axis_leaf];
+        center = bbox.max_corner[node.axis_leaf];
-    for(unsigned int j=0;j<objects.size();j++)
+        for(unsigned int j=0;j<objects.size();j++)
-    {
+        {
-      ISectTri* tri = objects[j];
+          ISectTri* tri = objects[j];
-      if (tri->point0[node.axis_leaf]<center)
+          if (tri->point0[node.axis_leaf]<center)
-        center=tri->point0[node.axis_leaf];
+            center=tri->point0[node.axis_leaf];
-      if (tri->point1[node.axis_leaf]<center)
+          if (tri->point1[node.axis_leaf]<center)
-        center=tri->point1[node.axis_leaf];
+            center=tri->point1[node.axis_leaf];
-      if (tri->point2[node.axis_leaf]<center)
+          if (tri->point2[node.axis_leaf]<center)
-        center=tri->point2[node.axis_leaf];
+            center=tri->point2[node.axis_leaf];
-    }
+        }
-    center -= diff;
+        center -= diff;
+      }
       if (right_zero)
+      {
-    // Find max position of all triangle vertices and place the center there
+        // Find max position of all triangle vertices and place the center there
-    center = bbox.min_corner[node.axis_leaf];
+        center = bbox.min_corner[node.axis_leaf];
-    for(unsigned int j=0;j<objects.size();j++)
+        for(unsigned int j=0;j<objects.size();j++)
-    {
+        {
-      ISectTri* tri = objects[j];
+          ISectTri* tri = objects[j];
-      if (tri->point0[node.axis_leaf]>center)
+          if (tri->point0[node.axis_leaf]>center)
-        center=tri->point0[node.axis_leaf];
+            center=tri->point0[node.axis_leaf];
-      if (tri->point1[node.axis_leaf]>center)
+          if (tri->point1[node.axis_leaf]>center)
-        center=tri->point1[node.axis_leaf];
+            center=tri->point1[node.axis_leaf];
-      if (tri->point2[node.axis_leaf]>center)
+          if (tri->point2[node.axis_leaf]>center)
-        center=tri->point2[node.axis_leaf];
+            center=tri->point2[node.axis_leaf];
-    }
+        }
-    center += diff;
+        center += diff;
+      }
       node.plane = center;
       left_bbox.max_corner[node.axis_leaf] = center;
       right_bbox.min_corner[node.axis_leaf] = center;
       // Now put the triangles in the right and left node
       for(i=0;i<objects.size();i++)
+      {
-    ISectTri* tri = objects[i];
+        ISectTri* tri = objects[i];
-    TriAccel *tri_accel = tri_objects[i];
+        TriAccel *tri_accel = tri_objects[i];
-    if (left_bbox.intersect_triangle(*tri))
+        if (left_bbox.intersect_triangle(*tri))
-    {
+        {
-      left_objects.push_back(tri);
+          left_objects.push_back(tri);
-      tri_left_objects.push_back(tri_accel);
+          tri_left_objects.push_back(tri_accel);
-    }
+        }
-    if (right_bbox.intersect_triangle(*tri))
+        if (right_bbox.intersect_triangle(*tri))
-    {
+        {
-      right_objects.push_back(tri);
+          right_objects.push_back(tri);
-      tri_right_objects.push_back(tri_accel);
+          tri_right_objects.push_back(tri_accel);
-    }
+        }
+      }
     //if (left_zero||right_zero)
     //  cout << left_objects.size() << "," << right_objects.size() << "," << level << endl;
       objects.clear();
     bbox.min_corner-=Vec3f(1.0);
     bbox.max_corner+=Vec3f(1.0);
+  }
   void BSPTree::init(vector<const TriMesh*>& _trimesh,
-             vector<Mat4x4f>& _transforms,
+                     vector<Mat4x4f>& _transforms,
-             int _max_objects, int _max_level)
+                     int _max_objects, int _max_level)
+  {
     trimesh = _trimesh;
     transforms = _transforms;
     for(unsigned int i=0;i<trimesh.size();i++)
+    {
       const TriMesh *mesh = trimesh[i];
       // Loop through all triangles and add them to intersection structure
       for(int j=0;j<mesh->geometry.no_faces();j++)
+      {
-    Vec3i face = mesh->geometry.face(j);
+        Vec3i face = mesh->geometry.face(j);
-    ISectTri new_tri;
+        ISectTri new_tri;
-    new_tri.point0 = transforms[i].mul_3D_point(mesh->geometry.vertex(face[0]));
+        new_tri.point0 = transforms[i].mul_3D_point(mesh->geometry.vertex(face[0]));
-    new_tri.point1 = transforms[i].mul_3D_point(mesh->geometry.vertex(face[1]));
+        new_tri.point1 = transforms[i].mul_3D_point(mesh->geometry.vertex(face[1]));
-    new_tri.point2 = transforms[i].mul_3D_point(mesh->geometry.vertex(face[2]));
+        new_tri.point2 = transforms[i].mul_3D_point(mesh->geometry.vertex(face[2]));
-    new_tri.edge0 = new_tri.point1 - new_tri.point0;
+        new_tri.edge0 = new_tri.point1 - new_tri.point0;
-    new_tri.edge1 = new_tri.point2 - new_tri.point0;
+        new_tri.edge1 = new_tri.point2 - new_tri.point0;
-    new_tri.mesh_id = i;
+        new_tri.mesh_id = i;
-    new_tri.tri_id = j;
+        new_tri.tri_id = j;
-    isecttris.push_back(new_tri);
+        isecttris.push_back(new_tri);
-    TriAccel ta;
+        TriAccel ta;
-    create_tri_accel(new_tri.point0, new_tri.point1, new_tri.point2, ta);
+        create_tri_accel(new_tri.point0, new_tri.point1, new_tri.point2, ta);
-    ta.mesh_id = i;
+        ta.mesh_id = i;
-    ta.tri_id = j;
+        ta.tri_id = j;
-    triaccel.push_back(ta);
+        triaccel.push_back(ta);
+      }
+    }
     max_objects = _max_objects;
     max_level = _max_level;
+    {
       vector<ISectTri*> objects;
       vector<TriAccel*> tri_objects;
       for(unsigned int i=0;i<isecttris.size();i++)
+      {
-    ISectTri* tri = &isecttris[i];
+        ISectTri* tri = &isecttris[i];
-    TriAccel* tri_accel = &triaccel[i];
+        TriAccel* tri_accel = &triaccel[i];
-    objects.push_back(tri);
+        objects.push_back(tri);
-    tri_objects.push_back(tri_accel);
+        tri_objects.push_back(tri_accel);
+      }
       subdivide_node(*root, bbox, 0, objects, tri_objects);
       b_is_build = true;
+    }
-    isecttris.clear();
-    all_objects.clear();
     make_fast_tree(root);
+  }
   bool BSPTree::is_build()
+  {
     if (node.axis_leaf==4)
+    {
       found = false;
       for(i=0;i<node.count;i++)
+      {
-//  const TriAccel* tri2 = all_triaccel[node.id+i];
+//        const TriAccel* tri2 = all_triaccel[node.id+i];
-    const ISectTri* tri = all_objects[node.id+i];
+        const ISectTri* tri = all_objects[node.id+i];
-//          if (intersect2(ray, *tri2, t_max))
+//        if (intersect2(ray, *tri2, t_max))
-//              found=true;
+//          found=true;
-    if (intersect(ray, *tri, t_max))
+        if (intersect(ray, *tri, t_max))
-      found=true;
+          found=true;
+      }
       if (found)
     return true;
       else
     return false;
+    {
       BSPNode *near_node;
       BSPNode *far_node;
       if (ray.direction[node.axis_leaf]>=0)
+      {
-    near_node = node.left;
+        near_node = node.left;
-    far_node = node.right;
+        far_node = node.right;
+      }
       else
+      {
-    near_node = node.right;
+        near_node = node.right;
-    far_node = node.left;
+        far_node = node.left;
+      }
       // In order to avoid instability
       double t;
       if (fabs(ray.direction[node.axis_leaf])<d_eps)
-    t = (node.plane - ray.origin[node.axis_leaf])/d_eps;// intersect node plane;
+        t = (node.plane - ray.origin[node.axis_leaf])/d_eps;// intersect node plane;
       else
-    t = (node.plane - ray.origin[node.axis_leaf])/ray.direction[node.axis_leaf];// intersect node plane;
+        t = (node.plane - ray.origin[node.axis_leaf])/ray.direction[node.axis_leaf];// intersect node plane;
       if (t>t_max)
         return intersect_node(ray, *near_node, t_min, t_max);
       else if (t<t_min)
-    return intersect_node(ray, *far_node, t_min, t_max);
+        return intersect_node(ray, *far_node, t_min, t_max);
       else
+      {
-    if (intersect_node(ray, *near_node, t_min, t))
+        if (intersect_node(ray, *near_node, t_min, t))
-      return true;
+          return true;
-    else
+        else
-      return intersect_node(ray, *far_node, t, t_max);
+          return intersect_node(ray, *far_node, t, t_max);
+      }
+    }
+  }
   bool BSPTree::intersect(Ray &ray) const
 //    intersect_fast_node(ray, &fast_tree[0], t_min, t_max);
     //  if (!ray.has_hit)
     //return false;
     else
+    {
-        //printf("HIT\n");
+      //printf("HIT\n");
       // Calculate the normal at the intersection
-        ray.id = reinterpret_cast<int>(ray.hit_object);
+      ray.id = reinterpret_cast<int>(ray.hit_object);
-        ray.hit_object = trimesh[ray.id];
+      ray.hit_object = trimesh[ray.id];
-        Vec3i face = ray.hit_object->normals.face(ray.hit_face_id);
+      Vec3i face = ray.hit_object->normals.face(ray.hit_face_id);
-        Vec3f normal0 = ray.hit_object->normals.vertex(face[0]);
+      Vec3f normal0 = ray.hit_object->normals.vertex(face[0]);
-        Vec3f normal1 = ray.hit_object->normals.vertex(face[1]);
+      Vec3f normal1 = ray.hit_object->normals.vertex(face[1]);
-        Vec3f normal2 = ray.hit_object->normals.vertex(face[2]);
+      Vec3f normal2 = ray.hit_object->normals.vertex(face[2]);
-        ray.hit_normal = transforms[ray.id].mul_3D_vector(
+      ray.hit_normal = transforms[ray.id].mul_3D_vector(
-            normalize(normal0*(1 - ray.u - ray.v)
+          normalize(normal0*(1 - ray.u - ray.v)
-            +normal1*ray.u
+          +normal1*ray.u
-            +normal2*ray.v));
+          +normal2*ray.v));
-        ray.hit_pos = ray.origin + ray.direction*ray.dist;
+      ray.hit_pos = ray.origin + ray.direction*ray.dist;
 /*
       Vec3i face = ray.hit_object->normals.face(ray.hit_face_id);
       Vec3f normal0 = ray.hit_object->normals.vertex(face[0]);
       Vec3f normal1 = ray.hit_object->normals.vertex(face[1]);
       Vec3f normal2 = ray.hit_object->normals.vertex(face[2]);
       ray.hit_normal = normalize(normal0*(1 - ray.u - ray.v)
                  +normal1*ray.u
                  +normal2*ray.v);
       ray.hit_pos = ray.origin + ray.direction*ray.dist;
 */
       return true;
+    }
+  }
   const int MAX_DEPTH=25;
   void BSPTree::push_fast_bsp_node(BSPNode *node, int id)
+  {
     if (node->axis_leaf==4)  // It is a leaf
+    {
-        //assert(false);
+      //assert(false);
-        //TODO: cant compile on 64 bit gcc
+      //TODO: cant compile on 64 bit gcc
-        //fast_tree[id].leaf.flagAndOffset = (unsigned int)1<<31 | (unsigned int)(&all_triaccel[node->id]);
+      //fast_tree[id].leaf.flagAndOffset = (unsigned int)1<<31 | (unsigned int)(&all_triaccel[node->id]);
       fast_tree[id].leaf.count = node->count;
+    }
     else // It is an inner node
+    {
       FastBSPNode fnode;
     // Precalculate one over dir
     double one_over_dir[3];
     for(int i=0;i<3;i++)
+    {
       if (ray.direction[i]!=0)
-    one_over_dir[i]=1.0/ray.direction[i];
+        one_over_dir[i]=1.0/ray.direction[i];
       else
-    one_over_dir[i]=1.0/d_eps;
+        one_over_dir[i]=1.0/d_eps;
+    }
     int dimension;
     while(1)
+    {
       while(!ABSP_ISLEAF(node))
+      {
-    dimension = ABSP_DIMENSION(node);
+        dimension = ABSP_DIMENSION(node);
-    t = (node->inner.splitCoordinate - ray.origin[dimension])*one_over_dir[dimension];
+        t = (node->inner.splitCoordinate - ray.origin[dimension])*one_over_dir[dimension];
-    if (t>=t_max)
+        if (t>=t_max)
-      node = ABSP_NEARNODE(node);
+          node = ABSP_NEARNODE(node);
-    else if (t<=t_min)
+        else if (t<=t_min)
-      node = ABSP_FARNODE(node);
+          node = ABSP_FARNODE(node);
-    else
+        else
-    {
+        {
-      // Stack push
+          // Stack push
-      stack[stack_id].node = ABSP_FARNODE(node);
+          stack[stack_id].node = ABSP_FARNODE(node);
-      stack[stack_id].t_min = t;
+          stack[stack_id].t_min = t;
-      stack[stack_id++].t_max = t_max;
+          stack[stack_id++].t_max = t_max;
-      // Set current node to near side
+          // Set current node to near side
-      node = ABSP_NEARNODE(node);
+          node = ABSP_NEARNODE(node);
-      t_max = t;
+          t_max = t;
-    }
+        }
+      }
       IntersectAlltrianglesInLeaf(&node->leaf, ray, t_max);
       if (ray.dist<t_max)
-    return;
+        return;
       if (stack_id==0)
-    return;
+        return;
       // Stack pop
       node = stack[--stack_id].node;
       t_min = stack[stack_id].t_min;
       t_max = stack[stack_id].t_max;
 //      const double eps = 0.001f;
 /********* Complain!!!!!!!!!!!!!!!! *****************/
     //p = cross(direction, edge1);
     // Why the &%¤/ is this so much faster????? - Because of MS Compiler - the intel compiler does it right!!
     p.set(direction[1] * edge1[2] - direction[2] * edge1[1],
-      direction[2] * edge1[0] - direction[0] * edge1[2],
+          direction[2] * edge1[0] - direction[0] * edge1[2],
-      direction[0] * edge1[1] - direction[1] * edge1[0]);
+          direction[0] * edge1[1] - direction[1] * edge1[0]);
 /****************************************************/
     a = dot(edge0,p);
     if (a>-d_eps && a<d_eps)
       return false;
   // Just delay these

Subversion Repositories gelsvn

(root)/trunk/src/Geometry/BSPTree.cpp @ 451 – Rev 364 → 428