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