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