Blender V5.3
bmo_connect_concave.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
18
19#include <algorithm>
20
21#include "MEM_guardedalloc.h"
22
23#include "BLI_array.hh"
24#include "BLI_heap.hh"
25
26#include "BLI_linklist.hh"
27#include "BLI_math_geom_c.hh"
28#include "BLI_math_vector_c.hh"
29#include "BLI_memarena.hh"
30#include "BLI_polyfill_2d.hh"
32
33#include "bmesh.hh"
34
35#include "intern/bmesh_operators_private.hh" /* own include */
36
37namespace blender {
38
39#define EDGE_OUT (1 << 0)
40#define FACE_OUT (1 << 1)
41
43 BMFace *f_base,
44 const float eps,
45
46 MemArena *pf_arena,
47 Heap *pf_heap)
48{
49 const int f_base_len = f_base->len;
50 int faces_array_tot = f_base_len - 3;
51 int edges_array_tot = f_base_len - 3;
52 Array<BMFace *, BM_DEFAULT_NGON_STACK_SIZE> faces_array(faces_array_tot);
53 Array<BMEdge *, BM_DEFAULT_NGON_STACK_SIZE> edges_array(edges_array_tot);
54 const int quad_method = 0, ngon_method = 0; /* beauty */
55 LinkNode *faces_double = nullptr;
56
57 float normal[3];
58 BLI_assert(f_base->len > 3);
59
60 copy_v3_v3(normal, f_base->no);
61
63 f_base,
64 faces_array.data(),
65 &faces_array_tot,
66 edges_array.data(),
67 &edges_array_tot,
68 &faces_double,
69 quad_method,
70 ngon_method,
71 false,
72 pf_arena,
73 pf_heap);
74
75 BLI_assert(edges_array_tot <= f_base_len - 3);
76
77 if (faces_array_tot) {
78 int i;
79 for (i = 0; i < faces_array_tot; i++) {
80 BMFace *f = faces_array[i];
82 }
83 }
85
86 if (edges_array_tot) {
87 int i;
88
89 std::sort(
90 edges_array.begin(), edges_array.begin() + edges_array_tot, [](BMEdge *e_a, BMEdge *e_b) {
91 int e_a_concave = (BM_elem_flag_test(e_a->v1, BM_ELEM_TAG) &&
92 BM_elem_flag_test(e_a->v2, BM_ELEM_TAG));
93 int e_b_concave = (BM_elem_flag_test(e_b->v1, BM_ELEM_TAG) &&
94 BM_elem_flag_test(e_b->v2, BM_ELEM_TAG));
95
96 /* merge edges between concave edges last since these
97 * are most likely to remain and be the main dividers */
98 if (e_a_concave != e_b_concave) {
99 return e_a_concave < e_b_concave;
100 }
101
102 /* otherwise shortest edges last */
103 const float e_a_len = BM_edge_calc_length_squared(e_a);
104 const float e_b_len = BM_edge_calc_length_squared(e_b);
105 return e_a_len > e_b_len;
106 });
107
108 for (i = 0; i < edges_array_tot; i++) {
109 BMLoop *l_pair[2];
110 BMEdge *e = edges_array[i];
112
113 if (BM_edge_is_contiguous(e) && BM_edge_loop_pair(e, &l_pair[0], &l_pair[1])) {
114 bool ok = true;
115 int j;
116 for (j = 0; j < 2; j++) {
117 BMLoop *l = l_pair[j];
118
119 /* check that merging the edge (on this side)
120 * wouldn't result in a convex face-loop.
121 *
122 * This is the (l->next, l->prev) we would have once joined.
123 */
124 float cross[3];
126
127 if (dot_v3v3(cross, normal) <= eps) {
128 ok = false;
129 break;
130 }
131 }
132
133 if (ok) {
134 BMFace *f_double;
135 BMFace *f_new, *f_pair[2] = {l_pair[0]->f, l_pair[1]->f};
136 f_new = BM_faces_join(bm, f_pair, 2, true, &f_double);
137
138 /* If a double is found - queue the new face to be removed
139 * since it's not expected that this would remove other existing geometry. */
140 if (f_double) [[unlikely]] {
141 BLI_linklist_prepend(&faces_double, f_new);
142 f_new = nullptr;
143 }
144
145 if (f_new) {
147 }
148 }
149 }
150 }
151 }
152
153 BLI_heap_clear(pf_heap, nullptr);
154
155 while (faces_double) {
156 LinkNode *next = faces_double->next;
157 BM_face_kill(bm, static_cast<BMFace *>(faces_double->link));
158 MEM_delete(faces_double);
159 faces_double = next;
160 }
161
162 return true;
163}
164
166{
167 bool is_concave = false;
168 if (f->len > 3) {
169 const BMLoop *l_iter, *l_first;
170
171 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
172 do {
173 if (BM_loop_is_convex(l_iter) == false) {
174 is_concave = true;
176 }
177 else {
179 }
180 } while ((l_iter = l_iter->next) != l_first);
181 }
182 return is_concave;
183}
184
186{
187 BMOIter siter;
188 BMFace *f;
189 bool changed = false;
190
191 MemArena *pf_arena;
192 Heap *pf_heap;
193
194 pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
196
197 BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
198 if (f->len > 3 && bm_face_convex_tag_verts(f)) {
199 if (bm_face_split_by_concave(bm, f, FLT_EPSILON, pf_arena, pf_heap)) {
200 changed = true;
201 }
202 }
203 }
204
205 if (changed) {
208 }
209
210 BLI_memarena_free(pf_arena);
211 BLI_heap_free(pf_heap, nullptr);
212}
213
214} // namespace blender
A min-heap / priority queue ADT.
#define BLI_POLYFILL_ARENA_SIZE
#define BLI_POLYFILL_ALLOC_NGON_RESERVE
Read Blender memory allocation and freeing.
#define BM_FACE_FIRST_LOOP(p)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BMO_edge_flag_enable(bm, e, oflag)
#define BMO_face_flag_enable(bm, e, oflag)
#define BMO_ITER(ele, iter, slot_args, slot_name, restrict_flag)
#define FACE_OUT
Definition bmo_bridge.cc:30
#define EDGE_OUT
Definition bmo_bridge.cc:29
const T * data() const
Definition BLI_array.hh:323
const T * begin() const
Definition BLI_array.hh:332
#define FLT_EPSILON
VecBase< float, 3 > cross(VecOp< float, 3 >, VecOp< float, 3 >) RET
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:173
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
void bmo_connect_verts_concave_exec(BMesh *bm, BMOperator *op)
MINLINE void copy_v3_v3(float r[3], const float a[3])
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **r_faces_new, int *r_faces_new_tot, BMEdge **r_edges_new, int *r_edges_new_tot, LinkNode **r_faces_double, const int quad_method, const int ngon_method, const bool use_tag, MemArena *pf_arena, Heap *pf_heap)
BMESH TRIANGULATE FACE.
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:193
void cross_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:30
void void BLI_linklist_prepend(LinkNode **listp, void *ptr) ATTR_NONNULL(1)
BMFace * BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del, BMFace **r_double)
Join Connected Faces.
void BMO_slot_buffer_from_enabled_flag(BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, short oflag)
BLI_INLINE bool BM_edge_is_contiguous(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
float BM_edge_calc_length_squared(const BMEdge *e)
void BM_face_kill(BMesh *bm, BMFace *f)
static bool bm_face_split_by_concave(BMesh *bm, BMFace *f_base, const float eps, MemArena *pf_arena, Heap *pf_heap)
static bool bm_face_convex_tag_verts(BMFace *f)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:215
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
bool BM_loop_is_convex(const BMLoop *l)
const btScalar eps
Definition poly34.cpp:11
struct BMLoop * next
struct BMVert * v
struct BMFace * f
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]
struct BMLoop * radial_next