ClangFormat: apply to source, most of intern
[blender.git] / source / blender / blenkernel / intern / pbvh.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file
18  * \ingroup bli
19  */
20
21 #include "MEM_guardedalloc.h"
22
23 #include "BLI_utildefines.h"
24
25 #include "BLI_bitmap.h"
26 #include "BLI_math.h"
27 #include "BLI_ghash.h"
28 #include "BLI_task.h"
29
30 #include "DNA_meshdata_types.h"
31
32 #include "BKE_pbvh.h"
33 #include "BKE_ccg.h"
34 #include "BKE_subsurf.h"
35 #include "BKE_DerivedMesh.h"
36 #include "BKE_mesh.h" /* for BKE_mesh_calc_normals */
37 #include "BKE_paint.h"
38
39 #include "GPU_buffers.h"
40 #include "GPU_immediate.h"
41
42 #include "bmesh.h"
43
44 #include "atomic_ops.h"
45
46 #include "pbvh_intern.h"
47
48 #include <limits.h>
49
50 #define LEAF_LIMIT 10000
51
52 //#define PERFCNTRS
53
54 #define STACK_FIXED_DEPTH 100
55
56 #define PBVH_THREADED_LIMIT 4
57
58 typedef struct PBVHStack {
59   PBVHNode *node;
60   bool revisiting;
61 } PBVHStack;
62
63 typedef struct PBVHIter {
64   PBVH *bvh;
65   BKE_pbvh_SearchCallback scb;
66   void *search_data;
67
68   PBVHStack *stack;
69   int stacksize;
70
71   PBVHStack stackfixed[STACK_FIXED_DEPTH];
72   int stackspace;
73 } PBVHIter;
74
75 void BB_reset(BB *bb)
76 {
77   bb->bmin[0] = bb->bmin[1] = bb->bmin[2] = FLT_MAX;
78   bb->bmax[0] = bb->bmax[1] = bb->bmax[2] = -FLT_MAX;
79 }
80
81 /* Expand the bounding box to include a new coordinate */
82 void BB_expand(BB *bb, const float co[3])
83 {
84   for (int i = 0; i < 3; ++i) {
85     bb->bmin[i] = min_ff(bb->bmin[i], co[i]);
86     bb->bmax[i] = max_ff(bb->bmax[i], co[i]);
87   }
88 }
89
90 /* Expand the bounding box to include another bounding box */
91 void BB_expand_with_bb(BB *bb, BB *bb2)
92 {
93   for (int i = 0; i < 3; ++i) {
94     bb->bmin[i] = min_ff(bb->bmin[i], bb2->bmin[i]);
95     bb->bmax[i] = max_ff(bb->bmax[i], bb2->bmax[i]);
96   }
97 }
98
99 /* Return 0, 1, or 2 to indicate the widest axis of the bounding box */
100 int BB_widest_axis(const BB *bb)
101 {
102   float dim[3];
103
104   for (int i = 0; i < 3; ++i)
105     dim[i] = bb->bmax[i] - bb->bmin[i];
106
107   if (dim[0] > dim[1]) {
108     if (dim[0] > dim[2])
109       return 0;
110     else
111       return 2;
112   }
113   else {
114     if (dim[1] > dim[2])
115       return 1;
116     else
117       return 2;
118   }
119 }
120
121 void BBC_update_centroid(BBC *bbc)
122 {
123   for (int i = 0; i < 3; ++i)
124     bbc->bcentroid[i] = (bbc->bmin[i] + bbc->bmax[i]) * 0.5f;
125 }
126
127 /* Not recursive */
128 static void update_node_vb(PBVH *bvh, PBVHNode *node)
129 {
130   BB vb;
131
132   BB_reset(&vb);
133
134   if (node->flag & PBVH_Leaf) {
135     PBVHVertexIter vd;
136
137     BKE_pbvh_vertex_iter_begin(bvh, node, vd, PBVH_ITER_ALL)
138     {
139       BB_expand(&vb, vd.co);
140     }
141     BKE_pbvh_vertex_iter_end;
142   }
143   else {
144     BB_expand_with_bb(&vb, &bvh->nodes[node->children_offset].vb);
145     BB_expand_with_bb(&vb, &bvh->nodes[node->children_offset + 1].vb);
146   }
147
148   node->vb = vb;
149 }
150
151 //void BKE_pbvh_node_BB_reset(PBVHNode *node)
152 //{
153 //  BB_reset(&node->vb);
154 //}
155 //
156 //void BKE_pbvh_node_BB_expand(PBVHNode *node, float co[3])
157 //{
158 //  BB_expand(&node->vb, co);
159 //}
160
161 static bool face_materials_match(const MPoly *f1, const MPoly *f2)
162 {
163   return ((f1->flag & ME_SMOOTH) == (f2->flag & ME_SMOOTH) && (f1->mat_nr == f2->mat_nr));
164 }
165
166 static bool grid_materials_match(const DMFlagMat *f1, const DMFlagMat *f2)
167 {
168   return ((f1->flag & ME_SMOOTH) == (f2->flag & ME_SMOOTH) && (f1->mat_nr == f2->mat_nr));
169 }
170
171 /* Adapted from BLI_kdopbvh.c */
172 /* Returns the index of the first element on the right of the partition */
173 static int partition_indices(int *prim_indices, int lo, int hi, int axis, float mid, BBC *prim_bbc)
174 {
175   int i = lo, j = hi;
176   for (;;) {
177     for (; prim_bbc[prim_indices[i]].bcentroid[axis] < mid; i++)
178       ;
179     for (; mid < prim_bbc[prim_indices[j]].bcentroid[axis]; j--)
180       ;
181
182     if (!(i < j))
183       return i;
184
185     SWAP(int, prim_indices[i], prim_indices[j]);
186     i++;
187   }
188 }
189
190 /* Returns the index of the first element on the right of the partition */
191 static int partition_indices_material(PBVH *bvh, int lo, int hi)
192 {
193   const MPoly *mpoly = bvh->mpoly;
194   const MLoopTri *looptri = bvh->looptri;
195   const DMFlagMat *flagmats = bvh->grid_flag_mats;
196   const int *indices = bvh->prim_indices;
197   const void *first;
198   int i = lo, j = hi;
199
200   if (bvh->looptri)
201     first = &mpoly[looptri[bvh->prim_indices[lo]].poly];
202   else
203     first = &flagmats[bvh->prim_indices[lo]];
204
205   for (;;) {
206     if (bvh->looptri) {
207       for (; face_materials_match(first, &mpoly[looptri[indices[i]].poly]); i++)
208         ;
209       for (; !face_materials_match(first, &mpoly[looptri[indices[j]].poly]); j--)
210         ;
211     }
212     else {
213       for (; grid_materials_match(first, &flagmats[indices[i]]); i++)
214         ;
215       for (; !grid_materials_match(first, &flagmats[indices[j]]); j--)
216         ;
217     }
218
219     if (!(i < j))
220       return i;
221
222     SWAP(int, bvh->prim_indices[i], bvh->prim_indices[j]);
223     i++;
224   }
225 }
226
227 void pbvh_grow_nodes(PBVH *bvh, int totnode)
228 {
229   if (UNLIKELY(totnode > bvh->node_mem_count)) {
230     bvh->node_mem_count = bvh->node_mem_count + (bvh->node_mem_count / 3);
231     if (bvh->node_mem_count < totnode)
232       bvh->node_mem_count = totnode;
233     bvh->nodes = MEM_recallocN(bvh->nodes, sizeof(PBVHNode) * bvh->node_mem_count);
234   }
235
236   bvh->totnode = totnode;
237 }
238
239 /* Add a vertex to the map, with a positive value for unique vertices and
240  * a negative value for additional vertices */
241 static int map_insert_vert(
242     PBVH *bvh, GHash *map, unsigned int *face_verts, unsigned int *uniq_verts, int vertex)
243 {
244   void *key, **value_p;
245
246   key = POINTER_FROM_INT(vertex);
247   if (!BLI_ghash_ensure_p(map, key, &value_p)) {
248     int value_i;
249     if (BLI_BITMAP_TEST(bvh->vert_bitmap, vertex) == 0) {
250       BLI_BITMAP_ENABLE(bvh->vert_bitmap, vertex);
251       value_i = *uniq_verts;
252       (*uniq_verts)++;
253     }
254     else {
255       value_i = ~(*face_verts);
256       (*face_verts)++;
257     }
258     *value_p = POINTER_FROM_INT(value_i);
259     return value_i;
260   }
261   else {
262     return POINTER_AS_INT(*value_p);
263   }
264 }
265
266 /* Find vertices used by the faces in this node and update the draw buffers */
267 static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node)
268 {
269   bool has_visible = false;
270
271   node->uniq_verts = node->face_verts = 0;
272   const int totface = node->totprim;
273
274   /* reserve size is rough guess */
275   GHash *map = BLI_ghash_int_new_ex("build_mesh_leaf_node gh", 2 * totface);
276
277   int(*face_vert_indices)[3] = MEM_mallocN(sizeof(int[3]) * totface, "bvh node face vert indices");
278
279   node->face_vert_indices = (const int(*)[3])face_vert_indices;
280
281   for (int i = 0; i < totface; ++i) {
282     const MLoopTri *lt = &bvh->looptri[node->prim_indices[i]];
283     for (int j = 0; j < 3; ++j) {
284       face_vert_indices[i][j] = map_insert_vert(
285           bvh, map, &node->face_verts, &node->uniq_verts, bvh->mloop[lt->tri[j]].v);
286     }
287
288     if (!paint_is_face_hidden(lt, bvh->verts, bvh->mloop)) {
289       has_visible = true;
290     }
291   }
292
293   int *vert_indices = MEM_callocN(sizeof(int) * (node->uniq_verts + node->face_verts),
294                                   "bvh node vert indices");
295   node->vert_indices = vert_indices;
296
297   /* Build the vertex list, unique verts first */
298   GHashIterator gh_iter;
299   GHASH_ITER (gh_iter, map) {
300     void *value = BLI_ghashIterator_getValue(&gh_iter);
301     int ndx = POINTER_AS_INT(value);
302
303     if (ndx < 0)
304       ndx = -ndx + node->uniq_verts - 1;
305
306     vert_indices[ndx] = POINTER_AS_INT(BLI_ghashIterator_getKey(&gh_iter));
307   }
308
309   for (int i = 0; i < totface; ++i) {
310     const int sides = 3;
311
312     for (int j = 0; j < sides; ++j) {
313       if (face_vert_indices[i][j] < 0)
314         face_vert_indices[i][j] = -face_vert_indices[i][j] + node->uniq_verts - 1;
315     }
316   }
317
318   BKE_pbvh_node_mark_rebuild_draw(node);
319
320   BKE_pbvh_node_fully_hidden_set(node, !has_visible);
321
322   BLI_ghash_free(map, NULL, NULL);
323 }
324
325 static void update_vb(PBVH *bvh, PBVHNode *node, BBC *prim_bbc, int offset, int count)
326 {
327   BB_reset(&node->vb);
328   for (int i = offset + count - 1; i >= offset; --i) {
329     BB_expand_with_bb(&node->vb, (BB *)(&prim_bbc[bvh->prim_indices[i]]));
330   }
331   node->orig_vb = node->vb;
332 }
333
334 /* Returns the number of visible quads in the nodes' grids. */
335 int BKE_pbvh_count_grid_quads(BLI_bitmap **grid_hidden,
336                               int *grid_indices,
337                               int totgrid,
338                               int gridsize)
339 {
340   const int gridarea = (gridsize - 1) * (gridsize - 1);
341   int totquad = 0;
342
343   /* grid hidden layer is present, so have to check each grid for
344    * visibility */
345
346   for (int i = 0; i < totgrid; i++) {
347     const BLI_bitmap *gh = grid_hidden[grid_indices[i]];
348
349     if (gh) {
350       /* grid hidden are present, have to check each element */
351       for (int y = 0; y < gridsize - 1; y++) {
352         for (int x = 0; x < gridsize - 1; x++) {
353           if (!paint_is_grid_face_hidden(gh, gridsize, x, y))
354             totquad++;
355         }
356       }
357     }
358     else
359       totquad += gridarea;
360   }
361
362   return totquad;
363 }
364
365 static void build_grid_leaf_node(PBVH *bvh, PBVHNode *node)
366 {
367   int totquads = BKE_pbvh_count_grid_quads(
368       bvh->grid_hidden, node->prim_indices, node->totprim, bvh->gridkey.grid_size);
369   BKE_pbvh_node_fully_hidden_set(node, (totquads == 0));
370   BKE_pbvh_node_mark_rebuild_draw(node);
371 }
372
373 static void build_leaf(PBVH *bvh, int node_index, BBC *prim_bbc, int offset, int count)
374 {
375   bvh->nodes[node_index].flag |= PBVH_Leaf;
376
377   bvh->nodes[node_index].prim_indices = bvh->prim_indices + offset;
378   bvh->nodes[node_index].totprim = count;
379
380   /* Still need vb for searches */
381   update_vb(bvh, &bvh->nodes[node_index], prim_bbc, offset, count);
382
383   if (bvh->looptri)
384     build_mesh_leaf_node(bvh, bvh->nodes + node_index);
385   else {
386     build_grid_leaf_node(bvh, bvh->nodes + node_index);
387   }
388 }
389
390 /* Return zero if all primitives in the node can be drawn with the
391  * same material (including flat/smooth shading), non-zero otherwise */
392 static bool leaf_needs_material_split(PBVH *bvh, int offset, int count)
393 {
394   if (count <= 1)
395     return false;
396
397   if (bvh->looptri) {
398     const MLoopTri *first = &bvh->looptri[bvh->prim_indices[offset]];
399     const MPoly *mp = &bvh->mpoly[first->poly];
400
401     for (int i = offset + count - 1; i > offset; --i) {
402       int prim = bvh->prim_indices[i];
403       const MPoly *mp_other = &bvh->mpoly[bvh->looptri[prim].poly];
404       if (!face_materials_match(mp, mp_other)) {
405         return true;
406       }
407     }
408   }
409   else {
410     const DMFlagMat *first = &bvh->grid_flag_mats[bvh->prim_indices[offset]];
411
412     for (int i = offset + count - 1; i > offset; --i) {
413       int prim = bvh->prim_indices[i];
414       if (!grid_materials_match(first, &bvh->grid_flag_mats[prim]))
415         return true;
416     }
417   }
418
419   return false;
420 }
421
422 /* Recursively build a node in the tree
423  *
424  * vb is the voxel box around all of the primitives contained in
425  * this node.
426  *
427  * cb is the bounding box around all the centroids of the primitives
428  * contained in this node
429  *
430  * offset and start indicate a range in the array of primitive indices
431  */
432
433 static void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc, int offset, int count)
434 {
435   int end;
436   BB cb_backing;
437
438   /* Decide whether this is a leaf or not */
439   const bool below_leaf_limit = count <= bvh->leaf_limit;
440   if (below_leaf_limit) {
441     if (!leaf_needs_material_split(bvh, offset, count)) {
442       build_leaf(bvh, node_index, prim_bbc, offset, count);
443       return;
444     }
445   }
446
447   /* Add two child nodes */
448   bvh->nodes[node_index].children_offset = bvh->totnode;
449   pbvh_grow_nodes(bvh, bvh->totnode + 2);
450
451   /* Update parent node bounding box */
452   update_vb(bvh, &bvh->nodes[node_index], prim_bbc, offset, count);
453
454   if (!below_leaf_limit) {
455     /* Find axis with widest range of primitive centroids */
456     if (!cb) {
457       cb = &cb_backing;
458       BB_reset(cb);
459       for (int i = offset + count - 1; i >= offset; --i)
460         BB_expand(cb, prim_bbc[bvh->prim_indices[i]].bcentroid);
461     }
462     const int axis = BB_widest_axis(cb);
463
464     /* Partition primitives along that axis */
465     end = partition_indices(bvh->prim_indices,
466                             offset,
467                             offset + count - 1,
468                             axis,
469                             (cb->bmax[axis] + cb->bmin[axis]) * 0.5f,
470                             prim_bbc);
471   }
472   else {
473     /* Partition primitives by material */
474     end = partition_indices_material(bvh, offset, offset + count - 1);
475   }
476
477   /* Build children */
478   build_sub(bvh, bvh->nodes[node_index].children_offset, NULL, prim_bbc, offset, end - offset);
479   build_sub(
480       bvh, bvh->nodes[node_index].children_offset + 1, NULL, prim_bbc, end, offset + count - end);
481 }
482
483 static void pbvh_build(PBVH *bvh, BB *cb, BBC *prim_bbc, int totprim)
484 {
485   if (totprim != bvh->totprim) {
486     bvh->totprim = totprim;
487     if (bvh->nodes)
488       MEM_freeN(bvh->nodes);
489     if (bvh->prim_indices)
490       MEM_freeN(bvh->prim_indices);
491     bvh->prim_indices = MEM_mallocN(sizeof(int) * totprim, "bvh prim indices");
492     for (int i = 0; i < totprim; ++i)
493       bvh->prim_indices[i] = i;
494     bvh->totnode = 0;
495     if (bvh->node_mem_count < 100) {
496       bvh->node_mem_count = 100;
497       bvh->nodes = MEM_callocN(sizeof(PBVHNode) * bvh->node_mem_count, "bvh initial nodes");
498     }
499   }
500
501   bvh->totnode = 1;
502   build_sub(bvh, 0, cb, prim_bbc, 0, totprim);
503 }
504
505 /**
506  * Do a full rebuild with on Mesh data structure.
507  *
508  * \note Unlike mpoly/mloop/verts, looptri is **totally owned** by PBVH (which means it may rewrite it if needed,
509  * see #BKE_pbvh_apply_vertCos().
510  */
511 void BKE_pbvh_build_mesh(PBVH *bvh,
512                          const MPoly *mpoly,
513                          const MLoop *mloop,
514                          MVert *verts,
515                          int totvert,
516                          struct CustomData *vdata,
517                          const MLoopTri *looptri,
518                          int looptri_num)
519 {
520   BBC *prim_bbc = NULL;
521   BB cb;
522
523   bvh->type = PBVH_FACES;
524   bvh->mpoly = mpoly;
525   bvh->mloop = mloop;
526   bvh->looptri = looptri;
527   bvh->verts = verts;
528   bvh->vert_bitmap = BLI_BITMAP_NEW(totvert, "bvh->vert_bitmap");
529   bvh->totvert = totvert;
530   bvh->leaf_limit = LEAF_LIMIT;
531   bvh->vdata = vdata;
532
533   BB_reset(&cb);
534
535   /* For each face, store the AABB and the AABB centroid */
536   prim_bbc = MEM_mallocN(sizeof(BBC) * looptri_num, "prim_bbc");
537
538   for (int i = 0; i < looptri_num; ++i) {
539     const MLoopTri *lt = &looptri[i];
540     const int sides = 3;
541     BBC *bbc = prim_bbc + i;
542
543     BB_reset((BB *)bbc);
544
545     for (int j = 0; j < sides; ++j)
546       BB_expand((BB *)bbc, verts[bvh->mloop[lt->tri[j]].v].co);
547
548     BBC_update_centroid(bbc);
549
550     BB_expand(&cb, bbc->bcentroid);
551   }
552
553   if (looptri_num)
554     pbvh_build(bvh, &cb, prim_bbc, looptri_num);
555
556   MEM_freeN(prim_bbc);
557   MEM_freeN(bvh->vert_bitmap);
558 }
559
560 /* Do a full rebuild with on Grids data structure */
561 void BKE_pbvh_build_grids(PBVH *bvh,
562                           CCGElem **grids,
563                           int totgrid,
564                           CCGKey *key,
565                           void **gridfaces,
566                           DMFlagMat *flagmats,
567                           BLI_bitmap **grid_hidden)
568 {
569   const int gridsize = key->grid_size;
570
571   bvh->type = PBVH_GRIDS;
572   bvh->grids = grids;
573   bvh->gridfaces = gridfaces;
574   bvh->grid_flag_mats = flagmats;
575   bvh->totgrid = totgrid;
576   bvh->gridkey = *key;
577   bvh->grid_hidden = grid_hidden;
578   bvh->leaf_limit = max_ii(LEAF_LIMIT / ((gridsize - 1) * (gridsize - 1)), 1);
579
580   BB cb;
581   BB_reset(&cb);
582
583   /* For each grid, store the AABB and the AABB centroid */
584   BBC *prim_bbc = MEM_mallocN(sizeof(BBC) * totgrid, "prim_bbc");
585
586   for (int i = 0; i < totgrid; ++i) {
587     CCGElem *grid = grids[i];
588     BBC *bbc = prim_bbc + i;
589
590     BB_reset((BB *)bbc);
591
592     for (int j = 0; j < gridsize * gridsize; ++j)
593       BB_expand((BB *)bbc, CCG_elem_offset_co(key, grid, j));
594
595     BBC_update_centroid(bbc);
596
597     BB_expand(&cb, bbc->bcentroid);
598   }
599
600   if (totgrid)
601     pbvh_build(bvh, &cb, prim_bbc, totgrid);
602
603   MEM_freeN(prim_bbc);
604 }
605
606 PBVH *BKE_pbvh_new(void)
607 {
608   PBVH *bvh = MEM_callocN(sizeof(PBVH), "pbvh");
609
610   return bvh;
611 }
612
613 void BKE_pbvh_free(PBVH *bvh)
614 {
615   for (int i = 0; i < bvh->totnode; ++i) {
616     PBVHNode *node = &bvh->nodes[i];
617
618     if (node->flag & PBVH_Leaf) {
619       if (node->draw_buffers)
620         GPU_pbvh_buffers_free(node->draw_buffers);
621       if (node->vert_indices)
622         MEM_freeN((void *)node->vert_indices);
623       if (node->face_vert_indices)
624         MEM_freeN((void *)node->face_vert_indices);
625       BKE_pbvh_node_layer_disp_free(node);
626
627       if (node->bm_faces)
628         BLI_gset_free(node->bm_faces, NULL);
629       if (node->bm_unique_verts)
630         BLI_gset_free(node->bm_unique_verts, NULL);
631       if (node->bm_other_verts)
632         BLI_gset_free(node->bm_other_verts, NULL);
633     }
634   }
635
636   if (bvh->deformed) {
637     if (bvh->verts) {
638       /* if pbvh was deformed, new memory was allocated for verts/faces -- free it */
639
640       MEM_freeN((void *)bvh->verts);
641     }
642   }
643
644   if (bvh->looptri) {
645     MEM_freeN((void *)bvh->looptri);
646   }
647
648   if (bvh->nodes)
649     MEM_freeN(bvh->nodes);
650
651   if (bvh->prim_indices)
652     MEM_freeN(bvh->prim_indices);
653
654   MEM_freeN(bvh);
655 }
656
657 void BKE_pbvh_free_layer_disp(PBVH *bvh)
658 {
659   for (int i = 0; i < bvh->totnode; ++i)
660     BKE_pbvh_node_layer_disp_free(&bvh->nodes[i]);
661 }
662
663 static void pbvh_iter_begin(PBVHIter *iter,
664                             PBVH *bvh,
665                             BKE_pbvh_SearchCallback scb,
666                             void *search_data)
667 {
668   iter->bvh = bvh;
669   iter->scb = scb;
670   iter->search_data = search_data;
671
672   iter->stack = iter->stackfixed;
673   iter->stackspace = STACK_FIXED_DEPTH;
674
675   iter->stack[0].node = bvh->nodes;
676   iter->stack[0].revisiting = false;
677   iter->stacksize = 1;
678 }
679
680 static void pbvh_iter_end(PBVHIter *iter)
681 {
682   if (iter->stackspace > STACK_FIXED_DEPTH)
683     MEM_freeN(iter->stack);
684 }
685
686 static void pbvh_stack_push(PBVHIter *iter, PBVHNode *node, bool revisiting)
687 {
688   if (UNLIKELY(iter->stacksize == iter->stackspace)) {
689     iter->stackspace *= 2;
690     if (iter->stackspace != (STACK_FIXED_DEPTH * 2)) {
691       iter->stack = MEM_reallocN(iter->stack, sizeof(PBVHStack) * iter->stackspace);
692     }
693     else {
694       iter->stack = MEM_mallocN(sizeof(PBVHStack) * iter->stackspace, "PBVHStack");
695       memcpy(iter->stack, iter->stackfixed, sizeof(PBVHStack) * iter->stacksize);
696     }
697   }
698
699   iter->stack[iter->stacksize].node = node;
700   iter->stack[iter->stacksize].revisiting = revisiting;
701   iter->stacksize++;
702 }
703
704 static PBVHNode *pbvh_iter_next(PBVHIter *iter)
705 {
706   /* purpose here is to traverse tree, visiting child nodes before their
707    * parents, this order is necessary for e.g. computing bounding boxes */
708
709   while (iter->stacksize) {
710     /* pop node */
711     iter->stacksize--;
712     PBVHNode *node = iter->stack[iter->stacksize].node;
713
714     /* on a mesh with no faces this can happen
715      * can remove this check if we know meshes have at least 1 face */
716     if (node == NULL)
717       return NULL;
718
719     bool revisiting = iter->stack[iter->stacksize].revisiting;
720
721     /* revisiting node already checked */
722     if (revisiting)
723       return node;
724
725     if (iter->scb && !iter->scb(node, iter->search_data))
726       continue; /* don't traverse, outside of search zone */
727
728     if (node->flag & PBVH_Leaf) {
729       /* immediately hit leaf node */
730       return node;
731     }
732     else {
733       /* come back later when children are done */
734       pbvh_stack_push(iter, node, true);
735
736       /* push two child nodes on the stack */
737       pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset + 1, false);
738       pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset, false);
739     }
740   }
741
742   return NULL;
743 }
744
745 static PBVHNode *pbvh_iter_next_occluded(PBVHIter *iter)
746 {
747   while (iter->stacksize) {
748     /* pop node */
749     iter->stacksize--;
750     PBVHNode *node = iter->stack[iter->stacksize].node;
751
752     /* on a mesh with no faces this can happen
753      * can remove this check if we know meshes have at least 1 face */
754     if (node == NULL)
755       return NULL;
756
757     if (iter->scb && !iter->scb(node, iter->search_data))
758       continue; /* don't traverse, outside of search zone */
759
760     if (node->flag & PBVH_Leaf) {
761       /* immediately hit leaf node */
762       return node;
763     }
764     else {
765       pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset + 1, false);
766       pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset, false);
767     }
768   }
769
770   return NULL;
771 }
772
773 void BKE_pbvh_search_gather(
774     PBVH *bvh, BKE_pbvh_SearchCallback scb, void *search_data, PBVHNode ***r_array, int *r_tot)
775 {
776   PBVHIter iter;
777   PBVHNode **array = NULL, *node;
778   int tot = 0, space = 0;
779
780   pbvh_iter_begin(&iter, bvh, scb, search_data);
781
782   while ((node = pbvh_iter_next(&iter))) {
783     if (node->flag & PBVH_Leaf) {
784       if (UNLIKELY(tot == space)) {
785         /* resize array if needed */
786         space = (tot == 0) ? 32 : space * 2;
787         array = MEM_recallocN_id(array, sizeof(PBVHNode *) * space, __func__);
788       }
789
790       array[tot] = node;
791       tot++;
792     }
793   }
794
795   pbvh_iter_end(&iter);
796
797   if (tot == 0 && array) {
798     MEM_freeN(array);
799     array = NULL;
800   }
801
802   *r_array = array;
803   *r_tot = tot;
804 }
805
806 void BKE_pbvh_search_callback(PBVH *bvh,
807                               BKE_pbvh_SearchCallback scb,
808                               void *search_data,
809                               BKE_pbvh_HitCallback hcb,
810                               void *hit_data)
811 {
812   PBVHIter iter;
813   PBVHNode *node;
814
815   pbvh_iter_begin(&iter, bvh, scb, search_data);
816
817   while ((node = pbvh_iter_next(&iter)))
818     if (node->flag & PBVH_Leaf)
819       hcb(node, hit_data);
820
821   pbvh_iter_end(&iter);
822 }
823
824 typedef struct node_tree {
825   PBVHNode *data;
826
827   struct node_tree *left;
828   struct node_tree *right;
829 } node_tree;
830
831 static void node_tree_insert(node_tree *tree, node_tree *new_node)
832 {
833   if (new_node->data->tmin < tree->data->tmin) {
834     if (tree->left) {
835       node_tree_insert(tree->left, new_node);
836     }
837     else {
838       tree->left = new_node;
839     }
840   }
841   else {
842     if (tree->right) {
843       node_tree_insert(tree->right, new_node);
844     }
845     else {
846       tree->right = new_node;
847     }
848   }
849 }
850
851 static void traverse_tree(node_tree *tree,
852                           BKE_pbvh_HitOccludedCallback hcb,
853                           void *hit_data,
854                           float *tmin)
855 {
856   if (tree->left)
857     traverse_tree(tree->left, hcb, hit_data, tmin);
858
859   hcb(tree->data, hit_data, tmin);
860
861   if (tree->right)
862     traverse_tree(tree->right, hcb, hit_data, tmin);
863 }
864
865 static void free_tree(node_tree *tree)
866 {
867   if (tree->left) {
868     free_tree(tree->left);
869     tree->left = NULL;
870   }
871
872   if (tree->right) {
873     free_tree(tree->right);
874     tree->right = NULL;
875   }
876
877   free(tree);
878 }
879
880 float BKE_pbvh_node_get_tmin(PBVHNode *node)
881 {
882   return node->tmin;
883 }
884
885 static void BKE_pbvh_search_callback_occluded(PBVH *bvh,
886                                               BKE_pbvh_SearchCallback scb,
887                                               void *search_data,
888                                               BKE_pbvh_HitOccludedCallback hcb,
889                                               void *hit_data)
890 {
891   PBVHIter iter;
892   PBVHNode *node;
893   node_tree *tree = NULL;
894
895   pbvh_iter_begin(&iter, bvh, scb, search_data);
896
897   while ((node = pbvh_iter_next_occluded(&iter))) {
898     if (node->flag & PBVH_Leaf) {
899       node_tree *new_node = malloc(sizeof(node_tree));
900
901       new_node->data = node;
902
903       new_node->left = NULL;
904       new_node->right = NULL;
905
906       if (tree) {
907         node_tree_insert(tree, new_node);
908       }
909       else {
910         tree = new_node;
911       }
912     }
913   }
914
915   pbvh_iter_end(&iter);
916
917   if (tree) {
918     float tmin = FLT_MAX;
919     traverse_tree(tree, hcb, hit_data, &tmin);
920     free_tree(tree);
921   }
922 }
923
924 static bool update_search_cb(PBVHNode *node, void *data_v)
925 {
926   int flag = POINTER_AS_INT(data_v);
927
928   if (node->flag & PBVH_Leaf)
929     return (node->flag & flag) != 0;
930
931   return true;
932 }
933
934 typedef struct PBVHUpdateData {
935   PBVH *bvh;
936   PBVHNode **nodes;
937   int totnode;
938
939   float (*fnors)[3];
940   float (*vnors)[3];
941   int flag;
942 } PBVHUpdateData;
943
944 static void pbvh_update_normals_accum_task_cb(void *__restrict userdata,
945                                               const int n,
946                                               const ParallelRangeTLS *__restrict UNUSED(tls))
947 {
948   PBVHUpdateData *data = userdata;
949
950   PBVH *bvh = data->bvh;
951   PBVHNode *node = data->nodes[n];
952   float(*fnors)[3] = data->fnors;
953   float(*vnors)[3] = data->vnors;
954
955   if ((node->flag & PBVH_UpdateNormals)) {
956     unsigned int mpoly_prev = UINT_MAX;
957     float fn[3];
958
959     const int *faces = node->prim_indices;
960     const int totface = node->totprim;
961
962     for (int i = 0; i < totface; ++i) {
963       const MLoopTri *lt = &bvh->looptri[faces[i]];
964       const unsigned int vtri[3] = {
965           bvh->mloop[lt->tri[0]].v,
966           bvh->mloop[lt->tri[1]].v,
967           bvh->mloop[lt->tri[2]].v,
968       };
969       const int sides = 3;
970
971       /* Face normal and mask */
972       if (lt->poly != mpoly_prev) {
973         const MPoly *mp = &bvh->mpoly[lt->poly];
974         BKE_mesh_calc_poly_normal(mp, &bvh->mloop[mp->loopstart], bvh->verts, fn);
975         mpoly_prev = lt->poly;
976
977         if (fnors) {
978           /* We can assume a face is only present in one node ever. */
979           copy_v3_v3(fnors[lt->poly], fn);
980         }
981       }
982
983       for (int j = sides; j--;) {
984         const int v = vtri[j];
985
986         if (bvh->verts[v].flag & ME_VERT_PBVH_UPDATE) {
987           /* Note: This avoids `lock, add_v3_v3, unlock` and is five to ten times quicker than a spinlock.
988            *       Not exact equivalent though, since atomicity is only ensured for one component
989            *       of the vector at a time, but here it shall not make any sensible difference. */
990           for (int k = 3; k--;) {
991             atomic_add_and_fetch_fl(&vnors[v][k], fn[k]);
992           }
993         }
994       }
995     }
996   }
997 }
998
999 static void pbvh_update_normals_store_task_cb(void *__restrict userdata,
1000                                               const int n,
1001                                               const ParallelRangeTLS *__restrict UNUSED(tls))
1002 {
1003   PBVHUpdateData *data = userdata;
1004   PBVH *bvh = data->bvh;
1005   PBVHNode *node = data->nodes[n];
1006   float(*vnors)[3] = data->vnors;
1007
1008   if (node->flag & PBVH_UpdateNormals) {
1009     const int *verts = node->vert_indices;
1010     const int totvert = node->uniq_verts;
1011
1012     for (int i = 0; i < totvert; ++i) {
1013       const int v = verts[i];
1014       MVert *mvert = &bvh->verts[v];
1015
1016       /* mvert is shared between nodes, hence between threads. */
1017       if (atomic_fetch_and_and_char(&mvert->flag, (char)~ME_VERT_PBVH_UPDATE) &
1018           ME_VERT_PBVH_UPDATE) {
1019         normalize_v3(vnors[v]);
1020         normal_float_to_short_v3(mvert->no, vnors[v]);
1021       }
1022     }
1023
1024     node->flag &= ~PBVH_UpdateNormals;
1025   }
1026 }
1027
1028 static void pbvh_update_normals(PBVH *bvh, PBVHNode **nodes, int totnode, float (*fnors)[3])
1029 {
1030   float(*vnors)[3];
1031
1032   if (bvh->type == PBVH_BMESH) {
1033     BLI_assert(fnors == NULL);
1034     pbvh_bmesh_normals_update(nodes, totnode);
1035     return;
1036   }
1037
1038   if (bvh->type != PBVH_FACES)
1039     return;
1040
1041   /* could be per node to save some memory, but also means
1042    * we have to store for each vertex which node it is in */
1043   vnors = MEM_callocN(sizeof(*vnors) * bvh->totvert, __func__);
1044
1045   /* subtle assumptions:
1046    * - We know that for all edited vertices, the nodes with faces
1047    *   adjacent to these vertices have been marked with PBVH_UpdateNormals.
1048    *   This is true because if the vertex is inside the brush radius, the
1049    *   bounding box of it's adjacent faces will be as well.
1050    * - However this is only true for the vertices that have actually been
1051    *   edited, not for all vertices in the nodes marked for update, so we
1052    *   can only update vertices marked with ME_VERT_PBVH_UPDATE.
1053    */
1054
1055   PBVHUpdateData data = {
1056       .bvh = bvh,
1057       .nodes = nodes,
1058       .fnors = fnors,
1059       .vnors = vnors,
1060   };
1061
1062   ParallelRangeSettings settings;
1063   BLI_parallel_range_settings_defaults(&settings);
1064   settings.use_threading = (totnode > PBVH_THREADED_LIMIT);
1065
1066   BLI_task_parallel_range(0, totnode, &data, pbvh_update_normals_accum_task_cb, &settings);
1067
1068   BLI_task_parallel_range(0, totnode, &data, pbvh_update_normals_store_task_cb, &settings);
1069
1070   MEM_freeN(vnors);
1071 }
1072
1073 static void pbvh_update_BB_redraw_task_cb(void *__restrict userdata,
1074                                           const int n,
1075                                           const ParallelRangeTLS *__restrict UNUSED(tls))
1076 {
1077   PBVHUpdateData *data = userdata;
1078   PBVH *bvh = data->bvh;
1079   PBVHNode *node = data->nodes[n];
1080   const int flag = data->flag;
1081
1082   if ((flag & PBVH_UpdateBB) && (node->flag & PBVH_UpdateBB))
1083     /* don't clear flag yet, leave it for flushing later */
1084     /* Note that bvh usage is read-only here, so no need to thread-protect it. */
1085     update_node_vb(bvh, node);
1086
1087   if ((flag & PBVH_UpdateOriginalBB) && (node->flag & PBVH_UpdateOriginalBB))
1088     node->orig_vb = node->vb;
1089
1090   if ((flag & PBVH_UpdateRedraw) && (node->flag & PBVH_UpdateRedraw))
1091     node->flag &= ~PBVH_UpdateRedraw;
1092 }
1093
1094 void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes, int totnode, int flag)
1095 {
1096   /* update BB, redraw flag */
1097   PBVHUpdateData data = {
1098       .bvh = bvh,
1099       .nodes = nodes,
1100       .flag = flag,
1101   };
1102
1103   ParallelRangeSettings settings;
1104   BLI_parallel_range_settings_defaults(&settings);
1105   settings.use_threading = (totnode > PBVH_THREADED_LIMIT);
1106   BLI_task_parallel_range(0, totnode, &data, pbvh_update_BB_redraw_task_cb, &settings);
1107 }
1108
1109 static int pbvh_get_buffers_update_flags(PBVH *bvh)
1110 {
1111   int update_flags = 0;
1112   update_flags |= bvh->show_mask ? GPU_PBVH_BUFFERS_SHOW_MASK : 0;
1113   return update_flags;
1114 }
1115
1116 static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode)
1117 {
1118   /* can't be done in parallel with OpenGL */
1119   for (int n = 0; n < totnode; n++) {
1120     PBVHNode *node = nodes[n];
1121
1122     if (node->flag & PBVH_RebuildDrawBuffers) {
1123       GPU_pbvh_buffers_free(node->draw_buffers);
1124       switch (bvh->type) {
1125         case PBVH_GRIDS:
1126           node->draw_buffers = GPU_pbvh_grid_buffers_build(node->totprim, bvh->grid_hidden);
1127           break;
1128         case PBVH_FACES:
1129           node->draw_buffers = GPU_pbvh_mesh_buffers_build(node->face_vert_indices,
1130                                                            bvh->mpoly,
1131                                                            bvh->mloop,
1132                                                            bvh->looptri,
1133                                                            bvh->verts,
1134                                                            node->prim_indices,
1135                                                            node->totprim);
1136           break;
1137         case PBVH_BMESH:
1138           node->draw_buffers = GPU_pbvh_bmesh_buffers_build(bvh->flags &
1139                                                             PBVH_DYNTOPO_SMOOTH_SHADING);
1140           break;
1141       }
1142
1143       node->flag &= ~PBVH_RebuildDrawBuffers;
1144     }
1145
1146     if (node->flag & PBVH_UpdateDrawBuffers) {
1147       const int update_flags = pbvh_get_buffers_update_flags(bvh);
1148       switch (bvh->type) {
1149         case PBVH_GRIDS:
1150           GPU_pbvh_grid_buffers_update(node->draw_buffers,
1151                                        bvh->grids,
1152                                        bvh->grid_flag_mats,
1153                                        node->prim_indices,
1154                                        node->totprim,
1155                                        &bvh->gridkey,
1156                                        update_flags);
1157           break;
1158         case PBVH_FACES:
1159           GPU_pbvh_mesh_buffers_update(node->draw_buffers,
1160                                        bvh->verts,
1161                                        node->vert_indices,
1162                                        node->uniq_verts + node->face_verts,
1163                                        CustomData_get_layer(bvh->vdata, CD_PAINT_MASK),
1164                                        node->face_vert_indices,
1165                                        update_flags);
1166           break;
1167         case PBVH_BMESH:
1168           GPU_pbvh_bmesh_buffers_update(node->draw_buffers,
1169                                         bvh->bm,
1170                                         node->bm_faces,
1171                                         node->bm_unique_verts,
1172                                         node->bm_other_verts,
1173                                         update_flags);
1174           break;
1175       }
1176
1177       node->flag &= ~PBVH_UpdateDrawBuffers;
1178     }
1179   }
1180 }
1181
1182 static int pbvh_flush_bb(PBVH *bvh, PBVHNode *node, int flag)
1183 {
1184   int update = 0;
1185
1186   /* difficult to multithread well, we just do single threaded recursive */
1187   if (node->flag & PBVH_Leaf) {
1188     if (flag & PBVH_UpdateBB) {
1189       update |= (node->flag & PBVH_UpdateBB);
1190       node->flag &= ~PBVH_UpdateBB;
1191     }
1192
1193     if (flag & PBVH_UpdateOriginalBB) {
1194       update |= (node->flag & PBVH_UpdateOriginalBB);
1195       node->flag &= ~PBVH_UpdateOriginalBB;
1196     }
1197
1198     return update;
1199   }
1200   else {
1201     update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset, flag);
1202     update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset + 1, flag);
1203
1204     if (update & PBVH_UpdateBB)
1205       update_node_vb(bvh, node);
1206     if (update & PBVH_UpdateOriginalBB)
1207       node->orig_vb = node->vb;
1208   }
1209
1210   return update;
1211 }
1212
1213 void BKE_pbvh_update(PBVH *bvh, int flag, float (*fnors)[3])
1214 {
1215   if (!bvh->nodes)
1216     return;
1217
1218   PBVHNode **nodes;
1219   int totnode;
1220
1221   BKE_pbvh_search_gather(bvh, update_search_cb, POINTER_FROM_INT(flag), &nodes, &totnode);
1222
1223   if (flag & PBVH_UpdateNormals)
1224     pbvh_update_normals(bvh, nodes, totnode, fnors);
1225
1226   if (flag & (PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateRedraw))
1227     pbvh_update_BB_redraw(bvh, nodes, totnode, flag);
1228
1229   if (flag & (PBVH_UpdateBB | PBVH_UpdateOriginalBB))
1230     pbvh_flush_bb(bvh, bvh->nodes, flag);
1231
1232   if (nodes)
1233     MEM_freeN(nodes);
1234 }
1235
1236 void BKE_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3])
1237 {
1238   PBVHIter iter;
1239   PBVHNode *node;
1240   BB bb;
1241
1242   BB_reset(&bb);
1243
1244   pbvh_iter_begin(&iter, bvh, NULL, NULL);
1245
1246   while ((node = pbvh_iter_next(&iter)))
1247     if (node->flag & PBVH_UpdateRedraw)
1248       BB_expand_with_bb(&bb, &node->vb);
1249
1250   pbvh_iter_end(&iter);
1251
1252   copy_v3_v3(bb_min, bb.bmin);
1253   copy_v3_v3(bb_max, bb.bmax);
1254 }
1255
1256 void BKE_pbvh_get_grid_updates(PBVH *bvh, bool clear, void ***r_gridfaces, int *r_totface)
1257 {
1258   GSet *face_set = BLI_gset_ptr_new(__func__);
1259   PBVHNode *node;
1260   PBVHIter iter;
1261
1262   pbvh_iter_begin(&iter, bvh, NULL, NULL);
1263
1264   while ((node = pbvh_iter_next(&iter))) {
1265     if (node->flag & PBVH_UpdateNormals) {
1266       for (unsigned i = 0; i < node->totprim; ++i) {
1267         void *face = bvh->gridfaces[node->prim_indices[i]];
1268         BLI_gset_add(face_set, face);
1269       }
1270
1271       if (clear)
1272         node->flag &= ~PBVH_UpdateNormals;
1273     }
1274   }
1275
1276   pbvh_iter_end(&iter);
1277
1278   const int tot = BLI_gset_len(face_set);
1279   if (tot == 0) {
1280     *r_totface = 0;
1281     *r_gridfaces = NULL;
1282     BLI_gset_free(face_set, NULL);
1283     return;
1284   }
1285
1286   void **faces = MEM_mallocN(sizeof(*faces) * tot, "PBVH Grid Faces");
1287
1288   GSetIterator gs_iter;
1289   int i;
1290   GSET_ITER_INDEX(gs_iter, face_set, i)
1291   {
1292     faces[i] = BLI_gsetIterator_getKey(&gs_iter);
1293   }
1294
1295   BLI_gset_free(face_set, NULL);
1296
1297   *r_totface = tot;
1298   *r_gridfaces = faces;
1299 }
1300
1301 /***************************** PBVH Access ***********************************/
1302
1303 PBVHType BKE_pbvh_type(const PBVH *bvh)
1304 {
1305   return bvh->type;
1306 }
1307
1308 bool BKE_pbvh_has_faces(const PBVH *bvh)
1309 {
1310   if (bvh->type == PBVH_BMESH) {
1311     return (bvh->bm->totface != 0);
1312   }
1313   else {
1314     return (bvh->totprim != 0);
1315   }
1316 }
1317
1318 void BKE_pbvh_bounding_box(const PBVH *bvh, float min[3], float max[3])
1319 {
1320   if (bvh->totnode) {
1321     const BB *bb = &bvh->nodes[0].vb;
1322     copy_v3_v3(min, bb->bmin);
1323     copy_v3_v3(max, bb->bmax);
1324   }
1325   else {
1326     zero_v3(min);
1327     zero_v3(max);
1328   }
1329 }
1330
1331 BLI_bitmap **BKE_pbvh_grid_hidden(const PBVH *bvh)
1332 {
1333   BLI_assert(bvh->type == PBVH_GRIDS);
1334   return bvh->grid_hidden;
1335 }
1336
1337 void BKE_pbvh_get_grid_key(const PBVH *bvh, CCGKey *key)
1338 {
1339   BLI_assert(bvh->type == PBVH_GRIDS);
1340   *key = bvh->gridkey;
1341 }
1342
1343 struct CCGElem **BKE_pbvh_get_grids(const PBVH *bvh, int *num_grids)
1344 {
1345   BLI_assert(bvh->type == PBVH_GRIDS);
1346   *num_grids = bvh->totgrid;
1347   return bvh->grids;
1348 }
1349
1350 BMesh *BKE_pbvh_get_bmesh(PBVH *bvh)
1351 {
1352   BLI_assert(bvh->type == PBVH_BMESH);
1353   return bvh->bm;
1354 }
1355
1356 /***************************** Node Access ***********************************/
1357
1358 void BKE_pbvh_node_mark_update(PBVHNode *node)
1359 {
1360   node->flag |= PBVH_UpdateNormals | PBVH_UpdateBB | PBVH_UpdateOriginalBB |
1361                 PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw;
1362 }
1363
1364 void BKE_pbvh_node_mark_rebuild_draw(PBVHNode *node)
1365 {
1366   node->flag |= PBVH_RebuildDrawBuffers | PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw;
1367 }
1368
1369 void BKE_pbvh_node_mark_redraw(PBVHNode *node)
1370 {
1371   node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw;
1372 }
1373
1374 void BKE_pbvh_node_mark_normals_update(PBVHNode *node)
1375 {
1376   node->flag |= PBVH_UpdateNormals;
1377 }
1378
1379 void BKE_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden)
1380 {
1381   BLI_assert(node->flag & PBVH_Leaf);
1382
1383   if (fully_hidden)
1384     node->flag |= PBVH_FullyHidden;
1385   else
1386     node->flag &= ~PBVH_FullyHidden;
1387 }
1388
1389 void BKE_pbvh_node_get_verts(PBVH *bvh,
1390                              PBVHNode *node,
1391                              const int **r_vert_indices,
1392                              MVert **r_verts)
1393 {
1394   if (r_vert_indices) {
1395     *r_vert_indices = node->vert_indices;
1396   }
1397
1398   if (r_verts) {
1399     *r_verts = bvh->verts;
1400   }
1401 }
1402
1403 void BKE_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node, int *r_uniquevert, int *r_totvert)
1404 {
1405   int tot;
1406
1407   switch (bvh->type) {
1408     case PBVH_GRIDS:
1409       tot = node->totprim * bvh->gridkey.grid_area;
1410       if (r_totvert)
1411         *r_totvert = tot;
1412       if (r_uniquevert)
1413         *r_uniquevert = tot;
1414       break;
1415     case PBVH_FACES:
1416       if (r_totvert)
1417         *r_totvert = node->uniq_verts + node->face_verts;
1418       if (r_uniquevert)
1419         *r_uniquevert = node->uniq_verts;
1420       break;
1421     case PBVH_BMESH:
1422       tot = BLI_gset_len(node->bm_unique_verts);
1423       if (r_totvert)
1424         *r_totvert = tot + BLI_gset_len(node->bm_other_verts);
1425       if (r_uniquevert)
1426         *r_uniquevert = tot;
1427       break;
1428   }
1429 }
1430
1431 void BKE_pbvh_node_get_grids(PBVH *bvh,
1432                              PBVHNode *node,
1433                              int **r_grid_indices,
1434                              int *r_totgrid,
1435                              int *r_maxgrid,
1436                              int *r_gridsize,
1437                              CCGElem ***r_griddata)
1438 {
1439   switch (bvh->type) {
1440     case PBVH_GRIDS:
1441       if (r_grid_indices)
1442         *r_grid_indices = node->prim_indices;
1443       if (r_totgrid)
1444         *r_totgrid = node->totprim;
1445       if (r_maxgrid)
1446         *r_maxgrid = bvh->totgrid;
1447       if (r_gridsize)
1448         *r_gridsize = bvh->gridkey.grid_size;
1449       if (r_griddata)
1450         *r_griddata = bvh->grids;
1451       break;
1452     case PBVH_FACES:
1453     case PBVH_BMESH:
1454       if (r_grid_indices)
1455         *r_grid_indices = NULL;
1456       if (r_totgrid)
1457         *r_totgrid = 0;
1458       if (r_maxgrid)
1459         *r_maxgrid = 0;
1460       if (r_gridsize)
1461         *r_gridsize = 0;
1462       if (r_griddata)
1463         *r_griddata = NULL;
1464       break;
1465   }
1466 }
1467
1468 void BKE_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
1469 {
1470   copy_v3_v3(bb_min, node->vb.bmin);
1471   copy_v3_v3(bb_max, node->vb.bmax);
1472 }
1473
1474 void BKE_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
1475 {
1476   copy_v3_v3(bb_min, node->orig_vb.bmin);
1477   copy_v3_v3(bb_max, node->orig_vb.bmax);
1478 }
1479
1480 void BKE_pbvh_node_get_proxies(PBVHNode *node, PBVHProxyNode **proxies, int *proxy_count)
1481 {
1482   if (node->proxy_count > 0) {
1483     if (proxies)
1484       *proxies = node->proxies;
1485     if (proxy_count)
1486       *proxy_count = node->proxy_count;
1487   }
1488   else {
1489     if (proxies)
1490       *proxies = NULL;
1491     if (proxy_count)
1492       *proxy_count = 0;
1493   }
1494 }
1495
1496 void BKE_pbvh_node_get_bm_orco_data(PBVHNode *node,
1497                                     int (**r_orco_tris)[3],
1498                                     int *r_orco_tris_num,
1499                                     float (**r_orco_coords)[3])
1500 {
1501   *r_orco_tris = node->bm_ortri;
1502   *r_orco_tris_num = node->bm_tot_ortri;
1503   *r_orco_coords = node->bm_orco;
1504 }
1505
1506 /**
1507  * \note doing a full search on all vertices here seems expensive,
1508  * however this is important to avoid having to recalculate boundbox & sync the buffers to the GPU
1509  * (which is far more expensive!) See: T47232.
1510  */
1511 bool BKE_pbvh_node_vert_update_check_any(PBVH *bvh, PBVHNode *node)
1512 {
1513   BLI_assert(bvh->type == PBVH_FACES);
1514   const int *verts = node->vert_indices;
1515   const int totvert = node->uniq_verts + node->face_verts;
1516
1517   for (int i = 0; i < totvert; ++i) {
1518     const int v = verts[i];
1519     const MVert *mvert = &bvh->verts[v];
1520
1521     if (mvert->flag & ME_VERT_PBVH_UPDATE) {
1522       return true;
1523     }
1524   }
1525
1526   return false;
1527 }
1528
1529 /********************************* Raycast ***********************************/
1530
1531 typedef struct {
1532   struct IsectRayAABB_Precalc ray;
1533   bool original;
1534 } RaycastData;
1535
1536 static bool ray_aabb_intersect(PBVHNode *node, void *data_v)
1537 {
1538   RaycastData *rcd = data_v;
1539   const float *bb_min, *bb_max;
1540
1541   if (rcd->original) {
1542     /* BKE_pbvh_node_get_original_BB */
1543     bb_min = node->orig_vb.bmin;
1544     bb_max = node->orig_vb.bmax;
1545   }
1546   else {
1547     /* BKE_pbvh_node_get_BB */
1548     bb_min = node->vb.bmin;
1549     bb_max = node->vb.bmax;
1550   }
1551
1552   return isect_ray_aabb_v3(&rcd->ray, bb_min, bb_max, &node->tmin);
1553 }
1554
1555 void BKE_pbvh_raycast(PBVH *bvh,
1556                       BKE_pbvh_HitOccludedCallback cb,
1557                       void *data,
1558                       const float ray_start[3],
1559                       const float ray_normal[3],
1560                       bool original)
1561 {
1562   RaycastData rcd;
1563
1564   isect_ray_aabb_v3_precalc(&rcd.ray, ray_start, ray_normal);
1565   rcd.original = original;
1566
1567   BKE_pbvh_search_callback_occluded(bvh, ray_aabb_intersect, &rcd, cb, data);
1568 }
1569
1570 bool ray_face_intersection_quad(const float ray_start[3],
1571                                 const float ray_normal[3],
1572                                 const float t0[3],
1573                                 const float t1[3],
1574                                 const float t2[3],
1575                                 const float t3[3],
1576                                 float *depth)
1577 {
1578   float depth_test;
1579
1580   if ((isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t1, t2, &depth_test, NULL, 0.1f) &&
1581        (depth_test < *depth)) ||
1582       (isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t2, t3, &depth_test, NULL, 0.1f) &&
1583        (depth_test < *depth))) {
1584     *depth = depth_test;
1585     return true;
1586   }
1587   else {
1588     return false;
1589   }
1590 }
1591
1592 bool ray_face_intersection_tri(const float ray_start[3],
1593                                const float ray_normal[3],
1594                                const float t0[3],
1595                                const float t1[3],
1596                                const float t2[3],
1597                                float *depth)
1598 {
1599   float depth_test;
1600
1601   if ((isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t1, t2, &depth_test, NULL, 0.1f) &&
1602        (depth_test < *depth))) {
1603     *depth = depth_test;
1604     return true;
1605   }
1606   else {
1607     return false;
1608   }
1609 }
1610
1611 /* Take advantage of the fact we know this wont be an intersection.
1612  * Just handle ray-tri edges. */
1613 static float dist_squared_ray_to_tri_v3_fast(const float ray_origin[3],
1614                                              const float ray_direction[3],
1615                                              const float v0[3],
1616                                              const float v1[3],
1617                                              const float v2[3],
1618                                              float r_point[3],
1619                                              float *r_depth)
1620 {
1621   const float *tri[3] = {v0, v1, v2};
1622   float dist_sq_best = FLT_MAX;
1623   for (int i = 0, j = 2; i < 3; j = i++) {
1624     float point_test[3], depth_test = FLT_MAX;
1625     const float dist_sq_test = dist_squared_ray_to_seg_v3(
1626         ray_origin, ray_direction, tri[i], tri[j], point_test, &depth_test);
1627     if (dist_sq_test < dist_sq_best || i == 0) {
1628       copy_v3_v3(r_point, point_test);
1629       *r_depth = depth_test;
1630       dist_sq_best = dist_sq_test;
1631     }
1632   }
1633   return dist_sq_best;
1634 }
1635
1636 bool ray_face_nearest_quad(const float ray_start[3],
1637                            const float ray_normal[3],
1638                            const float t0[3],
1639                            const float t1[3],
1640                            const float t2[3],
1641                            const float t3[3],
1642                            float *depth,
1643                            float *dist_sq)
1644 {
1645   float dist_sq_test;
1646   float co[3], depth_test;
1647
1648   if (((dist_sq_test = dist_squared_ray_to_tri_v3_fast(
1649             ray_start, ray_normal, t0, t1, t2, co, &depth_test)) < *dist_sq)) {
1650     *dist_sq = dist_sq_test;
1651     *depth = depth_test;
1652     if (((dist_sq_test = dist_squared_ray_to_tri_v3_fast(
1653               ray_start, ray_normal, t0, t2, t3, co, &depth_test)) < *dist_sq)) {
1654       *dist_sq = dist_sq_test;
1655       *depth = depth_test;
1656     }
1657     return true;
1658   }
1659   else {
1660     return false;
1661   }
1662 }
1663
1664 bool ray_face_nearest_tri(const float ray_start[3],
1665                           const float ray_normal[3],
1666                           const float t0[3],
1667                           const float t1[3],
1668                           const float t2[3],
1669                           float *depth,
1670                           float *dist_sq)
1671 {
1672   float dist_sq_test;
1673   float co[3], depth_test;
1674
1675   if (((dist_sq_test = dist_squared_ray_to_tri_v3_fast(
1676             ray_start, ray_normal, t0, t1, t2, co, &depth_test)) < *dist_sq)) {
1677     *dist_sq = dist_sq_test;
1678     *depth = depth_test;
1679     return true;
1680   }
1681   else {
1682     return false;
1683   }
1684 }
1685
1686 static bool pbvh_faces_node_raycast(PBVH *bvh,
1687                                     const PBVHNode *node,
1688                                     float (*origco)[3],
1689                                     const float ray_start[3],
1690                                     const float ray_normal[3],
1691                                     float *depth)
1692 {
1693   const MVert *vert = bvh->verts;
1694   const MLoop *mloop = bvh->mloop;
1695   const int *faces = node->prim_indices;
1696   int i, totface = node->totprim;
1697   bool hit = false;
1698
1699   for (i = 0; i < totface; ++i) {
1700     const MLoopTri *lt = &bvh->looptri[faces[i]];
1701     const int *face_verts = node->face_vert_indices[i];
1702
1703     if (paint_is_face_hidden(lt, vert, mloop))
1704       continue;
1705
1706     if (origco) {
1707       /* intersect with backuped original coordinates */
1708       hit |= ray_face_intersection_tri(ray_start,
1709                                        ray_normal,
1710                                        origco[face_verts[0]],
1711                                        origco[face_verts[1]],
1712                                        origco[face_verts[2]],
1713                                        depth);
1714     }
1715     else {
1716       /* intersect with current coordinates */
1717       hit |= ray_face_intersection_tri(ray_start,
1718                                        ray_normal,
1719                                        vert[mloop[lt->tri[0]].v].co,
1720                                        vert[mloop[lt->tri[1]].v].co,
1721                                        vert[mloop[lt->tri[2]].v].co,
1722                                        depth);
1723     }
1724   }
1725
1726   return hit;
1727 }
1728
1729 static bool pbvh_grids_node_raycast(PBVH *bvh,
1730                                     PBVHNode *node,
1731                                     float (*origco)[3],
1732                                     const float ray_start[3],
1733                                     const float ray_normal[3],
1734                                     float *depth)
1735 {
1736   const int totgrid = node->totprim;
1737   const int gridsize = bvh->gridkey.grid_size;
1738   bool hit = false;
1739
1740   for (int i = 0; i < totgrid; ++i) {
1741     CCGElem *grid = bvh->grids[node->prim_indices[i]];
1742     BLI_bitmap *gh;
1743
1744     if (!grid)
1745       continue;
1746
1747     gh = bvh->grid_hidden[node->prim_indices[i]];
1748
1749     for (int y = 0; y < gridsize - 1; ++y) {
1750       for (int x = 0; x < gridsize - 1; ++x) {
1751         /* check if grid face is hidden */
1752         if (gh) {
1753           if (paint_is_grid_face_hidden(gh, gridsize, x, y))
1754             continue;
1755         }
1756
1757         if (origco) {
1758           hit |= ray_face_intersection_quad(ray_start,
1759                                             ray_normal,
1760                                             origco[y * gridsize + x],
1761                                             origco[y * gridsize + x + 1],
1762                                             origco[(y + 1) * gridsize + x + 1],
1763                                             origco[(y + 1) * gridsize + x],
1764                                             depth);
1765         }
1766         else {
1767           hit |= ray_face_intersection_quad(ray_start,
1768                                             ray_normal,
1769                                             CCG_grid_elem_co(&bvh->gridkey, grid, x, y),
1770                                             CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y),
1771                                             CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y + 1),
1772                                             CCG_grid_elem_co(&bvh->gridkey, grid, x, y + 1),
1773                                             depth);
1774         }
1775       }
1776     }
1777
1778     if (origco)
1779       origco += gridsize * gridsize;
1780   }
1781
1782   return hit;
1783 }
1784
1785 bool BKE_pbvh_node_raycast(PBVH *bvh,
1786                            PBVHNode *node,
1787                            float (*origco)[3],
1788                            bool use_origco,
1789                            const float ray_start[3],
1790                            const float ray_normal[3],
1791                            float *depth)
1792 {
1793   bool hit = false;
1794
1795   if (node->flag & PBVH_FullyHidden)
1796     return false;
1797
1798   switch (bvh->type) {
1799     case PBVH_FACES:
1800       hit |= pbvh_faces_node_raycast(bvh, node, origco, ray_start, ray_normal, depth);
1801       break;
1802     case PBVH_GRIDS:
1803       hit |= pbvh_grids_node_raycast(bvh, node, origco, ray_start, ray_normal, depth);
1804       break;
1805     case PBVH_BMESH:
1806       hit = pbvh_bmesh_node_raycast(node, ray_start, ray_normal, depth, use_origco);
1807       break;
1808   }
1809
1810   return hit;
1811 }
1812
1813 void BKE_pbvh_raycast_project_ray_root(
1814     PBVH *bvh, bool original, float ray_start[3], float ray_end[3], float ray_normal[3])
1815 {
1816   if (bvh->nodes) {
1817     float rootmin_start, rootmin_end;
1818     float bb_min_root[3], bb_max_root[3], bb_center[3], bb_diff[3];
1819     struct IsectRayAABB_Precalc ray;
1820     float ray_normal_inv[3];
1821     float offset = 1.0f + 1e-3f;
1822     float offset_vec[3] = {1e-3f, 1e-3f, 1e-3f};
1823
1824     if (original)
1825       BKE_pbvh_node_get_original_BB(bvh->nodes, bb_min_root, bb_max_root);
1826     else
1827       BKE_pbvh_node_get_BB(bvh->nodes, bb_min_root, bb_max_root);
1828
1829     /* slightly offset min and max in case we have a zero width node (due to a plane mesh for instance),
1830      * or faces very close to the bounding box boundary. */
1831     mid_v3_v3v3(bb_center, bb_max_root, bb_min_root);
1832     /* diff should be same for both min/max since it's calculated from center */
1833     sub_v3_v3v3(bb_diff, bb_max_root, bb_center);
1834     /* handles case of zero width bb */
1835     add_v3_v3(bb_diff, offset_vec);
1836     madd_v3_v3v3fl(bb_max_root, bb_center, bb_diff, offset);
1837     madd_v3_v3v3fl(bb_min_root, bb_center, bb_diff, -offset);
1838
1839     /* first project start ray */
1840     isect_ray_aabb_v3_precalc(&ray, ray_start, ray_normal);
1841     if (!isect_ray_aabb_v3(&ray, bb_min_root, bb_max_root, &rootmin_start))
1842       return;
1843
1844     /* then the end ray */
1845     mul_v3_v3fl(ray_normal_inv, ray_normal, -1.0);
1846     isect_ray_aabb_v3_precalc(&ray, ray_end, ray_normal_inv);
1847     /* unlikely to fail exiting if entering succeeded, still keep this here */
1848     if (!isect_ray_aabb_v3(&ray, bb_min_root, bb_max_root, &rootmin_end))
1849       return;
1850
1851     madd_v3_v3v3fl(ray_start, ray_start, ray_normal, rootmin_start);
1852     madd_v3_v3v3fl(ray_end, ray_end, ray_normal_inv, rootmin_end);
1853   }
1854 }
1855
1856 /* -------------------------------------------------------------------- */
1857
1858 typedef struct {
1859   struct DistRayAABB_Precalc dist_ray_to_aabb_precalc;
1860   bool original;
1861 } FindNearestRayData;
1862
1863 static bool nearest_to_ray_aabb_dist_sq(PBVHNode *node, void *data_v)
1864 {
1865   FindNearestRayData *rcd = data_v;
1866   const float *bb_min, *bb_max;
1867
1868   if (rcd->original) {
1869     /* BKE_pbvh_node_get_original_BB */
1870     bb_min = node->orig_vb.bmin;
1871     bb_max = node->orig_vb.bmax;
1872   }
1873   else {
1874     /* BKE_pbvh_node_get_BB */
1875     bb_min = node->vb.bmin;
1876     bb_max = node->vb.bmax;
1877   }
1878
1879   float co_dummy[3], depth;
1880   node->tmin = dist_squared_ray_to_aabb_v3(
1881       &rcd->dist_ray_to_aabb_precalc, bb_min, bb_max, co_dummy, &depth);
1882   /* Ideally we would skip distances outside the range. */
1883   return depth > 0.0f;
1884 }
1885
1886 void BKE_pbvh_find_nearest_to_ray(PBVH *bvh,
1887                                   BKE_pbvh_SearchNearestCallback cb,
1888                                   void *data,
1889                                   const float ray_start[3],
1890                                   const float ray_normal[3],
1891                                   bool original)
1892 {
1893   FindNearestRayData ncd;
1894
1895   dist_squared_ray_to_aabb_v3_precalc(&ncd.dist_ray_to_aabb_precalc, ray_start, ray_normal);
1896   ncd.original = original;
1897
1898   BKE_pbvh_search_callback_occluded(bvh, nearest_to_ray_aabb_dist_sq, &ncd, cb, data);
1899 }
1900
1901 static bool pbvh_faces_node_nearest_to_ray(PBVH *bvh,
1902                                            const PBVHNode *node,
1903                                            float (*origco)[3],
1904                                            const float ray_start[3],
1905                                            const float ray_normal[3],
1906                                            float *depth,
1907                                            float *dist_sq)
1908 {
1909   const MVert *vert = bvh->verts;
1910   const MLoop *mloop = bvh->mloop;
1911   const int *faces = node->prim_indices;
1912   int i, totface = node->totprim;
1913   bool hit = false;
1914
1915   for (i = 0; i < totface; ++i) {
1916     const MLoopTri *lt = &bvh->looptri[faces[i]];
1917     const int *face_verts = node->face_vert_indices[i];
1918
1919     if (paint_is_face_hidden(lt, vert, mloop))
1920       continue;
1921
1922     if (origco) {
1923       /* intersect with backuped original coordinates */
1924       hit |= ray_face_nearest_tri(ray_start,
1925                                   ray_normal,
1926                                   origco[face_verts[0]],
1927                                   origco[face_verts[1]],
1928                                   origco[face_verts[2]],
1929                                   depth,
1930                                   dist_sq);
1931     }
1932     else {
1933       /* intersect with current coordinates */
1934       hit |= ray_face_nearest_tri(ray_start,
1935                                   ray_normal,
1936                                   vert[mloop[lt->tri[0]].v].co,
1937                                   vert[mloop[lt->tri[1]].v].co,
1938                                   vert[mloop[lt->tri[2]].v].co,
1939                                   depth,
1940                                   dist_sq);
1941     }
1942   }
1943
1944   return hit;
1945 }
1946
1947 static bool pbvh_grids_node_nearest_to_ray(PBVH *bvh,
1948                                            PBVHNode *node,
1949                                            float (*origco)[3],
1950                                            const float ray_start[3],
1951                                            const float ray_normal[3],
1952                                            float *depth,
1953                                            float *dist_sq)
1954 {
1955   const int totgrid = node->totprim;
1956   const int gridsize = bvh->gridkey.grid_size;
1957   bool hit = false;
1958
1959   for (int i = 0; i < totgrid; ++i) {
1960     CCGElem *grid = bvh->grids[node->prim_indices[i]];
1961     BLI_bitmap *gh;
1962
1963     if (!grid)
1964       continue;
1965
1966     gh = bvh->grid_hidden[node->prim_indices[i]];
1967
1968     for (int y = 0; y < gridsize - 1; ++y) {
1969       for (int x = 0; x < gridsize - 1; ++x) {
1970         /* check if grid face is hidden */
1971         if (gh) {
1972           if (paint_is_grid_face_hidden(gh, gridsize, x, y))
1973             continue;
1974         }
1975
1976         if (origco) {
1977           hit |= ray_face_nearest_quad(ray_start,
1978                                        ray_normal,
1979                                        origco[y * gridsize + x],
1980                                        origco[y * gridsize + x + 1],
1981                                        origco[(y + 1) * gridsize + x + 1],
1982                                        origco[(y + 1) * gridsize + x],
1983                                        depth,
1984                                        dist_sq);
1985         }
1986         else {
1987           hit |= ray_face_nearest_quad(ray_start,
1988                                        ray_normal,
1989                                        CCG_grid_elem_co(&bvh->gridkey, grid, x, y),
1990                                        CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y),
1991                                        CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y + 1),
1992                                        CCG_grid_elem_co(&bvh->gridkey, grid, x, y + 1),
1993                                        depth,
1994                                        dist_sq);
1995         }
1996       }
1997     }
1998
1999     if (origco)
2000       origco += gridsize * gridsize;
2001   }
2002
2003   return hit;
2004 }
2005
2006 bool BKE_pbvh_node_find_nearest_to_ray(PBVH *bvh,
2007                                        PBVHNode *node,
2008                                        float (*origco)[3],
2009                                        bool use_origco,
2010                                        const float ray_start[3],
2011                                        const float ray_normal[3],
2012                                        float *depth,
2013                                        float *dist_sq)
2014 {
2015   bool hit = false;
2016
2017   if (node->flag & PBVH_FullyHidden)
2018     return false;
2019
2020   switch (bvh->type) {
2021     case PBVH_FACES:
2022       hit |= pbvh_faces_node_nearest_to_ray(
2023           bvh, node, origco, ray_start, ray_normal, depth, dist_sq);
2024       break;
2025     case PBVH_GRIDS:
2026       hit |= pbvh_grids_node_nearest_to_ray(
2027           bvh, node, origco, ray_start, ray_normal, depth, dist_sq);
2028       break;
2029     case PBVH_BMESH:
2030       hit = pbvh_bmesh_node_nearest_to_ray(
2031           node, ray_start, ray_normal, depth, dist_sq, use_origco);
2032       break;
2033   }
2034
2035   return hit;
2036 }
2037
2038 typedef enum {
2039   ISECT_INSIDE,
2040   ISECT_OUTSIDE,
2041   ISECT_INTERSECT,
2042 } PlaneAABBIsect;
2043
2044 /* Adapted from:
2045  * http://www.gamedev.net/community/forums/topic.asp?topic_id=512123
2046  * Returns true if the AABB is at least partially within the frustum
2047  * (ok, not a real frustum), false otherwise.
2048  */
2049 static PlaneAABBIsect test_planes_aabb(const float bb_min[3],
2050                                        const float bb_max[3],
2051                                        const float (*planes)[4])
2052 {
2053   float vmin[3], vmax[3];
2054   PlaneAABBIsect ret = ISECT_INSIDE;
2055
2056   for (int i = 0; i < 4; ++i) {
2057     for (int axis = 0; axis < 3; ++axis) {
2058       if (planes[i][axis] > 0) {
2059         vmin[axis] = bb_min[axis];
2060         vmax[axis] = bb_max[axis];
2061       }
2062       else {
2063         vmin[axis] = bb_max[axis];
2064         vmax[axis] = bb_min[axis];
2065       }
2066     }
2067
2068     if (dot_v3v3(planes[i], vmin) + planes[i][3] > 0)
2069       return ISECT_OUTSIDE;
2070     else if (dot_v3v3(planes[i], vmax) + planes[i][3] >= 0)
2071       ret = ISECT_INTERSECT;
2072   }
2073
2074   return ret;
2075 }
2076
2077 bool BKE_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data)
2078 {
2079   const float *bb_min, *bb_max;
2080   /* BKE_pbvh_node_get_BB */
2081   bb_min = node->vb.bmin;
2082   bb_max = node->vb.bmax;
2083
2084   return test_planes_aabb(bb_min, bb_max, data) != ISECT_OUTSIDE;
2085 }
2086
2087 bool BKE_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data)
2088 {
2089   const float *bb_min, *bb_max;
2090   /* BKE_pbvh_node_get_BB */
2091   bb_min = node->vb.bmin;
2092   bb_max = node->vb.bmax;
2093
2094   return test_planes_aabb(bb_min, bb_max, data) != ISECT_INSIDE;
2095 }
2096
2097 struct PBVHNodeDrawCallbackData {
2098   void (*draw_fn)(void *user_data, GPUBatch *batch);
2099   void *user_data;
2100   bool fast;
2101   bool only_mask; /* Only draw nodes that have mask data. */
2102   bool wires;
2103 };
2104
2105 static void pbvh_node_draw_cb(PBVHNode *node, void *data_v)
2106 {
2107   struct PBVHNodeDrawCallbackData *data = data_v;
2108
2109   if (!(node->flag & PBVH_FullyHidden)) {
2110     GPUBatch *batch = GPU_pbvh_buffers_batch_get(node->draw_buffers, data->fast, data->wires);
2111     bool show_mask = GPU_pbvh_buffers_has_mask(node->draw_buffers);
2112     if (!data->only_mask || show_mask) {
2113       if (batch != NULL) {
2114         data->draw_fn(data->user_data, batch);
2115       }
2116     }
2117   }
2118 }
2119
2120 /**
2121  * Version of #BKE_pbvh_draw that runs a callback.
2122  */
2123 void BKE_pbvh_draw_cb(PBVH *bvh,
2124                       float (*planes)[4],
2125                       float (*fnors)[3],
2126                       bool fast,
2127                       bool wires,
2128                       bool only_mask,
2129                       void (*draw_fn)(void *user_data, GPUBatch *batch),
2130                       void *user_data)
2131 {
2132   struct PBVHNodeDrawCallbackData draw_data = {
2133       .only_mask = only_mask,
2134       .fast = fast,
2135       .wires = wires,
2136       .draw_fn = draw_fn,
2137       .user_data = user_data,
2138   };
2139   PBVHNode **nodes;
2140   int totnode;
2141
2142   BKE_pbvh_search_gather(bvh,
2143                          update_search_cb,
2144                          POINTER_FROM_INT(PBVH_UpdateNormals | PBVH_UpdateDrawBuffers),
2145                          &nodes,
2146                          &totnode);
2147
2148   pbvh_update_normals(bvh, nodes, totnode, fnors);
2149   pbvh_update_draw_buffers(bvh, nodes, totnode);
2150
2151   if (nodes)
2152     MEM_freeN(nodes);
2153
2154   if (planes) {
2155     BKE_pbvh_search_callback(
2156         bvh, BKE_pbvh_node_planes_contain_AABB, planes, pbvh_node_draw_cb, &draw_data);
2157   }
2158   else {
2159     BKE_pbvh_search_callback(bvh, NULL, NULL, pbvh_node_draw_cb, &draw_data);
2160   }
2161 #if 0
2162   if (G.debug_value == 14)
2163     pbvh_draw_BB(bvh);
2164 #endif
2165 }
2166
2167 void BKE_pbvh_grids_update(
2168     PBVH *bvh, CCGElem **grids, void **gridfaces, DMFlagMat *flagmats, BLI_bitmap **grid_hidden)
2169 {
2170   bvh->grids = grids;
2171   bvh->gridfaces = gridfaces;
2172
2173   if (flagmats != bvh->grid_flag_mats || bvh->grid_hidden != grid_hidden) {
2174     bvh->grid_flag_mats = flagmats;
2175     bvh->grid_hidden = grid_hidden;
2176
2177     for (int a = 0; a < bvh->totnode; ++a)
2178       BKE_pbvh_node_mark_rebuild_draw(&bvh->nodes[a]);
2179   }
2180 }
2181
2182 /* Get the node's displacement layer, creating it if necessary */
2183 float *BKE_pbvh_node_layer_disp_get(PBVH *bvh, PBVHNode *node)
2184 {
2185   if (!node->layer_disp) {
2186     int totvert = 0;
2187     BKE_pbvh_node_num_verts(bvh, node, &totvert, NULL);
2188     node->layer_disp = MEM_callocN(sizeof(float) * totvert, "layer disp");
2189   }
2190   return node->layer_disp;
2191 }
2192
2193 /* If the node has a displacement layer, free it and set to null */
2194 void BKE_pbvh_node_layer_disp_free(PBVHNode *node)
2195 {
2196   if (node->layer_disp) {
2197     MEM_freeN(node->layer_disp);
2198     node->layer_disp = NULL;
2199   }
2200 }
2201
2202 float (*BKE_pbvh_get_vertCos(PBVH *pbvh))[3]
2203 {
2204   float(*vertCos)[3] = NULL;
2205
2206   if (pbvh->verts) {
2207     MVert *mvert = pbvh->verts;
2208
2209     vertCos = MEM_callocN(3 * pbvh->totvert * sizeof(float), "BKE_pbvh_get_vertCoords");
2210     float *co = (float *)vertCos;
2211
2212     for (int a = 0; a < pbvh->totvert; a++, mvert++, co += 3) {
2213       copy_v3_v3(co, mvert->co);
2214     }
2215   }
2216
2217   return vertCos;
2218 }
2219
2220 void BKE_pbvh_apply_vertCos(PBVH *pbvh, float (*vertCos)[3], const int totvert)
2221 {
2222   if (totvert != pbvh->totvert) {
2223     BLI_assert(!"PBVH: Given deforming vcos number does not natch PBVH vertex number!");
2224     return;
2225   }
2226
2227   if (!pbvh->deformed) {
2228     if (pbvh->verts) {
2229       /* if pbvh is not already deformed, verts/faces points to the */
2230       /* original data and applying new coords to this arrays would lead to */
2231       /* unneeded deformation -- duplicate verts/faces to avoid this */
2232
2233       pbvh->verts = MEM_dupallocN(pbvh->verts);
2234       /* No need to dupalloc pbvh->looptri, this one is 'totally owned' by pbvh, it's never some mesh data. */
2235
2236       pbvh->deformed = true;
2237     }
2238   }
2239
2240   if (pbvh->verts) {
2241     MVert *mvert = pbvh->verts;
2242     /* copy new verts coords */
2243     for (int a = 0; a < pbvh->totvert; ++a, ++mvert) {
2244       /* no need for float comparison here (memory is exactly equal or not) */
2245       if (memcmp(mvert->co, vertCos[a], sizeof(float[3])) != 0) {
2246         copy_v3_v3(mvert->co, vertCos[a]);
2247         mvert->flag |= ME_VERT_PBVH_UPDATE;
2248       }
2249     }
2250
2251     /* coordinates are new -- normals should also be updated */
2252     BKE_mesh_calc_normals_looptri(
2253         pbvh->verts, pbvh->totvert, pbvh->mloop, pbvh->looptri, pbvh->totprim, NULL);
2254
2255     for (int a = 0; a < pbvh->totnode; ++a)
2256       BKE_pbvh_node_mark_update(&pbvh->nodes[a]);
2257
2258     BKE_pbvh_update(pbvh, PBVH_UpdateBB, NULL);
2259     BKE_pbvh_update(pbvh, PBVH_UpdateOriginalBB, NULL);
2260   }
2261 }
2262
2263 bool BKE_pbvh_isDeformed(PBVH *pbvh)
2264 {
2265   return pbvh->deformed;
2266 }
2267 /* Proxies */
2268
2269 PBVHProxyNode *BKE_pbvh_node_add_proxy(PBVH *bvh, PBVHNode *node)
2270 {
2271   int index, totverts;
2272
2273   index = node->proxy_count;
2274
2275   node->proxy_count++;
2276
2277   if (node->proxies)
2278     node->proxies = MEM_reallocN(node->proxies, node->proxy_count * sizeof(PBVHProxyNode));
2279   else
2280     node->proxies = MEM_mallocN(sizeof(PBVHProxyNode), "PBVHNodeProxy");
2281
2282   BKE_pbvh_node_num_verts(bvh, node, &totverts, NULL);
2283   node->proxies[index].co = MEM_callocN(sizeof(float[3]) * totverts, "PBVHNodeProxy.co");
2284
2285   return node->proxies + index;
2286 }
2287
2288 void BKE_pbvh_node_free_proxies(PBVHNode *node)
2289 {
2290   for (int p = 0; p < node->proxy_count; p++) {
2291     MEM_freeN(node->proxies[p].co);
2292     node->proxies[p].co = NULL;
2293   }
2294
2295   MEM_freeN(node->proxies);
2296   node->proxies = NULL;
2297
2298   node->proxy_count = 0;
2299 }
2300
2301 void BKE_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***r_array, int *r_tot)
2302 {
2303   PBVHNode **array = NULL;
2304   int tot = 0, space = 0;
2305
2306   for (int n = 0; n < pbvh->totnode; n++) {
2307     PBVHNode *node = pbvh->nodes + n;
2308
2309     if (node->proxy_count > 0) {
2310       if (tot == space) {
2311         /* resize array if needed */
2312         space = (tot == 0) ? 32 : space * 2;
2313         array = MEM_recallocN_id(array, sizeof(PBVHNode *) * space, __func__);
2314       }
2315
2316       array[tot] = node;
2317       tot++;
2318     }
2319   }
2320
2321   if (tot == 0 && array) {
2322     MEM_freeN(array);
2323     array = NULL;
2324   }
2325
2326   *r_array = array;
2327   *r_tot = tot;
2328 }
2329
2330 void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node, PBVHVertexIter *vi, int mode)
2331 {
2332   struct CCGElem **grids;
2333   struct MVert *verts;
2334   const int *vert_indices;
2335   int *grid_indices;
2336   int totgrid, gridsize, uniq_verts, totvert;
2337
2338   vi->grid = NULL;
2339   vi->no = NULL;
2340   vi->fno = NULL;
2341   vi->mvert = NULL;
2342
2343   BKE_pbvh_node_get_grids(bvh, node, &grid_indices, &totgrid, NULL, &gridsize, &grids);
2344   BKE_pbvh_node_num_verts(bvh, node, &uniq_verts, &totvert);
2345   BKE_pbvh_node_get_verts(bvh, node, &vert_indices, &verts);
2346   vi->key = &bvh->gridkey;
2347
2348   vi->grids = grids;
2349   vi->grid_indices = grid_indices;
2350   vi->totgrid = (grids) ? totgrid : 1;
2351   vi->gridsize = gridsize;
2352
2353   if (mode == PBVH_ITER_ALL)
2354     vi->totvert = totvert;
2355   else
2356     vi->totvert = uniq_verts;
2357   vi->vert_indices = vert_indices;
2358   vi->mverts = verts;
2359
2360   if (bvh->type == PBVH_BMESH) {
2361     BLI_gsetIterator_init(&vi->bm_unique_verts, node->bm_unique_verts);
2362     BLI_gsetIterator_init(&vi->bm_other_verts, node->bm_other_verts);
2363     vi->bm_vdata = &bvh->bm->vdata;
2364     vi->cd_vert_mask_offset = CustomData_get_offset(vi->bm_vdata, CD_PAINT_MASK);
2365   }
2366
2367   vi->gh = NULL;
2368   if (vi->grids && mode == PBVH_ITER_UNIQUE)
2369     vi->grid_hidden = bvh->grid_hidden;
2370
2371   vi->mask = NULL;
2372   if (bvh->type == PBVH_FACES)
2373     vi->vmask = CustomData_get_layer(bvh->vdata, CD_PAINT_MASK);
2374 }
2375
2376 bool pbvh_has_mask(PBVH *bvh)
2377 {
2378   switch (bvh->type) {
2379     case PBVH_GRIDS:
2380       return (bvh->gridkey.has_mask != 0);
2381     case PBVH_FACES:
2382       return (bvh->vdata && CustomData_get_layer(bvh->vdata, CD_PAINT_MASK));
2383     case PBVH_BMESH:
2384       return (bvh->bm && (CustomData_get_offset(&bvh->bm->vdata, CD_PAINT_MASK) != -1));
2385   }
2386
2387   return false;
2388 }
2389
2390 void pbvh_show_diffuse_color_set(PBVH *bvh, bool show_diffuse_color)
2391 {
2392   bvh->show_diffuse_color = !pbvh_has_mask(bvh) || show_diffuse_color;
2393 }
2394
2395 void pbvh_show_mask_set(PBVH *bvh, bool show_mask)
2396 {
2397   bvh->show_mask = show_mask;
2398 }