e9009050d4bc6dd5d61fb4a337f4058eba3a3757
[blender.git] / source / blender / blenkernel / intern / pbvh.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 /** \file blender/blenkernel/intern/pbvh.c
22  *  \ingroup bli
23  */
24
25 #include "DNA_meshdata_types.h"
26
27 #include "MEM_guardedalloc.h"
28
29 #include "BLI_bitmap.h"
30 #include "BLI_math.h"
31 #include "BLI_utildefines.h"
32 #include "BLI_ghash.h"
33
34 #include "BKE_pbvh.h"
35 #include "BKE_ccg.h"
36 #include "BKE_DerivedMesh.h"
37 #include "BKE_mesh.h" /* for BKE_mesh_calc_normals */
38 #include "BKE_global.h" /* for BKE_mesh_calc_normals */
39 #include "BKE_paint.h"
40 #include "BKE_subsurf.h"
41
42 #include "GPU_buffers.h"
43
44 #include "pbvh_intern.h"
45
46 #define LEAF_LIMIT 10000
47
48 //#define PERFCNTRS
49
50 #define STACK_FIXED_DEPTH   100
51
52 typedef struct PBVHStack {
53         PBVHNode *node;
54         int revisiting;
55 } PBVHStack;
56
57 typedef struct PBVHIter {
58         PBVH *bvh;
59         BLI_pbvh_SearchCallback scb;
60         void *search_data;
61
62         PBVHStack *stack;
63         int stacksize;
64
65         PBVHStack stackfixed[STACK_FIXED_DEPTH];
66         int stackspace;
67 } PBVHIter;
68
69 static void BB_reset(BB *bb)
70 {
71         bb->bmin[0] = bb->bmin[1] = bb->bmin[2] = FLT_MAX;
72         bb->bmax[0] = bb->bmax[1] = bb->bmax[2] = -FLT_MAX;
73 }
74
75 /* Expand the bounding box to include a new coordinate */
76 static void BB_expand(BB *bb, float co[3])
77 {
78         int i;
79         for (i = 0; i < 3; ++i) {
80                 bb->bmin[i] = min_ff(bb->bmin[i], co[i]);
81                 bb->bmax[i] = max_ff(bb->bmax[i], co[i]);
82         }
83 }
84
85 /* Expand the bounding box to include another bounding box */
86 static void BB_expand_with_bb(BB *bb, BB *bb2)
87 {
88         int i;
89         for (i = 0; i < 3; ++i) {
90                 bb->bmin[i] = min_ff(bb->bmin[i], bb2->bmin[i]);
91                 bb->bmax[i] = max_ff(bb->bmax[i], bb2->bmax[i]);
92         }
93 }
94
95 /* Return 0, 1, or 2 to indicate the widest axis of the bounding box */
96 static int BB_widest_axis(BB *bb)
97 {
98         float dim[3];
99         int i;
100
101         for (i = 0; i < 3; ++i)
102                 dim[i] = bb->bmax[i] - bb->bmin[i];
103
104         if (dim[0] > dim[1]) {
105                 if (dim[0] > dim[2])
106                         return 0;
107                 else
108                         return 2;
109         }
110         else {
111                 if (dim[1] > dim[2])
112                         return 1;
113                 else
114                         return 2;
115         }
116 }
117
118 static void BBC_update_centroid(BBC *bbc)
119 {
120         int i;
121         for (i = 0; i < 3; ++i)
122                 bbc->bcentroid[i] = (bbc->bmin[i] + bbc->bmax[i]) * 0.5f;
123 }
124
125 /* Not recursive */
126 static void update_node_vb(PBVH *bvh, PBVHNode *node)
127 {
128         BB vb;
129
130         BB_reset(&vb);
131         
132         if (node->flag & PBVH_Leaf) {
133                 PBVHVertexIter vd;
134
135                 BLI_pbvh_vertex_iter_begin(bvh, node, vd, PBVH_ITER_ALL)
136                 {
137                         BB_expand(&vb, vd.co);
138                 }
139                 BLI_pbvh_vertex_iter_end;
140         }
141         else {
142                 BB_expand_with_bb(&vb,
143                                   &bvh->nodes[node->children_offset].vb);
144                 BB_expand_with_bb(&vb,
145                                   &bvh->nodes[node->children_offset + 1].vb);
146         }
147
148         node->vb = vb;
149 }
150
151 //void BLI_pbvh_node_BB_reset(PBVHNode *node)
152 //{
153 //      BB_reset(&node->vb);
154 //}
155 //
156 //void BLI_pbvh_node_BB_expand(PBVHNode *node, float co[3])
157 //{
158 //      BB_expand(&node->vb, co);
159 //}
160
161 static int face_materials_match(const MFace *f1, const MFace *f2)
162 {
163         return ((f1->flag & ME_SMOOTH) == (f2->flag & ME_SMOOTH) &&
164                 (f1->mat_nr == f2->mat_nr));
165 }
166
167 static int grid_materials_match(const DMFlagMat *f1, const DMFlagMat *f2)
168 {
169         return ((f1->flag & ME_SMOOTH) == (f2->flag & ME_SMOOTH) &&
170                 (f1->mat_nr == f2->mat_nr));
171 }
172
173 /* Adapted from BLI_kdopbvh.c */
174 /* Returns the index of the first element on the right of the partition */
175 static int partition_indices(int *prim_indices, int lo, int hi, int axis,
176                              float mid, BBC *prim_bbc)
177 {
178         int i = lo, j = hi;
179         for (;; ) {
180                 for (; prim_bbc[prim_indices[i]].bcentroid[axis] < mid; i++) ;
181                 for (; mid < prim_bbc[prim_indices[j]].bcentroid[axis]; j--) ;
182                 
183                 if (!(i < j))
184                         return i;
185                 
186                 SWAP(int, prim_indices[i], prim_indices[j]);
187                 i++;
188         }
189 }
190
191 /* Returns the index of the first element on the right of the partition */
192 static int partition_indices_material(PBVH *bvh, int lo, int hi)
193 {
194         const MFace *faces = bvh->faces;
195         const DMFlagMat *flagmats = bvh->grid_flag_mats;
196         const int *indices = bvh->prim_indices;
197         const void *first;
198         int i = lo, j = hi;
199
200         if (bvh->faces)
201                 first = &faces[bvh->prim_indices[lo]];
202         else
203                 first = &flagmats[bvh->prim_indices[lo]];
204
205         for (;; ) {
206                 if (bvh->faces) {
207                         for (; face_materials_match(first, &faces[indices[i]]); i++) ;
208                         for (; !face_materials_match(first, &faces[indices[j]]); j--) ;
209                 }
210                 else {
211                         for (; grid_materials_match(first, &flagmats[indices[i]]); i++) ;
212                         for (; !grid_materials_match(first, &flagmats[indices[j]]); j--) ;
213                 }
214                 
215                 if (!(i < j))
216                         return i;
217
218                 SWAP(int, bvh->prim_indices[i], bvh->prim_indices[j]);
219                 i++;
220         }
221 }
222
223 static void grow_nodes(PBVH *bvh, int totnode)
224 {
225         if (totnode > bvh->node_mem_count) {
226                 PBVHNode *prev = bvh->nodes;
227                 bvh->node_mem_count *= 1.33;
228                 if (bvh->node_mem_count < totnode)
229                         bvh->node_mem_count = totnode;
230                 bvh->nodes = MEM_callocN(sizeof(PBVHNode) * bvh->node_mem_count,
231                                          "bvh nodes");
232                 memcpy(bvh->nodes, prev, bvh->totnode * sizeof(PBVHNode));
233                 MEM_freeN(prev);
234         }
235
236         bvh->totnode = totnode;
237 }
238
239 /* Add a vertex to the map, with a positive value for unique vertices and
240  * a negative value for additional vertices */
241 static int map_insert_vert(PBVH *bvh, GHash *map,
242                            unsigned int *face_verts,
243                            unsigned int *uniq_verts, int vertex)
244 {
245         void *value, *key = SET_INT_IN_POINTER(vertex);
246
247         if (!BLI_ghash_haskey(map, key)) {
248                 if (BLI_BITMAP_GET(bvh->vert_bitmap, vertex)) {
249                         value = SET_INT_IN_POINTER(~(*face_verts));
250                         ++(*face_verts);
251                 }
252                 else {
253                         BLI_BITMAP_SET(bvh->vert_bitmap, vertex);
254                         value = SET_INT_IN_POINTER(*uniq_verts);
255                         ++(*uniq_verts);
256                 }
257                 
258                 BLI_ghash_insert(map, key, value);
259                 return GET_INT_FROM_POINTER(value);
260         }
261         else
262                 return GET_INT_FROM_POINTER(BLI_ghash_lookup(map, key));
263 }
264
265 /* Find vertices used by the faces in this node and update the draw buffers */
266 static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node)
267 {
268         GHashIterator *iter;
269         GHash *map;
270         int i, j, totface;
271
272         map = BLI_ghash_int_new("build_mesh_leaf_node gh");
273         
274         node->uniq_verts = node->face_verts = 0;
275         totface = node->totprim;
276
277         node->face_vert_indices = MEM_callocN(sizeof(int) * 4 * totface,
278                                               "bvh node face vert indices");
279
280         for (i = 0; i < totface; ++i) {
281                 MFace *f = bvh->faces + node->prim_indices[i];
282                 int sides = f->v4 ? 4 : 3;
283
284                 for (j = 0; j < sides; ++j) {
285                         node->face_vert_indices[i][j] =
286                                 map_insert_vert(bvh, map, &node->face_verts,
287                                                 &node->uniq_verts, (&f->v1)[j]);
288                 }
289         }
290
291         node->vert_indices = MEM_callocN(sizeof(int) *
292                                          (node->uniq_verts + node->face_verts),
293                                          "bvh node vert indices");
294
295         /* Build the vertex list, unique verts first */
296         for (iter = BLI_ghashIterator_new(map), i = 0;
297              BLI_ghashIterator_isDone(iter) == FALSE;
298              BLI_ghashIterator_step(iter), ++i)
299         {
300                 void *value = BLI_ghashIterator_getValue(iter);
301                 int ndx = GET_INT_FROM_POINTER(value);
302
303                 if (ndx < 0)
304                         ndx = -ndx + node->uniq_verts - 1;
305
306                 node->vert_indices[ndx] =
307                     GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(iter));
308         }
309
310         BLI_ghashIterator_free(iter);
311
312         for (i = 0; i < totface; ++i) {
313                 MFace *f = bvh->faces + node->prim_indices[i];
314                 int sides = f->v4 ? 4 : 3;
315                 
316                 for (j = 0; j < sides; ++j) {
317                         if (node->face_vert_indices[i][j] < 0)
318                                 node->face_vert_indices[i][j] =
319                                         -node->face_vert_indices[i][j] +
320                                         node->uniq_verts - 1;
321                 }
322         }
323
324         if (!G.background) {
325                 node->draw_buffers =
326                         GPU_build_mesh_buffers(node->face_vert_indices,
327                                                bvh->faces, bvh->verts,
328                                                node->prim_indices,
329                                                node->totprim);
330         }
331
332         node->flag |= PBVH_UpdateDrawBuffers;
333
334         BLI_ghash_free(map, NULL, NULL);
335 }
336
337 static void build_grids_leaf_node(PBVH *bvh, PBVHNode *node)
338 {
339         if (!G.background) {
340                 node->draw_buffers =
341                     GPU_build_grid_buffers(node->prim_indices,
342                                            node->totprim, bvh->grid_hidden, bvh->gridkey.grid_size);
343         }
344         node->flag |= PBVH_UpdateDrawBuffers;
345 }
346
347 static void update_vb(PBVH *bvh, PBVHNode *node, BBC *prim_bbc,
348                       int offset, int count)
349 {
350         int i;
351         
352         BB_reset(&node->vb);
353         for (i = offset + count - 1; i >= offset; --i) {
354                 BB_expand_with_bb(&node->vb, (BB *)(&prim_bbc[bvh->prim_indices[i]]));
355         }
356         node->orig_vb = node->vb;
357 }
358
359 static void build_leaf(PBVH *bvh, int node_index, BBC *prim_bbc,
360                        int offset, int count)
361 {
362         bvh->nodes[node_index].flag |= PBVH_Leaf;
363
364         bvh->nodes[node_index].prim_indices = bvh->prim_indices + offset;
365         bvh->nodes[node_index].totprim = count;
366
367         /* Still need vb for searches */
368         update_vb(bvh, &bvh->nodes[node_index], prim_bbc, offset, count);
369                 
370         if (bvh->faces)
371                 build_mesh_leaf_node(bvh, bvh->nodes + node_index);
372         else
373                 build_grids_leaf_node(bvh, bvh->nodes + node_index);
374 }
375
376 /* Return zero if all primitives in the node can be drawn with the
377  * same material (including flat/smooth shading), non-zerootherwise */
378 static int leaf_needs_material_split(PBVH *bvh, int offset, int count)
379 {
380         int i, prim;
381
382         if (count <= 1)
383                 return 0;
384
385         if (bvh->faces) {
386                 const MFace *first = &bvh->faces[bvh->prim_indices[offset]];
387
388                 for (i = offset + count - 1; i > offset; --i) {
389                         prim = bvh->prim_indices[i];
390                         if (!face_materials_match(first, &bvh->faces[prim]))
391                                 return 1;
392                 }
393         }
394         else {
395                 const DMFlagMat *first = &bvh->grid_flag_mats[bvh->prim_indices[offset]];
396
397                 for (i = offset + count - 1; i > offset; --i) {
398                         prim = bvh->prim_indices[i];
399                         if (!grid_materials_match(first, &bvh->grid_flag_mats[prim]))
400                                 return 1;
401                 }
402         }
403
404         return 0;
405 }
406
407
408 /* Recursively build a node in the tree
409  *
410  * vb is the voxel box around all of the primitives contained in
411  * this node.
412  *
413  * cb is the bounding box around all the centroids of the primitives
414  * contained in this node
415  *
416  * offset and start indicate a range in the array of primitive indices
417  */
418
419 static void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc,
420                       int offset, int count)
421 {
422         int i, axis, end, below_leaf_limit;
423         BB cb_backing;
424
425         /* Decide whether this is a leaf or not */
426         below_leaf_limit = count <= bvh->leaf_limit;
427         if (below_leaf_limit) {
428                 if (!leaf_needs_material_split(bvh, offset, count)) {
429                         build_leaf(bvh, node_index, prim_bbc, offset, count);
430                         return;
431                 }
432         }
433
434         /* Add two child nodes */
435         bvh->nodes[node_index].children_offset = bvh->totnode;
436         grow_nodes(bvh, bvh->totnode + 2);
437
438         /* Update parent node bounding box */
439         update_vb(bvh, &bvh->nodes[node_index], prim_bbc, offset, count);
440
441         if (!below_leaf_limit) {
442                 /* Find axis with widest range of primitive centroids */
443                 if (!cb) {
444                         cb = &cb_backing;
445                         BB_reset(cb);
446                         for (i = offset + count - 1; i >= offset; --i)
447                                 BB_expand(cb, prim_bbc[bvh->prim_indices[i]].bcentroid);
448                 }
449                 axis = BB_widest_axis(cb);
450
451                 /* Partition primitives along that axis */
452                 end = partition_indices(bvh->prim_indices,
453                                         offset, offset + count - 1,
454                                         axis,
455                                         (cb->bmax[axis] + cb->bmin[axis]) * 0.5f,
456                                         prim_bbc);
457         }
458         else {
459                 /* Partition primitives by material */
460                 end = partition_indices_material(bvh, offset, offset + count - 1);
461         }
462
463         /* Build children */
464         build_sub(bvh, bvh->nodes[node_index].children_offset, NULL,
465                   prim_bbc, offset, end - offset);
466         build_sub(bvh, bvh->nodes[node_index].children_offset + 1, NULL,
467                   prim_bbc, end, offset + count - end);
468 }
469
470 static void pbvh_build(PBVH *bvh, BB *cb, BBC *prim_bbc, int totprim)
471 {
472         int i;
473
474         if (totprim != bvh->totprim) {
475                 bvh->totprim = totprim;
476                 if (bvh->nodes) MEM_freeN(bvh->nodes);
477                 if (bvh->prim_indices) MEM_freeN(bvh->prim_indices);
478                 bvh->prim_indices = MEM_callocN(sizeof(int) * totprim,
479                                                 "bvh prim indices");
480                 for (i = 0; i < totprim; ++i)
481                         bvh->prim_indices[i] = i;
482                 bvh->totnode = 0;
483                 if (bvh->node_mem_count < 100) {
484                         bvh->node_mem_count = 100;
485                         bvh->nodes = MEM_callocN(sizeof(PBVHNode) *
486                                                  bvh->node_mem_count,
487                                                  "bvh initial nodes");
488                 }
489         }
490
491         bvh->totnode = 1;
492         build_sub(bvh, 0, cb, prim_bbc, 0, totprim);
493 }
494
495 /* Do a full rebuild with on Mesh data structure */
496 void BLI_pbvh_build_mesh(PBVH *bvh, MFace *faces, MVert *verts, int totface, int totvert, struct CustomData *vdata)
497 {
498         BBC *prim_bbc = NULL;
499         BB cb;
500         int i, j;
501
502         bvh->type = PBVH_FACES;
503         bvh->faces = faces;
504         bvh->verts = verts;
505         bvh->vert_bitmap = BLI_BITMAP_NEW(totvert, "bvh->vert_bitmap");
506         bvh->totvert = totvert;
507         bvh->leaf_limit = LEAF_LIMIT;
508         bvh->vdata = vdata;
509
510         BB_reset(&cb);
511
512         /* For each face, store the AABB and the AABB centroid */
513         prim_bbc = MEM_mallocN(sizeof(BBC) * totface, "prim_bbc");
514
515         for (i = 0; i < totface; ++i) {
516                 MFace *f = faces + i;
517                 const int sides = f->v4 ? 4 : 3;
518                 BBC *bbc = prim_bbc + i;
519
520                 BB_reset((BB *)bbc);
521
522                 for (j = 0; j < sides; ++j)
523                         BB_expand((BB *)bbc, verts[(&f->v1)[j]].co);
524
525                 BBC_update_centroid(bbc);
526
527                 BB_expand(&cb, bbc->bcentroid);
528         }
529
530         if (totface)
531                 pbvh_build(bvh, &cb, prim_bbc, totface);
532
533         MEM_freeN(prim_bbc);
534         MEM_freeN(bvh->vert_bitmap);
535 }
536
537 /* Do a full rebuild with on Grids data structure */
538 void BLI_pbvh_build_grids(PBVH *bvh, CCGElem **grids, DMGridAdjacency *gridadj,
539                           int totgrid, CCGKey *key, void **gridfaces, DMFlagMat *flagmats, BLI_bitmap *grid_hidden)
540 {
541         BBC *prim_bbc = NULL;
542         BB cb;
543         int gridsize = key->grid_size;
544         int i, j;
545
546         bvh->type = PBVH_GRIDS;
547         bvh->grids = grids;
548         bvh->gridadj = gridadj;
549         bvh->gridfaces = gridfaces;
550         bvh->grid_flag_mats = flagmats;
551         bvh->totgrid = totgrid;
552         bvh->gridkey = *key;
553         bvh->grid_hidden = grid_hidden;
554         bvh->leaf_limit = max_ii(LEAF_LIMIT / ((gridsize - 1) * (gridsize - 1)), 1);
555
556         BB_reset(&cb);
557
558         /* For each grid, store the AABB and the AABB centroid */
559         prim_bbc = MEM_mallocN(sizeof(BBC) * totgrid, "prim_bbc");
560
561         for (i = 0; i < totgrid; ++i) {
562                 CCGElem *grid = grids[i];
563                 BBC *bbc = prim_bbc + i;
564
565                 BB_reset((BB *)bbc);
566
567                 for (j = 0; j < gridsize * gridsize; ++j)
568                         BB_expand((BB *)bbc, CCG_elem_offset_co(key, grid, j));
569
570                 BBC_update_centroid(bbc);
571
572                 BB_expand(&cb, bbc->bcentroid);
573         }
574
575         if (totgrid)
576                 pbvh_build(bvh, &cb, prim_bbc, totgrid);
577
578         MEM_freeN(prim_bbc);
579 }
580
581 PBVH *BLI_pbvh_new(void)
582 {
583         PBVH *bvh = MEM_callocN(sizeof(PBVH), "pbvh");
584
585         return bvh;
586 }
587
588 void BLI_pbvh_free(PBVH *bvh)
589 {
590         PBVHNode *node;
591         int i;
592
593         for (i = 0; i < bvh->totnode; ++i) {
594                 node = &bvh->nodes[i];
595
596                 if (node->flag & PBVH_Leaf) {
597                         if (node->draw_buffers)
598                                 GPU_free_buffers(node->draw_buffers);
599                         if (node->vert_indices)
600                                 MEM_freeN(node->vert_indices);
601                         if (node->face_vert_indices)
602                                 MEM_freeN(node->face_vert_indices);
603                         BLI_pbvh_node_layer_disp_free(node);
604                 }
605         }
606
607         if (bvh->deformed) {
608                 if (bvh->verts) {
609                         /* if pbvh was deformed, new memory was allocated for verts/faces -- free it */
610
611                         MEM_freeN(bvh->verts);
612                         if (bvh->faces)
613                                 MEM_freeN(bvh->faces);
614                 }
615         }
616
617         if (bvh->nodes)
618                 MEM_freeN(bvh->nodes);
619
620         if (bvh->prim_indices)
621                 MEM_freeN(bvh->prim_indices);
622
623         MEM_freeN(bvh);
624 }
625
626 static void pbvh_iter_begin(PBVHIter *iter, PBVH *bvh, BLI_pbvh_SearchCallback scb, void *search_data)
627 {
628         iter->bvh = bvh;
629         iter->scb = scb;
630         iter->search_data = search_data;
631
632         iter->stack = iter->stackfixed;
633         iter->stackspace = STACK_FIXED_DEPTH;
634
635         iter->stack[0].node = bvh->nodes;
636         iter->stack[0].revisiting = 0;
637         iter->stacksize = 1;
638 }
639
640 static void pbvh_iter_end(PBVHIter *iter)
641 {
642         if (iter->stackspace > STACK_FIXED_DEPTH)
643                 MEM_freeN(iter->stack);
644 }
645
646 static void pbvh_stack_push(PBVHIter *iter, PBVHNode *node, int revisiting)
647 {
648         if (iter->stacksize == iter->stackspace) {
649                 PBVHStack *newstack;
650
651                 iter->stackspace *= 2;
652                 newstack = MEM_callocN(sizeof(PBVHStack) * iter->stackspace, "PBVHStack");
653                 memcpy(newstack, iter->stack, sizeof(PBVHStack) * iter->stacksize);
654
655                 if (iter->stackspace > STACK_FIXED_DEPTH)
656                         MEM_freeN(iter->stack);
657                 iter->stack = newstack;
658         }
659
660         iter->stack[iter->stacksize].node = node;
661         iter->stack[iter->stacksize].revisiting = revisiting;
662         iter->stacksize++;
663 }
664
665 static PBVHNode *pbvh_iter_next(PBVHIter *iter)
666 {
667         PBVHNode *node;
668         int revisiting;
669
670         /* purpose here is to traverse tree, visiting child nodes before their
671          * parents, this order is necessary for e.g. computing bounding boxes */
672
673         while (iter->stacksize) {
674                 /* pop node */
675                 iter->stacksize--;
676                 node = iter->stack[iter->stacksize].node;
677
678                 /* on a mesh with no faces this can happen
679                  * can remove this check if we know meshes have at least 1 face */
680                 if (node == NULL)
681                         return NULL;
682
683                 revisiting = iter->stack[iter->stacksize].revisiting;
684
685                 /* revisiting node already checked */
686                 if (revisiting)
687                         return node;
688
689                 if (iter->scb && !iter->scb(node, iter->search_data))
690                         continue;  /* don't traverse, outside of search zone */
691
692                 if (node->flag & PBVH_Leaf) {
693                         /* immediately hit leaf node */
694                         return node;
695                 }
696                 else {
697                         /* come back later when children are done */
698                         pbvh_stack_push(iter, node, 1);
699
700                         /* push two child nodes on the stack */
701                         pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset + 1, 0);
702                         pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset, 0);
703                 }
704         }
705
706         return NULL;
707 }
708
709 static PBVHNode *pbvh_iter_next_occluded(PBVHIter *iter)
710 {
711         PBVHNode *node;
712
713         while (iter->stacksize) {
714                 /* pop node */
715                 iter->stacksize--;
716                 node = iter->stack[iter->stacksize].node;
717
718                 /* on a mesh with no faces this can happen
719                  * can remove this check if we know meshes have at least 1 face */
720                 if (node == NULL) return NULL;
721
722                 if (iter->scb && !iter->scb(node, iter->search_data)) continue;  /* don't traverse, outside of search zone */
723
724                 if (node->flag & PBVH_Leaf) {
725                         /* immediately hit leaf node */
726                         return node;
727                 }
728                 else {
729                         pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset + 1, 0);
730                         pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset, 0);
731                 }
732         }
733
734         return NULL;
735 }
736
737 void BLI_pbvh_search_gather(PBVH *bvh,
738                             BLI_pbvh_SearchCallback scb, void *search_data,
739                             PBVHNode ***r_array, int *r_tot)
740 {
741         PBVHIter iter;
742         PBVHNode **array = NULL, **newarray, *node;
743         int tot = 0, space = 0;
744
745         pbvh_iter_begin(&iter, bvh, scb, search_data);
746
747         while ((node = pbvh_iter_next(&iter))) {
748                 if (node->flag & PBVH_Leaf) {
749                         if (tot == space) {
750                                 /* resize array if needed */
751                                 space = (tot == 0) ? 32 : space * 2;
752                                 newarray = MEM_callocN(sizeof(PBVHNode) * space, "PBVHNodeSearch");
753
754                                 if (array) {
755                                         memcpy(newarray, array, sizeof(PBVHNode) * tot);
756                                         MEM_freeN(array);
757                                 }
758
759                                 array = newarray;
760                         }
761
762                         array[tot] = node;
763                         tot++;
764                 }
765         }
766
767         pbvh_iter_end(&iter);
768
769         if (tot == 0 && array) {
770                 MEM_freeN(array);
771                 array = NULL;
772         }
773
774         *r_array = array;
775         *r_tot = tot;
776 }
777
778 void BLI_pbvh_search_callback(PBVH *bvh,
779                               BLI_pbvh_SearchCallback scb, void *search_data,
780                               BLI_pbvh_HitCallback hcb, void *hit_data)
781 {
782         PBVHIter iter;
783         PBVHNode *node;
784
785         pbvh_iter_begin(&iter, bvh, scb, search_data);
786
787         while ((node = pbvh_iter_next(&iter)))
788                 if (node->flag & PBVH_Leaf)
789                         hcb(node, hit_data);
790
791         pbvh_iter_end(&iter);
792 }
793
794 typedef struct node_tree {
795         PBVHNode *data;
796
797         struct node_tree *left;
798         struct node_tree *right;
799 } node_tree;
800
801 static void node_tree_insert(node_tree *tree, node_tree *new_node)
802 {
803         if (new_node->data->tmin < tree->data->tmin) {
804                 if (tree->left) {
805                         node_tree_insert(tree->left, new_node);
806                 }
807                 else {
808                         tree->left = new_node;
809                 }
810         }
811         else {
812                 if (tree->right) {
813                         node_tree_insert(tree->right, new_node);
814                 }
815                 else {
816                         tree->right = new_node;
817                 }
818         }
819 }
820
821 static void traverse_tree(node_tree *tree, BLI_pbvh_HitOccludedCallback hcb, void *hit_data, float *tmin)
822 {
823         if (tree->left) traverse_tree(tree->left, hcb, hit_data, tmin);
824
825         hcb(tree->data, hit_data, tmin);
826
827         if (tree->right) traverse_tree(tree->right, hcb, hit_data, tmin);
828 }
829
830 static void free_tree(node_tree *tree)
831 {
832         if (tree->left) {
833                 free_tree(tree->left);
834                 tree->left = 0;
835         }
836
837         if (tree->right) {
838                 free_tree(tree->right);
839                 tree->right = 0;
840         }
841
842         free(tree);
843 }
844
845 float BLI_pbvh_node_get_tmin(PBVHNode *node)
846 {
847         return node->tmin;
848 }
849
850 static void BLI_pbvh_search_callback_occluded(PBVH *bvh,
851                                               BLI_pbvh_SearchCallback scb, void *search_data,
852                                               BLI_pbvh_HitOccludedCallback hcb, void *hit_data)
853 {
854         PBVHIter iter;
855         PBVHNode *node;
856         node_tree *tree = 0;
857
858         pbvh_iter_begin(&iter, bvh, scb, search_data);
859
860         while ((node = pbvh_iter_next_occluded(&iter))) {
861                 if (node->flag & PBVH_Leaf) {
862                         node_tree *new_node = malloc(sizeof(node_tree));
863
864                         new_node->data = node;
865
866                         new_node->left  = NULL;
867                         new_node->right = NULL;
868
869                         if (tree) {
870                                 node_tree_insert(tree, new_node);
871                         }
872                         else {
873                                 tree = new_node;
874                         }
875                 }
876         }
877
878         pbvh_iter_end(&iter);
879
880         if (tree) {
881                 float tmin = FLT_MAX;
882                 traverse_tree(tree, hcb, hit_data, &tmin);
883                 free_tree(tree);
884         }
885 }
886
887 static int update_search_cb(PBVHNode *node, void *data_v)
888 {
889         int flag = GET_INT_FROM_POINTER(data_v);
890
891         if (node->flag & PBVH_Leaf)
892                 return (node->flag & flag);
893
894         return 1;
895 }
896
897 static void pbvh_update_normals(PBVH *bvh, PBVHNode **nodes,
898                                 int totnode, float (*face_nors)[3])
899 {
900         float (*vnor)[3];
901         int n;
902
903         if (bvh->type != PBVH_FACES)
904                 return;
905
906         /* could be per node to save some memory, but also means
907          * we have to store for each vertex which node it is in */
908         vnor = MEM_callocN(sizeof(float) * 3 * bvh->totvert, "bvh temp vnors");
909
910         /* subtle assumptions:
911          * - We know that for all edited vertices, the nodes with faces
912          *   adjacent to these vertices have been marked with PBVH_UpdateNormals.
913          *   This is true because if the vertex is inside the brush radius, the
914          *   bounding box of it's adjacent faces will be as well.
915          * - However this is only true for the vertices that have actually been
916          *   edited, not for all vertices in the nodes marked for update, so we
917          *   can only update vertices marked with ME_VERT_PBVH_UPDATE.
918          */
919
920         #pragma omp parallel for private(n) schedule(static)
921         for (n = 0; n < totnode; n++) {
922                 PBVHNode *node = nodes[n];
923
924                 if ((node->flag & PBVH_UpdateNormals)) {
925                         int i, j, totface, *faces;
926
927                         faces = node->prim_indices;
928                         totface = node->totprim;
929
930                         for (i = 0; i < totface; ++i) {
931                                 MFace *f = bvh->faces + faces[i];
932                                 float fn[3];
933                                 unsigned int *fv = &f->v1;
934                                 int sides = (f->v4) ? 4 : 3;
935
936                                 if (f->v4)
937                                         normal_quad_v3(fn, bvh->verts[f->v1].co, bvh->verts[f->v2].co,
938                                                        bvh->verts[f->v3].co, bvh->verts[f->v4].co);
939                                 else
940                                         normal_tri_v3(fn, bvh->verts[f->v1].co, bvh->verts[f->v2].co,
941                                                       bvh->verts[f->v3].co);
942
943                                 for (j = 0; j < sides; ++j) {
944                                         int v = fv[j];
945
946                                         if (bvh->verts[v].flag & ME_VERT_PBVH_UPDATE) {
947                                                 /* this seems like it could be very slow but profile
948                                                  * does not show this, so just leave it for now? */
949                                                 #pragma omp atomic
950                                                 vnor[v][0] += fn[0];
951                                                 #pragma omp atomic
952                                                 vnor[v][1] += fn[1];
953                                                 #pragma omp atomic
954                                                 vnor[v][2] += fn[2];
955                                         }
956                                 }
957
958                                 if (face_nors)
959                                         copy_v3_v3(face_nors[faces[i]], fn);
960                         }
961                 }
962         }
963
964         #pragma omp parallel for private(n) schedule(static)
965         for (n = 0; n < totnode; n++) {
966                 PBVHNode *node = nodes[n];
967
968                 if (node->flag & PBVH_UpdateNormals) {
969                         int i, *verts, totvert;
970
971                         verts = node->vert_indices;
972                         totvert = node->uniq_verts;
973
974                         for (i = 0; i < totvert; ++i) {
975                                 const int v = verts[i];
976                                 MVert *mvert = &bvh->verts[v];
977
978                                 if (mvert->flag & ME_VERT_PBVH_UPDATE) {
979                                         float no[3];
980
981                                         copy_v3_v3(no, vnor[v]);
982                                         normalize_v3(no);
983                                         normal_float_to_short_v3(mvert->no, no);
984
985                                         mvert->flag &= ~ME_VERT_PBVH_UPDATE;
986                                 }
987                         }
988
989                         node->flag &= ~PBVH_UpdateNormals;
990                 }
991         }
992
993         MEM_freeN(vnor);
994 }
995
996 static void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes,
997                                   int totnode, int flag)
998 {
999         int n;
1000
1001         /* update BB, redraw flag */
1002         #pragma omp parallel for private(n) schedule(static)
1003         for (n = 0; n < totnode; n++) {
1004                 PBVHNode *node = nodes[n];
1005
1006                 if ((flag & PBVH_UpdateBB) && (node->flag & PBVH_UpdateBB))
1007                         /* don't clear flag yet, leave it for flushing later */
1008                         update_node_vb(bvh, node);
1009
1010                 if ((flag & PBVH_UpdateOriginalBB) && (node->flag & PBVH_UpdateOriginalBB))
1011                         node->orig_vb = node->vb;
1012
1013                 if ((flag & PBVH_UpdateRedraw) && (node->flag & PBVH_UpdateRedraw))
1014                         node->flag &= ~PBVH_UpdateRedraw;
1015         }
1016 }
1017
1018 static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode)
1019 {
1020         PBVHNode *node;
1021         int n;
1022
1023         /* can't be done in parallel with OpenGL */
1024         for (n = 0; n < totnode; n++) {
1025                 node = nodes[n];
1026
1027                 if (node->flag & PBVH_RebuildDrawBuffers) {
1028                         GPU_free_buffers(node->draw_buffers);
1029                         switch (bvh->type) {
1030                                 case PBVH_GRIDS:
1031                                         node->draw_buffers =
1032                                             GPU_build_grid_buffers(node->prim_indices,
1033                                                                    node->totprim,
1034                                                                    bvh->grid_hidden,
1035                                                                    bvh->gridkey.grid_size);
1036                                         break;
1037                                 case PBVH_FACES:
1038                                         node->draw_buffers =
1039                                             GPU_build_mesh_buffers(node->face_vert_indices,
1040                                                                    bvh->faces, bvh->verts,
1041                                                                    node->prim_indices,
1042                                                                    node->totprim);
1043                                         break;
1044                         }
1045  
1046                         node->flag &= ~PBVH_RebuildDrawBuffers;
1047                 }
1048
1049                 if (node->flag & PBVH_UpdateDrawBuffers) {
1050                         switch (bvh->type) {
1051                                 case PBVH_GRIDS:
1052                                         GPU_update_grid_buffers(node->draw_buffers,
1053                                                                 bvh->grids,
1054                                                                 bvh->grid_flag_mats,
1055                                                                 node->prim_indices,
1056                                                                 node->totprim,
1057                                                                 &bvh->gridkey,
1058                                                                 bvh->show_diffuse_color);
1059                                         break;
1060                                 case PBVH_FACES:
1061                                         GPU_update_mesh_buffers(node->draw_buffers,
1062                                                                 bvh->verts,
1063                                                                 node->vert_indices,
1064                                                                 node->uniq_verts +
1065                                                                 node->face_verts,
1066                                                                 CustomData_get_layer(bvh->vdata,
1067                                                                                      CD_PAINT_MASK),
1068                                                                 node->face_vert_indices,
1069                                                                 bvh->show_diffuse_color);
1070                                         break;
1071                         }
1072
1073                         node->flag &= ~PBVH_UpdateDrawBuffers;
1074                 }
1075         }
1076 }
1077
1078 static int pbvh_flush_bb(PBVH *bvh, PBVHNode *node, int flag)
1079 {
1080         int update = 0;
1081
1082         /* difficult to multithread well, we just do single threaded recursive */
1083         if (node->flag & PBVH_Leaf) {
1084                 if (flag & PBVH_UpdateBB) {
1085                         update |= (node->flag & PBVH_UpdateBB);
1086                         node->flag &= ~PBVH_UpdateBB;
1087                 }
1088
1089                 if (flag & PBVH_UpdateOriginalBB) {
1090                         update |= (node->flag & PBVH_UpdateOriginalBB);
1091                         node->flag &= ~PBVH_UpdateOriginalBB;
1092                 }
1093
1094                 return update;
1095         }
1096         else {
1097                 update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset, flag);
1098                 update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset + 1, flag);
1099
1100                 if (update & PBVH_UpdateBB)
1101                         update_node_vb(bvh, node);
1102                 if (update & PBVH_UpdateOriginalBB)
1103                         node->orig_vb = node->vb;
1104         }
1105
1106         return update;
1107 }
1108
1109 void BLI_pbvh_update(PBVH *bvh, int flag, float (*face_nors)[3])
1110 {
1111         PBVHNode **nodes;
1112         int totnode;
1113
1114         if (!bvh->nodes)
1115                 return;
1116
1117         BLI_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(flag),
1118                                &nodes, &totnode);
1119
1120         if (flag & PBVH_UpdateNormals)
1121                 pbvh_update_normals(bvh, nodes, totnode, face_nors);
1122
1123         if (flag & (PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateRedraw))
1124                 pbvh_update_BB_redraw(bvh, nodes, totnode, flag);
1125
1126         if (flag & (PBVH_UpdateBB | PBVH_UpdateOriginalBB))
1127                 pbvh_flush_bb(bvh, bvh->nodes, flag);
1128
1129         if (nodes) MEM_freeN(nodes);
1130 }
1131
1132 void BLI_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3])
1133 {
1134         PBVHIter iter;
1135         PBVHNode *node;
1136         BB bb;
1137
1138         BB_reset(&bb);
1139
1140         pbvh_iter_begin(&iter, bvh, NULL, NULL);
1141
1142         while ((node = pbvh_iter_next(&iter)))
1143                 if (node->flag & PBVH_UpdateRedraw)
1144                         BB_expand_with_bb(&bb, &node->vb);
1145
1146         pbvh_iter_end(&iter);
1147
1148         copy_v3_v3(bb_min, bb.bmin);
1149         copy_v3_v3(bb_max, bb.bmax);
1150 }
1151
1152 void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *totface)
1153 {
1154         PBVHIter iter;
1155         PBVHNode *node;
1156         GHashIterator *hiter;
1157         GHash *map;
1158         void *face, **faces;
1159         unsigned i;
1160         int tot;
1161
1162         map = BLI_ghash_ptr_new("pbvh_get_grid_updates gh");
1163
1164         pbvh_iter_begin(&iter, bvh, NULL, NULL);
1165
1166         while ((node = pbvh_iter_next(&iter))) {
1167                 if (node->flag & PBVH_UpdateNormals) {
1168                         for (i = 0; i < node->totprim; ++i) {
1169                                 face = bvh->gridfaces[node->prim_indices[i]];
1170                                 if (!BLI_ghash_lookup(map, face))
1171                                         BLI_ghash_insert(map, face, face);
1172                         }
1173
1174                         if (clear)
1175                                 node->flag &= ~PBVH_UpdateNormals;
1176                 }
1177         }
1178
1179         pbvh_iter_end(&iter);
1180         
1181         tot = BLI_ghash_size(map);
1182         if (tot == 0) {
1183                 *totface = 0;
1184                 *gridfaces = NULL;
1185                 BLI_ghash_free(map, NULL, NULL);
1186                 return;
1187         }
1188
1189         faces = MEM_callocN(sizeof(void *) * tot, "PBVH Grid Faces");
1190
1191         for (hiter = BLI_ghashIterator_new(map), i = 0;
1192              !BLI_ghashIterator_isDone(hiter);
1193              BLI_ghashIterator_step(hiter), ++i)
1194         {
1195                 faces[i] = BLI_ghashIterator_getKey(hiter);
1196         }
1197
1198         BLI_ghashIterator_free(hiter);
1199
1200         BLI_ghash_free(map, NULL, NULL);
1201
1202         *totface = tot;
1203         *gridfaces = faces;
1204 }
1205
1206 /***************************** PBVH Access ***********************************/
1207
1208 PBVHType BLI_pbvh_type(const PBVH *bvh)
1209 {
1210         return bvh->type;
1211 }
1212
1213 BLI_bitmap *BLI_pbvh_grid_hidden(const PBVH *bvh)
1214 {
1215         BLI_assert(bvh->type == PBVH_GRIDS);
1216         return bvh->grid_hidden;
1217 }
1218
1219 void BLI_pbvh_get_grid_key(const PBVH *bvh, CCGKey *key)
1220 {
1221         BLI_assert(bvh->type == PBVH_GRIDS);
1222         *key = bvh->gridkey;
1223 }
1224
1225 /***************************** Node Access ***********************************/
1226
1227 void BLI_pbvh_node_mark_update(PBVHNode *node)
1228 {
1229         node->flag |= PBVH_UpdateNormals | PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw;
1230 }
1231
1232 void BLI_pbvh_node_mark_rebuild_draw(PBVHNode *node)
1233 {
1234         node->flag |= PBVH_RebuildDrawBuffers | PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw;
1235 }
1236
1237 void BLI_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden)
1238 {
1239         BLI_assert(node->flag & PBVH_Leaf);
1240         
1241         if (fully_hidden)
1242                 node->flag |= PBVH_FullyHidden;
1243         else
1244                 node->flag &= ~PBVH_FullyHidden;
1245 }
1246
1247 void BLI_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node, int **vert_indices, MVert **verts)
1248 {
1249         if (vert_indices) *vert_indices = node->vert_indices;
1250         if (verts) *verts = bvh->verts;
1251 }
1252
1253 void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node, int *uniquevert, int *totvert)
1254 {
1255         int tot;
1256         
1257         switch (bvh->type) {
1258                 case PBVH_GRIDS:
1259                         tot = node->totprim * bvh->gridkey.grid_area;
1260                         if (totvert) *totvert = tot;
1261                         if (uniquevert) *uniquevert = tot;
1262                         break;
1263                 case PBVH_FACES:
1264                         if (totvert) *totvert = node->uniq_verts + node->face_verts;
1265                         if (uniquevert) *uniquevert = node->uniq_verts;
1266                         break;
1267         }
1268 }
1269
1270 void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node, int **grid_indices, int *totgrid, int *maxgrid, int *gridsize, CCGElem ***griddata, DMGridAdjacency **gridadj)
1271 {
1272         switch (bvh->type) {
1273                 case PBVH_GRIDS:
1274                         if (grid_indices) *grid_indices = node->prim_indices;
1275                         if (totgrid) *totgrid = node->totprim;
1276                         if (maxgrid) *maxgrid = bvh->totgrid;
1277                         if (gridsize) *gridsize = bvh->gridkey.grid_size;
1278                         if (griddata) *griddata = bvh->grids;
1279                         if (gridadj) *gridadj = bvh->gridadj;
1280                         break;
1281                 case PBVH_FACES:
1282                         if (grid_indices) *grid_indices = NULL;
1283                         if (totgrid) *totgrid = 0;
1284                         if (maxgrid) *maxgrid = 0;
1285                         if (gridsize) *gridsize = 0;
1286                         if (griddata) *griddata = NULL;
1287                         if (gridadj) *gridadj = NULL;
1288                         break;
1289         }
1290 }
1291
1292 void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
1293 {
1294         copy_v3_v3(bb_min, node->vb.bmin);
1295         copy_v3_v3(bb_max, node->vb.bmax);
1296 }
1297
1298 void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
1299 {
1300         copy_v3_v3(bb_min, node->orig_vb.bmin);
1301         copy_v3_v3(bb_max, node->orig_vb.bmax);
1302 }
1303
1304 void BLI_pbvh_node_get_proxies(PBVHNode *node, PBVHProxyNode **proxies, int *proxy_count)
1305 {
1306         if (node->proxy_count > 0) {
1307                 if (proxies) *proxies = node->proxies;
1308                 if (proxy_count) *proxy_count = node->proxy_count;
1309         }
1310         else {
1311                 if (proxies) *proxies = 0;
1312                 if (proxy_count) *proxy_count = 0;
1313         }
1314 }
1315
1316 /********************************* Raycast ***********************************/
1317
1318 typedef struct {
1319         IsectRayAABBData ray;
1320         int original;
1321 } RaycastData;
1322
1323 static int ray_aabb_intersect(PBVHNode *node, void *data_v)
1324 {
1325         RaycastData *rcd = data_v;
1326         float bb_min[3], bb_max[3];
1327
1328         if (rcd->original)
1329                 BLI_pbvh_node_get_original_BB(node, bb_min, bb_max);
1330         else
1331                 BLI_pbvh_node_get_BB(node, bb_min, bb_max);
1332
1333         return isect_ray_aabb(&rcd->ray, bb_min, bb_max, &node->tmin);
1334 }
1335
1336 void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitOccludedCallback cb, void *data,
1337                       const float ray_start[3], const float ray_normal[3],
1338                       int original)
1339 {
1340         RaycastData rcd;
1341
1342         isect_ray_aabb_initialize(&rcd.ray, ray_start, ray_normal);
1343         rcd.original = original;
1344
1345         BLI_pbvh_search_callback_occluded(bvh, ray_aabb_intersect, &rcd, cb, data);
1346 }
1347
1348 static int ray_face_intersection(const float ray_start[3],
1349                                  const float ray_normal[3],
1350                                  const float *t0, const float *t1,
1351                                  const float *t2, const float *t3,
1352                                  float *fdist)
1353 {
1354         float dist;
1355
1356         if ((isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t1, t2, &dist, NULL, 0.1f) && dist < *fdist) ||
1357             (t3 && isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t2, t3, &dist, NULL, 0.1f) && dist < *fdist))
1358         {
1359                 *fdist = dist;
1360                 return 1;
1361         }
1362         else {
1363                 return 0;
1364         }
1365 }
1366
1367 static int pbvh_faces_node_raycast(PBVH *bvh, const PBVHNode *node,
1368                                    float (*origco)[3],
1369                                    const float ray_start[3],
1370                                    const float ray_normal[3], float *dist)
1371 {
1372         const MVert *vert = bvh->verts;
1373         const int *faces = node->prim_indices;
1374         int i, hit = 0, totface = node->totprim;
1375
1376         for (i = 0; i < totface; ++i) {
1377                 const MFace *f = bvh->faces + faces[i];
1378                 const int *face_verts = node->face_vert_indices[i];
1379
1380                 if (paint_is_face_hidden(f, vert))
1381                         continue;
1382
1383                 if (origco) {
1384                         /* intersect with backuped original coordinates */
1385                         hit |= ray_face_intersection(ray_start, ray_normal,
1386                                                      origco[face_verts[0]],
1387                                                      origco[face_verts[1]],
1388                                                      origco[face_verts[2]],
1389                                                      f->v4 ? origco[face_verts[3]] : NULL,
1390                                                      dist);
1391                 }
1392                 else {
1393                         /* intersect with current coordinates */
1394                         hit |= ray_face_intersection(ray_start, ray_normal,
1395                                                      vert[f->v1].co,
1396                                                      vert[f->v2].co,
1397                                                      vert[f->v3].co,
1398                                                      f->v4 ? vert[f->v4].co : NULL,
1399                                                      dist);
1400                 }
1401         }
1402
1403         return hit;
1404 }
1405
1406 static int pbvh_grids_node_raycast(PBVH *bvh, PBVHNode *node,
1407                                    float (*origco)[3],
1408                                    const float ray_start[3],
1409                                    const float ray_normal[3], float *dist)
1410 {
1411         int totgrid = node->totprim;
1412         int gridsize = bvh->gridkey.grid_size;
1413         int i, x, y, hit = 0;
1414
1415         for (i = 0; i < totgrid; ++i) {
1416                 CCGElem *grid = bvh->grids[node->prim_indices[i]];
1417                 BLI_bitmap gh;
1418
1419                 if (!grid)
1420                         continue;
1421
1422                 gh = bvh->grid_hidden[node->prim_indices[i]];
1423
1424                 for (y = 0; y < gridsize - 1; ++y) {
1425                         for (x = 0; x < gridsize - 1; ++x) {
1426                                 /* check if grid face is hidden */
1427                                 if (gh) {
1428                                         if (paint_is_grid_face_hidden(gh, gridsize, x, y))
1429                                                 continue;
1430                                 }
1431
1432                                 if (origco) {
1433                                         hit |= ray_face_intersection(ray_start, ray_normal,
1434                                                                      origco[y * gridsize + x],
1435                                                                      origco[y * gridsize + x + 1],
1436                                                                      origco[(y + 1) * gridsize + x + 1],
1437                                                                      origco[(y + 1) * gridsize + x],
1438                                                                      dist);
1439                                 }
1440                                 else {
1441                                         hit |= ray_face_intersection(ray_start, ray_normal,
1442                                                                      CCG_grid_elem_co(&bvh->gridkey, grid, x, y),
1443                                                                      CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y),
1444                                                                      CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y + 1),
1445                                                                      CCG_grid_elem_co(&bvh->gridkey, grid, x, y + 1),
1446                                                                      dist);
1447                                 }
1448                         }
1449                 }
1450
1451                 if (origco)
1452                         origco += gridsize * gridsize;
1453         }
1454
1455         return hit;
1456 }
1457
1458 int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
1459                           const float ray_start[3], const float ray_normal[3],
1460                           float *dist)
1461 {
1462         int hit = 0;
1463
1464         if (node->flag & PBVH_FullyHidden)
1465                 return 0;
1466
1467         switch (bvh->type) {
1468                 case PBVH_FACES:
1469                         hit |= pbvh_faces_node_raycast(bvh, node, origco,
1470                                                        ray_start, ray_normal, dist);
1471                         break;
1472                 case PBVH_GRIDS:
1473                         hit |= pbvh_grids_node_raycast(bvh, node, origco,
1474                                                        ray_start, ray_normal, dist);
1475                         break;
1476         }
1477
1478         return hit;
1479 }
1480
1481 //#include <GL/glew.h>
1482
1483 void BLI_pbvh_node_draw(PBVHNode *node, void *setMaterial)
1484 {
1485 #if 0
1486         /* XXX: Just some quick code to show leaf nodes in different colors */
1487         float col[3]; int i;
1488
1489         if (0) { //is_partial) {
1490                 col[0] = (rand() / (float)RAND_MAX); col[1] = col[2] = 0.6;
1491         }
1492         else {
1493                 srand((long long)node);
1494                 for (i = 0; i < 3; ++i)
1495                         col[i] = (rand() / (float)RAND_MAX) * 0.3 + 0.7;
1496         }
1497         glMaterialfv(GL_FRONT_AND_BACK, GL_DIFFUSE, col);
1498
1499         glColor3f(1, 0, 0);
1500 #endif
1501
1502         if (!(node->flag & PBVH_FullyHidden))
1503                 GPU_draw_buffers(node->draw_buffers, setMaterial);
1504 }
1505
1506 typedef enum {
1507         ISECT_INSIDE,
1508         ISECT_OUTSIDE,
1509         ISECT_INTERSECT
1510 } PlaneAABBIsect;
1511
1512 /* Adapted from:
1513  * http://www.gamedev.net/community/forums/topic.asp?topic_id=512123
1514  * Returns true if the AABB is at least partially within the frustum
1515  * (ok, not a real frustum), false otherwise.
1516  */
1517 static PlaneAABBIsect test_planes_aabb(const float bb_min[3],
1518                                        const float bb_max[3],
1519                                        const float (*planes)[4])
1520 {
1521         float vmin[3], vmax[3];
1522         PlaneAABBIsect ret = ISECT_INSIDE;
1523         int i, axis;
1524         
1525         for (i = 0; i < 4; ++i) {
1526                 for (axis = 0; axis < 3; ++axis) {
1527                         if (planes[i][axis] > 0) {
1528                                 vmin[axis] = bb_min[axis];
1529                                 vmax[axis] = bb_max[axis];
1530                         }
1531                         else {
1532                                 vmin[axis] = bb_max[axis];
1533                                 vmax[axis] = bb_min[axis];
1534                         }
1535                 }
1536                 
1537                 if (dot_v3v3(planes[i], vmin) + planes[i][3] > 0)
1538                         return ISECT_OUTSIDE;
1539                 else if (dot_v3v3(planes[i], vmax) + planes[i][3] >= 0)
1540                         ret = ISECT_INTERSECT;
1541         }
1542
1543         return ret;
1544 }
1545
1546 int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data)
1547 {
1548         float bb_min[3], bb_max[3];
1549         
1550         BLI_pbvh_node_get_BB(node, bb_min, bb_max);
1551         return test_planes_aabb(bb_min, bb_max, data) != ISECT_OUTSIDE;
1552 }
1553
1554 int BLI_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data)
1555 {
1556         float bb_min[3], bb_max[3];
1557         
1558         BLI_pbvh_node_get_BB(node, bb_min, bb_max);
1559         return test_planes_aabb(bb_min, bb_max, data) != ISECT_INSIDE;
1560 }
1561
1562 static void pbvh_node_check_diffuse_changed(PBVH *bvh, PBVHNode *node)
1563 {
1564         if (!node->draw_buffers)
1565                 return;
1566
1567         if (GPU_buffers_diffuse_changed(node->draw_buffers, bvh->show_diffuse_color))
1568                 node->flag |= PBVH_UpdateDrawBuffers;
1569 }
1570
1571 void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3],
1572                    DMSetMaterial setMaterial)
1573 {
1574         PBVHNode **nodes;
1575         int a, totnode;
1576
1577         for (a = 0; a < bvh->totnode; a++)
1578                 pbvh_node_check_diffuse_changed(bvh, &bvh->nodes[a]);
1579
1580         BLI_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(PBVH_UpdateNormals | PBVH_UpdateDrawBuffers),
1581                                &nodes, &totnode);
1582
1583         pbvh_update_normals(bvh, nodes, totnode, face_nors);
1584         pbvh_update_draw_buffers(bvh, nodes, totnode);
1585
1586         if (nodes) MEM_freeN(nodes);
1587
1588         if (planes) {
1589                 BLI_pbvh_search_callback(bvh, BLI_pbvh_node_planes_contain_AABB,
1590                                          planes, BLI_pbvh_node_draw, setMaterial);
1591         }
1592         else {
1593                 BLI_pbvh_search_callback(bvh, NULL, NULL, BLI_pbvh_node_draw, setMaterial);
1594         }
1595 }
1596
1597 void BLI_pbvh_grids_update(PBVH *bvh, CCGElem **grids, DMGridAdjacency *gridadj, void **gridfaces,
1598                            DMFlagMat *flagmats, BLI_bitmap *grid_hidden)
1599 {
1600         int a;
1601
1602         bvh->grids = grids;
1603         bvh->gridadj = gridadj;
1604         bvh->gridfaces = gridfaces;
1605
1606         if (flagmats != bvh->grid_flag_mats || bvh->grid_hidden != grid_hidden) {
1607                 bvh->grid_flag_mats = flagmats;
1608                 bvh->grid_hidden = grid_hidden;
1609
1610                 for (a = 0; a < bvh->totnode; ++a)
1611                         BLI_pbvh_node_mark_rebuild_draw(&bvh->nodes[a]);
1612         }
1613 }
1614
1615 /* Get the node's displacement layer, creating it if necessary */
1616 float *BLI_pbvh_node_layer_disp_get(PBVH *bvh, PBVHNode *node)
1617 {
1618         if (!node->layer_disp) {
1619                 int totvert = 0;
1620                 BLI_pbvh_node_num_verts(bvh, node, &totvert, NULL);
1621                 node->layer_disp = MEM_callocN(sizeof(float) * totvert, "layer disp");
1622         }
1623         return node->layer_disp;
1624 }
1625
1626 /* If the node has a displacement layer, free it and set to null */
1627 void BLI_pbvh_node_layer_disp_free(PBVHNode *node)
1628 {
1629         if (node->layer_disp) {
1630                 MEM_freeN(node->layer_disp);
1631                 node->layer_disp = NULL;
1632         }
1633 }
1634
1635 float (*BLI_pbvh_get_vertCos(PBVH * pbvh))[3]
1636 {
1637         int a;
1638         float (*vertCos)[3] = NULL;
1639
1640         if (pbvh->verts) {
1641                 float *co;
1642                 MVert *mvert = pbvh->verts;
1643
1644                 vertCos = MEM_callocN(3 * pbvh->totvert * sizeof(float), "BLI_pbvh_get_vertCoords");
1645                 co = (float *)vertCos;
1646
1647                 for (a = 0; a < pbvh->totvert; a++, mvert++, co += 3) {
1648                         copy_v3_v3(co, mvert->co);
1649                 }
1650         }
1651
1652         return vertCos;
1653 }
1654
1655 void BLI_pbvh_apply_vertCos(PBVH *pbvh, float (*vertCos)[3])
1656 {
1657         int a;
1658
1659         if (!pbvh->deformed) {
1660                 if (pbvh->verts) {
1661                         /* if pbvh is not already deformed, verts/faces points to the */
1662                         /* original data and applying new coords to this arrays would lead to */
1663                         /* unneeded deformation -- duplicate verts/faces to avoid this */
1664
1665                         pbvh->verts = MEM_dupallocN(pbvh->verts);
1666                         pbvh->faces = MEM_dupallocN(pbvh->faces);
1667
1668                         pbvh->deformed = 1;
1669                 }
1670         }
1671
1672         if (pbvh->verts) {
1673                 MVert *mvert = pbvh->verts;
1674                 /* copy new verts coords */
1675                 for (a = 0; a < pbvh->totvert; ++a, ++mvert) {
1676                         copy_v3_v3(mvert->co, vertCos[a]);
1677                         mvert->flag |= ME_VERT_PBVH_UPDATE;
1678                 }
1679
1680                 /* coordinates are new -- normals should also be updated */
1681                 BKE_mesh_calc_normals_tessface(pbvh->verts, pbvh->totvert, pbvh->faces, pbvh->totprim, NULL);
1682
1683                 for (a = 0; a < pbvh->totnode; ++a)
1684                         BLI_pbvh_node_mark_update(&pbvh->nodes[a]);
1685
1686                 BLI_pbvh_update(pbvh, PBVH_UpdateBB, NULL);
1687                 BLI_pbvh_update(pbvh, PBVH_UpdateOriginalBB, NULL);
1688
1689         }
1690 }
1691
1692 int BLI_pbvh_isDeformed(PBVH *pbvh)
1693 {
1694         return pbvh->deformed;
1695 }
1696 /* Proxies */
1697
1698 PBVHProxyNode *BLI_pbvh_node_add_proxy(PBVH *bvh, PBVHNode *node)
1699 {
1700         int index, totverts;
1701
1702         #pragma omp critical
1703         {
1704
1705                 index = node->proxy_count;
1706
1707                 node->proxy_count++;
1708
1709                 if (node->proxies)
1710                         node->proxies = MEM_reallocN(node->proxies, node->proxy_count * sizeof(PBVHProxyNode));
1711                 else
1712                         node->proxies = MEM_mallocN(sizeof(PBVHProxyNode), "PBVHNodeProxy");
1713
1714                 BLI_pbvh_node_num_verts(bvh, node, &totverts, NULL);
1715                 node->proxies[index].co = MEM_callocN(sizeof(float[3]) * totverts, "PBVHNodeProxy.co");
1716         }
1717
1718         return node->proxies + index;
1719 }
1720
1721 void BLI_pbvh_node_free_proxies(PBVHNode *node)
1722 {
1723         #pragma omp critical
1724         {
1725                 int p;
1726
1727                 for (p = 0; p < node->proxy_count; p++) {
1728                         MEM_freeN(node->proxies[p].co);
1729                         node->proxies[p].co = 0;
1730                 }
1731
1732                 MEM_freeN(node->proxies);
1733                 node->proxies = 0;
1734
1735                 node->proxy_count = 0;
1736         }
1737 }
1738
1739 void BLI_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***r_array,  int *r_tot)
1740 {
1741         PBVHNode **array = NULL, **newarray, *node;
1742         int tot = 0, space = 0;
1743         int n;
1744
1745         for (n = 0; n < pbvh->totnode; n++) {
1746                 node = pbvh->nodes + n;
1747
1748                 if (node->proxy_count > 0) {
1749                         if (tot == space) {
1750                                 /* resize array if needed */
1751                                 space = (tot == 0) ? 32 : space * 2;
1752                                 newarray = MEM_callocN(sizeof(PBVHNode) * space, "BLI_pbvh_gather_proxies");
1753
1754                                 if (array) {
1755                                         memcpy(newarray, array, sizeof(PBVHNode) * tot);
1756                                         MEM_freeN(array);
1757                                 }
1758
1759                                 array = newarray;
1760                         }
1761
1762                         array[tot] = node;
1763                         tot++;
1764                 }
1765         }
1766
1767         if (tot == 0 && array) {
1768                 MEM_freeN(array);
1769                 array = NULL;
1770         }
1771
1772         *r_array = array;
1773         *r_tot = tot;
1774 }
1775
1776 void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node,
1777                            PBVHVertexIter *vi, int mode)
1778 {
1779         struct CCGElem **grids;
1780         struct MVert *verts;
1781         int *grid_indices, *vert_indices;
1782         int totgrid, gridsize, uniq_verts, totvert;
1783         
1784         vi->grid = 0;
1785         vi->no = 0;
1786         vi->fno = 0;
1787         vi->mvert = 0;
1788         
1789         BLI_pbvh_node_get_grids(bvh, node, &grid_indices, &totgrid, NULL, &gridsize, &grids, NULL);
1790         BLI_pbvh_node_num_verts(bvh, node, &uniq_verts, &totvert);
1791         BLI_pbvh_node_get_verts(bvh, node, &vert_indices, &verts);
1792         vi->key = &bvh->gridkey;
1793         
1794         vi->grids = grids;
1795         vi->grid_indices = grid_indices;
1796         vi->totgrid = (grids) ? totgrid : 1;
1797         vi->gridsize = gridsize;
1798         
1799         if (mode == PBVH_ITER_ALL)
1800                 vi->totvert = totvert;
1801         else
1802                 vi->totvert = uniq_verts;
1803         vi->vert_indices = vert_indices;
1804         vi->mverts = verts;
1805
1806         vi->gh = NULL;
1807         if (vi->grids && mode == PBVH_ITER_UNIQUE)
1808                 vi->grid_hidden = bvh->grid_hidden;
1809
1810         vi->mask = NULL;
1811         if (!vi->grids)
1812                 vi->vmask = CustomData_get_layer(bvh->vdata, CD_PAINT_MASK);
1813 }
1814
1815 void pbvh_show_diffuse_color_set(PBVH *bvh, int show_diffuse_color)
1816 {
1817         bvh->show_diffuse_color = show_diffuse_color;
1818 }