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