82e2090c43256fc5768fc5865dcb19929eba7a72
[blender.git] / source / blender / blenlib / intern / pbvh.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23
24
25 #include "DNA_meshdata_types.h"
26
27 #include "BLI_math.h"
28 #include "BLI_ghash.h"
29 #include "BLI_pbvh.h"
30
31 #include "BKE_DerivedMesh.h"
32 #include "BKE_mesh.h" /* for mesh_calc_normals */
33 #include "BKE_global.h" /* for mesh_calc_normals */
34
35 #include "gpu_buffers.h"
36
37 #define LEAF_LIMIT 10000
38
39 //#define PERFCNTRS
40
41 /* Bitmap */
42 typedef char* BLI_bitmap;
43
44 BLI_bitmap BLI_bitmap_new(int tot)
45 {
46         return MEM_callocN((tot >> 3) + 1, "BLI bitmap");
47 }
48
49 int BLI_bitmap_get(BLI_bitmap b, int index)
50 {
51         return b[index >> 3] & (1 << (index & 7));
52 }
53
54 void BLI_bitmap_set(BLI_bitmap b, int index)
55 {
56         b[index >> 3] |= (1 << (index & 7));
57 }
58
59 void BLI_bitmap_clear(BLI_bitmap b, int index)
60 {
61         b[index >> 3] &= ~(1 << (index & 7));
62 }
63
64 /* Axis-aligned bounding box */
65 typedef struct {
66         float bmin[3], bmax[3];
67 } BB;
68
69 /* Axis-aligned bounding box with centroid */
70 typedef struct {
71         float bmin[3], bmax[3], bcentroid[3];
72 } BBC;
73
74 struct PBVHNode {
75         /* Opaque handle for drawing code */
76         void *draw_buffers;
77
78         int *vert_indices;
79
80         /* Voxel bounds */
81         BB vb;
82         BB orig_vb;
83
84         /* For internal nodes */
85         int children_offset;
86
87         /* Pointer into bvh prim_indices */
88         int *prim_indices;
89         int *face_vert_indices;
90
91         unsigned int totprim;
92         unsigned int uniq_verts, face_verts;
93
94         char flag;
95 };
96
97 struct PBVH {
98         PBVHNode *nodes;
99         int node_mem_count, totnode;
100
101         int *prim_indices;
102         int totprim;
103         int totvert;
104
105         int leaf_limit;
106
107         /* Mesh data */
108         MVert *verts;
109         MFace *faces;
110
111         /* Grid Data */
112         DMGridData **grids;
113         DMGridAdjacency *gridadj;
114         void **gridfaces;
115         int totgrid;
116         int gridsize;
117
118         /* Only used during BVH build and update,
119            don't need to remain valid after */
120         BLI_bitmap vert_bitmap;
121
122 #ifdef PERFCNTRS
123         int perf_modified;
124 #endif
125
126         /* flag are verts/faces deformed */
127         int deformed;
128 };
129
130 #define STACK_FIXED_DEPTH       100
131
132 typedef struct PBVHStack {
133         PBVHNode *node;
134         int revisiting;
135 } PBVHStack;
136
137 typedef struct PBVHIter {
138         PBVH *bvh;
139         BLI_pbvh_SearchCallback scb;
140         void *search_data;
141
142         PBVHStack *stack;
143         int stacksize;
144
145         PBVHStack stackfixed[STACK_FIXED_DEPTH];
146         int stackspace;
147 } PBVHIter;
148
149 static void BB_reset(BB *bb)
150 {
151         bb->bmin[0] = bb->bmin[1] = bb->bmin[2] = FLT_MAX;
152         bb->bmax[0] = bb->bmax[1] = bb->bmax[2] = -FLT_MAX;
153 }
154
155 /* Expand the bounding box to include a new coordinate */
156 static void BB_expand(BB *bb, float co[3])
157 {
158         int i;
159         for(i = 0; i < 3; ++i) {
160                 bb->bmin[i] = MIN2(bb->bmin[i], co[i]);
161                 bb->bmax[i] = MAX2(bb->bmax[i], co[i]);
162         }
163 }
164
165 /* Expand the bounding box to include another bounding box */
166 static void BB_expand_with_bb(BB *bb, BB *bb2)
167 {
168         int i;
169         for(i = 0; i < 3; ++i) {
170                 bb->bmin[i] = MIN2(bb->bmin[i], bb2->bmin[i]);
171                 bb->bmax[i] = MAX2(bb->bmax[i], bb2->bmax[i]);
172         }
173 }
174
175 /* Return 0, 1, or 2 to indicate the widest axis of the bounding box */
176 static int BB_widest_axis(BB *bb)
177 {
178         float dim[3];
179         int i;
180
181         for(i = 0; i < 3; ++i)
182                 dim[i] = bb->bmax[i] - bb->bmin[i];
183
184         if(dim[0] > dim[1]) {
185                 if(dim[0] > dim[2])
186                         return 0;
187                 else
188                         return 2;
189         }
190         else {
191                 if(dim[1] > dim[2])
192                         return 1;
193                 else
194                         return 2;
195         }
196 }
197
198 static void BBC_update_centroid(BBC *bbc)
199 {
200         int i;
201         for(i = 0; i < 3; ++i)
202                 bbc->bcentroid[i] = (bbc->bmin[i] + bbc->bmax[i]) * 0.5f;
203 }
204
205 /* Not recursive */
206 static void update_node_vb(PBVH *bvh, PBVHNode *node)
207 {
208         BB vb;
209
210         BB_reset(&vb);
211         
212         if(node->flag & PBVH_Leaf) {
213                 PBVHVertexIter vd;
214
215                 BLI_pbvh_vertex_iter_begin(bvh, node, vd, PBVH_ITER_ALL) {
216                         BB_expand(&vb, vd.co);
217                 }
218                 BLI_pbvh_vertex_iter_end;
219         }
220         else {
221                 BB_expand_with_bb(&vb,
222                                   &bvh->nodes[node->children_offset].vb);
223                 BB_expand_with_bb(&vb,
224                                   &bvh->nodes[node->children_offset + 1].vb);
225         }
226
227         node->vb= vb;
228 }
229
230 /* Adapted from BLI_kdopbvh.c */
231 /* Returns the index of the first element on the right of the partition */
232 static int partition_indices(int *prim_indices, int lo, int hi, int axis,
233                                  float mid, BBC *prim_bbc)
234 {
235         int i=lo, j=hi;
236         for(;;) {
237                 for(; prim_bbc[prim_indices[i]].bcentroid[axis] < mid; i++);
238                 for(; mid < prim_bbc[prim_indices[j]].bcentroid[axis]; j--);
239                 
240                 if(!(i < j))
241                         return i;
242                 
243                 SWAP(int, prim_indices[i], prim_indices[j]);
244                 i++;
245         }
246 }
247
248 void check_partitioning(int *prim_indices, int lo, int hi, int axis,
249                                    float mid, BBC *prim_bbc, int index_of_2nd_partition)
250 {
251         int i;
252         for(i = lo; i <= hi; ++i) {
253                 const float c = prim_bbc[prim_indices[i]].bcentroid[axis];
254
255                 if((i < index_of_2nd_partition && c > mid) ||
256                    (i > index_of_2nd_partition && c < mid)) {
257                         printf("fail\n");
258                 }
259         }
260 }
261
262 static void grow_nodes(PBVH *bvh, int totnode)
263 {
264         if(totnode > bvh->node_mem_count) {
265                 PBVHNode *prev = bvh->nodes;
266                 bvh->node_mem_count *= 1.33;
267                 if(bvh->node_mem_count < totnode)
268                         bvh->node_mem_count = totnode;
269                 bvh->nodes = MEM_callocN(sizeof(PBVHNode) * bvh->node_mem_count,
270                                          "bvh nodes");
271                 memcpy(bvh->nodes, prev, bvh->totnode * sizeof(PBVHNode));
272                 MEM_freeN(prev);
273         }
274
275         bvh->totnode = totnode;
276 }
277
278 /* Add a vertex to the map, with a positive value for unique vertices and
279    a negative value for additional vertices */
280 static int map_insert_vert(PBVH *bvh, GHash *map,
281                                 unsigned int *face_verts,
282                                 unsigned int *uniq_verts, int vertex)
283 {
284         void *value, *key = SET_INT_IN_POINTER(vertex);
285
286         if(!BLI_ghash_haskey(map, key)) {
287                 if(BLI_bitmap_get(bvh->vert_bitmap, vertex)) {
288                         value = SET_INT_IN_POINTER(-(*face_verts) - 1);
289                         ++(*face_verts);
290                 }
291                 else {
292                         BLI_bitmap_set(bvh->vert_bitmap, vertex);
293                         value = SET_INT_IN_POINTER(*uniq_verts);
294                         ++(*uniq_verts);
295                 }
296                 
297                 BLI_ghash_insert(map, key, value);
298                 return GET_INT_FROM_POINTER(value);
299         }
300         else
301                 return GET_INT_FROM_POINTER(BLI_ghash_lookup(map, key));
302 }
303
304 /* Find vertices used by the faces in this node and update the draw buffers */
305 static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node)
306 {
307         GHashIterator *iter;
308         GHash *map;
309         int i, j, totface;
310
311         map = BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp, "build_mesh_leaf_node gh");
312         
313         node->uniq_verts = node->face_verts = 0;
314         totface= node->totprim;
315
316         node->face_vert_indices = MEM_callocN(sizeof(int) *
317                                          4*totface, "bvh node face vert indices");
318
319         for(i = 0; i < totface; ++i) {
320                 MFace *f = bvh->faces + node->prim_indices[i];
321                 int sides = f->v4 ? 4 : 3;
322
323                 for(j = 0; j < sides; ++j) {
324                         node->face_vert_indices[i*4 + j]= 
325                                 map_insert_vert(bvh, map, &node->face_verts,
326                                                 &node->uniq_verts, (&f->v1)[j]);
327                 }
328         }
329
330         node->vert_indices = MEM_callocN(sizeof(int) *
331                                          (node->uniq_verts + node->face_verts),
332                                          "bvh node vert indices");
333
334         /* Build the vertex list, unique verts first */
335         for(iter = BLI_ghashIterator_new(map), i = 0;
336                 !BLI_ghashIterator_isDone(iter);
337                 BLI_ghashIterator_step(iter), ++i) {
338                 void *value = BLI_ghashIterator_getValue(iter);
339                 int ndx = GET_INT_FROM_POINTER(value);
340
341                 if(ndx < 0)
342                         ndx = -ndx + node->uniq_verts - 1;
343
344                 node->vert_indices[ndx] =
345                         GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(iter));
346         }
347
348         BLI_ghashIterator_free(iter);
349
350         for(i = 0; i < totface*4; ++i)
351                 if(node->face_vert_indices[i] < 0)
352                         node->face_vert_indices[i]= -node->face_vert_indices[i] + node->uniq_verts - 1;
353
354         if(!G.background) {
355                 node->draw_buffers =
356                         GPU_build_mesh_buffers(map, bvh->verts, bvh->faces,
357                                   node->prim_indices,
358                                   node->totprim, node->vert_indices,
359                                   node->uniq_verts,
360                                   node->uniq_verts + node->face_verts);
361         }
362
363         node->flag |= PBVH_UpdateDrawBuffers;
364
365         BLI_ghash_free(map, NULL, NULL);
366 }
367
368 static void build_grids_leaf_node(PBVH *bvh, PBVHNode *node)
369 {
370         if(!G.background) {
371                 node->draw_buffers =
372                         GPU_build_grid_buffers(bvh->grids, node->prim_indices,
373                                 node->totprim, bvh->gridsize);
374         }
375         node->flag |= PBVH_UpdateDrawBuffers;
376 }
377
378 /* Recursively build a node in the tree
379
380    vb is the voxel box around all of the primitives contained in
381    this node.
382
383    cb is the bounding box around all the centroids of the primitives
384    contained in this node
385
386    offset and start indicate a range in the array of primitive indices
387 */
388
389 void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc,
390                    int offset, int count)
391 {
392         int i, axis, end;
393         BB cb_backing;
394
395         /* Decide whether this is a leaf or not */
396         // XXX adapt leaf limit for grids
397         if(count <= bvh->leaf_limit) {
398                 bvh->nodes[node_index].flag |= PBVH_Leaf;
399
400                 bvh->nodes[node_index].prim_indices = bvh->prim_indices + offset;
401                 bvh->nodes[node_index].totprim = count;
402
403                 /* Still need vb for searches */
404                 BB_reset(&bvh->nodes[node_index].vb);
405                 for(i = offset + count - 1; i >= offset; --i) {
406                         BB_expand_with_bb(&bvh->nodes[node_index].vb,
407                                           (BB*)(prim_bbc +
408                                                 bvh->prim_indices[i]));
409                 }
410                 
411                 if(bvh->faces)
412                         build_mesh_leaf_node(bvh, bvh->nodes + node_index);
413                 else
414                         build_grids_leaf_node(bvh, bvh->nodes + node_index);
415                 bvh->nodes[node_index].orig_vb= bvh->nodes[node_index].vb;
416
417                 /* Done with this subtree */
418                 return;
419         }
420         else {
421                 BB_reset(&bvh->nodes[node_index].vb);
422                 bvh->nodes[node_index].children_offset = bvh->totnode;
423                 grow_nodes(bvh, bvh->totnode + 2);
424
425                 if(!cb) {
426                         cb = &cb_backing;
427                         BB_reset(cb);
428                         for(i = offset + count - 1; i >= offset; --i)
429                                 BB_expand(cb, prim_bbc[bvh->prim_indices[i]].bcentroid);
430                 }
431         }
432
433         axis = BB_widest_axis(cb);
434
435         for(i = offset + count - 1; i >= offset; --i) {
436                 BB_expand_with_bb(&bvh->nodes[node_index].vb,
437                                   (BB*)(prim_bbc + bvh->prim_indices[i]));
438         }
439
440         bvh->nodes[node_index].orig_vb= bvh->nodes[node_index].vb;
441
442         end = partition_indices(bvh->prim_indices, offset, offset + count - 1,
443                                 axis,
444                                 (cb->bmax[axis] + cb->bmin[axis]) * 0.5f,
445                                 prim_bbc);
446         check_partitioning(bvh->prim_indices, offset, offset + count - 1,
447                            axis,
448                            (cb->bmax[axis] + cb->bmin[axis]) * 0.5f,
449                            prim_bbc, end);
450
451         build_sub(bvh, bvh->nodes[node_index].children_offset, NULL,
452                   prim_bbc, offset, end - offset);
453         build_sub(bvh, bvh->nodes[node_index].children_offset + 1, NULL,
454                   prim_bbc, end, offset + count - end);
455 }
456
457 static void pbvh_build(PBVH *bvh, BB *cb, BBC *prim_bbc, int totprim)
458 {
459         int i;
460
461         if(totprim != bvh->totprim) {
462                 bvh->totprim = totprim;
463                 if(bvh->nodes) MEM_freeN(bvh->nodes);
464                 if(bvh->prim_indices) MEM_freeN(bvh->prim_indices);
465                 bvh->prim_indices = MEM_callocN(sizeof(int) * totprim,
466                                                 "bvh prim indices");
467                 for(i = 0; i < totprim; ++i)
468                         bvh->prim_indices[i] = i;
469                 bvh->totnode = 0;
470                 if(bvh->node_mem_count < 100) {
471                         bvh->node_mem_count = 100;
472                         bvh->nodes = MEM_callocN(sizeof(PBVHNode) *
473                                                  bvh->node_mem_count,
474                                                  "bvh initial nodes");
475                 }
476         }
477
478         bvh->totnode = 1;
479         build_sub(bvh, 0, cb, prim_bbc, 0, totprim);
480 }
481
482 /* Do a full rebuild with on Mesh data structure */
483 void BLI_pbvh_build_mesh(PBVH *bvh, MFace *faces, MVert *verts, int totface, int totvert)
484 {
485         BBC *prim_bbc = NULL;
486         BB cb;
487         int i, j;
488
489         bvh->faces = faces;
490         bvh->verts = verts;
491         bvh->vert_bitmap = BLI_bitmap_new(totvert);
492         bvh->totvert = totvert;
493         bvh->leaf_limit = LEAF_LIMIT;
494
495         BB_reset(&cb);
496
497         /* For each face, store the AABB and the AABB centroid */
498         prim_bbc = MEM_mallocN(sizeof(BBC) * totface, "prim_bbc");
499
500         for(i = 0; i < totface; ++i) {
501                 MFace *f = faces + i;
502                 const int sides = f->v4 ? 4 : 3;
503                 BBC *bbc = prim_bbc + i;
504
505                 BB_reset((BB*)bbc);
506
507                 for(j = 0; j < sides; ++j)
508                         BB_expand((BB*)bbc, verts[(&f->v1)[j]].co);
509
510                 BBC_update_centroid(bbc);
511
512                 BB_expand(&cb, bbc->bcentroid);
513         }
514
515         if(totface)
516                 pbvh_build(bvh, &cb, prim_bbc, totface);
517
518         MEM_freeN(prim_bbc);
519         MEM_freeN(bvh->vert_bitmap);
520 }
521
522 /* Do a full rebuild with on Grids data structure */
523 void BLI_pbvh_build_grids(PBVH *bvh, DMGridData **grids, DMGridAdjacency *gridadj,
524         int totgrid, int gridsize, void **gridfaces)
525 {
526         BBC *prim_bbc = NULL;
527         BB cb;
528         int i, j;
529
530         bvh->grids= grids;
531         bvh->gridadj= gridadj;
532         bvh->gridfaces= gridfaces;
533         bvh->totgrid= totgrid;
534         bvh->gridsize= gridsize;
535         bvh->leaf_limit = MAX2(LEAF_LIMIT/((gridsize-1)*(gridsize-1)), 1);
536
537         BB_reset(&cb);
538
539         /* For each grid, store the AABB and the AABB centroid */
540         prim_bbc = MEM_mallocN(sizeof(BBC) * totgrid, "prim_bbc");
541
542         for(i = 0; i < totgrid; ++i) {
543                 DMGridData *grid= grids[i];
544                 BBC *bbc = prim_bbc + i;
545
546                 BB_reset((BB*)bbc);
547
548                 for(j = 0; j < gridsize*gridsize; ++j)
549                         BB_expand((BB*)bbc, grid[j].co);
550
551                 BBC_update_centroid(bbc);
552
553                 BB_expand(&cb, bbc->bcentroid);
554         }
555
556         if(totgrid)
557                 pbvh_build(bvh, &cb, prim_bbc, totgrid);
558
559         MEM_freeN(prim_bbc);
560 }
561
562 PBVH *BLI_pbvh_new(void)
563 {
564         PBVH *bvh = MEM_callocN(sizeof(PBVH), "pbvh");
565
566         return bvh;
567 }
568
569 void BLI_pbvh_free(PBVH *bvh)
570 {
571         PBVHNode *node;
572         int i;
573
574         for(i = 0; i < bvh->totnode; ++i) {
575                 node= &bvh->nodes[i];
576
577                 if(node->flag & PBVH_Leaf) {
578                         if(node->draw_buffers)
579                                 GPU_free_buffers(node->draw_buffers);
580                         if(node->vert_indices)
581                                 MEM_freeN(node->vert_indices);
582                         if(node->face_vert_indices)
583                                 MEM_freeN(node->face_vert_indices);
584                 }
585         }
586
587         if (bvh->deformed) {
588                 if (bvh->verts) {
589                         /* if pbvh was deformed, new memory was allocated for verts/faces -- free it */
590
591                         MEM_freeN(bvh->verts);
592                         MEM_freeN(bvh->faces);
593                 }
594         }
595
596         MEM_freeN(bvh->nodes);
597         MEM_freeN(bvh->prim_indices);
598         MEM_freeN(bvh);
599 }
600
601 static void pbvh_iter_begin(PBVHIter *iter, PBVH *bvh, BLI_pbvh_SearchCallback scb, void *search_data)
602 {
603         iter->bvh= bvh;
604         iter->scb= scb;
605         iter->search_data= search_data;
606
607         iter->stack= iter->stackfixed;
608         iter->stackspace= STACK_FIXED_DEPTH;
609
610         iter->stack[0].node= bvh->nodes;
611         iter->stack[0].revisiting= 0;
612         iter->stacksize= 1;
613 }
614
615 static void pbvh_iter_end(PBVHIter *iter)
616 {
617         if(iter->stackspace > STACK_FIXED_DEPTH)
618                 MEM_freeN(iter->stack);
619 }
620
621 static void pbvh_stack_push(PBVHIter *iter, PBVHNode *node, int revisiting)
622 {
623         if(iter->stacksize == iter->stackspace) {
624                 PBVHStack *newstack;
625
626                 iter->stackspace *= 2;
627                 newstack= MEM_callocN(sizeof(PBVHStack)*iter->stackspace, "PBVHStack");
628                 memcpy(newstack, iter->stack, sizeof(PBVHStack)*iter->stacksize);
629
630                 if(iter->stackspace > STACK_FIXED_DEPTH)
631                         MEM_freeN(iter->stack);
632                 iter->stack= newstack;
633         }
634
635         iter->stack[iter->stacksize].node= node;
636         iter->stack[iter->stacksize].revisiting= revisiting;
637         iter->stacksize++;
638 }
639
640 static PBVHNode *pbvh_iter_next(PBVHIter *iter)
641 {
642         PBVHNode *node;
643         int revisiting;
644         void *search_data;
645
646         /* purpose here is to traverse tree, visiting child nodes before their
647            parents, this order is necessary for e.g. computing bounding boxes */
648
649         while(iter->stacksize) {
650                 /* pop node */
651                 iter->stacksize--;
652                 node= iter->stack[iter->stacksize].node;
653
654                 /* on a mesh with no faces this can happen
655                  * can remove this check if we know meshes have at least 1 face */
656                 if(node==NULL)
657                         return NULL;
658
659                 revisiting= iter->stack[iter->stacksize].revisiting;
660
661                 /* revisiting node already checked */
662                 if(revisiting)
663                         return node;
664
665                 /* check search callback */
666                 search_data= iter->search_data;
667
668                 if(iter->scb && !iter->scb(node, search_data))
669                         continue; /* don't traverse, outside of search zone */
670
671                 if(node->flag & PBVH_Leaf) {
672                         /* immediately hit leaf node */
673                         return node;
674                 }
675                 else {
676                         /* come back later when children are done */
677                         pbvh_stack_push(iter, node, 1);
678
679                         /* push two child nodes on the stack */
680                         pbvh_stack_push(iter, iter->bvh->nodes+node->children_offset+1, 0);
681                         pbvh_stack_push(iter, iter->bvh->nodes+node->children_offset, 0);
682                 }
683         }
684
685         return NULL;
686 }
687
688 void BLI_pbvh_search_gather(PBVH *bvh,
689         BLI_pbvh_SearchCallback scb, void *search_data,
690         PBVHNode ***r_array, int *r_tot)
691 {
692         PBVHIter iter;
693         PBVHNode **array= NULL, **newarray, *node;
694         int tot= 0, space= 0;
695
696         pbvh_iter_begin(&iter, bvh, scb, search_data);
697
698         while((node=pbvh_iter_next(&iter))) {
699                 if(node->flag & PBVH_Leaf) {
700                         if(tot == space) {
701                                 /* resize array if needed */
702                                 space= (tot == 0)? 32: space*2;
703                                 newarray= MEM_callocN(sizeof(PBVHNode)*space, "PBVHNodeSearch");
704
705                                 if(array) {
706                                         memcpy(newarray, array, sizeof(PBVHNode)*tot);
707                                         MEM_freeN(array);
708                                 }
709
710                                 array= newarray;
711                         }
712
713                         array[tot]= node;
714                         tot++;
715                 }
716         }
717
718         pbvh_iter_end(&iter);
719
720         if(tot == 0 && array) {
721                 MEM_freeN(array);
722                 array= NULL;
723         }
724
725         *r_array= array;
726         *r_tot= tot;
727 }
728
729 void BLI_pbvh_search_callback(PBVH *bvh,
730         BLI_pbvh_SearchCallback scb, void *search_data,
731         BLI_pbvh_HitCallback hcb, void *hit_data)
732 {
733         PBVHIter iter;
734         PBVHNode *node;
735
736         pbvh_iter_begin(&iter, bvh, scb, search_data);
737
738         while((node=pbvh_iter_next(&iter)))
739                 if(node->flag & PBVH_Leaf)
740                         hcb(node, hit_data);
741
742         pbvh_iter_end(&iter);
743 }
744
745 static int update_search_cb(PBVHNode *node, void *data_v)
746 {
747         int flag= GET_INT_FROM_POINTER(data_v);
748
749         if(node->flag & PBVH_Leaf)
750                 return (node->flag & flag);
751         
752         return 1;
753 }
754
755 static void pbvh_update_normals(PBVH *bvh, PBVHNode **nodes,
756         int totnode, float (*face_nors)[3])
757 {
758         float (*vnor)[3];
759         int n;
760
761         if(bvh->grids)
762                 return;
763
764         /* could be per node to save some memory, but also means
765            we have to store for each vertex which node it is in */
766         vnor= MEM_callocN(sizeof(float)*3*bvh->totvert, "bvh temp vnors");
767
768         /* subtle assumptions:
769            - We know that for all edited vertices, the nodes with faces
770                  adjacent to these vertices have been marked with PBVH_UpdateNormals.
771                  This is true because if the vertex is inside the brush radius, the
772                  bounding box of it's adjacent faces will be as well.
773            - However this is only true for the vertices that have actually been
774                  edited, not for all vertices in the nodes marked for update, so we
775                  can only update vertices marked with ME_VERT_PBVH_UPDATE.
776         */
777
778         #pragma omp parallel for private(n) schedule(static)
779         for(n = 0; n < totnode; n++) {
780                 PBVHNode *node= nodes[n];
781
782                 if((node->flag & PBVH_UpdateNormals)) {
783                         int i, j, totface, *faces;
784
785                         faces= node->prim_indices;
786                         totface= node->totprim;
787
788                         for(i = 0; i < totface; ++i) {
789                                 MFace *f= bvh->faces + faces[i];
790                                 float fn[3];
791                                 unsigned int *fv = &f->v1;
792                                 int sides= (f->v4)? 4: 3;
793
794                                 if(f->v4)
795                                         normal_quad_v3(fn, bvh->verts[f->v1].co, bvh->verts[f->v2].co,
796                                                                    bvh->verts[f->v3].co, bvh->verts[f->v4].co);
797                                 else
798                                         normal_tri_v3(fn, bvh->verts[f->v1].co, bvh->verts[f->v2].co,
799                                                                   bvh->verts[f->v3].co);
800
801                                 for(j = 0; j < sides; ++j) {
802                                         int v= fv[j];
803
804                                         if(bvh->verts[v].flag & ME_VERT_PBVH_UPDATE) {
805                                                 /* this seems like it could be very slow but profile
806                                                    does not show this, so just leave it for now? */
807                                                 #pragma omp atomic
808                                                 vnor[v][0] += fn[0];
809                                                 #pragma omp atomic
810                                                 vnor[v][1] += fn[1];
811                                                 #pragma omp atomic
812                                                 vnor[v][2] += fn[2];
813                                         }
814                                 }
815
816                                 if(face_nors)
817                                         copy_v3_v3(face_nors[faces[i]], fn);
818                         }
819                 }
820         }
821
822         #pragma omp parallel for private(n) schedule(static)
823         for(n = 0; n < totnode; n++) {
824                 PBVHNode *node= nodes[n];
825
826                 if(node->flag & PBVH_UpdateNormals) {
827                         int i, *verts, totvert;
828
829                         verts= node->vert_indices;
830                         totvert= node->uniq_verts;
831
832                         for(i = 0; i < totvert; ++i) {
833                                 const int v = verts[i];
834                                 MVert *mvert= &bvh->verts[v];
835
836                                 if(mvert->flag & ME_VERT_PBVH_UPDATE) {
837                                         float no[3];
838
839                                         copy_v3_v3(no, vnor[v]);
840                                         normalize_v3(no);
841                                         
842                                         mvert->no[0] = (short)(no[0]*32767.0f);
843                                         mvert->no[1] = (short)(no[1]*32767.0f);
844                                         mvert->no[2] = (short)(no[2]*32767.0f);
845                                         
846                                         mvert->flag &= ~ME_VERT_PBVH_UPDATE;
847                                 }
848                         }
849
850                         node->flag &= ~PBVH_UpdateNormals;
851                 }
852         }
853
854         MEM_freeN(vnor);
855 }
856
857 static void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes,
858         int totnode, int flag)
859 {
860         int n;
861
862         /* update BB, redraw flag */
863         #pragma omp parallel for private(n) schedule(static)
864         for(n = 0; n < totnode; n++) {
865                 PBVHNode *node= nodes[n];
866
867                 if((flag & PBVH_UpdateBB) && (node->flag & PBVH_UpdateBB))
868                         /* don't clear flag yet, leave it for flushing later */
869                         update_node_vb(bvh, node);
870
871                 if((flag & PBVH_UpdateOriginalBB) && (node->flag & PBVH_UpdateOriginalBB))
872                         node->orig_vb= node->vb;
873
874                 if((flag & PBVH_UpdateRedraw) && (node->flag & PBVH_UpdateRedraw))
875                         node->flag &= ~PBVH_UpdateRedraw;
876         }
877 }
878
879 static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode, int smooth)
880 {
881         PBVHNode *node;
882         int n;
883
884         /* can't be done in parallel with OpenGL */
885         for(n = 0; n < totnode; n++) {
886                 node= nodes[n];
887
888                 if(node->flag & PBVH_UpdateDrawBuffers) {
889                         if(bvh->grids) {
890                                 GPU_update_grid_buffers(node->draw_buffers,
891                                                    bvh->grids,
892                                                    node->prim_indices,
893                                                    node->totprim,
894                                                    bvh->gridsize,
895                                                    smooth);
896                         }
897                         else {
898                                 GPU_update_mesh_buffers(node->draw_buffers,
899                                                    bvh->verts,
900                                                    node->vert_indices,
901                                                    node->uniq_verts +
902                                                    node->face_verts);
903                         }
904
905                         node->flag &= ~PBVH_UpdateDrawBuffers;
906                 }
907         }
908 }
909
910 static int pbvh_flush_bb(PBVH *bvh, PBVHNode *node, int flag)
911 {
912         int update= 0;
913
914         /* difficult to multithread well, we just do single threaded recursive */
915         if(node->flag & PBVH_Leaf) {
916                 if(flag & PBVH_UpdateBB) {
917                         update |= (node->flag & PBVH_UpdateBB);
918                         node->flag &= ~PBVH_UpdateBB;
919                 }
920
921                 if(flag & PBVH_UpdateOriginalBB) {
922                         update |= (node->flag & PBVH_UpdateOriginalBB);
923                         node->flag &= ~PBVH_UpdateOriginalBB;
924                 }
925
926                 return update;
927         }
928         else {
929                 update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset, flag);
930                 update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset + 1, flag);
931
932                 if(update & PBVH_UpdateBB)
933                         update_node_vb(bvh, node);
934                 if(update & PBVH_UpdateOriginalBB)
935                         node->orig_vb= node->vb;
936         }
937
938         return update;
939 }
940
941 void BLI_pbvh_update(PBVH *bvh, int flag, float (*face_nors)[3])
942 {
943         PBVHNode **nodes;
944         int totnode;
945
946         BLI_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(flag),
947                 &nodes, &totnode);
948
949         if(flag & PBVH_UpdateNormals)
950                 pbvh_update_normals(bvh, nodes, totnode, face_nors);
951
952         if(flag & (PBVH_UpdateBB|PBVH_UpdateOriginalBB|PBVH_UpdateRedraw))
953                 pbvh_update_BB_redraw(bvh, nodes, totnode, flag);
954
955         if(flag & (PBVH_UpdateBB|PBVH_UpdateOriginalBB))
956                 pbvh_flush_bb(bvh, bvh->nodes, flag);
957
958         if(nodes) MEM_freeN(nodes);
959 }
960
961 void BLI_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3])
962 {
963         PBVHIter iter;
964         PBVHNode *node;
965         BB bb;
966
967         BB_reset(&bb);
968
969         pbvh_iter_begin(&iter, bvh, NULL, NULL);
970
971         while((node=pbvh_iter_next(&iter)))
972                 if(node->flag & PBVH_UpdateRedraw)
973                         BB_expand_with_bb(&bb, &node->vb);
974
975         pbvh_iter_end(&iter);
976
977         copy_v3_v3(bb_min, bb.bmin);
978         copy_v3_v3(bb_max, bb.bmax);
979 }
980
981 void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *totface)
982 {
983         PBVHIter iter;
984         PBVHNode *node;
985         GHashIterator *hiter;
986         GHash *map;
987         void *face, **faces;
988         int i, tot;
989
990         map = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "pbvh_get_grid_updates gh");
991
992         pbvh_iter_begin(&iter, bvh, NULL, NULL);
993
994         while((node=pbvh_iter_next(&iter))) {
995                 if(node->flag & PBVH_UpdateNormals) {
996                         for(i = 0; i < node->totprim; ++i) {
997                                 face= bvh->gridfaces[node->prim_indices[i]];
998                                 if(!BLI_ghash_lookup(map, face))
999                                         BLI_ghash_insert(map, face, face);
1000                         }
1001
1002                         if(clear)
1003                                 node->flag &= ~PBVH_UpdateNormals;
1004                 }
1005         }
1006
1007         pbvh_iter_end(&iter);
1008         
1009         tot= BLI_ghash_size(map);
1010         if(tot == 0) {
1011                 *totface= 0;
1012                 *gridfaces= NULL;
1013                 BLI_ghash_free(map, NULL, NULL);
1014                 return;
1015         }
1016
1017         faces= MEM_callocN(sizeof(void*)*tot, "PBVH Grid Faces");
1018
1019         for(hiter = BLI_ghashIterator_new(map), i = 0;
1020                 !BLI_ghashIterator_isDone(hiter);
1021                 BLI_ghashIterator_step(hiter), ++i)
1022                 faces[i]= BLI_ghashIterator_getKey(hiter);
1023
1024         BLI_ghashIterator_free(hiter);
1025
1026         BLI_ghash_free(map, NULL, NULL);
1027
1028         *totface= tot;
1029         *gridfaces= faces;
1030 }
1031
1032 /***************************** Node Access ***********************************/
1033
1034 void BLI_pbvh_node_mark_update(PBVHNode *node)
1035 {
1036         node->flag |= PBVH_UpdateNormals|PBVH_UpdateBB|PBVH_UpdateOriginalBB|PBVH_UpdateDrawBuffers|PBVH_UpdateRedraw;
1037 }
1038
1039 void BLI_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node, int **vert_indices, MVert **verts)
1040 {
1041         if(vert_indices) *vert_indices= node->vert_indices;
1042         if(verts) *verts= bvh->verts;
1043 }
1044
1045 void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node, int *uniquevert, int *totvert)
1046 {
1047         if(bvh->grids) {
1048                 if(totvert) *totvert= node->totprim*bvh->gridsize*bvh->gridsize;
1049                 if(uniquevert) *uniquevert= *totvert;
1050         }
1051         else {
1052                 if(totvert) *totvert= node->uniq_verts + node->face_verts;
1053                 if(uniquevert) *uniquevert= node->uniq_verts;
1054         }
1055 }
1056
1057 void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node, int **grid_indices, int *totgrid, int *maxgrid, int *gridsize, DMGridData ***griddata, DMGridAdjacency **gridadj)
1058 {
1059         if(bvh->grids) {
1060                 if(grid_indices) *grid_indices= node->prim_indices;
1061                 if(totgrid) *totgrid= node->totprim;
1062                 if(maxgrid) *maxgrid= bvh->totgrid;
1063                 if(gridsize) *gridsize= bvh->gridsize;
1064                 if(griddata) *griddata= bvh->grids;
1065                 if(gridadj) *gridadj= bvh->gridadj;
1066         }
1067         else {
1068                 if(grid_indices) *grid_indices= NULL;
1069                 if(totgrid) *totgrid= 0;
1070                 if(maxgrid) *maxgrid= 0;
1071                 if(gridsize) *gridsize= 0;
1072                 if(griddata) *griddata= NULL;
1073                 if(gridadj) *gridadj= NULL;
1074         }
1075 }
1076
1077 void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
1078 {
1079         copy_v3_v3(bb_min, node->vb.bmin);
1080         copy_v3_v3(bb_max, node->vb.bmax);
1081 }
1082
1083 void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
1084 {
1085         copy_v3_v3(bb_min, node->orig_vb.bmin);
1086         copy_v3_v3(bb_max, node->orig_vb.bmax);
1087 }
1088
1089 /********************************* Raycast ***********************************/
1090
1091 typedef struct {
1092         /* Ray */
1093         float start[3];
1094         int sign[3];
1095         float inv_dir[3];
1096         int original;
1097 } RaycastData;
1098
1099 /* Adapted from here: http://www.gamedev.net/community/forums/topic.asp?topic_id=459973 */
1100 static int ray_aabb_intersect(PBVHNode *node, void *data_v)
1101 {
1102         RaycastData *ray = data_v;
1103         float bb_min[3], bb_max[3], bbox[2][3];
1104         float tmin, tmax, tymin, tymax, tzmin, tzmax;
1105
1106         if(ray->original)
1107                 BLI_pbvh_node_get_original_BB(node, bb_min, bb_max);
1108         else
1109                 BLI_pbvh_node_get_BB(node, bb_min, bb_max);
1110         
1111         copy_v3_v3(bbox[0], bb_min);
1112         copy_v3_v3(bbox[1], bb_max);
1113
1114         tmin = (bbox[ray->sign[0]][0] - ray->start[0]) * ray->inv_dir[0];
1115         tmax = (bbox[1-ray->sign[0]][0] - ray->start[0]) * ray->inv_dir[0];
1116
1117         tymin = (bbox[ray->sign[1]][1] - ray->start[1]) * ray->inv_dir[1];
1118         tymax = (bbox[1-ray->sign[1]][1] - ray->start[1]) * ray->inv_dir[1];
1119
1120         if((tmin > tymax) || (tymin > tmax))
1121                 return 0;
1122         if(tymin > tmin)
1123                 tmin = tymin;
1124         if(tymax < tmax)
1125                 tmax = tymax;
1126
1127         tzmin = (bbox[ray->sign[2]][2] - ray->start[2]) * ray->inv_dir[2];
1128         tzmax = (bbox[1-ray->sign[2]][2] - ray->start[2]) * ray->inv_dir[2];
1129
1130         if((tmin > tzmax) || (tzmin > tmax))
1131                 return 0;
1132         
1133         return 1;
1134
1135         /* XXX: Not sure about this? 
1136            if(tzmin > tmin)
1137            tmin = tzmin;
1138            if(tzmax < tmax)
1139            tmax = tzmax;
1140            return ((tmin < t1) && (tmax > t0));
1141         */
1142
1143 }
1144
1145 void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitCallback cb, void *data,
1146                           float ray_start[3], float ray_normal[3], int original)
1147 {
1148         RaycastData rcd;
1149
1150         copy_v3_v3(rcd.start, ray_start);
1151         rcd.inv_dir[0] = 1.0f / ray_normal[0];
1152         rcd.inv_dir[1] = 1.0f / ray_normal[1];
1153         rcd.inv_dir[2] = 1.0f / ray_normal[2];
1154         rcd.sign[0] = rcd.inv_dir[0] < 0;
1155         rcd.sign[1] = rcd.inv_dir[1] < 0;
1156         rcd.sign[2] = rcd.inv_dir[2] < 0;
1157         rcd.original = original;
1158
1159         BLI_pbvh_search_callback(bvh, ray_aabb_intersect, &rcd, cb, data);
1160 }
1161
1162 /* XXX: Code largely copied from bvhutils.c, could be unified */
1163 /* Returns 1 if a better intersection has been found */
1164 static int ray_face_intersection(float ray_start[3], float ray_normal[3],
1165                                  float *t0, float *t1, float *t2, float *t3,
1166                                  float *fdist)
1167 {
1168         int hit = 0;
1169
1170         do
1171         {       
1172                 float dist = FLT_MAX;
1173                         
1174                 if(!isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t1, t2,
1175                                          &dist, NULL, 0.1f))
1176                         dist = FLT_MAX;
1177
1178                 if(dist >= 0 && dist < *fdist) {
1179                         hit = 1;
1180                         *fdist = dist;
1181                 }
1182
1183                 t1 = t2;
1184                 t2 = t3;
1185                 t3 = NULL;
1186
1187         } while(t2);
1188
1189         return hit;
1190 }
1191
1192 int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
1193         float ray_start[3], float ray_normal[3], float *dist)
1194 {
1195         int hit= 0;
1196
1197         if(bvh->faces) {
1198                 MVert *vert = bvh->verts;
1199                 int *faces= node->prim_indices;
1200                 int *face_verts= node->face_vert_indices;
1201                 int totface= node->totprim;
1202                 int i;
1203
1204                 for(i = 0; i < totface; ++i) {
1205                         MFace *f = bvh->faces + faces[i];
1206
1207                         if(origco) {
1208                                 /* intersect with backuped original coordinates */
1209                                 hit |= ray_face_intersection(ray_start, ray_normal,
1210                                                          origco[face_verts[i*4+0]],
1211                                                          origco[face_verts[i*4+1]],
1212                                                          origco[face_verts[i*4+2]],
1213                                                          f->v4? origco[face_verts[i*4+3]]: NULL,
1214                                                          dist);
1215                         }
1216                         else {
1217                                 /* intersect with current coordinates */
1218                                 hit |= ray_face_intersection(ray_start, ray_normal,
1219                                                          vert[f->v1].co,
1220                                                          vert[f->v2].co,
1221                                                          vert[f->v3].co,
1222                                                          f->v4 ? vert[f->v4].co : NULL,
1223                                                          dist);
1224                         }
1225                 }
1226         }
1227         else {
1228                 int totgrid= node->totprim;
1229                 int gridsize= bvh->gridsize;
1230                 int i, x, y;
1231
1232                 for(i = 0; i < totgrid; ++i) {
1233                         DMGridData *grid= bvh->grids[node->prim_indices[i]];
1234                         if (!grid)
1235                                 continue;
1236
1237                         for(y = 0; y < gridsize-1; ++y) {
1238                                 for(x = 0; x < gridsize-1; ++x) {
1239                                         if(origco) {
1240                                                 hit |= ray_face_intersection(ray_start, ray_normal,
1241                                                                          origco[y*gridsize + x],
1242                                                                          origco[y*gridsize + x+1],
1243                                                                          origco[(y+1)*gridsize + x+1],
1244                                                                          origco[(y+1)*gridsize + x],
1245                                                                          dist);
1246                                         }
1247                                         else {
1248                                                 hit |= ray_face_intersection(ray_start, ray_normal,
1249                                                                          grid[y*gridsize + x].co,
1250                                                                          grid[y*gridsize + x+1].co,
1251                                                                          grid[(y+1)*gridsize + x+1].co,
1252                                                                          grid[(y+1)*gridsize + x].co,
1253                                                                          dist);
1254                                         }
1255                                 }
1256                         }
1257
1258                         if(origco)
1259                                 origco += gridsize*gridsize;
1260                 }
1261         }
1262
1263         return hit;
1264 }
1265
1266 //#include <GL/glew.h>
1267
1268 void BLI_pbvh_node_draw(PBVHNode *node, void *data)
1269 {
1270 #if 0
1271         /* XXX: Just some quick code to show leaf nodes in different colors */
1272         float col[3]; int i;
1273
1274         if(0) { //is_partial) {
1275                 col[0] = (rand() / (float)RAND_MAX); col[1] = col[2] = 0.6;
1276         }
1277         else {
1278                 srand((long long)node);
1279                 for(i = 0; i < 3; ++i)
1280                         col[i] = (rand() / (float)RAND_MAX) * 0.3 + 0.7;
1281         }
1282         glMaterialfv(GL_FRONT_AND_BACK, GL_DIFFUSE, col);
1283
1284         glColor3f(1, 0, 0);
1285 #endif
1286         GPU_draw_buffers(node->draw_buffers);
1287 }
1288
1289 /* Adapted from:
1290    http://www.gamedev.net/community/forums/topic.asp?topic_id=512123
1291    Returns true if the AABB is at least partially within the frustum
1292    (ok, not a real frustum), false otherwise.
1293 */
1294 int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data)
1295 {
1296         float (*planes)[4] = data;
1297         int i, axis;
1298         float vmin[3], vmax[3], bb_min[3], bb_max[3];
1299
1300         BLI_pbvh_node_get_BB(node, bb_min, bb_max);
1301
1302         for(i = 0; i < 4; ++i) { 
1303                 for(axis = 0; axis < 3; ++axis) {
1304                         if(planes[i][axis] > 0) { 
1305                                 vmin[axis] = bb_min[axis];
1306                                 vmax[axis] = bb_max[axis];
1307                         }
1308                         else {
1309                                 vmin[axis] = bb_max[axis];
1310                                 vmax[axis] = bb_min[axis];
1311                         }
1312                 }
1313                 
1314                 if(dot_v3v3(planes[i], vmin) + planes[i][3] > 0)
1315                         return 0;
1316         } 
1317
1318         return 1;
1319 }
1320
1321 void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3], int smooth)
1322 {
1323         PBVHNode **nodes;
1324         int totnode;
1325
1326         BLI_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(PBVH_UpdateNormals|PBVH_UpdateDrawBuffers),
1327                 &nodes, &totnode);
1328
1329         pbvh_update_normals(bvh, nodes, totnode, face_nors);
1330         pbvh_update_draw_buffers(bvh, nodes, totnode, smooth);
1331
1332         if(nodes) MEM_freeN(nodes);
1333
1334         if(planes) {
1335                 BLI_pbvh_search_callback(bvh, BLI_pbvh_node_planes_contain_AABB,
1336                                 planes, BLI_pbvh_node_draw, NULL);
1337         }
1338         else {
1339                 BLI_pbvh_search_callback(bvh, NULL, NULL, BLI_pbvh_node_draw, NULL);
1340         }
1341 }
1342
1343 void BLI_pbvh_grids_update(PBVH *bvh, DMGridData **grids, DMGridAdjacency *gridadj, void **gridfaces)
1344 {
1345         bvh->grids= grids;
1346         bvh->gridadj= gridadj;
1347         bvh->gridfaces= gridfaces;
1348 }
1349
1350 float (*BLI_pbvh_get_vertCos(PBVH *pbvh))[3]
1351 {
1352         int a;
1353         float (*vertCos)[3]= NULL;
1354
1355         if (pbvh->verts) {
1356                 float *co;
1357                 MVert *mvert= pbvh->verts;
1358
1359                 vertCos= MEM_callocN(3*pbvh->totvert*sizeof(float), "BLI_pbvh_get_vertCoords");
1360                 co= (float*)vertCos;
1361
1362                 for (a= 0; a<pbvh->totvert; a++, mvert++, co+= 3) {
1363                         copy_v3_v3(co, mvert->co);
1364                 }
1365         }
1366
1367         return vertCos;
1368 }
1369
1370 void BLI_pbvh_apply_vertCos(PBVH *pbvh, float (*vertCos)[3])
1371 {
1372         int a;
1373
1374         if (!pbvh->deformed) {
1375                 if (pbvh->verts) {
1376                         /* if pbvh is not already deformed, verts/faces points to the */
1377                         /* original data and applying new coords to this arrays would lead to */
1378                         /* unneeded deformation -- duplicate verts/faces to avoid this */
1379
1380                         pbvh->verts= MEM_dupallocN(pbvh->verts);
1381                         pbvh->faces= MEM_dupallocN(pbvh->faces);
1382
1383                         pbvh->deformed= 1;
1384                 }
1385         }
1386
1387         if (pbvh->verts) {
1388                 /* copy new verts coords */
1389                 for (a= 0; a < pbvh->totvert; ++a) {
1390                         copy_v3_v3(pbvh->verts[a].co, vertCos[a]);
1391                 }
1392
1393                 /* coordinates are new -- normals should also be updated */
1394                 mesh_calc_normals(pbvh->verts, pbvh->totvert, pbvh->faces, pbvh->totprim, NULL);
1395         }
1396 }
1397
1398 int BLI_pbvh_isDeformed(PBVH *pbvh)
1399 {
1400         return pbvh->deformed;
1401 }