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