rename api functions...
[blender.git] / source / blender / blenlib / intern / BLI_kdopbvh.c
index e9ee91505de978b6176029781fe8c41287f9c760..4dea802208364d4eefd22cf93fe9dd365576c701 100644 (file)
  *  \ingroup bli
  */
 
-
 #include <assert.h>
 
 #include "MEM_guardedalloc.h"
 
 #include "BLI_utildefines.h"
-
-
-
 #include "BLI_kdopbvh.h"
 #include "BLI_math.h"
 
 #include <omp.h>
 #endif
 
-
-
 #define MAX_TREETYPE 32
-#define DEFAULT_FIND_NEAREST_HEAP_SIZE 1024
 
 typedef struct BVHNode {
        struct BVHNode **children;
-       struct BVHNode *parent; // some user defined traversed need that
+       struct BVHNode *parent; /* some user defined traversed need that */
        struct BVHNode *skip[2];
        float *bv;      /* Bounding volume of all nodes, max 13 axis */
        int index;      /* face, edge, vertex index */
@@ -104,16 +97,15 @@ typedef struct BVHRayCastData {
 
        BVHTreeRayHit hit;
 } BVHRayCastData;
-////////////////////////////////////////m
 
 
-////////////////////////////////////////////////////////////////////////
-// Bounding Volume Hierarchy Definition
-// 
-// Notes: From OBB until 26-DOP --> all bounding volumes possible, just choose type below
-// Notes: You have to choose the type at compile time ITM
-// Notes: You can choose the tree type --> binary, quad, octree, choose below
-////////////////////////////////////////////////////////////////////////
+/*
+ * Bounding Volume Hierarchy Definition
+ *
+ * Notes: From OBB until 26-DOP --> all bounding volumes possible, just choose type below
+ * Notes: You have to choose the type at compile time ITM
+ * Notes: You can choose the tree type --> binary, quad, octree, choose below
+ */
 
 static float KDOP_AXES[13][3] = {
        {1.0, 0, 0}, {0, 1.0, 0}, {0, 0, 1.0}, {1.0, 1.0, 1.0}, {1.0, -1.0, 1.0}, {1.0, 1.0, -1.0},
@@ -121,6 +113,8 @@ static float KDOP_AXES[13][3] = {
        {0, 1.0, -1.0}
 };
 
+#if 0
+
 /*
  * Generic push and pop heap
  */
@@ -139,7 +133,7 @@ static float KDOP_AXES[13][3] = {
                        else break;                                                       \
                }                                                                     \
                heap[child] = element;                                                \
-       }
+       } (void)0
 
 #define POP_HEAP_BODY(HEAP_TYPE, PRIORITY, heap, heap_size)                   \
        {                                                                         \
@@ -158,9 +152,8 @@ static float KDOP_AXES[13][3] = {
                        parent = child2;                                                  \
                }                                                                     \
                heap[parent] = element;                                               \
-       }
+       } (void)0
 
-#if 0
 static int ADJUST_MEMORY(void *local_memblock, void **memblock, int new_size, int *max_size, int size_per_item)
 {
        int new_max_size = *max_size * 2;
@@ -188,13 +181,15 @@ static int ADJUST_MEMORY(void *local_memblock, void **memblock, int new_size, in
 }
 #endif
 
-//////////////////////////////////////////////////////////////////////////////////////////////////////
-// Introsort 
-// with permission deriven from the following Java code:
-// http://ralphunden.net/content/tutorials/a-guide-to-introsort/
-// and he derived it from the SUN STL 
-//////////////////////////////////////////////////////////////////////////////////////////////////////
+/*
+ * Introsort
+ * with permission deriven from the following Java code:
+ * http://ralphunden.net/content/tutorials/a-guide-to-introsort/
+ * and he derived it from the SUN STL
+ */
+
 //static int size_threshold = 16;
+
 /*
  * Common methods for all algorithms
  */
@@ -274,7 +269,7 @@ static void bvh_heapsort(BVHNode **a, int lo, int hi, int axis)
 }
 #endif
 
