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