← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to source/blender/blenkernel/intern/bvhutils.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/blenkernel/intern/bvhutils.c
1
 
/**
2
 
 *
3
 
 * $Id: bvhutils.c 27655 2010-03-22 09:30:00Z campbellbarton $
4
 
 *
 
1
/*
5
2
 * ***** BEGIN GPL LICENSE BLOCK *****
6
3
 *
7
4
 * This program is free software; you can redistribute it and/or
23
20
 *
24
21
 * The Original Code is: all of this file.
25
22
 *
26
 
 * Contributor(s): André Pinto.
 
23
 * Contributor(s): Andr Pinto.
27
24
 *
28
25
 * ***** END GPL LICENSE BLOCK *****
29
26
 */
 
27
 
 
28
/** \file blender/blenkernel/intern/bvhutils.c
 
29
 *  \ingroup bke
 
30
 */
 
31
 
30
32
#include <stdio.h>
31
33
#include <string.h>
32
34
#include <math.h>
34
36
 
35
37
#include "DNA_meshdata_types.h"
36
38
 
 
39
#include "BLI_utildefines.h"
 
40
#include "BLI_linklist.h"
 
41
 
37
42
#include "BKE_DerivedMesh.h"
38
 
#include "BKE_utildefines.h"
 
43
#include "BKE_tessmesh.h"
39
44
 
40
45
#include "BLI_math.h"
41
46
#include "MEM_guardedalloc.h"
42
47
 
43
48
/* Math stuff for ray casting on mesh faces and for nearest surface */
44
49
 
45
 
static float ray_tri_intersection(const BVHTreeRay *ray, const float m_dist, const float *v0, const float *v1, const float *v2)
 
50
float bvhtree_ray_tri_intersection(const BVHTreeRay *ray, const float UNUSED(m_dist), const float v0[3], const float v1[3], const float v2[3])
46
51
{
47
52
        float dist;
48
53
 
49
 
        if(isect_ray_tri_v3((float*)ray->origin, (float*)ray->direction, (float*)v0, (float*)v1, (float*)v2, &dist, NULL))
 
54
        if (isect_ray_tri_epsilon_v3(ray->origin, ray->direction, v0, v1, v2, &dist, NULL, FLT_EPSILON))
50
55
                return dist;
51
56
 
52
57
        return FLT_MAX;
53
58
}
54
59
 
55
 
static float sphereray_tri_intersection(const BVHTreeRay *ray, float radius, const float m_dist, const float *v0, const float *v1, const float *v2)
 
