Text archives Help

---

Author: boulos
Date: Fri Feb 24 00:03:16 2006
New Revision: 955

Added:
   trunk/Model/Groups/DynBVH.cc
   trunk/Model/Groups/DynBVH.h
Modified:
   trunk/Model/Groups/CMakeLists.txt
   trunk/Model/Groups/Group.cc
   trunk/Model/Groups/Group.h
Log:
Adding const version of get and changing 
getSize to be const. 

Adding the first compiling version of the 
SIGGRAPH Dynamic BVH (not yet tested and lacks
interval arithmetic culling).



Modified: trunk/Model/Groups/CMakeLists.txt
==============================================================================
--- trunk/Model/Groups/CMakeLists.txt   (original)
+++ trunk/Model/Groups/CMakeLists.txt   Fri Feb 24 00:03:16 2006
@@ -10,6 +10,8 @@
 SET (Manta_Groups_SRCS
      Groups/BVH.cc
      Groups/BVH.h
+     Groups/DynBVH.h
+     Groups/DynBVH.cc
      Groups/GriddedGroup.cc
      Groups/GriddedGroup.h
      Groups/Group.cc

Added: trunk/Model/Groups/DynBVH.cc
==============================================================================
--- (empty file)
+++ trunk/Model/Groups/DynBVH.cc        Fri Feb 24 00:03:16 2006
@@ -0,0 +1,373 @@
+#include <Model/Groups/DynBVH.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <float.h>
+using namespace Manta;
+
+const float BVH_C_isec = 10.f;
+const float BVH_C_trav = 10.f;
+
+void DynBVH::intersect(const RenderContext& context, RayPacket& rays) const
+{
+    rays.computeInverseDirections();
+    rays.computeSigns();
+
+    intersectNode(0,context,rays);
+}
+
+void DynBVH::intersectNode(int nodeID, const RenderContext& context, 
RayPacket& rays) const
+{
+    const BVHNode& node = nodes[nodeID];
+    int firstActive = firstIntersects(node.bounds, rays);
+
+    if (firstActive != rays.end())
+    {
+        if (node.isLeaf())
+        {
+            // we already know that one of the rays from begin to end
+            // hits the object, so lastActive is going to find something
+            // we need not create a subpacket to help it stop early
+
+            // actually if we're just one ray it'll look more than it
+            // needs to... damn
+            int lastActive = lastIntersects(node.bounds, rays);
+
+            // build a subpacket from firstActive to lastActive
+            RayPacket subpacket(rays, firstActive, lastActive);
+
+            for (int i = 0; i < node.children; i++ )
+            {
+                const int object_id = object_ids[node.child+i];
+                this->get(object_id)->intersect(context,subpacket);
+            }
+        }
+        else
+        {
+            // make a subpacket from the (possibly) new firstActive to the 
current end
+            RayPacket subpacket(rays, firstActive, rays.end());
+
+            // recurse
+            intersectNode(node.child+0, context, subpacket);
+            intersectNode(node.child+1, context, subpacket);
+        }
+    }
+}
+
+// return the first index (between [rays.begin(),rays.end()]) which hits the 
box
+int DynBVH::firstIntersects(const BBox& box, const RayPacket& rays) const
+{
+    for (int ray = rays.begin(); ray < rays.end(); ray++ )
+    {
+        float maximum_minimum = 1e-4;
+        float minimum_maximum = rays.getMinT(ray);
+
+        float x_minimum = (box[rays.getSign(ray,0)][0]   - 
rays.getOrigin(ray,0)) * rays.getInverseDirection(ray,0);
+        float x_maximum = (box[1-rays.getSign(ray,0)][0] - 
rays.getOrigin(ray,0)) * rays.getInverseDirection(ray,0);
+
+        float y_minimum = (box[rays.getSign(ray,1)][1]   - 
rays.getOrigin(ray,1)) * rays.getInverseDirection(ray,1);
+        float y_maximum = (box[1-rays.getSign(ray,1)][1] - 
rays.getOrigin(ray,1)) * rays.getInverseDirection(ray,1);
+
+        float z_minimum = (box[rays.getSign(ray,2)][2]   - 
rays.getOrigin(ray,2)) * rays.getInverseDirection(ray,2);
+        float z_maximum = (box[1-rays.getSign(ray,2)][2] - 
rays.getOrigin(ray,2)) * rays.getInverseDirection(ray,2);
+
+        if ( minimum_maximum < x_minimum ||
+             maximum_minimum > x_maximum )
+            continue;
+        if ( minimum_maximum > x_maximum )
+            minimum_maximum = x_maximum;
+        if ( maximum_minimum < x_minimum )
+            maximum_minimum = x_minimum;
+        if ( minimum_maximum < y_minimum ||
+             maximum_minimum > y_maximum )
+            continue;
+        if ( minimum_maximum > y_maximum )
+                minimum_maximum = y_maximum;
+        if ( maximum_minimum < y_minimum )
+            maximum_minimum = y_minimum;
+
+        if ( minimum_maximum >= z_minimum &&
+             maximum_minimum <= z_maximum )
+            return ray; // found a hit
+    }
+    return rays.end();
+}
+
+// return the last index which hits the box
+int DynBVH::lastIntersects(const BBox& box, const RayPacket& rays) const
+{
+    for (int ray = rays.end() - 1; ray >= rays.begin(); ray-- )
+    {
+        float maximum_minimum = 1e-4;
+        float minimum_maximum = rays.getMinT(ray);
+
+        float x_minimum = (box[rays.getSign(ray,0)][0]   - 
rays.getOrigin(ray,0)) * rays.getInverseDirection(ray,0);
+        float x_maximum = (box[1-rays.getSign(ray,0)][0] - 
rays.getOrigin(ray,0)) * rays.getInverseDirection(ray,0);
+
+        float y_minimum = (box[rays.getSign(ray,1)][1]   - 
rays.getOrigin(ray,1)) * rays.getInverseDirection(ray,1);
+        float y_maximum = (box[1-rays.getSign(ray,1)][1] - 
rays.getOrigin(ray,1)) * rays.getInverseDirection(ray,1);
+
+        float z_minimum = (box[rays.getSign(ray,2)][2]   - 
rays.getOrigin(ray,2)) * rays.getInverseDirection(ray,2);
+        float z_maximum = (box[1-rays.getSign(ray,2)][2] - 
rays.getOrigin(ray,2)) * rays.getInverseDirection(ray,2);
+
+        if ( minimum_maximum < x_minimum ||
+             maximum_minimum > x_maximum )
+            continue;
+        if ( minimum_maximum > x_maximum )
+            minimum_maximum = x_maximum;
+        if ( maximum_minimum < x_minimum )
+            maximum_minimum = x_minimum;
+        if ( minimum_maximum < y_minimum ||
+             maximum_minimum > y_maximum )
+            continue;
+        if ( minimum_maximum > y_maximum )
+                minimum_maximum = y_maximum;
+        if ( maximum_minimum < y_minimum )
+            maximum_minimum = y_minimum;
+
+        if ( minimum_maximum >= z_minimum &&
+             maximum_minimum <= z_maximum )
+            return ray; // found a hit
+    }
+    return rays.begin();
+}
+
+void DynBVH::preprocess(const PreprocessContext& context)
+{
+    Group::preprocess(context);
+
+    nodes = new BVHNode[2*this->getSize()];
+    object_ids = new int[this->getSize()];
+    for ( int i = 0; i < this->getSize(); i++ )
+        object_ids[i] = i;
+
+    num_nodes = 1; // root node
+    build(context, 0, 0, this->getSize(), num_nodes);
+    updateBounds(context, 0);
+}
+
+void DynBVH::build(const PreprocessContext& context,
+                   int nodeID, int objectBegin, int objectEnd,
+                   int& nextFree, int depth)
+{
+
+    if (objectBegin <= objectEnd)
+    {
+        printf("ERROR! Tried building BVH over 
%d,%d\n",objectBegin,objectEnd);
+        exit(-1);
+    }
+
+    BVHNode& node = nodes[nodeID];
+
+    int bestAxis = -1;
+    int split = partitionSAH(context, objectBegin,objectEnd,bestAxis);
+
+    if (bestAxis == -1)
+    {
+        // make leaf
+        node.makeLeaf(objectBegin, objectEnd-objectBegin);
+
+        std::sort(object_ids+objectBegin,object_ids+objectEnd);
+
+        num_nodes++;
+    }
+    else
+    {
+        // make internal node
+        node.makeInternal(nextFree, bestAxis);
+        num_nodes++;
+        // allocate two spots
+        nextFree += 2;
+
+        build(context, node.child+0,objectBegin,split,nextFree,depth+1);
+        build(context, node.child+1, split, objectEnd,nextFree,depth+1);
+    }
+
+    if (depth == 0)
+    {
+        printf("DynBVH Build Complete\n");
+    }
+
+}
+
+void DynBVH::updateBounds(const PreprocessContext& context, int ID)
+{
+    BVHNode& node = nodes[ID];
+    if (node.isLeaf())
+    {
+        node.bounds.reset();
+        for (int i = 0; i < node.children; i++ )
+        {
+            BBox temp;
+            int obj_id = object_ids[node.child + i];
+            this->get(obj_id)->computeBounds(context,temp);
+
+            node.bounds.extendByBox(temp);
+        }
+        node.axis = 0;
+        node.axis_sign = 0;
+    }
+    else
+    {
+        int left_son = node.child;
+        int right_son = left_son + 1;
+        updateBounds(context, left_son);
+        updateBounds(context, right_son);
+
+        node.bounds.reset();
+        const BVHNode& left_node = nodes[left_son];
+        const BVHNode& right_node = nodes[right_son];
+
+        node.bounds.extendByBox(left_node.bounds);
+        node.bounds.extendByBox(right_node.bounds);
+    }
+}
+
+int DynBVH::partitionSAH(const PreprocessContext& context,
+                         int objBegin, int objEnd, int& output_axis)
+{
+    int num_objects = objEnd - objBegin;
+    if ( num_objects == 1 )
+    {
+        output_axis = -1;
+        return -1;
+    }
+
+    BVHCostEval best_cost;
+    best_cost.cost = BVH_C_isec * num_objects;
+    best_cost.axis = -1;
+
+    for ( int axis = 0; axis < 3; axis++ )
+    {
+        BVHCostEval new_cost;
+        if ( buildEvents(context, objBegin,objEnd,axis,new_cost) )
+        {
+            if ( new_cost.cost < best_cost.cost )
+            {
+                best_cost = new_cost;
+            }
+        }
+    }
+
+    output_axis = best_cost.axis;
+    if ( output_axis != -1 )
+    {
+        // build the events and sort them
+        std::vector<BVHSAHEvent> events;
+        for ( int i = objBegin; i < objEnd; i++ )
+        {
+            BVHSAHEvent new_event;
+            BBox tri_box;
+            this->get(object_ids[i])->computeBounds(context, tri_box);
+            new_event.position = tri_box.center()[output_axis];
+            new_event.obj_id   = object_ids[i];
+            events.push_back(new_event);
+        }
+
+        std::sort(events.begin(), events.end(), CompareBVHSAHEvent());
+
+        for ( int i = objBegin; i < objEnd; i++ )
+        {
+            object_ids[i] = events[i-objBegin].obj_id;
+        }
+
+        int result = objBegin + best_cost.event;
+
+        if ( result == objBegin || result == objEnd )
+        {
+            if ( num_objects < 8 )
+            {
+                output_axis = -1;
+                return 0;
+            }
+            result = objBegin + num_objects/2;
+            return result;
+        }
+        else
+            return result;
+    }
+    else
+    {
+        return 0; // making a leaf anyway
+    }
+
+}
+
+bool DynBVH::buildEvents(const PreprocessContext& context,
+                         int first,
+                         int last,
+                         int axis,
+                         BVHCostEval& best_eval)
+{
+    BBox overall_box;
+    std::vector<BVHSAHEvent> events;
+    for ( int i = first; i < last; i++ )
+    {
+        BVHSAHEvent new_event;
+        BBox tri_box;
+        this->get(object_ids[i])->computeBounds(context, tri_box);
+        new_event.position = tri_box.center()[axis];
+        new_event.obj_id   = object_ids[i];
+        events.push_back(new_event);
+
+        overall_box.extendByBox(tri_box);
+    }
+
+    std::sort(events.begin(),events.end(),CompareBVHSAHEvent());
+
+    int num_events = int(events.size());
+    BBox left_box;
+
+    int num_left = 0;
+    int num_right = num_events;
+
+    for ( size_t i = 0; i < events.size(); i++ )
+    {
+        events[i].num_left = num_left;
+        events[i].num_right = num_right;
+        events[i].left_area = left_box.computeArea();
+
+        BBox tri_box;
+        this->get(events[i].obj_id)->computeBounds(context, tri_box);
+        left_box.extendByBox(tri_box);
+
+        num_left++;
+        num_right--;
+    }
+
+    BBox right_box;
+
+    best_eval.cost = FLT_MAX;
+    best_eval.event = -1;
+
+    for ( int i = num_events - 1; i >= 0; i-- )
+    {
+        BBox tri_box;
+        this->get(events[i].obj_id)->computeBounds(context, tri_box);
+
+        right_box.extendByBox(tri_box);
+
+        if ( events[i].num_left > 0 && events[i].num_right > 0 )
+        {
+            events[i].right_area = right_box.computeArea();
+
+            float this_cost = (events[i].num_left * events[i].left_area +
+                               events[i].num_right * events[i].right_area);
+            this_cost /= overall_box.computeArea();
+            this_cost *= BVH_C_isec;
+            this_cost += BVH_C_trav;
+
+            events[i].cost = this_cost;
+            if ( this_cost < best_eval.cost )
+            {
+                best_eval.cost       = this_cost;
+                best_eval.position   = events[i].position;
+                best_eval.axis       = axis;
+                best_eval.event      = i;
+                best_eval.num_left   = events[i].num_left;
+                best_eval.num_right  = events[i].num_right;
+
+            }
+        }
+    }
+    return best_eval.event != -1;
+}

Added: trunk/Model/Groups/DynBVH.h
==============================================================================
--- (empty file)
+++ trunk/Model/Groups/DynBVH.h Fri Feb 24 00:03:16 2006
@@ -0,0 +1,124 @@
+#ifndef _MANTA_DYNBVH_H_
+#define _MANTA_DYNBVH_H_
+
+#include <Model/Groups/Group.h>
+#include <Core/Geometry/BBox.h>
+#include <Interface/RayPacket.h>
+
+namespace Manta
+{
+    class DynBVH : public Group
+    {
+    public:
+        struct BVHNode
+        {
+            BBox bounds;
+            int child; // my child
+            unsigned char axis; // 0 = x, 1 = y, 2 = z,
+            unsigned char axis_sign; // 0 means left-right, 1 means 
right-left
+            short children; // num children
+
+            // 24 bytes + 4 bytes + 1 + 1 + 2 = 32 bytes
+
+            inline void makeLeaf(int first_child, short num_children)
+            {
+                child = first_child;
+                children = num_children;
+                axis = 0;
+                axis_sign = 0;
+            }
+
+            inline void makeInternal(int first_child, unsigned char _axis)
+            {
+                child = first_child;
+                children = 0;
+                axis = _axis;
+                axis_sign = 0; // for now
+            }
+
+            inline bool isLeaf() const
+            {
+                return children != 0;
+            }
+
+        };
+
+        BVHNode* nodes;
+        int* object_ids;
+        int num_nodes;
+
+        DynBVH() : nodes(NULL), num_nodes(0)
+        {}
+
+        void preprocess(const PreprocessContext&);
+        void intersect(const RenderContext& context, RayPacket& rays) const;
+        void intersectNode(int nodeID, const RenderContext& context, 
RayPacket& rays) const;
+
+
+        // return the first index (between [rays.begin(),rays.end()]) which 
hits the box
+        int firstIntersects(const BBox& box, const RayPacket& rays) const;
+        // return the last index which hits the box
+        int lastIntersects(const BBox& box, const RayPacket& rays) const;
+
+        void computeBounds(const PreprocessContext&,
+                           BBox& bbox) const
+        {
+            if (num_nodes)
+                bbox = nodes[0].bounds;
+        }
+
+        static Group* create(const vector<string>&)
+        {
+            return new DynBVH();
+        }
+
+        void build(const PreprocessContext& context,
+                   int nodeID, int objectBegin, int objectEnd,
+                   int &nextFree, int depth = 0);
+
+        void updateBounds(const PreprocessContext& context, int ID = 0);
+
+
+        int partitionSAH(const PreprocessContext& context,
+                         int objBegin, int objEnd, int& output_axis);
+
+        struct BVHCostEval
+        {
+            float position;
+            float cost;
+            int num_left;
+            int num_right;
+            int event;
+            int axis;
+        };
+
+        struct BVHSAHEvent
+        {
+            float position;
+            int obj_id;
+            float left_area;
+            float right_area;
+            int num_left;
+            int num_right;
+            float cost;
+        };
+
+        struct CompareBVHSAHEvent
+        {
+            bool operator()(const BVHSAHEvent& x, const BVHSAHEvent& y)
+            {
+                // add obj_id sorting in here automatically?
+                return x.position < y.position;
+            }
+        };
+
+        bool buildEvents(const PreprocessContext& context,
+                         int first,
+                         int last,
+                         int axis,
+                         BVHCostEval& eval);
+
+    };
+};
+
+#endif

Modified: trunk/Model/Groups/Group.cc
==============================================================================
--- trunk/Model/Groups/Group.cc (original)
+++ trunk/Model/Groups/Group.cc Fri Feb 24 00:03:16 2006
@@ -36,7 +36,12 @@
   return objs[i];
 }
 
-void Group::shrinkTo(int firstNumObjs, bool deleteRemainder) 
+const Object* Group::get(int i) const
+{
+    return objs[i];
+}
+
+void Group::shrinkTo(int firstNumObjs, bool deleteRemainder)
 {
     if (deleteRemainder)
         for(int i=firstNumObjs;i<static_cast<int>(objs.size());i++)
@@ -44,7 +49,7 @@
     objs.resize(firstNumObjs);
 }
 
-int Group::getSize() 
+int Group::getSize() const
 {
   return static_cast<int>(objs.size());
 }

Modified: trunk/Model/Groups/Group.h
==============================================================================
--- trunk/Model/Groups/Group.h  (original)
+++ trunk/Model/Groups/Group.h  Fri Feb 24 00:03:16 2006
@@ -19,9 +19,10 @@
     void add(Object* obj);
     void set( int i, Object *obj );
     Object *get( int i );
+    const Object* get(int i) const;
 
     void shrinkTo(int firstNumObjs, bool deleteRemainder);
-    int getSize();
+    int getSize() const;
 
     virtual void preprocess(const PreprocessContext&);
     virtual void intersect(const RenderContext& context, RayPacket& rays) 
const;

---

• [MANTA] r955 - trunk/Model/Groups, boulos, 02/24/2006

---

Archive powered by MHonArc 2.6.16.