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