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