← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to source/blender/blenlib/intern/BLI_kdopbvh.c

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2014-02-19 11:24:23 UTC
  • mfrom: (14.2.23 sid)
  • Revision ID: package-import@ubuntu.com-20140219112423-rkmaz2m7ha06d4tk
Tags: 2.69-3ubuntu1
* Merge with Debian; remaining changes:
  - Configure without OpenImageIO on armhf, as it is not available on
    Ubuntu.

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/blenlib/intern/BLI_kdopbvh.c
36
36
#include "BLI_utildefines.h"
37
37
#include "BLI_kdopbvh.h"
38
38
#include "BLI_math.h"
 
39
#include "BLI_strict_flags.h"
39
40
 
40
41
#ifdef _OPENMP
41
42
#include <omp.h>
65
66
        int totleaf;            /* leafs */
66
67
        int totbranch;
67
68
        axis_t start_axis, stop_axis;  /* KDOP_AXES array indices according to axis */
68
 
        axis_t axis;              /* kdop type (6 => OBB, 7 => AABB, ...) */
69
 
        char tree_type;         /* type of tree (4 => quadtree) */
 
69
        axis_t axis;                   /* kdop type (6 => OBB, 7 => AABB, ...) */
 
70
        char tree_type;                /* type of tree (4 => quadtree) */
70
71
};
71
72
 
72
73
/* optimization, ensure we stay small */
73
74
BLI_STATIC_ASSERT((sizeof(void *) == 8 && sizeof(BVHTree) <= 48) ||
74
75
                  (sizeof(void *) == 4 && sizeof(BVHTree) <= 32),
75
 
                  "over sized");
 
76
                  "over sized")
76
77
 
77
78
typedef struct BVHOverlapData {
78
79
        BVHTree *tree1, *tree2; 
79
80
        BVHTreeOverlap *overlap; 
80
 
        int i, max_overlap; /* i is number of overlaps */
 
81
        unsigned int i;
 
82
        unsigned int max_overlap; /* i is number of overlaps */
81
83
        axis_t start_axis, stop_axis;
82
84
} BVHOverlapData;
83
85
 
437
439
 
438
440
/* only supports x,y,z axis in the moment
439
441
 * but we should use a plain and simple function here for speed sake */
440
 
static char get_largest_axis(float *bv)
 
442
static char get_largest_axis(const float *bv)
441
443
{
442
444
        float middle_point[3];
443
445
 
497
499
        axis_t axis_iter;
498
500
 
499
501
        for (i = 0; i < depth; i++) printf(" ");
500
 
        printf(" - %d (%ld): ", node->index, node - tree->nodearray);
501
 
        for (axis_iter = 2 * tree->start_axis; axis_iter < 2 * tree->stop_axis; axis_iter++)
 
502
        printf(" - %d (%ld): ", node->index, (long int)(node - tree->nodearray));
 
503
        for (axis_iter = (axis_t)(2 * tree->start_axis);
 
504
             axis_iter < (axis_t)(2 * tree->stop_axis);
 
505
             axis_iter++)
 
506
        {
502
507
                printf("%.3f ", node->bv[axis_iter]);
 
508
        }
503
509
        printf("\n");
504
510
 
505
511
        for (i = 0; i < tree->tree_type; i++)
513
519
        printf("tree_type = %d, axis = %d, epsilon = %f\n", tree->tree_type, tree->axis, tree->epsilon);
514
520
        printf("nodes = %d, branches = %d, leafs = %d\n", tree->totbranch + tree->totleaf,  tree->totbranch, tree->totleaf);
515
521
        printf("Memory per node = %ldbytes\n", sizeof(BVHNode) + sizeof(BVHNode *) * tree->tree_type + sizeof(float) * tree->axis);
516
 
        printf("BV memory = %dbytes\n", MEM_allocN_len(tree->nodebv));
 
522
        printf("BV memory = %dbytes\n", (int)MEM_allocN_len(tree->nodebv));
517
523
 
518
524
        printf("Total memory = %ldbytes\n", sizeof(BVHTree) +
519
525
               MEM_allocN_len(tree->nodes) +
603
609
        data->branches_on_level[0] = 1;
604
610
 
605
611
        /* We could stop the loop first (but I am lazy to find out when) */
 
612
        /* note: this often causes integer overflow, may be worth avoiding? - campbell */
606
613
        for (depth = 1; depth < 32; depth++) {
607
614
                data->branches_on_level[depth] = data->branches_on_level[depth - 1] * data->tree_type;
608
615
                data->leafs_per_child[depth] = data->leafs_per_child[depth - 1] / data->tree_type;
791
798
                                        break;
792
799
                                }
793
800
 
794
 
                                parent->totnode = k + 1;
 
801
                                parent->totnode = (char)(k + 1);
795
802
                        }
796
803
                }
