Blender  V3.3
mesh_boolean_convert.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2001-2002 NaN Holding BV. All rights reserved. */
3 
8 #include "DNA_mesh_types.h"
9 #include "DNA_meshdata_types.h"
10 #include "DNA_object_types.h"
11 
12 #include "BKE_customdata.h"
13 #include "BKE_material.h"
14 #include "BKE_mesh.h"
16 
17 #include "BLI_alloca.h"
18 #include "BLI_array.hh"
19 #include "BLI_float4x4.hh"
20 #include "BLI_math.h"
21 #include "BLI_math_vec_types.hh"
22 #include "BLI_mesh_boolean.hh"
23 #include "BLI_mesh_intersect.hh"
24 #include "BLI_span.hh"
25 #include "BLI_task.hh"
26 
27 namespace blender::meshintersect {
28 
29 #ifdef WITH_GMP
30 
31 constexpr int estimated_max_facelen = 100; /* Used for initial size of some Vectors. */
32 
33 /* Snap entries that are near 0 or 1 or -1 to those values.
34  * Sometimes Blender's rotation matrices for multiples of 90 degrees have
35  * tiny numbers where there should be zeros. That messes makes some things
36  * every so slightly non-coplanar when users expect coplanarity,
37  * so this is a hack to clean up such matrices.
38  * Would be better to change the transformation code itself.
39  */
40 static float4x4 clean_transform(const float4x4 &mat)
41 {
42  float4x4 cleaned;
43  const float fuzz = 1e-6f;
44  for (int i = 0; i < 4; i++) {
45  for (int j = 0; j < 4; j++) {
46  float f = mat.values[i][j];
47  if (fabsf(f) <= fuzz) {
48  f = 0.0f;
49  }
50  else if (fabsf(f - 1.0f) <= fuzz) {
51  f = 1.0f;
52  }
53  else if (fabsf(f + 1.0f) <= fuzz) {
54  f = -1.0f;
55  }
56  cleaned.values[i][j] = f;
57  }
58  }
59  return cleaned;
60 }
61 
62 /* `MeshesToIMeshInfo` keeps track of information used when combining a number
63  * of `Mesh`es into a single `IMesh` for doing boolean on.
64  * Mostly this means keeping track of the index offsets for various mesh elements. */
65 class MeshesToIMeshInfo {
66  public:
67  /* The input meshes, */
68  Span<const Mesh *> meshes;
69  /* Numbering the vertices of the meshes in order of meshes,
70  * at what offset does the vertex range for mesh[i] start? */
71  Array<int> mesh_vert_offset;
72  /* Similarly for edges of meshes. */
73  Array<int> mesh_edge_offset;
74  /* Similarly for polys of meshes. */
75  Array<int> mesh_poly_offset;
76  /* For each Mesh vertex in all the meshes (with concatenated indexing),
77  * what is the IMesh Vert* allocated for it in the input IMesh? */
78  Array<const Vert *> mesh_to_imesh_vert;
79  /* Similarly for each Mesh poly. */
80  Array<Face *> mesh_to_imesh_face;
81  /* Transformation matrix to transform a coordinate in the corresponding
82  * Mesh to the local space of the first Mesh. */
83  Array<float4x4> to_target_transform;
84  /* For each input mesh, whether or not their transform is negative. */
85  Array<bool> has_negative_transform;
86  /* For each input mesh, how to remap the material slot numbers to
87  * the material slots in the first mesh. */
88  Span<Array<short>> material_remaps;
89  /* Total number of input mesh vertices. */
90  int tot_meshes_verts;
91  /* Total number of input mesh edges. */
92  int tot_meshes_edges;
93  /* Total number of input mesh polys. */
94  int tot_meshes_polys;
95 
96  int input_mesh_for_imesh_vert(int imesh_v) const;
97  int input_mesh_for_imesh_edge(int imesh_e) const;
98  int input_mesh_for_imesh_face(int imesh_f) const;
99  const MPoly *input_mpoly_for_orig_index(int orig_index,
100  const Mesh **r_orig_mesh,
101  int *r_orig_mesh_index,
102  int *r_index_in_orig_mesh) const;
103  const MVert *input_mvert_for_orig_index(int orig_index,
104  const Mesh **r_orig_mesh,
105  int *r_index_in_orig_mesh) const;
106  const MEdge *input_medge_for_orig_index(int orig_index,
107  const Mesh **r_orig_mesh,
108  int *r_index_in_orig_mesh) const;
109 };
110 
111 /* Given an index `imesh_v` in the `IMesh`, return the index of the
112  * input `Mesh` that contained the `MVert` that it came from. */
113 int MeshesToIMeshInfo::input_mesh_for_imesh_vert(int imesh_v) const
114 {
115  int n = static_cast<int>(mesh_vert_offset.size());
116  for (int i = 0; i < n - 1; ++i) {
117  if (imesh_v < mesh_vert_offset[i + 1]) {
118  return i;
119  }
120  }
121  return n - 1;
122 }
123 
124 /* Given an index `imesh_e` used as an original index in the `IMesh`,
125  * return the index of the input `Mesh` that contained the `MVert` that it came from. */
126 int MeshesToIMeshInfo::input_mesh_for_imesh_edge(int imesh_e) const
127 {
128  int n = static_cast<int>(mesh_edge_offset.size());
129  for (int i = 0; i < n - 1; ++i) {
130  if (imesh_e < mesh_edge_offset[i + 1]) {
131  return i;
132  }
133  }
134  return n - 1;
135 }
136 
137 /* Given an index `imesh_f` in the `IMesh`, return the index of the
138  * input `Mesh` that contained the `MPoly` that it came from. */
139 int MeshesToIMeshInfo::input_mesh_for_imesh_face(int imesh_f) const
140 {
141  int n = static_cast<int>(mesh_poly_offset.size());
142  for (int i = 0; i < n - 1; ++i) {
143  if (imesh_f < mesh_poly_offset[i + 1]) {
144  return i;
145  }
146  }
147  return n - 1;
148 }
149 
150 /* Given an index of an original face in the `IMesh`, find out the input
151  * `Mesh` that it came from and return it in `*r_orig_mesh`,
152  * and also return the index of that `Mesh` in `*r_orig_mesh_index`.
153  * Finally, return the index of the corresponding `MPoly` in that `Mesh`
154  * in `*r_index_in_orig_mesh`. */
155 const MPoly *MeshesToIMeshInfo::input_mpoly_for_orig_index(int orig_index,
156  const Mesh **r_orig_mesh,
157  int *r_orig_mesh_index,
158  int *r_index_in_orig_mesh) const
159 {
160  int orig_mesh_index = input_mesh_for_imesh_face(orig_index);
161  BLI_assert(0 <= orig_mesh_index && orig_mesh_index < meshes.size());
162  const Mesh *me = meshes[orig_mesh_index];
163  int index_in_mesh = orig_index - mesh_poly_offset[orig_mesh_index];
164  BLI_assert(0 <= index_in_mesh && index_in_mesh < me->totpoly);
165  const MPoly *mp = &me->mpoly[index_in_mesh];
166  if (r_orig_mesh) {
167  *r_orig_mesh = me;
168  }
169  if (r_orig_mesh_index) {
170  *r_orig_mesh_index = orig_mesh_index;
171  }
172  if (r_index_in_orig_mesh) {
173  *r_index_in_orig_mesh = index_in_mesh;
174  }
175  return mp;
176 }
177 
178 /* Given an index of an original vertex in the `IMesh`, find out the input
179  * `Mesh` that it came from and return it in `*r_orig_mesh`.
180  * Also find the index of the `MVert` in that `Mesh` and return it in
181  * `*r_index_in_orig_mesh`. */
182 const MVert *MeshesToIMeshInfo::input_mvert_for_orig_index(int orig_index,
183  const Mesh **r_orig_mesh,
184  int *r_index_in_orig_mesh) const
185 {
186  int orig_mesh_index = input_mesh_for_imesh_vert(orig_index);
187  BLI_assert(0 <= orig_mesh_index && orig_mesh_index < meshes.size());
188  const Mesh *me = meshes[orig_mesh_index];
189  int index_in_mesh = orig_index - mesh_vert_offset[orig_mesh_index];
190  BLI_assert(0 <= index_in_mesh && index_in_mesh < me->totvert);
191  const MVert *mv = &me->mvert[index_in_mesh];
192  if (r_orig_mesh) {
193  *r_orig_mesh = me;
194  }
195  if (r_index_in_orig_mesh) {
196  *r_index_in_orig_mesh = index_in_mesh;
197  }
198  return mv;
199 }
200 
201 /* Similarly for edges. */
202 const MEdge *MeshesToIMeshInfo::input_medge_for_orig_index(int orig_index,
203  const Mesh **r_orig_mesh,
204  int *r_index_in_orig_mesh) const
205 {
206  int orig_mesh_index = input_mesh_for_imesh_edge(orig_index);
207  BLI_assert(0 <= orig_mesh_index && orig_mesh_index < meshes.size());
208  const Mesh *me = meshes[orig_mesh_index];
209  int index_in_mesh = orig_index - mesh_edge_offset[orig_mesh_index];
210  BLI_assert(0 <= index_in_mesh && index_in_mesh < me->totedge);
211  const MEdge *medge = &me->medge[index_in_mesh];
212  if (r_orig_mesh) {
213  *r_orig_mesh = me;
214  }
215  if (r_index_in_orig_mesh) {
216  *r_index_in_orig_mesh = index_in_mesh;
217  }
218  return medge;
219 }
220 
233 static IMesh meshes_to_imesh(Span<const Mesh *> meshes,
234  Span<const float4x4 *> obmats,
235  Span<Array<short>> material_remaps,
236  const float4x4 &target_transform,
237  IMeshArena &arena,
238  MeshesToIMeshInfo *r_info)
239 {
240  int nmeshes = meshes.size();
241  BLI_assert(nmeshes > 0);
242  r_info->meshes = meshes;
243  r_info->tot_meshes_verts = 0;
244  r_info->tot_meshes_polys = 0;
245  int &totvert = r_info->tot_meshes_verts;
246  int &totedge = r_info->tot_meshes_edges;
247  int &totpoly = r_info->tot_meshes_polys;
248  for (const Mesh *me : meshes) {
249  totvert += me->totvert;
250  totedge += me->totedge;
251  totpoly += me->totpoly;
252  }
253 
254  /* Estimate the number of vertices and faces in the boolean output,
255  * so that the memory arena can reserve some space. It is OK if these
256  * estimates are wrong. */
257  const int estimate_num_outv = 3 * totvert;
258  const int estimate_num_outf = 4 * totpoly;
259  arena.reserve(estimate_num_outv, estimate_num_outf);
260  r_info->mesh_to_imesh_vert.reinitialize(totvert);
261  r_info->mesh_to_imesh_face.reinitialize(totpoly);
262  r_info->mesh_vert_offset.reinitialize(nmeshes);
263  r_info->mesh_edge_offset.reinitialize(nmeshes);
264  r_info->mesh_poly_offset.reinitialize(nmeshes);
265  r_info->to_target_transform.reinitialize(nmeshes);
266  r_info->has_negative_transform.reinitialize(nmeshes);
267  r_info->material_remaps = material_remaps;
268  int v = 0;
269  int e = 0;
270  int f = 0;
271 
272  /* Put these Vectors here, with a size unlikely to need resizing,
273  * so that the loop to make new Faces will likely not need to allocate
274  * over and over. */
275  Vector<const Vert *, estimated_max_facelen> face_vert;
276  Vector<int, estimated_max_facelen> face_edge_orig;
277 
278  /* To convert the coordinates of meshes 1, 2, etc. into the local space
279  * of the target, multiply each transform by the inverse of the
280  * target matrix. Exact Boolean works better if these matrices are 'cleaned'
281  * -- see the comment for the `clean_transform` function, above. */
282  const float4x4 inv_target_mat = clean_transform(target_transform).inverted();
283 
284  /* For each input `Mesh`, make `Vert`s and `Face`s for the corresponding
285  * `MVert`s and `MPoly`s, and keep track of the original indices (using the
286  * concatenating offset scheme) inside the `Vert`s and `Face`s.
287  * When making `Face`s, we also put in the original indices for `MEdge`s that
288  * make up the `MPoly`s using the same scheme. */
289  for (int mi : meshes.index_range()) {
290  const Mesh *me = meshes[mi];
291  r_info->mesh_vert_offset[mi] = v;
292  r_info->mesh_edge_offset[mi] = e;
293  r_info->mesh_poly_offset[mi] = f;
294  /* Get matrix that transforms a coordinate in meshes[mi]'s local space
295  * to the target space. */
296  const float4x4 objn_mat = (obmats[mi] == nullptr) ? float4x4::identity() :
297  clean_transform(*obmats[mi]);
298  r_info->to_target_transform[mi] = inv_target_mat * objn_mat;
299  r_info->has_negative_transform[mi] = objn_mat.is_negative();
300 
301  /* All meshes 1 and up will be transformed into the local space of operand 0.
302  * Historical behavior of the modifier has been to flip the faces of any meshes
303  * that would have a negative transform if you do that. */
304  bool need_face_flip = r_info->has_negative_transform[mi] != r_info->has_negative_transform[0];
305 
306  Vector<Vert *> verts(me->totvert);
307  Span<MVert> mverts = Span(me->mvert, me->totvert);
308 
309  /* Allocate verts
310  * Skip the matrix multiplication for each point when there is no transform for a mesh,
311  * for example when the first mesh is already in the target space. (Note the logic
312  * directly above, which uses an identity matrix with a null input transform). */
313  if (obmats[mi] == nullptr) {
314  threading::parallel_for(mverts.index_range(), 2048, [&](IndexRange range) {
315  float3 co;
316  for (int i : range) {
317  co = float3(mverts[i].co);
318  mpq3 mco = mpq3(co.x, co.y, co.z);
319  double3 dco(mco[0].get_d(), mco[1].get_d(), mco[2].get_d());
320  verts[i] = new Vert(mco, dco, NO_INDEX, i);
321  }
322  });
323  }
324  else {
325  threading::parallel_for(mverts.index_range(), 2048, [&](IndexRange range) {
326  float3 co;
327  for (int i : range) {
328  co = r_info->to_target_transform[mi] * float3(mverts[i].co);
329  mpq3 mco = mpq3(co.x, co.y, co.z);
330  double3 dco(mco[0].get_d(), mco[1].get_d(), mco[2].get_d());
331  verts[i] = new Vert(mco, dco, NO_INDEX, i);
332  }
333  });
334  }
335  for (int i : mverts.index_range()) {
336  r_info->mesh_to_imesh_vert[v] = arena.add_or_find_vert(verts[i]);
337  ++v;
338  }
339 
340  for (const MPoly &poly : Span(me->mpoly, me->totpoly)) {
341  int flen = poly.totloop;
342  face_vert.resize(flen);
343  face_edge_orig.resize(flen);
344  const MLoop *l = &me->mloop[poly.loopstart];
345  for (int i = 0; i < flen; ++i) {
346  int mverti = r_info->mesh_vert_offset[mi] + l->v;
347  const Vert *fv = r_info->mesh_to_imesh_vert[mverti];
348  if (need_face_flip) {
349  face_vert[flen - i - 1] = fv;
350  int iedge = i < flen - 1 ? flen - i - 2 : flen - 1;
351  face_edge_orig[iedge] = e + l->e;
352  }
353  else {
354  face_vert[i] = fv;
355  face_edge_orig[i] = e + l->e;
356  }
357  ++l;
358  }
359  r_info->mesh_to_imesh_face[f] = arena.add_face(face_vert, f, face_edge_orig);
360  ++f;
361  }
362  e += me->totedge;
363  }
364  return IMesh(r_info->mesh_to_imesh_face);
365 }
366 
367 /* Copy vertex attributes, including customdata, from `orig_mv` to `mv`.
368  * `mv` is in `dest_mesh` with index `mv_index`.
369  * The `orig_mv` vertex came from Mesh `orig_me` and had index `index_in_orig_me` there. */
370 static void copy_vert_attributes(Mesh *dest_mesh,
371  MVert *mv,
372  const MVert *orig_mv,
373  const Mesh *orig_me,
374  int mv_index,
375  int index_in_orig_me)
376 {
377  mv->bweight = orig_mv->bweight;
378  mv->flag = orig_mv->flag;
379 
380  /* For all layers in the orig mesh, copy the layer information. */
381  CustomData *target_cd = &dest_mesh->vdata;
382  const CustomData *source_cd = &orig_me->vdata;
383  for (int source_layer_i = 0; source_layer_i < source_cd->totlayer; ++source_layer_i) {
384  int ty = source_cd->layers[source_layer_i].type;
385  /* The (first) CD_MVERT layer is the same as dest_mesh->vdata, so we've
386  * already set the coordinate to the right value. */
387  if (ty == CD_MVERT) {
388  continue;
389  }
390  const char *name = source_cd->layers[source_layer_i].name;
391  int target_layer_i = CustomData_get_named_layer_index(target_cd, ty, name);
392  /* Not all layers were merged in target: some are marked CD_FLAG_NOCOPY
393  * and some are not in the CD_MASK_MESH.vdata. */
394  if (target_layer_i != -1) {
396  source_cd, target_cd, source_layer_i, target_layer_i, index_in_orig_me, mv_index, 1);
397  }
398  }
399 }
400 
401 /* Similar to copy_vert_attributes but for poly attributes. */
402 static void copy_poly_attributes(Mesh *dest_mesh,
403  MPoly *mp,
404  const MPoly *orig_mp,
405  const Mesh *orig_me,
406  int mp_index,
407  int index_in_orig_me,
408  Span<short> material_remap)
409 {
410  if (material_remap.size() > 0 && material_remap.index_range().contains(orig_mp->mat_nr)) {
411  mp->mat_nr = material_remap[orig_mp->mat_nr];
412  }
413  else {
414  mp->mat_nr = orig_mp->mat_nr;
415  }
416 
417  mp->flag = orig_mp->flag;
418  CustomData *target_cd = &dest_mesh->pdata;
419  const CustomData *source_cd = &orig_me->pdata;
420  for (int source_layer_i = 0; source_layer_i < source_cd->totlayer; ++source_layer_i) {
421  int ty = source_cd->layers[source_layer_i].type;
422  if (ty == CD_MPOLY) {
423  continue;
424  }
425  const char *name = source_cd->layers[source_layer_i].name;
426  int target_layer_i = CustomData_get_named_layer_index(target_cd, ty, name);
427  if (target_layer_i != -1) {
429  source_cd, target_cd, source_layer_i, target_layer_i, index_in_orig_me, mp_index, 1);
430  }
431  }
432 }
433 
434 /* Similar to copy_vert_attributes but for edge attributes. */
435 static void copy_edge_attributes(Mesh *dest_mesh,
436  MEdge *medge,
437  const MEdge *orig_medge,
438  const Mesh *orig_me,
439  int medge_index,
440  int index_in_orig_me)
441 {
442  medge->bweight = orig_medge->bweight;
443  medge->crease = orig_medge->crease;
444  medge->flag = orig_medge->flag;
445  CustomData *target_cd = &dest_mesh->edata;
446  const CustomData *source_cd = &orig_me->edata;
447  for (int source_layer_i = 0; source_layer_i < source_cd->totlayer; ++source_layer_i) {
448  int ty = source_cd->layers[source_layer_i].type;
449  if (ty == CD_MEDGE) {
450  continue;
451  }
452  const char *name = source_cd->layers[source_layer_i].name;
453  int target_layer_i = CustomData_get_named_layer_index(target_cd, ty, name);
454  if (target_layer_i != -1) {
456  source_cd, target_cd, source_layer_i, target_layer_i, index_in_orig_me, medge_index, 1);
457  }
458  }
459 }
460 
471 static int fill_orig_loops(const Face *f,
472  const MPoly *orig_mp,
473  const Mesh *orig_me,
474  int orig_me_index,
475  MeshesToIMeshInfo &mim,
476  Array<int> &orig_loops)
477 {
478  orig_loops.fill(-1);
479  int orig_mplen = orig_mp->totloop;
480  if (f->size() != orig_mplen) {
481  return 0;
482  }
483  BLI_assert(orig_loops.size() == orig_mplen);
484  /* We'll look for the case where the first vertex in f has an original vertex
485  * that is the same as one in orig_me (after correcting for offset in mim meshes).
486  * Then see that loop and any subsequent ones have the same start and end vertex.
487  * This may miss some cases of partial alignment, but that's OK since discovering
488  * aligned loops is only an optimization to avoid some re-interpolation.
489  */
490  int first_orig_v = f->vert[0]->orig;
491  if (first_orig_v == NO_INDEX) {
492  return 0;
493  }
494  /* It is possible that the original vert was merged with another in another mesh. */
495  if (orig_me_index != mim.input_mesh_for_imesh_vert(first_orig_v)) {
496  return 0;
497  }
498  int orig_me_vert_offset = mim.mesh_vert_offset[orig_me_index];
499  int first_orig_v_in_orig_me = first_orig_v - orig_me_vert_offset;
500  BLI_assert(0 <= first_orig_v_in_orig_me && first_orig_v_in_orig_me < orig_me->totvert);
501  /* Assume all vertices in an mpoly are unique. */
502  int offset = -1;
503  for (int i = 0; i < orig_mplen; ++i) {
504  int loop_i = i + orig_mp->loopstart;
505  if (orig_me->mloop[loop_i].v == first_orig_v_in_orig_me) {
506  offset = i;
507  break;
508  }
509  }
510  if (offset == -1) {
511  return 0;
512  }
513  int num_orig_loops_found = 0;
514  for (int mp_loop_index = 0; mp_loop_index < orig_mplen; ++mp_loop_index) {
515  int orig_mp_loop_index = (mp_loop_index + offset) % orig_mplen;
516  MLoop *l = &orig_me->mloop[orig_mp->loopstart + orig_mp_loop_index];
517  int fv_orig = f->vert[mp_loop_index]->orig;
518  if (fv_orig != NO_INDEX) {
519  fv_orig -= orig_me_vert_offset;
520  if (fv_orig < 0 || fv_orig >= orig_me->totvert) {
521  fv_orig = NO_INDEX;
522  }
523  }
524  if (l->v == fv_orig) {
525  MLoop *lnext = &orig_me->mloop[orig_mp->loopstart + ((orig_mp_loop_index + 1) % orig_mplen)];
526  int fvnext_orig = f->vert[(mp_loop_index + 1) % orig_mplen]->orig;
527  if (fvnext_orig != NO_INDEX) {
528  fvnext_orig -= orig_me_vert_offset;
529  if (fvnext_orig < 0 || fvnext_orig >= orig_me->totvert) {
530  fvnext_orig = NO_INDEX;
531  }
532  }
533  if (lnext->v == fvnext_orig) {
534  orig_loops[mp_loop_index] = orig_mp->loopstart + orig_mp_loop_index;
535  ++num_orig_loops_found;
536  }
537  }
538  }
539  return num_orig_loops_found;
540 }
541 
542 /* Fill `cos_2d` with the 2d coordinates found by projection MPoly `mp` along
543  * its normal. Also fill in r_axis_mat with the matrix that does that projection.
544  * But before projecting, also transform the 3d coordinate by multiplying by trans_mat.
545  * `cos_2d` should have room for `mp->totloop` entries. */
546 static void get_poly2d_cos(const Mesh *me,
547  const MPoly *mp,
548  float (*cos_2d)[2],
549  const float4x4 &trans_mat,
550  float r_axis_mat[3][3])
551 {
552  int n = mp->totloop;
553 
554  /* Project coordinates to 2d in cos_2d, using normal as projection axis. */
555  float axis_dominant[3];
556  BKE_mesh_calc_poly_normal(mp, &me->mloop[mp->loopstart], me->mvert, axis_dominant);
557  axis_dominant_v3_to_m3(r_axis_mat, axis_dominant);
558  MLoop *ml = &me->mloop[mp->loopstart];
559  const MVert *mverts = me->mvert;
560  for (int i = 0; i < n; ++i) {
561  float3 co = mverts[ml->v].co;
562  co = trans_mat * co;
563  mul_v2_m3v3(cos_2d[i], r_axis_mat, co);
564  ++ml;
565  }
566 }
567 
568 /* For the loops of `mp`, see if the face is unchanged from `orig_mp`, and if so,
569  * copy the Loop attributes from corresponding loops to corresponding loops.
570  * Otherwise, interpolate the Loop attributes in the face `orig_mp`. */
571 static void copy_or_interp_loop_attributes(Mesh *dest_mesh,
572  const Face *f,
573  MPoly *mp,
574  const MPoly *orig_mp,
575  const Mesh *orig_me,
576  int orig_me_index,
577  MeshesToIMeshInfo &mim)
578 {
579  Array<int> orig_loops(mp->totloop);
580  int norig = fill_orig_loops(f, orig_mp, orig_me, orig_me_index, mim, orig_loops);
581  /* We may need these arrays if we have to interpolate Loop attributes rather than just copy.
582  * Right now, trying Array<float[2]> complains, so declare cos_2d a different way. */
583  float(*cos_2d)[2];
584  Array<float> weights;
585  Array<const void *> src_blocks_ofs;
586  float axis_mat[3][3];
587  if (norig != mp->totloop) {
588  /* We will need to interpolate. Make `cos_2d` hold 2d-projected coordinates of `orig_mp`,
589  * which are transformed into object 0's local space before projecting.
590  * At this point we cannot yet calculate the interpolation weights, as they depend on
591  * the coordinate where interpolation is to happen, but we can allocate the needed arrays,
592  * so they don't have to be allocated per-layer. */
593  cos_2d = (float(*)[2])BLI_array_alloca(cos_2d, orig_mp->totloop);
594  weights = Array<float>(orig_mp->totloop);
595  src_blocks_ofs = Array<const void *>(orig_mp->totloop);
596  get_poly2d_cos(orig_me, orig_mp, cos_2d, mim.to_target_transform[orig_me_index], axis_mat);
597  }
598  CustomData *target_cd = &dest_mesh->ldata;
599  for (int i = 0; i < mp->totloop; ++i) {
600  int loop_index = mp->loopstart + i;
601  int orig_loop_index = norig > 0 ? orig_loops[i] : -1;
602  const CustomData *source_cd = &orig_me->ldata;
603  if (orig_loop_index == -1) {
604  /* Will need interpolation weights for this loop's vertex's coordinates.
605  * The coordinate needs to be projected into 2d, just like the interpolating polygon's
606  * coordinates were. The `dest_mesh` coordinates are already in object 0 local space. */
607  float co[2];
608  mul_v2_m3v3(co, axis_mat, dest_mesh->mvert[dest_mesh->mloop[loop_index].v].co);
609  interp_weights_poly_v2(weights.data(), cos_2d, orig_mp->totloop, co);
610  }
611  for (int source_layer_i = 0; source_layer_i < source_cd->totlayer; ++source_layer_i) {
612  int ty = source_cd->layers[source_layer_i].type;
613  if (ty == CD_MLOOP) {
614  continue;
615  }
616  const char *name = source_cd->layers[source_layer_i].name;
617  int target_layer_i = CustomData_get_named_layer_index(target_cd, ty, name);
618  if (target_layer_i == -1) {
619  continue;
620  }
621  if (orig_loop_index != -1) {
623  source_cd, target_cd, source_layer_i, target_layer_i, orig_loop_index, loop_index, 1);
624  }
625  else {
626  /* NOTE: although CustomData_bmesh_interp_n function has bmesh in its name, nothing about
627  * it is BMesh-specific. We can't use CustomData_interp because it assumes that
628  * all source layers exist in the dest.
629  * A non bmesh version could have the benefit of not copying data into src_blocks_ofs -
630  * using the contiguous data instead. TODO: add to the custom data API. */
631  int target_layer_type_index = CustomData_get_named_layer(target_cd, ty, name);
632  if (!CustomData_layer_has_interp(source_cd, source_layer_i)) {
633  continue;
634  }
635  int source_layer_type_index = source_layer_i - source_cd->typemap[ty];
636  BLI_assert(target_layer_type_index != -1 && source_layer_type_index >= 0);
637  for (int j = 0; j < orig_mp->totloop; ++j) {
638  src_blocks_ofs[j] = CustomData_get_n(
639  source_cd, ty, orig_mp->loopstart + j, source_layer_type_index);
640  }
641  void *dst_block_ofs = CustomData_get_n(target_cd, ty, loop_index, target_layer_type_index);
642  CustomData_bmesh_interp_n(target_cd,
643  src_blocks_ofs.data(),
644  weights.data(),
645  nullptr,
646  orig_mp->totloop,
647  dst_block_ofs,
648  target_layer_i);
649  }
650  }
651  }
652 }
653 
660 static void merge_vertex_loop_poly_customdata_layers(Mesh *target, MeshesToIMeshInfo &mim)
661 {
662  for (int mesh_index = 1; mesh_index < mim.meshes.size(); ++mesh_index) {
663  const Mesh *me = mim.meshes[mesh_index];
664  if (me->totvert) {
666  &me->vdata, &target->vdata, CD_MASK_MESH.vmask, CD_DEFAULT, target->totvert);
667  }
668  if (me->totloop) {
670  &me->ldata, &target->ldata, CD_MASK_MESH.lmask, CD_DEFAULT, target->totloop);
671  }
672  if (me->totpoly) {
674  &me->pdata, &target->pdata, CD_MASK_MESH.pmask, CD_DEFAULT, target->totpoly);
675  }
676  }
677 }
678 
679 static void merge_edge_customdata_layers(Mesh *target, MeshesToIMeshInfo &mim)
680 {
681  for (int mesh_index = 1; mesh_index < mim.meshes.size(); ++mesh_index) {
682  const Mesh *me = mim.meshes[mesh_index];
683  if (me->totedge) {
685  &me->edata, &target->edata, CD_MASK_MESH.emask, CD_DEFAULT, target->totedge);
686  }
687  }
688 }
689 
694 static Mesh *imesh_to_mesh(IMesh *im, MeshesToIMeshInfo &mim)
695 {
696  constexpr int dbg_level = 0;
697 
698  im->populate_vert();
699  int out_totvert = im->vert_size();
700  int out_totpoly = im->face_size();
701  int out_totloop = 0;
702  for (const Face *f : im->faces()) {
703  out_totloop += f->size();
704  }
705  /* Will calculate edges later. */
707  mim.meshes[0], out_totvert, 0, 0, out_totloop, out_totpoly);
708 
709  merge_vertex_loop_poly_customdata_layers(result, mim);
710  /* Set the vertex coordinate values and other data. */
711  for (int vi : im->vert_index_range()) {
712  const Vert *v = im->vert(vi);
713  MVert *mv = &result->mvert[vi];
714  copy_v3fl_v3db(mv->co, v->co);
715  if (v->orig != NO_INDEX) {
716  const Mesh *orig_me;
717  int index_in_orig_me;
718  const MVert *orig_mv = mim.input_mvert_for_orig_index(v->orig, &orig_me, &index_in_orig_me);
719  copy_vert_attributes(result, mv, orig_mv, orig_me, vi, index_in_orig_me);
720  }
721  }
722 
723  /* Set the loopstart and totloop for each output poly,
724  * and set the vertices in the appropriate loops. */
725  int cur_loop_index = 0;
726  MLoop *l = result->mloop;
727  for (int fi : im->face_index_range()) {
728  const Face *f = im->face(fi);
729  const Mesh *orig_me;
730  int index_in_orig_me;
731  int orig_me_index;
732  const MPoly *orig_mp = mim.input_mpoly_for_orig_index(
733  f->orig, &orig_me, &orig_me_index, &index_in_orig_me);
734  MPoly *mp = &result->mpoly[fi];
735  mp->totloop = f->size();
736  mp->loopstart = cur_loop_index;
737  for (int j : f->index_range()) {
738  const Vert *vf = f->vert[j];
739  const int vfi = im->lookup_vert(vf);
740  l->v = vfi;
741  ++l;
742  ++cur_loop_index;
743  }
744 
745  copy_poly_attributes(result,
746  mp,
747  orig_mp,
748  orig_me,
749  fi,
750  index_in_orig_me,
751  (mim.material_remaps.size() > 0) ?
752  mim.material_remaps[orig_me_index].as_span() :
753  Span<short>());
754  copy_or_interp_loop_attributes(result, f, mp, orig_mp, orig_me, orig_me_index, mim);
755  }
756 
757  /* BKE_mesh_calc_edges will calculate and populate all the
758  * MEdges from the MPolys. */
759  BKE_mesh_calc_edges(result, false, false);
760  merge_edge_customdata_layers(result, mim);
761 
762  /* Now that the MEdges are populated, we can copy over the required attributes and custom layers.
763  */
764  for (int fi : im->face_index_range()) {
765  const Face *f = im->face(fi);
766  MPoly *mp = &result->mpoly[fi];
767  for (int j : f->index_range()) {
768  if (f->edge_orig[j] != NO_INDEX) {
769  const Mesh *orig_me;
770  int index_in_orig_me;
771  const MEdge *orig_medge = mim.input_medge_for_orig_index(
772  f->edge_orig[j], &orig_me, &index_in_orig_me);
773  int e_index = result->mloop[mp->loopstart + j].e;
774  MEdge *medge = &result->medge[e_index];
775  copy_edge_attributes(result, medge, orig_medge, orig_me, e_index, index_in_orig_me);
776  }
777  }
778  }
779 
780  if (dbg_level > 0) {
781  BKE_mesh_validate(result, true, true);
782  }
783  return result;
784 }
785 
786 #endif // WITH_GMP
787 
789  Span<const float4x4 *> transforms,
790  const float4x4 &target_transform,
791  Span<Array<short>> material_remaps,
792  const bool use_self,
793  const bool hole_tolerant,
794  const int boolean_mode,
795  Vector<int> *r_intersecting_edges)
796 {
797 #ifdef WITH_GMP
798  BLI_assert(meshes.size() == transforms.size());
799  BLI_assert(material_remaps.size() == 0 || material_remaps.size() == meshes.size());
800  if (meshes.size() <= 0) {
801  return nullptr;
802  }
803 
804  const int dbg_level = 0;
805  if (dbg_level > 0) {
806  std::cout << "\nDIRECT_MESH_INTERSECT, nmeshes = " << meshes.size() << "\n";
807  }
808  MeshesToIMeshInfo mim;
809  IMeshArena arena;
810  IMesh m_in = meshes_to_imesh(meshes, transforms, material_remaps, target_transform, arena, &mim);
811  std::function<int(int)> shape_fn = [&mim](int f) {
812  for (int mi = 0; mi < mim.mesh_poly_offset.size() - 1; ++mi) {
813  if (f < mim.mesh_poly_offset[mi + 1]) {
814  return mi;
815  }
816  }
817  return static_cast<int>(mim.mesh_poly_offset.size()) - 1;
818  };
819  IMesh m_out = boolean_mesh(m_in,
820  static_cast<BoolOpType>(boolean_mode),
821  meshes.size(),
822  shape_fn,
823  use_self,
824  hole_tolerant,
825  nullptr,
826  &arena);
827  if (dbg_level > 0) {
828  std::cout << m_out;
829  write_obj_mesh(m_out, "m_out");
830  }
831 
832  Mesh *result = imesh_to_mesh(&m_out, mim);
833 
834  /* Store intersecting edge indices. */
835  if (r_intersecting_edges != nullptr) {
836  for (int fi : m_out.face_index_range()) {
837  const Face &face = *m_out.face(fi);
838  const MPoly &poly = result->mpoly[fi];
839  for (int corner_i : face.index_range()) {
840  if (face.is_intersect[corner_i]) {
841  int e_index = result->mloop[poly.loopstart + corner_i].e;
842  r_intersecting_edges->append(e_index);
843  }
844  }
845  }
846  }
847 
848  return result;
849 #else // WITH_GMP
850  UNUSED_VARS(meshes,
851  transforms,
852  material_remaps,
853  target_transform,
854  use_self,
855  hole_tolerant,
856  boolean_mode,
857  r_intersecting_edges);
858  return nullptr;
859 #endif // WITH_GMP
860 }
861 
862 } // namespace blender::meshintersect
typedef float(TangentPoint)[2]
CustomData interface, see also DNA_customdata_types.h.
bool CustomData_merge(const struct CustomData *source, struct CustomData *dest, eCustomDataMask mask, eCDAllocType alloctype, int totelem)
@ CD_DEFAULT
bool CustomData_layer_has_interp(const struct CustomData *data, int layer_n)
void CustomData_bmesh_interp_n(struct CustomData *data, const void **src_blocks, const float *weights, const float *sub_weights, int count, void *dst_block_ofs, int n)
Definition: customdata.cc:4071
int CustomData_get_named_layer_index(const struct CustomData *data, int type, const char *name)
void CustomData_copy_data_layer(const CustomData *source, CustomData *dest, int src_layer_index, int dst_layer_index, int src_index, int dst_index, int count)
Definition: customdata.cc:3094
void * CustomData_get_n(const struct CustomData *data, int type, int index, int n)
int CustomData_get_named_layer(const struct CustomData *data, int type, const char *name)
const CustomData_MeshMasks CD_MASK_MESH
Definition: customdata.cc:2065
General operations, lookup, etc. for materials.
struct Mesh * BKE_mesh_new_nomain_from_template(const struct Mesh *me_src, int verts_len, int edges_len, int tessface_len, int loops_len, int polys_len)
bool BKE_mesh_validate(struct Mesh *me, bool do_verbose, bool cddata_check_mask)
void BKE_mesh_calc_poly_normal(const struct MPoly *mpoly, const struct MLoop *loopstart, const struct MVert *mvarray, float r_no[3])
void BKE_mesh_calc_edges(struct Mesh *mesh, bool keep_existing_edges, bool select_new_edges)
#define BLI_array_alloca(arr, realsize)
Definition: BLI_alloca.h:22
#define BLI_assert(a)
Definition: BLI_assert.h:46
void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3])
Normal to x,y matrix.
Definition: math_geom.c:3527
void interp_weights_poly_v2(float w[], float v[][2], int n, const float co[2])
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
Definition: math_matrix.c:917
MINLINE void copy_v3fl_v3db(float r[3], const double a[3])
#define UNUSED_VARS(...)
@ CD_MEDGE
@ CD_MVERT
Object is a sort of wrapper for general info.
float float4x4[4][4]
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
constexpr int64_t size() const
Definition: BLI_span.hh:240
void append(const T &value)
Definition: BLI_vector.hh:433
static float verts[][3]
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
#define fabsf(x)
Definition: metal/compat.h:219
Mesh * direct_mesh_boolean(Span< const Mesh * > meshes, Span< const float4x4 * > transforms, const float4x4 &target_transform, Span< Array< short >> material_remaps, bool use_self, bool hole_tolerant, int boolean_mode, Vector< int > *r_intersecting_edges)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Definition: BLI_task.hh:51
struct BMVert * v
Definition: bmesh_class.h:153
struct BMEdge * e
Definition: bmesh_class.h:164
float co[3]
Definition: bmesh_class.h:87
CustomDataLayer * layers
unsigned int v
short mat_nr
float co[3]
struct MEdge * medge
CustomData vdata
struct MVert * mvert
int totedge
int totvert
struct MLoop * mloop
CustomData pdata
int totpoly
CustomData edata
int totloop
struct MPoly * mpoly
CustomData ldata
static float4x4 identity()
Definition: BLI_float4x4.hh:80