← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

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

  • Committer: Package Import Robot
  • Author(s): Matteo F. Vescovi
  • Date: 2012-07-23 08:54:18 UTC
  • mfrom: (14.2.16 sid)
  • mto: (14.2.19 sid)
  • mto: This revision was merged to the branch mainline in revision 42.
  • Revision ID: package-import@ubuntu.com-20120723085418-9foz30v6afaf5ffs
Tags: 2.63a-2
http://bugs.debian.org/658075
* debian/: Cycles support added (Closes: #658075)
  For now, this top feature has been enabled only
  on [any-amd64 any-i386] architectures because
  of OpenImageIO failing on all others
* debian/: scripts installation path changed
  from /usr/lib to /usr/share:
  + debian/patches/: patchset re-worked for path changing
  + debian/control: "Breaks" field added on yafaray-exporter

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/blenlib/intern/BLI_kdtree.c
1
 
/**
2
 
 * $Id: BLI_kdtree.c 27629 2010-03-20 18:52:03Z campbellbarton $
3
 
 *
 
1
/*
4
2
 * ***** BEGIN GPL LICENSE BLOCK *****
5
3
 *
6
4
 * This program is free software; you can redistribute it and/or
28
26
 * ***** END GPL LICENSE BLOCK *****
29
27
 */
30
28
 
 
29
/** \file blender/blenlib/intern/BLI_kdtree.c
 
30
 *  \ingroup bli
 
31
 */
 
32
 
 
33
 
31
34
 
32
35
#include "MEM_guardedalloc.h"
33
36
 
64
67
 
65
68
void BLI_kdtree_free(KDTree *tree)
66
69
{
67
 
        if(tree) {
 
70
        if (tree) {
68
71
                MEM_freeN(tree->nodes);
69
72
                MEM_freeN(tree);
70
73
        }
76
79
 
77
80
        node->index= index;
78
81
        copy_v3_v3(node->co, co);
79
 
        if(nor) copy_v3_v3(node->nor, nor);
 
82
        if (nor) copy_v3_v3(node->nor, nor);
80
83
}
81
84
 
82
85
static KDTreeNode *kdtree_balance(KDTreeNode *nodes, int totnode, int axis)
85
88
        float co;
86
89
        int left, right, median, i, j;
87
90
 
88
 
        if(totnode <= 0)
 
91
        if (totnode <= 0)
89
92
                return NULL;
90
 
        else if(totnode == 1)
 
93
        else if (totnode == 1)
91
94
                return nodes;
92
95
        
93
96
        /* quicksort style sorting around median */
95
98
        right= totnode-1;
96
99
        median= totnode/2;
97
100
 
98
 
        while(right > left) {
 
101
        while (right > left) {
99
102
                co= nodes[right].co[axis];
100
103
                i= left-1;
101
104
                j= right;
102
105
 
103
 
                while(1) {
104
 
                        while(nodes[++i].co[axis] < co);
105
 
                        while(nodes[--j].co[axis] > co && j>left);
 
106
                while (1) {
 
107
                        while (nodes[++i].co[axis] < co);
 
108
                        while (nodes[--j].co[axis] > co && j>left);
106
109
 
107
 
                        if(i >= j) break;
 
110
                        if (i >= j) break;
108
111
                        SWAP(KDTreeNode, nodes[i], nodes[j]);
109
112
                }
110
113
 
111
114
                SWAP(KDTreeNode, nodes[i], nodes[right]);
112
 
                if(i >= median)
 
115
                if (i >= median)
113
116
                        right= i-1;
114
 
                if(i <= median)
 
117
                if (i <= median)
115
118
                        left= i+1;
116
119
        }
117
120
 
129
132
        tree->root= kdtree_balance(tree->nodes, tree->totnode, 0);
130
133
}
131
134
 
132
 
static float squared_distance(float *v2, float *v1, float *n1, float *n2)
 
135
static float squared_distance(const float v2[3], const float v1[3], float *UNUSED(n1), float *n2)
133
136
{
134
137
        float d[3], dist;
135
138
 
137
140
        d[1]= v2[1]-v1[1];
138
141
        d[2]= v2[2]-v1[2];
139
142
 
140
 
        dist= d[0]*d[0] + d[1]*d[1] + d[2]*d[2];
141
 
 
142
 
        //if(n1 && n2 && n1[0]*n2[0] + n1[1]*n2[1] + n1[2]*n2[2] < 0.0f)
143
 
        if(n2 && d[0]*n2[0] + d[1]*n2[1] + d[2]*n2[2] < 0.0f)
 
143
        dist = dot_v3v3(d, d);
 
144
 
 
145
        //if (n1 && n2 && (dot_v3v3(n1, n2) < 0.0f))
 
146
 
 
147
        /* can someone explain why this is done?*/
 
148
        if (n2 && (dot_v3v3(d, n2) < 0.0f)) {
144
149
                dist *= 10.0f;
 
150
        }
145
151
 
146
152
        return dist;
147
153
}
153
159
        float min_dist, cur_dist;
154
160
        int totstack, cur=0;
155
161
 
156
 
        if(!tree->root)
 
162
        if (!tree->root)
157
163
                return -1;
158
164
 
159
165
        stack= defaultstack;
163
169
        min_node= root;
164
170
        min_dist= squared_distance(root->co,co,root->nor,nor);
165
171
 
166
 
        if(co[root->d] < root->co[root->d]) {
167
 
                if(root->right)
 
172
        if (co[root->d] < root->co[root->d]) {
 
173
                if (root->right)
168
174
                        stack[cur++]=root->right;
169
 
                if(root->left)
 
175
                if (root->left)
170
176
                        stack[cur++]=root->left;
171
177
        }
172
178
        else {
173
 
                if(root->left)
 
179
                if (root->left)
174
180
                        stack[cur++]=root->left;
175
 
                if(root->right)
 
181
                if (root->right)
176
182
                        stack[cur++]=root->right;
177
183
        }
178
184
        
179
 
        while(cur--){
 
185
        while (cur--) {
180
186
                node=stack[cur];
181
187
 
182
188
                cur_dist = node->co[node->d] - co[node->d];
183
189
 
184
 
                if(cur_dist<0.0){
 
190
                if (cur_dist<0.0f) {
185
191
                        cur_dist= -cur_dist*cur_dist;
186
192
 
187
 
                        if(-cur_dist<min_dist){
 
193
                        if (-cur_dist<min_dist) {
188
194
                                cur_dist=squared_distance(node->co,co,node->nor,nor);
189
 
                                if(cur_dist<min_dist){
 
195
                                if (cur_dist<min_dist) {
190
196
                                        min_dist=cur_dist;
191
197
                                        min_node=node;
192
198
                                }
193
 
                                if(node->left)
 
199
                                if (node->left)
194
200
                                        stack[cur++]=node->left;
195
201
                        }
196
 
                        if(node->right)
 
202
                        if (node->right)
197
203
                                stack[cur++]=node->right;
198
204
                }
199
 
                else{
 
205
                else {
200
206
                        cur_dist= cur_dist*cur_dist;
201
207
 
202
 
                        if(cur_dist<min_dist){
 
208
                        if (cur_dist<min_dist) {
203
209
                                cur_dist=squared_distance(node->co,co,node->nor,nor);
204
 
                                if(cur_dist<min_dist){
 
210
                                if (cur_dist<min_dist) {
205
211
                                        min_dist=cur_dist;
206
212
                                        min_node=node;
207
213
                                }
208
 
                                if(node->right)
 
214
                                if (node->right)
209
215
                                        stack[cur++]=node->right;
210
216
                        }
211
 
                        if(node->left)
 
217
                        if (node->left)
212
218
                                stack[cur++]=node->left;
213
219
                }
214
 
                if(cur+3 > totstack){
 
220
                if (cur+3 > totstack) {
215
221
                        KDTreeNode **temp=MEM_callocN((totstack+100)*sizeof(KDTreeNode*), "psys_treestack");
216
222
                        memcpy(temp,stack,totstack*sizeof(KDTreeNode*));
217
 
                        if(stack != defaultstack)
 
223
                        if (stack != defaultstack)
218
224
                                MEM_freeN(stack);
219
225
                        stack=temp;
220
226
                        totstack+=100;
221
227
                }
222
228
        }
223
229
 
224
 
        if(nearest) {
 
230
        if (nearest) {
225
231
                nearest->index= min_node->index;
226
232
                nearest->dist= sqrt(min_dist);
227
233
                copy_v3_v3(nearest->co, min_node->co);
228
234
        }
229
235
 
230
 
        if(stack != defaultstack)
 
236
        if (stack != defaultstack)
231
237
                MEM_freeN(stack);
232
238
 
233
239
        return min_node->index;
237
243
{
238
244
        int i;
239
245
 
240
 
        if(*found<n) (*found)++;
 
246
        if (*found<n) (*found)++;
241
247
 
242
 
        for(i=*found-1; i>0; i--) {
243
 
                if(dist >= ptn[i-1].dist)
 
248
        for (i=*found-1; i>0; i--) {
 
249
                if (dist >= ptn[i-1].dist)
244
250
                        break;
245
251
                else
246
252
                        ptn[i]= ptn[i-1];
254
260
/* finds the nearest n entries in tree to specified coordinates */
255
261
int     BLI_kdtree_find_n_nearest(KDTree *tree, int n, float *co, float *nor, KDTreeNearest *nearest)
256
262
{
257
 
        KDTreeNode *root, *node=0;
 
263
        KDTreeNode *root, *node= NULL;
258
264
        KDTreeNode **stack, *defaultstack[100];
259
265
        float cur_dist;
260
266
        int i, totstack, cur=0, found=0;
261
267
 
262
 
        if(!tree->root)
 
268
        if (!tree->root)
263
269
                return 0;
264
270
 
265
271
        stack= defaultstack;
270
276
        cur_dist= squared_distance(root->co,co,root->nor,nor);
271
277
        add_nearest(nearest,&found,n,root->index,cur_dist,root->co);
272
278
        
273
 
        if(co[root->d] < root->co[root->d]) {
274
 
                if(root->right)
 
279
        if (co[root->d] < root->co[root->d]) {
 
280
                if (root->right)
275
281
                        stack[cur++]=root->right;
276
 
                if(root->left)
 
282
                if (root->left)
277
283
                        stack[cur++]=root->left;
278
284
        }
279
285
        else {
280
 
                if(root->left)
 
286
                if (root->left)
281
287
                        stack[cur++]=root->left;
282
 
                if(root->right)
 
288
                if (root->right)
283
289
                        stack[cur++]=root->right;
284
290
        }
285
291
 
286
 
        while(cur--){
 
292
        while (cur--) {
287
293
                node=stack[cur];
288
294
 
289
295
                cur_dist = node->co[node->d] - co[node->d];
290
296
 
291
 
                if(cur_dist<0.0){
 
297
                if (cur_dist<0.0f) {
292
298
                        cur_dist= -cur_dist*cur_dist;
293
299
 
294
 
                        if(found<n || -cur_dist<nearest[found-1].dist){
 
300
                        if (found<n || -cur_dist<nearest[found-1].dist) {
295
301
                                cur_dist=squared_distance(node->co,co,node->nor,nor);
296
302
 
297
 
                                if(found<n || cur_dist<nearest[found-1].dist)
 
303
                                if (found<n || cur_dist<nearest[found-1].dist)
298
304
                                        add_nearest(nearest,&found,n,node->index,cur_dist,node->co);
299
305
 
300
 
                                if(node->left)
 
306
                                if (node->left)
301
307
                                        stack[cur++]=node->left;
302
308
                        }
303
 
                        if(node->right)
 
309
                        if (node->right)
304
310
                                stack[cur++]=node->right;
305
311
                }
306
 
                else{
 
312
                else {
307
313
                        cur_dist= cur_dist*cur_dist;
308
314
 
309
 
                        if(found<n || cur_dist<nearest[found-1].dist){
 
315
                        if (found<n || cur_dist<nearest[found-1].dist) {
310
316
                                cur_dist=squared_distance(node->co,co,node->nor,nor);
311
 
                                if(found<n || cur_dist<nearest[found-1].dist)
 
317
                                if (found<n || cur_dist<nearest[found-1].dist)
312
318
                                        add_nearest(nearest,&found,n,node->index,cur_dist,node->co);
313
319
 
314
 
                                if(node->right)
 
320
                                if (node->right)
315
321
                                        stack[cur++]=node->right;
316
322
                        }
317
 
                        if(node->left)
 
323
                        if (node->left)
318
324
                                stack[cur++]=node->left;
319
325
                }
320
 
                if(cur+3 > totstack){
 
326
                if (cur+3 > totstack) {
321
327
                        KDTreeNode **temp=MEM_callocN((totstack+100)*sizeof(KDTreeNode*), "psys_treestack");
322
328
                        memcpy(temp,stack,totstack*sizeof(KDTreeNode*));
323
 
                        if(stack != defaultstack)
 
329
                        if (stack != defaultstack)
324
330
                                MEM_freeN(stack);
325
331
                        stack=temp;
326
332
                        totstack+=100;
327
333
                }
328
334
        }
329
335
 
330
 
        for(i=0; i<found; i++)
 
336
        for (i=0; i<found; i++)
331
337
                nearest[i].dist= sqrt(nearest[i].dist);
332
338
 
333
 
        if(stack != defaultstack)
 
339
        if (stack != defaultstack)
334
340
                MEM_freeN(stack);
335
341
 
336
342
        return found;
341
347
        const KDTreeNearest *kda = a;
342
348
        const KDTreeNearest *kdb = b;
343
349
 
344
 
        if(kda->dist < kdb->dist)
 
350
        if (kda->dist < kdb->dist)
345
351
                return -1;
346
 
        else if(kda->dist > kdb->dist)
 
352
        else if (kda->dist > kdb->dist)
347
353
                return 1;
348
354
        else
349
355
                return 0;
352
358
{
353
359
        KDTreeNearest *to;
354
360
 
355
 
        if(found+1 > *totfoundstack) {
 
361
        if (found+1 > *totfoundstack) {
356
362
                KDTreeNearest *temp=MEM_callocN((*totfoundstack+50)*sizeof(KDTreeNode), "psys_treefoundstack");
357
363
                memcpy(temp, *ptn, *totfoundstack * sizeof(KDTreeNearest));
358
 
                if(*ptn)
 
364
                if (*ptn)
359
365
                        MEM_freeN(*ptn);
360
366
                *ptn = temp;
361
367
                *totfoundstack+=50;
369
375
}
370
376
int BLI_kdtree_range_search(KDTree *tree, float range, float *co, float *nor, KDTreeNearest **nearest)
371
377
{
372
 
        KDTreeNode *root, *node=0;
 
378
        KDTreeNode *root, *node= NULL;
373
379
        KDTreeNode **stack, *defaultstack[100];
374
380
        KDTreeNearest *foundstack=NULL;
375
381
        float range2 = range*range, dist2;
376
382
        int totstack, cur=0, found=0, totfoundstack=0;
377
383
 
378
 
        if(!tree || !tree->root)
 
384
        if (!tree || !tree->root)
379
385
                return 0;
380
386
 
381
387
        stack= defaultstack;
383
389
 
384
390
        root= tree->root;
385
391
 
386
 
        if(co[root->d] + range < root->co[root->d]) {
387
 
                if(root->left)
 
392
        if (co[root->d] + range < root->co[root->d]) {
 
393
                if (root->left)
388
394
                        stack[cur++]=root->left;
389
395
        }
390
 
        else if(co[root->d] - range > root->co[root->d]) {
391
 
                if(root->right)
 
396
        else if (co[root->d] - range > root->co[root->d]) {
 
397
                if (root->right)
392
398
                        stack[cur++]=root->right;
393
399
        }
394
400
        else {
395
401
                dist2 = squared_distance(root->co, co, root->nor, nor);
396
 
                if(dist2  <= range2)
 
402
                if (dist2  <= range2)
397
403
                        add_in_range(&foundstack, found++, &totfoundstack, root->index, dist2, root->co);
398
404
 
399
 
                if(root->left)
 
405
                if (root->left)
400
406
                        stack[cur++]=root->left;
401
 
                if(root->right)
 
407
                if (root->right)
402
408
                        stack[cur++]=root->right;
403
409
        }
404
410
 
405
 
        while(cur--) {
 
411
        while (cur--) {
406
412
                node=stack[cur];
407
413
 
408
 
                if(co[node->d] + range < node->co[node->d]) {
409
 
                        if(node->left)
 
414
                if (co[node->d] + range < node->co[node->d]) {
 
415
                        if (node->left)
410
416
                                stack[cur++]=node->left;
411
417
                }
412
 
                else if(co[node->d] - range > node->co[node->d]) {
413
 
                        if(node->right)
 
418
                else if (co[node->d] - range > node->co[node->d]) {
 
419
                        if (node->right)
414
420
                                stack[cur++]=node->right;
415
421
                }
416
422
                else {
417
423
                        dist2 = squared_distance(node->co, co, node->nor, nor);
418
 
                        if(dist2 <= range2)
 
424
                        if (dist2 <= range2)
419
425
                                add_in_range(&foundstack, found++, &totfoundstack, node->index, dist2, node->co);
420
426
 
421
 
                        if(node->left)
 
427
                        if (node->left)
422
428
                                stack[cur++]=node->left;
423
 
                        if(node->right)
 
429
                        if (node->right)
424
430
                                stack[cur++]=node->right;
425
431
                }
426
432
 
427
 
                if(cur+3 > totstack){
 
433
                if (cur+3 > totstack) {
428
434
                        KDTreeNode **temp=MEM_callocN((totstack+100)*sizeof(KDTreeNode*), "psys_treestack");
429
435
                        memcpy(temp,stack,totstack*sizeof(KDTreeNode*));
430
 
                        if(stack != defaultstack)
 
436
                        if (stack != defaultstack)
431
437
                                MEM_freeN(stack);
432
438
                        stack=temp;
433
439
                        totstack+=100;
434
440
                }
435
441
        }
436
442
 
437
 
        if(stack != defaultstack)
 
443
        if (stack != defaultstack)
438
444
                MEM_freeN(stack);
439
445
 
440
 
        if(found)
 
446
        if (found)
441
447
                qsort(foundstack, found, sizeof(KDTreeNearest), range_compare);
442
448
 
443
449
        *nearest = foundstack;