797
804
        }
810
817
        if (tree_type < 2)
811
818
                return NULL;
812
819
 
813
 
        if (tree_type > MAX_TREETYPE)
814
 
                return NULL;
 
820
        BLI_assert(tree_type <= MAX_TREETYPE);
815
821
 
816
 
        tree = (BVHTree *)MEM_callocN(sizeof(BVHTree), "BVHTree");
 
822
        tree = MEM_callocN(sizeof(BVHTree), "BVHTree");
817
823
 
818
824
        /* tree epsilon must be >= FLT_EPSILON
819
825
         * so that tangent rays can still hit a bounding volume..
854
860
                /* Allocate arrays */
855
861
                numnodes = maxsize + implicit_needed_branches(tree_type, maxsize) + tree_type;
856
862
 
857
 
                tree->nodes = (BVHNode **)MEM_callocN(sizeof(BVHNode *) * numnodes, "BVHNodes");
 
863
                tree->nodes = MEM_callocN(sizeof(BVHNode *) * (size_t)numnodes, "BVHNodes");
858
864
                
859
865
                if (!tree->nodes) {
860
866
                        MEM_freeN(tree);
861
867
                        return NULL;
862
868
                }
863
 
                
864
 
                tree->nodebv = (float *)MEM_callocN(sizeof(float) * axis * numnodes, "BVHNodeBV");
 
869
 
 
870
                tree->nodebv = MEM_callocN(sizeof(float) * (size_t)(axis * numnodes), "BVHNodeBV");
865
871
                if (!tree->nodebv) {
866
872
                        MEM_freeN(tree->nodes);
867
873
                        MEM_freeN(tree);
868
874
                }
869
875
 
870
 
                tree->nodechild = (BVHNode **)MEM_callocN(sizeof(BVHNode *) * tree_type * numnodes, "BVHNodeBV");
 
876
                tree->nodechild = MEM_callocN(sizeof(BVHNode *) * (size_t)(tree_type * numnodes), "BVHNodeBV");
871
877
                if (!tree->nodechild) {
872
878
                        MEM_freeN(tree->nodebv);
873
879
                        MEM_freeN(tree->nodes);
874
880
                        MEM_freeN(tree);
875
881
                }
876
882
 
877
 
                tree->nodearray = (BVHNode *)MEM_callocN(sizeof(BVHNode) * numnodes, "BVHNodeArray");
 
883
                tree->nodearray = MEM_callocN(sizeof(BVHNode) * (size_t)numnodes, "BVHNodeArray");
878
884
                
879
885
                if (!tree->nodearray) {
880
886
                        MEM_freeN(tree->nodechild);
914
920
        BVHNode **leafs_array    = tree->nodes;
915
921
 
916
922
        /* This function should only be called once (some big bug goes here if its being called more than once per tree) */
917
 
        assert(tree->totbranch == 0);
 
923
        BLI_assert(tree->totbranch == 0);
918
924
 
919
925
        /* Build the implicit tree */
920
926
        non_recursive_bvh_div_nodes(tree, branches_array, leafs_array, tree->totleaf);
929
935
        /* bvhtree_info(tree); */
930
936
}
931
937
 
932
 
int BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
 
