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