60
static float sphereray_tri_intersection(const BVHTreeRay *ray, float radius, const float m_dist, const float v0[3], const float v1[3], const float v2[3])
56
61
{
57
62
        
58
63
        float idist;
59
64
        float p1[3];
60
65
        float plane_normal[3], hit_point[3];
61
66
 
62
 
        normal_tri_v3( plane_normal,(float*)v0, (float*)v1, (float*)v2);
 
67
        normal_tri_v3(plane_normal, v0, v1, v2);
63
68
 
64
 
        VECADDFAC( p1, ray->origin, ray->direction, m_dist);
65
 
        if(isect_sweeping_sphere_tri_v3((float*)ray->origin, p1, radius, (float*)v0, (float*)v1, (float*)v2, &idist, hit_point))
66
 
        {
 
69
        madd_v3_v3v3fl(p1, ray->origin, ray->direction, m_dist);
 
70
        if (isect_sweeping_sphere_tri_v3(ray->origin, p1, radius, v0, v1, v2, &idist, hit_point)) {
67
71
                return idist * m_dist;
68
72
        }
69
73
 
75
79
 * Function adapted from David Eberly's distance tools (LGPL)
76
80
 * http://www.geometrictools.com/LibFoundation/Distance/Distance.html
77
81
 */
78
 
static float nearest_point_in_tri_surface(const float *v0,const float *v1,const float *v2,const float *p, int *v, int *e, float *nearest )
 
82
float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const float v2[3], const float p[3], int *v, int *e, float nearest[3])
79
83
{
80
84
        float diff[3];
81
85
        float e0[3];
92
96
        float sqrDist;
93
97
        int lv = -1, le = -1;
94
98
        
95
 
        VECSUB(diff, v0, p);
96
 
        VECSUB(e0, v1, v0);
97
 
        VECSUB(e1, v2, v0);
 
99
        sub_v3_v3v3(diff, v0, p);
 
100
        sub_v3_v3v3(e0, v1, v0);
 
101
        sub_v3_v3v3(e1, v2, v0);
98
102
        
99
 
        A00 = INPR ( e0, e0 );
100
 
        A01 = INPR( e0, e1 );
101
 
        A11 = INPR ( e1, e1 );
102
 
        B0 = INPR( diff, e0 );
103
 
        B1 = INPR( diff, e1 );
104
 
        C = INPR( diff, diff );
 
103
        A00 = dot_v3v3(e0, e0);
 
104
        A01 = dot_v3v3(e0, e1 );
 
105
        A11 = dot_v3v3(e1, e1 );
 
106
        B0 = dot_v3v3(diff, e0 );
 
107
        B1 = dot_v3v3(diff, e1 );
 
108
        C = dot_v3v3(diff, diff );
105
109
        Det = fabs( A00 * A11 - A01 * A01 );
106
110
        S = A01 * B1 - A11 * B0;
107
111
        T = A01 * B0 - A00 * B1;
108
112
 
109
 
        if ( S + T <= Det )
110
 
        {
111
 
                if ( S < 0.0f )
112
 
                {
113
 
                        if ( T < 0.0f )  // Region 4
114
 
                        {
115
 
                                if ( B0 < 0.0f )
116
 
                                {
 
113
        if (S + T <= Det) {
 
114
                if (S < 0.0f) {
 
115
                        if (T < 0.0f) { /* Region 4 */
 
116
                                if (B0 < 0.0f) {
117
117
                                        T = 0.0f;
118
 
                                        if ( -B0 >= A00 )
119
 
                                        {
120
 
                                                S = (float)1.0;
 
118
                                        if (-B0 >= A00) {
 
119
                                                S = 1.0f;
121
120
                                                sqrDist = A00 + 2.0f * B0 + C;
122
121
                                                lv = 1;
123
122
                                        }
124
 
                                        else
125
 
                                        {
126
 
                                                if(fabs(A00) > FLT_EPSILON)
 
123
                                        else {
 
124
                                                if (fabsf(A00) > FLT_EPSILON)
127
125
                                                        S = -B0/A00;
128
126
                                                else
129
127
                                                        S = 0.0f;
131
129
                                                le = 0;
132
130
                                        }
133
131
                                }
134
 
                                else
135
 
                                {
 
132
                                else {
136
133
                                        S = 0.0f;
137
 
                                        if ( B1 >= 0.0f )
138
 
                                        {
 
134
                                        if (B1 >= 0.0f) {
139
135
                                                T = 0.0f;
140
136
                                                sqrDist = C;
141
137
                                                lv = 0;
142
138
                                        }
143
 
                                        else if ( -B1 >= A11 )
144
 
                                        {
 
139
                                        else if (-B1 >= A11) {
145
140
                                                T = 1.0f;
146
141
                                                sqrDist = A11 + 2.0f * B1 + C;
147
142
                                                lv = 2;
148
143
                                        }
149
 
                                        else
150
 
                                        {
151
 
                                                if(fabs(A11) > FLT_EPSILON)
 
144
                                        else {
 
145
                                                if (fabsf(A11) > FLT_EPSILON)
152
146
                                                        T = -B1 / A11;
153
147
                                                else
154
148
                                                        T = 0.0f;
157
151
                                        }
158
152
                                }
159
153
                        }
160
 
                        else  // Region 3
161
 
                        {
 
154
                        else { /* Region 3 */
162
155
                                S = 0.0f;
163
 
                                if ( B1 >= 0.0f )
164
 
                                {
 
156
                                if (B1 >= 0.0f) {
165
157
                                        T = 0.0f;
166
158
                                        sqrDist = C;
167
159
                                        lv = 0;
168
160
                                }
169
 
                                else if ( -B1 >= A11 )
170
 
                                {
 
161
                                else if (-B1 >= A11) {
171
162
                                        T = 1.0f;
172
163
                                        sqrDist = A11 + 2.0f * B1 + C;
173
164
                                        lv = 2;
174
165
                                }
175
 
                                else
176
 
                                {
177
 
                                        if(fabs(A11) > FLT_EPSILON)
 
166
                                else {
 
167
                                        if (fabsf(A11) > FLT_EPSILON)
178
168
                                                T = -B1 / A11;
179
169
                                        else
180
170
                                                T = 0.0;
183
173
                                }
184
174
                        }
185
175
                }
186
 
                else if ( T < 0.0f )  // Region 5
187
 
                {
 
176
                else if (T < 0.0f) { /* Region 5 */
188
177
                        T = 0.0f;
189
 
                        if ( B0 >= 0.0f )
190
 
                        {
 
178
                        if (B0 >= 0.0f) {
191
179
                                S = 0.0f;
192
180
                                sqrDist = C;
193
181
                                lv = 0;
194
182
                        }
195
 
                        else if ( -B0 >= A00 )
196
 
                        {
 
183
                        else if (-B0 >= A00) {
197
184
                                S = 1.0f;
198
185
                                sqrDist = A00 + 2.0f * B0 + C;
199
186
                                lv = 1;
200
187
                        }
201
 
                        else
202
 
                        {
203
 
                                if(fabs(A00) > FLT_EPSILON)
 
188
                        else {
 
189
                                if (fabsf(A00) > FLT_EPSILON)
204
190
                                        S = -B0 / A00;
205
191
                                else
206
192
                                        S = 0.0f;
208
194
                                le = 0;
209
195
                        }
210
196
                }
211
 
                else  // Region 0
212
 
                {
 
197
                else { /* Region 0 */
213
198
                        // Minimum at interior lv
214
199
                        float invDet;
215
 
                        if(fabs(Det) > FLT_EPSILON)
 
200
                        if (fabsf(Det) > FLT_EPSILON)
216
201
                                invDet = 1.0f / Det;
217
202
                        else
218
203
                                invDet = 0.0f;
219
204
                        S *= invDet;
220
205
                        T *= invDet;
221
206
                        sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0) +
222
 
                                        T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
 
207
                                  T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
223
208
                }
224
209
        }
225
 
        else
226
 
        {
 
210
        else {
227
211
                float tmp0, tmp1, numer, denom;
228
212
 
229
 
                if ( S < 0.0f )  // Region 2
230
 
                {
 
213
                if (S < 0.0f) { /* Region 2 */
231
214
                        tmp0 = A01 + B0;
232
215
                        tmp1 = A11 + B1;
233
 
                        if ( tmp1 > tmp0 )
234
 
                        {
 
216
                        if ( tmp1 > tmp0 ) {
235
217
                                numer = tmp1 - tmp0;
236
218
                                denom = A00 - 2.0f * A01 + A11;
237
 
                                if ( numer >= denom )
238
 
                                {
 
219
                                if ( numer >= denom ) {
239
220
                                        S = 1.0f;
240
221
                                        T = 0.0f;
241
222
                                        sqrDist = A00 + 2.0f * B0 + C;
242
223
                                        lv = 1;
243
224
                                }
244
 
                                else
245
 
                                {
246
 
                                        if(fabs(denom) > FLT_EPSILON)
 
225
                                else {
 
226
                                        if (fabsf(denom) > FLT_EPSILON)
247
227
                                                S = numer / denom;
248
228
                                        else
249
229
                                                S = 0.0f;
250
230
                                        T = 1.0f - S;
251
231
                                        sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) +
252
 
                                                        T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
 
232
                                                  T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
253
233
                                        le = 2;
254
234
                                }
255
235
                        }
256
 
                        else
257
 
                        {
 
236
                        else {
258
237
                                S = 0.0f;
259
 
                                if ( tmp1 <= 0.0f )
260
 
                                {
 
238
                                if ( tmp1 <= 0.0f ) {
261
239
                                        T = 1.0f;
262
240
                                        sqrDist = A11 + 2.0f * B1 + C;
263
241
                                        lv = 2;
264
242
                                }
265
 
                                else if ( B1 >= 0.0f )
266
 
                                {
 
243
                                else if (B1 >= 0.0f) {
267
244
                                        T = 0.0f;
268
245
                                        sqrDist = C;
269
246
                                        lv = 0;
270
247
                                }
271
 
                                else
272
 
                                {
273
 
                                        if(fabs(A11) > FLT_EPSILON)
 
248
                                else {
 
249
                                        if (fabsf(A11) > FLT_EPSILON)
274
250
                                                T = -B1 / A11;
275
251
                                        else
276
252
                                                T = 0.0f;
279
255
                                }
280
256
                        }
281
257
                }
282
 
                else if ( T < 0.0f )  // Region 6
283
 
                {
 
258
                else if (T < 0.0f) { /* Region 6 */
284
259
                        tmp0 = A01 + B1;
285
260
                        tmp1 = A00 + B0;
286
 
                        if ( tmp1 > tmp0 )
287
 
                        {
 
261
                        if ( tmp1 > tmp0 ) {
288
262
                                numer = tmp1 - tmp0;
289
263
                                denom = A00 - 2.0f * A01 + A11;
290
 
                                if ( numer >= denom )
291
 
                                {
 
264
                                if ( numer >= denom ) {
292
265
                                        T = 1.0f;
293
266
                                        S = 0.0f;
294
267
                                        sqrDist = A11 + 2.0f * B1 + C;
295
268
                                        lv = 2;
296
269
                                }
297
 
                                else
298
 
                                {
299
 
                                        if(fabs(denom) > FLT_EPSILON)
 
270
                                else {
 
271
                                        if (fabsf(denom) > FLT_EPSILON)
300
272
                                                T = numer / denom;
301
273
                                        else
302
274
                                                T = 0.0f;
303
275
                                        S = 1.0f - T;
304
276
                                        sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) +
305
 
                                                        T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
 
277
                                                  T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
306
278
                                        le = 2;
307
279
                                }
308
280
                        }
309
 
                        else
310
 
                        {
 
281
                        else {
311
282
                                T = 0.0f;
312
 
                                if ( tmp1 <= 0.0f )
313
 
                                {
 
283
                                if (tmp1 <= 0.0f) {
314
284
                                        S = 1.0f;
315
285
                                        sqrDist = A00 + 2.0f * B0 + C;
316
286
                                        lv = 1;
317
287
                                }
318
 
                                else if ( B0 >= 0.0f )
319
 
                                {
 
288
                                else if (B0 >= 0.0f) {
320
289
                                        S = 0.0f;
321
290
                                        sqrDist = C;
322
291
                                        lv = 0;
323
292
                                }
324
 
                                else
325
 
                                {
326
 
                                        if(fabs(A00) > FLT_EPSILON)
 
293
                                else {
 
294
                                        if (fabsf(A00) > FLT_EPSILON)
327
295
                                                S = -B0 / A00;
328
296
                                        else
329
297
                                                S = 0.0f;
332
300
                                }
333
301
                        }
334
302
                }
335
 
                else  // Region 1
336
 
                {
 
303
                else { /* Region 1 */
337
304
                        numer = A11 + B1 - A01 - B0;
338
 
                        if ( numer <= 0.0f )
339
 
                        {
 
305
                        if ( numer <= 0.0f ) {
340
306
                                S = 0.0f;
341
307
                                T = 1.0f;
342
308
                                sqrDist = A11 + 2.0f * B1 + C;
343
309
                                lv = 2;
344
310
                        }
345
 
                        else
346
 
                        {
 
311
                        else {
347
312
                                denom = A00 - 2.0f * A01 + A11;
348
 
                                if ( numer >= denom )
349
 
                                {
 
313
                                if ( numer >= denom ) {
350
314
                                        S = 1.0f;
351
315
                                        T = 0.0f;
352
316
                                        sqrDist = A00 + 2.0f * B0 + C;
353
317
                                        lv = 1;
354
318
                                }
355
 
                                else
356
 
                                {
357
 
                                        if(fabs(denom) > FLT_EPSILON)
 
319
                                else {
 
320
                                        if (fabsf(denom) > FLT_EPSILON)
358
321
                                                S = numer / denom;
359
322
                                        else
360
323
                                                S = 0.0f;
361
324
                                        T = 1.0f - S;
362
325
                                        sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) +
363
 
                                                        T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
 
326
                                                  T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
364
327
                                        le = 2;
365
328
                                }
366
329
                        }
373
336
        
374
337
        {
375
338
                float w[3], x[3], y[3], z[3];
376
 
                VECCOPY(w, v0);
377
 
                VECCOPY(x, e0);
 
339
                copy_v3_v3(w, v0);
 
340
                copy_v3_v3(x, e0);
378
341
                mul_v3_fl(x, S);
379
 
                VECCOPY(y, e1);
 
342
                copy_v3_v3(y, e1);
380
343
                mul_v3_fl(y, T);
381
 
                VECADD(z, w, x);
382
 
                VECADD(z, z, y);
383
 
                //VECSUB(d, p, z);
384
 
                VECCOPY(nearest, z);
 
344
                add_v3_v3v3(z, w, x);
 
345
                add_v3_v3v3(z, z, y);
 
346
                //sub_v3_v3v3(d, p, z);
 
347
                copy_v3_v3(nearest, z);
385
348
                // d = p - ( v0 + S * e0 + T * e1 );
386
349
        }
387
350
        *v = lv;
397
360
 
398
361
// Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_faces.
399
362
// userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
400
 
static void mesh_faces_nearest_point(void *userdata, int index, const float *co, BVHTreeNearest *nearest)
 
363
static void mesh_faces_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
401
364
{
402
365
        const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
403
366
        MVert *vert     = data->vert;
416
379
                int vertex, edge;
417
380
                
418
381
                dist = nearest_point_in_tri_surface(t0, t1, t2, co, &vertex, &edge, nearest_tmp);
419
 
                if(dist < nearest->dist)
420
 
                {
 
382
                if (dist < nearest->dist) {
421
383
                        nearest->index = index;
422
384
                        nearest->dist = dist;
423
 
                        VECCOPY(nearest->co, nearest_tmp);
 
385
                        copy_v3_v3(nearest->co, nearest_tmp);
424
386
                        normal_tri_v3( nearest->no,t0, t1, t2);
425
387
                }
426
388
 
428
390
                t2 = t3;
429
391
                t3 = NULL;
430
392
 
431
 
        } while(t2);
 
393
        } while (t2);
432
394
}
433
395
 
434
396
// Callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_faces.
449
411
        do
450
412
        {       
451
413
                float dist;
452
 
                if(data->sphere_radius == 0.0f)
453
 
                        dist = ray_tri_intersection(ray, hit->dist, t0, t1, t2);
 
414
                if (data->sphere_radius == 0.0f)
 
415
                        dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
454
416
                else
455
417
                        dist = sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, t0, t1, t2);
456
418
 
457
 
                if(dist >= 0 && dist < hit->dist)
458
 
                {
 
419
                if (dist >= 0 && dist < hit->dist) {
459
420
                        hit->index = index;
460
421
                        hit->dist = dist;
461
 
                        VECADDFAC(hit->co, ray->origin, ray->direction, dist);
 
422
                        madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
462
423
 
463
424
                        normal_tri_v3( hit->no,t0, t1, t2);
464
425
                }
467
428
                t2 = t3;
468
429
                t3 = NULL;
469
430
 
470
 
        } while(t2);
 
431
        } while (t2);
471
432
}
472
433
 
473
434
// Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_edges.
474
435
// userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
475
 
static void mesh_edges_nearest_point(void *userdata, int index, const float *co, BVHTreeNearest *nearest)
 
436
static void mesh_edges_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
476
437
{
477
438
        const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
478
439
        MVert *vert     = data->vert;
482
443
        float *t0, *t1;
483
444
        t0 = vert[ edge->v1 ].co;
484
445
        t1 = vert[ edge->v2 ].co;
485
 
        
486
 
        // NOTE: casts to "float*" here are due to co being "const float*"
487
 
        closest_to_line_segment_v3(nearest_tmp, (float*)co, t0, t1);
488
 
        dist = len_v3v3(nearest_tmp, (float*)co);
489
 
        
490
 
        if(dist < nearest->dist)
491
 
        {
 
446
 
 
447
        closest_to_line_segment_v3(nearest_tmp, co, t0, t1);
 
448
        dist = len_squared_v3v3(nearest_tmp, co);
 
449
        
 
450
        if (dist < nearest->dist) {
492
451
                nearest->index = index;
493
452
                nearest->dist = dist;
494
 
                VECCOPY(nearest->co, nearest_tmp);
 
453
                copy_v3_v3(nearest->co, nearest_tmp);
495
454
                sub_v3_v3v3(nearest->no, t0, t1);
496
455
                normalize_v3(nearest->no);
497
456
        }
506
465
        BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_VERTICES);
507
466
 
508
467
        //Not in cache
509
 
        if(tree == NULL)
510
 
        {
 
468
        if (tree == NULL) {
511
469
                int i;
512
470
                int numVerts= mesh->getNumVerts(mesh);
513
471
                MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
514
472
 
515
 
                if(vert != NULL)
516
 
                {
 
473
                if (vert != NULL) {
517
474
                        tree = BLI_bvhtree_new(numVerts, epsilon, tree_type, axis);
518
475
 
519
 
                        if(tree != NULL)
520
 
                        {
521
 
                                for(i = 0; i < numVerts; i++)
 
476
                        if (tree != NULL) {
 
477
                                for (i = 0; i < numVerts; i++) {
522
478
                                        BLI_bvhtree_insert(tree, i, vert[i].co, 1);
 
479
                                }
523
480
 
524
481
                                BLI_bvhtree_balance(tree);
525
482
 
529
486
                        }
530
487
                }
531
488
        }
532
 
        else
533
 
        {
 
489
        else {
534
490
//              printf("BVHTree is already build, using cached tree\n");
535
491
        }
536
492
 
539
495
        memset(data, 0, sizeof(*data));
540
496
        data->tree = tree;
541
497
 
542
 
        if(data->tree)
543
 
        {
 
498
        if (data->tree) {
544
499
                data->cached = TRUE;
545
500
 
546
501
                //a NULL nearest callback works fine
550
505
 
551
506
                data->mesh = mesh;
552
507
                data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
553
 
                data->face = mesh->getFaceDataArray(mesh, CD_MFACE);
 
508
                data->face = mesh->getTessFaceDataArray(mesh, CD_MFACE);
554
509
 
555
510
                data->sphere_radius = epsilon;
556
511
        }
564
519
        BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_FACES);
565
520
 
566
521
        //Not in cache
567
 
        if(tree == NULL)
568
 
        {
 
522
        if (tree == NULL) {
569
523
                int i;
570
 
                int numFaces= mesh->getNumFaces(mesh);
571
 
                MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
572
 
                MFace *face = mesh->getFaceDataArray(mesh, CD_MFACE);
573
 
 
574
 
                if(vert != NULL && face != NULL)
575
 
                {
 
524
                int numFaces= mesh->getNumTessFaces(mesh);
 
525
 
 
526
                /* BMESH specific check that we have tessfaces,
 
527
                 * we _could_ tessellate here but rather not - campbell
 
528
                 *
 
529
                 * this assert checks we have tessfaces,
 
530
                 * if not caller should use DM_ensure_tessface() */
 
531
                BLI_assert(!(numFaces == 0 && mesh->getNumPolys(mesh) != 0));
 
532
 
 
533
                if (numFaces != 0) {
576
534
                        /* Create a bvh-tree of the given target */
577
535
                        tree = BLI_bvhtree_new(numFaces, epsilon, tree_type, axis);
578
 
                        if(tree != NULL)
579
 
                        {
580
 
                                for(i = 0; i < numFaces; i++)
581
 
                                {
582
 
                                        float co[4][3];
583
 
                                        VECCOPY(co[0], vert[ face[i].v1 ].co);
584
 
                                        VECCOPY(co[1], vert[ face[i].v2 ].co);
585
 
                                        VECCOPY(co[2], vert[ face[i].v3 ].co);
586
 
                                        if(face[i].v4)
587
 
                                                VECCOPY(co[3], vert[ face[i].v4 ].co);
588
 
                        
589
 
                                        BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
 
536
                        if (tree != NULL) {
 
537
                                BMEditMesh *em= data->em_evil;
 
538
                                if (em) {
 
539
                                        /* data->em_evil is only set for snapping, and only for the mesh of the object
 
540
                                         * which is currently open in edit mode. When set, the bvhtree should not contain
 
541
                                         * faces that will interfere with snapping (e.g. faces that are hidden/selected
 
542
                                         * or faces that have selected verts).*/
 
543
 
 
544
                                        /* XXX, for snap only, em & dm are assumed to be aligned, since dm is the em's cage */
 
545
 
 
546
                                        /* Insert BMesh-tessellation triangles into the bvh tree, unless they are hidden
 
547
                                         * and/or selected. Even if the faces themselves are not selected for the snapped
 
548
                                         * transform, having a vertex selected means the face (and thus it's tessellated
 
549
                                         * triangles) will be moving and will not be a good snap targets.*/
 
550
                                        for (i = 0; i < em->tottri; i++) {
 
551
                                                BMLoop **tri = em->looptris[i];
 
552
                                                BMFace *f;
 
553
                                                BMVert *v;
 
554
                                                BMIter iter;
 
555
                                                int insert;
 
556
 
 
557
                                                /* Each loop of the triangle points back to the BMFace it was tessellated from.
 
558
                                                 * All three should point to the same face, so just use the face from the first
 
559
                                                 * loop.*/
 
560
                                                f = tri[0]->f;
 
561
 
 
562
                                                /* If the looptris is ordered such that all triangles tessellated from a single
 
563
                                                 * faces are consecutive elements in the array, then we could speed up the tests
 
564
                                                 * below by using the insert value from the previous iteration.*/
 
565
 
 
566
                                                /*Start with the assumption the triangle should be included for snapping.*/
 
567
                                                insert = 1;
 
568
 
 
569
                                                if (BM_elem_flag_test(f, BM_ELEM_SELECT) || BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
 
570
                                                        /* Don't insert triangles tessellated from faces that are hidden
 
571
                                                         * or selected*/
 
572
                                                        insert = 0;
 
573
                                                }
 
574
                                                else {
 
575
                                                        BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
 
576
                                                                if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
 
577
                                                                        /* Don't insert triangles tessellated from faces that have
 
578
                                                                         * any selected verts.*/
 
579
                                                                        insert = 0;
 
580
                                                                }
 
581
                                                        }
 
582
                                                }
 
583
 
 
584
                                                if (insert) {
 
585
                                                        /* No reason found to block hit-testing the triangle for snap,
 
586
                                                         * so insert it now.*/
 
587
                                                        float co[4][3];
 
588
                                                        copy_v3_v3(co[0], tri[0]->v->co);
 
589
                                                        copy_v3_v3(co[1], tri[1]->v->co);
 
590
                                                        copy_v3_v3(co[2], tri[2]->v->co);
 
591
                                        
 
592
                                                        BLI_bvhtree_insert(tree, i, co[0], 3);
 
593
                                                }
 
594
                                        }
 
595
                                }
 
596
                                else {
 
597
                                        MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
 
598
                                        MFace *face = mesh->getTessFaceDataArray(mesh, CD_MFACE);
 
599
 
 
600
                                        if (vert != NULL && face != NULL) {
 
601
                                                for (i = 0; i < numFaces; i++) {
 
602
                                                        float co[4][3];
 
603
                                                        copy_v3_v3(co[0], vert[ face[i].v1 ].co);
 
604
                                                        copy_v3_v3(co[1], vert[ face[i].v2 ].co);
 
605
                                                        copy_v3_v3(co[2], vert[ face[i].v3 ].co);
 
606
                                                        if (face[i].v4)
 
607
                                                                copy_v3_v3(co[3], vert[ face[i].v4 ].co);
 
608
                                        
 
609
                                                        BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
 
610
                                                }
 
611
                                        }
590
612
                                }
591
613
                                BLI_bvhtree_balance(tree);
592
614
 
596
618
                        }
597
619
                }
598
620
        }
599
 
        else
600
 
        {
 
621
        else {
601
622
//              printf("BVHTree is already build, using cached tree\n");
602
623
        }
603
624
 
606
627
        memset(data, 0, sizeof(*data));
607
628
        data->tree = tree;
608
629
 
609
 
        if(data->tree)
610
 
        {
 
630
        if (data->tree) {
611
631
                data->cached = TRUE;
612
632
 
613
633
                data->nearest_callback = mesh_faces_nearest_point;
615
635
 
616
636
                data->mesh = mesh;
617
637
                data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
618
 
                data->face = mesh->getFaceDataArray(mesh, CD_MFACE);
 
638
                data->face = mesh->getTessFaceDataArray(mesh, CD_MFACE);
619
639
 
620
640
                data->sphere_radius = epsilon;
621
641
        }
629
649
        BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_EDGES);
630
650
 
631
651
        //Not in cache
632
 
        if(tree == NULL)
 
652
        if (tree == NULL)
633
653
        {
634
654
                int i;
635
655
                int numEdges= mesh->getNumEdges(mesh);
636
656
                MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
637
657
                MEdge *edge = mesh->getEdgeDataArray(mesh, CD_MEDGE);
638
658
 
639
 
                if(vert != NULL && edge != NULL)
640
 
                {
 
659
                if (vert != NULL && edge != NULL) {
641
660
                        /* Create a bvh-tree of the given target */
642
661
                        tree = BLI_bvhtree_new(numEdges, epsilon, tree_type, axis);
643
 
                        if(tree != NULL)
644
 
                        {
645
 
                                for(i = 0; i < numEdges; i++)
646
 
                                {
 
662
                        if (tree != NULL) {
 
663
                                for (i = 0; i < numEdges; i++) {
647
664
                                        float co[4][3];
648
 
                                        VECCOPY(co[0], vert[ edge[i].v1 ].co);
649
 
                                        VECCOPY(co[1], vert[ edge[i].v2 ].co);
 
665
                                        copy_v3_v3(co[0], vert[ edge[i].v1 ].co);
 
666
                                        copy_v3_v3(co[1], vert[ edge[i].v2 ].co);
650
667
                        
651
668
                                        BLI_bvhtree_insert(tree, i, co[0], 2);
652
669
                                }
668
685
        memset(data, 0, sizeof(*data));
669
686
        data->tree = tree;
670
687
 
671
 
        if(data->tree)
672
 
        {
 
688
        if (data->tree) {
673
689
                data->cached = TRUE;
674
690
 
675
691
                data->nearest_callback = mesh_edges_nearest_point;
688
704
// Frees data allocated by a call to bvhtree_from_mesh_*.
689
705
void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
690
706
{
691
 
        if(data->tree)
692
 
        {
693
 
                if(!data->cached)
 
707
        if (data->tree) {
 
708
                if (!data->cached)
694
709
                        BLI_bvhtree_free(data->tree);
695
710
 
696
 
                memset( data, 0, sizeof(data) );
 
711
                memset( data, 0, sizeof(*data) );
697
712
        }
698
713
}
699
714
 
711
726
        BVHCacheItem * cached = (BVHCacheItem *)_cached;
712
727
        BVHCacheItem * search = (BVHCacheItem *)_search;
713
728
 
714
 
        if(search->type == cached->type)
715
 
        {
 
729
        if (search->type == cached->type) {
716
730
                search->tree = cached->tree;            
717
731
        }
718
732
} 
740
754
        item->type = type;
741
755
        item->tree = tree;
742
756
 
743
 
        BLI_linklist_prepend( cache, item );
 
757
        BLI_linklist_prepend(cache, item);
744
758
}
745
759
 
746
760