28 #include "../intern/bmesh_structure.h"
36 #define USE_CUSTOMDATA
37 #define USE_TRIANGULATE
39 #define USE_VERT_NORMAL_INTERP
42 #define USE_TOPOLOGY_FALLBACK
43 #ifdef USE_TOPOLOGY_FALLBACK
45 # define TOPOLOGY_FALLBACK_EPS 1e-12f
48 #define BOUNDARY_PRESERVE_WEIGHT 100.0f
53 #define OPTIMIZE_EPS 1e-8
54 #define COST_INVALID FLT_MAX
91 }
while ((l_iter = l_iter->
next) != l_first);
99 double edge_plane_db[4];
138 optimize_co[0] = 0.5 * ((
double)
e->v1->
co[0] + (
double)
e->v2->
co[0]);
139 optimize_co[1] = 0.5 * ((
double)
e->v1->
co[1] + (
double)
e->v2->
co[1]);
140 optimize_co[2] = 0.5 * ((
double)
e->v1->
co[2] + (
double)
e->v2->
co[2]);
145 double optimize_co_db[3];
156 for (i = 0; i < 2; i++) {
162 const float *co_prev =
l->
prev->
v->
co;
163 const float *co_next =
l->
next->
v->
co;
164 float cross_exist[3];
165 float cross_optim[3];
183 if (
dot_v3v3(cross_exist, cross_optim) <=
193 if (
dot_v3v3(cross_exist, cross_optim) <= FLT_EPSILON) {
205 #ifdef USE_TOPOLOGY_FALLBACK
227 const float *vweights,
228 const float vweight_factor,
241 if (
e->l->f->len == 3) {
250 if ((
e->l->f->len == 3) && (
e->l->radial_next->f->len == 3)) {
264 double optimize_co[3];
278 #ifdef USE_TOPOLOGY_FALLBACK
284 if (vweights ==
NULL) {
295 cost *= 1.0f + (e_weight * vweight_factor);
331 const float *vweights,
332 const float vweight_factor,
342 eheap_table[i] =
NULL;
364 const float UNUSED(co[3]),
369 float e_other_dir[3];
397 int *edge_symmetry_map;
409 BLI_kdtree_3d_insert(
tree, i, co);
411 edge_symmetry_map[i] = -1;
414 BLI_kdtree_3d_balance(
tree);
420 if (edge_symmetry_map[i] == -1) {
423 co[symmetry_axis] *= -1.0f;
427 sym_data.
e_v1_co[symmetry_axis] *= -1.0f;
428 sym_data.
e_v2_co[symmetry_axis] *= -1.0f;
436 edge_symmetry_map[i] = i_other;
437 edge_symmetry_map[i_other] = i;
443 BLI_kdtree_3d_free(
tree);
445 return edge_symmetry_map;
449 #ifdef USE_TRIANGULATE
468 int *r_edges_tri_tot,
472 struct Heap *pf_heap)
474 const int f_base_len = f_base->
len;
475 int faces_array_tot = f_base_len - 3;
476 int edges_array_tot = f_base_len - 3;
479 const int quad_method = 0, ngon_method = 0;
481 bool has_cut =
false;
498 for (
int i = 0; i < edges_array_tot; i++) {
500 l_iter = l_first = edges_array[i]->
l;
504 }
while ((l_iter = l_iter->
radial_next) != l_first);
507 for (
int i = 0; i < faces_array_tot; i++) {
511 *r_edges_tri_tot += edges_array_tot;
520 bool has_ngon =
false;
521 bool has_cut =
false;
533 }
while ((l_iter = l_iter->
next) != l_first);
535 has_ngon |= (f->
len > 4);
570 while (faces_double) {
611 if (l_a_index != -1) {
613 if (l_a_index == l_b_index) {
614 if (l_a->
v !=
l_b->
v) {
617 # define CAN_LOOP_MERGE(l) \
618 (BM_loop_is_manifold(l) && ((l)->v != (l)->radial_next->v) && \
619 (l_a_index == BM_elem_index_get(l)) && (l_a_index == BM_elem_index_get((l)->radial_next)))
631 BLI_assert(
ELEM(vquad[0], vquad[1], vquad[2], vquad[3]) ==
false);
632 BLI_assert(
ELEM(vquad[1], vquad[0], vquad[2], vquad[3]) ==
false);
633 BLI_assert(
ELEM(vquad[2], vquad[1], vquad[0], vquad[3]) ==
false);
634 BLI_assert(
ELEM(vquad[3], vquad[1], vquad[2], vquad[0]) ==
false);
636 if (!
is_quad_convex_v3(vquad[0]->co, vquad[1]->co, vquad[2]->co, vquad[3]->co)) {
640 # undef CAN_LOOP_MERGE
650 for (
int i = 0; i <
STACK_SIZE(edges_tri); i++) {
669 #ifdef USE_CUSTOMDATA
681 BMLoop *l_clear, *l_other;
686 if (
l->
v == v_clear) {
701 for (side = 0; side < 2; side++) {
703 bool is_seam =
false;
713 l_iter = l_first = l_clear;
717 w[0] = customdata_fac;
718 w[1] = 1.0f - customdata_fac;
721 l_iter = l_first = l_other;
725 w[0] = 1.0f - customdata_fac;
726 w[1] = customdata_fac;
737 if (f_exit &&
UNLIKELY(f_exit == l_iter->
f)) {
751 const void *cd_src[2] = {
800 if (
e->l !=
e->l->radial_next) {
812 if (
e->l !=
e->l->radial_next) {
892 l_radial = e_first->
l;
900 if (l_radial != l_face) {
934 int r_e_clear_other[2],
936 int *edge_symmetry_map,
940 const float customdata_fac
943 const float UNUSED(customdata_fac)
954 BMEdge *e_a_other[2], *e_b_other[2];
966 e_a_other[0] = l_a->
prev->
e;
967 e_a_other[1] = l_a->
next->
e;
970 e_a_other[1] = l_a->
prev->
e;
971 e_a_other[0] = l_a->
next->
e;
991 if (
ELEM(e_a_other[0], e_b_other[0], e_b_other[1]) ||
992 ELEM(e_a_other[1], e_b_other[0], e_b_other[1])) {
1002 #ifdef USE_CUSTOMDATA
1030 if (edge_symmetry_map) {
1031 if (edge_symmetry_map[r_e_clear_other[0]] != -1) {
1032 edge_symmetry_map[edge_symmetry_map[r_e_clear_other[0]]] =
BM_elem_index_get(e_a_other[1]);
1034 if (edge_symmetry_map[r_e_clear_other[1]] != -1) {
1035 edge_symmetry_map[edge_symmetry_map[r_e_clear_other[1]]] =
BM_elem_index_get(e_b_other[1]);
1055 e_a_other[0] = l_a->
prev->
e;
1056 e_a_other[1] = l_a->
next->
e;
1059 e_a_other[1] = l_a->
prev->
e;
1060 e_a_other[0] = l_a->
next->
e;
1064 r_e_clear_other[1] = -1;
1066 #ifdef USE_CUSTOMDATA
1089 if (edge_symmetry_map) {
1090 if (edge_symmetry_map[r_e_clear_other[0]] != -1) {
1091 edge_symmetry_map[edge_symmetry_map[r_e_clear_other[0]]] =
BM_elem_index_get(e_a_other[1]);
1112 const float vweight_factor,
1116 int *edge_symmetry_map,
1119 float optimize_co[3],
1120 bool optimize_co_calc)
1122 int e_clear_other[2];
1127 float customdata_fac;
1129 #ifdef USE_VERT_NORMAL_INTERP
1130 float v_clear_no[3];
1135 if (optimize_co_calc) {
1158 if (customdata_fac < 0.0 - FLT_EPSILON || customdata_fac > 1.0f + FLT_EPSILON) {
1165 customdata_fac = 0.5f;
1181 float v_other_weight =
interpf(
1182 vweights[v_other_index], vweights[v_clear_index], customdata_fac);
1183 CLAMP(v_other_weight, 0.0f, 1.0f);
1184 vweights[v_other_index] = v_other_weight;
1193 for (i = 0; i < 2; i++) {
1195 if ((e_clear_other[i] != -1) && (eheap_table[e_clear_other[i]] !=
NULL)) {
1197 eheap_table[e_clear_other[i]] =
NULL;
1208 #ifdef USE_VERT_NORMAL_INTERP
1219 e_iter = e_first = v_other->
e;
1223 e_iter, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1236 if (
l->
f->
len == 3) {
1248 e_outer, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1267 float vweight_factor,
1268 const bool do_triangulate,
1269 const int symmetry_axis,
1270 const float symmetry_eps)
1279 int face_tot_target;
1284 bool use_symmetry = (symmetry_axis != -1);
1285 int *edge_symmetry_map;
1288 #ifdef USE_TRIANGULATE
1289 int edges_tri_tot = 0;
1318 #ifdef USE_CUSTOMDATA
1333 if (use_symmetry ==
false)
1341 float optimize_co[3];
1377 const int e_index_mirr = edge_symmetry_map[e_index];
1379 float optimize_co[3];
1380 char e_invalidate = 0;
1384 eheap_table[e_index] =
NULL;
1386 if (e_index_mirr != -1) {
1387 if (e_index_mirr == e_index) {
1390 else if (eheap_table[e_index_mirr]) {
1418 e_invalidate |= (1 | (e_mirr ? 2 : 0));
1424 if (e_index_mirr == e_index) {
1425 optimize_co[symmetry_axis] = 0.0f;
1430 e_invalidate |= (1 | (e_mirr ? 2 : 0));
1446 if (e_mirr && (eheap_table[e_index_mirr])) {
1449 eheap_table[e_index_mirr] =
NULL;
1450 optimize_co[symmetry_axis] *= -1.0f;
1465 if (e_mirr && (eheap_table[e_index_mirr])) {
1475 if (e_invalidate & 1) {
1479 if (e_invalidate & 2) {
1482 eheap_table[e_index_mirr] =
NULL;
1491 #ifdef USE_TRIANGULATE
1492 if (do_triangulate ==
false) {
1494 if (
LIKELY(use_triangulate)) {
1510 (
void)tot_edge_orig;
CustomData interface, see also DNA_customdata_types.h.
bool CustomData_has_math(const struct CustomData *data)
void CustomData_bmesh_interp_n(struct CustomData *data, const void **src_blocks, const float *weights, const float *sub_weights, int count, void *dst_block_ofs, int n)
bool CustomData_data_equals(int type, const void *data1, const void *data2)
bool CustomData_has_interp(const struct CustomData *data)
bool CustomData_layer_has_math(const struct CustomData *data, int layer_n)
#define BLI_array_alloca(arr, realsize)
A min-heap / priority queue ADT.
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
float BLI_heap_top_value(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
void * BLI_heap_node_ptr(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
A KD-tree for nearest neighbor search.
MINLINE float min_ff(float a, float b)
MINLINE float square_f(float a)
MINLINE float interpf(float a, float b, float t)
bool is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
MINLINE double normalize_v3_db(double n[3])
MINLINE bool compare_v3v3(const float a[3], const float b[3], float limit) ATTR_WARN_UNUSED_RESULT
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float normalize_v3(float r[3])
MINLINE float len_squared_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
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void copy_v3fl_v3db(float r[3], const double a[3])
MINLINE void copy_v3db_v3fl(double r[3], const float a[3])
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
void BLI_memarena_free(struct MemArena *ma) ATTR_NONNULL(1)
struct MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
#define BLI_POLYFILL_ARENA_SIZE
#define BLI_POLYFILL_ALLOC_NGON_RESERVE
void BLI_quadric_mul(Quadric *a, double scalar)
bool BLI_quadric_optimize(const Quadric *q, double v[3], double epsilon)
void BLI_quadric_from_plane(Quadric *q, const double v[4])
double BLI_quadric_evaluate(const Quadric *q, const double v[3])
void BLI_quadric_add_qu_qu(Quadric *a, const Quadric *b)
void BLI_quadric_add_qu_ququ(Quadric *r, const Quadric *a, const Quadric *b)
#define UNUSED_VARS_NDEBUG(...)
#define POINTER_OFFSET(v, ofs)
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
typedef double(DMatrix)[4][4]
NSNotificationCenter * center
_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
Read Guarded memory(de)allocation.
Group Output data from inside of a node group A color picker Mix two input colors RGB to Convert a color s luminance to a grayscale value Generate a normal vector and a dot product Bright Control the brightness and contrast of the input color Vector Map an input vectors to used to fine tune the interpolation of the input Camera Retrieve information about the camera and how it relates to the current shading point s position CLAMP
#define BM_FACE_FIRST_LOOP(p)
BMFace * BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del)
Join Connected Faces.
bool BM_edge_splice(BMesh *bm, BMEdge *e_dst, BMEdge *e_src)
Splice Edge.
bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src)
Splice Vert.
void BM_face_kill(BMesh *bm, BMFace *f)
void BM_edge_kill(BMesh *bm, BMEdge *e)
static void bm_edge_tag_enable(BMEdge *e)
static void bm_decim_invalid_edge_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table)
static bool bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
static void bm_decim_build_edge_cost(BMesh *bm, const Quadric *vquadrics, const float *vweights, const float vweight_factor, Heap *eheap, HeapNode **eheap_table)
#define TOPOLOGY_FALLBACK_EPS
static int * bm_edge_symmetry_map(BMesh *bm, uint symmetry_axis, float limit)
static void bm_edge_tag_disable(BMEdge *e)
static bool bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_co[3])
static bool bm_face_triangulate(BMesh *bm, BMFace *f_base, LinkNode **r_faces_double, int *r_edges_tri_tot, MemArena *pf_arena, struct Heap *pf_heap)
void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, float vweight_factor, const bool do_triangulate, const int symmetry_axis, const float symmetry_eps)
BM_mesh_decimate.
static void bm_decim_triangulate_end(BMesh *bm, const int edges_tri_tot)
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)
#define BOUNDARY_PRESERVE_WEIGHT
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)
#define CAN_LOOP_MERGE(l)
BLI_INLINE int bm_edge_is_manifold_or_boundary(BMLoop *l)
static float bm_decim_build_edge_cost_single__topology(BMEdge *e)
static bool bm_decim_triangulate_begin(BMesh *bm, int *r_edges_tri_tot)
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)
static void bm_decim_calc_target_co_db(BMEdge *e, double optimize_co[3], const Quadric *vquadrics)
static float bm_decim_build_edge_cost_single_squared__topology(BMEdge *e)
static bool bm_edge_symmetry_check_cb(void *user_data, int index, const float UNUSED(co[3]), float UNUSED(dist_sq))
static bool bm_edge_tag_test(BMEdge *e)
static void bm_edge_collapse_loop_customdata(BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other, const float customdata_fac)
static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics)
#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)
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.
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.
#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)
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
void BM_vert_normal_update(BMVert *v)
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, struct Heap *pf_heap)
void BM_face_normal_update(BMFace *f)
void BM_face_calc_center_median(const BMFace *f, float r_cent[3])
BMEdge * BM_edge_find_double(BMEdge *e)
bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
bool BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2)
BMVert * BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
float BM_edge_calc_length(const BMEdge *e)
BMLoop * BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step)
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
ATTR_WARN_UNUSED_RESULT const BMVert * v
BLI_INLINE BMEdge * bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
SIMD_FORCE_INLINE void invalidate()
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
SyclQueue void void * src
SyclQueue void void size_t num_bytes void
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
void(* MEM_freeN)(void *vmemh)
void *(* MEM_callocN)(size_t len, const char *str)
void *(* MEM_mallocN)(size_t len, const char *str)
static void clear(Message *msg)
struct BMLoop * radial_next