-== Cloth / kdop ==-
authorDaniel Genrich <daniel.genrich@gmx.net>
Sun, 25 May 2008 13:15:54 +0000 (13:15 +0000)
committerDaniel Genrich <daniel.genrich@gmx.net>
Sun, 25 May 2008 13:15:54 +0000 (13:15 +0000)
1. Bugfix for crash on enabling cloth on object
2. Correcting kdop nth element sorting function (fix provided by AndrĂ© Pinto)

source/blender/blenkernel/intern/cloth.c
source/blender/blenlib/intern/BLI_kdopbvh.c

index 916e3d6d3e885fcad25027a34c8c68c5e1fd2ba4..55d89e5f0dd5a9d0bad78f5c999ddf7ba0337e06 100644 (file)
@@ -210,11 +210,11 @@ BVHTree *bvhselftree_build_from_cloth (ClothModifierData *clmd, float epsilon)
        mfaces = cloth->mfaces;
        
        // in the moment, return zero if no faces there
-       if(!cloth->numfaces)
+       if(!cloth->numverts)
                return NULL;
        
        // create quadtree with k=26
-       bvhtree = BLI_bvhtree_new(cloth->numfaces, epsilon, 4, 6);
+       bvhtree = BLI_bvhtree_new(cloth->numverts, epsilon, 4, 6);
        
        // fill tree
        for(i = 0; i < cloth->numverts; i++, verts++)
index 83afe258aad563e90d7615f51f279bdcdabfbe24..5c3849d12104418991161ed2e642581b596740e9 100644 (file)
@@ -276,21 +276,22 @@ void sort_along_axis(BVHTree *tree, int start, int end, int axis)
 }
 
 //after a call to this function you can expect one of:
-//     every node to left of a[n] are smaller than it
-//     every node to the right of a[n-1] are greater than it
-void partition_nth_element(BVHNode **a, int _begin, int _end, int n, int axis)
-{
-       int begin = _begin, end = _end;
-       while(begin < n && end >= n)
-       {
-               int mid = bvh_partition(a, begin, end, bvh_medianof3(a, begin, (begin+end-1)/2, end-1, axis), axis );
-
-               if(mid >= n)
-                       end = n-1;
-               else
-                       begin = n+1;
-       }
-
+//      every node to left of a[n] are smaller or equal to it
+//      every node to the right of a[n] are greater or equal to it
+int partition_nth_element(BVHNode **a, int _begin, int _end, int n, int axis){        
+       int begin = _begin, end = _end, cut;        
+       int i;         
+       while(end-begin > 3)        
+       {                            
+               cut = bvh_partition(a, begin, end, bvh_medianof3(a, begin, (begin+end)/2, end-1, axis), axis );                 
+               if(cut <= n)                        
+                       begin = cut;                
+               else                        
+                       end = cut;        
+       }        
+       bvh_insertionsort(a, begin, end, axis);
+
+       return n;
 }
 
 
@@ -550,7 +551,8 @@ static void bvh_div_nodes(BVHTree *tree, BVHNode *node, int start, int end, char
                        tree->totbranch++;
                        tnode->parent = node;
                        
-                       partition_nth_element(tree->nodes, start, end, tend, laxis);
+                       if(tend != end)
+                               partition_nth_element(tree->nodes, start, end, tend, laxis);
                        refit_kdop_hull(tree, tnode, start, tend);
                        bvh_div_nodes(tree, tnode, start, tend, laxis);
                }
@@ -707,7 +709,7 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result)
 {
        int j, total = 0;
        BVHTreeOverlap *overlap = NULL, *to = NULL;
-       BVHOverlapData *data[tree1->tree_type];
+       BVHOverlapData **data;
        
        // check for compatibility of both trees (can't compare 14-DOP with 18-DOP)
        if((tree1->axis != tree2->axis) && ((tree1->axis == 14) || tree2->axis == 14))
@@ -716,6 +718,8 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result)
        // fast check root nodes for collision before doing big splitting + traversal
        if(!tree_overlap(tree1->nodes[tree1->totleaf]->bv, tree2->nodes[tree2->totleaf]->bv, MIN2(tree1->start_axis, tree2->start_axis), MIN2(tree1->stop_axis, tree2->stop_axis)))
                return 0;
+
+       *data = MEM_callocN(sizeof(BVHOverlapData *)* tree1->tree_type, "BVHOverlapData_star");
        
        for(j = 0; j < tree1->tree_type; j++)
        {
@@ -751,6 +755,7 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result)
                free(data[j]->overlap);
                MEM_freeN(data[j]);
        }
+       MEM_freeN(*data);
        
        (*result) = total;
        return overlap;