938
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
933
939
{
934
940
        axis_t axis_iter;
935
941
        BVHNode *node = NULL;
936
942
 
937
943
        /* insert should only possible as long as tree->totbranch is 0 */
938
 
        if (tree->totbranch > 0)
939
 
                return 0;
940
 
 
941
 
        if (tree->totleaf + 1 >= MEM_allocN_len(tree->nodes) / sizeof(*(tree->nodes)))
942
 
                return 0;
943
 
 
944
 
        /* TODO check if have enough nodes in array */
 
944
        BLI_assert(tree->totbranch <= 0);
 
945
        BLI_assert((size_t)tree->totleaf < MEM_allocN_len(tree->nodes) / sizeof(*(tree->nodes)));
945
946
 
946
947
        node = tree->nodes[tree->totleaf] = &(tree->nodearray[tree->totleaf]);
947
948
        tree->totleaf++;
954
955
                node->bv[(2 * axis_iter)] -= tree->epsilon; /* minimum */
955
956
                node->bv[(2 * axis_iter) + 1] += tree->epsilon; /* maximum */
956
957
        }
957
 
 
958
 
        return 1;
959
958
}
960
959
 
961
960
 
1011
1010
 * overlap - is it possible for 2 bv's to collide ? */
1012
1011
static int tree_overlap(BVHNode *node1, BVHNode *node2, axis_t start_axis, axis_t stop_axis)
1013
1012
{
1014
 
        float *bv1 = node1->bv;
1015
 
        float *bv2 = node2->bv;
 
1013
        const float *bv1 = node1->bv;
 
1014
        const float *bv2 = node2->bv;
1016
1015
 
1017
 
        float *bv1_end = bv1 + (stop_axis << 1);
 
1016
        const float *bv1_end = bv1 + (stop_axis << 1);
1018
1017
                
1019
1018
        bv1 += start_axis << 1;
1020
1019
        bv2 += start_axis << 1;
1044
1043
 
1045
1044
                                if (data->i >= data->max_overlap) {
1046
1045
                                        /* try to make alloc'ed memory bigger */
1047
 
                                        data->overlap = realloc(data->overlap, sizeof(BVHTreeOverlap) * data->max_overlap * 2);
 
1046
                                        data->overlap = realloc(data->overlap, sizeof(BVHTreeOverlap) * (size_t)data->max_overlap * 2);
1048
1047
                                        
1049
1048
                                        if (!data->overlap) {
1050
1049
                                                printf("Out of Memory in traverse\n");
1098
1097
        data = MEM_callocN(sizeof(BVHOverlapData *) * tree1->tree_type, "BVHOverlapData_star");
1099
1098
        
1100
1099
        for (j = 0; j < tree1->tree_type; j++) {
1101
 
                data[j] = (BVHOverlapData *)MEM_callocN(sizeof(BVHOverlapData), "BVHOverlapData");
 
1100
                data[j] = MEM_callocN(sizeof(BVHOverlapData), "BVHOverlapData");
1102
1101
                
1103
1102
                /* init BVHOverlapData */
1104
 
                data[j]->overlap = (BVHTreeOverlap *)malloc(sizeof(BVHTreeOverlap) * max_ii(tree1->totleaf, tree2->totleaf));
 
1103
                data[j]->overlap = malloc(sizeof(BVHTreeOverlap) * (size_t)max_ii(tree1->totleaf, tree2->totleaf));
1105
1104
                data[j]->tree1 = tree1;
1106
1105
                data[j]->tree2 = tree2;
1107
 
                data[j]->max_overlap = max_ii(tree1->totleaf, tree2->totleaf);
 
1106
                data[j]->max_overlap = (unsigned int)max_ii(tree1->totleaf, tree2->totleaf);
1108
1107
                data[j]->i = 0;
1109
1108
                data[j]->start_axis = min_axis(tree1->start_axis, tree2->start_axis);
1110
1109
                data[j]->stop_axis  = min_axis(tree1->stop_axis,  tree2->stop_axis);
1118
1117
        for (j = 0; j < tree1->tree_type; j++)
1119
1118
                total += data[j]->i;
1120
1119
        
1121
 
        to = overlap = (BVHTreeOverlap *)MEM_callocN(sizeof(BVHTreeOverlap) * total, "BVHTreeOverlap");
 
1120
        to = overlap = MEM_callocN(sizeof(BVHTreeOverlap) * total, "BVHTreeOverlap");
1122
1121
        
1123
1122
        for (j = 0; j < tree1->tree_type; j++) {
1124
1123
                memcpy(to, data[j]->overlap, data[j]->i * sizeof(BVHTreeOverlap));