Add dynamic topology support to the PBVH
[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         BLI_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                 BLI_pbvh_vertex_iter_begin(bvh, node, vd, PBVH_ITER_ALL)
136                 {
137                         BB_expand(&vb, vd.co);
138                 }
139                 BLI_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 BLI_pbvh_node_BB_reset(PBVHNode *node)
152 //{
153 //      BB_reset(&node->vb);
154 //}
155 //
156 //void BLI_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_isDone(iter) == FALSE;
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 BLI_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 BLI_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 *BLI_pbvh_new(void)
582 {
583         PBVH *bvh = MEM_callocN(sizeof(PBVH), "pbvh");
584
585         return bvh;
586 }
587
588 void BLI_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                         BLI_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, BLI_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 BLI_pbvh_search_gather(PBVH *bvh,
750                             BLI_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 BLI_pbvh_search_callback(PBVH *bvh,
791                               BLI_pbvh_SearchCallback scb, void *search_data,
792                               BLI_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, BLI_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 BLI_pbvh_node_get_tmin(PBVHNode *node)
858 {
859         return node->tmin;
860 }
861
862 static void BLI_pbvh_search_callback_occluded(PBVH *bvh,
863                                               BLI_pbvh_SearchCallback scb, void *search_data,
864                                               BLI_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 BLI_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         BLI_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 BLI_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 BLI_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_isDone(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 BLI_pbvh_type(const PBVH *bvh)
1237 {
1238         return bvh->type;
1239 }
1240
1241 BLI_bitmap *BLI_pbvh_grid_hidden(const PBVH *bvh)
1242 {
1243         BLI_assert(bvh->type == PBVH_GRIDS);
1244         return bvh->grid_hidden;
1245 }
1246
1247 void BLI_pbvh_get_grid_key(const PBVH *bvh, CCGKey *key)
1248 {
1249         BLI_assert(bvh->type == PBVH_GRIDS);
1250         *key = bvh->gridkey;
1251 }
1252
1253 BMesh *BLI_pbvh_get_bmesh(PBVH *bvh)
1254 {
1255         BLI_assert(bvh->type == PBVH_BMESH);
1256         return bvh->bm;
1257 }
1258
1259 /***************************** Node Access ***********************************/
1260
1261 void BLI_pbvh_node_mark_update(PBVHNode *node)
1262 {
1263         node->flag |= PBVH_UpdateNormals | PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw;
1264 }
1265
1266 void BLI_pbvh_node_mark_rebuild_draw(PBVHNode *node)
1267 {
1268         node->flag |= PBVH_RebuildDrawBuffers | PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw;
1269 }
1270
1271 void BLI_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden)
1272 {
1273         BLI_assert(node->flag & PBVH_Leaf);
1274         
1275         if (fully_hidden)
1276                 node->flag |= PBVH_FullyHidden;
1277         else
1278                 node->flag &= ~PBVH_FullyHidden;
1279 }
1280
1281 void BLI_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node, int **vert_indices, MVert **verts)
1282 {
1283         if (vert_indices) *vert_indices = node->vert_indices;
1284         if (verts) *verts = bvh->verts;
1285 }
1286
1287 void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node, int *uniquevert, int *totvert)
1288 {
1289         int tot;
1290         
1291         switch (bvh->type) {
1292                 case PBVH_GRIDS:
1293                         tot = node->totprim * bvh->gridkey.grid_area;
1294                         if (totvert) *totvert = tot;
1295                         if (uniquevert) *uniquevert = tot;
1296                         break;
1297                 case PBVH_FACES:
1298                         if (totvert) *totvert = node->uniq_verts + node->face_verts;
1299                         if (uniquevert) *uniquevert = node->uniq_verts;
1300                         break;
1301                 case PBVH_BMESH:
1302                         tot = BLI_ghash_size(node->bm_unique_verts);
1303                         if (totvert) *totvert = tot + BLI_ghash_size(node->bm_other_verts);
1304                         if (uniquevert) *uniquevert = tot;
1305                         break;
1306         }
1307 }
1308
1309 void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node, int **grid_indices, int *totgrid, int *maxgrid, int *gridsize, CCGElem ***griddata, DMGridAdjacency **gridadj)
1310 {
1311         switch (bvh->type) {
1312                 case PBVH_GRIDS:
1313                         if (grid_indices) *grid_indices = node->prim_indices;
1314                         if (totgrid) *totgrid = node->totprim;
1315                         if (maxgrid) *maxgrid = bvh->totgrid;
1316                         if (gridsize) *gridsize = bvh->gridkey.grid_size;
1317                         if (griddata) *griddata = bvh->grids;
1318                         if (gridadj) *gridadj = bvh->gridadj;
1319                         break;
1320                 case PBVH_FACES:
1321                 case PBVH_BMESH:
1322                         if (grid_indices) *grid_indices = NULL;
1323                         if (totgrid) *totgrid = 0;
1324                         if (maxgrid) *maxgrid = 0;
1325                         if (gridsize) *gridsize = 0;
1326                         if (griddata) *griddata = NULL;
1327                         if (gridadj) *gridadj = NULL;
1328                         break;
1329         }
1330 }
1331
1332 void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
1333 {
1334         copy_v3_v3(bb_min, node->vb.bmin);
1335         copy_v3_v3(bb_max, node->vb.bmax);
1336 }
1337
1338 void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
1339 {
1340         copy_v3_v3(bb_min, node->orig_vb.bmin);
1341         copy_v3_v3(bb_max, node->orig_vb.bmax);
1342 }
1343
1344 void BLI_pbvh_node_get_proxies(PBVHNode *node, PBVHProxyNode **proxies, int *proxy_count)
1345 {
1346         if (node->proxy_count > 0) {
1347                 if (proxies) *proxies = node->proxies;
1348                 if (proxy_count) *proxy_count = node->proxy_count;
1349         }
1350         else {
1351                 if (proxies) *proxies = 0;
1352                 if (proxy_count) *proxy_count = 0;
1353         }
1354 }
1355
1356 /********************************* Raycast ***********************************/
1357
1358 typedef struct {
1359         IsectRayAABBData ray;
1360         int original;
1361 } RaycastData;
1362
1363 static int ray_aabb_intersect(PBVHNode *node, void *data_v)
1364 {
1365         RaycastData *rcd = data_v;
1366         float bb_min[3], bb_max[3];
1367
1368         if (rcd->original)
1369                 BLI_pbvh_node_get_original_BB(node, bb_min, bb_max);
1370         else
1371                 BLI_pbvh_node_get_BB(node, bb_min, bb_max);
1372
1373         return isect_ray_aabb(&rcd->ray, bb_min, bb_max, &node->tmin);
1374 }
1375
1376 void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitOccludedCallback cb, void *data,
1377                       const float ray_start[3], const float ray_normal[3],
1378                       int original)
1379 {
1380         RaycastData rcd;
1381
1382         isect_ray_aabb_initialize(&rcd.ray, ray_start, ray_normal);
1383         rcd.original = original;
1384
1385         BLI_pbvh_search_callback_occluded(bvh, ray_aabb_intersect, &rcd, cb, data);
1386 }
1387
1388 int ray_face_intersection(const float ray_start[3],
1389                                                   const float ray_normal[3],
1390                                                   const float *t0, const float *t1,
1391                                                   const float *t2, const float *t3,
1392                                                   float *fdist)
1393 {
1394         float dist;
1395
1396         if ((isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t1, t2, &dist, NULL, 0.1f) && dist < *fdist) ||
1397             (t3 && isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t2, t3, &dist, NULL, 0.1f) && dist < *fdist))
1398         {
1399                 *fdist = dist;
1400                 return 1;
1401         }
1402         else {
1403                 return 0;
1404         }
1405 }
1406
1407 static int pbvh_faces_node_raycast(PBVH *bvh, const PBVHNode *node,
1408                                    float (*origco)[3],
1409                                    const float ray_start[3],
1410                                    const float ray_normal[3], float *dist)
1411 {
1412         const MVert *vert = bvh->verts;
1413         const int *faces = node->prim_indices;
1414         int i, hit = 0, totface = node->totprim;
1415
1416         for (i = 0; i < totface; ++i) {
1417                 const MFace *f = bvh->faces + faces[i];
1418                 const int *face_verts = node->face_vert_indices[i];
1419
1420                 if (paint_is_face_hidden(f, vert))
1421                         continue;
1422
1423                 if (origco) {
1424                         /* intersect with backuped original coordinates */
1425                         hit |= ray_face_intersection(ray_start, ray_normal,
1426                                                      origco[face_verts[0]],
1427                                                      origco[face_verts[1]],
1428                                                      origco[face_verts[2]],
1429                                                      f->v4 ? origco[face_verts[3]] : NULL,
1430                                                      dist);
1431                 }
1432                 else {
1433                         /* intersect with current coordinates */
1434                         hit |= ray_face_intersection(ray_start, ray_normal,
1435                                                      vert[f->v1].co,
1436                                                      vert[f->v2].co,
1437                                                      vert[f->v3].co,
1438                                                      f->v4 ? vert[f->v4].co : NULL,
1439                                                      dist);
1440                 }
1441         }
1442
1443         return hit;
1444 }
1445
1446 static int pbvh_grids_node_raycast(PBVH *bvh, PBVHNode *node,
1447                                    float (*origco)[3],
1448                                    const float ray_start[3],
1449                                    const float ray_normal[3], float *dist)
1450 {
1451         int totgrid = node->totprim;
1452         int gridsize = bvh->gridkey.grid_size;
1453         int i, x, y, hit = 0;
1454
1455         for (i = 0; i < totgrid; ++i) {
1456                 CCGElem *grid = bvh->grids[node->prim_indices[i]];
1457                 BLI_bitmap gh;
1458
1459                 if (!grid)
1460                         continue;
1461
1462                 gh = bvh->grid_hidden[node->prim_indices[i]];
1463
1464                 for (y = 0; y < gridsize - 1; ++y) {
1465                         for (x = 0; x < gridsize - 1; ++x) {
1466                                 /* check if grid face is hidden */
1467                                 if (gh) {
1468                                         if (paint_is_grid_face_hidden(gh, gridsize, x, y))
1469                                                 continue;
1470                                 }
1471
1472                                 if (origco) {
1473                                         hit |= ray_face_intersection(ray_start, ray_normal,
1474                                                                      origco[y * gridsize + x],
1475                                                                      origco[y * gridsize + x + 1],
1476                                                                      origco[(y + 1) * gridsize + x + 1],
1477                                                                      origco[(y + 1) * gridsize + x],
1478                                                                      dist);
1479                                 }
1480                                 else {
1481                                         hit |= ray_face_intersection(ray_start, ray_normal,
1482                                                                      CCG_grid_elem_co(&bvh->gridkey, grid, x, y),
1483                                                                      CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y),
1484                                                                      CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y + 1),
1485                                                                      CCG_grid_elem_co(&bvh->gridkey, grid, x, y + 1),
1486                                                                      dist);
1487                                 }
1488                         }
1489                 }
1490
1491                 if (origco)
1492                         origco += gridsize * gridsize;
1493         }
1494
1495         return hit;
1496 }
1497
1498 int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3], int use_origco,
1499                           const float ray_start[3], const float ray_normal[3],
1500                           float *dist)
1501 {
1502         int hit = 0;
1503
1504         if (node->flag & PBVH_FullyHidden)
1505                 return 0;
1506
1507         switch (bvh->type) {
1508                 case PBVH_FACES:
1509                         hit |= pbvh_faces_node_raycast(bvh, node, origco,
1510                                                        ray_start, ray_normal, dist);
1511                         break;
1512                 case PBVH_GRIDS:
1513                         hit |= pbvh_grids_node_raycast(bvh, node, origco,
1514                                                        ray_start, ray_normal, dist);
1515                         break;
1516                 case PBVH_BMESH:
1517                         hit = pbvh_bmesh_node_raycast(node, ray_start, ray_normal, dist, use_origco);
1518                         break;
1519         }
1520
1521         return hit;
1522 }
1523
1524 //#include <GL/glew.h>
1525
1526 void BLI_pbvh_node_draw(PBVHNode *node, void *setMaterial)
1527 {
1528 #if 0
1529         /* XXX: Just some quick code to show leaf nodes in different colors */
1530         float col[3]; int i;
1531
1532         if (0) { //is_partial) {
1533                 col[0] = (rand() / (float)RAND_MAX); col[1] = col[2] = 0.6;
1534         }
1535         else {
1536                 srand((long long)node);
1537                 for (i = 0; i < 3; ++i)
1538                         col[i] = (rand() / (float)RAND_MAX) * 0.3 + 0.7;
1539         }
1540         glMaterialfv(GL_FRONT_AND_BACK, GL_DIFFUSE, col);
1541
1542         glColor3f(1, 0, 0);
1543 #endif
1544
1545         if (!(node->flag & PBVH_FullyHidden))
1546                 GPU_draw_buffers(node->draw_buffers, setMaterial);
1547 }
1548
1549 typedef enum {
1550         ISECT_INSIDE,
1551         ISECT_OUTSIDE,
1552         ISECT_INTERSECT
1553 } PlaneAABBIsect;
1554
1555 /* Adapted from:
1556  * http://www.gamedev.net/community/forums/topic.asp?topic_id=512123
1557  * Returns true if the AABB is at least partially within the frustum
1558  * (ok, not a real frustum), false otherwise.
1559  */
1560 static PlaneAABBIsect test_planes_aabb(const float bb_min[3],
1561                                        const float bb_max[3],
1562                                        const float (*planes)[4])
1563 {
1564         float vmin[3], vmax[3];
1565         PlaneAABBIsect ret = ISECT_INSIDE;
1566         int i, axis;
1567         
1568         for (i = 0; i < 4; ++i) {
1569                 for (axis = 0; axis < 3; ++axis) {
1570                         if (planes[i][axis] > 0) {
1571                                 vmin[axis] = bb_min[axis];
1572                                 vmax[axis] = bb_max[axis];
1573                         }
1574                         else {
1575                                 vmin[axis] = bb_max[axis];
1576                                 vmax[axis] = bb_min[axis];
1577                         }
1578                 }
1579                 
1580                 if (dot_v3v3(planes[i], vmin) + planes[i][3] > 0)
1581                         return ISECT_OUTSIDE;
1582                 else if (dot_v3v3(planes[i], vmax) + planes[i][3] >= 0)
1583                         ret = ISECT_INTERSECT;
1584         }
1585
1586         return ret;
1587 }
1588
1589 int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data)
1590 {
1591         float bb_min[3], bb_max[3];
1592         
1593         BLI_pbvh_node_get_BB(node, bb_min, bb_max);
1594         return test_planes_aabb(bb_min, bb_max, data) != ISECT_OUTSIDE;
1595 }
1596
1597 int BLI_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data)
1598 {
1599         float bb_min[3], bb_max[3];
1600         
1601         BLI_pbvh_node_get_BB(node, bb_min, bb_max);
1602         return test_planes_aabb(bb_min, bb_max, data) != ISECT_INSIDE;
1603 }
1604
1605 static void pbvh_node_check_diffuse_changed(PBVH *bvh, PBVHNode *node)
1606 {
1607         if (!node->draw_buffers)
1608                 return;
1609
1610         if (GPU_buffers_diffuse_changed(node->draw_buffers, bvh->show_diffuse_color))
1611                 node->flag |= PBVH_UpdateDrawBuffers;
1612 }
1613
1614 void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3],
1615                    DMSetMaterial setMaterial)
1616 {
1617         PBVHNode **nodes;
1618         int a, totnode;
1619
1620         for (a = 0; a < bvh->totnode; a++)
1621                 pbvh_node_check_diffuse_changed(bvh, &bvh->nodes[a]);
1622
1623         BLI_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(PBVH_UpdateNormals | PBVH_UpdateDrawBuffers),
1624                                &nodes, &totnode);
1625
1626         pbvh_update_normals(bvh, nodes, totnode, face_nors);
1627         pbvh_update_draw_buffers(bvh, nodes, totnode);
1628
1629         if (nodes) MEM_freeN(nodes);
1630
1631         if (planes) {
1632                 BLI_pbvh_search_callback(bvh, BLI_pbvh_node_planes_contain_AABB,
1633                                          planes, BLI_pbvh_node_draw, setMaterial);
1634         }
1635         else {
1636                 BLI_pbvh_search_callback(bvh, NULL, NULL, BLI_pbvh_node_draw, setMaterial);
1637         }
1638 }
1639
1640 void BLI_pbvh_grids_update(PBVH *bvh, CCGElem **grids, DMGridAdjacency *gridadj, void **gridfaces,
1641                            DMFlagMat *flagmats, BLI_bitmap *grid_hidden)
1642 {
1643         int a;
1644
1645         bvh->grids = grids;
1646         bvh->gridadj = gridadj;
1647         bvh->gridfaces = gridfaces;
1648
1649         if (flagmats != bvh->grid_flag_mats || bvh->grid_hidden != grid_hidden) {
1650                 bvh->grid_flag_mats = flagmats;
1651                 bvh->grid_hidden = grid_hidden;
1652
1653                 for (a = 0; a < bvh->totnode; ++a)
1654                         BLI_pbvh_node_mark_rebuild_draw(&bvh->nodes[a]);
1655         }
1656 }
1657
1658 /* Get the node's displacement layer, creating it if necessary */
1659 float *BLI_pbvh_node_layer_disp_get(PBVH *bvh, PBVHNode *node)
1660 {
1661         if (!node->layer_disp) {
1662                 int totvert = 0;
1663                 BLI_pbvh_node_num_verts(bvh, node, &totvert, NULL);
1664                 node->layer_disp = MEM_callocN(sizeof(float) * totvert, "layer disp");
1665         }
1666         return node->layer_disp;
1667 }
1668
1669 /* If the node has a displacement layer, free it and set to null */
1670 void BLI_pbvh_node_layer_disp_free(PBVHNode *node)
1671 {
1672         if (node->layer_disp) {
1673                 MEM_freeN(node->layer_disp);
1674                 node->layer_disp = NULL;
1675         }
1676 }
1677
1678 float (*BLI_pbvh_get_vertCos(PBVH * pbvh))[3]
1679 {
1680         int a;
1681         float (*vertCos)[3] = NULL;
1682
1683         if (pbvh->verts) {
1684                 float *co;
1685                 MVert *mvert = pbvh->verts;
1686
1687                 vertCos = MEM_callocN(3 * pbvh->totvert * sizeof(float), "BLI_pbvh_get_vertCoords");
1688                 co = (float *)vertCos;
1689
1690                 for (a = 0; a < pbvh->totvert; a++, mvert++, co += 3) {
1691                         copy_v3_v3(co, mvert->co);
1692                 }
1693         }
1694
1695         return vertCos;
1696 }
1697
1698 void BLI_pbvh_apply_vertCos(PBVH *pbvh, float (*vertCos)[3])
1699 {
1700         int a;
1701
1702         if (!pbvh->deformed) {
1703                 if (pbvh->verts) {
1704                         /* if pbvh is not already deformed, verts/faces points to the */
1705                         /* original data and applying new coords to this arrays would lead to */
1706                         /* unneeded deformation -- duplicate verts/faces to avoid this */
1707
1708                         pbvh->verts = MEM_dupallocN(pbvh->verts);
1709                         pbvh->faces = MEM_dupallocN(pbvh->faces);
1710
1711                         pbvh->deformed = 1;
1712                 }
1713         }
1714
1715         if (pbvh->verts) {
1716                 MVert *mvert = pbvh->verts;
1717                 /* copy new verts coords */
1718                 for (a = 0; a < pbvh->totvert; ++a, ++mvert) {
1719                         copy_v3_v3(mvert->co, vertCos[a]);
1720                         mvert->flag |= ME_VERT_PBVH_UPDATE;
1721                 }
1722
1723                 /* coordinates are new -- normals should also be updated */
1724                 BKE_mesh_calc_normals_tessface(pbvh->verts, pbvh->totvert, pbvh->faces, pbvh->totprim, NULL);
1725
1726                 for (a = 0; a < pbvh->totnode; ++a)
1727                         BLI_pbvh_node_mark_update(&pbvh->nodes[a]);
1728
1729                 BLI_pbvh_update(pbvh, PBVH_UpdateBB, NULL);
1730                 BLI_pbvh_update(pbvh, PBVH_UpdateOriginalBB, NULL);
1731
1732         }
1733 }
1734
1735 int BLI_pbvh_isDeformed(PBVH *pbvh)
1736 {
1737         return pbvh->deformed;
1738 }
1739 /* Proxies */
1740
1741 PBVHProxyNode *BLI_pbvh_node_add_proxy(PBVH *bvh, PBVHNode *node)
1742 {
1743         int index, totverts;
1744
1745         #pragma omp critical
1746         {
1747
1748                 index = node->proxy_count;
1749
1750                 node->proxy_count++;
1751
1752                 if (node->proxies)
1753                         node->proxies = MEM_reallocN(node->proxies, node->proxy_count * sizeof(PBVHProxyNode));
1754                 else
1755                         node->proxies = MEM_mallocN(sizeof(PBVHProxyNode), "PBVHNodeProxy");
1756
1757                 BLI_pbvh_node_num_verts(bvh, node, &totverts, NULL);
1758                 node->proxies[index].co = MEM_callocN(sizeof(float[3]) * totverts, "PBVHNodeProxy.co");
1759         }
1760
1761         return node->proxies + index;
1762 }
1763
1764 void BLI_pbvh_node_free_proxies(PBVHNode *node)
1765 {
1766         #pragma omp critical
1767         {
1768                 int p;
1769
1770                 for (p = 0; p < node->proxy_count; p++) {
1771                         MEM_freeN(node->proxies[p].co);
1772                         node->proxies[p].co = 0;
1773                 }
1774
1775                 MEM_freeN(node->proxies);
1776                 node->proxies = 0;
1777
1778                 node->proxy_count = 0;
1779         }
1780 }
1781
1782 void BLI_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***r_array,  int *r_tot)
1783 {
1784         PBVHNode **array = NULL, **newarray, *node;
1785         int tot = 0, space = 0;
1786         int n;
1787
1788         for (n = 0; n < pbvh->totnode; n++) {
1789                 node = pbvh->nodes + n;
1790
1791                 if (node->proxy_count > 0) {
1792                         if (tot == space) {
1793                                 /* resize array if needed */
1794                                 space = (tot == 0) ? 32 : space * 2;
1795                                 newarray = MEM_callocN(sizeof(PBVHNode) * space, "BLI_pbvh_gather_proxies");
1796
1797                                 if (array) {
1798                                         memcpy(newarray, array, sizeof(PBVHNode) * tot);
1799                                         MEM_freeN(array);
1800                                 }
1801
1802                                 array = newarray;
1803                         }
1804
1805                         array[tot] = node;
1806                         tot++;
1807                 }
1808         }
1809
1810         if (tot == 0 && array) {
1811                 MEM_freeN(array);
1812                 array = NULL;
1813         }
1814
1815         *r_array = array;
1816         *r_tot = tot;
1817 }
1818
1819 void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node,
1820                            PBVHVertexIter *vi, int mode)
1821 {
1822         struct CCGElem **grids;
1823         struct MVert *verts;
1824         int *grid_indices, *vert_indices;
1825         int totgrid, gridsize, uniq_verts, totvert;
1826         
1827         vi->grid = 0;
1828         vi->no = 0;
1829         vi->fno = 0;
1830         vi->mvert = 0;
1831         
1832         BLI_pbvh_node_get_grids(bvh, node, &grid_indices, &totgrid, NULL, &gridsize, &grids, NULL);
1833         BLI_pbvh_node_num_verts(bvh, node, &uniq_verts, &totvert);
1834         BLI_pbvh_node_get_verts(bvh, node, &vert_indices, &verts);
1835         vi->key = &bvh->gridkey;
1836         
1837         vi->grids = grids;
1838         vi->grid_indices = grid_indices;
1839         vi->totgrid = (grids) ? totgrid : 1;
1840         vi->gridsize = gridsize;
1841         
1842         if (mode == PBVH_ITER_ALL)
1843                 vi->totvert = totvert;
1844         else
1845                 vi->totvert = uniq_verts;
1846         vi->vert_indices = vert_indices;
1847         vi->mverts = verts;
1848
1849         if (bvh->type == PBVH_BMESH) {
1850                 BLI_ghashIterator_init(&vi->bm_unique_verts, node->bm_unique_verts);
1851                 BLI_ghashIterator_init(&vi->bm_other_verts, node->bm_other_verts);
1852                 vi->bm_vdata = &bvh->bm->vdata;
1853         }
1854
1855         vi->gh = NULL;
1856         if (vi->grids && mode == PBVH_ITER_UNIQUE)
1857                 vi->grid_hidden = bvh->grid_hidden;
1858
1859         vi->mask = NULL;
1860         if (bvh->type == PBVH_FACES)
1861                 vi->vmask = CustomData_get_layer(bvh->vdata, CD_PAINT_MASK);
1862 }
1863
1864 void pbvh_show_diffuse_color_set(PBVH *bvh, int show_diffuse_color)
1865 {
1866         bvh->show_diffuse_color = show_diffuse_color;
1867 }