Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/blenlib/intern/BLI_kdtree.c
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenlib/intern/BLI_kdtree.c')
-rw-r--r--source/blender/blenlib/intern/BLI_kdtree.c162
1 files changed, 81 insertions, 81 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c
index 6db21ec14a6..388c61ec9dd 100644
--- a/source/blender/blenlib/intern/BLI_kdtree.c
+++ b/source/blender/blenlib/intern/BLI_kdtree.c
@@ -67,7 +67,7 @@ KDTree *BLI_kdtree_new(int maxsize)
void BLI_kdtree_free(KDTree *tree)
{
- if(tree) {
+ if (tree) {
MEM_freeN(tree->nodes);
MEM_freeN(tree);
}
@@ -79,7 +79,7 @@ void BLI_kdtree_insert(KDTree *tree, int index, float *co, float *nor)
node->index= index;
copy_v3_v3(node->co, co);
- if(nor) copy_v3_v3(node->nor, nor);
+ if (nor) copy_v3_v3(node->nor, nor);
}
static KDTreeNode *kdtree_balance(KDTreeNode *nodes, int totnode, int axis)
@@ -88,9 +88,9 @@ static KDTreeNode *kdtree_balance(KDTreeNode *nodes, int totnode, int axis)
float co;
int left, right, median, i, j;
- if(totnode <= 0)
+ if (totnode <= 0)
return NULL;
- else if(totnode == 1)
+ else if (totnode == 1)
return nodes;
/* quicksort style sorting around median */
@@ -98,23 +98,23 @@ static KDTreeNode *kdtree_balance(KDTreeNode *nodes, int totnode, int axis)
right= totnode-1;
median= totnode/2;
- while(right > left) {
+ while (right > left) {
co= nodes[right].co[axis];
i= left-1;
j= right;
- while(1) {
- while(nodes[++i].co[axis] < co);
- while(nodes[--j].co[axis] > co && j>left);
+ while (1) {
+ while (nodes[++i].co[axis] < co);
+ while (nodes[--j].co[axis] > co && j>left);
- if(i >= j) break;
+ if (i >= j) break;
SWAP(KDTreeNode, nodes[i], nodes[j]);
}
SWAP(KDTreeNode, nodes[i], nodes[right]);
- if(i >= median)
+ if (i >= median)
right= i-1;
- if(i <= median)
+ if (i <= median)
left= i+1;
}
@@ -145,7 +145,7 @@ static float squared_distance(const float v2[3], const float v1[3], float *UNUSE
//if(n1 && n2 && (dot_v3v3(n1, n2) < 0.0f))
/* can someone explain why this is done?*/
- if(n2 && (dot_v3v3(d, n2) < 0.0f)) {
+ if (n2 && (dot_v3v3(d, n2) < 0.0f)) {
dist *= 10.0f;
}
@@ -159,7 +159,7 @@ int BLI_kdtree_find_nearest(KDTree *tree, float *co, float *nor, KDTreeNearest *
float min_dist, cur_dist;
int totstack, cur=0;
- if(!tree->root)
+ if (!tree->root)
return -1;
stack= defaultstack;
@@ -169,71 +169,71 @@ int BLI_kdtree_find_nearest(KDTree *tree, float *co, float *nor, KDTreeNearest *
min_node= root;
min_dist= squared_distance(root->co,co,root->nor,nor);
- if(co[root->d] < root->co[root->d]) {
- if(root->right)
+ if (co[root->d] < root->co[root->d]) {
+ if (root->right)
stack[cur++]=root->right;
- if(root->left)
+ if (root->left)
stack[cur++]=root->left;
}
else {
- if(root->left)
+ if (root->left)
stack[cur++]=root->left;
- if(root->right)
+ if (root->right)
stack[cur++]=root->right;
}
- while(cur--) {
+ while (cur--) {
node=stack[cur];
cur_dist = node->co[node->d] - co[node->d];
- if(cur_dist<0.0f) {
+ if (cur_dist<0.0f) {
cur_dist= -cur_dist*cur_dist;
- if(-cur_dist<min_dist) {
+ if (-cur_dist<min_dist) {
cur_dist=squared_distance(node->co,co,node->nor,nor);
- if(cur_dist<min_dist) {
+ if (cur_dist<min_dist) {
min_dist=cur_dist;
min_node=node;
}
- if(node->left)
+ if (node->left)
stack[cur++]=node->left;
}
- if(node->right)
+ if (node->right)
stack[cur++]=node->right;
}
- else{
+ else {
cur_dist= cur_dist*cur_dist;
- if(cur_dist<min_dist) {
+ if (cur_dist<min_dist) {
cur_dist=squared_distance(node->co,co,node->nor,nor);
- if(cur_dist<min_dist) {
+ if (cur_dist<min_dist) {
min_dist=cur_dist;
min_node=node;
}
- if(node->right)
+ if (node->right)
stack[cur++]=node->right;
}
- if(node->left)
+ if (node->left)
stack[cur++]=node->left;
}
- if(cur+3 > totstack) {
+ if (cur+3 > totstack) {
KDTreeNode **temp=MEM_callocN((totstack+100)*sizeof(KDTreeNode*), "psys_treestack");
memcpy(temp,stack,totstack*sizeof(KDTreeNode*));
- if(stack != defaultstack)
+ if (stack != defaultstack)
MEM_freeN(stack);
stack=temp;
totstack+=100;
}
}
- if(nearest) {
+ if (nearest) {
nearest->index= min_node->index;
nearest->dist= sqrt(min_dist);
copy_v3_v3(nearest->co, min_node->co);
}
- if(stack != defaultstack)
+ if (stack != defaultstack)
MEM_freeN(stack);
return min_node->index;
@@ -243,10 +243,10 @@ static void add_nearest(KDTreeNearest *ptn, int *found, int n, int index, float
{
int i;
- if(*found<n) (*found)++;
+ if (*found<n) (*found)++;
- for(i=*found-1; i>0; i--) {
- if(dist >= ptn[i-1].dist)
+ for (i=*found-1; i>0; i--) {
+ if (dist >= ptn[i-1].dist)
break;
else
ptn[i]= ptn[i-1];
@@ -265,7 +265,7 @@ int BLI_kdtree_find_n_nearest(KDTree *tree, int n, float *co, float *nor, KDTree
float cur_dist;
int i, totstack, cur=0, found=0;
- if(!tree->root)
+ if (!tree->root)
return 0;
stack= defaultstack;
@@ -276,67 +276,67 @@ int BLI_kdtree_find_n_nearest(KDTree *tree, int n, float *co, float *nor, KDTree
cur_dist= squared_distance(root->co,co,root->nor,nor);
add_nearest(nearest,&found,n,root->index,cur_dist,root->co);
- if(co[root->d] < root->co[root->d]) {
- if(root->right)
+ if (co[root->d] < root->co[root->d]) {
+ if (root->right)
stack[cur++]=root->right;
- if(root->left)
+ if (root->left)
stack[cur++]=root->left;
}
else {
- if(root->left)
+ if (root->left)
stack[cur++]=root->left;
- if(root->right)
+ if (root->right)
stack[cur++]=root->right;
}
- while(cur--) {
+ while (cur--) {
node=stack[cur];
cur_dist = node->co[node->d] - co[node->d];
- if(cur_dist<0.0f) {
+ if (cur_dist<0.0f) {
cur_dist= -cur_dist*cur_dist;
- if(found<n || -cur_dist<nearest[found-1].dist) {
+ if (found<n || -cur_dist<nearest[found-1].dist) {
cur_dist=squared_distance(node->co,co,node->nor,nor);
- if(found<n || cur_dist<nearest[found-1].dist)
+ if (found<n || cur_dist<nearest[found-1].dist)
add_nearest(nearest,&found,n,node->index,cur_dist,node->co);
- if(node->left)
+ if (node->left)
stack[cur++]=node->left;
}
- if(node->right)
+ if (node->right)
stack[cur++]=node->right;
}
- else{
+ else {
cur_dist= cur_dist*cur_dist;
- if(found<n || cur_dist<nearest[found-1].dist) {
+ if (found<n || cur_dist<nearest[found-1].dist) {
cur_dist=squared_distance(node->co,co,node->nor,nor);
- if(found<n || cur_dist<nearest[found-1].dist)
+ if (found<n || cur_dist<nearest[found-1].dist)
add_nearest(nearest,&found,n,node->index,cur_dist,node->co);
- if(node->right)
+ if (node->right)
stack[cur++]=node->right;
}
- if(node->left)
+ if (node->left)
stack[cur++]=node->left;
}
- if(cur+3 > totstack) {
+ if (cur+3 > totstack) {
KDTreeNode **temp=MEM_callocN((totstack+100)*sizeof(KDTreeNode*), "psys_treestack");
memcpy(temp,stack,totstack*sizeof(KDTreeNode*));
- if(stack != defaultstack)
+ if (stack != defaultstack)
MEM_freeN(stack);
stack=temp;
totstack+=100;
}
}
- for(i=0; i<found; i++)
+ for (i=0; i<found; i++)
nearest[i].dist= sqrt(nearest[i].dist);
- if(stack != defaultstack)
+ if (stack != defaultstack)
MEM_freeN(stack);
return found;
@@ -347,9 +347,9 @@ static int range_compare(const void * a, const void * b)
const KDTreeNearest *kda = a;
const KDTreeNearest *kdb = b;
- if(kda->dist < kdb->dist)
+ if (kda->dist < kdb->dist)
return -1;
- else if(kda->dist > kdb->dist)
+ else if (kda->dist > kdb->dist)
return 1;
else
return 0;
@@ -358,10 +358,10 @@ static void add_in_range(KDTreeNearest **ptn, int found, int *totfoundstack, int
{
KDTreeNearest *to;
- if(found+1 > *totfoundstack) {
+ if (found+1 > *totfoundstack) {
KDTreeNearest *temp=MEM_callocN((*totfoundstack+50)*sizeof(KDTreeNode), "psys_treefoundstack");
memcpy(temp, *ptn, *totfoundstack * sizeof(KDTreeNearest));
- if(*ptn)
+ if (*ptn)
MEM_freeN(*ptn);
*ptn = temp;
*totfoundstack+=50;
@@ -381,7 +381,7 @@ int BLI_kdtree_range_search(KDTree *tree, float range, float *co, float *nor, KD
float range2 = range*range, dist2;
int totstack, cur=0, found=0, totfoundstack=0;
- if(!tree || !tree->root)
+ if (!tree || !tree->root)
return 0;
stack= defaultstack;
@@ -389,61 +389,61 @@ int BLI_kdtree_range_search(KDTree *tree, float range, float *co, float *nor, KD
root= tree->root;
- if(co[root->d] + range < root->co[root->d]) {
- if(root->left)
+ if (co[root->d] + range < root->co[root->d]) {
+ if (root->left)
stack[cur++]=root->left;
}
- else if(co[root->d] - range > root->co[root->d]) {
- if(root->right)
+ else if (co[root->d] - range > root->co[root->d]) {
+ if (root->right)
stack[cur++]=root->right;
}
else {
dist2 = squared_distance(root->co, co, root->nor, nor);
- if(dist2 <= range2)
+ if (dist2 <= range2)
add_in_range(&foundstack, found++, &totfoundstack, root->index, dist2, root->co);
- if(root->left)
+ if (root->left)
stack[cur++]=root->left;
- if(root->right)
+ if (root->right)
stack[cur++]=root->right;
}
- while(cur--) {
+ while (cur--) {
node=stack[cur];
- if(co[node->d] + range < node->co[node->d]) {
- if(node->left)
+ if (co[node->d] + range < node->co[node->d]) {
+ if (node->left)
stack[cur++]=node->left;
}
- else if(co[node->d] - range > node->co[node->d]) {
- if(node->right)
+ else if (co[node->d] - range > node->co[node->d]) {
+ if (node->right)
stack[cur++]=node->right;
}
else {
dist2 = squared_distance(node->co, co, node->nor, nor);
- if(dist2 <= range2)
+ if (dist2 <= range2)
add_in_range(&foundstack, found++, &totfoundstack, node->index, dist2, node->co);
- if(node->left)
+ if (node->left)
stack[cur++]=node->left;
- if(node->right)
+ if (node->right)
stack[cur++]=node->right;
}
- if(cur+3 > totstack) {
+ if (cur+3 > totstack) {
KDTreeNode **temp=MEM_callocN((totstack+100)*sizeof(KDTreeNode*), "psys_treestack");
memcpy(temp,stack,totstack*sizeof(KDTreeNode*));
- if(stack != defaultstack)
+ if (stack != defaultstack)
MEM_freeN(stack);
stack=temp;
totstack+=100;
}
}
- if(stack != defaultstack)
+ if (stack != defaultstack)
MEM_freeN(stack);
- if(found)
+ if (found)
qsort(foundstack, found, sizeof(KDTreeNearest), range_compare);
*nearest = foundstack;
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-29 03:48:49 +0300