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