Blender  V3.3
mesh_merge_by_distance.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #include "BLI_array.hh"
4 #include "BLI_index_mask.hh"
5 #include "BLI_kdtree.h"
6 #include "BLI_math_vector.h"
7 #include "BLI_math_vector.hh"
8 #include "BLI_vector.hh"
9 
10 #include "DNA_mesh_types.h"
11 #include "DNA_meshdata_types.h"
12 
13 #include "BKE_customdata.h"
14 #include "BKE_mesh.h"
15 
17 
18 //#define USE_WELD_DEBUG
19 //#define USE_WELD_NORMALS
20 
21 namespace blender::geometry {
22 
23 /* Indicates when the element was not computed. */
24 #define OUT_OF_CONTEXT (int)(-1)
25 /* Indicates if the edge or face will be collapsed. */
26 #define ELEM_COLLAPSED (int)(-2)
27 /* indicates whether an edge or vertex in groups_map will be merged. */
28 #define ELEM_MERGED (int)(-2)
29 
30 /* Used to indicate a range in an array specifying a group. */
31 struct WeldGroup {
32  int len;
33  int ofs;
34 };
35 
36 /* Edge groups that will be merged. Final vertices are also indicated. */
37 struct WeldGroupEdge {
38  struct WeldGroup group;
39  int v1;
40  int v2;
41 };
42 
43 struct WeldVert {
44  /* Indexes relative to the original Mesh. */
45  int vert_dest;
46  int vert_orig;
47 };
48 
49 struct WeldEdge {
50  union {
51  int flag;
52  struct {
53  /* Indexes relative to the original Mesh. */
54  int edge_dest;
55  int edge_orig;
56  int vert_a;
57  int vert_b;
58  };
59  };
60 };
61 
62 struct WeldLoop {
63  union {
64  int flag;
65  struct {
66  /* Indexes relative to the original Mesh. */
67  int vert;
68  int edge;
69  int loop_orig;
71  };
72  };
73 };
74 
75 struct WeldPoly {
76  union {
77  int flag;
78  struct {
79  /* Indexes relative to the original Mesh. */
80  int poly_dst;
81  int poly_orig;
83  int loop_end;
84  /* Final Polygon Size. */
85  int loop_len;
86  /* Group of loops that will be affected. */
87  struct WeldGroup loops;
88  };
89  };
90 };
91 
92 struct WeldMesh {
93  /* Group of vertices to be merged. */
96 
97  /* Group of edges to be merged. */
100  /* From the original index of the vertex, this indicates which group it is or is going to be
101  * merged. */
103 
104  /* References all polygons and loops that will be affected. */
108 
109  /* From the actual index of the element in the mesh, it indicates what is the index of the Weld
110  * element above. */
113 
117  int poly_kill_len; /* Including the new polygons. */
118 
119  /* Size of the affected polygon with more sides. */
121 };
122 
125  int loop_end;
129  /* Weld group. */
130  int *group;
131 
132  int l_curr;
133  int l_next;
134 
135  /* Return */
137  int v;
138  int e;
139  char type;
140 };
141 
142 /* -------------------------------------------------------------------- */
146 #ifdef USE_WELD_DEBUG
148  const WeldPoly &wp,
149  Span<WeldLoop> wloop,
150  Span<MLoop> mloop,
151  Span<int> loop_map,
152  int *group_buffer);
153 
155 
156 static void weld_assert_edge_kill_len(Span<WeldEdge> wedge, const int supposed_kill_len)
157 {
158  int kills = 0;
159  const WeldEdge *we = &wedge[0];
160  for (int i = wedge.size(); i--; we++) {
161  int edge_dest = we->edge_dest;
162  /* Magically includes collapsed edges. */
163  if (edge_dest != OUT_OF_CONTEXT) {
164  kills++;
165  }
166  }
167  BLI_assert(kills == supposed_kill_len);
168 }
169 
170 static void weld_assert_poly_and_loop_kill_len(WeldMesh *weld_mesh,
171  Span<MLoop> mloop,
172  Span<MPoly> mpoly,
173  const int supposed_poly_kill_len,
174  const int supposed_loop_kill_len)
175 {
176  int poly_kills = 0;
177  int loop_kills = mloop.size();
178  const MPoly *mp = &mpoly[0];
179  for (int i = 0; i < mpoly.size(); i++, mp++) {
180  int poly_ctx = weld_mesh->poly_map[i];
181  if (poly_ctx != OUT_OF_CONTEXT) {
182  const WeldPoly *wp = &weld_mesh->wpoly[poly_ctx];
183  WeldLoopOfPolyIter iter;
185  iter, *wp, weld_mesh->wloop, mloop, weld_mesh->loop_map, nullptr)) {
186  poly_kills++;
187  continue;
188  }
189  else {
190  if (wp->poly_dst != OUT_OF_CONTEXT) {
191  poly_kills++;
192  continue;
193  }
194  int remain = wp->loop_len;
195  int l = wp->loop_start;
196  while (remain) {
197  int l_next = l + 1;
198  int loop_ctx = weld_mesh->loop_map[l];
199  if (loop_ctx != OUT_OF_CONTEXT) {
200  const WeldLoop *wl = &weld_mesh->wloop[loop_ctx];
201  if (wl->loop_skip_to != OUT_OF_CONTEXT) {
202  l_next = wl->loop_skip_to;
203  }
204  if (wl->flag != ELEM_COLLAPSED) {
205  loop_kills--;
206  remain--;
207  }
208  }
209  else {
210  loop_kills--;
211  remain--;
212  }
213  l = l_next;
214  }
215  }
216  }
217  else {
218  loop_kills -= mp->totloop;
219  }
220  }
221 
222  for (const int i : weld_mesh->wpoly.index_range().take_back(weld_mesh->wpoly_new_len)) {
223  const WeldPoly &wp = weld_mesh->wpoly[i];
224  if (wp.poly_dst != OUT_OF_CONTEXT) {
225  poly_kills++;
226  continue;
227  }
228  int remain = wp.loop_len;
229  int l = wp.loop_start;
230  while (remain) {
231  int l_next = l + 1;
232  int loop_ctx = weld_mesh->loop_map[l];
233  if (loop_ctx != OUT_OF_CONTEXT) {
234  const WeldLoop *wl = &weld_mesh->wloop[loop_ctx];
235  if (wl->loop_skip_to != OUT_OF_CONTEXT) {
236  l_next = wl->loop_skip_to;
237  }
238  if (wl->flag != ELEM_COLLAPSED) {
239  loop_kills--;
240  remain--;
241  }
242  }
243  else {
244  loop_kills--;
245  remain--;
246  }
247  l = l_next;
248  }
249  }
250 
251  BLI_assert(poly_kills == supposed_poly_kill_len);
252  BLI_assert(loop_kills == supposed_loop_kill_len);
253 }
254 
255 static void weld_assert_poly_no_vert_repetition(const WeldPoly &wp,
256  Span<WeldLoop> wloop,
257  Span<MLoop> mloop,
258  Span<int> loop_map)
259 {
260  const int loop_len = wp.loop_len;
261  Array<int, 64> verts(loop_len);
262  WeldLoopOfPolyIter iter;
263  if (!weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr)) {
264  return;
265  }
266  else {
267  int i = 0;
268  while (weld_iter_loop_of_poly_next(iter)) {
269  verts[i++] = iter.v;
270  }
271  }
272  for (int i = 0; i < loop_len; i++) {
273  int va = verts[i];
274  for (int j = i + 1; j < loop_len; j++) {
275  int vb = verts[j];
276  BLI_assert(va != vb);
277  }
278  }
279 }
280 
281 static void weld_assert_poly_len(const WeldPoly *wp, const Span<WeldLoop> wloop)
282 {
283  if (wp->flag == ELEM_COLLAPSED) {
284  return;
285  }
286 
287  int loop_len = wp->loop_len;
288  const WeldLoop *wl = &wloop[wp->loops.ofs];
289  BLI_assert(wp->loop_start <= wl->loop_orig);
290 
291  int end_wloop = wp->loops.ofs + wp->loops.len;
292  const WeldLoop *wl_end = &wloop[end_wloop - 1];
293 
294  int min_len = 0;
295  for (; wl <= wl_end; wl++) {
296  BLI_assert(wl->loop_skip_to == OUT_OF_CONTEXT); /* Not for this case. */
297  if (wl->flag != ELEM_COLLAPSED) {
298  min_len++;
299  }
300  }
301  BLI_assert(loop_len >= min_len);
302 
303  int max_len = wp->loop_end - wp->loop_start + 1;
304  BLI_assert(loop_len <= max_len);
305 }
306 
307 #endif /* USE_WELD_DEBUG */
308 
311 /* -------------------------------------------------------------------- */
316  const int vert_kill_len)
317 {
318  Vector<WeldVert> wvert;
319  wvert.reserve(std::min<int>(2 * vert_kill_len, vert_dest_map.size()));
320 
321  for (const int i : vert_dest_map.index_range()) {
322  if (vert_dest_map[i] != OUT_OF_CONTEXT) {
323  WeldVert wv{};
324  wv.vert_dest = vert_dest_map[i];
325  wv.vert_orig = i;
326  wvert.append(wv);
327  }
328  }
329  return wvert;
330 }
331 
333  Span<int> vert_dest_map,
334  MutableSpan<int> r_vert_groups_map,
335  Array<int> &r_vert_groups_buffer,
336  Array<WeldGroup> &r_vert_groups)
337 {
338  /* Get weld vert groups. */
339 
340  int wgroups_len = 0;
341  for (const int i : vert_dest_map.index_range()) {
342  const int vert_dest = vert_dest_map[i];
343  if (vert_dest != OUT_OF_CONTEXT) {
344  if (vert_dest != i) {
345  r_vert_groups_map[i] = ELEM_MERGED;
346  }
347  else {
348  r_vert_groups_map[i] = wgroups_len;
349  wgroups_len++;
350  }
351  }
352  else {
353  r_vert_groups_map[i] = OUT_OF_CONTEXT;
354  }
355  }
356 
357  r_vert_groups.reinitialize(wgroups_len);
358  r_vert_groups.fill({0, 0});
359  MutableSpan<WeldGroup> wgroups = r_vert_groups;
360 
361  for (const WeldVert &wv : wvert) {
362  int group_index = r_vert_groups_map[wv.vert_dest];
363  wgroups[group_index].len++;
364  }
365 
366  int ofs = 0;
367  for (WeldGroup &wg : wgroups) {
368  wg.ofs = ofs;
369  ofs += wg.len;
370  }
371 
372  BLI_assert(ofs == wvert.size());
373 
374  r_vert_groups_buffer.reinitialize(ofs);
375  for (const WeldVert &wv : wvert) {
376  int group_index = r_vert_groups_map[wv.vert_dest];
377  r_vert_groups_buffer[wgroups[group_index].ofs++] = wv.vert_orig;
378  }
379 
380  for (WeldGroup &wg : wgroups) {
381  wg.ofs -= wg.len;
382  }
383 }
384 
387 /* -------------------------------------------------------------------- */
392  Span<int> vert_dest_map,
393  MutableSpan<int> r_edge_dest_map,
394  MutableSpan<int> r_edge_ctx_map)
395 {
396  /* Edge Context. */
397  int wedge_len = 0;
398 
399  Vector<WeldEdge> wedge;
400  wedge.reserve(medge.size());
401 
402  for (const int i : medge.index_range()) {
403  int v1 = medge[i].v1;
404  int v2 = medge[i].v2;
405  int v_dest_1 = vert_dest_map[v1];
406  int v_dest_2 = vert_dest_map[v2];
407  if ((v_dest_1 != OUT_OF_CONTEXT) || (v_dest_2 != OUT_OF_CONTEXT)) {
408  WeldEdge we{};
409  we.vert_a = (v_dest_1 != OUT_OF_CONTEXT) ? v_dest_1 : v1;
410  we.vert_b = (v_dest_2 != OUT_OF_CONTEXT) ? v_dest_2 : v2;
412  we.edge_orig = i;
413  wedge.append(we);
414  r_edge_dest_map[i] = i;
415  r_edge_ctx_map[i] = wedge_len++;
416  }
417  else {
418  r_edge_dest_map[i] = OUT_OF_CONTEXT;
419  r_edge_ctx_map[i] = OUT_OF_CONTEXT;
420  }
421  }
422 
423  return wedge;
424 }
425 
427  MutableSpan<int> r_edge_dest_map,
428  MutableSpan<WeldEdge> r_wedge,
429  int *r_edge_kiil_len)
430 {
431  /* Setup Edge Overlap. */
432  int edge_kill_len = 0;
433 
434  MutableSpan<WeldGroup> v_links = r_vlinks;
435 
436  for (WeldEdge &we : r_wedge) {
437  int dst_vert_a = we.vert_a;
438  int dst_vert_b = we.vert_b;
439 
440  if (dst_vert_a == dst_vert_b) {
442  r_edge_dest_map[we.edge_orig] = ELEM_COLLAPSED;
443  we.flag = ELEM_COLLAPSED;
444  edge_kill_len++;
445  continue;
446  }
447 
448  v_links[dst_vert_a].len++;
449  v_links[dst_vert_b].len++;
450  }
451 
452  int link_len = 0;
453  for (WeldGroup &vl : r_vlinks) {
454  vl.ofs = link_len;
455  link_len += vl.len;
456  }
457 
458  if (link_len > 0) {
459  Array<int> link_edge_buffer(link_len);
460 
461  for (const int i : r_wedge.index_range()) {
462  const WeldEdge &we = r_wedge[i];
463  if (we.flag == ELEM_COLLAPSED) {
464  continue;
465  }
466 
467  int dst_vert_a = we.vert_a;
468  int dst_vert_b = we.vert_b;
469 
470  link_edge_buffer[v_links[dst_vert_a].ofs++] = i;
471  link_edge_buffer[v_links[dst_vert_b].ofs++] = i;
472  }
473 
474  for (WeldGroup &vl : r_vlinks) {
475  /* Fix offset */
476  vl.ofs -= vl.len;
477  }
478 
479  for (const int i : r_wedge.index_range()) {
480  const WeldEdge &we = r_wedge[i];
481  if (we.edge_dest != OUT_OF_CONTEXT) {
482  /* No need to retest edges.
483  * (Already includes collapsed edges). */
484  continue;
485  }
486 
487  int dst_vert_a = we.vert_a;
488  int dst_vert_b = we.vert_b;
489 
490  struct WeldGroup *link_a = &v_links[dst_vert_a];
491  struct WeldGroup *link_b = &v_links[dst_vert_b];
492 
493  int edges_len_a = link_a->len;
494  int edges_len_b = link_b->len;
495 
496  if (edges_len_a <= 1 || edges_len_b <= 1) {
497  continue;
498  }
499 
500  int *edges_ctx_a = &link_edge_buffer[link_a->ofs];
501  int *edges_ctx_b = &link_edge_buffer[link_b->ofs];
502  int edge_orig = we.edge_orig;
503 
504  for (; edges_len_a--; edges_ctx_a++) {
505  int e_ctx_a = *edges_ctx_a;
506  if (e_ctx_a == i) {
507  continue;
508  }
509  while (edges_len_b && *edges_ctx_b < e_ctx_a) {
510  edges_ctx_b++;
511  edges_len_b--;
512  }
513  if (edges_len_b == 0) {
514  break;
515  }
516  int e_ctx_b = *edges_ctx_b;
517  if (e_ctx_a == e_ctx_b) {
518  WeldEdge *we_b = &r_wedge[e_ctx_b];
519  BLI_assert(ELEM(we_b->vert_a, dst_vert_a, dst_vert_b));
520  BLI_assert(ELEM(we_b->vert_b, dst_vert_a, dst_vert_b));
522  BLI_assert(we_b->edge_orig != edge_orig);
523  r_edge_dest_map[we_b->edge_orig] = edge_orig;
524  we_b->edge_dest = edge_orig;
525  edge_kill_len++;
526  }
527  }
528  }
529 
530 #ifdef USE_WELD_DEBUG
531  weld_assert_edge_kill_len(r_wedge, edge_kill_len);
532 #endif
533  }
534 
535  *r_edge_kiil_len = edge_kill_len;
536 }
537 
538 static void weld_edge_groups_setup(const int medge_len,
539  const int edge_kill_len,
540  MutableSpan<WeldEdge> wedge,
541  Span<int> wedge_map,
542  MutableSpan<int> r_edge_groups_map,
543  Array<int> &r_edge_groups_buffer,
544  Array<WeldGroupEdge> &r_edge_groups)
545 {
546  /* Get weld edge groups. */
547  int wgroups_len = wedge.size() - edge_kill_len;
548  r_edge_groups.reinitialize(wgroups_len);
549  r_edge_groups.fill({{0}});
550  MutableSpan<WeldGroupEdge> wegroups = r_edge_groups;
551 
552  wgroups_len = 0;
553  for (const int i : IndexRange(medge_len)) {
554  int edge_ctx = wedge_map[i];
555  if (edge_ctx != OUT_OF_CONTEXT) {
556  WeldEdge *we = &wedge[edge_ctx];
557  int edge_dest = we->edge_dest;
558  if (edge_dest != OUT_OF_CONTEXT) {
559  BLI_assert(edge_dest != we->edge_orig);
560  r_edge_groups_map[i] = ELEM_MERGED;
561  }
562  else {
563  we->edge_dest = we->edge_orig;
564  wegroups[wgroups_len].v1 = we->vert_a;
565  wegroups[wgroups_len].v2 = we->vert_b;
566  r_edge_groups_map[i] = wgroups_len;
567  wgroups_len++;
568  }
569  }
570  else {
571  r_edge_groups_map[i] = OUT_OF_CONTEXT;
572  }
573  }
574 
575  BLI_assert(wgroups_len == wedge.size() - edge_kill_len);
576 
577  if (wgroups_len == 0) {
578  /* All edges in the context are collapsed. */
579  return;
580  }
581 
582  for (const WeldEdge &we : wedge) {
583  if (we.flag == ELEM_COLLAPSED) {
584  continue;
585  }
586  int group_index = r_edge_groups_map[we.edge_dest];
587  wegroups[group_index].group.len++;
588  }
589 
590  int ofs = 0;
591  for (WeldGroupEdge &wegrp : wegroups) {
592  wegrp.group.ofs = ofs;
593  ofs += wegrp.group.len;
594  }
595 
596  r_edge_groups_buffer.reinitialize(ofs);
597  for (const WeldEdge &we : wedge) {
598  if (we.flag == ELEM_COLLAPSED) {
599  continue;
600  }
601  int group_index = r_edge_groups_map[we.edge_dest];
602  r_edge_groups_buffer[wegroups[group_index].group.ofs++] = we.edge_orig;
603  }
604 
605  for (WeldGroupEdge &wegrp : wegroups) {
606  wegrp.group.ofs -= wegrp.group.len;
607  }
608 }
609 
612 /* -------------------------------------------------------------------- */
617  const WeldPoly &wp,
618  Span<WeldLoop> wloop,
619  Span<MLoop> mloop,
620  Span<int> loop_map,
621  int *group_buffer)
622 {
623  if (wp.flag == ELEM_COLLAPSED) {
624  return false;
625  }
626 
627  iter.loop_start = wp.loop_start;
628  iter.loop_end = wp.loop_end;
629  iter.wloop = wloop;
630  iter.mloop = mloop;
631  iter.loop_map = loop_map;
632  iter.group = group_buffer;
633 
634  int group_len = 0;
635  if (group_buffer) {
636  /* First loop group needs more attention. */
637  int loop_start, loop_end, l;
638  loop_start = iter.loop_start;
639  loop_end = l = iter.loop_end;
640  while (l >= loop_start) {
641  const int loop_ctx = loop_map[l];
642  if (loop_ctx != OUT_OF_CONTEXT) {
643  const WeldLoop *wl = &wloop[loop_ctx];
644  if (wl->flag == ELEM_COLLAPSED) {
645  l--;
646  continue;
647  }
648  }
649  break;
650  }
651  if (l != loop_end) {
652  group_len = loop_end - l;
653  int i = 0;
654  while (l < loop_end) {
655  iter.group[i++] = ++l;
656  }
657  }
658  }
659  iter.group_len = group_len;
660 
661  iter.l_next = iter.loop_start;
662 #ifdef USE_WELD_DEBUG
663  iter.v = OUT_OF_CONTEXT;
664 #endif
665  return true;
666 }
667 
669 {
670  const int loop_end = iter.loop_end;
671  Span<WeldLoop> wloop = iter.wloop;
672  Span<int> loop_map = iter.loop_map;
673  int l = iter.l_curr = iter.l_next;
674  if (l == iter.loop_start) {
675  /* `grupo_len` is already calculated in the first loop */
676  }
677  else {
678  iter.group_len = 0;
679  }
680  while (l <= loop_end) {
681  int l_next = l + 1;
682  const int loop_ctx = loop_map[l];
683  if (loop_ctx != OUT_OF_CONTEXT) {
684  const WeldLoop *wl = &wloop[loop_ctx];
685  if (wl->loop_skip_to != OUT_OF_CONTEXT) {
686  l_next = wl->loop_skip_to;
687  }
688  if (wl->flag == ELEM_COLLAPSED) {
689  if (iter.group) {
690  iter.group[iter.group_len++] = l;
691  }
692  l = l_next;
693  continue;
694  }
695 #ifdef USE_WELD_DEBUG
696  BLI_assert(iter.v != wl->vert);
697 #endif
698  iter.v = wl->vert;
699  iter.e = wl->edge;
700  iter.type = 1;
701  }
702  else {
703  const MLoop &ml = iter.mloop[l];
704 #ifdef USE_WELD_DEBUG
705  BLI_assert((uint)iter.v != ml.v);
706 #endif
707  iter.v = ml.v;
708  iter.e = ml.e;
709  iter.type = 0;
710  }
711  if (iter.group) {
712  iter.group[iter.group_len++] = l;
713  }
714  iter.l_next = l_next;
715  return true;
716  }
717 
718  return false;
719 }
720 
722  Span<MLoop> mloop,
723  Span<int> vert_dest_map,
724  Span<int> edge_dest_map,
725  WeldMesh *r_weld_mesh)
726 {
727  /* Loop/Poly Context. */
728  Array<int> loop_map(mloop.size());
729  Array<int> poly_map(mpoly.size());
730  int wloop_len = 0;
731  int wpoly_len = 0;
732  int max_ctx_poly_len = 4;
733 
734  Vector<WeldLoop> wloop;
735  wloop.reserve(mloop.size());
736 
737  Vector<WeldPoly> wpoly;
738  wpoly.reserve(mpoly.size());
739 
740  int maybe_new_poly = 0;
741 
742  for (const int i : mpoly.index_range()) {
743  const MPoly &mp = mpoly[i];
744  const int loopstart = mp.loopstart;
745  const int totloop = mp.totloop;
746 
747  int vert_ctx_len = 0;
748 
749  int prev_wloop_len = wloop_len;
750  for (const int i_loop : mloop.index_range().slice(loopstart, totloop)) {
751  int v = mloop[i_loop].v;
752  int e = mloop[i_loop].e;
753  int v_dest = vert_dest_map[v];
754  int e_dest = edge_dest_map[e];
755  bool is_vert_ctx = v_dest != OUT_OF_CONTEXT;
756  bool is_edge_ctx = e_dest != OUT_OF_CONTEXT;
757  if (is_vert_ctx) {
758  vert_ctx_len++;
759  }
760  if (is_vert_ctx || is_edge_ctx) {
761  WeldLoop wl{};
762  wl.vert = is_vert_ctx ? v_dest : v;
763  wl.edge = is_edge_ctx ? e_dest : e;
764  wl.loop_orig = i_loop;
765  wl.loop_skip_to = OUT_OF_CONTEXT;
766  wloop.append(wl);
767 
768  loop_map[i_loop] = wloop_len++;
769  }
770  else {
771  loop_map[i_loop] = OUT_OF_CONTEXT;
772  }
773  }
774  if (wloop_len != prev_wloop_len) {
775  int loops_len = wloop_len - prev_wloop_len;
776  WeldPoly wp{};
778  wp.poly_orig = i;
779  wp.loops.len = loops_len;
780  wp.loops.ofs = prev_wloop_len;
781  wp.loop_start = loopstart;
782  wp.loop_end = loopstart + totloop - 1;
783  wp.loop_len = totloop;
784  wpoly.append(wp);
785 
786  poly_map[i] = wpoly_len++;
787  if (totloop > 5 && vert_ctx_len > 1) {
788  int max_new = (totloop / 3) - 1;
789  vert_ctx_len /= 2;
790  maybe_new_poly += MIN2(max_new, vert_ctx_len);
791  CLAMP_MIN(max_ctx_poly_len, totloop);
792  }
793  }
794  else {
795  poly_map[i] = OUT_OF_CONTEXT;
796  }
797  }
798 
799  wpoly.reserve(wpoly.size() + maybe_new_poly);
800 
801  r_weld_mesh->wloop = std::move(wloop);
802  r_weld_mesh->wpoly = std::move(wpoly);
803  r_weld_mesh->wpoly_new_len = 0;
804  r_weld_mesh->loop_map = std::move(loop_map);
805  r_weld_mesh->poly_map = std::move(poly_map);
806  r_weld_mesh->max_poly_len = max_ctx_poly_len;
807 }
808 
809 static void weld_poly_split_recursive(Span<int> vert_dest_map,
810 #ifdef USE_WELD_DEBUG
811  const Span<MLoop> mloop,
812 #endif
813  int ctx_verts_len,
814  WeldPoly *r_wp,
815  WeldMesh *r_weld_mesh,
816  int *r_poly_kill,
817  int *r_loop_kill)
818 {
819  int poly_loop_len = r_wp->loop_len;
820  if (poly_loop_len < 3 || ctx_verts_len < 1) {
821  return;
822  }
823 
824  const int ctx_loops_len = r_wp->loops.len;
825  const int ctx_loops_ofs = r_wp->loops.ofs;
826  MutableSpan<WeldLoop> wloop = r_weld_mesh->wloop;
827 
828  int loop_kill = 0;
829 
830  WeldLoop *poly_loops = &wloop[ctx_loops_ofs];
831  WeldLoop *wla = &poly_loops[0];
832  WeldLoop *wla_prev = &poly_loops[ctx_loops_len - 1];
833  while (wla_prev->flag == ELEM_COLLAPSED) {
834  wla_prev--;
835  }
836  const int la_len = ctx_loops_len - 1;
837  for (int la = 0; la < la_len; la++, wla++) {
838  wa_continue:
839  if (wla->flag == ELEM_COLLAPSED) {
840  continue;
841  }
842  int vert_a = wla->vert;
843  /* Only test vertices that will be merged. */
844  if (vert_dest_map[vert_a] != OUT_OF_CONTEXT) {
845  int lb = la + 1;
846  WeldLoop *wlb = wla + 1;
847  WeldLoop *wlb_prev = wla;
848  int killed_ab = 0;
849  ctx_verts_len = 1;
850  for (; lb < ctx_loops_len; lb++, wlb++) {
852  if (wlb->flag == ELEM_COLLAPSED) {
853  killed_ab++;
854  continue;
855  }
856  int vert_b = wlb->vert;
857  if (vert_dest_map[vert_b] != OUT_OF_CONTEXT) {
858  ctx_verts_len++;
859  }
860  if (vert_a == vert_b) {
861  const int dist_a = wlb->loop_orig - wla->loop_orig - killed_ab;
862  const int dist_b = poly_loop_len - dist_a;
863 
864  BLI_assert(dist_a != 0 && dist_b != 0);
865  if (dist_a == 1 || dist_b == 1) {
866  BLI_assert(dist_a != dist_b);
867  BLI_assert((wla->flag == ELEM_COLLAPSED) || (wlb->flag == ELEM_COLLAPSED));
868  }
869  else {
870  WeldLoop *wl_tmp = nullptr;
871  if (dist_a == 2) {
872  wl_tmp = wlb_prev;
873  BLI_assert(wla->flag != ELEM_COLLAPSED);
874  BLI_assert(wl_tmp->flag != ELEM_COLLAPSED);
875  wla->flag = ELEM_COLLAPSED;
876  wl_tmp->flag = ELEM_COLLAPSED;
877  loop_kill += 2;
878  poly_loop_len -= 2;
879  }
880  if (dist_b == 2) {
881  if (wl_tmp != nullptr) {
882  r_wp->flag = ELEM_COLLAPSED;
883  *r_poly_kill += 1;
884  }
885  else {
886  wl_tmp = wla_prev;
887  BLI_assert(wlb->flag != ELEM_COLLAPSED);
888  BLI_assert(wl_tmp->flag != ELEM_COLLAPSED);
889  wlb->flag = ELEM_COLLAPSED;
890  wl_tmp->flag = ELEM_COLLAPSED;
891  }
892  loop_kill += 2;
893  poly_loop_len -= 2;
894  }
895  if (wl_tmp == nullptr) {
896  const int new_loops_len = lb - la;
897  const int new_loops_ofs = ctx_loops_ofs + la;
898 
899  r_weld_mesh->wpoly.increase_size_by_unchecked(1);
900  WeldPoly *new_wp = &r_weld_mesh->wpoly.last();
901  new_wp->poly_dst = OUT_OF_CONTEXT;
902  new_wp->poly_orig = r_wp->poly_orig;
903  new_wp->loops.len = new_loops_len;
904  new_wp->loops.ofs = new_loops_ofs;
905  new_wp->loop_start = wla->loop_orig;
906  new_wp->loop_end = wlb_prev->loop_orig;
907  new_wp->loop_len = dist_a;
908  r_weld_mesh->wpoly_new_len++;
909  weld_poly_split_recursive(vert_dest_map,
910 #ifdef USE_WELD_DEBUG
911  mloop,
912 #endif
913  ctx_verts_len,
914  new_wp,
915  r_weld_mesh,
916  r_poly_kill,
917  r_loop_kill);
918  BLI_assert(dist_b == poly_loop_len - dist_a);
919  poly_loop_len = dist_b;
920  if (wla_prev->loop_orig > wla->loop_orig) {
921  /* New start. */
922  r_wp->loop_start = wlb->loop_orig;
923  }
924  else {
925  /* The `loop_start` doesn't change but some loops must be skipped. */
926  wla_prev->loop_skip_to = wlb->loop_orig;
927  }
928  wla = wlb;
929  la = lb;
930  goto wa_continue;
931  }
932  break;
933  }
934  }
935  if (wlb->flag != ELEM_COLLAPSED) {
936  wlb_prev = wlb;
937  }
938  }
939  }
940  if (wla->flag != ELEM_COLLAPSED) {
941  wla_prev = wla;
942  }
943  }
944  r_wp->loop_len = poly_loop_len;
945  *r_loop_kill += loop_kill;
946 
947 #ifdef USE_WELD_DEBUG
948  weld_assert_poly_no_vert_repetition(*r_wp, wloop, mloop, r_weld_mesh->loop_map);
949 #endif
950 }
951 
953 #ifdef USE_WELD_DEBUG
954  Span<MPoly> mpoly,
955 #endif
956  const int mvert_len,
957  Span<int> vert_dest_map,
958  const int remain_edge_ctx_len,
959  MutableSpan<WeldGroup> r_vlinks,
960  WeldMesh *r_weld_mesh)
961 {
962  WeldPoly *wpoly = r_weld_mesh->wpoly.data();
963  MutableSpan<WeldLoop> wloop = r_weld_mesh->wloop;
964  int poly_kill_len = 0;
965  int loop_kill_len = 0;
966 
967  Span<int> loop_map = r_weld_mesh->loop_map;
968 
969  if (remain_edge_ctx_len) {
970 
971  /* Setup Poly/Loop. */
972  /* `wpoly.size()` may change during the loop,
973  * so make it clear that we are only working with the original wpolys. */
974  IndexRange wpoly_original_range = r_weld_mesh->wpoly.index_range();
975  for (const int i : wpoly_original_range) {
976  WeldPoly &wp = wpoly[i];
977  const int ctx_loops_len = wp.loops.len;
978  const int ctx_loops_ofs = wp.loops.ofs;
979 
980  int poly_loop_len = wp.loop_len;
981  int ctx_verts_len = 0;
982  WeldLoop *wl = &wloop[ctx_loops_ofs];
983  for (int l = ctx_loops_len; l--; wl++) {
984  const int edge_dest = wl->edge;
985  if (edge_dest == ELEM_COLLAPSED) {
986  wl->flag = ELEM_COLLAPSED;
987  if (poly_loop_len == 3) {
988  wp.flag = ELEM_COLLAPSED;
989  poly_kill_len++;
990  loop_kill_len += 3;
991  poly_loop_len = 0;
992  break;
993  }
994  loop_kill_len++;
995  poly_loop_len--;
996  }
997  else {
998  const int vert_dst = wl->vert;
999  if (vert_dest_map[vert_dst] != OUT_OF_CONTEXT) {
1000  ctx_verts_len++;
1001  }
1002  }
1003  }
1004 
1005  if (poly_loop_len) {
1006  wp.loop_len = poly_loop_len;
1007 #ifdef USE_WELD_DEBUG
1008  weld_assert_poly_len(&wp, wloop);
1009 #endif
1010 
1011  weld_poly_split_recursive(vert_dest_map,
1012 #ifdef USE_WELD_DEBUG
1013  mloop,
1014 #endif
1015  ctx_verts_len,
1016  &wp,
1017  r_weld_mesh,
1018  &poly_kill_len,
1019  &loop_kill_len);
1020  }
1021  }
1022 
1023 #ifdef USE_WELD_DEBUG
1024  weld_assert_poly_and_loop_kill_len(r_weld_mesh, mloop, mpoly, poly_kill_len, loop_kill_len);
1025 #endif
1026 
1027  /* Setup Polygon Overlap. */
1028 
1029  r_vlinks.fill({0, 0});
1030  MutableSpan<WeldGroup> v_links = r_vlinks;
1031 
1032  for (const WeldPoly &wp : r_weld_mesh->wpoly) {
1033  WeldLoopOfPolyIter iter;
1034  if (weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr)) {
1035  while (weld_iter_loop_of_poly_next(iter)) {
1036  v_links[iter.v].len++;
1037  }
1038  }
1039  }
1040 
1041  int link_len = 0;
1042  for (const int i : IndexRange(mvert_len)) {
1043  v_links[i].ofs = link_len;
1044  link_len += v_links[i].len;
1045  }
1046 
1047  if (link_len) {
1048  Array<int> link_poly_buffer(link_len);
1049 
1050  for (const int i : IndexRange(r_weld_mesh->wpoly.size())) {
1051  const WeldPoly &wp = wpoly[i];
1052  WeldLoopOfPolyIter iter;
1053  if (weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr)) {
1054  while (weld_iter_loop_of_poly_next(iter)) {
1055  link_poly_buffer[v_links[iter.v].ofs++] = i;
1056  }
1057  }
1058  }
1059 
1060  for (WeldGroup &vl : r_vlinks) {
1061  /* Fix offset */
1062  vl.ofs -= vl.len;
1063  }
1064 
1065  int polys_len_a, polys_len_b, *polys_ctx_a, *polys_ctx_b, p_ctx_a, p_ctx_b;
1066  polys_len_b = p_ctx_b = 0; /* silence warnings */
1067 
1068  for (const int i : IndexRange(r_weld_mesh->wpoly.size())) {
1069  const WeldPoly &wp = wpoly[i];
1070  if (wp.poly_dst != OUT_OF_CONTEXT) {
1071  /* No need to retest poly.
1072  * (Already includes collapsed polygons). */
1073  continue;
1074  }
1075 
1076  WeldLoopOfPolyIter iter;
1077  weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr);
1079  struct WeldGroup *link_a = &v_links[iter.v];
1080  polys_len_a = link_a->len;
1081  if (polys_len_a == 1) {
1082  BLI_assert(link_poly_buffer[link_a->ofs] == i);
1083  continue;
1084  }
1085  int wp_loop_len = wp.loop_len;
1086  polys_ctx_a = &link_poly_buffer[link_a->ofs];
1087  for (; polys_len_a--; polys_ctx_a++) {
1088  p_ctx_a = *polys_ctx_a;
1089  if (p_ctx_a == i) {
1090  continue;
1091  }
1092 
1093  WeldPoly *wp_tmp = &wpoly[p_ctx_a];
1094  if (wp_tmp->loop_len != wp_loop_len) {
1095  continue;
1096  }
1097 
1098  WeldLoopOfPolyIter iter_b = iter;
1099  while (weld_iter_loop_of_poly_next(iter_b)) {
1100  struct WeldGroup *link_b = &v_links[iter_b.v];
1101  polys_len_b = link_b->len;
1102  if (polys_len_b == 1) {
1103  BLI_assert(link_poly_buffer[link_b->ofs] == i);
1104  polys_len_b = 0;
1105  break;
1106  }
1107 
1108  polys_ctx_b = &link_poly_buffer[link_b->ofs];
1109  for (; polys_len_b; polys_len_b--, polys_ctx_b++) {
1110  p_ctx_b = *polys_ctx_b;
1111  if (p_ctx_b < p_ctx_a) {
1112  continue;
1113  }
1114  if (p_ctx_b >= p_ctx_a) {
1115  if (p_ctx_b > p_ctx_a) {
1116  polys_len_b = 0;
1117  }
1118  break;
1119  }
1120  }
1121  if (polys_len_b == 0) {
1122  break;
1123  }
1124  }
1125  if (polys_len_b == 0) {
1126  continue;
1127  }
1128  BLI_assert(p_ctx_a > i);
1129  BLI_assert(p_ctx_a == p_ctx_b);
1130  BLI_assert(wp_tmp->poly_dst == OUT_OF_CONTEXT);
1131  BLI_assert(wp_tmp != &wp);
1132  wp_tmp->poly_dst = wp.poly_orig;
1133  loop_kill_len += wp_tmp->loop_len;
1134  poly_kill_len++;
1135  }
1136  }
1137  }
1138  }
1139  else {
1140  poly_kill_len = r_weld_mesh->wpoly.size();
1141  loop_kill_len = r_weld_mesh->wloop.size();
1142 
1143  for (WeldPoly &wp : r_weld_mesh->wpoly) {
1144  wp.flag = ELEM_COLLAPSED;
1145  }
1146  }
1147 
1148 #ifdef USE_WELD_DEBUG
1149  weld_assert_poly_and_loop_kill_len(r_weld_mesh, mloop, mpoly, poly_kill_len, loop_kill_len);
1150 #endif
1151 
1152  r_weld_mesh->poly_kill_len = poly_kill_len;
1153  r_weld_mesh->loop_kill_len = loop_kill_len;
1154 }
1155 
1158 /* -------------------------------------------------------------------- */
1163  MutableSpan<int> vert_dest_map,
1164  const int vert_kill_len,
1165  WeldMesh *r_weld_mesh)
1166 {
1167  Span<MEdge> medge{mesh.medge, mesh.totedge};
1168  Span<MPoly> mpoly{mesh.mpoly, mesh.totpoly};
1169  Span<MLoop> mloop{mesh.mloop, mesh.totloop};
1170  const int mvert_len = mesh.totvert;
1171 
1172  Vector<WeldVert> wvert = weld_vert_ctx_alloc_and_setup(vert_dest_map, vert_kill_len);
1173  r_weld_mesh->vert_kill_len = vert_kill_len;
1174 
1175  Array<int> edge_dest_map(medge.size());
1176  Array<int> edge_ctx_map(medge.size());
1177  Vector<WeldEdge> wedge = weld_edge_ctx_alloc(medge, vert_dest_map, edge_dest_map, edge_ctx_map);
1178 
1179  Array<WeldGroup> v_links(mvert_len, {0, 0});
1180  weld_edge_ctx_setup(v_links, edge_dest_map, wedge, &r_weld_mesh->edge_kill_len);
1181 
1182  weld_poly_loop_ctx_alloc(mpoly, mloop, vert_dest_map, edge_dest_map, r_weld_mesh);
1183 
1185 #ifdef USE_WELD_DEBUG
1186  mpoly,
1187 
1188 #endif
1189  mvert_len,
1190  vert_dest_map,
1191  wedge.size() - r_weld_mesh->edge_kill_len,
1192  v_links,
1193  r_weld_mesh);
1194 
1195  weld_vert_groups_setup(wvert,
1196  vert_dest_map,
1197  vert_dest_map,
1198  r_weld_mesh->vert_groups_buffer,
1199  r_weld_mesh->vert_groups);
1200 
1201  weld_edge_groups_setup(medge.size(),
1202  r_weld_mesh->edge_kill_len,
1203  wedge,
1204  edge_ctx_map,
1205  edge_dest_map,
1206  r_weld_mesh->edge_groups_buffer,
1207  r_weld_mesh->edge_groups);
1208 
1209  r_weld_mesh->edge_groups_map = std::move(edge_dest_map);
1210 }
1211 
1214 /* -------------------------------------------------------------------- */
1218 static void customdata_weld(
1219  const CustomData *source, CustomData *dest, const int *src_indices, int count, int dest_index)
1220 {
1221  if (count == 1) {
1222  CustomData_copy_data(source, dest, src_indices[0], dest_index, 1);
1223  return;
1224  }
1225 
1226  CustomData_interp(source, dest, (const int *)src_indices, nullptr, nullptr, count, dest_index);
1227 
1228  int src_i, dest_i;
1229  int j;
1230 
1231  float co[3] = {0.0f, 0.0f, 0.0f};
1232 #ifdef USE_WELD_NORMALS
1233  float no[3] = {0.0f, 0.0f, 0.0f};
1234 #endif
1235  int crease = 0;
1236  int bweight = 0;
1237  short flag = 0;
1238 
1239  /* interpolates a layer at a time */
1240  dest_i = 0;
1241  for (src_i = 0; src_i < source->totlayer; src_i++) {
1242  const int type = source->layers[src_i].type;
1243 
1244  /* find the first dest layer with type >= the source type
1245  * (this should work because layers are ordered by type)
1246  */
1247  while (dest_i < dest->totlayer && dest->layers[dest_i].type < type) {
1248  dest_i++;
1249  }
1250 
1251  /* if there are no more dest layers, we're done */
1252  if (dest_i == dest->totlayer) {
1253  break;
1254  }
1255 
1256  /* if we found a matching layer, add the data */
1257  if (dest->layers[dest_i].type == type) {
1258  void *src_data = source->layers[src_i].data;
1259 
1260  if (type == CD_MVERT) {
1261  for (j = 0; j < count; j++) {
1262  MVert *mv_src = &((MVert *)src_data)[src_indices[j]];
1263  add_v3_v3(co, mv_src->co);
1264 #ifdef USE_WELD_NORMALS
1265  short *mv_src_no = mv_src->no;
1266  no[0] += mv_src_no[0];
1267  no[1] += mv_src_no[1];
1268  no[2] += mv_src_no[2];
1269 #endif
1270  bweight += mv_src->bweight;
1271  flag |= mv_src->flag;
1272  }
1273  }
1274  else if (type == CD_MEDGE) {
1275  for (j = 0; j < count; j++) {
1276  MEdge *me_src = &((MEdge *)src_data)[src_indices[j]];
1277  crease += me_src->crease;
1278  bweight += me_src->bweight;
1279  flag |= me_src->flag;
1280  }
1281  }
1282  else if (CustomData_layer_has_interp(dest, dest_i)) {
1283  /* Already calculated.
1284  * TODO: Optimize by exposing `typeInfo->interp`. */
1285  }
1286  else if (CustomData_layer_has_math(dest, dest_i)) {
1287  const int size = CustomData_sizeof(type);
1288  void *dst_data = dest->layers[dest_i].data;
1289  void *v_dst = POINTER_OFFSET(dst_data, (size_t)dest_index * size);
1290  for (j = 0; j < count; j++) {
1292  type, v_dst, POINTER_OFFSET(src_data, (size_t)src_indices[j] * size));
1293  }
1294  }
1295  else {
1296  CustomData_copy_layer_type_data(source, dest, type, src_indices[0], dest_index, 1);
1297  }
1298 
1299  /* if there are multiple source & dest layers of the same type,
1300  * we don't want to copy all source layers to the same dest, so
1301  * increment dest_i
1302  */
1303  dest_i++;
1304  }
1305  }
1306 
1307  float fac = 1.0f / count;
1308 
1309  for (dest_i = 0; dest_i < dest->totlayer; dest_i++) {
1310  CustomDataLayer *layer_dst = &dest->layers[dest_i];
1311  const int type = layer_dst->type;
1312  if (type == CD_MVERT) {
1313  MVert *mv = &((MVert *)layer_dst->data)[dest_index];
1314  mul_v3_fl(co, fac);
1315  bweight *= fac;
1316  CLAMP_MAX(bweight, 255);
1317 
1318  copy_v3_v3(mv->co, co);
1319 #ifdef USE_WELD_NORMALS
1320  mul_v3_fl(no, fac);
1321  short *mv_no = mv->no;
1322  mv_no[0] = (short)no[0];
1323  mv_no[1] = (short)no[1];
1324  mv_no[2] = (short)no[2];
1325 #endif
1326 
1327  mv->flag = (char)flag;
1328  mv->bweight = (char)bweight;
1329  }
1330  else if (type == CD_MEDGE) {
1331  MEdge *me = &((MEdge *)layer_dst->data)[dest_index];
1332  crease *= fac;
1333  bweight *= fac;
1334  CLAMP_MAX(crease, 255);
1335  CLAMP_MAX(bweight, 255);
1336 
1337  me->crease = (char)crease;
1338  me->bweight = (char)bweight;
1339  me->flag = flag;
1340  }
1341  else if (CustomData_layer_has_interp(dest, dest_i)) {
1342  /* Already calculated. */
1343  }
1344  else if (CustomData_layer_has_math(dest, dest_i)) {
1345  const int size = CustomData_sizeof(type);
1346  void *dst_data = layer_dst->data;
1347  void *v_dst = POINTER_OFFSET(dst_data, (size_t)dest_index * size);
1348  CustomData_data_multiply(type, v_dst, fac);
1349  }
1350  }
1351 }
1352 
1355 /* -------------------------------------------------------------------- */
1360  MutableSpan<int> vert_dest_map,
1361  const int removed_vertex_count)
1362 {
1363  Span<MPoly> mpoly{mesh.mpoly, mesh.totpoly};
1364  Span<MLoop> mloop{mesh.mloop, mesh.totloop};
1365  const int totvert = mesh.totvert;
1366  const int totedge = mesh.totedge;
1367  const int totloop = mesh.totloop;
1368  const int totpoly = mesh.totpoly;
1369 
1370  WeldMesh weld_mesh;
1371  weld_mesh_context_create(mesh, vert_dest_map, removed_vertex_count, &weld_mesh);
1372 
1373  const int result_nverts = totvert - weld_mesh.vert_kill_len;
1374  const int result_nedges = totedge - weld_mesh.edge_kill_len;
1375  const int result_nloops = totloop - weld_mesh.loop_kill_len;
1376  const int result_npolys = totpoly - weld_mesh.poly_kill_len + weld_mesh.wpoly_new_len;
1377 
1379  &mesh, result_nverts, result_nedges, 0, result_nloops, result_npolys);
1380 
1381  /* Vertices. */
1382 
1383  /* Be careful when editing this array, to avoid new allocations it uses the same buffer as
1384  * #vert_dest_map. This map will be used to adjust the edges, polys and loops. */
1385  MutableSpan<int> vert_final = vert_dest_map;
1386 
1387  int dest_index = 0;
1388  for (int i = 0; i < totvert; i++) {
1389  int source_index = i;
1390  int count = 0;
1391  while (i < totvert && vert_dest_map[i] == OUT_OF_CONTEXT) {
1392  vert_final[i] = dest_index + count;
1393  count++;
1394  i++;
1395  }
1396  if (count) {
1397  CustomData_copy_data(&mesh.vdata, &result->vdata, source_index, dest_index, count);
1398  dest_index += count;
1399  }
1400  if (i == totvert) {
1401  break;
1402  }
1403  if (vert_dest_map[i] != ELEM_MERGED) {
1404  struct WeldGroup *wgroup = &weld_mesh.vert_groups[vert_dest_map[i]];
1406  &result->vdata,
1407  &weld_mesh.vert_groups_buffer[wgroup->ofs],
1408  wgroup->len,
1409  dest_index);
1410  vert_final[i] = dest_index;
1411  dest_index++;
1412  }
1413  }
1414 
1415  BLI_assert(dest_index == result_nverts);
1416 
1417  /* Edges. */
1418 
1419  /* Be careful when editing this array, to avoid new allocations it uses the same buffer as
1420  * #edge_groups_map. This map will be used to adjust the polys and loops. */
1421  MutableSpan<int> edge_final = weld_mesh.edge_groups_map;
1422 
1423  dest_index = 0;
1424  for (int i = 0; i < totedge; i++) {
1425  const int source_index = i;
1426  int count = 0;
1427  while (i < totedge && weld_mesh.edge_groups_map[i] == OUT_OF_CONTEXT) {
1428  edge_final[i] = dest_index + count;
1429  count++;
1430  i++;
1431  }
1432  if (count) {
1433  CustomData_copy_data(&mesh.edata, &result->edata, source_index, dest_index, count);
1434  MEdge *me = &result->medge[dest_index];
1435  dest_index += count;
1436  for (; count--; me++) {
1437  me->v1 = vert_final[me->v1];
1438  me->v2 = vert_final[me->v2];
1439  }
1440  }
1441  if (i == totedge) {
1442  break;
1443  }
1444  if (weld_mesh.edge_groups_map[i] != ELEM_MERGED) {
1445  struct WeldGroupEdge *wegrp = &weld_mesh.edge_groups[weld_mesh.edge_groups_map[i]];
1447  &result->edata,
1448  &weld_mesh.edge_groups_buffer[wegrp->group.ofs],
1449  wegrp->group.len,
1450  dest_index);
1451  MEdge *me = &result->medge[dest_index];
1452  me->v1 = vert_final[wegrp->v1];
1453  me->v2 = vert_final[wegrp->v2];
1454  /* "For now, assume that all merged edges are loose. This flag will be cleared in the
1455  * Polys/Loops step". */
1456  me->flag |= ME_LOOSEEDGE;
1457 
1458  edge_final[i] = dest_index;
1459  dest_index++;
1460  }
1461  }
1462 
1463  BLI_assert(dest_index == result_nedges);
1464 
1465  /* Polys/Loops. */
1466 
1467  MPoly *r_mp = &result->mpoly[0];
1468  MLoop *r_ml = &result->mloop[0];
1469  int r_i = 0;
1470  int loop_cur = 0;
1471  Array<int, 64> group_buffer(weld_mesh.max_poly_len);
1472  for (const int i : mpoly.index_range()) {
1473  const MPoly &mp = mpoly[i];
1474  const int loop_start = loop_cur;
1475  const int poly_ctx = weld_mesh.poly_map[i];
1476  if (poly_ctx == OUT_OF_CONTEXT) {
1477  int mp_loop_len = mp.totloop;
1478  CustomData_copy_data(&mesh.ldata, &result->ldata, mp.loopstart, loop_cur, mp_loop_len);
1479  loop_cur += mp_loop_len;
1480  for (; mp_loop_len--; r_ml++) {
1481  r_ml->v = vert_final[r_ml->v];
1482  r_ml->e = edge_final[r_ml->e];
1483  }
1484  }
1485  else {
1486  const WeldPoly &wp = weld_mesh.wpoly[poly_ctx];
1487  WeldLoopOfPolyIter iter;
1489  iter, wp, weld_mesh.wloop, mloop, weld_mesh.loop_map, group_buffer.data())) {
1490  continue;
1491  }
1492 
1493  if (wp.poly_dst != OUT_OF_CONTEXT) {
1494  continue;
1495  }
1496  while (weld_iter_loop_of_poly_next(iter)) {
1498  &mesh.ldata, &result->ldata, group_buffer.data(), iter.group_len, loop_cur);
1499  int v = vert_final[iter.v];
1500  int e = edge_final[iter.e];
1501  r_ml->v = v;
1502  r_ml->e = e;
1503  r_ml++;
1504  loop_cur++;
1505  if (iter.type) {
1506  result->medge[e].flag &= ~ME_LOOSEEDGE;
1507  }
1508  BLI_assert((result->medge[e].flag & ME_LOOSEEDGE) == 0);
1509  }
1510  }
1511 
1512  CustomData_copy_data(&mesh.pdata, &result->pdata, i, r_i, 1);
1513  r_mp->loopstart = loop_start;
1514  r_mp->totloop = loop_cur - loop_start;
1515  r_mp++;
1516  r_i++;
1517  }
1518 
1519  /* New Polygons. */
1520  for (const int i : weld_mesh.wpoly.index_range().take_back(weld_mesh.wpoly_new_len)) {
1521  const WeldPoly &wp = weld_mesh.wpoly[i];
1522  const int loop_start = loop_cur;
1523  WeldLoopOfPolyIter iter;
1525  iter, wp, weld_mesh.wloop, mloop, weld_mesh.loop_map, group_buffer.data())) {
1526  continue;
1527  }
1528 
1529  if (wp.poly_dst != OUT_OF_CONTEXT) {
1530  continue;
1531  }
1532  while (weld_iter_loop_of_poly_next(iter)) {
1533  customdata_weld(&mesh.ldata, &result->ldata, group_buffer.data(), iter.group_len, loop_cur);
1534  int v = vert_final[iter.v];
1535  int e = edge_final[iter.e];
1536  r_ml->v = v;
1537  r_ml->e = e;
1538  r_ml++;
1539  loop_cur++;
1540  if (iter.type) {
1541  result->medge[e].flag &= ~ME_LOOSEEDGE;
1542  }
1543  BLI_assert((result->medge[e].flag & ME_LOOSEEDGE) == 0);
1544  }
1545 
1546  r_mp->loopstart = loop_start;
1547  r_mp->totloop = loop_cur - loop_start;
1548  r_mp++;
1549  r_i++;
1550  }
1551 
1552  BLI_assert((int)r_i == result_npolys);
1553  BLI_assert(loop_cur == result_nloops);
1554 
1555  return result;
1556 }
1557 
1560 /* -------------------------------------------------------------------- */
1564 std::optional<Mesh *> mesh_merge_by_distance_all(const Mesh &mesh,
1565  const IndexMask selection,
1566  const float merge_distance)
1567 {
1568  Array<int> vert_dest_map(mesh.totvert, OUT_OF_CONTEXT);
1569 
1570  KDTree_3d *tree = BLI_kdtree_3d_new(selection.size());
1571 
1572  for (const int i : selection) {
1573  BLI_kdtree_3d_insert(tree, i, mesh.mvert[i].co);
1574  }
1575 
1576  BLI_kdtree_3d_balance(tree);
1577  const int vert_kill_len = BLI_kdtree_3d_calc_duplicates_fast(
1578  tree, merge_distance, false, vert_dest_map.data());
1579  BLI_kdtree_3d_free(tree);
1580 
1581  if (vert_kill_len == 0) {
1582  return std::nullopt;
1583  }
1584 
1585  return create_merged_mesh(mesh, vert_dest_map, vert_kill_len);
1586 }
1587 
1589  float co[3];
1591 };
1592 
1593 std::optional<Mesh *> mesh_merge_by_distance_connected(const Mesh &mesh,
1594  Span<bool> selection,
1595  const float merge_distance,
1596  const bool only_loose_edges)
1597 {
1599  Span<MEdge> edges{mesh.medge, mesh.totedge};
1600 
1601  int vert_kill_len = 0;
1602 
1603  /* From the original index of the vertex.
1604  * This indicates which vert it is or is going to be merged. */
1605  Array<int> vert_dest_map(mesh.totvert, OUT_OF_CONTEXT);
1606 
1607  Array<WeldVertexCluster> vert_clusters(mesh.totvert);
1608 
1609  for (const int i : verts.index_range()) {
1610  WeldVertexCluster &vc = vert_clusters[i];
1611  copy_v3_v3(vc.co, verts[i].co);
1612  vc.merged_verts = 0;
1613  }
1614  const float merge_dist_sq = square_f(merge_distance);
1615 
1616  range_vn_i(vert_dest_map.data(), mesh.totvert, 0);
1617 
1618  /* Collapse Edges that are shorter than the threshold. */
1619  for (const int i : edges.index_range()) {
1620  int v1 = edges[i].v1;
1621  int v2 = edges[i].v2;
1622 
1623  if (only_loose_edges && (edges[i].flag & ME_LOOSEEDGE) == 0) {
1624  continue;
1625  }
1626  while (v1 != vert_dest_map[v1]) {
1627  v1 = vert_dest_map[v1];
1628  }
1629  while (v2 != vert_dest_map[v2]) {
1630  v2 = vert_dest_map[v2];
1631  }
1632  if (v1 == v2) {
1633  continue;
1634  }
1635  if (!selection.is_empty() && (!selection[v1] || !selection[v2])) {
1636  continue;
1637  }
1638  if (v1 > v2) {
1639  SWAP(int, v1, v2);
1640  }
1641  WeldVertexCluster *v1_cluster = &vert_clusters[v1];
1642  WeldVertexCluster *v2_cluster = &vert_clusters[v2];
1643 
1644  float edgedir[3];
1645  sub_v3_v3v3(edgedir, v2_cluster->co, v1_cluster->co);
1646  const float dist_sq = len_squared_v3(edgedir);
1647  if (dist_sq <= merge_dist_sq) {
1648  float influence = (v2_cluster->merged_verts + 1) /
1649  (float)(v1_cluster->merged_verts + v2_cluster->merged_verts + 2);
1650  madd_v3_v3fl(v1_cluster->co, edgedir, influence);
1651 
1652  v1_cluster->merged_verts += v2_cluster->merged_verts + 1;
1653  vert_dest_map[v2] = v1;
1654  vert_kill_len++;
1655  }
1656  }
1657 
1658  if (vert_kill_len == 0) {
1659  return std::nullopt;
1660  }
1661 
1662  for (const int i : IndexRange(mesh.totvert)) {
1663  if (i == vert_dest_map[i]) {
1664  vert_dest_map[i] = OUT_OF_CONTEXT;
1665  }
1666  else {
1667  int v = i;
1668  while ((v != vert_dest_map[v]) && (vert_dest_map[v] != OUT_OF_CONTEXT)) {
1669  v = vert_dest_map[v];
1670  }
1671  vert_dest_map[v] = v;
1672  vert_dest_map[i] = v;
1673  }
1674  }
1675 
1676  return create_merged_mesh(mesh, vert_dest_map, vert_kill_len);
1677 }
1678 
1681 } // namespace blender::geometry
CustomData interface, see also DNA_customdata_types.h.
void CustomData_copy_layer_type_data(const struct CustomData *source, struct CustomData *destination, int type, int source_index, int destination_index, int count)
bool CustomData_layer_has_interp(const struct CustomData *data, int layer_n)
void CustomData_data_add(int type, void *data1, const void *data2)
Definition: customdata.cc:4011
void CustomData_interp(const struct CustomData *source, struct CustomData *dest, const int *src_indices, const float *weights, const float *sub_weights, int count, int dest_index)
void CustomData_data_multiply(int type, void *data, float fac)
Definition: customdata.cc:4002
int CustomData_sizeof(int type)
Definition: customdata.cc:4268
bool CustomData_layer_has_math(const struct CustomData *data, int layer_n)
void CustomData_copy_data(const struct CustomData *source, struct CustomData *dest, int source_index, int dest_index, int count)
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)
#define BLI_assert(a)
Definition: BLI_assert.h:46
A KD-tree for nearest neighbor search.
MINLINE float square_f(float a)
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void madd_v3_v3fl(float r[3], const float a[3], float f)
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void mul_v3_fl(float r[3], float f)
MINLINE void copy_v3_v3(float r[3], const float a[3])
void range_vn_i(int *array_tar, int size, int start)
Definition: math_vector.c:1021
MINLINE void add_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition: BLI_sys_types.h:67
#define CLAMP_MAX(a, c)
#define SWAP(type, a, b)
#define ELEM(...)
#define MIN2(a, b)
#define POINTER_OFFSET(v, ofs)
#define CLAMP_MIN(a, b)
@ CD_MEDGE
@ CD_MVERT
@ ME_LOOSEEDGE
_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 type
_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
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
const T * data() const
Definition: BLI_array.hh:300
void fill(const T &value) const
Definition: BLI_array.hh:260
void reinitialize(const int64_t new_size)
Definition: BLI_array.hh:387
int64_t size() const
constexpr IndexRange slice(int64_t start, int64_t size) const
constexpr int64_t size() const
Definition: BLI_span.hh:511
constexpr void fill(const T &value)
Definition: BLI_span.hh:527
constexpr IndexRange index_range() const
Definition: BLI_span.hh:661
constexpr int64_t size() const
Definition: BLI_span.hh:240
constexpr IndexRange index_range() const
Definition: BLI_span.hh:401
constexpr bool is_empty() const
Definition: BLI_span.hh:248
int64_t size() const
Definition: BLI_vector.hh:694
void append(const T &value)
Definition: BLI_vector.hh:433
void reserve(const int64_t min_capacity)
Definition: BLI_vector.hh:340
SyclQueue void * dest
void * tree
static float verts[][3]
int count
#define ELEM_COLLAPSED
#define OUT_OF_CONTEXT
#define ELEM_MERGED
std::optional< Mesh * > mesh_merge_by_distance_connected(const Mesh &mesh, Span< bool > selection, float merge_distance, bool only_loose_edges)
static Vector< WeldVert > weld_vert_ctx_alloc_and_setup(Span< int > vert_dest_map, const int vert_kill_len)
static void weld_poly_loop_ctx_alloc(Span< MPoly > mpoly, Span< MLoop > mloop, Span< int > vert_dest_map, Span< int > edge_dest_map, WeldMesh *r_weld_mesh)
static void weld_edge_groups_setup(const int medge_len, const int edge_kill_len, MutableSpan< WeldEdge > wedge, Span< int > wedge_map, MutableSpan< int > r_edge_groups_map, Array< int > &r_edge_groups_buffer, Array< WeldGroupEdge > &r_edge_groups)
static void weld_mesh_context_create(const Mesh &mesh, MutableSpan< int > vert_dest_map, const int vert_kill_len, WeldMesh *r_weld_mesh)
static void weld_poly_loop_ctx_setup(Span< MLoop > mloop, const int mvert_len, Span< int > vert_dest_map, const int remain_edge_ctx_len, MutableSpan< WeldGroup > r_vlinks, WeldMesh *r_weld_mesh)
std::optional< Mesh * > mesh_merge_by_distance_all(const Mesh &mesh, IndexMask selection, float merge_distance)
static void weld_edge_ctx_setup(MutableSpan< WeldGroup > r_vlinks, MutableSpan< int > r_edge_dest_map, MutableSpan< WeldEdge > r_wedge, int *r_edge_kiil_len)
static bool weld_iter_loop_of_poly_next(WeldLoopOfPolyIter &iter)
static void weld_vert_groups_setup(Span< WeldVert > wvert, Span< int > vert_dest_map, MutableSpan< int > r_vert_groups_map, Array< int > &r_vert_groups_buffer, Array< WeldGroup > &r_vert_groups)
static Vector< WeldEdge > weld_edge_ctx_alloc(Span< MEdge > medge, Span< int > vert_dest_map, MutableSpan< int > r_edge_dest_map, MutableSpan< int > r_edge_ctx_map)
static Mesh * create_merged_mesh(const Mesh &mesh, MutableSpan< int > vert_dest_map, const int removed_vertex_count)
static bool weld_iter_loop_of_poly_begin(WeldLoopOfPolyIter &iter, const WeldPoly &wp, Span< WeldLoop > wloop, Span< MLoop > mloop, Span< int > loop_map, int *group_buffer)
static void weld_poly_split_recursive(Span< int > vert_dest_map, int ctx_verts_len, WeldPoly *r_wp, WeldMesh *r_weld_mesh, int *r_poly_kill, int *r_loop_kill)
static void customdata_weld(const CustomData *source, CustomData *dest, const int *src_indices, int count, int dest_index)
CustomDataLayer * layers
unsigned int v1
unsigned int v2
unsigned int e
unsigned int v
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
Array< WeldGroupEdge > edge_groups