Blender V5.3
multires_unsubdivide.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2020 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
11
12#include "MEM_guardedalloc.h"
13
14#include "DNA_mesh_types.h"
15#include "DNA_meshdata_types.h"
16#include "DNA_modifier_types.h"
17#include "DNA_object_types.h"
18
19#include "BLI_array_utils.hh"
20#include "BLI_gsqueue.hh"
21#include "BLI_math_vector_c.hh"
22
23#include "BKE_attribute.hh"
24#include "BKE_ccg.hh"
25#include "BKE_customdata.hh"
26#include "BKE_mesh.hh"
27#include "BKE_multires.hh"
28#include "BKE_report.hh"
29
30#include "bmesh.hh"
31
32#include "multires_reshape.hh"
34
35namespace blender {
36
37/* This is done in the following steps:
38 *
39 * - If there are already grids in the original mesh,
40 * convert them from tangent displacement to object space coordinates.
41 * - Assign data-layers to the original mesh to map vertices to a new base mesh.
42 * These data-layers store the indices of the elements in the original mesh.
43 * This way the original indices are
44 * preserved when doing mesh modifications (removing and dissolving vertices)
45 * when building the new base mesh.
46 * - Try to find a lower resolution base mesh. This is done by flood fill operation that tags the
47 * center vertices of the lower level grid.
48 * If the algorithm can tag all vertices correctly,
49 * the lower level base mesh is generated by dissolving the tagged vertices.
50 * - Use the data-layers to map vertices from the base mesh to the original mesh and original to
51 * base mesh.
52 * - Find two adjacent vertices on the base mesh to a given vertex to map that loop from base mesh
53 * to original mesh
54 * - Extract the grid from the original mesh from that loop. If there are no grids in the original
55 * mesh, build the new grid directly from the vertex coordinates by iterating in a grid pattern
56 * over them. If there are grids in the original mesh, iterate in a grid pattern over the faces,
57 * reorder all the coordinates of the grid in that face and copy those coordinates to the new
58 * base mesh grid.
59 * - Copy the new grid data over to a new allocated MDISP layer with the appropriate size to store
60 * the new levels.
61 * - Convert the grid data from object space to tangent displacement.
62 */
63
67static bool is_vertex_in_id(BMVert *v, const int *elem_id, int elem)
68{
69 const int v_index = BM_elem_index_get(v);
70 return elem_id[v_index] == elem;
71}
72
77
83
90static BMVert *unsubdivide_find_any_pole(BMesh *bm, int *elem_id, int elem)
91{
92 BMIter iter;
93 BMVert *v;
94 BMVert *pole = nullptr;
96 if (is_vertex_in_id(v, elem_id, elem) && is_vertex_pole_three(v)) {
97 return v;
98 }
99 if (is_vertex_in_id(v, elem_id, elem) && is_vertex_pole(v)) {
100 pole = v;
101 }
102 }
103 return pole;
104}
105
113{
114 BMIter iter;
115 BMFace *f;
116 BMVert *v;
117 if (bm->totface < 3) {
118 return false;
119 }
120
121 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
122 if (f->len != 4) {
123 return false;
124 }
125 }
126
127 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
128 if (BM_vert_is_wire(v) || (v->e == nullptr)) {
129 return false;
130 }
131 }
132
133 return true;
134}
135
139static bool is_vertex_diagonal(BMVert *from_v, BMVert *to_v)
140{
141 return !BM_edge_exists(from_v, to_v);
142}
143
153static void unsubdivide_face_center_vertex_tag(BMesh *bm, BMVert *initial_vertex)
154{
155 BitVector<> visited_verts(bm->totvert);
156 GSQueue *queue;
157 queue = BLI_gsqueue_new(sizeof(BMVert *));
158
159 /* Add and tag the vertices connected by a diagonal to initial_vertex to the flood fill queue. If
160 * initial_vertex is a pole and there is a valid solution, those vertices should be the (0,0) of
161 * the grids for the loops of initial_vertex. */
162 BMIter iter;
163 BMIter iter_a;
164 BMFace *f;
165 BMVert *neighbor_v;
166 BM_ITER_ELEM (f, &iter, initial_vertex, BM_FACES_OF_VERT) {
167 BM_ITER_ELEM (neighbor_v, &iter_a, f, BM_VERTS_OF_FACE) {
168 int neighbor_vertex_index = BM_elem_index_get(neighbor_v);
169 if (neighbor_v != initial_vertex && is_vertex_diagonal(neighbor_v, initial_vertex)) {
170 BLI_gsqueue_push(queue, &neighbor_v);
171 visited_verts[neighbor_vertex_index].set();
172 BM_elem_flag_set(neighbor_v, BM_ELEM_TAG, true);
173 }
174 }
175 }
176
177 /* Repeat a similar operation for all vertices in the queue. */
178 /* In this case, add to the queue the vertices connected by 2 steps using the diagonals in any
179 * direction. If a solution exists and `initial_vertex` was a pole, this is guaranteed that will
180 * tag all the (0,0) vertices of the grids, and nothing else. */
181 /* If it was not a pole, it may or may not find a solution, even if the solution exists. */
182 while (!BLI_gsqueue_is_empty(queue)) {
183 BMVert *from_v;
184 BLI_gsqueue_pop(queue, &from_v);
185
186 /* Get the diagonals (first connected step) */
187 GSQueue *diagonals;
188 diagonals = BLI_gsqueue_new(sizeof(BMVert *));
189 BM_ITER_ELEM (f, &iter, from_v, BM_FACES_OF_VERT) {
190 BM_ITER_ELEM (neighbor_v, &iter_a, f, BM_VERTS_OF_FACE) {
191 if (neighbor_v != from_v && is_vertex_diagonal(neighbor_v, from_v)) {
192 BLI_gsqueue_push(diagonals, &neighbor_v);
193 }
194 }
195 }
196
197 /* Do the second connected step. This vertices are the ones that are added to the flood fill
198 * queue. */
199 while (!BLI_gsqueue_is_empty(diagonals)) {
200 BMVert *diagonal_v;
201 BLI_gsqueue_pop(diagonals, &diagonal_v);
202 BM_ITER_ELEM (f, &iter, diagonal_v, BM_FACES_OF_VERT) {
203 BM_ITER_ELEM (neighbor_v, &iter_a, f, BM_VERTS_OF_FACE) {
204 int neighbor_vertex_index = BM_elem_index_get(neighbor_v);
205 if (!visited_verts[neighbor_vertex_index] && neighbor_v != diagonal_v &&
206 is_vertex_diagonal(neighbor_v, diagonal_v))
207 {
208 BLI_gsqueue_push(queue, &neighbor_v);
209 visited_verts[neighbor_vertex_index].set(true);
210 BM_elem_flag_set(neighbor_v, BM_ELEM_TAG, true);
211 }
212 }
213 }
214 }
215 BLI_gsqueue_free(diagonals);
216 }
217
218 BLI_gsqueue_free(queue);
219}
220
232static bool unsubdivide_is_center_vertex_tag_valid(BMesh *bm, int *elem_id, int elem)
233{
234 BMVert *v, *neighbor_v;
235 BMIter iter, iter_a, iter_b;
236 BMFace *f;
237
238 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
239 if (is_vertex_in_id(v, elem_id, elem)) {
241 /* Tagged vertex in boundary */
242 if (BM_vert_is_boundary(v)) {
243 return false;
244 }
245 /* Tagged vertex with connected tagged vertex. */
246 BM_ITER_ELEM (f, &iter_a, v, BM_FACES_OF_VERT) {
247 BM_ITER_ELEM (neighbor_v, &iter_b, f, BM_VERTS_OF_FACE) {
248 if (neighbor_v != v && BM_elem_flag_test(neighbor_v, BM_ELEM_TAG)) {
249 return false;
250 }
251 }
252 }
253 }
254 if (BM_vert_is_boundary(v)) {
255 /* Un-tagged vertex in boundary without connected tagged vertices. */
256 bool any_tagged = false;
257 BM_ITER_ELEM (f, &iter_a, v, BM_FACES_OF_VERT) {
258 BM_ITER_ELEM (neighbor_v, &iter_b, f, BM_VERTS_OF_FACE) {
259 if (neighbor_v != v && BM_elem_flag_test(neighbor_v, BM_ELEM_TAG)) {
260 any_tagged = true;
261 }
262 }
263 }
264 if (!any_tagged) {
265 return false;
266 }
267 }
268 }
269 }
270
271 return true;
272}
273
277static bool unsubdivide_tag_disconnected_mesh_element(BMesh *bm, int *elem_id, int elem)
278{
279 /* First, get vertex candidates to try to generate possible un-subdivide solution. */
280 /* Find a vertex pole. If there is a solution on an all quad base mesh, this vertex should be
281 * part of the base mesh. If it isn't, then there is no solution. */
282 GSQueue *initial_vertex = BLI_gsqueue_new(sizeof(BMVert *));
283 BMVert *initial_vertex_pole = unsubdivide_find_any_pole(bm, elem_id, elem);
284 if (initial_vertex_pole != nullptr) {
285 BLI_gsqueue_push(initial_vertex, &initial_vertex_pole);
286 }
287
288 /* Also try from the different 4 vertices of a quad in the current
289 * disconnected element ID. If a solution exists the search should return a valid solution from
290 * one of these vertices. */
291 BMFace *f, *init_face = nullptr;
292 BMVert *v;
293 BMIter iter_a, iter_b;
294 BM_ITER_MESH (f, &iter_a, bm, BM_FACES_OF_MESH) {
295 BM_ITER_ELEM (v, &iter_b, f, BM_VERTS_OF_FACE) {
296 if (is_vertex_in_id(v, elem_id, elem)) {
297 init_face = f;
298 break;
299 }
300 }
301 if (init_face != nullptr) {
302 break;
303 }
304 }
305
306 BM_ITER_ELEM (v, &iter_a, init_face, BM_VERTS_OF_FACE) {
307 BLI_gsqueue_push(initial_vertex, &v);
308 }
309
310 bool valid_tag_found = false;
311
312 /* Check all vertex candidates to a solution. */
313 while (!BLI_gsqueue_is_empty(initial_vertex)) {
314
315 BMVert *iv;
316 BLI_gsqueue_pop(initial_vertex, &iv);
317
318 /* Generate a possible solution. */
320
321 /* Check if the solution is valid. If it is, stop searching. */
322 if (unsubdivide_is_center_vertex_tag_valid(bm, elem_id, elem)) {
323 valid_tag_found = true;
324 break;
325 }
326
327 /* If the solution is not valid, reset the state of all tags in this disconnected element ID
328 * and try again. */
329 BMVert *v_reset;
330 BMIter iter;
331 BM_ITER_MESH (v_reset, &iter, bm, BM_VERTS_OF_MESH) {
332 if (is_vertex_in_id(v_reset, elem_id, elem)) {
333 BM_elem_flag_set(v_reset, BM_ELEM_TAG, false);
334 }
335 }
336 }
337 BLI_gsqueue_free(initial_vertex);
338 return valid_tag_found;
339}
340
344static int unsubdivide_init_elem_ids(BMesh *bm, int *elem_id)
345{
346 bool *visited_verts = MEM_new_array_zeroed<bool>(bm->totvert, "visited vertices");
347 int current_id = 0;
348 for (int i = 0; i < bm->totvert; i++) {
349 if (!visited_verts[i]) {
350 GSQueue *queue;
351 queue = BLI_gsqueue_new(sizeof(BMVert *));
352
353 visited_verts[i] = true;
354 elem_id[i] = current_id;
355 BMVert *iv = BM_vert_at_index(bm, i);
356 BLI_gsqueue_push(queue, &iv);
357
358 while (!BLI_gsqueue_is_empty(queue)) {
359 BMIter iter;
360 BMVert *current_v, *neighbor_v;
361 BMEdge *ed;
362 BLI_gsqueue_pop(queue, &current_v);
363 BM_ITER_ELEM (ed, &iter, current_v, BM_EDGES_OF_VERT) {
364 neighbor_v = BM_edge_other_vert(ed, current_v);
365 const int neighbor_index = BM_elem_index_get(neighbor_v);
366 if (!visited_verts[neighbor_index]) {
367 visited_verts[neighbor_index] = true;
368 elem_id[neighbor_index] = current_id;
369 BLI_gsqueue_push(queue, &neighbor_v);
370 }
371 }
372 }
373 current_id++;
374 BLI_gsqueue_free(queue);
375 }
376 }
377 MEM_delete(visited_verts);
378 return current_id;
379}
380
386{
387 BMVert *v;
388 BMIter iter;
389
390 /* Stores the vertices which correspond to (1, 0) and (0, 1) of the grids in the select flag. */
392 BMVert *v_neighbor;
393 BMIter iter_a;
394 BMEdge *ed;
395 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
396 BM_ITER_ELEM (ed, &iter_a, v, BM_EDGES_OF_VERT) {
397 v_neighbor = BM_edge_other_vert(ed, v);
398 if (BM_elem_flag_test(v_neighbor, BM_ELEM_TAG)) {
400 }
401 }
402 }
403
404 /* Dissolves the (0,0) vertices of the grids. */
407 "dissolve_verts verts=%hv use_face_split=%b use_boundary_tear=%b",
409 false,
410 true);
411
413
414 /* Copy the select flag to the tag flag. */
415 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
418 }
419 }
420
421 /* Dissolves the (1,0) and (0,1) vertices of the grids. */
424 "dissolve_verts verts=%hv use_face_split=%b use_boundary_tear=%b",
426 false,
427 true);
428}
429
440{
441
442 /* Do a first check to make sure that it makes sense to search for un-subdivision in this mesh.
443 */
445 return false;
446 };
447
448 /* Initialize the vertex table. */
451
452 /* Build disconnected elements IDs. Each disconnected mesh element is evaluated separately. */
453 int *elem_id = MEM_new_array_zeroed<int>(bm->totvert, " ELEM ID");
454 const int tot_ids = unsubdivide_init_elem_ids(bm, elem_id);
455
456 bool valid_tag_found = true;
457
458 /* Reset the #BMesh flags as they are used to store data during the un-subdivide process.
459 * Un-hiding all faces is important so the entire mesh is handled, see: #126633. */
462
463 /* For each disconnected mesh element ID, search if an un-subdivide solution is possible. The
464 * whole un-subdivide process fails if a single disconnected mesh element fails. */
465 for (int id = 0; id < tot_ids; id++) {
466 /* Try to the #BMesh vertex flag tags corresponding to an un-subdivide solution. */
468 valid_tag_found = false;
469 break;
470 }
471 }
472
473 /* If a solution was found for all elements IDs, build the new base mesh using the solution
474 * stored in the BMVert tags. */
475 if (valid_tag_found) {
477 }
478
479 MEM_delete(elem_id);
480 return valid_tag_found;
481}
482
486static BMEdge *edge_step(BMVert *v, BMEdge *edge, BMVert **r_next_vertex)
487{
488 BMIter iter;
489 BMEdge *test_edge;
490 if (edge == nullptr) {
491 (*r_next_vertex) = v;
492 return edge;
493 }
494 (*r_next_vertex) = BM_edge_other_vert(edge, v);
495 BM_ITER_ELEM (test_edge, &iter, (*r_next_vertex), BM_EDGES_OF_VERT) {
496 if (!BM_edge_share_quad_check(test_edge, edge)) {
497 return test_edge;
498 }
499 }
500 return nullptr;
501}
502
503static BMFace *face_step(BMEdge *edge, BMFace *f)
504{
505 BMLoop *l_a, *l_b;
506 if (BM_edge_loop_pair(edge, &l_a, &l_b)) {
507 if (f == l_a->f) {
508 return l_b->f;
509 }
510
511 if (f == l_b->f) {
512 return l_a->f;
513 }
514 }
515 return f;
516}
517
522static BMEdge *get_initial_edge_y(BMFace *f, BMEdge *edge_x, BMVert *initial_vertex)
523{
524 BMIter iter;
525 BMEdge *test_edge;
526 BM_ITER_ELEM (test_edge, &iter, f, BM_EDGES_OF_FACE) {
527 if (edge_x != test_edge) {
528 if (test_edge->v1 != initial_vertex && test_edge->v2 == initial_vertex) {
529 return test_edge;
530 }
531 if (test_edge->v2 != initial_vertex && test_edge->v1 == initial_vertex) {
532 return test_edge;
533 }
534 }
535 }
536 return nullptr;
537}
538
543 float (*face_grid)[3], MDisps *mdisp, int face_grid_size, int orig_grid_size, int loop)
544{
545 int origin[2];
546 int step_x[2];
547 int step_y[2];
548
549 const int grid_offset = orig_grid_size - 1;
550 origin[0] = grid_offset;
551 origin[1] = grid_offset;
552
553 switch (loop) {
554 case 0:
555 step_x[0] = -1;
556 step_x[1] = 0;
557
558 step_y[0] = 0;
559 step_y[1] = -1;
560
561 break;
562 case 1:
563 step_x[0] = 0;
564 step_x[1] = 1;
565
566 step_y[0] = -1;
567 step_y[1] = -0;
568 break;
569 case 2:
570 step_x[0] = 1;
571 step_x[1] = 0;
572
573 step_y[0] = 0;
574 step_y[1] = 1;
575 break;
576 case 3:
577 step_x[0] = 0;
578 step_x[1] = -1;
579
580 step_y[0] = 1;
581 step_y[1] = 0;
582 break;
583 default:
584 BLI_assert_msg(0, "Should never happen");
585 break;
586 }
587
588 for (int y = 0; y < orig_grid_size; y++) {
589 for (int x = 0; x < orig_grid_size; x++) {
590 const int remap_x = origin[1] + (step_x[1] * x) + (step_y[1] * y);
591 const int remap_y = origin[0] + (step_x[0] * x) + (step_y[0] * y);
592
593 const int final_index = remap_x + remap_y * face_grid_size;
594 copy_v3_v3(face_grid[final_index], mdisp->disps[x + y * orig_grid_size]);
595 }
596 }
597}
598
604 float (*face_grid)[3],
605 int face_grid_size,
606 int gunsub_x,
607 int gunsub_y)
608{
609 const int grid_it = face_grid_size - 1;
610 for (int y = 0; y < face_grid_size; y++) {
611 for (int x = 0; x < face_grid_size; x++) {
612 const int remap_x = (grid_it * gunsub_x) + x;
613 const int remap_y = (grid_it * gunsub_y) + y;
614
615 const int remap_index_y = grid->grid_size - remap_x - 1;
616 const int remap_index_x = grid->grid_size - remap_y - 1;
617 const int grid_index = remap_index_x + (remap_index_y * grid->grid_size);
618 copy_v3_v3(grid->grid_co[grid_index], face_grid[x + y * face_grid_size]);
619 }
620 }
621}
622
631 BMVert *v,
632 BMFace *f,
633 int grid_x,
634 int grid_y)
635{
636 Mesh *original_mesh = context->original_mesh;
637 const OffsetIndices faces = original_mesh->faces();
638 const Span<int> corner_verts = original_mesh->corner_verts();
639 const IndexRange face = faces[BM_elem_index_get(f)];
640
641 const int corner_vertex_index = BM_elem_index_get(v);
642
643 /* Calculates an offset to write the grids correctly oriented in the main
644 * #MultiresUnsubdivideGrid. */
645 int loop_offset = 0;
646 for (int i = 0; i < face.size(); i++) {
647 const int loop_index = face[i];
648 if (corner_verts[loop_index] == corner_vertex_index) {
649 loop_offset = i;
650 break;
651 }
652 }
653
654 /* Write the 4 grids of the current quad with the right orientation into the face_grid buffer. */
655 const int grid_size = CCG_grid_size(context->num_original_levels);
656 const int face_grid_size = CCG_grid_size(context->num_original_levels + 1);
657 const int face_grid_area = face_grid_size * face_grid_size;
658 float (*face_grid)[3] = MEM_new_array_zeroed<float[3]>(face_grid_area, "face_grid");
659
660 for (int i = 0; i < face.size(); i++) {
661 const int loop_index = face[i];
662 MDisps *mdisp = &context->original_mdisp[loop_index];
663 int quad_loop = i - loop_offset;
664 if (quad_loop < 0) {
665 quad_loop += 4;
666 }
667 if (quad_loop >= 4) {
668 quad_loop -= 4;
669 }
670 write_loop_in_face_grid(face_grid, mdisp, face_grid_size, grid_size, quad_loop);
671 }
672
673 /* Write the face_grid buffer in the correct position in the #MultiresUnsubdivideGrids that is
674 * being extracted. */
675 write_face_grid_in_unsubdivide_grid(grid, face_grid, face_grid_size, grid_x, grid_y);
676
677 MEM_delete(face_grid);
678}
679
684static void store_vertex_data(MultiresUnsubdivideGrid *grid, BMVert *v, int grid_x, int grid_y)
685{
686 const int remap_index_y = grid->grid_size - 1 - grid_x;
687 const int remap_index_x = grid->grid_size - 1 - grid_y;
688
689 const int grid_index = remap_index_x + (remap_index_y * grid->grid_size);
690
691 copy_v3_v3(grid->grid_co[grid_index], v->co);
692}
693
704 BMFace *f1,
705 BMEdge *e1,
706 bool flip_grid,
708{
709 BMVert *initial_vertex;
710 BMEdge *initial_edge_x;
711 BMEdge *initial_edge_y;
712
713 const int grid_size = CCG_grid_size(context->num_new_levels);
714 const int unsubdiv_grid_size = grid->grid_size = CCG_grid_size(context->num_total_levels);
715 BLI_assert(grid->grid_co == nullptr);
716 grid->grid_size = unsubdiv_grid_size;
718 size_t(unsubdiv_grid_size) * size_t(unsubdiv_grid_size), "grids coordinates");
719
720 /* Get the vertex on the corner of the grid. This vertex was tagged previously as it also exist
721 * on the base mesh. */
722 initial_edge_x = e1;
723 if (BM_elem_flag_test(initial_edge_x->v1, BM_ELEM_TAG)) {
724 initial_vertex = initial_edge_x->v1;
725 }
726 else {
727 initial_vertex = initial_edge_x->v2;
728 }
729
730 /* From that vertex, get the edge that defines the grid Y axis for extraction. */
731 initial_edge_y = get_initial_edge_y(f1, initial_edge_x, initial_vertex);
732
733 if (flip_grid) {
734 BMEdge *edge_temp;
735 edge_temp = initial_edge_x;
736 initial_edge_x = initial_edge_y;
737 initial_edge_y = edge_temp;
738 }
739
740 BMVert *current_vertex_x = initial_vertex;
741 BMEdge *edge_x = initial_edge_x;
742
743 BMVert *current_vertex_y = initial_vertex;
744 BMEdge *edge_y = initial_edge_y;
745 BMEdge *prev_edge_y = initial_edge_y;
746
747 BMFace *current_face = f1;
748 BMFace *grid_face = f1;
749
750 const bool has_original_grid_data = context->num_original_levels > 0;
751
752 /* NOTE(@ideasman42): early returning on first
753 * encountering null elements cause unexpected regressions.
754 * Instead of early exit, track if #store_vertex_data or #store_grid_data couldn't run,
755 * returning false if any failed. */
756 bool ok = true;
757
758 /* If the data is going to be extracted from the already existing grids, there is no need to go
759 * to the last vertex of the iteration as that coordinate is also included in the grids
760 * corresponding to the loop of the face of the previous iteration. */
761 const int grid_iteration_max_steps = grid_size - (has_original_grid_data ? 1 : 0);
762
763 /* Iterate over the mesh vertices in a grid pattern using the axis defined by the two initial
764 * edges. */
765 for (const int grid_y : IndexRange(grid_iteration_max_steps)) {
766
767 grid_face = current_face;
768
769 for (const int grid_x : IndexRange(grid_iteration_max_steps)) {
770 if (has_original_grid_data == false) {
771 /* If there were no grids on the original mesh, extract the data directly from the
772 * vertices. */
773 if (current_vertex_x) {
774 store_vertex_data(grid, current_vertex_x, grid_x, grid_y);
775 }
776 else {
777 ok = false;
778 }
779 edge_x = edge_step(current_vertex_x, edge_x, &current_vertex_x);
780 }
781 else {
782 /* If there were grids in the original mesh, extract the data from the grids and iterate
783 * over the faces. */
784 if (current_vertex_x && grid_face) {
785 store_grid_data(context, grid, current_vertex_x, grid_face, grid_x, grid_y);
786 }
787 else {
788 ok = false;
789 }
790 edge_x = edge_step(current_vertex_x, edge_x, &current_vertex_x);
791 grid_face = edge_x ? face_step(edge_x, grid_face) : nullptr;
792 }
793 }
794
795 edge_y = edge_step(current_vertex_y, edge_y, &current_vertex_y);
796 current_vertex_x = current_vertex_y;
797
798 /* Get the next edge_x to extract the next row of the grid. This needs to be done because there
799 * may be two edges connected to current_vertex_x that belong to two different grids. */
800 BMIter iter;
801 BMEdge *ed;
802 edge_x = nullptr;
803 BM_ITER_ELEM (ed, &iter, current_vertex_x, BM_EDGES_OF_VERT) {
804 if (ed != prev_edge_y && BM_edge_in_face(ed, current_face)) {
805 edge_x = ed;
806 break;
807 }
808 }
809 /* May be null, check on next access (if this isn't the end of iteration). */
810 current_face = edge_x ? face_step(edge_x, current_face) : nullptr;
811
812 prev_edge_y = edge_y;
813 }
814
815 return ok;
816}
817
826 BMEdge *edge,
827 int *vert_visit,
828 const int visit_id)
829{
830 edge = edge_step(v, edge, &v);
831 while (!BM_elem_flag_test(v, BM_ELEM_TAG)) {
832 /* Prevent an eternal loop - typically caused by degenerate geometry.
833 * Every lookup uses a new ID, so we can detect if we met the vertex before.
834 * See #162395. */
835 const int v_index = BM_elem_index_get(v);
836 if (vert_visit[v_index] == visit_id) [[unlikely]] {
837 return nullptr;
838 }
839 vert_visit[v_index] = visit_id;
840
841 edge = edge_step(v, edge, &v);
842 }
843 return v;
844}
845
855 BMEdge *e1,
856 int *vert_visit,
857 int *visit_id,
858 BMVert **r_corner_x,
859 BMVert **r_corner_y)
860{
861 BMVert *initial_vertex;
862 BMEdge *initial_edge_x;
863 BMEdge *initial_edge_y;
864
865 initial_edge_x = e1;
866 if (BM_elem_flag_test(initial_edge_x->v1, BM_ELEM_TAG)) {
867 initial_vertex = initial_edge_x->v1;
868 }
869 else {
870 initial_vertex = initial_edge_x->v2;
871 }
872
873 /* From that vertex, get the edge that defines the grid Y axis for extraction. */
874 initial_edge_y = get_initial_edge_y(f1, initial_edge_x, initial_vertex);
875
876 BMVert *current_vertex_x = initial_vertex;
877 BMEdge *edge_x = initial_edge_x;
878
879 BMVert *current_vertex_y = initial_vertex;
880 BMEdge *edge_y = initial_edge_y;
881
882 /* Do an edge step until it finds a tagged vertex, which is part of the base mesh. */
883
884 /* X axis. */
886 current_vertex_x, edge_x, vert_visit, ++(*visit_id));
887 if (corner_x == nullptr) [[unlikely]] {
888 return false;
889 }
890 /* Y axis. */
892 current_vertex_y, edge_y, vert_visit, ++(*visit_id));
893 if (corner_y == nullptr) [[unlikely]] {
894 return false;
895 }
896
897 *r_corner_x = corner_x;
898 *r_corner_y = corner_y;
899 return true;
900}
901
903{
905
906 BMeshCreateParams bm_create_params{};
907 bm_create_params.use_toolflags = true;
908 BMesh *bm = BM_mesh_create(&allocsize, &bm_create_params);
909
910 BMeshFromMeshParams bm_from_me_params{};
911 bm_from_me_params.calc_face_normal = true;
912 bm_from_me_params.calc_vert_normal = true;
913 BM_mesh_bm_from_me(bm, mesh, &bm_from_me_params);
914
915 return bm;
916}
917
918/* Data-layer names to store the original indices of the elements before modifying the mesh. */
919static const char lname[] = "l_remap_index";
920static const char vname[] = "v_remap_index";
921
923{
924 bke::MutableAttributeAccessor attributes = mesh->attributes_for_write();
925 attributes.remove(lname);
926 attributes.remove(vname);
927}
928
948
951{
952 Mesh *original_mesh = context->original_mesh;
953
954 Mesh *base_mesh = context->base_mesh;
955
956 BMesh *bm_original_mesh = context->bm_original_mesh = get_bmesh_from_mesh(original_mesh);
957
958 /* Initialize the elem tables. */
959 BM_mesh_elem_table_ensure(bm_original_mesh, BM_VERT | BM_EDGE | BM_FACE);
960
961 /* Disable all flags. */
962 BM_mesh_elem_hflag_disable_all(bm_original_mesh,
965 false);
966
967 /* Get the mapping data-layer. */
968 bke::AttributeAccessor attributes = base_mesh->attributes();
969 context->base_to_orig_vmap = *attributes.lookup<int>(vname);
970
971 /* Tag the base mesh vertices in the original mesh. */
972 for (int i = 0; i < base_mesh->verts_num; i++) {
973 int vert_basemesh_index = context->base_to_orig_vmap[i];
974 BMVert *v = BM_vert_at_index(bm_original_mesh, vert_basemesh_index);
976 }
977
978 context->loop_to_face_map = original_mesh->corner_to_face_map();
979}
980
986 const Span<int> corner_verts,
987 int face_index,
988 int loop,
989 int v_x)
990{
991 const IndexRange face = faces[face_index];
992
993 const int v_first = corner_verts[face.start()];
994 if ((loop == (face.start() + (face.size() - 1))) && v_first == v_x) {
995 return true;
996 }
997
998 int next_l_index = loop + 1;
999 if (next_l_index < face.start() + face.size()) {
1000 const int v_next = corner_verts[next_l_index];
1001 if (v_next == v_x) {
1002 return true;
1003 }
1004 }
1005
1006 return false;
1007}
1008
1011{
1012 Mesh *original_mesh = context->original_mesh;
1013 Mesh *base_mesh = context->base_mesh;
1014
1015 BMesh *bm_original_mesh = context->bm_original_mesh;
1016
1017 context->num_grids = base_mesh->corners_num;
1018 context->base_mesh_grids = MEM_new_array_zeroed<MultiresUnsubdivideGrid>(
1019 size_t(base_mesh->corners_num), "grids");
1020
1021 /* Based on the existing indices in the data-layers, generate two vertex indices maps. */
1022 /* From vertex index in original to vertex index in base and from vertex index in base to vertex
1023 * index in original. */
1024 int *orig_to_base_vmap = MEM_new_array_zeroed<int>(bm_original_mesh->totvert, "orig vmap");
1025 /* Per vertex ID's for detecting a walk which loops back on itself, ID's start at 1. */
1026 int *vert_visit = MEM_new_array_zeroed<int>(bm_original_mesh->totvert, "vert visit");
1027 int visit_id = 0;
1028 /* The walk stamps `vert_visit` by vertex index. */
1029 BLI_assert((bm_original_mesh->elem_index_dirty & BM_VERT) == 0);
1030 int *base_to_orig_vmap = MEM_new_array_zeroed<int>(base_mesh->verts_num, "base vmap");
1031
1032 const bke::AttributeAccessor attributes = base_mesh->attributes();
1033 context->base_to_orig_vmap = *attributes.lookup<int>(vname);
1034 for (int i = 0; i < base_mesh->verts_num; i++) {
1035 base_to_orig_vmap[i] = context->base_to_orig_vmap[i];
1036 }
1037
1038 /* If an index in original does not exist in base (it was dissolved when creating the new base
1039 * mesh), return -1. */
1040 for (int i = 0; i < original_mesh->verts_num; i++) {
1041 orig_to_base_vmap[i] = -1;
1042 }
1043
1044 for (int i = 0; i < base_mesh->verts_num; i++) {
1045 const int orig_vertex_index = context->base_to_orig_vmap[i];
1046 orig_to_base_vmap[orig_vertex_index] = i;
1047 }
1048
1049 /* Add the original data-layers to the base mesh to have the loop indices stored in a data-layer,
1050 * so they can be used from #BMesh. */
1052
1053 BMesh *bm_base_mesh = get_bmesh_from_mesh(base_mesh);
1054 BMIter iter, iter_a, iter_b;
1055 BMVert *v;
1056 BMLoop *l, *lb;
1057
1058 BM_mesh_elem_table_ensure(bm_base_mesh, BM_VERT | BM_FACE);
1059
1060 /* Get the data-layer that contains the loops indices. */
1061 const int base_l_offset = CustomData_get_offset_named(
1062 &bm_base_mesh->ldata, CD_PROP_INT32, lname);
1063
1064 const OffsetIndices faces = base_mesh->faces();
1065 const Span<int> corner_verts = base_mesh->corner_verts();
1066
1067 /* Main loop for extracting the grids. Iterates over the base mesh vertices. */
1068 BM_ITER_MESH (v, &iter, bm_base_mesh, BM_VERTS_OF_MESH) {
1069
1070 /* For each base mesh vertex, get the corresponding #BMVert of the original mesh using the
1071 * vertex map. */
1072 const int orig_vertex_index = base_to_orig_vmap[BM_elem_index_get(v)];
1073 BMVert *vert_original = BM_vert_at_index(bm_original_mesh, orig_vertex_index);
1074
1075 /* Iterate over the loops of that vertex in the original mesh. */
1076 BM_ITER_ELEM (l, &iter_a, vert_original, BM_LOOPS_OF_VERT) {
1077 /* For each loop, get the two vertices that should map to the l+1 and l-1 vertices in the
1078 * base mesh of the face of grid that is going to be extracted. */
1079 BMVert *corner_x, *corner_y;
1081 l->f, l->e, vert_visit, &visit_id, &corner_x, &corner_y))
1082 {
1083 info.unsupported_grid_count += 1;
1084 continue;
1085 }
1086
1087 /* Map the two obtained vertices to the base mesh. */
1088 const int corner_x_index = orig_to_base_vmap[BM_elem_index_get(corner_x)];
1089 const int corner_y_index = orig_to_base_vmap[BM_elem_index_get(corner_y)];
1090 if (corner_x_index < 0 || corner_y_index < 0) {
1091 continue;
1092 }
1093
1094 /* Iterate over the loops of the same vertex in the base mesh. With the previously obtained
1095 * vertices and the current vertex it is possible to get the index of the loop in the base
1096 * mesh the grid that is going to be extracted belongs to. */
1097 BM_ITER_ELEM (lb, &iter_b, v, BM_LOOPS_OF_VERT) {
1098 BMFace *base_face = lb->f;
1099 BMVert *base_corner_x = BM_vert_at_index(bm_base_mesh, corner_x_index);
1100 BMVert *base_corner_y = BM_vert_at_index(bm_base_mesh, corner_y_index);
1101 /* If this is the correct loop in the base mesh, the original vertex and the two corners
1102 * should be in the loop's face. */
1103 if (BM_vert_in_face(base_corner_x, base_face) && BM_vert_in_face(base_corner_y, base_face))
1104 {
1105 /* Get the index of the loop. */
1106 const int base_mesh_loop_index = BM_ELEM_CD_GET_INT(lb, base_l_offset);
1107 const int base_mesh_face_index = BM_elem_index_get(base_face);
1108
1109 /* Check the orientation of the loops in case that is needed to flip the x and y axis
1110 * when extracting the grid. */
1111 const bool flip_grid = multires_unsubdivide_flip_grid_x_axis(
1112 faces, corner_verts, base_mesh_face_index, base_mesh_loop_index, corner_x_index);
1113
1114 /* Extract the grid for that loop. */
1115 MultiresUnsubdivideGrid *grid = &context->base_mesh_grids[base_mesh_loop_index];
1116 if (grid->grid_co != nullptr) [[unlikely]] {
1117 /* It's possible this grid has already been initialized which occurs when quads
1118 * share two edge, while not so common it happens with "Suzanne's" nose,
1119 * see: #126633 & run un-subdivide.
1120 *
1121 * Continue here instead of breaking as logically: quads sharing 2 edges
1122 * will share 3 vertices and those 3 vertices may be attached to any number of quads.
1123 * So in this case, continue scanning instead of breaking out of the loop
1124 * because the `lb` to extract a grid from has not yet been encountered. */
1125 continue;
1126 }
1127
1128 grid->grid_index = base_mesh_loop_index;
1130 context, l->f, l->e, !flip_grid, grid))
1131 {
1132 info.unsupported_grid_count += 1;
1133 }
1134
1135 break;
1136 }
1137 }
1138 }
1139 }
1140
1141 MEM_delete(vert_visit);
1142 MEM_delete(orig_to_base_vmap);
1143 MEM_delete(base_to_orig_vmap);
1144
1145 BM_mesh_free(bm_base_mesh);
1147}
1148
1150{
1151 if (context->bm_original_mesh != nullptr) {
1152 BM_mesh_free(context->bm_original_mesh);
1153 }
1154}
1155
1157 Mesh *original_mesh,
1159{
1160 context->original_mesh = original_mesh;
1161 context->num_new_levels = 0;
1162 context->num_total_levels = 0;
1163 context->num_original_levels = mmd->totlvl;
1164}
1165
1168{
1169 Mesh *original_mesh = context->original_mesh;
1170
1171 /* Prepare the data-layers to map base to original. */
1173 BMesh *bm_base_mesh = get_bmesh_from_mesh(original_mesh);
1174
1175 /* Un-subdivide as many iterations as possible. */
1176 context->num_new_levels = 0;
1177 int num_levels_left = context->max_new_levels;
1178 while (num_levels_left > 0 && multires_unsubdivide_single_level(bm_base_mesh)) {
1179 context->num_new_levels++;
1180 num_levels_left--;
1181 }
1182
1183 /* If no un-subdivide steps were possible, free the bmesh, the map data-layers and stop. */
1184 if (context->num_new_levels == 0) {
1186 BM_mesh_free(bm_base_mesh);
1187 return false;
1188 }
1189
1190 /* Calculate the final levels for the new grids over base mesh. */
1191 context->num_total_levels = context->num_new_levels + context->num_original_levels;
1192
1193 /* Store the new base-mesh as a mesh in context, free bmesh.
1194 * NOTE(@ideasman42): passing the original mesh in the template is important so mesh settings &
1195 * vertex groups are kept, see: #93911. */
1196 context->base_mesh = BKE_mesh_new_nomain_from_template(original_mesh, 0, 0, 0, 0);
1197
1198 /* De-select all.
1199 * The user-selection has been overwritten and this selection has not been flushed. */
1201
1202 BMeshToMeshParams bm_to_me_params{};
1203 bm_to_me_params.calc_object_remap = true;
1204 BM_mesh_bm_to_me(nullptr, bm_base_mesh, context->base_mesh, &bm_to_me_params);
1205 BM_mesh_free(bm_base_mesh);
1206
1207 /* Initialize bmesh and maps for the original mesh and extract the grids. */
1208
1211
1212 return true;
1213}
1214
1216{
1218 for (int i = 0; i < context->num_grids; i++) {
1219 if (context->base_mesh_grids[i].grid_size > 0) {
1220 MEM_SAFE_DELETE(context->base_mesh_grids[i].grid_co);
1221 }
1222 }
1223 MEM_SAFE_DELETE(context->base_mesh_grids);
1224}
1225
1231 Mesh *base_mesh)
1232{
1233 /* Free the current MDISPS and create a new ones. */
1234 if (CustomData_has_layer(&base_mesh->corner_data, CD_MDISPS)) {
1236 }
1237 MDisps *mdisps = static_cast<MDisps *>(CustomData_add_layer(
1238 &base_mesh->corner_data, CD_MDISPS, CD_SET_DEFAULT, base_mesh->corners_num));
1239
1240 const int totdisp = pow_i(CCG_grid_size(context->num_total_levels), 2);
1241 const int totloop = base_mesh->corners_num;
1242
1243 BLI_assert(base_mesh->corners_num == context->num_grids);
1244
1245 /* Allocate the MDISPS grids and copy the extracted data from context. */
1246 for (int i = 0; i < totloop; i++) {
1247 float (*disps)[3] = MEM_new_array_zeroed<float[3]>(totdisp, __func__);
1248
1249 if (mdisps[i].disps) {
1250 MEM_delete(mdisps[i].disps);
1251 }
1252
1253 for (int j = 0; j < totdisp; j++) {
1254 if (context->base_mesh_grids[i].grid_co) {
1255 copy_v3_v3(disps[j], context->base_mesh_grids[i].grid_co[j]);
1256 }
1257 }
1258
1259 mdisps[i].disps = disps;
1260 mdisps[i].totdisp = totdisp;
1261 }
1262}
1263
1264int multiresModifier_rebuild_subdiv(Depsgraph *depsgraph,
1265 Object *object,
1267 int rebuild_limit,
1268 bool switch_view_to_lower_level,
1270{
1271 Mesh *mesh = id_cast<Mesh *>(object->data);
1272
1274
1275 MultiresUnsubdivideContext unsubdiv_context{};
1276 MultiresReshapeContext reshape_context{};
1277
1278 multires_unsubdivide_context_init(&unsubdiv_context, mesh, mmd);
1279
1280 /* Convert and store the existing grids in object space if available. */
1281 if (mmd->totlvl != 0) {
1282 if (!multires_reshape_context_create_from_object(&reshape_context, depsgraph, object, mmd)) {
1283 return 0;
1284 }
1285
1286 multires_reshape_store_original_grids(&reshape_context);
1288 unsubdiv_context.original_mdisp = reshape_context.mdisps;
1289 }
1290
1291 /* Set the limit for the levels that should be rebuild. */
1292 unsubdiv_context.max_new_levels = rebuild_limit;
1293
1294 /* Un-subdivide and create the data for the new grids. */
1295 if (multires_unsubdivide_to_basemesh(&unsubdiv_context, info) == 0) {
1296 /* If there was no possible to rebuild any level, free the data and return. */
1297 if (mmd->totlvl != 0) {
1299 multires_unsubdivide_context_free(&unsubdiv_context);
1300 }
1301 multires_reshape_context_free(&reshape_context);
1302 return 0;
1303 }
1304
1305 /* Free the reshape context used to convert the data from the original grids to object space. */
1306 if (mmd->totlvl != 0) {
1307 multires_reshape_context_free(&reshape_context);
1308 }
1309
1310 /* Copy the new base mesh to the original mesh. */
1311 Mesh *base_mesh = id_cast<Mesh *>(object->data);
1312 BKE_mesh_nomain_to_mesh(unsubdiv_context.base_mesh, base_mesh, object);
1313 multires_create_grids_in_unsubdivided_base_mesh(&unsubdiv_context, base_mesh);
1314
1315 /* Update the levels in the modifier. Force always to display at level 0 as it contains the new
1316 * created level. */
1317 mmd->totlvl = char(unsubdiv_context.num_total_levels);
1318
1319 if (switch_view_to_lower_level) {
1320 mmd->sculptlvl = 0;
1321 mmd->lvl = 0;
1322 }
1323 else {
1324 mmd->sculptlvl = char(mmd->sculptlvl + unsubdiv_context.num_new_levels);
1325 mmd->lvl = char(mmd->lvl + unsubdiv_context.num_new_levels);
1326 }
1327
1328 mmd->renderlvl = char(mmd->renderlvl + unsubdiv_context.num_new_levels);
1329
1330 /* Create a reshape context to convert the MDISPS data to tangent displacement. It can be the
1331 * same as the previous one as a new Subdivision needs to be created for the new base mesh. */
1332 if (!multires_reshape_context_create_from_base_mesh(&reshape_context, depsgraph, object, mmd)) {
1333 return 0;
1334 }
1336 multires_reshape_context_free(&reshape_context);
1337
1338 /* Free the un-subdivide context and return the total number of levels that were rebuild. */
1339 const int rebuild_subdvis = unsubdiv_context.num_new_levels;
1340 multires_unsubdivide_context_free(&unsubdiv_context);
1341
1342 return rebuild_subdvis;
1343}
1344
1346 ReportList *reports)
1347{
1348 if (info.unsupported_grid_count != 0) {
1349 BKE_reportf(reports,
1351 "%d grid(s) with unexpected topology found, "
1352 "multi-res data will be incomplete",
1354 }
1355}
1356
1357} // namespace blender
CustomData interface, see also DNA_customdata_types.h.
Object is a sort of wrapper for general info.
Read Blender memory allocation and freeing.
#define BLI_assert_msg(a, msg)
#define BM_ELEM_CD_GET_INT(ele, offset)
#define BM_elem_index_get(ele)
#define BM_elem_flag_set(ele, hflag, val)
#define BM_elem_flag_test(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BMALLOC_TEMPLATE_FROM_ME(...)
#define BMO_FLAG_DEFAULTS
#define BM_vert_edge_count_is_equal(v, n)
#define BM_vert_edge_count_is_over(v, n)
constexpr int64_t size() const
constexpr IndexRange()=default
constexpr int64_t start() const
GAttributeReader lookup(const StringRef name) const
GSpanAttributeWriter lookup_or_add_for_write_only_span(StringRef name, AttrDomain domain, AttrType data_type)
void fill_index_range(MutableSpan< T > span, const T start=0)
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void multires_reshape_assign_final_coords_from_mdisps(const MultiresReshapeContext *reshape_context)
static BMesh * get_bmesh_from_mesh(Mesh *mesh)
static bool is_vertex_pole_three(BMVert *v)
void BLI_gsqueue_push(GSQueue *queue, const void *item)
Definition gsqueue.cc:104
void BM_mesh_elem_hflag_enable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
void multires_reshape_store_original_grids(MultiresReshapeContext *reshape_context)
static BMVert * unsubdivide_walk_to_tagged_vert(BMVert *v, BMEdge *edge, int *vert_visit, const int visit_id)
static void multires_unsubdivide_add_original_index_datalayers(Mesh *mesh)
static bool multires_unsubdivide_extract_single_grid_from_face_edge(MultiresUnsubdivideContext *context, BMFace *f1, BMEdge *e1, bool flip_grid, MultiresUnsubdivideGrid *grid)
bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
@ RPT_WARNING
Definition BKE_report.hh:40
static void store_grid_data(MultiresUnsubdivideContext *context, MultiresUnsubdivideGrid *grid, BMVert *v, BMFace *f, int grid_x, int grid_y)
static void unsubdivide_build_base_mesh_from_tags(BMesh *bm)
void BM_mesh_free(BMesh *bm)
BMesh Free Mesh.
static void multires_unsubdivide_prepare_original_bmesh_for_extract(MultiresUnsubdivideContext *context)
MINLINE void copy_v3_v3(float r[3], const float a[3])
static void unsubdivide_face_center_vertex_tag(BMesh *bm, BMVert *initial_vertex)
bool multires_unsubdivide_to_basemesh(MultiresUnsubdivideContext *context, MultiresUnsubdivideInfo &info)
bool CustomData_free_layers(CustomData *data, eCustomDataType type)
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void multires_unsubdivide_context_free(MultiresUnsubdivideContext *context)
void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
bool CustomData_has_layer(const CustomData *data, eCustomDataType type)
bool BM_vert_is_wire(const BMVert *v)
void multiresModifier_unsubdivide_report_if_needed(const MultiresUnsubdivideInfo &info, ReportList *reports)
void BKE_mesh_nomain_to_mesh(Mesh *mesh_src, Mesh *mesh_dst, Object *ob, bool process_shape_keys=true)
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
ATTR_WARN_UNUSED_RESULT const BMVert * v
static bool unsubdivide_is_all_quads(BMesh *bm)
bool BM_vert_is_boundary(const BMVert *v)
static void multires_unsubdivide_extract_grids(MultiresUnsubdivideContext *context, MultiresUnsubdivideInfo &info)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static void write_loop_in_face_grid(float(*face_grid)[3], MDisps *mdisp, int face_grid_size, int orig_grid_size, int loop)
void BLI_gsqueue_pop(GSQueue *queue, void *r_item)
Definition gsqueue.cc:139
static const char vname[]
void BM_mesh_bm_from_me(BMesh *bm, const Mesh *mesh, const BMeshFromMeshParams *params)
Mesh -> BMesh.
void BLI_gsqueue_free(GSQueue *queue)
Definition gsqueue.cc:97
static bool multires_unsubdivide_get_grid_corners_on_base_mesh(BMFace *f1, BMEdge *e1, int *vert_visit, int *visit_id, BMVert **r_corner_x, BMVert **r_corner_y)
GSQueue * BLI_gsqueue_new(size_t elem_size)
Definition gsqueue.cc:76
static BMVert * unsubdivide_find_any_pole(BMesh *bm, int *elem_id, int elem)
static bool is_vertex_pole(BMVert *v)
int CustomData_get_offset_named(const CustomData *data, eCustomDataType type, StringRef name)
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
bool multires_reshape_context_create_from_base_mesh(MultiresReshapeContext *reshape_context, Depsgraph *depsgraph, Object *object, MultiresModifierData *mmd)
bool BM_vert_in_face(BMVert *v, BMFace *f)
static bool multires_unsubdivide_flip_grid_x_axis(const OffsetIndices< int > faces, const Span< int > corner_verts, int face_index, int loop, int v_x)
static const char lname[]
static bool multires_unsubdivide_single_level(BMesh *bm)
bool BMO_op_callf(BMesh *bm, int flag, const char *fmt,...)
static BMEdge * get_initial_edge_y(BMFace *f, BMEdge *edge_x, BMVert *initial_vertex)
void multires_force_sculpt_rebuild(Object *object)
Definition multires.cc:332
static void write_face_grid_in_unsubdivide_grid(MultiresUnsubdivideGrid *grid, float(*face_grid)[3], int face_grid_size, int gunsub_x, int gunsub_y)
BLI_INLINE BMVert * BM_vert_at_index(BMesh *bm, const int index)
static bool unsubdivide_is_center_vertex_tag_valid(BMesh *bm, int *elem_id, int elem)
static void multires_unsubdivide_private_extract_data_free(MultiresUnsubdivideContext *context)
static void multires_create_grids_in_unsubdivided_base_mesh(MultiresUnsubdivideContext *context, Mesh *base_mesh)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
int pow_i(int base, int exp)
Definition math_base.cc:15
bool BM_edge_share_quad_check(BMEdge *e1, BMEdge *e2)
void BKE_reportf(ReportList *reports, eReportType type, const char *format,...) ATTR_PRINTF_FORMAT(3
Definition report.cc:191
bool multires_reshape_context_create_from_object(MultiresReshapeContext *reshape_context, Depsgraph *depsgraph, Object *object, MultiresModifierData *mmd)
void multires_reshape_context_free(MultiresReshapeContext *reshape_context)
bool BLI_gsqueue_is_empty(const GSQueue *queue)
Definition gsqueue.cc:167
static bool unsubdivide_tag_disconnected_mesh_element(BMesh *bm, int *elem_id, int elem)
void multires_reshape_object_grids_to_tangent_displacement(const MultiresReshapeContext *reshape_context)
static int unsubdivide_init_elem_ids(BMesh *bm, int *elem_id)
static BMEdge * edge_step(BMVert *v, BMEdge *edge, BMVert **r_next_vertex)
static void multires_unsubdivide_free_original_datalayers(Mesh *mesh)
Mesh * BKE_mesh_new_nomain_from_template(const Mesh *me_src, int verts_num, int edges_num, int faces_num, int corners_num)
int CCG_grid_size(const int level)
Definition BKE_ccg.hh:106
void BM_mesh_bm_to_me(Main *bmain, BMesh *bm, Mesh *mesh, const BMeshToMeshParams *params)
void BM_mesh_elem_table_init(BMesh *bm, const char htype)
static void store_vertex_data(MultiresUnsubdivideGrid *grid, BMVert *v, int grid_x, int grid_y)
int multiresModifier_rebuild_subdiv(Depsgraph *depsgraph, Object *object, MultiresModifierData *mmd, int rebuild_limit, bool switch_view_to_lower_level, MultiresUnsubdivideInfo &info)
BMesh * BM_mesh_create(const BMAllocTemplate *allocsize, const BMeshCreateParams *params)
BMesh Make Mesh.
static bool is_vertex_in_id(BMVert *v, const int *elem_id, int elem)
void multires_unsubdivide_context_init(MultiresUnsubdivideContext *context, Mesh *original_mesh, MultiresModifierData *mmd)
static bool is_vertex_diagonal(BMVert *from_v, BMVert *to_v)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void * CustomData_add_layer(CustomData *data, eCustomDataType type, eCDAllocType alloctype, int totelem)
static BMFace * face_step(BMEdge *edge, BMFace *f)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
struct BMFace * f
CustomData ldata
CustomData corner_data