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