43#define USE_TRIANGULATE
45#define USE_VERT_NORMAL_INTERP
48#define USE_TOPOLOGY_FALLBACK
49#ifdef USE_TOPOLOGY_FALLBACK
51# define TOPOLOGY_FALLBACK_EPS 1e-12f
54#define BOUNDARY_PRESERVE_WEIGHT 100.0f
59#define OPTIMIZE_EPS 1e-8
60#define COST_INVALID FLT_MAX
98 }
while ((l_iter = l_iter->
next) != l_first);
104 float edge_vector[3];
106 double edge_plane_db[4];
145 optimize_co[0] = 0.5 * (double(
e->v1->
co[0]) + double(
e->v2->
co[0]));
146 optimize_co[1] = 0.5 * (double(
e->v1->
co[1]) + double(
e->v2->
co[1]));
147 optimize_co[2] = 0.5 * (double(
e->v1->
co[2]) + double(
e->v2->
co[2]));
152 double optimize_co_db[3];
163 for (i = 0; i < 2; i++) {
169 const float *co_prev =
l->
prev->
v->
co;
170 const float *co_next =
l->
next->
v->
co;
171 float cross_exist[3];
172 float cross_optim[3];
190 if (
dot_v3v3(cross_exist, cross_optim) <=
213#ifdef USE_TOPOLOGY_FALLBACK
235 const float *vweights,
236 const float vweight_factor,
250 if (
e->l->f->len == 3) {
259 if ((
e->l->f->len == 3) && (
e->l->radial_next->f->len == 3)) {
273 double optimize_co[3];
287#ifdef USE_TOPOLOGY_FALLBACK
293 if (vweights ==
nullptr) {
304 cost *= 1.0f + (e_weight * vweight_factor);
341 const float *vweights,
342 const float vweight_factor,
353 eheap_table[i] =
nullptr;
381 float e_other_dir[3];
411 int *edge_symmetry_map;
412 const float limit_sq =
square_f(limit);
425 edge_symmetry_map[i] = -1;
434 if (edge_symmetry_map[i] == -1) {
437 co[symmetry_axis] *= -1.0f;
441 sym_data.
e_v1_co[symmetry_axis] *= -1.0f;
442 sym_data.
e_v2_co[symmetry_axis] *= -1.0f;
447 tree, co, limit, [&](
int index,
const float3 &co,
float dist_sq) {
453 edge_symmetry_map[i] = i_other;
454 edge_symmetry_map[i_other] = i;
462 return edge_symmetry_map;
466#ifdef USE_TRIANGULATE
485 int *r_edges_tri_tot,
491 const int f_base_len = f_base->
len;
492 int faces_array_tot = f_base_len - 3;
493 int edges_array_tot = f_base_len - 3;
496 const int quad_method = 0, ngon_method = 0;
498 bool has_cut =
false;
515 for (
int i = 0; i < edges_array_tot; i++) {
517 l_iter = l_first = edges_array[i]->l;
521 }
while ((l_iter = l_iter->
radial_next) != l_first);
524 for (
int i = 0; i < faces_array_tot; i++) {
528 *r_edges_tri_tot += edges_array_tot;
537 bool has_ngon =
false;
538 bool has_cut =
false;
550 }
while ((l_iter = l_iter->
next) != l_first);
552 has_ngon |= (f->
len > 4);
587 while (faces_double) {
590 MEM_delete(faces_double);
628 if (l_a_index != -1) {
630 if (l_a_index == l_b_index) {
631 if (l_a->
v !=
l_b->
v) {
634# define CAN_LOOP_MERGE(l) \
635 (BM_loop_is_manifold(l) && ((l)->v != (l)->radial_next->v) && \
636 (l_a_index == BM_elem_index_get(l)) && (l_a_index == BM_elem_index_get((l)->radial_next)))
649 BLI_assert(
ELEM(vquad[0], vquad[1], vquad[2], vquad[3]) ==
false);
650 BLI_assert(
ELEM(vquad[1], vquad[0], vquad[2], vquad[3]) ==
false);
651 BLI_assert(
ELEM(vquad[2], vquad[1], vquad[0], vquad[3]) ==
false);
652 BLI_assert(
ELEM(vquad[3], vquad[1], vquad[2], vquad[0]) ==
false);
654 if (!
is_quad_convex_v3(vquad[0]->co, vquad[1]->co, vquad[2]->co, vquad[3]->co)) {
658# undef CAN_LOOP_MERGE
668 for (
int i = 0; i <
STACK_SIZE(edges_tri); i++) {
680 if (f_double !=
nullptr) [[unlikely]] {
684 if (
e->l ==
nullptr) {
689 MEM_delete(edges_tri);
709 BMLoop *l_clear, *l_other;
714 if (
l->
v == v_clear) {
729 for (side = 0; side < 2; side++) {
731 bool is_seam =
false;
741 l_iter = l_first = l_clear;
745 w[0] = customdata_fac;
746 w[1] = 1.0f - customdata_fac;
749 l_iter = l_first = l_other;
753 w[0] = 1.0f - customdata_fac;
754 w[1] = customdata_fac;
765 if (f_exit &&
UNLIKELY(f_exit == l_iter->
f)) {
779 const void *cd_src[2] = {
827 if (
e->l !=
e->l->radial_next) {
839 if (
e->l !=
e->l->radial_next) {
919 l_radial = e_first->
l;
927 if (l_radial != l_face) {
961 int r_e_clear_other[2],
963 int *edge_symmetry_map,
967 const float customdata_fac
981 BMEdge *e_a_other[2], *e_b_other[2];
993 e_a_other[0] = l_a->
prev->
e;
994 e_a_other[1] = l_a->
next->
e;
997 e_a_other[1] = l_a->
prev->
e;
998 e_a_other[0] = l_a->
next->
e;
1018 if (
ELEM(e_a_other[0], e_b_other[0], e_b_other[1]) ||
1019 ELEM(e_a_other[1], e_b_other[0], e_b_other[1]))
1030#ifdef USE_CUSTOMDATA
1058 if (edge_symmetry_map) {
1059 if (edge_symmetry_map[r_e_clear_other[0]] != -1) {
1060 edge_symmetry_map[edge_symmetry_map[r_e_clear_other[0]]] =
BM_elem_index_get(e_a_other[1]);
1062 if (edge_symmetry_map[r_e_clear_other[1]] != -1) {
1063 edge_symmetry_map[edge_symmetry_map[r_e_clear_other[1]]] =
BM_elem_index_get(e_b_other[1]);
1083 e_a_other[0] = l_a->
prev->
e;
1084 e_a_other[1] = l_a->
next->
e;
1087 e_a_other[1] = l_a->
prev->
e;
1088 e_a_other[0] = l_a->
next->
e;
1092 r_e_clear_other[1] = -1;
1094#ifdef USE_CUSTOMDATA
1117 if (edge_symmetry_map) {
1118 if (edge_symmetry_map[r_e_clear_other[0]] != -1) {
1119 edge_symmetry_map[edge_symmetry_map[r_e_clear_other[0]]] =
BM_elem_index_get(e_a_other[1]);
1140 const float vweight_factor,
1144 int *edge_symmetry_map,
1147 float optimize_co[3],
1148 bool optimize_co_calc)
1150 int e_clear_other[2];
1155 float customdata_fac;
1157#ifdef USE_VERT_NORMAL_INTERP
1158 float v_clear_no[3];
1163 if (optimize_co_calc) {
1186 if (customdata_fac < 0.0 - FLT_EPSILON || customdata_fac > 1.0f +
FLT_EPSILON) {
1193 customdata_fac = 0.5f;
1210 float v_other_weight =
interpf(
1211 vweights[v_other_index], vweights[v_clear_index], customdata_fac);
1212 CLAMP(v_other_weight, 0.0f, 1.0f);
1213 vweights[v_other_index] = v_other_weight;
1222 for (i = 0; i < 2; i++) {
1224 if ((e_clear_other[i] != -1) && (eheap_table[e_clear_other[i]] !=
nullptr)) {
1226 eheap_table[e_clear_other[i]] =
nullptr;
1237#ifdef USE_VERT_NORMAL_INTERP
1245 if (v_other->
e) [[likely]] {
1248 e_iter = e_first = v_other->
e;
1252 e_iter, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1265 if (
l->
f->
len == 3) {
1277 e_outer, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1296 float vweight_factor,
1297 const bool do_triangulate,
1298 const int symmetry_axis,
1299 const float symmetry_eps)
1308 int face_tot_target;
1313 bool use_symmetry = (symmetry_axis != -1);
1314 int *edge_symmetry_map;
1317#ifdef USE_TRIANGULATE
1318 int edges_tri_tot = 0;
1352#ifdef USE_CUSTOMDATA
1367 if (use_symmetry ==
false)
1376 float optimize_co[3];
1412 const int e_index_mirr = edge_symmetry_map[e_index];
1413 BMEdge *e_mirr =
nullptr;
1414 float optimize_co[3];
1415 char e_invalidate = 0;
1419 eheap_table[e_index] =
nullptr;
1421 if (e_index_mirr != -1) {
1422 if (e_index_mirr == e_index) {
1425 else if (eheap_table[e_index_mirr]) {
1452 if (!ok_a || !ok_b) [[unlikely]] {
1453 e_invalidate |= (1 | (e_mirr ? 2 : 0));
1459 if (e_index_mirr == e_index) {
1460 optimize_co[symmetry_axis] = 0.0f;
1465 e_invalidate |= (1 | (e_mirr ? 2 : 0));
1482 if (e_mirr && (eheap_table[e_index_mirr])) {
1485 eheap_table[e_index_mirr] =
nullptr;
1486 optimize_co[symmetry_axis] *= -1.0f;
1501 if (e_mirr && (eheap_table[e_index_mirr])) {
1511 if (e_invalidate & 1) {
1515 if (e_invalidate & 2) {
1516 BLI_assert(eheap_table[e_index_mirr] !=
nullptr);
1518 eheap_table[e_index_mirr] =
nullptr;
1523 MEM_delete(edge_symmetry_map);
1527#ifdef USE_TRIANGULATE
1528 if (do_triangulate ==
false) {
1530 if (use_triangulate) [[likely]] {
1538 MEM_delete(vquadrics);
1539 MEM_delete(eheap_table);
1546 (void)tot_edge_orig;
CustomData interface, see also DNA_customdata_types.h.
#define ENUM_OPERATORS(_enum_type)
A min-heap / priority queue ADT.
A KD-tree for nearest neighbor search.
#define BLI_POLYFILL_ARENA_SIZE
#define BLI_POLYFILL_ALLOC_NGON_RESERVE
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
Read Blender memory allocation and freeing.
#define UNUSED_VARS_NDEBUG(...)
#define POINTER_OFFSET(v, ofs)
#define BM_FACE_FIRST_LOOP(p)
#define TOPOLOGY_FALLBACK_EPS
#define BOUNDARY_PRESERVE_WEIGHT
#define CAN_LOOP_MERGE(l)
#define BM_elem_index_get(ele)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
SIMD_FORCE_INLINE void invalidate()
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
MINLINE float min_ff(float a, float b)
static bool bm_decim_triangulate_begin(BMesh *bm, int *r_edges_tri_tot)
void BM_face_calc_center_median(const BMFace *f, float r_cent[3])
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
void kdtree_balance(KDTree< CoordT > *tree)
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
static bool bm_face_triangulate(BMesh *bm, BMFace *f_base, LinkNode **r_faces_double, int *r_edges_tri_tot, MemArena *pf_arena, Heap *pf_heap)
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
MINLINE void copy_v3_v3(float r[3], const float a[3])
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
ATTR_WARN_UNUSED_RESULT const BMLoop * l
static void bm_decim_build_edge_cost_single(BMEdge *e, const Quadric *vquadrics, const float *vweights, const float vweight_factor, Heap *eheap, HeapNode **eheap_table)
MINLINE void copy_v3db_v3fl(double r[3], const float a[3])
static void bm_decim_build_edge_cost(BMesh *bm, const Quadric *vquadrics, const float *vweights, const float vweight_factor, Heap *eheap, HeapNode **eheap_table)
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
static void bm_decim_calc_target_co_fl(BMEdge *e, float optimize_co[3], const Quadric *vquadrics)
static bool bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e_clear_other[2], int *edge_symmetry_map, const CD_UseFlag customdata_flag, const float customdata_fac)
bool CustomData_has_interp(const CustomData *data)
BMVert * BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
static bool bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_co[3])
void BLI_quadric_from_plane(Quadric *q, const double v[4])
void kdtree_range_search_cb(const KDTree< CoordT > *tree, const CoordT &co, typename KDTree< CoordT >::ValueType range, Fn &&search_cb)
static bool bm_decim_edge_collapse(BMesh *bm, BMEdge *e, Quadric *vquadrics, float *vweights, const float vweight_factor, Heap *eheap, HeapNode **eheap_table, int *edge_symmetry_map, const CD_UseFlag customdata_flag, float optimize_co[3], bool optimize_co_calc)
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.
BMLoop * BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step)
bool CustomData_data_equals(eCustomDataType type, const void *data1, const void *data2)
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
static bool bm_edge_tag_test(BMEdge *e)
ATTR_WARN_UNUSED_RESULT const BMVert * v
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
void BM_data_interp_from_edges(BMesh *bm, const BMEdge *e_src_1, const BMEdge *e_src_2, BMEdge *e_dst, const float fac)
Data, Interpolate From Edges.
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void BLI_quadric_add_qu_ququ(Quadric *r, const Quadric *a, const Quadric *b)
static bool bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
float BM_edge_calc_length(const BMEdge *e)
bool BLI_quadric_optimize(const Quadric *q, double v[3], double epsilon)
BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
static void bm_edge_tag_disable(BMEdge *e)
static float bm_decim_build_edge_cost_single_squared__topology(BMEdge *e)
void BM_vert_normal_update(BMVert *v)
BMFace * BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del, BMFace **r_double)
Join Connected Faces.
KDTree< CoordT > * kdtree_new(uint nodes_len_capacity)
static int * bm_edge_symmetry_map(BMesh *bm, uint symmetry_axis, float limit)
bool BM_edge_splice(BMesh *bm, BMEdge *e_dst, BMEdge *e_src)
Splice Edge.
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
void BM_face_normal_update(BMFace *f)
void CustomData_bmesh_interp_n(CustomData *data, const void **src_blocks, const float *weights, int count, void *dst_block_ofs, int n)
void BM_edge_kill(BMesh *bm, BMEdge *e)
float BLI_heap_top_value(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
void kdtree_insert(KDTree< CoordT > *tree, int index, const CoordT &co)
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src)
Splice Vert.
void BLI_quadric_add_qu_qu(Quadric *a, const Quadric *b)
BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
static void bm_decim_calc_target_co_db(BMEdge *e, double optimize_co[3], const Quadric *vquadrics)
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1
static bool bm_edge_symmetry_check_cb(void *user_data, int index, const float3 &, float)
MINLINE void copy_v3fl_v3db(float r[3], const double a[3])
MINLINE float normalize_v3(float n[3])
void kdtree_free(KDTree< CoordT > *tree)
bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE bool compare_v3v3(const float v1[3], const float v2[3], float limit) ATTR_WARN_UNUSED_RESULT
void BM_mesh_decimate_collapse(BMesh *bm, float factor, float *vweights, float vweight_factor, bool do_triangulate, int symmetry_axis, float symmetry_eps)
BM_mesh_decimate.
void BM_face_kill(BMesh *bm, BMFace *f)
bool is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
double BLI_quadric_evaluate(const Quadric *q, const double v[3])
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float square_f(float a)
MINLINE float interpf(float target, float origin, float t)
BMEdge * BM_edge_find_double(BMEdge *e)
BLI_INLINE BMEdge * bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE int bm_edge_is_manifold_or_boundary(BMLoop *l)
static void bm_decim_triangulate_end(BMesh *bm, const int edges_tri_tot)
void BM_data_interp_from_verts(BMesh *bm, const BMVert *v_src_1, const BMVert *v_src_2, BMVert *v_dst, const float fac)
Data, Interpolate From Verts.
bool CustomData_has_math(const CustomData *data)
VecBase< float, 3 > float3
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
bool BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2)
static void bm_decim_invalid_edge_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table)
MINLINE double normalize_v3_db(double n[3])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE double dot_v3db_v3fl(const double a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
static float bm_decim_build_edge_cost_single__topology(BMEdge *e)
static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics)
bool CustomData_layer_has_math(const CustomData *data, int layer_n)
static void bm_edge_collapse_loop_customdata(BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other, const float customdata_fac)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void BLI_quadric_mul(Quadric *a, double scalar)
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void * BLI_heap_node_ptr(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
static void bm_edge_tag_enable(BMEdge *e)
struct BMLoop * radial_next
struct BMLoop * radial_next