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