Blender  V3.3
pbvh.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
7 #include "MEM_guardedalloc.h"
8 
9 #include "BLI_utildefines.h"
10 
11 #include "BLI_bitmap.h"
12 #include "BLI_ghash.h"
13 #include "BLI_math.h"
14 #include "BLI_rand.h"
15 #include "BLI_task.h"
16 
17 #include "DNA_mesh_types.h"
18 #include "DNA_meshdata_types.h"
19 
20 #include "BKE_attribute.h"
21 #include "BKE_ccg.h"
22 #include "BKE_mesh.h"
23 #include "BKE_mesh_mapping.h"
24 #include "BKE_paint.h"
25 #include "BKE_pbvh.h"
26 #include "BKE_subdiv_ccg.h"
27 
28 #include "PIL_time.h"
29 
30 #include "GPU_buffers.h"
31 
32 #include "bmesh.h"
33 
34 #include "atomic_ops.h"
35 
36 #include "pbvh_intern.h"
37 
38 #include <limits.h>
39 
40 #define LEAF_LIMIT 10000
41 
42 //#define PERFCNTRS
43 
44 #define STACK_FIXED_DEPTH 100
45 
46 typedef struct PBVHStack {
48  bool revisiting;
50 
51 typedef struct PBVHIter {
54  void *search_data;
55 
57  int stacksize;
58 
62 
63 void BB_reset(BB *bb)
64 {
65  bb->bmin[0] = bb->bmin[1] = bb->bmin[2] = FLT_MAX;
66  bb->bmax[0] = bb->bmax[1] = bb->bmax[2] = -FLT_MAX;
67 }
68 
69 void BB_expand(BB *bb, const float co[3])
70 {
71  for (int i = 0; i < 3; i++) {
72  bb->bmin[i] = min_ff(bb->bmin[i], co[i]);
73  bb->bmax[i] = max_ff(bb->bmax[i], co[i]);
74  }
75 }
76 
77 void BB_expand_with_bb(BB *bb, BB *bb2)
78 {
79  for (int i = 0; i < 3; i++) {
80  bb->bmin[i] = min_ff(bb->bmin[i], bb2->bmin[i]);
81  bb->bmax[i] = max_ff(bb->bmax[i], bb2->bmax[i]);
82  }
83 }
84 
85 int BB_widest_axis(const BB *bb)
86 {
87  float dim[3];
88 
89  for (int i = 0; i < 3; i++) {
90  dim[i] = bb->bmax[i] - bb->bmin[i];
91  }
92 
93  if (dim[0] > dim[1]) {
94  if (dim[0] > dim[2]) {
95  return 0;
96  }
97 
98  return 2;
99  }
100 
101  if (dim[1] > dim[2]) {
102  return 1;
103  }
104 
105  return 2;
106 }
107 
109 {
110  for (int i = 0; i < 3; i++) {
111  bbc->bcentroid[i] = (bbc->bmin[i] + bbc->bmax[i]) * 0.5f;
112  }
113 }
114 
115 /* Not recursive */
116 static void update_node_vb(PBVH *pbvh, PBVHNode *node)
117 {
118  BB vb;
119 
120  BB_reset(&vb);
121 
122  if (node->flag & PBVH_Leaf) {
123  PBVHVertexIter vd;
124 
126  BB_expand(&vb, vd.co);
127  }
129  }
130  else {
131  BB_expand_with_bb(&vb, &pbvh->nodes[node->children_offset].vb);
132  BB_expand_with_bb(&vb, &pbvh->nodes[node->children_offset + 1].vb);
133  }
134 
135  node->vb = vb;
136 }
137 
138 // void BKE_pbvh_node_BB_reset(PBVHNode *node)
139 //{
140 // BB_reset(&node->vb);
141 //}
142 //
143 // void BKE_pbvh_node_BB_expand(PBVHNode *node, float co[3])
144 //{
145 // BB_expand(&node->vb, co);
146 //}
147 
148 static bool face_materials_match(const MPoly *f1, const MPoly *f2)
149 {
150  return ((f1->flag & ME_SMOOTH) == (f2->flag & ME_SMOOTH) && (f1->mat_nr == f2->mat_nr));
151 }
152 
153 static bool grid_materials_match(const DMFlagMat *f1, const DMFlagMat *f2)
154 {
155  return ((f1->flag & ME_SMOOTH) == (f2->flag & ME_SMOOTH) && (f1->mat_nr == f2->mat_nr));
156 }
157 
158 /* Adapted from BLI_kdopbvh.c */
159 /* Returns the index of the first element on the right of the partition */
160 static int partition_indices(int *prim_indices, int lo, int hi, int axis, float mid, BBC *prim_bbc)
161 {
162  int i = lo, j = hi;
163  for (;;) {
164  for (; prim_bbc[prim_indices[i]].bcentroid[axis] < mid; i++) {
165  /* pass */
166  }
167  for (; mid < prim_bbc[prim_indices[j]].bcentroid[axis]; j--) {
168  /* pass */
169  }
170 
171  if (!(i < j)) {
172  return i;
173  }
174 
175  SWAP(int, prim_indices[i], prim_indices[j]);
176  i++;
177  }
178 }
179 
180 /* Returns the index of the first element on the right of the partition */
181 static int partition_indices_material(PBVH *pbvh, int lo, int hi)
182 {
183  const MPoly *mpoly = pbvh->mpoly;
184  const MLoopTri *looptri = pbvh->looptri;
185  const DMFlagMat *flagmats = pbvh->grid_flag_mats;
186  const int *indices = pbvh->prim_indices;
187  const void *first;
188  int i = lo, j = hi;
189 
190  if (pbvh->looptri) {
191  first = &mpoly[looptri[pbvh->prim_indices[lo]].poly];
192  }
193  else {
194  first = &flagmats[pbvh->prim_indices[lo]];
195  }
196 
197  for (;;) {
198  if (pbvh->looptri) {
199  for (; face_materials_match(first, &mpoly[looptri[indices[i]].poly]); i++) {
200  /* pass */
201  }
202  for (; !face_materials_match(first, &mpoly[looptri[indices[j]].poly]); j--) {
203  /* pass */
204  }
205  }
206  else {
207  for (; grid_materials_match(first, &flagmats[indices[i]]); i++) {
208  /* pass */
209  }
210  for (; !grid_materials_match(first, &flagmats[indices[j]]); j--) {
211  /* pass */
212  }
213  }
214 
215  if (!(i < j)) {
216  return i;
217  }
218 
219  SWAP(int, pbvh->prim_indices[i], pbvh->prim_indices[j]);
220  i++;
221  }
222 }
223 
224 void pbvh_grow_nodes(PBVH *pbvh, int totnode)
225 {
226  if (UNLIKELY(totnode > pbvh->node_mem_count)) {
227  pbvh->node_mem_count = pbvh->node_mem_count + (pbvh->node_mem_count / 3);
228  if (pbvh->node_mem_count < totnode) {
229  pbvh->node_mem_count = totnode;
230  }
231  pbvh->nodes = MEM_recallocN(pbvh->nodes, sizeof(PBVHNode) * pbvh->node_mem_count);
232  }
233 
234  pbvh->totnode = totnode;
235 }
236 
237 /* Add a vertex to the map, with a positive value for unique vertices and
238  * a negative value for additional vertices */
239 static int map_insert_vert(
240  PBVH *pbvh, GHash *map, unsigned int *face_verts, unsigned int *uniq_verts, int vertex)
241 {
242  void *key, **value_p;
243 
244  key = POINTER_FROM_INT(vertex);
245  if (!BLI_ghash_ensure_p(map, key, &value_p)) {
246  int value_i;
247  if (!pbvh->vert_bitmap[vertex]) {
248  pbvh->vert_bitmap[vertex] = true;
249  value_i = *uniq_verts;
250  (*uniq_verts)++;
251  }
252  else {
253  value_i = ~(*face_verts);
254  (*face_verts)++;
255  }
256  *value_p = POINTER_FROM_INT(value_i);
257  return value_i;
258  }
259 
260  return POINTER_AS_INT(*value_p);
261 }
262 
263 /* Find vertices used by the faces in this node and update the draw buffers */
265 {
266  bool has_visible = false;
267 
268  node->uniq_verts = node->face_verts = 0;
269  const int totface = node->totprim;
270 
271  /* reserve size is rough guess */
272  GHash *map = BLI_ghash_int_new_ex("build_mesh_leaf_node gh", 2 * totface);
273 
274  int(*face_vert_indices)[3] = MEM_mallocN(sizeof(int[3]) * totface, "bvh node face vert indices");
275 
276  node->face_vert_indices = (const int(*)[3])face_vert_indices;
277 
278  if (pbvh->respect_hide == false) {
279  has_visible = true;
280  }
281 
282  for (int i = 0; i < totface; i++) {
283  const MLoopTri *lt = &pbvh->looptri[node->prim_indices[i]];
284  for (int j = 0; j < 3; j++) {
285  face_vert_indices[i][j] = map_insert_vert(
286  pbvh, map, &node->face_verts, &node->uniq_verts, pbvh->mloop[lt->tri[j]].v);
287  }
288 
289  if (has_visible == false) {
290  if (!paint_is_face_hidden(lt, pbvh->verts, pbvh->mloop)) {
291  has_visible = true;
292  }
293  }
294  }
295 
296  int *vert_indices = MEM_callocN(sizeof(int) * (node->uniq_verts + node->face_verts),
297  "bvh node vert indices");
298  node->vert_indices = vert_indices;
299 
300  /* Build the vertex list, unique verts first */
301  GHashIterator gh_iter;
302  GHASH_ITER (gh_iter, map) {
303  void *value = BLI_ghashIterator_getValue(&gh_iter);
304  int ndx = POINTER_AS_INT(value);
305 
306  if (ndx < 0) {
307  ndx = -ndx + node->uniq_verts - 1;
308  }
309 
310  vert_indices[ndx] = POINTER_AS_INT(BLI_ghashIterator_getKey(&gh_iter));
311  }
312 
313  for (int i = 0; i < totface; i++) {
314  const int sides = 3;
315 
316  for (int j = 0; j < sides; j++) {
317  if (face_vert_indices[i][j] < 0) {
318  face_vert_indices[i][j] = -face_vert_indices[i][j] + node->uniq_verts - 1;
319  }
320  }
321  }
322 
324 
325  BKE_pbvh_node_fully_hidden_set(node, !has_visible);
326 
328 }
329 
330 static void update_vb(PBVH *pbvh, PBVHNode *node, BBC *prim_bbc, int offset, int count)
331 {
332  BB_reset(&node->vb);
333  for (int i = offset + count - 1; i >= offset; i--) {
334  BB_expand_with_bb(&node->vb, (BB *)(&prim_bbc[pbvh->prim_indices[i]]));
335  }
336  node->orig_vb = node->vb;
337 }
338 
340  const int *grid_indices,
341  int totgrid,
342  int gridsize)
343 {
344  const int gridarea = (gridsize - 1) * (gridsize - 1);
345  int totquad = 0;
346 
347  /* grid hidden layer is present, so have to check each grid for
348  * visibility */
349 
350  for (int i = 0; i < totgrid; i++) {
351  const BLI_bitmap *gh = grid_hidden[grid_indices[i]];
352 
353  if (gh) {
354  /* grid hidden are present, have to check each element */
355  for (int y = 0; y < gridsize - 1; y++) {
356  for (int x = 0; x < gridsize - 1; x++) {
357  if (!paint_is_grid_face_hidden(gh, gridsize, x, y)) {
358  totquad++;
359  }
360  }
361  }
362  }
363  else {
364  totquad += gridarea;
365  }
366  }
367 
368  return totquad;
369 }
370 
372 {
373  const int gridsize = pbvh->gridkey.grid_size;
374  for (int i = 0; i < pbvh->totgrid; i++) {
375  BLI_bitmap *gh = pbvh->grid_hidden[i];
376  const int face_index = BKE_subdiv_ccg_grid_to_face_index(pbvh->subdiv_ccg, i);
377  if (!gh && pbvh->face_sets[face_index] < 0) {
378  gh = pbvh->grid_hidden[i] = BLI_BITMAP_NEW(pbvh->gridkey.grid_area,
379  "partialvis_update_grids");
380  }
381  if (gh) {
382  for (int y = 0; y < gridsize; y++) {
383  for (int x = 0; x < gridsize; x++) {
384  BLI_BITMAP_SET(gh, y * gridsize + x, pbvh->face_sets[face_index] < 0);
385  }
386  }
387  }
388  }
389 }
390 
392 {
393  int totquads = BKE_pbvh_count_grid_quads(
394  pbvh->grid_hidden, node->prim_indices, node->totprim, pbvh->gridkey.grid_size);
395  BKE_pbvh_node_fully_hidden_set(node, (totquads == 0));
397 }
398 
399 static void build_leaf(PBVH *pbvh, int node_index, BBC *prim_bbc, int offset, int count)
400 {
401  pbvh->nodes[node_index].flag |= PBVH_Leaf;
402 
403  pbvh->nodes[node_index].prim_indices = pbvh->prim_indices + offset;
404  pbvh->nodes[node_index].totprim = count;
405 
406  /* Still need vb for searches */
407  update_vb(pbvh, &pbvh->nodes[node_index], prim_bbc, offset, count);
408 
409  if (pbvh->looptri) {
410  build_mesh_leaf_node(pbvh, pbvh->nodes + node_index);
411  }
412  else {
413  build_grid_leaf_node(pbvh, pbvh->nodes + node_index);
414  }
415 }
416 
417 /* Return zero if all primitives in the node can be drawn with the
418  * same material (including flat/smooth shading), non-zero otherwise */
419 static bool leaf_needs_material_split(PBVH *pbvh, int offset, int count)
420 {
421  if (count <= 1) {
422  return false;
423  }
424 
425  if (pbvh->looptri) {
426  const MLoopTri *first = &pbvh->looptri[pbvh->prim_indices[offset]];
427  const MPoly *mp = &pbvh->mpoly[first->poly];
428 
429  for (int i = offset + count - 1; i > offset; i--) {
430  int prim = pbvh->prim_indices[i];
431  const MPoly *mp_other = &pbvh->mpoly[pbvh->looptri[prim].poly];
432  if (!face_materials_match(mp, mp_other)) {
433  return true;
434  }
435  }
436  }
437  else {
438  const DMFlagMat *first = &pbvh->grid_flag_mats[pbvh->prim_indices[offset]];
439 
440  for (int i = offset + count - 1; i > offset; i--) {
441  int prim = pbvh->prim_indices[i];
442  if (!grid_materials_match(first, &pbvh->grid_flag_mats[prim])) {
443  return true;
444  }
445  }
446  }
447 
448  return false;
449 }
450 
451 /* Recursively build a node in the tree
452  *
453  * vb is the voxel box around all of the primitives contained in
454  * this node.
455  *
456  * cb is the bounding box around all the centroids of the primitives
457  * contained in this node
458  *
459  * offset and start indicate a range in the array of primitive indices
460  */
461 
462 static void build_sub(PBVH *pbvh, int node_index, BB *cb, BBC *prim_bbc, int offset, int count)
463 {
464  int end;
465  BB cb_backing;
466 
467  /* Decide whether this is a leaf or not */
468  const bool below_leaf_limit = count <= pbvh->leaf_limit;
469  if (below_leaf_limit) {
470  if (!leaf_needs_material_split(pbvh, offset, count)) {
471  build_leaf(pbvh, node_index, prim_bbc, offset, count);
472  return;
473  }
474  }
475 
476  /* Add two child nodes */
477  pbvh->nodes[node_index].children_offset = pbvh->totnode;
478  pbvh_grow_nodes(pbvh, pbvh->totnode + 2);
479 
480  /* Update parent node bounding box */
481  update_vb(pbvh, &pbvh->nodes[node_index], prim_bbc, offset, count);
482 
483  if (!below_leaf_limit) {
484  /* Find axis with widest range of primitive centroids */
485  if (!cb) {
486  cb = &cb_backing;
487  BB_reset(cb);
488  for (int i = offset + count - 1; i >= offset; i--) {
489  BB_expand(cb, prim_bbc[pbvh->prim_indices[i]].bcentroid);
490  }
491  }
492  const int axis = BB_widest_axis(cb);
493 
494  /* Partition primitives along that axis */
495  end = partition_indices(pbvh->prim_indices,
496  offset,
497  offset + count - 1,
498  axis,
499  (cb->bmax[axis] + cb->bmin[axis]) * 0.5f,
500  prim_bbc);
501  }
502  else {
503  /* Partition primitives by material */
504  end = partition_indices_material(pbvh, offset, offset + count - 1);
505  }
506 
507  /* Build children */
508  build_sub(pbvh, pbvh->nodes[node_index].children_offset, NULL, prim_bbc, offset, end - offset);
509  build_sub(pbvh,
510  pbvh->nodes[node_index].children_offset + 1,
511  NULL,
512  prim_bbc,
513  end,
514  offset + count - end);
515 }
516 
517 static void pbvh_build(PBVH *pbvh, BB *cb, BBC *prim_bbc, int totprim)
518 {
519  if (totprim != pbvh->totprim) {
520  pbvh->totprim = totprim;
521  if (pbvh->nodes) {
522  MEM_freeN(pbvh->nodes);
523  }
524  if (pbvh->prim_indices) {
525  MEM_freeN(pbvh->prim_indices);
526  }
527  pbvh->prim_indices = MEM_mallocN(sizeof(int) * totprim, "bvh prim indices");
528  for (int i = 0; i < totprim; i++) {
529  pbvh->prim_indices[i] = i;
530  }
531  pbvh->totnode = 0;
532  if (pbvh->node_mem_count < 100) {
533  pbvh->node_mem_count = 100;
534  pbvh->nodes = MEM_callocN(sizeof(PBVHNode) * pbvh->node_mem_count, "bvh initial nodes");
535  }
536  }
537 
538  pbvh->totnode = 1;
539  build_sub(pbvh, 0, cb, prim_bbc, 0, totprim);
540 }
541 
543  Mesh *mesh,
544  const MPoly *mpoly,
545  const MLoop *mloop,
546  MVert *verts,
547  int totvert,
548  struct CustomData *vdata,
549  struct CustomData *ldata,
550  struct CustomData *pdata,
551  const MLoopTri *looptri,
552  int looptri_num)
553 {
554  BBC *prim_bbc = NULL;
555  BB cb;
556 
557  pbvh->mesh = mesh;
558  pbvh->type = PBVH_FACES;
559  pbvh->mpoly = mpoly;
560  pbvh->mloop = mloop;
561  pbvh->looptri = looptri;
562  pbvh->verts = verts;
565  pbvh->vert_bitmap = MEM_calloc_arrayN(totvert, sizeof(bool), "bvh->vert_bitmap");
566  pbvh->totvert = totvert;
567  pbvh->leaf_limit = LEAF_LIMIT;
568  pbvh->vdata = vdata;
569  pbvh->ldata = ldata;
570  pbvh->pdata = pdata;
571 
574 
575  BB_reset(&cb);
576 
577  /* For each face, store the AABB and the AABB centroid */
578  prim_bbc = MEM_mallocN(sizeof(BBC) * looptri_num, "prim_bbc");
579 
580  for (int i = 0; i < looptri_num; i++) {
581  const MLoopTri *lt = &looptri[i];
582  const int sides = 3;
583  BBC *bbc = prim_bbc + i;
584 
585  BB_reset((BB *)bbc);
586 
587  for (int j = 0; j < sides; j++) {
588  BB_expand((BB *)bbc, verts[pbvh->mloop[lt->tri[j]].v].co);
589  }
590 
591  BBC_update_centroid(bbc);
592 
593  BB_expand(&cb, bbc->bcentroid);
594  }
595 
596  if (looptri_num) {
597  pbvh_build(pbvh, &cb, prim_bbc, looptri_num);
598  }
599 
600  MEM_freeN(prim_bbc);
601 
602  /* Clear the bitmap so it can be used as an update tag later on. */
603  memset(pbvh->vert_bitmap, 0, sizeof(bool) * totvert);
604 
606 }
607 
609  CCGElem **grids,
610  int totgrid,
611  CCGKey *key,
612  void **gridfaces,
613  DMFlagMat *flagmats,
614  BLI_bitmap **grid_hidden)
615 {
616  const int gridsize = key->grid_size;
617 
618  pbvh->type = PBVH_GRIDS;
619  pbvh->grids = grids;
620  pbvh->gridfaces = gridfaces;
621  pbvh->grid_flag_mats = flagmats;
622  pbvh->totgrid = totgrid;
623  pbvh->gridkey = *key;
624  pbvh->grid_hidden = grid_hidden;
625  pbvh->leaf_limit = max_ii(LEAF_LIMIT / (gridsize * gridsize), 1);
626 
627  BB cb;
628  BB_reset(&cb);
629 
630  /* For each grid, store the AABB and the AABB centroid */
631  BBC *prim_bbc = MEM_mallocN(sizeof(BBC) * totgrid, "prim_bbc");
632 
633  for (int i = 0; i < totgrid; i++) {
634  CCGElem *grid = grids[i];
635  BBC *bbc = prim_bbc + i;
636 
637  BB_reset((BB *)bbc);
638 
639  for (int j = 0; j < gridsize * gridsize; j++) {
640  BB_expand((BB *)bbc, CCG_elem_offset_co(key, grid, j));
641  }
642 
643  BBC_update_centroid(bbc);
644 
645  BB_expand(&cb, bbc->bcentroid);
646  }
647 
648  if (totgrid) {
649  pbvh_build(pbvh, &cb, prim_bbc, totgrid);
650  }
651 
652  MEM_freeN(prim_bbc);
653 }
654 
656 {
657  PBVH *pbvh = MEM_callocN(sizeof(PBVH), "pbvh");
658  pbvh->respect_hide = true;
659  pbvh->draw_cache_invalid = true;
660  return pbvh;
661 }
662 
663 void BKE_pbvh_free(PBVH *pbvh)
664 {
665  for (int i = 0; i < pbvh->totnode; i++) {
666  PBVHNode *node = &pbvh->nodes[i];
667 
668  if (node->flag & PBVH_Leaf) {
669  if (node->draw_buffers) {
670  GPU_pbvh_buffers_free(node->draw_buffers);
671  }
672  if (node->vert_indices) {
673  MEM_freeN((void *)node->vert_indices);
674  }
675  if (node->loop_indices) {
676  MEM_freeN(node->loop_indices);
677  }
678  if (node->face_vert_indices) {
679  MEM_freeN((void *)node->face_vert_indices);
680  }
681  if (node->bm_faces) {
682  BLI_gset_free(node->bm_faces, NULL);
683  }
684  if (node->bm_unique_verts) {
685  BLI_gset_free(node->bm_unique_verts, NULL);
686  }
687  if (node->bm_other_verts) {
688  BLI_gset_free(node->bm_other_verts, NULL);
689  }
690 
692  }
693  }
694 
695  if (pbvh->deformed) {
696  if (pbvh->verts) {
697  /* if pbvh was deformed, new memory was allocated for verts/faces -- free it */
698 
699  MEM_freeN((void *)pbvh->verts);
700  }
701  }
702 
703  if (pbvh->looptri) {
704  MEM_freeN((void *)pbvh->looptri);
705  }
706 
707  if (pbvh->nodes) {
708  MEM_freeN(pbvh->nodes);
709  }
710 
711  if (pbvh->prim_indices) {
712  MEM_freeN(pbvh->prim_indices);
713  }
714 
715  MEM_SAFE_FREE(pbvh->vert_bitmap);
716 
717  if (pbvh->vbo_id) {
719  }
720 
721  MEM_freeN(pbvh);
722 }
723 
724 static void pbvh_iter_begin(PBVHIter *iter,
725  PBVH *pbvh,
727  void *search_data)
728 {
729  iter->pbvh = pbvh;
730  iter->scb = scb;
731  iter->search_data = search_data;
732 
733  iter->stack = iter->stackfixed;
735 
736  iter->stack[0].node = pbvh->nodes;
737  iter->stack[0].revisiting = false;
738  iter->stacksize = 1;
739 }
740 
741 static void pbvh_iter_end(PBVHIter *iter)
742 {
743  if (iter->stackspace > STACK_FIXED_DEPTH) {
744  MEM_freeN(iter->stack);
745  }
746 }
747 
748 static void pbvh_stack_push(PBVHIter *iter, PBVHNode *node, bool revisiting)
749 {
750  if (UNLIKELY(iter->stacksize == iter->stackspace)) {
751  iter->stackspace *= 2;
752  if (iter->stackspace != (STACK_FIXED_DEPTH * 2)) {
753  iter->stack = MEM_reallocN(iter->stack, sizeof(PBVHStack) * iter->stackspace);
754  }
755  else {
756  iter->stack = MEM_mallocN(sizeof(PBVHStack) * iter->stackspace, "PBVHStack");
757  memcpy(iter->stack, iter->stackfixed, sizeof(PBVHStack) * iter->stacksize);
758  }
759  }
760 
761  iter->stack[iter->stacksize].node = node;
762  iter->stack[iter->stacksize].revisiting = revisiting;
763  iter->stacksize++;
764 }
765 
767 {
768  /* purpose here is to traverse tree, visiting child nodes before their
769  * parents, this order is necessary for e.g. computing bounding boxes */
770 
771  while (iter->stacksize) {
772  /* pop node */
773  iter->stacksize--;
774  PBVHNode *node = iter->stack[iter->stacksize].node;
775 
776  /* on a mesh with no faces this can happen
777  * can remove this check if we know meshes have at least 1 face */
778  if (node == NULL) {
779  return NULL;
780  }
781 
782  bool revisiting = iter->stack[iter->stacksize].revisiting;
783 
784  /* revisiting node already checked */
785  if (revisiting) {
786  return node;
787  }
788 
789  if (iter->scb && !iter->scb(node, iter->search_data)) {
790  continue; /* don't traverse, outside of search zone */
791  }
792 
793  if (node->flag & PBVH_Leaf) {
794  /* immediately hit leaf node */
795  return node;
796  }
797 
798  /* come back later when children are done */
799  pbvh_stack_push(iter, node, true);
800 
801  /* push two child nodes on the stack */
802  pbvh_stack_push(iter, iter->pbvh->nodes + node->children_offset + 1, false);
803  pbvh_stack_push(iter, iter->pbvh->nodes + node->children_offset, false);
804  }
805 
806  return NULL;
807 }
808 
810 {
811  while (iter->stacksize) {
812  /* pop node */
813  iter->stacksize--;
814  PBVHNode *node = iter->stack[iter->stacksize].node;
815 
816  /* on a mesh with no faces this can happen
817  * can remove this check if we know meshes have at least 1 face */
818  if (node == NULL) {
819  return NULL;
820  }
821 
822  if (iter->scb && !iter->scb(node, iter->search_data)) {
823  continue; /* don't traverse, outside of search zone */
824  }
825 
826  if (node->flag & PBVH_Leaf) {
827  /* immediately hit leaf node */
828  return node;
829  }
830 
831  pbvh_stack_push(iter, iter->pbvh->nodes + node->children_offset + 1, false);
832  pbvh_stack_push(iter, iter->pbvh->nodes + node->children_offset, false);
833  }
834 
835  return NULL;
836 }
837 
839  PBVH *pbvh, BKE_pbvh_SearchCallback scb, void *search_data, PBVHNode ***r_array, int *r_tot)
840 {
841  PBVHIter iter;
842  PBVHNode **array = NULL, *node;
843  int tot = 0, space = 0;
844 
845  pbvh_iter_begin(&iter, pbvh, scb, search_data);
846 
847  while ((node = pbvh_iter_next(&iter))) {
848  if (node->flag & PBVH_Leaf) {
849  if (UNLIKELY(tot == space)) {
850  /* resize array if needed */
851  space = (tot == 0) ? 32 : space * 2;
852  array = MEM_recallocN_id(array, sizeof(PBVHNode *) * space, __func__);
853  }
854 
855  array[tot] = node;
856  tot++;
857  }
858  }
859 
860  pbvh_iter_end(&iter);
861 
862  if (tot == 0 && array) {
863  MEM_freeN(array);
864  array = NULL;
865  }
866 
867  *r_array = array;
868  *r_tot = tot;
869 }
870 
873  void *search_data,
875  void *hit_data)
876 {
877  PBVHIter iter;
878  PBVHNode *node;
879 
880  pbvh_iter_begin(&iter, pbvh, scb, search_data);
881 
882  while ((node = pbvh_iter_next(&iter))) {
883  if (node->flag & PBVH_Leaf) {
884  hcb(node, hit_data);
885  }
886  }
887 
888  pbvh_iter_end(&iter);
889 }
890 
891 typedef struct node_tree {
893 
894  struct node_tree *left;
895  struct node_tree *right;
897 
898 static void node_tree_insert(node_tree *tree, node_tree *new_node)
899 {
900  if (new_node->data->tmin < tree->data->tmin) {
901  if (tree->left) {
902  node_tree_insert(tree->left, new_node);
903  }
904  else {
905  tree->left = new_node;
906  }
907  }
908  else {
909  if (tree->right) {
910  node_tree_insert(tree->right, new_node);
911  }
912  else {
913  tree->right = new_node;
914  }
915  }
916 }
917 
920  void *hit_data,
921  float *tmin)
922 {
923  if (tree->left) {
924  traverse_tree(tree->left, hcb, hit_data, tmin);
925  }
926 
927  hcb(tree->data, hit_data, tmin);
928 
929  if (tree->right) {
930  traverse_tree(tree->right, hcb, hit_data, tmin);
931  }
932 }
933 
934 static void free_tree(node_tree *tree)
935 {
936  if (tree->left) {
937  free_tree(tree->left);
938  tree->left = NULL;
939  }
940 
941  if (tree->right) {
942  free_tree(tree->right);
943  tree->right = NULL;
944  }
945 
946  free(tree);
947 }
948 
950 {
951  return node->tmin;
952 }
953 
956  void *search_data,
958  void *hit_data)
959 {
960  PBVHIter iter;
961  PBVHNode *node;
962  node_tree *tree = NULL;
963 
964  pbvh_iter_begin(&iter, pbvh, scb, search_data);
965 
966  while ((node = pbvh_iter_next_occluded(&iter))) {
967  if (node->flag & PBVH_Leaf) {
968  node_tree *new_node = malloc(sizeof(node_tree));
969 
970  new_node->data = node;
971 
972  new_node->left = NULL;
973  new_node->right = NULL;
974 
975  if (tree) {
976  node_tree_insert(tree, new_node);
977  }
978  else {
979  tree = new_node;
980  }
981  }
982  }
983 
984  pbvh_iter_end(&iter);
985 
986  if (tree) {
987  float tmin = FLT_MAX;
988  traverse_tree(tree, hcb, hit_data, &tmin);
989  free_tree(tree);
990  }
991 }
992 
993 static bool update_search_cb(PBVHNode *node, void *data_v)
994 {
995  int flag = POINTER_AS_INT(data_v);
996 
997  if (node->flag & PBVH_Leaf) {
998  return (node->flag & flag) != 0;
999  }
1000 
1001  return true;
1002 }
1003 
1004 typedef struct PBVHUpdateData {
1007  int totnode;
1008 
1009  float (*vnors)[3];
1010  int flag;
1013 
1014 static void pbvh_update_normals_clear_task_cb(void *__restrict userdata,
1015  const int n,
1016  const TaskParallelTLS *__restrict UNUSED(tls))
1017 {
1018  PBVHUpdateData *data = userdata;
1019  PBVH *pbvh = data->pbvh;
1020  PBVHNode *node = data->nodes[n];
1021  float(*vnors)[3] = data->vnors;
1022 
1023  if (node->flag & PBVH_UpdateNormals) {
1024  const int *verts = node->vert_indices;
1025  const int totvert = node->uniq_verts;
1026  for (int i = 0; i < totvert; i++) {
1027  const int v = verts[i];
1028  if (pbvh->vert_bitmap[v]) {
1029  zero_v3(vnors[v]);
1030  }
1031  }
1032  }
1033 }
1034 
1035 static void pbvh_update_normals_accum_task_cb(void *__restrict userdata,
1036  const int n,
1037  const TaskParallelTLS *__restrict UNUSED(tls))
1038 {
1039  PBVHUpdateData *data = userdata;
1040 
1041  PBVH *pbvh = data->pbvh;
1042  PBVHNode *node = data->nodes[n];
1043  float(*vnors)[3] = data->vnors;
1044 
1045  if (node->flag & PBVH_UpdateNormals) {
1046  unsigned int mpoly_prev = UINT_MAX;
1047  float fn[3];
1048 
1049  const int *faces = node->prim_indices;
1050  const int totface = node->totprim;
1051 
1052  for (int i = 0; i < totface; i++) {
1053  const MLoopTri *lt = &pbvh->looptri[faces[i]];
1054  const unsigned int vtri[3] = {
1055  pbvh->mloop[lt->tri[0]].v,
1056  pbvh->mloop[lt->tri[1]].v,
1057  pbvh->mloop[lt->tri[2]].v,
1058  };
1059  const int sides = 3;
1060 
1061  /* Face normal and mask */
1062  if (lt->poly != mpoly_prev) {
1063  const MPoly *mp = &pbvh->mpoly[lt->poly];
1064  BKE_mesh_calc_poly_normal(mp, &pbvh->mloop[mp->loopstart], pbvh->verts, fn);
1065  mpoly_prev = lt->poly;
1066  }
1067 
1068  for (int j = sides; j--;) {
1069  const int v = vtri[j];
1070 
1071  if (pbvh->vert_bitmap[v]) {
1072  /* NOTE: This avoids `lock, add_v3_v3, unlock`
1073  * and is five to ten times quicker than a spin-lock.
1074  * Not exact equivalent though, since atomicity is only ensured for one component
1075  * of the vector at a time, but here it shall not make any sensible difference. */
1076  for (int k = 3; k--;) {
1077  atomic_add_and_fetch_fl(&vnors[v][k], fn[k]);
1078  }
1079  }
1080  }
1081  }
1082  }
1083 }
1084 
1085 static void pbvh_update_normals_store_task_cb(void *__restrict userdata,
1086  const int n,
1087  const TaskParallelTLS *__restrict UNUSED(tls))
1088 {
1089  PBVHUpdateData *data = userdata;
1090  PBVH *pbvh = data->pbvh;
1091  PBVHNode *node = data->nodes[n];
1092  float(*vnors)[3] = data->vnors;
1093 
1094  if (node->flag & PBVH_UpdateNormals) {
1095  const int *verts = node->vert_indices;
1096  const int totvert = node->uniq_verts;
1097 
1098  for (int i = 0; i < totvert; i++) {
1099  const int v = verts[i];
1100 
1101  /* No atomics necessary because we are iterating over uniq_verts only,
1102  * so we know only this thread will handle this vertex. */
1103  if (pbvh->vert_bitmap[v]) {
1104  normalize_v3(vnors[v]);
1105  pbvh->vert_bitmap[v] = false;
1106  }
1107  }
1108 
1109  node->flag &= ~PBVH_UpdateNormals;
1110  }
1111 }
1112 
1113 static void pbvh_faces_update_normals(PBVH *pbvh, PBVHNode **nodes, int totnode)
1114 {
1115  /* subtle assumptions:
1116  * - We know that for all edited vertices, the nodes with faces
1117  * adjacent to these vertices have been marked with PBVH_UpdateNormals.
1118  * This is true because if the vertex is inside the brush radius, the
1119  * bounding box of its adjacent faces will be as well.
1120  * - However this is only true for the vertices that have actually been
1121  * edited, not for all vertices in the nodes marked for update, so we
1122  * can only update vertices marked in the `vert_bitmap`.
1123  */
1124 
1125  PBVHUpdateData data = {
1126  .pbvh = pbvh,
1127  .nodes = nodes,
1128  .vnors = pbvh->vert_normals,
1129  };
1130 
1131  TaskParallelSettings settings;
1132  BKE_pbvh_parallel_range_settings(&settings, true, totnode);
1133 
1134  /* Zero normals before accumulation. */
1138 }
1139 
1140 static void pbvh_update_mask_redraw_task_cb(void *__restrict userdata,
1141  const int n,
1142  const TaskParallelTLS *__restrict UNUSED(tls))
1143 {
1144 
1145  PBVHUpdateData *data = userdata;
1146  PBVH *pbvh = data->pbvh;
1147  PBVHNode *node = data->nodes[n];
1148  if (node->flag & PBVH_UpdateMask) {
1149 
1150  bool has_unmasked = false;
1151  bool has_masked = true;
1152  if (node->flag & PBVH_Leaf) {
1153  PBVHVertexIter vd;
1154 
1156  if (vd.mask && *vd.mask < 1.0f) {
1157  has_unmasked = true;
1158  }
1159  if (vd.mask && *vd.mask > 0.0f) {
1160  has_masked = false;
1161  }
1162  }
1164  }
1165  else {
1166  has_unmasked = true;
1167  has_masked = true;
1168  }
1169  BKE_pbvh_node_fully_masked_set(node, !has_unmasked);
1171 
1172  node->flag &= ~PBVH_UpdateMask;
1173  }
1174 }
1175 
1176 static void pbvh_update_mask_redraw(PBVH *pbvh, PBVHNode **nodes, int totnode, int flag)
1177 {
1178  PBVHUpdateData data = {
1179  .pbvh = pbvh,
1180  .nodes = nodes,
1181  .flag = flag,
1182  };
1183 
1184  TaskParallelSettings settings;
1185  BKE_pbvh_parallel_range_settings(&settings, true, totnode);
1187 }
1188 
1189 static void pbvh_update_visibility_redraw_task_cb(void *__restrict userdata,
1190  const int n,
1191  const TaskParallelTLS *__restrict UNUSED(tls))
1192 {
1193 
1194  PBVHUpdateData *data = userdata;
1195  PBVH *pbvh = data->pbvh;
1196  PBVHNode *node = data->nodes[n];
1197  if (node->flag & PBVH_UpdateVisibility) {
1198  node->flag &= ~PBVH_UpdateVisibility;
1200  if (node->flag & PBVH_Leaf) {
1201  PBVHVertexIter vd;
1203  if (vd.visible) {
1205  return;
1206  }
1207  }
1209  }
1210  }
1211 }
1212 
1213 static void pbvh_update_visibility_redraw(PBVH *pbvh, PBVHNode **nodes, int totnode, int flag)
1214 {
1215  PBVHUpdateData data = {
1216  .pbvh = pbvh,
1217  .nodes = nodes,
1218  .flag = flag,
1219  };
1220 
1221  TaskParallelSettings settings;
1222  BKE_pbvh_parallel_range_settings(&settings, true, totnode);
1224 }
1225 
1226 static void pbvh_update_BB_redraw_task_cb(void *__restrict userdata,
1227  const int n,
1228  const TaskParallelTLS *__restrict UNUSED(tls))
1229 {
1230  PBVHUpdateData *data = userdata;
1231  PBVH *pbvh = data->pbvh;
1232  PBVHNode *node = data->nodes[n];
1233  const int flag = data->flag;
1234 
1235  if ((flag & PBVH_UpdateBB) && (node->flag & PBVH_UpdateBB)) {
1236  /* don't clear flag yet, leave it for flushing later */
1237  /* Note that bvh usage is read-only here, so no need to thread-protect it. */
1238  update_node_vb(pbvh, node);
1239  }
1240 
1241  if ((flag & PBVH_UpdateOriginalBB) && (node->flag & PBVH_UpdateOriginalBB)) {
1242  node->orig_vb = node->vb;
1243  }
1244 
1245  if ((flag & PBVH_UpdateRedraw) && (node->flag & PBVH_UpdateRedraw)) {
1246  node->flag &= ~PBVH_UpdateRedraw;
1247  }
1248 }
1249 
1250 void pbvh_update_BB_redraw(PBVH *pbvh, PBVHNode **nodes, int totnode, int flag)
1251 {
1252  /* update BB, redraw flag */
1253  PBVHUpdateData data = {
1254  .pbvh = pbvh,
1255  .nodes = nodes,
1256  .flag = flag,
1257  };
1258 
1259  TaskParallelSettings settings;
1260  BKE_pbvh_parallel_range_settings(&settings, true, totnode);
1262 }
1263 
1265 {
1268  return update_flags;
1269 }
1270 
1271 bool BKE_pbvh_get_color_layer(const Mesh *me, CustomDataLayer **r_layer, eAttrDomain *r_attr)
1272 {
1274 
1275  if (!layer || !ELEM(layer->type, CD_PROP_COLOR, CD_PROP_BYTE_COLOR)) {
1276  *r_layer = NULL;
1277  *r_attr = ATTR_DOMAIN_NUM;
1278  return false;
1279  }
1280 
1281  eAttrDomain domain = BKE_id_attribute_domain((ID *)me, layer);
1282 
1283  if (!ELEM(domain, ATTR_DOMAIN_POINT, ATTR_DOMAIN_CORNER)) {
1284  *r_layer = NULL;
1285  *r_attr = ATTR_DOMAIN_NUM;
1286  return false;
1287  }
1288 
1289  *r_layer = layer;
1290  *r_attr = domain;
1291 
1292  return true;
1293 }
1294 
1295 static void pbvh_update_draw_buffer_cb(void *__restrict userdata,
1296  const int n,
1297  const TaskParallelTLS *__restrict UNUSED(tls))
1298 {
1299  /* Create and update draw buffers. The functions called here must not
1300  * do any OpenGL calls. Flags are not cleared immediately, that happens
1301  * after GPU_pbvh_buffer_flush() which does the final OpenGL calls. */
1302  PBVHUpdateData *data = userdata;
1303  PBVH *pbvh = data->pbvh;
1304  PBVHNode *node = data->nodes[n];
1305 
1306  CustomData *vdata, *ldata;
1307 
1308  if (!pbvh->bm) {
1309  vdata = pbvh->vdata;
1310  ldata = pbvh->ldata;
1311  }
1312  else {
1313  vdata = &pbvh->bm->vdata;
1314  ldata = &pbvh->bm->ldata;
1315  }
1316 
1317  if (node->flag & PBVH_RebuildDrawBuffers) {
1318  switch (pbvh->type) {
1319  case PBVH_GRIDS: {
1320  bool smooth = node->totprim > 0 ?
1321  pbvh->grid_flag_mats[node->prim_indices[0]].flag & ME_SMOOTH :
1322  false;
1323 
1324  node->draw_buffers = GPU_pbvh_grid_buffers_build(node->totprim, pbvh->grid_hidden, smooth);
1325  break;
1326  }
1327  case PBVH_FACES:
1328  node->draw_buffers = GPU_pbvh_mesh_buffers_build(
1329  pbvh->mpoly,
1330  pbvh->mloop,
1331  pbvh->looptri,
1332  pbvh->verts,
1333  node->prim_indices,
1335  node->totprim,
1336  pbvh->mesh);
1337  break;
1338  case PBVH_BMESH:
1339  node->draw_buffers = GPU_pbvh_bmesh_buffers_build(pbvh->flags &
1341  break;
1342  }
1343  }
1344 
1345  if (node->flag & PBVH_UpdateDrawBuffers) {
1346  const int update_flags = pbvh_get_buffers_update_flags(pbvh);
1347  switch (pbvh->type) {
1348  case PBVH_GRIDS:
1350  node->draw_buffers,
1351  pbvh->subdiv_ccg,
1352  pbvh->grids,
1353  pbvh->grid_flag_mats,
1354  node->prim_indices,
1355  node->totprim,
1356  pbvh->face_sets,
1357  pbvh->face_sets_color_seed,
1359  &pbvh->gridkey,
1360  update_flags);
1361  break;
1362  case PBVH_FACES: {
1364  node->draw_buffers,
1365  pbvh->verts,
1366  vdata,
1367  ldata,
1370  pbvh->face_sets_color_seed,
1372  update_flags,
1373  pbvh->vert_normals);
1374  break;
1375  }
1376  case PBVH_BMESH:
1378  node->draw_buffers,
1379  pbvh->bm,
1380  node->bm_faces,
1381  node->bm_unique_verts,
1382  node->bm_other_verts,
1383  update_flags);
1384  break;
1385  }
1386  }
1387 }
1388 
1390 {
1391  if (node->draw_buffers) {
1392  pbvh->draw_cache_invalid = true;
1393 
1394  GPU_pbvh_buffers_free(node->draw_buffers);
1395  node->draw_buffers = NULL;
1396  }
1397 }
1398 
1399 static void pbvh_check_draw_layout(PBVH *pbvh)
1400 {
1401  const CustomData *vdata;
1402  const CustomData *ldata;
1403 
1404  if (!pbvh->vbo_id) {
1405  pbvh->vbo_id = GPU_pbvh_make_format();
1406  }
1407 
1408  switch (pbvh->type) {
1409  case PBVH_BMESH:
1410  if (!pbvh->bm) {
1411  /* BMesh hasn't been created yet */
1412  return;
1413  }
1414 
1415  vdata = &pbvh->bm->vdata;
1416  ldata = &pbvh->bm->ldata;
1417  break;
1418  case PBVH_FACES:
1419  vdata = pbvh->vdata;
1420  ldata = pbvh->ldata;
1421  break;
1422  case PBVH_GRIDS:
1423  ldata = vdata = NULL;
1424  break;
1425  }
1426 
1427  /* Rebuild all draw buffers if attribute layout changed.
1428  *
1429  * NOTE: The optimization where we only send active attributes
1430  * to the GPU in workbench mode is disabled due to bugs
1431  * (there's no guarantee there isn't another EEVEE viewport which would
1432  * free the draw buffers and corrupt the draw cache).
1433  */
1434  if (GPU_pbvh_attribute_names_update(pbvh->type, pbvh->vbo_id, vdata, ldata, false)) {
1435  /* attribute layout changed; force rebuild */
1436  for (int i = 0; i < pbvh->totnode; i++) {
1437  PBVHNode *node = pbvh->nodes + i;
1438 
1439  if (node->flag & PBVH_Leaf) {
1441  }
1442  }
1443  }
1444 }
1445 
1446 static void pbvh_update_draw_buffers(PBVH *pbvh, PBVHNode **nodes, int totnode, int update_flag)
1447 {
1448  const CustomData *vdata;
1449 
1450  if (!pbvh->vbo_id) {
1451  pbvh->vbo_id = GPU_pbvh_make_format();
1452  }
1453 
1454  switch (pbvh->type) {
1455  case PBVH_BMESH:
1456  if (!pbvh->bm) {
1457  /* BMesh hasn't been created yet */
1458  return;
1459  }
1460 
1461  vdata = &pbvh->bm->vdata;
1462  break;
1463  case PBVH_FACES:
1464  vdata = pbvh->vdata;
1465  break;
1466  case PBVH_GRIDS:
1467  vdata = NULL;
1468  break;
1469  }
1470  UNUSED_VARS(vdata);
1471 
1472  if ((update_flag & PBVH_RebuildDrawBuffers) || ELEM(pbvh->type, PBVH_GRIDS, PBVH_BMESH)) {
1473  /* Free buffers uses OpenGL, so not in parallel. */
1474  for (int n = 0; n < totnode; n++) {
1475  PBVHNode *node = nodes[n];
1476  if (node->flag & PBVH_RebuildDrawBuffers) {
1478  }
1479  else if ((node->flag & PBVH_UpdateDrawBuffers) && node->draw_buffers) {
1480  if (pbvh->type == PBVH_GRIDS) {
1482  node->draw_buffers, pbvh->grid_flag_mats, node->prim_indices);
1483  }
1484  else if (pbvh->type == PBVH_BMESH) {
1486  }
1487  }
1488  }
1489  }
1490 
1491  /* Parallel creation and update of draw buffers. */
1492  PBVHUpdateData data = {
1493  .pbvh = pbvh,
1494  .nodes = nodes,
1495  };
1496 
1497  TaskParallelSettings settings;
1498  BKE_pbvh_parallel_range_settings(&settings, true, totnode);
1499  BLI_task_parallel_range(0, totnode, &data, pbvh_update_draw_buffer_cb, &settings);
1500 
1501  for (int i = 0; i < totnode; i++) {
1502  PBVHNode *node = nodes[i];
1503 
1504  if (node->flag & PBVH_UpdateDrawBuffers) {
1505  /* Flush buffers uses OpenGL, so not in parallel. */
1506  GPU_pbvh_buffers_update_flush(node->draw_buffers);
1507  }
1508 
1510  }
1511 }
1512 
1513 static int pbvh_flush_bb(PBVH *pbvh, PBVHNode *node, int flag)
1514 {
1515  int update = 0;
1516 
1517  /* Difficult to multi-thread well, we just do single threaded recursive. */
1518  if (node->flag & PBVH_Leaf) {
1519  if (flag & PBVH_UpdateBB) {
1520  update |= (node->flag & PBVH_UpdateBB);
1521  node->flag &= ~PBVH_UpdateBB;
1522  }
1523 
1524  if (flag & PBVH_UpdateOriginalBB) {
1525  update |= (node->flag & PBVH_UpdateOriginalBB);
1526  node->flag &= ~PBVH_UpdateOriginalBB;
1527  }
1528 
1529  return update;
1530  }
1531 
1532  update |= pbvh_flush_bb(pbvh, pbvh->nodes + node->children_offset, flag);
1533  update |= pbvh_flush_bb(pbvh, pbvh->nodes + node->children_offset + 1, flag);
1534 
1535  if (update & PBVH_UpdateBB) {
1536  update_node_vb(pbvh, node);
1537  }
1538  if (update & PBVH_UpdateOriginalBB) {
1539  node->orig_vb = node->vb;
1540  }
1541 
1542  return update;
1543 }
1544 
1545 void BKE_pbvh_update_bounds(PBVH *pbvh, int flag)
1546 {
1547  if (!pbvh->nodes) {
1548  return;
1549  }
1550 
1551  PBVHNode **nodes;
1552  int totnode;
1553 
1554  BKE_pbvh_search_gather(pbvh, update_search_cb, POINTER_FROM_INT(flag), &nodes, &totnode);
1555 
1557  pbvh_update_BB_redraw(pbvh, nodes, totnode, flag);
1558  }
1559 
1560  if (flag & (PBVH_UpdateBB | PBVH_UpdateOriginalBB)) {
1561  pbvh_flush_bb(pbvh, pbvh->nodes, flag);
1562  }
1563 
1564  MEM_SAFE_FREE(nodes);
1565 }
1566 
1567 void BKE_pbvh_update_vertex_data(PBVH *pbvh, int flag)
1568 {
1569  if (!pbvh->nodes) {
1570  return;
1571  }
1572 
1573  PBVHNode **nodes;
1574  int totnode;
1575 
1576  BKE_pbvh_search_gather(pbvh, update_search_cb, POINTER_FROM_INT(flag), &nodes, &totnode);
1577 
1578  if (flag & (PBVH_UpdateMask)) {
1579  pbvh_update_mask_redraw(pbvh, nodes, totnode, flag);
1580  }
1581 
1582  if (flag & (PBVH_UpdateColor)) {
1583  for (int i = 0; i < totnode; i++) {
1585  }
1586  }
1587 
1588  if (flag & (PBVH_UpdateVisibility)) {
1589  pbvh_update_visibility_redraw(pbvh, nodes, totnode, flag);
1590  }
1591 
1592  if (nodes) {
1593  MEM_freeN(nodes);
1594  }
1595 }
1596 
1598 {
1599  MVert *mvert;
1600  const int *vert_indices;
1601  int totvert, i;
1602  BKE_pbvh_node_num_verts(pbvh, node, NULL, &totvert);
1603  BKE_pbvh_node_get_verts(pbvh, node, &vert_indices, &mvert);
1604 
1605  for (i = 0; i < totvert; i++) {
1606  MVert *v = &mvert[vert_indices[i]];
1607  if (!(v->flag & ME_HIDE)) {
1609  return;
1610  }
1611  }
1612 
1614 }
1615 
1617 {
1618  CCGElem **grids;
1619  BLI_bitmap **grid_hidden;
1620  int *grid_indices, totgrid, i;
1621 
1622  BKE_pbvh_node_get_grids(pbvh, node, &grid_indices, &totgrid, NULL, NULL, &grids);
1623  grid_hidden = BKE_pbvh_grid_hidden(pbvh);
1624  CCGKey key = *BKE_pbvh_get_grid_key(pbvh);
1625 
1626  for (i = 0; i < totgrid; i++) {
1627  int g = grid_indices[i], x, y;
1628  BLI_bitmap *gh = grid_hidden[g];
1629 
1630  if (!gh) {
1632  return;
1633  }
1634 
1635  for (y = 0; y < key.grid_size; y++) {
1636  for (x = 0; x < key.grid_size; x++) {
1637  if (!BLI_BITMAP_TEST(gh, y * key.grid_size + x)) {
1639  return;
1640  }
1641  }
1642  }
1643  }
1645 }
1646 
1648 {
1649  GSet *unique, *other;
1650 
1653 
1654  GSetIterator gs_iter;
1655 
1656  GSET_ITER (gs_iter, unique) {
1657  BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
1660  return;
1661  }
1662  }
1663 
1664  GSET_ITER (gs_iter, other) {
1665  BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
1668  return;
1669  }
1670  }
1671 
1673 }
1674 
1675 static void pbvh_update_visibility_task_cb(void *__restrict userdata,
1676  const int n,
1677  const TaskParallelTLS *__restrict UNUSED(tls))
1678 {
1679 
1680  PBVHUpdateData *data = userdata;
1681  PBVH *pbvh = data->pbvh;
1682  PBVHNode *node = data->nodes[n];
1683  if (node->flag & PBVH_UpdateVisibility) {
1684  switch (BKE_pbvh_type(pbvh)) {
1685  case PBVH_FACES:
1687  break;
1688  case PBVH_GRIDS:
1690  break;
1691  case PBVH_BMESH:
1693  break;
1694  }
1695  node->flag &= ~PBVH_UpdateVisibility;
1696  }
1697 }
1698 
1699 static void pbvh_update_visibility(PBVH *pbvh, PBVHNode **nodes, int totnode)
1700 {
1701  PBVHUpdateData data = {
1702  .pbvh = pbvh,
1703  .nodes = nodes,
1704  };
1705 
1706  TaskParallelSettings settings;
1707  BKE_pbvh_parallel_range_settings(&settings, true, totnode);
1709 }
1710 
1712 {
1713  if (!pbvh->nodes) {
1714  return;
1715  }
1716 
1717  PBVHNode **nodes;
1718  int totnode;
1719 
1721  pbvh, update_search_cb, POINTER_FROM_INT(PBVH_UpdateVisibility), &nodes, &totnode);
1722  pbvh_update_visibility(pbvh, nodes, totnode);
1723 
1724  if (nodes) {
1725  MEM_freeN(nodes);
1726  }
1727 }
1728 
1729 void BKE_pbvh_redraw_BB(PBVH *pbvh, float bb_min[3], float bb_max[3])
1730 {
1731  PBVHIter iter;
1732  PBVHNode *node;
1733  BB bb;
1734 
1735  BB_reset(&bb);
1736 
1737  pbvh_iter_begin(&iter, pbvh, NULL, NULL);
1738 
1739  while ((node = pbvh_iter_next(&iter))) {
1740  if (node->flag & PBVH_UpdateRedraw) {
1741  BB_expand_with_bb(&bb, &node->vb);
1742  }
1743  }
1744 
1745  pbvh_iter_end(&iter);
1746 
1747  copy_v3_v3(bb_min, bb.bmin);
1748  copy_v3_v3(bb_max, bb.bmax);
1749 }
1750 
1751 void BKE_pbvh_get_grid_updates(PBVH *pbvh, bool clear, void ***r_gridfaces, int *r_totface)
1752 {
1753  GSet *face_set = BLI_gset_ptr_new(__func__);
1754  PBVHNode *node;
1755  PBVHIter iter;
1756 
1757  pbvh_iter_begin(&iter, pbvh, NULL, NULL);
1758 
1759  while ((node = pbvh_iter_next(&iter))) {
1760  if (node->flag & PBVH_UpdateNormals) {
1761  for (uint i = 0; i < node->totprim; i++) {
1762  void *face = pbvh->gridfaces[node->prim_indices[i]];
1763  BLI_gset_add(face_set, face);
1764  }
1765 
1766  if (clear) {
1767  node->flag &= ~PBVH_UpdateNormals;
1768  }
1769  }
1770  }
1771 
1772  pbvh_iter_end(&iter);
1773 
1774  const int tot = BLI_gset_len(face_set);
1775  if (tot == 0) {
1776  *r_totface = 0;
1777  *r_gridfaces = NULL;
1778  BLI_gset_free(face_set, NULL);
1779  return;
1780  }
1781 
1782  void **faces = MEM_mallocN(sizeof(*faces) * tot, "PBVH Grid Faces");
1783 
1784  GSetIterator gs_iter;
1785  int i;
1786  GSET_ITER_INDEX (gs_iter, face_set, i) {
1787  faces[i] = BLI_gsetIterator_getKey(&gs_iter);
1788  }
1789 
1790  BLI_gset_free(face_set, NULL);
1791 
1792  *r_totface = tot;
1793  *r_gridfaces = faces;
1794 }
1795 
1796 /***************************** PBVH Access ***********************************/
1797 
1799 {
1800  return pbvh->type;
1801 }
1802 
1803 bool BKE_pbvh_has_faces(const PBVH *pbvh)
1804 {
1805  if (pbvh->type == PBVH_BMESH) {
1806  return (pbvh->bm->totface != 0);
1807  }
1808 
1809  return (pbvh->totprim != 0);
1810 }
1811 
1812 void BKE_pbvh_bounding_box(const PBVH *pbvh, float min[3], float max[3])
1813 {
1814  if (pbvh->totnode) {
1815  const BB *bb = &pbvh->nodes[0].vb;
1816  copy_v3_v3(min, bb->bmin);
1817  copy_v3_v3(max, bb->bmax);
1818  }
1819  else {
1820  zero_v3(min);
1821  zero_v3(max);
1822  }
1823 }
1824 
1826 {
1827  BLI_assert(pbvh->type == PBVH_GRIDS);
1828  return pbvh->grid_hidden;
1829 }
1830 
1831 const CCGKey *BKE_pbvh_get_grid_key(const PBVH *pbvh)
1832 {
1833  BLI_assert(pbvh->type == PBVH_GRIDS);
1834  return &pbvh->gridkey;
1835 }
1836 
1837 struct CCGElem **BKE_pbvh_get_grids(const PBVH *pbvh)
1838 {
1839  BLI_assert(pbvh->type == PBVH_GRIDS);
1840  return pbvh->grids;
1841 }
1842 
1844 {
1845  BLI_assert(pbvh->type == PBVH_GRIDS);
1846  return pbvh->grid_hidden;
1847 }
1848 
1850 {
1851  BLI_assert(pbvh->type == PBVH_GRIDS);
1852  return pbvh->totgrid * pbvh->gridkey.grid_area;
1853 }
1854 
1856 {
1857  BLI_assert(pbvh->type == PBVH_GRIDS);
1858  return pbvh->totgrid * (pbvh->gridkey.grid_size - 1) * (pbvh->gridkey.grid_size - 1);
1859 }
1860 
1862 {
1863  BLI_assert(pbvh->type == PBVH_BMESH);
1864  return pbvh->bm;
1865 }
1866 
1867 /***************************** Node Access ***********************************/
1868 
1870 {
1873 }
1874 
1876 {
1878 }
1879 
1881 {
1883 }
1884 
1886 {
1887  for (int n = 0; n < pbvh->totnode; n++) {
1888  PBVHNode *node = &pbvh->nodes[n];
1889  if (node->flag & PBVH_Leaf) {
1890  node->flag |= PBVH_RebuildPixels;
1891  }
1892  }
1893 }
1894 
1896 {
1899 }
1900 
1902 {
1904 }
1905 
1907 {
1909 }
1910 
1912 {
1913  node->flag |= PBVH_UpdateNormals;
1914 }
1915 
1917 {
1918  BLI_assert(node->flag & PBVH_Leaf);
1919 
1920  if (fully_hidden) {
1921  node->flag |= PBVH_FullyHidden;
1922  }
1923  else {
1924  node->flag &= ~PBVH_FullyHidden;
1925  }
1926 }
1927 
1929 {
1930  return (node->flag & PBVH_Leaf) && (node->flag & PBVH_FullyHidden);
1931 }
1932 
1934 {
1935  BLI_assert(node->flag & PBVH_Leaf);
1936 
1937  if (fully_masked) {
1938  node->flag |= PBVH_FullyMasked;
1939  }
1940  else {
1941  node->flag &= ~PBVH_FullyMasked;
1942  }
1943 }
1944 
1946 {
1947  return (node->flag & PBVH_Leaf) && (node->flag & PBVH_FullyMasked);
1948 }
1949 
1951 {
1952  BLI_assert(node->flag & PBVH_Leaf);
1953 
1954  if (fully_masked) {
1955  node->flag |= PBVH_FullyUnmasked;
1956  }
1957  else {
1958  node->flag &= ~PBVH_FullyUnmasked;
1959  }
1960 }
1961 
1963 {
1964  return (node->flag & PBVH_Leaf) && (node->flag & PBVH_FullyUnmasked);
1965 }
1966 
1968 {
1969  BLI_assert(pbvh->type == PBVH_FACES);
1970  pbvh->vert_bitmap[index] = true;
1971 }
1972 
1974  PBVHNode *node,
1975  const int **r_loop_indices,
1976  const MLoop **r_loops)
1977 {
1979 
1980  if (r_loop_indices) {
1981  *r_loop_indices = node->loop_indices;
1982  }
1983 
1984  if (r_loops) {
1985  *r_loops = pbvh->mloop;
1986  }
1987 }
1988 
1990  PBVHNode *node,
1991  const int **r_vert_indices,
1992  MVert **r_verts)
1993 {
1994  if (r_vert_indices) {
1995  *r_vert_indices = node->vert_indices;
1996  }
1997 
1998  if (r_verts) {
1999  *r_verts = pbvh->verts;
2000  }
2001 }
2002 
2003 void BKE_pbvh_node_num_verts(PBVH *pbvh, PBVHNode *node, int *r_uniquevert, int *r_totvert)
2004 {
2005  int tot;
2006 
2007  switch (pbvh->type) {
2008  case PBVH_GRIDS:
2009  tot = node->totprim * pbvh->gridkey.grid_area;
2010  if (r_totvert) {
2011  *r_totvert = tot;
2012  }
2013  if (r_uniquevert) {
2014  *r_uniquevert = tot;
2015  }
2016  break;
2017  case PBVH_FACES:
2018  if (r_totvert) {
2019  *r_totvert = node->uniq_verts + node->face_verts;
2020  }
2021  if (r_uniquevert) {
2022  *r_uniquevert = node->uniq_verts;
2023  }
2024  break;
2025  case PBVH_BMESH:
2026  tot = BLI_gset_len(node->bm_unique_verts);
2027  if (r_totvert) {
2028  *r_totvert = tot + BLI_gset_len(node->bm_other_verts);
2029  }
2030  if (r_uniquevert) {
2031  *r_uniquevert = tot;
2032  }
2033  break;
2034  }
2035 }
2036 
2038  PBVHNode *node,
2039  int **r_grid_indices,
2040  int *r_totgrid,
2041  int *r_maxgrid,
2042  int *r_gridsize,
2043  CCGElem ***r_griddata)
2044 {
2045  switch (pbvh->type) {
2046  case PBVH_GRIDS:
2047  if (r_grid_indices) {
2048  *r_grid_indices = node->prim_indices;
2049  }
2050  if (r_totgrid) {
2051  *r_totgrid = node->totprim;
2052  }
2053  if (r_maxgrid) {
2054  *r_maxgrid = pbvh->totgrid;
2055  }
2056  if (r_gridsize) {
2057  *r_gridsize = pbvh->gridkey.grid_size;
2058  }
2059  if (r_griddata) {
2060  *r_griddata = pbvh->grids;
2061  }
2062  break;
2063  case PBVH_FACES:
2064  case PBVH_BMESH:
2065  if (r_grid_indices) {
2066  *r_grid_indices = NULL;
2067  }
2068  if (r_totgrid) {
2069  *r_totgrid = 0;
2070  }
2071  if (r_maxgrid) {
2072  *r_maxgrid = 0;
2073  }
2074  if (r_gridsize) {
2075  *r_gridsize = 0;
2076  }
2077  if (r_griddata) {
2078  *r_griddata = NULL;
2079  }
2080  break;
2081  }
2082 }
2083 
2084 void BKE_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
2085 {
2086  copy_v3_v3(bb_min, node->vb.bmin);
2087  copy_v3_v3(bb_max, node->vb.bmax);
2088 }
2089 
2090 void BKE_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
2091 {
2092  copy_v3_v3(bb_min, node->orig_vb.bmin);
2093  copy_v3_v3(bb_max, node->orig_vb.bmax);
2094 }
2095 
2096 void BKE_pbvh_node_get_proxies(PBVHNode *node, PBVHProxyNode **proxies, int *proxy_count)
2097 {
2098  if (node->proxy_count > 0) {
2099  if (proxies) {
2100  *proxies = node->proxies;
2101  }
2102  if (proxy_count) {
2103  *proxy_count = node->proxy_count;
2104  }
2105  }
2106  else {
2107  if (proxies) {
2108  *proxies = NULL;
2109  }
2110  if (proxy_count) {
2111  *proxy_count = 0;
2112  }
2113  }
2114 }
2115 
2117  int (**r_orco_tris)[3],
2118  int *r_orco_tris_num,
2119  float (**r_orco_coords)[3])
2120 {
2121  *r_orco_tris = node->bm_ortri;
2122  *r_orco_tris_num = node->bm_tot_ortri;
2123  *r_orco_coords = node->bm_orco;
2124 }
2125 
2127 {
2128  BLI_assert(pbvh->type == PBVH_FACES);
2129  const int *verts = node->vert_indices;
2130  const int totvert = node->uniq_verts + node->face_verts;
2131 
2132  for (int i = 0; i < totvert; i++) {
2133  const int v = verts[i];
2134 
2135  if (pbvh->vert_bitmap[v]) {
2136  return true;
2137  }
2138  }
2139 
2140  return false;
2141 }
2142 
2143 /********************************* Ray-cast ***********************************/
2144 
2145 typedef struct {
2146  struct IsectRayAABB_Precalc ray;
2147  bool original;
2148 } RaycastData;
2149 
2150 static bool ray_aabb_intersect(PBVHNode *node, void *data_v)
2151 {
2152  RaycastData *rcd = data_v;
2153  const float *bb_min, *bb_max;
2154 
2155  if (rcd->original) {
2156  /* BKE_pbvh_node_get_original_BB */
2157  bb_min = node->orig_vb.bmin;
2158  bb_max = node->orig_vb.bmax;
2159  }
2160  else {
2161  /* BKE_pbvh_node_get_BB */
2162  bb_min = node->vb.bmin;
2163  bb_max = node->vb.bmax;
2164  }
2165 
2166  return isect_ray_aabb_v3(&rcd->ray, bb_min, bb_max, &node->tmin);
2167 }
2168 
2171  void *data,
2172  const float ray_start[3],
2173  const float ray_normal[3],
2174  bool original)
2175 {
2176  RaycastData rcd;
2177 
2178  isect_ray_aabb_v3_precalc(&rcd.ray, ray_start, ray_normal);
2179  rcd.original = original;
2180 
2182 }
2183 
2184 bool ray_face_intersection_quad(const float ray_start[3],
2185  struct IsectRayPrecalc *isect_precalc,
2186  const float t0[3],
2187  const float t1[3],
2188  const float t2[3],
2189  const float t3[3],
2190  float *depth)
2191 {
2192  float depth_test;
2193 
2194  if ((isect_ray_tri_watertight_v3(ray_start, isect_precalc, t0, t1, t2, &depth_test, NULL) &&
2195  (depth_test < *depth)) ||
2196  (isect_ray_tri_watertight_v3(ray_start, isect_precalc, t0, t2, t3, &depth_test, NULL) &&
2197  (depth_test < *depth))) {
2198  *depth = depth_test;
2199  return true;
2200  }
2201 
2202  return false;
2203 }
2204 
2205 bool ray_face_intersection_tri(const float ray_start[3],
2206  struct IsectRayPrecalc *isect_precalc,
2207  const float t0[3],
2208  const float t1[3],
2209  const float t2[3],
2210  float *depth)
2211 {
2212  float depth_test;
2213  if ((isect_ray_tri_watertight_v3(ray_start, isect_precalc, t0, t1, t2, &depth_test, NULL) &&
2214  (depth_test < *depth))) {
2215  *depth = depth_test;
2216  return true;
2217  }
2218 
2219  return false;
2220 }
2221 
2222 /* Take advantage of the fact we know this won't be an intersection.
2223  * Just handle ray-tri edges. */
2224 static float dist_squared_ray_to_tri_v3_fast(const float ray_origin[3],
2225  const float ray_direction[3],
2226  const float v0[3],
2227  const float v1[3],
2228  const float v2[3],
2229  float r_point[3],
2230  float *r_depth)
2231 {
2232  const float *tri[3] = {v0, v1, v2};
2233  float dist_sq_best = FLT_MAX;
2234  for (int i = 0, j = 2; i < 3; j = i++) {
2235  float point_test[3], depth_test = FLT_MAX;
2236  const float dist_sq_test = dist_squared_ray_to_seg_v3(
2237  ray_origin, ray_direction, tri[i], tri[j], point_test, &depth_test);
2238  if (dist_sq_test < dist_sq_best || i == 0) {
2239  copy_v3_v3(r_point, point_test);
2240  *r_depth = depth_test;
2241  dist_sq_best = dist_sq_test;
2242  }
2243  }
2244  return dist_sq_best;
2245 }
2246 
2247 bool ray_face_nearest_quad(const float ray_start[3],
2248  const float ray_normal[3],
2249  const float t0[3],
2250  const float t1[3],
2251  const float t2[3],
2252  const float t3[3],
2253  float *depth,
2254  float *dist_sq)
2255 {
2256  float dist_sq_test;
2257  float co[3], depth_test;
2258 
2259  if (((dist_sq_test = dist_squared_ray_to_tri_v3_fast(
2260  ray_start, ray_normal, t0, t1, t2, co, &depth_test)) < *dist_sq)) {
2261  *dist_sq = dist_sq_test;
2262  *depth = depth_test;
2263  if (((dist_sq_test = dist_squared_ray_to_tri_v3_fast(
2264  ray_start, ray_normal, t0, t2, t3, co, &depth_test)) < *dist_sq)) {
2265  *dist_sq = dist_sq_test;
2266  *depth = depth_test;
2267  }
2268  return true;
2269  }
2270 
2271  return false;
2272 }
2273 
2274 bool ray_face_nearest_tri(const float ray_start[3],
2275  const float ray_normal[3],
2276  const float t0[3],
2277  const float t1[3],
2278  const float t2[3],
2279  float *depth,
2280  float *dist_sq)
2281 {
2282  float dist_sq_test;
2283  float co[3], depth_test;
2284 
2285  if (((dist_sq_test = dist_squared_ray_to_tri_v3_fast(
2286  ray_start, ray_normal, t0, t1, t2, co, &depth_test)) < *dist_sq)) {
2287  *dist_sq = dist_sq_test;
2288  *depth = depth_test;
2289  return true;
2290  }
2291 
2292  return false;
2293 }
2294 
2295 static bool pbvh_faces_node_raycast(PBVH *pbvh,
2296  const PBVHNode *node,
2297  float (*origco)[3],
2298  const float ray_start[3],
2299  const float ray_normal[3],
2300  struct IsectRayPrecalc *isect_precalc,
2301  float *depth,
2302  int *r_active_vertex_index,
2303  int *r_active_face_index,
2304  float *r_face_normal)
2305 {
2306  const MVert *vert = pbvh->verts;
2307  const MLoop *mloop = pbvh->mloop;
2308  const int *faces = node->prim_indices;
2309  int totface = node->totprim;
2310  bool hit = false;
2311  float nearest_vertex_co[3] = {0.0f};
2312 
2313  for (int i = 0; i < totface; i++) {
2314  const MLoopTri *lt = &pbvh->looptri[faces[i]];
2315  const int *face_verts = node->face_vert_indices[i];
2316 
2317  if (pbvh->respect_hide && paint_is_face_hidden(lt, vert, mloop)) {
2318  continue;
2319  }
2320 
2321  const float *co[3];
2322  if (origco) {
2323  /* Intersect with backed up original coordinates. */
2324  co[0] = origco[face_verts[0]];
2325  co[1] = origco[face_verts[1]];
2326  co[2] = origco[face_verts[2]];
2327  }
2328  else {
2329  /* intersect with current coordinates */
2330  co[0] = vert[mloop[lt->tri[0]].v].co;
2331  co[1] = vert[mloop[lt->tri[1]].v].co;
2332  co[2] = vert[mloop[lt->tri[2]].v].co;
2333  }
2334 
2335  if (ray_face_intersection_tri(ray_start, isect_precalc, co[0], co[1], co[2], depth)) {
2336  hit = true;
2337 
2338  if (r_face_normal) {
2339  normal_tri_v3(r_face_normal, co[0], co[1], co[2]);
2340  }
2341 
2342  if (r_active_vertex_index) {
2343  float location[3] = {0.0f};
2344  madd_v3_v3v3fl(location, ray_start, ray_normal, *depth);
2345  for (int j = 0; j < 3; j++) {
2346  /* Always assign nearest_vertex_co in the first iteration to avoid comparison against
2347  * uninitialized values. This stores the closest vertex in the current intersecting
2348  * triangle. */
2349  if (j == 0 ||
2350  len_squared_v3v3(location, co[j]) < len_squared_v3v3(location, nearest_vertex_co)) {
2351  copy_v3_v3(nearest_vertex_co, co[j]);
2352  *r_active_vertex_index = mloop[lt->tri[j]].v;
2353  *r_active_face_index = lt->poly;
2354  }
2355  }
2356  }
2357  }
2358  }
2359 
2360  return hit;
2361 }
2362 
2363 static bool pbvh_grids_node_raycast(PBVH *pbvh,
2364  PBVHNode *node,
2365  float (*origco)[3],
2366  const float ray_start[3],
2367  const float ray_normal[3],
2368  struct IsectRayPrecalc *isect_precalc,
2369  float *depth,
2370  int *r_active_vertex_index,
2371  int *r_active_grid_index,
2372  float *r_face_normal)
2373 {
2374  const int totgrid = node->totprim;
2375  const int gridsize = pbvh->gridkey.grid_size;
2376  bool hit = false;
2377  float nearest_vertex_co[3] = {0.0};
2378  const CCGKey *gridkey = &pbvh->gridkey;
2379 
2380  for (int i = 0; i < totgrid; i++) {
2381  const int grid_index = node->prim_indices[i];
2382  CCGElem *grid = pbvh->grids[grid_index];
2383  BLI_bitmap *gh;
2384 
2385  if (!grid) {
2386  continue;
2387  }
2388 
2389  gh = pbvh->grid_hidden[grid_index];
2390 
2391  for (int y = 0; y < gridsize - 1; y++) {
2392  for (int x = 0; x < gridsize - 1; x++) {
2393  /* check if grid face is hidden */
2394  if (gh) {
2395  if (paint_is_grid_face_hidden(gh, gridsize, x, y)) {
2396  continue;
2397  }
2398  }
2399 
2400  const float *co[4];
2401  if (origco) {
2402  co[0] = origco[(y + 1) * gridsize + x];
2403  co[1] = origco[(y + 1) * gridsize + x + 1];
2404  co[2] = origco[y * gridsize + x + 1];
2405  co[3] = origco[y * gridsize + x];
2406  }
2407  else {
2408  co[0] = CCG_grid_elem_co(gridkey, grid, x, y + 1);
2409  co[1] = CCG_grid_elem_co(gridkey, grid, x + 1, y + 1);
2410  co[2] = CCG_grid_elem_co(gridkey, grid, x + 1, y);
2411  co[3] = CCG_grid_elem_co(gridkey, grid, x, y);
2412  }
2413 
2415  ray_start, isect_precalc, co[0], co[1], co[2], co[3], depth)) {
2416  hit = true;
2417 
2418  if (r_face_normal) {
2419  normal_quad_v3(r_face_normal, co[0], co[1], co[2], co[3]);
2420  }
2421 
2422  if (r_active_vertex_index) {
2423  float location[3] = {0.0};
2424  madd_v3_v3v3fl(location, ray_start, ray_normal, *depth);
2425 
2426  const int x_it[4] = {0, 1, 1, 0};
2427  const int y_it[4] = {1, 1, 0, 0};
2428 
2429  for (int j = 0; j < 4; j++) {
2430  /* Always assign nearest_vertex_co in the first iteration to avoid comparison against
2431  * uninitialized values. This stores the closest vertex in the current intersecting
2432  * quad. */
2433  if (j == 0 || len_squared_v3v3(location, co[j]) <
2434  len_squared_v3v3(location, nearest_vertex_co)) {
2435  copy_v3_v3(nearest_vertex_co, co[j]);
2436 
2437  *r_active_vertex_index = gridkey->grid_area * grid_index +
2438  (y + y_it[j]) * gridkey->grid_size + (x + x_it[j]);
2439  }
2440  }
2441  }
2442  if (r_active_grid_index) {
2443  *r_active_grid_index = grid_index;
2444  }
2445  }
2446  }
2447  }
2448 
2449  if (origco) {
2450  origco += gridsize * gridsize;
2451  }
2452  }
2453 
2454  return hit;
2455 }
2456 
2458  PBVHNode *node,
2459  float (*origco)[3],
2460  bool use_origco,
2461  const float ray_start[3],
2462  const float ray_normal[3],
2463  struct IsectRayPrecalc *isect_precalc,
2464  float *depth,
2465  int *active_vertex_index,
2466  int *active_face_grid_index,
2467  float *face_normal)
2468 {
2469  bool hit = false;
2470 
2471  if (node->flag & PBVH_FullyHidden) {
2472  return false;
2473  }
2474 
2475  switch (pbvh->type) {
2476  case PBVH_FACES:
2477  hit |= pbvh_faces_node_raycast(pbvh,
2478  node,
2479  origco,
2480  ray_start,
2481  ray_normal,
2482  isect_precalc,
2483  depth,
2484  active_vertex_index,
2485  active_face_grid_index,
2486  face_normal);
2487  break;
2488  case PBVH_GRIDS:
2489  hit |= pbvh_grids_node_raycast(pbvh,
2490  node,
2491  origco,
2492  ray_start,
2493  ray_normal,
2494  isect_precalc,
2495  depth,
2496  active_vertex_index,
2497  active_face_grid_index,
2498  face_normal);
2499  break;
2500  case PBVH_BMESH:
2503  ray_start,
2504  ray_normal,
2505  isect_precalc,
2506  depth,
2507  use_origco,
2508  active_vertex_index,
2509  face_normal);
2510  break;
2511  }
2512 
2513  return hit;
2514 }
2515 
2517  PBVH *pbvh, bool original, float ray_start[3], float ray_end[3], float ray_normal[3])
2518 {
2519  if (pbvh->nodes) {
2520  float rootmin_start, rootmin_end;
2521  float bb_min_root[3], bb_max_root[3], bb_center[3], bb_diff[3];
2522  struct IsectRayAABB_Precalc ray;
2523  float ray_normal_inv[3];
2524  float offset = 1.0f + 1e-3f;
2525  const float offset_vec[3] = {1e-3f, 1e-3f, 1e-3f};
2526 
2527  if (original) {
2528  BKE_pbvh_node_get_original_BB(pbvh->nodes, bb_min_root, bb_max_root);
2529  }
2530  else {
2531  BKE_pbvh_node_get_BB(pbvh->nodes, bb_min_root, bb_max_root);
2532  }
2533 
2534  /* Slightly offset min and max in case we have a zero width node
2535  * (due to a plane mesh for instance), or faces very close to the bounding box boundary. */
2536  mid_v3_v3v3(bb_center, bb_max_root, bb_min_root);
2537  /* diff should be same for both min/max since it's calculated from center */
2538  sub_v3_v3v3(bb_diff, bb_max_root, bb_center);
2539  /* handles case of zero width bb */
2540  add_v3_v3(bb_diff, offset_vec);
2541  madd_v3_v3v3fl(bb_max_root, bb_center, bb_diff, offset);
2542  madd_v3_v3v3fl(bb_min_root, bb_center, bb_diff, -offset);
2543 
2544  /* first project start ray */
2545  isect_ray_aabb_v3_precalc(&ray, ray_start, ray_normal);
2546  if (!isect_ray_aabb_v3(&ray, bb_min_root, bb_max_root, &rootmin_start)) {
2547  return;
2548  }
2549 
2550  /* then the end ray */
2551  mul_v3_v3fl(ray_normal_inv, ray_normal, -1.0);
2552  isect_ray_aabb_v3_precalc(&ray, ray_end, ray_normal_inv);
2553  /* unlikely to fail exiting if entering succeeded, still keep this here */
2554  if (!isect_ray_aabb_v3(&ray, bb_min_root, bb_max_root, &rootmin_end)) {
2555  return;
2556  }
2557 
2558  madd_v3_v3v3fl(ray_start, ray_start, ray_normal, rootmin_start);
2559  madd_v3_v3v3fl(ray_end, ray_end, ray_normal_inv, rootmin_end);
2560  }
2561 }
2562 
2563 /* -------------------------------------------------------------------- */
2564 
2565 typedef struct {
2566  struct DistRayAABB_Precalc dist_ray_to_aabb_precalc;
2567  bool original;
2569 
2570 static bool nearest_to_ray_aabb_dist_sq(PBVHNode *node, void *data_v)
2571 {
2572  FindNearestRayData *rcd = data_v;
2573  const float *bb_min, *bb_max;
2574 
2575  if (rcd->original) {
2576  /* BKE_pbvh_node_get_original_BB */
2577  bb_min = node->orig_vb.bmin;
2578  bb_max = node->orig_vb.bmax;
2579  }
2580  else {
2581  /* BKE_pbvh_node_get_BB */
2582  bb_min = node->vb.bmin;
2583  bb_max = node->vb.bmax;
2584  }
2585 
2586  float co_dummy[3], depth;
2588  &rcd->dist_ray_to_aabb_precalc, bb_min, bb_max, co_dummy, &depth);
2589  /* Ideally we would skip distances outside the range. */
2590  return depth > 0.0f;
2591 }
2592 
2595  void *data,
2596  const float ray_start[3],
2597  const float ray_normal[3],
2598  bool original)
2599 {
2600  FindNearestRayData ncd;
2601 
2603  ncd.original = original;
2604 
2606 }
2607 
2609  const PBVHNode *node,
2610  float (*origco)[3],
2611  const float ray_start[3],
2612  const float ray_normal[3],
2613  float *depth,
2614  float *dist_sq)
2615 {
2616  const MVert *vert = pbvh->verts;
2617  const MLoop *mloop = pbvh->mloop;
2618  const int *faces = node->prim_indices;
2619  int i, totface = node->totprim;
2620  bool hit = false;
2621 
2622  for (i = 0; i < totface; i++) {
2623  const MLoopTri *lt = &pbvh->looptri[faces[i]];
2624  const int *face_verts = node->face_vert_indices[i];
2625 
2626  if (pbvh->respect_hide && paint_is_face_hidden(lt, vert, mloop)) {
2627  continue;
2628  }
2629 
2630  if (origco) {
2631  /* Intersect with backed-up original coordinates. */
2632  hit |= ray_face_nearest_tri(ray_start,
2633  ray_normal,
2634  origco[face_verts[0]],
2635  origco[face_verts[1]],
2636  origco[face_verts[2]],
2637  depth,
2638  dist_sq);
2639  }
2640  else {
2641  /* intersect with current coordinates */
2642  hit |= ray_face_nearest_tri(ray_start,
2643  ray_normal,
2644  vert[mloop[lt->tri[0]].v].co,
2645  vert[mloop[lt->tri[1]].v].co,
2646  vert[mloop[lt->tri[2]].v].co,
2647  depth,
2648  dist_sq);
2649  }
2650  }
2651 
2652  return hit;
2653 }
2654 
2656  PBVHNode *node,
2657  float (*origco)[3],
2658  const float ray_start[3],
2659  const float ray_normal[3],
2660  float *depth,
2661  float *dist_sq)
2662 {
2663  const int totgrid = node->totprim;
2664  const int gridsize = pbvh->gridkey.grid_size;
2665  bool hit = false;
2666 
2667  for (int i = 0; i < totgrid; i++) {
2668  CCGElem *grid = pbvh->grids[node->prim_indices[i]];
2669  BLI_bitmap *gh;
2670 
2671  if (!grid) {
2672  continue;
2673  }
2674 
2675  gh = pbvh->grid_hidden[node->prim_indices[i]];
2676 
2677  for (int y = 0; y < gridsize - 1; y++) {
2678  for (int x = 0; x < gridsize - 1; x++) {
2679  /* check if grid face is hidden */
2680  if (gh) {
2681  if (paint_is_grid_face_hidden(gh, gridsize, x, y)) {
2682  continue;
2683  }
2684  }
2685 
2686  if (origco) {
2687  hit |= ray_face_nearest_quad(ray_start,
2688  ray_normal,
2689  origco[y * gridsize + x],
2690  origco[y * gridsize + x + 1],
2691  origco[(y + 1) * gridsize + x + 1],
2692  origco[(y + 1) * gridsize + x],
2693  depth,
2694  dist_sq);
2695  }
2696  else {
2697  hit |= ray_face_nearest_quad(ray_start,
2698  ray_normal,
2699  CCG_grid_elem_co(&pbvh->gridkey, grid, x, y),
2700  CCG_grid_elem_co(&pbvh->gridkey, grid, x + 1, y),
2701  CCG_grid_elem_co(&pbvh->gridkey, grid, x + 1, y + 1),
2702  CCG_grid_elem_co(&pbvh->gridkey, grid, x, y + 1),
2703  depth,
2704  dist_sq);
2705  }
2706  }
2707  }
2708 
2709  if (origco) {
2710  origco += gridsize * gridsize;
2711  }
2712  }
2713 
2714  return hit;
2715 }
2716 
2718  PBVHNode *node,
2719  float (*origco)[3],
2720  bool use_origco,
2721  const float ray_start[3],
2722  const float ray_normal[3],
2723  float *depth,
2724  float *dist_sq)
2725 {
2726  bool hit = false;
2727 
2728  if (node->flag & PBVH_FullyHidden) {
2729  return false;
2730  }
2731 
2732  switch (pbvh->type) {
2733  case PBVH_FACES:
2735  pbvh, node, origco, ray_start, ray_normal, depth, dist_sq);
2736  break;
2737  case PBVH_GRIDS:
2739  pbvh, node, origco, ray_start, ray_normal, depth, dist_sq);
2740  break;
2741  case PBVH_BMESH:
2743  node, ray_start, ray_normal, depth, dist_sq, use_origco);
2744  break;
2745  }
2746 
2747  return hit;
2748 }
2749 
2750 typedef enum {
2754 } PlaneAABBIsect;
2755 
2756 /* Adapted from:
2757  * http://www.gamedev.net/community/forums/topic.asp?topic_id=512123
2758  * Returns true if the AABB is at least partially within the frustum
2759  * (ok, not a real frustum), false otherwise.
2760  */
2761 static PlaneAABBIsect test_frustum_aabb(const float bb_min[3],
2762  const float bb_max[3],
2763  PBVHFrustumPlanes *frustum)
2764 {
2766  float(*planes)[4] = frustum->planes;
2767 
2768  for (int i = 0; i < frustum->num_planes; i++) {
2769  float vmin[3], vmax[3];
2770 
2771  for (int axis = 0; axis < 3; axis++) {
2772  if (planes[i][axis] < 0) {
2773  vmin[axis] = bb_min[axis];
2774  vmax[axis] = bb_max[axis];
2775  }
2776  else {
2777  vmin[axis] = bb_max[axis];
2778  vmax[axis] = bb_min[axis];
2779  }
2780  }
2781 
2782  if (dot_v3v3(planes[i], vmin) + planes[i][3] < 0) {
2783  return ISECT_OUTSIDE;
2784  }
2785  if (dot_v3v3(planes[i], vmax) + planes[i][3] <= 0) {
2786  ret = ISECT_INTERSECT;
2787  }
2788  }
2789 
2790  return ret;
2791 }
2792 
2794 {
2795  const float *bb_min, *bb_max;
2796  /* BKE_pbvh_node_get_BB */
2797  bb_min = node->vb.bmin;
2798  bb_max = node->vb.bmax;
2799 
2800  return test_frustum_aabb(bb_min, bb_max, data) != ISECT_OUTSIDE;
2801 }
2802 
2804 {
2805  const float *bb_min, *bb_max;
2806  /* BKE_pbvh_node_get_BB */
2807  bb_min = node->vb.bmin;
2808  bb_max = node->vb.bmax;
2809 
2810  return test_frustum_aabb(bb_min, bb_max, data) != ISECT_INSIDE;
2811 }
2812 
2813 void BKE_pbvh_update_normals(PBVH *pbvh, struct SubdivCCG *subdiv_ccg)
2814 {
2815  /* Update normals */
2816  PBVHNode **nodes;
2817  int totnode;
2818 
2820  pbvh, update_search_cb, POINTER_FROM_INT(PBVH_UpdateNormals), &nodes, &totnode);
2821 
2822  if (totnode > 0) {
2823  if (pbvh->type == PBVH_BMESH) {
2824  pbvh_bmesh_normals_update(nodes, totnode);
2825  }
2826  else if (pbvh->type == PBVH_FACES) {
2827  pbvh_faces_update_normals(pbvh, nodes, totnode);
2828  }
2829  else if (pbvh->type == PBVH_GRIDS) {
2830  struct CCGFace **faces;
2831  int num_faces;
2832  BKE_pbvh_get_grid_updates(pbvh, true, (void ***)&faces, &num_faces);
2833  if (num_faces > 0) {
2834  BKE_subdiv_ccg_update_normals(subdiv_ccg, faces, num_faces);
2835  MEM_freeN(faces);
2836  }
2837  }
2838  }
2839 
2840  MEM_SAFE_FREE(nodes);
2841 }
2842 
2843 void BKE_pbvh_face_sets_color_set(PBVH *pbvh, int seed, int color_default)
2844 {
2845  pbvh->face_sets_color_seed = seed;
2846  pbvh->face_sets_color_default = color_default;
2847 }
2848 
2853 typedef struct PBVHDrawSearchData {
2857 
2858 static bool pbvh_draw_search_cb(PBVHNode *node, void *data_v)
2859 {
2860  PBVHDrawSearchData *data = data_v;
2861  if (data->frustum && !BKE_pbvh_node_frustum_contain_AABB(node, data->frustum)) {
2862  return false;
2863  }
2864 
2865  data->accum_update_flag |= node->flag;
2866  return true;
2867 }
2868 
2870  bool update_only_visible,
2871  PBVHFrustumPlanes *update_frustum,
2872  PBVHFrustumPlanes *draw_frustum,
2873  void (*draw_fn)(void *user_data, GPU_PBVH_Buffers *buffers),
2874  void *user_data,
2875  bool UNUSED(full_render))
2876 {
2877  PBVHNode **nodes;
2878  int totnode;
2879  int update_flag = 0;
2880 
2881  pbvh->draw_cache_invalid = false;
2882 
2883  /* Search for nodes that need updates. */
2884  if (update_only_visible) {
2885  /* Get visible nodes with draw updates. */
2886  PBVHDrawSearchData data = {.frustum = update_frustum, .accum_update_flag = 0};
2887  BKE_pbvh_search_gather(pbvh, pbvh_draw_search_cb, &data, &nodes, &totnode);
2888  update_flag = data.accum_update_flag;
2889  }
2890  else {
2891  /* Get all nodes with draw updates, also those outside the view. */
2892  const int search_flag = PBVH_RebuildDrawBuffers | PBVH_UpdateDrawBuffers;
2894  pbvh, update_search_cb, POINTER_FROM_INT(search_flag), &nodes, &totnode);
2896  }
2897 
2898  pbvh_check_draw_layout(pbvh);
2899 
2900  /* Update draw buffers. */
2901  if (totnode != 0 && (update_flag & (PBVH_RebuildDrawBuffers | PBVH_UpdateDrawBuffers))) {
2902  pbvh_update_draw_buffers(pbvh, nodes, totnode, update_flag);
2903  }
2904  MEM_SAFE_FREE(nodes);
2905 
2906  /* Draw visible nodes. */
2907  PBVHDrawSearchData draw_data = {.frustum = draw_frustum, .accum_update_flag = 0};
2908  BKE_pbvh_search_gather(pbvh, pbvh_draw_search_cb, &draw_data, &nodes, &totnode);
2909 
2910  for (int i = 0; i < totnode; i++) {
2911  PBVHNode *node = nodes[i];
2912  if (!(node->flag & PBVH_FullyHidden)) {
2913  draw_fn(user_data, node->draw_buffers);
2914  }
2915  }
2916 
2917  MEM_SAFE_FREE(nodes);
2918 }
2919 
2921  PBVH *pbvh,
2922  void (*draw_fn)(void *user_data, const float bmin[3], const float bmax[3], PBVHNodeFlags flag),
2923  void *user_data)
2924 {
2925  for (int a = 0; a < pbvh->totnode; a++) {
2926  PBVHNode *node = &pbvh->nodes[a];
2927 
2928  draw_fn(user_data, node->vb.bmin, node->vb.bmax, node->flag);
2929  }
2930 }
2931 
2933  PBVH *pbvh, CCGElem **grids, void **gridfaces, DMFlagMat *flagmats, BLI_bitmap **grid_hidden)
2934 {
2935  pbvh->grids = grids;
2936  pbvh->gridfaces = gridfaces;
2937 
2938  if (flagmats != pbvh->grid_flag_mats || pbvh->grid_hidden != grid_hidden) {
2939  pbvh->grid_flag_mats = flagmats;
2940  pbvh->grid_hidden = grid_hidden;
2941 
2942  for (int a = 0; a < pbvh->totnode; a++) {
2944  }
2945  }
2946 }
2947 
2949 {
2950  float(*vertCos)[3] = NULL;
2951 
2952  if (pbvh->verts) {
2953  MVert *mvert = pbvh->verts;
2954 
2955  vertCos = MEM_callocN(3 * pbvh->totvert * sizeof(float), "BKE_pbvh_get_vertCoords");
2956  float *co = (float *)vertCos;
2957 
2958  for (int a = 0; a < pbvh->totvert; a++, mvert++, co += 3) {
2959  copy_v3_v3(co, mvert->co);
2960  }
2961  }
2962 
2963  return vertCos;
2964 }
2965 
2966 void BKE_pbvh_vert_coords_apply(PBVH *pbvh, const float (*vertCos)[3], const int totvert)
2967 {
2968  if (totvert != pbvh->totvert) {
2969  BLI_assert_msg(0, "PBVH: Given deforming vcos number does not match PBVH vertex number!");
2970  return;
2971  }
2972 
2973  if (!pbvh->deformed) {
2974  if (pbvh->verts) {
2975  /* if pbvh is not already deformed, verts/faces points to the */
2976  /* original data and applying new coords to this arrays would lead to */
2977  /* unneeded deformation -- duplicate verts/faces to avoid this */
2978 
2979  pbvh->verts = MEM_dupallocN(pbvh->verts);
2980  /* No need to dupalloc pbvh->looptri, this one is 'totally owned' by pbvh,
2981  * it's never some mesh data. */
2982 
2983  pbvh->deformed = true;
2984  }
2985  }
2986 
2987  if (pbvh->verts) {
2988  MVert *mvert = pbvh->verts;
2989  /* copy new verts coords */
2990  for (int a = 0; a < pbvh->totvert; a++, mvert++) {
2991  /* no need for float comparison here (memory is exactly equal or not) */
2992  if (memcmp(mvert->co, vertCos[a], sizeof(float[3])) != 0) {
2993  copy_v3_v3(mvert->co, vertCos[a]);
2995  }
2996  }
2997 
2998  /* coordinates are new -- normals should also be updated */
3000  pbvh->verts, pbvh->totvert, pbvh->mloop, pbvh->looptri, pbvh->totprim, NULL);
3001 
3002  for (int a = 0; a < pbvh->totnode; a++) {
3004  }
3005 
3007  }
3008 }
3009 
3011 {
3012  return pbvh->deformed;
3013 }
3014 /* Proxies */
3015 
3017 {
3018  int index, totverts;
3019 
3020  index = node->proxy_count;
3021 
3022  node->proxy_count++;
3023 
3024  if (node->proxies) {
3025  node->proxies = MEM_reallocN(node->proxies, node->proxy_count * sizeof(PBVHProxyNode));
3026  }
3027  else {
3028  node->proxies = MEM_mallocN(sizeof(PBVHProxyNode), "PBVHNodeProxy");
3029  }
3030 
3031  BKE_pbvh_node_num_verts(pbvh, node, &totverts, NULL);
3032  node->proxies[index].co = MEM_callocN(sizeof(float[3]) * totverts, "PBVHNodeProxy.co");
3033 
3034  return node->proxies + index;
3035 }
3036 
3038 {
3039  for (int p = 0; p < node->proxy_count; p++) {
3040  MEM_freeN(node->proxies[p].co);
3041  node->proxies[p].co = NULL;
3042  }
3043 
3044  MEM_freeN(node->proxies);
3045  node->proxies = NULL;
3046 
3047  node->proxy_count = 0;
3048 }
3049 
3050 void BKE_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***r_array, int *r_tot)
3051 {
3052  PBVHNode **array = NULL;
3053  int tot = 0, space = 0;
3054 
3055  for (int n = 0; n < pbvh->totnode; n++) {
3056  PBVHNode *node = pbvh->nodes + n;
3057 
3058  if (node->proxy_count > 0) {
3059  if (tot == space) {
3060  /* resize array if needed */
3061  space = (tot == 0) ? 32 : space * 2;
3062  array = MEM_recallocN_id(array, sizeof(PBVHNode *) * space, __func__);
3063  }
3064 
3065  array[tot] = node;
3066  tot++;
3067  }
3068  }
3069 
3070  if (tot == 0 && array) {
3071  MEM_freeN(array);
3072  array = NULL;
3073  }
3074 
3075  *r_array = array;
3076  *r_tot = tot;
3077 }
3078 
3080 {
3081 
3082  if (!node->color_buffer.color) {
3083  node->color_buffer.color = MEM_callocN(sizeof(float[4]) * node->uniq_verts, "Color buffer");
3084  }
3085  return &node->color_buffer;
3086 }
3087 
3089 {
3090  PBVHNode **nodes;
3091  int totnode;
3092  BKE_pbvh_search_gather(pbvh, NULL, NULL, &nodes, &totnode);
3093  for (int i = 0; i < totnode; i++) {
3094  MEM_SAFE_FREE(nodes[i]->color_buffer.color);
3095  }
3096  MEM_SAFE_FREE(nodes);
3097 }
3098 
3100 {
3101  struct CCGElem **grids;
3102  struct MVert *verts;
3103  const int *vert_indices;
3104  int *grid_indices;
3105  int totgrid, gridsize, uniq_verts, totvert;
3106 
3107  vi->grid = NULL;
3108  vi->no = NULL;
3109  vi->fno = NULL;
3110  vi->mvert = NULL;
3111 
3112  vi->respect_hide = pbvh->respect_hide;
3113  if (pbvh->respect_hide == false) {
3114  /* The same value for all vertices. */
3115  vi->visible = true;
3116  }
3117 
3118  BKE_pbvh_node_get_grids(pbvh, node, &grid_indices, &totgrid, NULL, &gridsize, &grids);
3119  BKE_pbvh_node_num_verts(pbvh, node, &uniq_verts, &totvert);
3120  BKE_pbvh_node_get_verts(pbvh, node, &vert_indices, &verts);
3121  vi->key = pbvh->gridkey;
3122 
3123  vi->grids = grids;
3124  vi->grid_indices = grid_indices;
3125  vi->totgrid = (grids) ? totgrid : 1;
3126  vi->gridsize = gridsize;
3127 
3128  if (mode == PBVH_ITER_ALL) {
3129  vi->totvert = totvert;
3130  }
3131  else {
3132  vi->totvert = uniq_verts;
3133  }
3134  vi->vert_indices = vert_indices;
3135  vi->mverts = verts;
3136 
3137  if (pbvh->type == PBVH_BMESH) {
3138  BLI_gsetIterator_init(&vi->bm_unique_verts, node->bm_unique_verts);
3139  BLI_gsetIterator_init(&vi->bm_other_verts, node->bm_other_verts);
3140  vi->bm_vdata = &pbvh->bm->vdata;
3142  }
3143 
3144  vi->gh = NULL;
3145  if (vi->grids && mode == PBVH_ITER_UNIQUE) {
3146  vi->grid_hidden = pbvh->grid_hidden;
3147  }
3148 
3149  vi->mask = NULL;
3150  if (pbvh->type == PBVH_FACES) {
3151  vi->vert_normals = pbvh->vert_normals;
3152 
3154  }
3155 }
3156 
3157 bool pbvh_has_mask(const PBVH *pbvh)
3158 {
3159  switch (pbvh->type) {
3160  case PBVH_GRIDS:
3161  return (pbvh->gridkey.has_mask != 0);
3162  case PBVH_FACES:
3163  return (pbvh->vdata && CustomData_get_layer(pbvh->vdata, CD_PAINT_MASK));
3164  case PBVH_BMESH:
3165  return (pbvh->bm && (CustomData_get_offset(&pbvh->bm->vdata, CD_PAINT_MASK) != -1));
3166  }
3167 
3168  return false;
3169 }
3170 
3172 {
3173  switch (pbvh->type) {
3174  case PBVH_GRIDS:
3175  return (pbvh->pdata && CustomData_get_layer(pbvh->pdata, CD_SCULPT_FACE_SETS));
3176  case PBVH_FACES:
3177  return (pbvh->pdata && CustomData_get_layer(pbvh->pdata, CD_SCULPT_FACE_SETS));
3178  case PBVH_BMESH:
3179  return false;
3180  }
3181 
3182  return false;
3183 }
3184 
3185 void pbvh_show_mask_set(PBVH *pbvh, bool show_mask)
3186 {
3187  pbvh->show_mask = show_mask;
3188 }
3189 
3190 void pbvh_show_face_sets_set(PBVH *pbvh, bool show_face_sets)
3191 {
3192  pbvh->show_face_sets = show_face_sets;
3193 }
3194 
3196 {
3197  pbvh->num_planes = planes->num_planes;
3198  for (int i = 0; i < pbvh->num_planes; i++) {
3199  copy_v4_v4(pbvh->planes[i], planes->planes[i]);
3200  }
3201 }
3202 
3204 {
3205  planes->num_planes = pbvh->num_planes;
3206  for (int i = 0; i < planes->num_planes; i++) {
3207  copy_v4_v4(planes->planes[i], pbvh->planes[i]);
3208  }
3209 }
3210 
3212  bool use_threading,
3213  int totnode)
3214 {
3215  memset(settings, 0, sizeof(*settings));
3216  settings->use_threading = use_threading && totnode > 1;
3217 }
3218 
3220 {
3221  BLI_assert(pbvh->type == PBVH_FACES);
3222  return pbvh->verts;
3223 }
3224 
3225 const float (*BKE_pbvh_get_vert_normals(const PBVH *pbvh))[3]
3226 {
3227  BLI_assert(pbvh->type == PBVH_FACES);
3228  return pbvh->vert_normals;
3229 }
3230 
3231 void BKE_pbvh_subdiv_cgg_set(PBVH *pbvh, SubdivCCG *subdiv_ccg)
3232 {
3233  pbvh->subdiv_ccg = subdiv_ccg;
3234 }
3235 
3236 void BKE_pbvh_face_sets_set(PBVH *pbvh, int *face_sets)
3237 {
3238  pbvh->face_sets = face_sets;
3239 }
3240 
3241 void BKE_pbvh_respect_hide_set(PBVH *pbvh, bool respect_hide)
3242 {
3243  pbvh->respect_hide = respect_hide;
3244 }
3245 bool BKE_pbvh_is_drawing(const PBVH *pbvh)
3246 {
3247  return pbvh->is_drawing;
3248 }
3249 
3251 {
3252  return pbvh->draw_cache_invalid;
3253 }
3254 
3255 void BKE_pbvh_is_drawing_set(PBVH *pbvh, bool val)
3256 {
3257  pbvh->is_drawing = val;
3258 }
3259 
3260 void BKE_pbvh_node_num_loops(PBVH *pbvh, PBVHNode *node, int *r_totloop)
3261 {
3262  UNUSED_VARS(pbvh);
3264 
3265  if (r_totloop) {
3266  *r_totloop = node->loop_indices_num;
3267  }
3268 }
3269 
3271 {
3273 }
3274 
3275 void BKE_pbvh_pmap_set(PBVH *pbvh, const MeshElemMap *pmap)
3276 {
3277  pbvh->pmap = pmap;
3278 }
3279 
3281 {
3283 
3284  int totloop = 0;
3285 
3286  /* Check if nodes already have loop indices. */
3287  for (int i = 0; i < pbvh->totnode; i++) {
3288  PBVHNode *node = pbvh->nodes + i;
3289 
3290  if (!(node->flag & PBVH_Leaf)) {
3291  continue;
3292  }
3293 
3294  if (node->loop_indices) {
3295  return;
3296  }
3297 
3298  totloop += node->totprim * 3;
3299  }
3300 
3301  BLI_bitmap *visit = BLI_BITMAP_NEW(totloop, __func__);
3302 
3303  /* Create loop indices from node loop triangles. */
3304  for (int i = 0; i < pbvh->totnode; i++) {
3305  PBVHNode *node = pbvh->nodes + i;
3306 
3307  if (!(node->flag & PBVH_Leaf)) {
3308  continue;
3309  }
3310 
3311  node->loop_indices = MEM_malloc_arrayN(node->totprim * 3, sizeof(int), __func__);
3312  node->loop_indices_num = 0;
3313 
3314  for (int j = 0; j < node->totprim; j++) {
3315  const MLoopTri *mlt = pbvh->looptri + node->prim_indices[j];
3316 
3317  for (int k = 0; k < 3; k++) {
3318  if (!BLI_BITMAP_TEST(visit, mlt->tri[k])) {
3319  node->loop_indices[node->loop_indices_num++] = mlt->tri[k];
3320  BLI_BITMAP_ENABLE(visit, mlt->tri[k]);
3321  }
3322  }
3323  }
3324  }
3325 
3326  MEM_SAFE_FREE(visit);
3327 }
typedef float(TangentPoint)[2]
Generic geometry attributes built on CustomData.
eAttrDomain
Definition: BKE_attribute.h:25
@ ATTR_DOMAIN_POINT
Definition: BKE_attribute.h:27
@ ATTR_DOMAIN_CORNER
Definition: BKE_attribute.h:30
struct CustomDataLayer * BKE_id_attributes_active_color_get(const struct ID *id)
eAttrDomain BKE_id_attribute_domain(const struct ID *id, const struct CustomDataLayer *layer)
#define ATTR_DOMAIN_NUM
Definition: BKE_attribute.h:34
BLI_INLINE float * CCG_grid_elem_co(const CCGKey *key, CCGElem *elem, int x, int y)
Definition: BKE_ccg.h:114
struct CCGElem CCGElem
Definition: BKE_ccg.h:30
BLI_INLINE float * CCG_elem_offset_co(const CCGKey *key, CCGElem *elem, int offset)
Definition: BKE_ccg.h:129
void * CustomData_get_layer(const struct CustomData *data, int type)
int CustomData_get_offset(const struct CustomData *data, int type)
float(* BKE_mesh_vertex_normals_for_write(struct Mesh *mesh))[3]
const float(* BKE_mesh_vertex_normals_ensure(const struct Mesh *mesh))[3]
void BKE_mesh_calc_normals_looptri(struct MVert *mverts, int numVerts, const struct MLoop *mloop, const struct MLoopTri *looptri, int looptri_num, float(*r_tri_nors)[3])
void BKE_mesh_calc_poly_normal(const struct MPoly *mpoly, const struct MLoop *loopstart, const struct MVert *mvarray, float r_no[3])
bool paint_is_face_hidden(const struct MLoopTri *lt, const struct MVert *mvert, const struct MLoop *mloop)
bool paint_is_grid_face_hidden(const unsigned int *grid_hidden, int gridsize, int x, int y)
Definition: paint.c:1253
A BVH for high poly meshes.
#define BKE_pbvh_vertex_iter_begin(pbvh, node, vi, mode)
Definition: BKE_pbvh.h:439
#define PBVH_ITER_ALL
Definition: BKE_pbvh.h:390
void(* BKE_pbvh_HitCallback)(PBVHNode *node, void *data)
Definition: BKE_pbvh.h:100
#define BKE_pbvh_vertex_iter_end
Definition: BKE_pbvh.h:509
#define PBVH_ITER_UNIQUE
Definition: BKE_pbvh.h:391
struct GSet * BKE_pbvh_bmesh_node_other_verts(PBVHNode *node)
Definition: pbvh_bmesh.c:2108
PBVHType
Definition: BKE_pbvh.h:233
@ PBVH_GRIDS
Definition: BKE_pbvh.h:235
@ PBVH_BMESH
Definition: BKE_pbvh.h:236
@ PBVH_FACES
Definition: BKE_pbvh.h:234
void(* BKE_pbvh_HitOccludedCallback)(PBVHNode *node, void *data, float *tmin)
Definition: BKE_pbvh.h:101
struct GSet * BKE_pbvh_bmesh_node_unique_verts(PBVHNode *node)
Definition: pbvh_bmesh.c:2103
void(* BKE_pbvh_SearchNearestCallback)(PBVHNode *node, void *data, float *tmin)
Definition: BKE_pbvh.h:103
PBVHNodeFlags
Definition: BKE_pbvh.h:63
@ PBVH_RebuildPixels
Definition: BKE_pbvh.h:81
@ PBVH_FullyMasked
Definition: BKE_pbvh.h:76
@ PBVH_UpdateDrawBuffers
Definition: BKE_pbvh.h:69
@ PBVH_RebuildDrawBuffers
Definition: BKE_pbvh.h:74
@ PBVH_UpdateVisibility
Definition: BKE_pbvh.h:72
@ PBVH_UpdateMask
Definition: BKE_pbvh.h:71
@ PBVH_UpdateColor
Definition: BKE_pbvh.h:80
@ PBVH_UpdateNormals
Definition: BKE_pbvh.h:66
@ PBVH_FullyHidden
Definition: BKE_pbvh.h:75
@ PBVH_UpdateBB
Definition: BKE_pbvh.h:67
@ PBVH_Leaf
Definition: BKE_pbvh.h:64
@ PBVH_UpdateOriginalBB
Definition: BKE_pbvh.h:68
@ PBVH_UpdateRedraw
Definition: BKE_pbvh.h:70
@ PBVH_FullyUnmasked
Definition: BKE_pbvh.h:77
bool(* BKE_pbvh_SearchCallback)(PBVHNode *node, void *data)
Definition: BKE_pbvh.h:98
void BKE_subdiv_ccg_update_normals(SubdivCCG *subdiv_ccg, struct CCGFace **effected_faces, int num_effected_faces)
Definition: subdiv_ccg.c:870
int BKE_subdiv_ccg_grid_to_face_index(const SubdivCCG *subdiv_ccg, int grid_index)
Definition: subdiv_ccg.c:1940
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_assert_msg(a, msg)
Definition: BLI_assert.h:53
#define BLI_BITMAP_NEW(_num, _alloc_string)
Definition: BLI_bitmap.h:40
#define BLI_BITMAP_TEST(_bitmap, _index)
Definition: BLI_bitmap.h:64
#define BLI_BITMAP_ENABLE(_bitmap, _index)
Definition: BLI_bitmap.h:81
#define BLI_BITMAP_SET(_bitmap, _index, _set)
Definition: BLI_bitmap.h:102
unsigned int BLI_bitmap
Definition: BLI_bitmap.h:16
#define GSET_ITER_INDEX(gs_iter_, gset_, i_)
Definition: BLI_ghash.h:475
struct GSet GSet
Definition: BLI_ghash.h:340
BLI_INLINE void * BLI_ghashIterator_getKey(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.h:298
GHash * BLI_ghash_int_new_ex(const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
BLI_INLINE void * BLI_ghashIterator_getValue(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.h:302
#define GHASH_ITER(gh_iter_, ghash_)
Definition: BLI_ghash.h:321
GSet * BLI_gset_ptr_new(const char *info)
unsigned int BLI_gset_len(const GSet *gs) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:957
#define GSET_ITER(gs_iter_, gset_)
Definition: BLI_ghash.h:471
BLI_INLINE void BLI_gsetIterator_init(GSetIterator *gsi, GSet *gs)
Definition: BLI_ghash.h:450
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition: BLI_ghash.c:863
void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp)
Definition: BLI_ghash.c:1037
BLI_INLINE void * BLI_gsetIterator_getKey(GSetIterator *gsi)
Definition: BLI_ghash.h:458
bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:755
bool BLI_gset_add(GSet *gs, void *key)
Definition: BLI_ghash.c:969
void BLI_kdtree_nd_() free(KDTree *tree)
Definition: kdtree_impl.h:102
MINLINE float max_ff(float a, float b)
MINLINE float min_ff(float a, float b)
MINLINE int max_ii(int a, int b)
float normal_quad_v3(float n[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition: math_geom.c:50
bool isect_ray_aabb_v3(const struct IsectRayAABB_Precalc *data, const float bb_min[3], const float bb_max[3], float *tmin)
Definition: math_geom.c:3072
void dist_squared_ray_to_aabb_v3_precalc(struct DistRayAABB_Precalc *neasrest_precalc, const float ray_origin[3], const float ray_direction[3])
Definition: math_geom.c:651
bool isect_ray_tri_watertight_v3(const float ray_origin[3], const struct IsectRayPrecalc *isect_precalc, const float v0[3], const float v1[3], const float v2[3], float *r_dist, float r_uv[2])
Definition: math_geom.c:1811
void isect_ray_aabb_v3_precalc(struct IsectRayAABB_Precalc *data, const float ray_origin[3], const float ray_direction[3])
Definition: math_geom.c:3057
float dist_squared_ray_to_seg_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], float r_point[3], float *r_depth)
Definition: math_geom.c:579
float dist_squared_ray_to_aabb_v3(const struct DistRayAABB_Precalc *data, const float bb_min[3], const float bb_max[3], float r_point[3], float *r_depth)
Definition: math_geom.c:665
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:33
MINLINE void copy_v4_v4(float r[4], const float a[4])
MINLINE float normalize_v3(float r[3])
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
Definition: math_vector.c:237
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
MINLINE void zero_v3(float r[3])
MINLINE void mul_v3_v3fl(float r[3], const float a[3], float f)
MINLINE void add_v3_v3(float r[3], const float a[3])
Random number functions.
unsigned int uint
Definition: BLI_sys_types.h:67
void BLI_task_parallel_range(int start, int stop, void *userdata, TaskParallelRangeFunc func, const TaskParallelSettings *settings)
Definition: task_range.cc:94
#define UNUSED_VARS(...)
#define SWAP(type, a, b)
#define POINTER_FROM_INT(i)
#define UNUSED(x)
#define POINTER_AS_INT(i)
#define UNLIKELY(x)
#define ELEM(...)
@ CD_PROP_BYTE_COLOR
@ CD_PAINT_MASK
@ CD_PROP_COLOR
@ CD_SCULPT_FACE_SETS
@ ME_HIDE
@ ME_SMOOTH
GPU_PBVH_Buffers * GPU_pbvh_mesh_buffers_build(const struct MPoly *mpoly, const struct MLoop *mloop, const struct MLoopTri *looptri, const struct MVert *mvert, const int *face_indices, const int *sculpt_face_sets, int face_indices_len, const struct Mesh *mesh)
void GPU_pbvh_buffers_free(GPU_PBVH_Buffers *buffers)
Definition: gpu_buffers.c:1471
void GPU_pbvh_bmesh_buffers_update(PBVHGPUFormat *vbo_id, struct GPU_PBVH_Buffers *buffers, struct BMesh *bm, struct GSet *bm_faces, struct GSet *bm_unique_verts, struct GSet *bm_other_verts, const int update_flags)
Definition: gpu_buffers.c:999
void GPU_pbvh_bmesh_buffers_update_free(GPU_PBVH_Buffers *buffers)
Definition: gpu_buffers.c:984
void GPU_pbvh_free_format(PBVHGPUFormat *vbo_id)
Definition: gpu_buffers.c:113
@ GPU_PBVH_BUFFERS_SHOW_MASK
Definition: GPU_buffers.h:82
@ GPU_PBVH_BUFFERS_SHOW_VCOL
Definition: GPU_buffers.h:83
@ GPU_PBVH_BUFFERS_SHOW_SCULPT_FACE_SETS
Definition: GPU_buffers.h:84
void GPU_pbvh_mesh_buffers_update(PBVHGPUFormat *vbo_id, GPU_PBVH_Buffers *buffers, const struct MVert *mvert, const CustomData *vdata, const CustomData *ldata, const float *vmask, const int *sculpt_face_sets, const int face_sets_color_seed, const int face_sets_color_default, const int update_flags, const float(*vert_normals)[3])
void GPU_pbvh_grid_buffers_update(PBVHGPUFormat *vbo_id, GPU_PBVH_Buffers *buffers, struct SubdivCCG *subdiv_ccg, struct CCGElem **grids, const struct DMFlagMat *grid_flag_mats, int *grid_indices, int totgrid, const int *sculpt_face_sets, int face_sets_color_seed, int face_sets_color_default, const struct CCGKey *key, int update_flags)
Definition: gpu_buffers.c:706
void GPU_pbvh_buffers_update_flush(GPU_PBVH_Buffers *buffers)
Definition: gpu_buffers.c:1457
GPU_PBVH_Buffers * GPU_pbvh_grid_buffers_build(int totgrid, unsigned int **grid_hidden, bool smooth)
Definition: gpu_buffers.c:884
GPU_PBVH_Buffers * GPU_pbvh_bmesh_buffers_build(bool smooth_shading)
Definition: gpu_buffers.c:1169
bool GPU_pbvh_attribute_names_update(PBVHType pbvh_type, PBVHGPUFormat *vbo_id, const struct CustomData *vdata, const struct CustomData *ldata, bool active_attrs_only)
void GPU_pbvh_grid_buffers_update_free(GPU_PBVH_Buffers *buffers, const struct DMFlagMat *grid_flag_mats, const int *grid_indices)
Definition: gpu_buffers.c:686
PBVHGPUFormat * GPU_pbvh_make_format(void)
Definition: gpu_buffers.c:104
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint y
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
#define MEM_recallocN(vmemh, len)
#define MEM_SAFE_FREE(v)
#define MEM_reallocN(vmemh, len)
Platform independent time functions.
Provides wrapper around system-specific atomic primitives, and some extensions (faked-atomic operatio...
ATOMIC_INLINE float atomic_add_and_fetch_fl(float *p, const float x)
@ BM_VERT
Definition: bmesh_class.h:383
@ BM_ELEM_HIDDEN
Definition: bmesh_class.h:472
#define BM_elem_flag_test(ele, hflag)
Definition: bmesh_inline.h:12
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
Definition: bmesh_mesh.cc:446
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert * v
static unsigned long seed
Definition: btSoftBody.h:39
OperationNode * node
void * user_data
void * tree
static float verts[][3]
#define UINT_MAX
Definition: hash_md5.c:43
int count
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
ccl_gpu_kernel_postfix int ccl_global int * indices
void *(* MEM_malloc_arrayN)(size_t len, size_t size, const char *str)
Definition: mallocn.c:34
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_dupallocN)(const void *vmemh)
Definition: mallocn.c:28
void *(* MEM_calloc_arrayN)(size_t len, size_t size, const char *str)
Definition: mallocn.c:32
void *(* MEM_recallocN_id)(void *vmemh, size_t len, const char *str)
Definition: mallocn.c:30
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static char faces[256]
static void clear(Message *msg)
Definition: msgfmt.c:278
static unsigned a[3]
Definition: RandGen.cpp:78
static const pxr::TfToken g("g", pxr::TfToken::Immortal)
static void update(bNodeTree *ntree)
SocketIndexByIdentifierMap * map
smooth(Type::FLOAT, "mask_weight")
static PlaneAABBIsect test_frustum_aabb(const float bb_min[3], const float bb_max[3], PBVHFrustumPlanes *frustum)
Definition: pbvh.c:2761
bool BKE_pbvh_node_fully_masked_get(PBVHNode *node)
Definition: pbvh.c:1945
static float dist_squared_ray_to_tri_v3_fast(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], const float v2[3], float r_point[3], float *r_depth)
Definition: pbvh.c:2224
static void pbvh_build(PBVH *pbvh, BB *cb, BBC *prim_bbc, int totprim)
Definition: pbvh.c:517
bool ray_face_nearest_tri(const float ray_start[3], const float ray_normal[3], const float t0[3], const float t1[3], const float t2[3], float *depth, float *dist_sq)
Definition: pbvh.c:2274
int BKE_pbvh_get_grid_num_faces(const PBVH *pbvh)
Definition: pbvh.c:1855
void BKE_pbvh_node_free_proxies(PBVHNode *node)
Definition: pbvh.c:3037
void BKE_pbvh_set_frustum_planes(PBVH *pbvh, PBVHFrustumPlanes *planes)
Definition: pbvh.c:3195
static void pbvh_iter_end(PBVHIter *iter)
Definition: pbvh.c:741
static void build_mesh_leaf_node(PBVH *pbvh, PBVHNode *node)
Definition: pbvh.c:264
void BKE_pbvh_node_mark_update(PBVHNode *node)
Definition: pbvh.c:1869
BLI_bitmap ** BKE_pbvh_get_grid_visibility(const PBVH *pbvh)
Definition: pbvh.c:1843
void BKE_pbvh_node_get_bm_orco_data(PBVHNode *node, int(**r_orco_tris)[3], int *r_orco_tris_num, float(**r_orco_coords)[3])
Definition: pbvh.c:2116
void BKE_pbvh_build_grids(PBVH *pbvh, CCGElem **grids, int totgrid, CCGKey *key, void **gridfaces, DMFlagMat *flagmats, BLI_bitmap **grid_hidden)
Definition: pbvh.c:608
static void node_tree_insert(node_tree *tree, node_tree *new_node)
Definition: pbvh.c:898
void BKE_pbvh_sync_face_sets_to_grids(PBVH *pbvh)
Definition: pbvh.c:371
static bool grid_materials_match(const DMFlagMat *f1, const DMFlagMat *f2)
Definition: pbvh.c:153
void BKE_pbvh_node_fully_masked_set(PBVHNode *node, int fully_masked)
Definition: pbvh.c:1933
static int partition_indices(int *prim_indices, int lo, int hi, int axis, float mid, BBC *prim_bbc)
Definition: pbvh.c:160
struct PBVHUpdateData PBVHUpdateData
void BKE_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
Definition: pbvh.c:2090
void BKE_pbvh_is_drawing_set(PBVH *pbvh, bool val)
Definition: pbvh.c:3255
void BKE_pbvh_subdiv_cgg_set(PBVH *pbvh, SubdivCCG *subdiv_ccg)
Definition: pbvh.c:3231
void BKE_pbvh_node_mark_update_visibility(PBVHNode *node)
Definition: pbvh.c:1895
struct CCGElem ** BKE_pbvh_get_grids(const PBVH *pbvh)
Definition: pbvh.c:1837
void BKE_pbvh_node_mark_update_color(PBVHNode *node)
Definition: pbvh.c:1880
static void BKE_pbvh_search_callback_occluded(PBVH *pbvh, BKE_pbvh_SearchCallback scb, void *search_data, BKE_pbvh_HitOccludedCallback hcb, void *hit_data)
Definition: pbvh.c:954
void BKE_pbvh_vert_coords_apply(PBVH *pbvh, const float(*vertCos)[3], const int totvert)
Definition: pbvh.c:2966
void BKE_pbvh_get_frustum_planes(PBVH *pbvh, PBVHFrustumPlanes *planes)
Definition: pbvh.c:3203
static PBVHNode * pbvh_iter_next(PBVHIter *iter)
Definition: pbvh.c:766
void BKE_pbvh_raycast_project_ray_root(PBVH *pbvh, bool original, float ray_start[3], float ray_end[3], float ray_normal[3])
Definition: pbvh.c:2516
void BKE_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***r_array, int *r_tot)
Definition: pbvh.c:3050
void BKE_pbvh_redraw_BB(PBVH *pbvh, float bb_min[3], float bb_max[3])
Definition: pbvh.c:1729
void BKE_pbvh_node_num_verts(PBVH *pbvh, PBVHNode *node, int *r_uniquevert, int *r_totvert)
Definition: pbvh.c:2003
void BKE_pbvh_node_get_loops(PBVH *pbvh, PBVHNode *node, const int **r_loop_indices, const MLoop **r_loops)
Definition: pbvh.c:1973
void BKE_pbvh_build_mesh(PBVH *pbvh, Mesh *mesh, const MPoly *mpoly, const MLoop *mloop, MVert *verts, int totvert, struct CustomData *vdata, struct CustomData *ldata, struct CustomData *pdata, const MLoopTri *looptri, int looptri_num)
Definition: pbvh.c:542
void BB_expand_with_bb(BB *bb, BB *bb2)
Definition: pbvh.c:77
static void pbvh_update_draw_buffer_cb(void *__restrict userdata, const int n, const TaskParallelTLS *__restrict UNUSED(tls))
Definition: pbvh.c:1295
struct node_tree node_tree
void BKE_pbvh_node_fully_unmasked_set(PBVHNode *node, int fully_masked)
Definition: pbvh.c:1950
void BKE_pbvh_update_bounds(PBVH *pbvh, int flag)
Definition: pbvh.c:1545
PlaneAABBIsect
Definition: pbvh.c:2750
@ ISECT_INTERSECT
Definition: pbvh.c:2753
@ ISECT_INSIDE
Definition: pbvh.c:2751
@ ISECT_OUTSIDE
Definition: pbvh.c:2752
void BKE_pbvh_draw_debug_cb(PBVH *pbvh, void(*draw_fn)(void *user_data, const float bmin[3], const float bmax[3], PBVHNodeFlags flag), void *user_data)
Definition: pbvh.c:2920
static void update_vb(PBVH *pbvh, PBVHNode *node, BBC *prim_bbc, int offset, int count)
Definition: pbvh.c:330
static void build_sub(PBVH *pbvh, int node_index, BB *cb, BBC *prim_bbc, int offset, int count)
Definition: pbvh.c:462
static void pbvh_faces_update_normals(PBVH *pbvh, PBVHNode **nodes, int totnode)
Definition: pbvh.c:1113
void BKE_pbvh_update_visibility(PBVH *pbvh)
Definition: pbvh.c:1711
static void pbvh_iter_begin(PBVHIter *iter, PBVH *pbvh, BKE_pbvh_SearchCallback scb, void *search_data)
Definition: pbvh.c:724
void BKE_pbvh_get_grid_updates(PBVH *pbvh, bool clear, void ***r_gridfaces, int *r_totface)
Definition: pbvh.c:1751
MVert * BKE_pbvh_get_verts(const PBVH *pbvh)
Definition: pbvh.c:3219
void pbvh_show_mask_set(PBVH *pbvh, bool show_mask)
Definition: pbvh.c:3185
static int pbvh_flush_bb(PBVH *pbvh, PBVHNode *node, int flag)
Definition: pbvh.c:1513
static bool ray_aabb_intersect(PBVHNode *node, void *data_v)
Definition: pbvh.c:2150
static int pbvh_get_buffers_update_flags(PBVH *UNUSED(pbvh))
Definition: pbvh.c:1264
static bool nearest_to_ray_aabb_dist_sq(PBVHNode *node, void *data_v)
Definition: pbvh.c:2570
void BKE_pbvh_free(PBVH *pbvh)
Definition: pbvh.c:663
int BB_widest_axis(const BB *bb)
Definition: pbvh.c:85
void BKE_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3])
Definition: pbvh.c:2084
static bool leaf_needs_material_split(PBVH *pbvh, int offset, int count)
Definition: pbvh.c:419
void BKE_pbvh_node_color_buffer_free(PBVH *pbvh)
Definition: pbvh.c:3088
static bool pbvh_grids_node_nearest_to_ray(PBVH *pbvh, PBVHNode *node, float(*origco)[3], const float ray_start[3], const float ray_normal[3], float *depth, float *dist_sq)
Definition: pbvh.c:2655
PBVHType BKE_pbvh_type(const PBVH *pbvh)
Definition: pbvh.c:1798
static void pbvh_update_visibility_redraw_task_cb(void *__restrict userdata, const int n, const TaskParallelTLS *__restrict UNUSED(tls))
Definition: pbvh.c:1189
void pbvh_show_face_sets_set(PBVH *pbvh, bool show_face_sets)
Definition: pbvh.c:3190
bool ray_face_nearest_quad(const float ray_start[3], const float ray_normal[3], const float t0[3], const float t1[3], const float t2[3], const float t3[3], float *depth, float *dist_sq)
Definition: pbvh.c:2247
static bool pbvh_grids_node_raycast(PBVH *pbvh, PBVHNode *node, float(*origco)[3], const float ray_start[3], const float ray_normal[3], struct IsectRayPrecalc *isect_precalc, float *depth, int *r_active_vertex_index, int *r_active_grid_index, float *r_face_normal)
Definition: pbvh.c:2363
float BKE_pbvh_node_get_tmin(PBVHNode *node)
Definition: pbvh.c:949
bool BKE_pbvh_is_drawing(const PBVH *pbvh)
Definition: pbvh.c:3245
void BKE_pbvh_draw_cb(PBVH *pbvh, bool update_only_visible, PBVHFrustumPlanes *update_frustum, PBVHFrustumPlanes *draw_frustum, void(*draw_fn)(void *user_data, GPU_PBVH_Buffers *buffers), void *user_data, bool UNUSED(full_render))
Definition: pbvh.c:2869
void BKE_pbvh_mark_rebuild_pixels(PBVH *pbvh)
Definition: pbvh.c:1885
static bool pbvh_draw_search_cb(PBVHNode *node, void *data_v)
Definition: pbvh.c:2858
void pbvh_grow_nodes(PBVH *pbvh, int totnode)
Definition: pbvh.c:224
void pbvh_update_BB_redraw(PBVH *pbvh, PBVHNode **nodes, int totnode, int flag)
Definition: pbvh.c:1250
bool BKE_pbvh_node_has_vert_with_normal_update_tag(PBVH *pbvh, PBVHNode *node)
Definition: pbvh.c:2126
static void pbvh_update_visibility(PBVH *pbvh, PBVHNode **nodes, int totnode)
Definition: pbvh.c:1699
bool ray_face_intersection_tri(const float ray_start[3], struct IsectRayPrecalc *isect_precalc, const float t0[3], const float t1[3], const float t2[3], float *depth)
Definition: pbvh.c:2205
void BKE_pbvh_node_mark_rebuild_draw(PBVHNode *node)
Definition: pbvh.c:1901
static void pbvh_update_visibility_redraw(PBVH *pbvh, PBVHNode **nodes, int totnode, int flag)
Definition: pbvh.c:1213
struct PBVHIter PBVHIter
static void pbvh_update_normals_clear_task_cb(void *__restrict userdata, const int n, const TaskParallelTLS *__restrict UNUSED(tls))
Definition: pbvh.c:1014
bool BKE_pbvh_node_raycast(PBVH *pbvh, PBVHNode *node, float(*origco)[3], bool use_origco, const float ray_start[3], const float ray_normal[3], struct IsectRayPrecalc *isect_precalc, float *depth, int *active_vertex_index, int *active_face_grid_index, float *face_normal)
Definition: pbvh.c:2457
void BKE_pbvh_node_mark_normals_update(PBVHNode *node)
Definition: pbvh.c:1911
void BKE_pbvh_face_sets_color_set(PBVH *pbvh, int seed, int color_default)
Definition: pbvh.c:2843
void BKE_pbvh_raycast(PBVH *pbvh, BKE_pbvh_HitOccludedCallback cb, void *data, const float ray_start[3], const float ray_normal[3], bool original)
Definition: pbvh.c:2169
void BKE_pbvh_update_vertex_data(PBVH *pbvh, int flag)
Definition: pbvh.c:1567
void BKE_pbvh_vert_tag_update_normal(PBVH *pbvh, int index)
Definition: pbvh.c:1967
bool ray_face_intersection_quad(const float ray_start[3], struct IsectRayPrecalc *isect_precalc, const float t0[3], const float t1[3], const float t2[3], const float t3[3], float *depth)
Definition: pbvh.c:2184
void BKE_pbvh_search_gather(PBVH *pbvh, BKE_pbvh_SearchCallback scb, void *search_data, PBVHNode ***r_array, int *r_tot)
Definition: pbvh.c:838
const float(* BKE_pbvh_get_vert_normals(const PBVH *pbvh))[3]
Definition: pbvh.c:3225
static void pbvh_update_visibility_task_cb(void *__restrict userdata, const int n, const TaskParallelTLS *__restrict UNUSED(tls))
Definition: pbvh.c:1675
static void pbvh_bmesh_node_visibility_update(PBVHNode *node)
Definition: pbvh.c:1647
struct PBVHDrawSearchData PBVHDrawSearchData
static bool pbvh_faces_node_nearest_to_ray(PBVH *pbvh, const PBVHNode *node, float(*origco)[3], const float ray_start[3], const float ray_normal[3], float *depth, float *dist_sq)
Definition: pbvh.c:2608
static void pbvh_update_normals_accum_task_cb(void *__restrict userdata, const int n, const TaskParallelTLS *__restrict UNUSED(tls))
Definition: pbvh.c:1035
bool BKE_pbvh_is_deformed(PBVH *pbvh)
Definition: pbvh.c:3010
void BKE_pbvh_update_active_vcol(PBVH *pbvh, const Mesh *mesh)
Definition: pbvh.c:3270
int BKE_pbvh_get_grid_num_vertices(const PBVH *pbvh)
Definition: pbvh.c:1849
int BKE_pbvh_count_grid_quads(BLI_bitmap **grid_hidden, const int *grid_indices, int totgrid, int gridsize)
Definition: pbvh.c:339
bool pbvh_has_mask(const PBVH *pbvh)
Definition: pbvh.c:3157
void BKE_pbvh_update_normals(PBVH *pbvh, struct SubdivCCG *subdiv_ccg)
Definition: pbvh.c:2813
void pbvh_free_draw_buffers(PBVH *pbvh, PBVHNode *node)
Definition: pbvh.c:1389
bool BKE_pbvh_node_find_nearest_to_ray(PBVH *pbvh, PBVHNode *node, float(*origco)[3], bool use_origco, const float ray_start[3], const float ray_normal[3], float *depth, float *dist_sq)
Definition: pbvh.c:2717
static void pbvh_update_mask_redraw_task_cb(void *__restrict userdata, const int n, const TaskParallelTLS *__restrict UNUSED(tls))
Definition: pbvh.c:1140
static bool face_materials_match(const MPoly *f1, const MPoly *f2)
Definition: pbvh.c:148
void BKE_pbvh_ensure_node_loops(PBVH *pbvh)
Definition: pbvh.c:3280
static void pbvh_check_draw_layout(PBVH *pbvh)
Definition: pbvh.c:1399
PBVHProxyNode * BKE_pbvh_node_add_proxy(PBVH *pbvh, PBVHNode *node)
Definition: pbvh.c:3016
static void build_leaf(PBVH *pbvh, int node_index, BBC *prim_bbc, int offset, int count)
Definition: pbvh.c:399
static bool update_search_cb(PBVHNode *node, void *data_v)
Definition: pbvh.c:993
static void pbvh_stack_push(PBVHIter *iter, PBVHNode *node, bool revisiting)
Definition: pbvh.c:748
PBVH * BKE_pbvh_new(void)
Definition: pbvh.c:655
static bool pbvh_faces_node_raycast(PBVH *pbvh, const PBVHNode *node, float(*origco)[3], const float ray_start[3], const float ray_normal[3], struct IsectRayPrecalc *isect_precalc, float *depth, int *r_active_vertex_index, int *r_active_face_index, float *r_face_normal)
Definition: pbvh.c:2295
bool BKE_pbvh_has_faces(const PBVH *pbvh)
Definition: pbvh.c:1803
void BKE_pbvh_pmap_set(PBVH *pbvh, const MeshElemMap *pmap)
Definition: pbvh.c:3275
bool BKE_pbvh_node_fully_hidden_get(PBVHNode *node)
Definition: pbvh.c:1928
static void build_grid_leaf_node(PBVH *pbvh, PBVHNode *node)
Definition: pbvh.c:391
void BKE_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden)
Definition: pbvh.c:1916
void BKE_pbvh_grids_update(PBVH *pbvh, CCGElem **grids, void **gridfaces, DMFlagMat *flagmats, BLI_bitmap **grid_hidden)
Definition: pbvh.c:2932
bool BKE_pbvh_node_frustum_contain_AABB(PBVHNode *node, void *data)
Definition: pbvh.c:2793
static void pbvh_update_normals_store_task_cb(void *__restrict userdata, const int n, const TaskParallelTLS *__restrict UNUSED(tls))
Definition: pbvh.c:1085
void BKE_pbvh_node_num_loops(PBVH *pbvh, PBVHNode *node, int *r_totloop)
Definition: pbvh.c:3260
PBVHColorBufferNode * BKE_pbvh_node_color_buffer_get(PBVHNode *node)
Definition: pbvh.c:3079
static void pbvh_grids_node_visibility_update(PBVH *pbvh, PBVHNode *node)
Definition: pbvh.c:1616
const CCGKey * BKE_pbvh_get_grid_key(const PBVH *pbvh)
Definition: pbvh.c:1831
static void pbvh_faces_node_visibility_update(PBVH *pbvh, PBVHNode *node)
Definition: pbvh.c:1597
bool BKE_pbvh_node_frustum_exclude_AABB(PBVHNode *node, void *data)
Definition: pbvh.c:2803
void BKE_pbvh_respect_hide_set(PBVH *pbvh, bool respect_hide)
Definition: pbvh.c:3241
void BKE_pbvh_node_mark_update_mask(PBVHNode *node)
Definition: pbvh.c:1875
void BBC_update_centroid(BBC *bbc)
Definition: pbvh.c:108
void BKE_pbvh_node_get_verts(PBVH *pbvh, PBVHNode *node, const int **r_vert_indices, MVert **r_verts)
Definition: pbvh.c:1989
bool BKE_pbvh_get_color_layer(const Mesh *me, CustomDataLayer **r_layer, eAttrDomain *r_attr)
Definition: pbvh.c:1271
static int map_insert_vert(PBVH *pbvh, GHash *map, unsigned int *face_verts, unsigned int *uniq_verts, int vertex)
Definition: pbvh.c:239
bool BKE_pbvh_node_fully_unmasked_get(PBVHNode *node)
Definition: pbvh.c:1962
BMesh * BKE_pbvh_get_bmesh(PBVH *pbvh)
Definition: pbvh.c:1861
static void pbvh_update_BB_redraw_task_cb(void *__restrict userdata, const int n, const TaskParallelTLS *__restrict UNUSED(tls))
Definition: pbvh.c:1226
BLI_bitmap ** BKE_pbvh_grid_hidden(const PBVH *pbvh)
Definition: pbvh.c:1825
static int partition_indices_material(PBVH *pbvh, int lo, int hi)
Definition: pbvh.c:181
static void update_node_vb(PBVH *pbvh, PBVHNode *node)
Definition: pbvh.c:116
void BKE_pbvh_bounding_box(const PBVH *pbvh, float min[3], float max[3])
Definition: pbvh.c:1812
void BKE_pbvh_search_callback(PBVH *pbvh, BKE_pbvh_SearchCallback scb, void *search_data, BKE_pbvh_HitCallback hcb, void *hit_data)
Definition: pbvh.c:871
void BB_reset(BB *bb)
Definition: pbvh.c:63
bool BKE_pbvh_draw_cache_invalid(const PBVH *pbvh)
Definition: pbvh.c:3250
void BKE_pbvh_node_mark_redraw(PBVHNode *node)
Definition: pbvh.c:1906
#define STACK_FIXED_DEPTH
Definition: pbvh.c:44
static PBVHNode * pbvh_iter_next_occluded(PBVHIter *iter)
Definition: pbvh.c:809
static void traverse_tree(node_tree *tree, BKE_pbvh_HitOccludedCallback hcb, void *hit_data, float *tmin)
Definition: pbvh.c:918
void pbvh_vertex_iter_init(PBVH *pbvh, PBVHNode *node, PBVHVertexIter *vi, int mode)
Definition: pbvh.c:3099
void BKE_pbvh_node_get_grids(PBVH *pbvh, PBVHNode *node, int **r_grid_indices, int *r_totgrid, int *r_maxgrid, int *r_gridsize, CCGElem ***r_griddata)
Definition: pbvh.c:2037
struct PBVHStack PBVHStack
static void pbvh_update_mask_redraw(PBVH *pbvh, PBVHNode **nodes, int totnode, int flag)
Definition: pbvh.c:1176
void BKE_pbvh_face_sets_set(PBVH *pbvh, int *face_sets)
Definition: pbvh.c:3236
void BKE_pbvh_node_get_proxies(PBVHNode *node, PBVHProxyNode **proxies, int *proxy_count)
Definition: pbvh.c:2096
void BKE_pbvh_find_nearest_to_ray(PBVH *pbvh, BKE_pbvh_SearchNearestCallback cb, void *data, const float ray_start[3], const float ray_normal[3], bool original)
Definition: pbvh.c:2593
static void free_tree(node_tree *tree)
Definition: pbvh.c:934
float(* BKE_pbvh_vert_coords_alloc(PBVH *pbvh))[3]
Definition: pbvh.c:2948
#define LEAF_LIMIT
Definition: pbvh.c:40
void BB_expand(BB *bb, const float co[3])
Definition: pbvh.c:69
static void pbvh_update_draw_buffers(PBVH *pbvh, PBVHNode **nodes, int totnode, int update_flag)
Definition: pbvh.c:1446
void BKE_pbvh_parallel_range_settings(TaskParallelSettings *settings, bool use_threading, int totnode)
Definition: pbvh.c:3211
bool pbvh_has_face_sets(PBVH *pbvh)
Definition: pbvh.c:3171
bool pbvh_bmesh_node_nearest_to_ray(PBVHNode *node, const float ray_start[3], const float ray_normal[3], float *depth, float *dist_sq, bool use_original)
Definition: pbvh_bmesh.c:1606
bool pbvh_bmesh_node_raycast(PBVHNode *node, const float ray_start[3], const float ray_normal[3], struct IsectRayPrecalc *isect_precalc, float *depth, bool use_original, int *r_active_vertex_index, float *r_face_normal)
Definition: pbvh_bmesh.c:1498
void pbvh_bmesh_normals_update(PBVHNode **nodes, int totnode)
Definition: pbvh_bmesh.c:1647
@ PBVH_DYNTOPO_SMOOTH_SHADING
Definition: pbvh_intern.h:128
void pbvh_pixels_free(PBVHNode *node)
Definition: pbvh_pixels.cc:388
return ret
#define min(a, b)
Definition: sort.c:35
float bmax[3]
Definition: pbvh_intern.h:27
float bmin[3]
Definition: pbvh_intern.h:27
float bcentroid[3]
Definition: pbvh_intern.h:27
Definition: pbvh_intern.h:21
float bmax[3]
Definition: pbvh_intern.h:22
float bmin[3]
Definition: pbvh_intern.h:22
CustomData vdata
Definition: bmesh_class.h:337
CustomData ldata
Definition: bmesh_class.h:337
int totface
Definition: bmesh_class.h:297
Definition: BKE_ccg.h:32
int has_mask
Definition: BKE_ccg.h:55
int grid_size
Definition: BKE_ccg.h:40
int grid_area
Definition: BKE_ccg.h:42
struct DistRayAABB_Precalc dist_ray_to_aabb_precalc
Definition: pbvh.c:2566
Definition: DNA_ID.h:368
unsigned int poly
unsigned int tri[3]
unsigned int v
short mat_nr
float co[3]
int face_sets_color_seed
int face_sets_color_default
PBVHFrustumPlanes * frustum
Definition: pbvh.c:2854
int accum_update_flag
Definition: pbvh.c:2855
float(* planes)[4]
Definition: BKE_pbvh.h:86
Definition: pbvh.c:51
PBVHStack stackfixed[STACK_FIXED_DEPTH]
Definition: pbvh.c:59
void * search_data
Definition: pbvh.c:54
PBVH * pbvh
Definition: pbvh.c:52
BKE_pbvh_SearchCallback scb
Definition: pbvh.c:53
PBVHStack * stack
Definition: pbvh.c:56
int stacksize
Definition: pbvh.c:57
int stackspace
Definition: pbvh.c:60
unsigned int totprim
Definition: pbvh_intern.h:57
float tmin
Definition: pbvh_intern.h:102
int * prim_indices
Definition: pbvh_intern.h:56
int children_offset
Definition: pbvh_intern.h:44
PBVHNodeFlags flag
Definition: pbvh_intern.h:99
Definition: pbvh.c:46
PBVHNode * node
Definition: pbvh.c:47
bool revisiting
Definition: pbvh.c:48
PBVH * pbvh
Definition: pbvh.c:1005
int totnode
Definition: pbvh.c:1007
bool show_sculpt_face_sets
Definition: pbvh.c:1011
float(* vnors)[3]
Definition: pbvh.c:1009
PBVHNode ** nodes
Definition: pbvh.c:1006
struct MVert * mvert
Definition: BKE_pbvh.h:428
int * grid_indices
Definition: BKE_pbvh.h:409
bool respect_hide
Definition: BKE_pbvh.h:402
struct CCGKey key
Definition: BKE_pbvh.h:405
float * co
Definition: BKE_pbvh.h:430
int cd_vert_mask_offset
Definition: BKE_pbvh.h:424
float * fno
Definition: BKE_pbvh.h:432
float * no
Definition: BKE_pbvh.h:431
BLI_bitmap ** grid_hidden
Definition: BKE_pbvh.h:408
struct GSetIterator bm_other_verts
Definition: BKE_pbvh.h:422
struct GSetIterator bm_unique_verts
Definition: BKE_pbvh.h:421
BLI_bitmap * gh
Definition: BKE_pbvh.h:408
float * vmask
Definition: BKE_pbvh.h:418
struct CCGElem ** grids
Definition: BKE_pbvh.h:406
struct CCGElem * grid
Definition: BKE_pbvh.h:407
float(* vert_normals)[3]
Definition: BKE_pbvh.h:415
float * mask
Definition: BKE_pbvh.h:433
const int * vert_indices
Definition: BKE_pbvh.h:417
struct CustomData * bm_vdata
Definition: BKE_pbvh.h:423
struct MVert * mverts
Definition: BKE_pbvh.h:414
PBVHType type
Definition: pbvh_intern.h:133
float planes[6][4]
Definition: pbvh_intern.h:192
int totvert
Definition: pbvh_intern.h:142
int * prim_indices
Definition: pbvh_intern.h:140
CustomData * ldata
Definition: pbvh_intern.h:156
const DMFlagMat * grid_flag_mats
Definition: pbvh_intern.h:167
CustomData * pdata
Definition: pbvh_intern.h:157
float(* vert_normals)[3]
Definition: pbvh_intern.h:150
bool respect_hide
Definition: pbvh_intern.h:183
BLI_bitmap ** grid_hidden
Definition: pbvh_intern.h:169
bool deformed
Definition: pbvh_intern.h:180
bool * vert_bitmap
Definition: pbvh_intern.h:173
struct MVert * verts
Definition: pbvh_intern.h:151
const struct MPoly * mpoly
Definition: pbvh_intern.h:152
bool show_mask
Definition: pbvh_intern.h:181
int face_sets_color_seed
Definition: pbvh_intern.h:159
CCGElem ** grids
Definition: pbvh_intern.h:165
const struct Mesh * mesh
Definition: pbvh_intern.h:147
const struct MeshElemMap * pmap
Definition: pbvh_intern.h:198
bool is_drawing
Definition: pbvh_intern.h:203
CCGKey gridkey
Definition: pbvh_intern.h:164
int totprim
Definition: pbvh_intern.h:141
int num_planes
Definition: pbvh_intern.h:193
int node_mem_count
Definition: pbvh_intern.h:137
int totgrid
Definition: pbvh_intern.h:168
void ** gridfaces
Definition: pbvh_intern.h:166
int leaf_limit
Definition: pbvh_intern.h:144
bool draw_cache_invalid
Definition: pbvh_intern.h:206
struct PBVHGPUFormat * vbo_id
Definition: pbvh_intern.h:208
const struct MLoop * mloop
Definition: pbvh_intern.h:153
bool show_face_sets
Definition: pbvh_intern.h:182
eAttrDomain color_domain
Definition: pbvh_intern.h:201
int * face_sets
Definition: pbvh_intern.h:161
PBVHFlags flags
Definition: pbvh_intern.h:134
const struct MLoopTri * looptri
Definition: pbvh_intern.h:154
struct SubdivCCG * subdiv_ccg
Definition: pbvh_intern.h:196
BMesh * bm
Definition: pbvh_intern.h:186
int totnode
Definition: pbvh_intern.h:137
CustomData * vdata
Definition: pbvh_intern.h:155
PBVHNode * nodes
Definition: pbvh_intern.h:136
int face_sets_color_default
Definition: pbvh_intern.h:160
CustomDataLayer * color_layer
Definition: pbvh_intern.h:200
bool original
Definition: pbvh.c:2147
struct IsectRayAABB_Precalc ray
Definition: pbvh.c:2146
struct node_tree * left
Definition: pbvh.c:894
PBVHNode * data
Definition: pbvh.c:892
struct node_tree * right
Definition: pbvh.c:895
float max