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