-static BVHNode *bvh_medianof3(BVHNode **a, int lo, int mid, int hi, int axis) // returns Sortable
+static BVHNode *bvh_medianof3(BVHNode **a, int lo, int mid, int hi, int axis)  /* returns Sortable */
 {
        if ((a[mid])->bv[axis] < (a[lo])->bv[axis]) {
                if ((a[hi])->bv[axis] < (a[mid])->bv[axis])
@@ -336,9 +331,9 @@ static void sort_along_axis(BVHTree *tree, int start, int end, int axis)
 }
 #endif
 
-//after a call to this function you can expect one of:
-//      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
+/after a call to this function you can expect one of:
+ * - 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 */
 static int partition_nth_element(BVHNode **a, int _begin, int _end, int n, int axis)
 {
        int begin = _begin, end = _end, cut;
@@ -354,7 +349,7 @@ static int partition_nth_element(BVHNode **a, int _begin, int _end, int n, int a
        return n;
 }
 
-//////////////////////////////////////////////////////////////////////////////////////////////////////
+/* --- */
 static void build_skip_links(BVHTree *tree, BVHNode *node, BVHNode *left, BVHNode *right)
 {
        int i;
@@ -381,8 +376,8 @@ static void create_kdop_hull(BVHTree *tree, BVHNode *node, const float *co, int
        float *bv = node->bv;
        int i, k;
        
-       // don't init boudings for the moving case
-       if (!moving) {
+       /* don't init boudings for the moving case */
+               if (!moving) {
                for (i = tree->start_axis; i < tree->stop_axis; i++) {
                        bv[2 * i] = FLT_MAX;
                        bv[2 * i + 1] = -FLT_MAX;
@@ -401,7 +396,7 @@ static void create_kdop_hull(BVHTree *tree, BVHNode *node, const float *co, int
        }
 }
 
-// depends on the fact that the BVH's for each face is already build
+/* depends on the fact that the BVH's for each face is already build */
 static void refit_kdop_hull(BVHTree *tree, BVHNode *node, int start, int end)
 {
        float newmin, newmax;
@@ -429,31 +424,31 @@ static void refit_kdop_hull(BVHTree *tree, BVHNode *node, int start, int end)
 
 }
 
-// only supports x,y,z axis in the moment
-// but we should use a plain and simple function here for speed sake
+/* only supports x,y,z axis in the moment
+ * but we should use a plain and simple function here for speed sake */
 static char get_largest_axis(float *bv)
 {
        float middle_point[3];
 
-       middle_point[0] = (bv[1]) - (bv[0]); // x axis
-       middle_point[1] = (bv[3]) - (bv[2]); // y axis
-       middle_point[2] = (bv[5]) - (bv[4]); // z axis
+       middle_point[0] = (bv[1]) - (bv[0]); /* x axis */
+       middle_point[1] = (bv[3]) - (bv[2]); /* y axis */
+       middle_point[2] = (bv[5]) - (bv[4]); /* z axis */
        if (middle_point[0] > middle_point[1]) {
                if (middle_point[0] > middle_point[2])
-                       return 1;  // max x axis
+                       return 1;  /* max x axis */
                else
-                       return 5;  // max z axis
+                       return 5;  /* max z axis */
        }
        else {
                if (middle_point[1] > middle_point[2])
-                       return 3;  // max y axis
+                       return 3;  /* max y axis */
                else
-                       return 5;  // max z axis
+                       return 5;  /* max z axis */
        }
 }
 
-// bottom-up update of bvh node BV
-// join the children on the parent BV
+/* bottom-up update of bvh node BV
+ * join the children on the parent BV */
 static void node_join(BVHTree *tree, BVHNode *node)
 {
        int i, j;
@@ -466,11 +461,11 @@ static void node_join(BVHTree *tree, BVHNode *node)
        for (i = 0; i < tree->tree_type; i++) {
                if (node->children[i]) {
                        for (j = tree->start_axis; j < tree->stop_axis; j++) {
-                               // update minimum 
-                               if (node->children[i]->bv[(2 * j)] < node->bv[(2 * j)]) 
+                               /* update minimum */
+                               if (node->children[i]->bv[(2 * j)] < node->bv[(2 * j)])
                                        node->bv[(2 * j)] = node->children[i]->bv[(2 * j)];
-                               
-                               // update maximum 
+
+                               /* update maximum */
                                if (node->children[i]->bv[(2 * j) + 1] > node->bv[(2 * j) + 1])
                                        node->bv[(2 * j) + 1] = node->children[i]->bv[(2 * j) + 1];
                        }
@@ -523,7 +518,7 @@ static void verify_tree(BVHTree *tree)
 {
        int i, j, check = 0;
        
-       // check the pointer list
+       /* check the pointer list */
        for (i = 0; i < tree->totleaf; i++)
        {
                if (tree->nodes[i]->parent == NULL) {
@@ -543,7 +538,7 @@ static void verify_tree(BVHTree *tree)
                }
        }
        
-       // check the leaf list
+       /* check the leaf list */
        for (i = 0; i < tree->totleaf; i++)
        {
                if (tree->nodearray[i].parent == NULL) {
@@ -567,8 +562,8 @@ static void verify_tree(BVHTree *tree)
 }
 #endif
 
-//Helper data and structures to build a min-leaf generalized implicit tree
-//This code can be easily reduced (basicly this is only method to calculate pow(k, n) in O(1).. and stuff like that)
+/Helper data and structures to build a min-leaf generalized implicit tree
+ * This code can be easily reduced (basicly this is only method to calculate pow(k, n) in O(1).. and stuff like that) */
 typedef struct BVHBuildHelper {
        int tree_type;              /* */
        int totleafs;               /* */
@@ -589,7 +584,7 @@ static void build_implicit_tree_helper(BVHTree *tree, BVHBuildHelper *data)
        data->totleafs = tree->totleaf;
        data->tree_type = tree->tree_type;
 
-       //Calculate the smallest tree_type^n such that tree_type^n >= num_leafs
+       /* Calculate the smallest tree_type^n such that tree_type^n >= num_leafs */
        for (data->leafs_per_child[0] = 1;
             data->leafs_per_child[0] <  data->totleafs;
             data->leafs_per_child[0] *= data->tree_type)
@@ -599,7 +594,7 @@ static void build_implicit_tree_helper(BVHTree *tree, BVHBuildHelper *data)
 
        data->branches_on_level[0] = 1;
 
-       //We could stop the loop first (but I am lazy to find out when)
+       /* We could stop the loop first (but I am lazy to find out when) */
        for (depth = 1; depth < 32; depth++) {
                data->branches_on_level[depth] = data->branches_on_level[depth - 1] * data->tree_type;
                data->leafs_per_child[depth] = data->leafs_per_child[depth - 1] / data->tree_type;
@@ -650,10 +645,10 @@ static int implicit_leafs_index(BVHBuildHelper *data, int depth, int child_index
  *    (looping elements, knowing if its a leaf or not.. etc...)
  */
 
-// This functions returns the number of branches needed to have the requested number of leafs.
+/* This functions returns the number of branches needed to have the requested number of leafs. */
 static int implicit_needed_branches(int tree_type, int leafs)
 {
-       return MAX2(1, (leafs + tree_type - 3) / (tree_type - 1) );
+       return max_ii(1, (leafs + tree_type - 3) / (tree_type - 1) );
 }
 
 /*
@@ -692,7 +687,7 @@ static void split_leafs(BVHNode **leafs_array, int *nth, int partitions, int spl
  * The reason is that we can build level N+1 from level N without any data dependencies.. thus it allows
  * to use multithread building.
  *
- * To archieve this is necessary to find how much leafs are accessible from a certain branch, BVHBuildHelper
+ * To archive this is necessary to find how much leafs are accessible from a certain branch, BVHBuildHelper
  * implicit_needed_branches and implicit_leafs_index are auxiliary functions to solve that "optimal-split".
  */
 static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array, BVHNode **leafs_array, int num_leafs)
@@ -700,18 +695,18 @@ static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array,
        int i;
 
        const int tree_type   = tree->tree_type;
-       const int tree_offset = 2 - tree->tree_type; //this value is 0 (on binary trees) and negative on the others
+       const int tree_offset = 2 - tree->tree_type; /* this value is 0 (on binary trees) and negative on the others */
        const int num_branches = implicit_needed_branches(tree_type, num_leafs);
 
        BVHBuildHelper data;
        int depth;
        
-       // set parent from root node to NULL
+       /* set parent from root node to NULL */
        BVHNode *tmp = branches_array + 0;
        tmp->parent = NULL;
 
-       //Most of bvhtree code relies on 1-leaf trees having at least one branch
-       //We handle that special case here
+       /Most of bvhtree code relies on 1-leaf trees having at least one branch
+        * We handle that special case here */
        if (num_leafs == 1) {
                BVHNode *root = branches_array + 0;
                refit_kdop_hull(tree, root, 0, num_leafs);
@@ -722,17 +717,17 @@ static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array,
                return;
        }
 
-       branches_array--;   //Implicit trees use 1-based indexs
-       
+       branches_array--;  /* Implicit trees use 1-based indexs */
+
        build_implicit_tree_helper(tree, &data);
 
-       //Loop tree levels (log N) loops
+       /* Loop tree levels (log N) loops */
        for (i = 1, depth = 1; i <= num_branches; i = i * tree_type + tree_offset, depth++) {
                const int first_of_next_level = i * tree_type + tree_offset;
-               const int end_j = MIN2(first_of_next_level, num_branches + 1);  //index of last branch on this level
+               const int end_j = MIN2(first_of_next_level, num_branches + 1);  /* index of last branch on this level */
                int j;
 
-               //Loop all branches on this level
+               /* Loop all branches on this level */
 #pragma omp parallel for private(j) schedule(static)
                for (j = i; j < end_j; j++) {
                        int k;
@@ -744,34 +739,34 @@ static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array,
                        int parent_leafs_begin = implicit_leafs_index(&data, depth, parent_level_index);
                        int parent_leafs_end   = implicit_leafs_index(&data, depth, parent_level_index + 1);
 
-                       //This calculates the bounding box of this branch
-                       //and chooses the largest axis as the axis to divide leafs
+                       /This calculates the bounding box of this branch
+                        * and chooses the largest axis as the axis to divide leafs */
                        refit_kdop_hull(tree, parent, parent_leafs_begin, parent_leafs_end);
                        split_axis = get_largest_axis(parent->bv);
 
-                       //Save split axis (this can be used on raytracing to speedup the query time)
+                       /* Save split axis (this can be used on raytracing to speedup the query time) */
                        parent->main_axis = split_axis / 2;
 
-                       //Split the childs along the split_axis, note: its not needed to sort the whole leafs array
-                       //Only to assure that the elements are partioned on a way that each child takes the elements
-                       //it would take in case the whole array was sorted.
-                       //Split_leafs takes care of that "sort" problem.
+                       /Split the childs along the split_axis, note: its not needed to sort the whole leafs array
+                        * Only to assure that the elements are partitioned on a way that each child takes the elements
+                        * it would take in case the whole array was sorted.
+                        * Split_leafs takes care of that "sort" problem. */
                        nth_positions[0] = parent_leafs_begin;
                        nth_positions[tree_type] = parent_leafs_end;
                        for (k = 1; k < tree_type; k++) {
                                int child_index = j * tree_type + tree_offset + k;
-                               int child_level_index = child_index - first_of_next_level; //child level index
+                               int child_level_index = child_index - first_of_next_level; /* child level index */
                                nth_positions[k] = implicit_leafs_index(&data, depth + 1, child_level_index);
                        }
 
                        split_leafs(leafs_array, nth_positions, tree_type, split_axis);
 
 
-                       //Setup children and totnode counters
-                       //Not really needed but currently most of BVH code relies on having an explicit children structure
+                       /Setup children and totnode counters
+                        * Not really needed but currently most of BVH code relies on having an explicit children structure */
                        for (k = 0; k < tree_type; k++) {
                                int child_index = j * tree_type + tree_offset + k;
-                               int child_level_index = child_index - first_of_next_level; //child level index
+                               int child_level_index = child_index - first_of_next_level; /* child level index */
 
                                int child_leafs_begin = implicit_leafs_index(&data, depth + 1, child_level_index);
                                int child_leafs_end   = implicit_leafs_index(&data, depth + 1, child_level_index + 1);
@@ -803,20 +798,20 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
        BVHTree *tree;
        int numnodes, i;
        
-       // theres not support for trees below binary-trees :P
+       /* theres not support for trees below binary-trees :P */
        if (tree_type < 2)
                return NULL;
-       
+
        if (tree_type > MAX_TREETYPE)
                return NULL;
 
        tree = (BVHTree *)MEM_callocN(sizeof(BVHTree), "BVHTree");
 
-       //tree epsilon must be >= FLT_EPSILON
-       //so that tangent rays can still hit a bounding volume..
-       //this bug would show up when casting a ray aligned with a kdop-axis and with an edge of 2 faces
+       /tree epsilon must be >= FLT_EPSILON
+        * so that tangent rays can still hit a bounding volume..
+        * this bug would show up when casting a ray aligned with a kdop-axis and with an edge of 2 faces */
        epsilon = MAX2(FLT_EPSILON, epsilon);
-       
+
        if (tree) {
                tree->epsilon = epsilon;
                tree->tree_type = tree_type; 
@@ -848,7 +843,7 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
                }
 
 
-               //Allocate arrays
+               /* Allocate arrays */
                numnodes = maxsize + implicit_needed_branches(tree_type, maxsize) + tree_type;
 
                tree->nodes = (BVHNode **)MEM_callocN(sizeof(BVHNode *) * numnodes, "BVHNodes");
@@ -881,7 +876,7 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
                        return NULL;
                }
 
-               //link the dynamic bv and child links
+               /* link the dynamic bv and child links */
                for (i = 0; i < numnodes; i++) {
                        tree->nodearray[i].bv = tree->nodebv + i * axis;
                        tree->nodearray[i].children = tree->nodechild + i * tree_type;
@@ -910,59 +905,59 @@ void BLI_bvhtree_balance(BVHTree *tree)
        BVHNode *branches_array = tree->nodearray + tree->totleaf;
        BVHNode **leafs_array    = tree->nodes;
 
-       //This function should only be called once (some big bug goes here if its being called more than once per tree)
+       /* This function should only be called once (some big bug goes here if its being called more than once per tree) */
        assert(tree->totbranch == 0);
 
-       //Build the implicit tree
+       /* Build the implicit tree */
        non_recursive_bvh_div_nodes(tree, branches_array, leafs_array, tree->totleaf);
 
-       //current code expects the branches to be linked to the nodes array
-       //we perform that linkage here
+       /*current code expects the branches to be linked to the nodes array
+        *we perform that linkage here */
        tree->totbranch = implicit_needed_branches(tree->tree_type, tree->totleaf);
        for (i = 0; i < tree->totbranch; i++)
                tree->nodes[tree->totleaf + i] = branches_array + i;
 
        build_skip_links(tree, tree->nodes[tree->totleaf], NULL, NULL);
-       //bvhtree_info(tree);
+       /* bvhtree_info(tree); */
 }
 
-int BLI_bvhtree_insert(BVHTree *tree, int index, const float *co, int numpoints)
+int BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
 {
        int i;
        BVHNode *node = NULL;
-       
-       // insert should only possible as long as tree->totbranch is 0
+
+       /* insert should only possible as long as tree->totbranch is 0 */
        if (tree->totbranch > 0)
                return 0;
-       
+
        if (tree->totleaf + 1 >= MEM_allocN_len(tree->nodes) / sizeof(*(tree->nodes)))
                return 0;
-       
-       // TODO check if have enough nodes in array
-       
+
+       /* TODO check if have enough nodes in array */
+
        node = tree->nodes[tree->totleaf] = &(tree->nodearray[tree->totleaf]);
        tree->totleaf++;
-       
+
        create_kdop_hull(tree, node, co, numpoints, 0);
        node->index = index;
-       
-       // inflate the bv with some epsilon
+
+       /* inflate the bv with some epsilon */
        for (i = tree->start_axis; i < tree->stop_axis; i++) {
-               node->bv[(2 * i)] -= tree->epsilon; // minimum 
-               node->bv[(2 * i) + 1] += tree->epsilon; // maximum 
+               node->bv[(2 * i)] -= tree->epsilon; /* minimum */
+               node->bv[(2 * i) + 1] += tree->epsilon; /* maximum */
        }
 
        return 1;
 }
 
 
-// call before BLI_bvhtree_update_tree()
-int BLI_bvhtree_update_node(BVHTree *tree, int index, const float *co, const float *co_moving, int numpoints)
+/* call before BLI_bvhtree_update_tree() */
+int BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints)
 {
        int i;
        BVHNode *node = NULL;
        
-       // check if index exists
+       /* check if index exists */
        if (index > tree->totleaf)
                return 0;
        
@@ -973,21 +968,21 @@ int BLI_bvhtree_update_node(BVHTree *tree, int index, const float *co, const flo
        if (co_moving)
                create_kdop_hull(tree, node, co_moving, numpoints, 1);
        
-       // inflate the bv with some epsilon
+       /* inflate the bv with some epsilon */
        for (i = tree->start_axis; i < tree->stop_axis; i++) {
-               node->bv[(2 * i)] -= tree->epsilon; // minimum 
-               node->bv[(2 * i) + 1] += tree->epsilon; // maximum 
+               node->bv[(2 * i)]     -= tree->epsilon; /* minimum */
+               node->bv[(2 * i) + 1] += tree->epsilon; /* maximum */
        }
 
        return 1;
 }
 
-// call BLI_bvhtree_update_node() first for every node/point/triangle
+/* call BLI_bvhtree_update_node() first for every node/point/triangle */
 void BLI_bvhtree_update_tree(BVHTree *tree)
 {
-       //Update bottom=>top
-       //TRICKY: the way we build the tree all the childs have an index greater than the parent
-       //This allows us todo a bottom up update by starting on the biger numbered branch
+       /Update bottom=>top
+        * TRICKY: the way we build the tree all the childs have an index greater than the parent
+        * This allows us todo a bottom up update by starting on the bigger numbered branch */
 
        BVHNode **root  = tree->nodes + tree->totleaf;
        BVHNode **index = tree->nodes + tree->totleaf + tree->totbranch - 1;
@@ -1004,8 +999,8 @@ float BLI_bvhtree_getepsilon(BVHTree *tree)
 
 /*
  * BLI_bvhtree_overlap
- */
-// overlap - is it possbile for 2 bv's to collide ?
+ *
+ * overlap - is it possible for 2 bv's to collide ? */
 static int tree_overlap(BVHNode *node1, BVHNode *node2, int start_axis, int stop_axis)
 {
        float *bv1 = node1->bv;
@@ -1016,31 +1011,31 @@ static int tree_overlap(BVHNode *node1, BVHNode *node2, int start_axis, int stop
        bv1 += start_axis << 1;
        bv2 += start_axis << 1;
        
-       // test all axis if min + max overlap
+       /* test all axis if min + max overlap */
        for (; bv1 != bv1_end; bv1 += 2, bv2 += 2) {
-               if ((*(bv1) > *(bv2 + 1)) || (*(bv2) > *(bv1 + 1))) 
+               if ((*(bv1) > *(bv2 + 1)) || (*(bv2) > *(bv1 + 1)))
                        return 0;
        }
-       
+
        return 1;
 }
 
 static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2)
 {
        int j;
-       
+
        if (tree_overlap(node1, node2, data->start_axis, data->stop_axis)) {
-               // check if node1 is a leaf
+               /* check if node1 is a leaf */
                if (!node1->totnode) {
-                       // check if node2 is a leaf
+                       /* check if node2 is a leaf */
                        if (!node2->totnode) {
-                               
+
                                if (node1 == node2) {
                                        return;
                                }
-                                       
+
                                if (data->i >= data->max_overlap) {
-                                       // try to make alloc'ed memory bigger
+                                       /* try to make alloc'ed memory bigger */
                                        data->overlap = realloc(data->overlap, sizeof(BVHTreeOverlap) * data->max_overlap * 2);
                                        
                                        if (!data->overlap) {
@@ -1050,7 +1045,7 @@ static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2)
                                        data->max_overlap *= 2;
                                }
                                
-                               // both leafs, insert overlap!
+                               /* both leafs, insert overlap! */
                                data->overlap[data->i].indexA = node1->index;
                                data->overlap[data->i].indexB = node2->index;
 
@@ -1080,11 +1075,11 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int
        BVHTreeOverlap *overlap = NULL, *to = NULL;
        BVHOverlapData **data;
        
-       // check for compatibility of both trees (can't compare 14-DOP with 18-DOP)
+       /* 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) && (tree1->axis == 18 || tree2->axis == 18))
                return NULL;
        
-       // fast check root nodes for collision before doing big splitting + traversal
+       /* fast check root nodes for collision before doing big splitting + traversal */
        if (!tree_overlap(tree1->nodes[tree1->totleaf], tree2->nodes[tree2->totleaf], MIN2(tree1->start_axis, tree2->start_axis), MIN2(tree1->stop_axis, tree2->stop_axis)))
                return NULL;
 
@@ -1093,7 +1088,7 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int
        for (j = 0; j < tree1->tree_type; j++) {
                data[j] = (BVHOverlapData *)MEM_callocN(sizeof(BVHOverlapData), "BVHOverlapData");
                
-               // init BVHOverlapData
+               /* init BVHOverlapData */
                data[j]->overlap = (BVHTreeOverlap *)malloc(sizeof(BVHTreeOverlap) * MAX2(tree1->totleaf, tree2->totleaf));
                data[j]->tree1 = tree1;
                data[j]->tree2 = tree2;
@@ -1128,13 +1123,13 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int
        return overlap;
 }
 
-//Determines the nearest point of the given node BV. Returns the squared distance to that point.
+/* Determines the nearest point of the given node BV. Returns the squared distance to that point. */
 static float calc_nearest_point(const float proj[3], BVHNode *node, float *nearest)
 {
        int i;
        const float *bv = node->bv;
 
-       //nearest on AABB hull
+       /* nearest on AABB hull */
        for (i = 0; i != 3; i++, bv += 2) {
                if (bv[0] > proj[i])
                        nearest[i] = bv[0];
@@ -1145,7 +1140,7 @@ static float calc_nearest_point(const float proj[3], BVHNode *node, float *neare
        }
 
 #if 0
-       //nearest on a general hull
+       /* nearest on a general hull */
        copy_v3_v3(nearest, data->co);
        for (i = data->tree->start_axis; i != data->tree->stop_axis; i++, bv += 2)
        {
@@ -1172,9 +1167,7 @@ typedef struct NodeDistance {
 
 } NodeDistance;
 
-#define NodeDistance_priority(a, b) ( (a).dist < (b).dist)
-
-// TODO: use a priority queue to reduce the number of nodes looked on
+/* TODO: use a priority queue to reduce the number of nodes looked on */
 static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node)
 {
        if (node->totnode == 0) {
@@ -1186,7 +1179,7 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node)
                }
        }
        else {
-               //Better heuristic to pick the closest node to dive on
+               /* Better heuristic to pick the closest node to dive on */
                int i;
                float nearest[3];
 
@@ -1216,20 +1209,25 @@ static void dfs_find_nearest_begin(BVHNearestData *data, BVHNode *node)
 
 
 #if 0
+
+#define DEFAULT_FIND_NEAREST_HEAP_SIZE 1024
+
+#define NodeDistance_priority(a, b) ( (a).dist < (b).dist)
+
 static void NodeDistance_push_heap(NodeDistance *heap, int heap_size)
 PUSH_HEAP_BODY(NodeDistance, NodeDistance_priority, heap, heap_size)
 
 static void NodeDistance_pop_heap(NodeDistance *heap, int heap_size)
 POP_HEAP_BODY(NodeDistance, NodeDistance_priority, heap, heap_size)
 
-//NN function that uses an heap.. this functions leads to an optimal number of min-distance
-//but for normal tri-faces and BV 6-dop.. a simple dfs with local heuristics (as implemented
-//in source/blender/blenkernel/intern/shrinkwrap.c) works faster.
-//
-//It may make sense to use this function if the callback queries are very slow.. or if its impossible
-//to get a nice heuristic
-//
-//this function uses "malloc/free" instead of the MEM_* because it intends to be openmp safe
+/NN function that uses an heap.. this functions leads to an optimal number of min-distance
+ * but for normal tri-faces and BV 6-dop.. a simple dfs with local heuristics (as implemented
+ * in source/blender/blenkernel/intern/shrinkwrap.c) works faster.
+ *
+ * It may make sense to use this function if the callback queries are very slow.. or if its impossible
+ * to get a nice heuristic
+ *
+ * this function uses "malloc/free" instead of the MEM_* because it intends to be openmp safe */
 static void bfs_find_nearest(BVHNearestData *data, BVHNode *node)
 {
        int i;
@@ -1261,7 +1259,7 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node)
                                dfs_find_nearest_dfs(data, child);
                        }
                        else {
-                               //adjust heap size
+                               /* adjust heap size */
                                if ((heap_size >= max_heap_size) &&
                                    ADJUST_MEMORY(default_heap, (void **)&heap, heap_size + 1, &max_heap_size, sizeof(heap[0])) == FALSE)
                                {
@@ -1308,7 +1306,7 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *n
        BVHNearestData data;
        BVHNode *root = tree->nodes[tree->totleaf];
 
-       //init data to search
+       /* init data to search */
        data.tree = tree;
        data.co = co;
 
@@ -1327,11 +1325,11 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *n
                data.nearest.dist = FLT_MAX;
        }
 
-       //dfs search
+       /* dfs search */
        if (root)
                dfs_find_nearest_begin(&data, root);
 
-       //copy back results
+       /* copy back results */
        if (nearest) {
                memcpy(nearest, &data.nearest, sizeof(*nearest));
        }
@@ -1347,8 +1345,8 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *n
  */
 
 
-//Determines the distance that the ray must travel to hit the bounding volume of the given node
-static float ray_nearest_hit(BVHRayCastData *data, float *bv)
+/* Determines the distance that the ray must travel to hit the bounding volume of the given node */
+static float ray_nearest_hit(BVHRayCastData *data, const float bv[6])
 {
        int i;
 
@@ -1356,7 +1354,7 @@ static float ray_nearest_hit(BVHRayCastData *data, float *bv)
 
        for (i = 0; i != 3; i++, bv += 2) {
                if (data->ray_dot_axis[i] == 0.0f) {
-                       //axis aligned ray
+                       /* axis aligned ray */
                        if (data->ray.origin[i] < bv[0] - data->ray.radius ||
                            data->ray.origin[i] > bv[1] + data->ray.radius)
                        {
@@ -1382,11 +1380,11 @@ static float ray_nearest_hit(BVHRayCastData *data, float *bv)
        return low;
 }
 
-//Determines the distance that the ray must travel to hit the bounding volume of the given node
-//Based on Tactical Optimization of Ray/Box Intersection, by Graham Fyffe
-//[http://tog.acm.org/resources/RTNews/html/rtnv21n1.html#art9]
-//
-//TODO this doens't has data->ray.radius in consideration
+/Determines the distance that the ray must travel to hit the bounding volume of the given node
+ * Based on Tactical Optimization of Ray/Box Intersection, by Graham Fyffe
+ * [http://tog.acm.org/resources/RTNews/html/rtnv21n1.html#art9]
+ *
+ * TODO this doens't has data->ray.radius in consideration */
 static float fast_ray_nearest_hit(const BVHRayCastData *data, const BVHNode *node)
 {
        const float *bv = node->bv;
@@ -1413,8 +1411,8 @@ static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
 {
        int i;
 
-       //ray-bv is really fast.. and simple tests revealed its worth to test it
-       //before calling the ray-primitive functions
+       /ray-bv is really fast.. and simple tests revealed its worth to test it
+        * before calling the ray-primitive functions */
        /* XXX: temporary solution for particles until fast_ray_nearest_hit supports ray.radius */
        float dist = (data->ray.radius > 0.0f) ? ray_nearest_hit(data, node->bv) : fast_ray_nearest_hit(data, node);
        if (dist >= data->hit.dist) return;
@@ -1430,7 +1428,7 @@ static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
                }
        }
        else {
-               //pick loop direction to dive into the tree (based on ray direction and split axis)
+               /* pick loop direction to dive into the tree (based on ray direction and split axis) */
                if (data->ray_dot_axis[(int)node->main_axis] > 0.0f) {
                        for (i = 0; i != node->totnode; i++) {
                                dfs_raycast(data, node->children[i]);
@@ -1471,7 +1469,7 @@ static void iterative_raycast(BVHRayCastData *data, BVHNode *node)
                }
                else {
                        node = node->children[0];
-               }       
+               }
        }
 }
 #endif
@@ -1526,14 +1524,14 @@ int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], f
        return data.hit.index;
 }
 
-float BLI_bvhtree_bb_raycast(float *bv, const float light_start[3], const float light_end[3], float pos[3])
+float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], const float light_end[3], float pos[3])
 {
        BVHRayCastData data;
        float dist = 0.0;
 
        data.hit.dist = FLT_MAX;
        
-       // get light direction
+       /* get light direction */
        data.ray.direction[0] = light_end[0] - light_start[0];
        data.ray.direction[1] = light_end[1] - light_start[1];
        data.ray.direction[2] = light_end[2] - light_start[2];
@@ -1565,7 +1563,7 @@ float BLI_bvhtree_bb_raycast(float *bv, const float light_start[3], const float
 typedef struct RangeQueryData {
        BVHTree *tree;
        const float *center;
-       float radius;           //squared radius
+       float radius;  /* squared radius */
 
        int hits;
 
@@ -1580,7 +1578,7 @@ static void dfs_range_query(RangeQueryData *data, BVHNode *node)
 {
        if (node->totnode == 0) {
 #if 0   /*UNUSED*/
-               //Calculate the node min-coords (if the node was a point then this is the point coordinates)
+               /* Calculate the node min-coords (if the node was a point then this is the point coordinates) */
                float co[3];
                co[0] = node->bv[0];
                co[1] = node->bv[2];
@@ -1593,7 +1591,7 @@ static void dfs_range_query(RangeQueryData *data, BVHNode *node)
                        float nearest[3];
                        float dist = calc_nearest_point(data->center, node->children[i], nearest);
                        if (dist < data->radius) {
-                               //Its a leaf.. call the callback
+                               /* Its a leaf.. call the callback */
                                if (node->children[i]->totnode == 0) {
                                        data->hits++;
                                        data->callback(data->userdata, node->children[i]->index, dist);