35#define ASSERT_VALID_ERROR_METRIC(val) BLI_assert(isfinite(val) && (val) >= 0 && (val) <= 2 * M_PI)
80# define USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
83#define FACE_OUT (1 << 0)
84#define FACE_INPUT (1 << 2)
120#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
128 int debug_merge_limit;
131 int debug_merge_count;
146 int debug_neighbor_global_count;
153 bool debug_this_step;
183 float angle_a, angle_b;
194 diff = (angle_a + angle_b) /
float(
M_PI * 2);
203 float edge_vecs[4][3];
230 float area_min, area_max, area_a, area_b;
236 area_min =
min_ff(area_a, area_b);
237 area_max =
max_ff(area_a, area_b);
240 diff = area_max ? (1.0f - (area_min / area_max)) : 1.0f;
261 BLI_assert(
e->l->f->len == 3 &&
e->l->radial_next->f->len == 3);
262 r_v_quad[0] =
e->l->v;
263 r_v_quad[1] =
e->l->radial_next->prev->v;
264 r_v_quad[2] =
e->l->next->v;
265 r_v_quad[3] =
e->l->prev->v;
276struct DelimitData_CD {
287 uint do_angle_face : 1;
288 uint do_angle_shape : 1;
291 float angle_face__cos;
295 DelimitData_CD cdata[4];
305 for (cd_offset = delimit_data->cd_offset; cd_offset < delimit_data->cd_offset_end;
306 cd_offset += delimit_data->cd_size)
319 DelimitData_CD *r_delim_cd)
322 r_delim_cd->cd_type = type;
325 r_delim_cd->cd_offset_end = r_delim_cd->cd_offset + (r_delim_cd->cd_size * layer_len);
326 return (r_delim_cd->cd_offset != -1);
337 DelimitData delimit_data = {0};
344 if (angle_face <
DEG2RADF(180.0f)) {
345 delimit_data.angle_face = angle_face;
346 delimit_data.angle_face__cos =
cosf(angle_face);
347 delimit_data.do_angle_face =
true;
350 delimit_data.do_angle_face =
false;
355 if (angle_shape <
DEG2RADF(180.0f)) {
356 delimit_data.angle_shape = angle_shape;
357 delimit_data.do_angle_shape =
true;
360 delimit_data.do_angle_shape =
false;
367 delimit_data.cdata_len += 1;
370 delimit_data.cdata[delimit_data.cdata_len].cd_offset = -1;
375 delimit_data.cdata_len += 1;
377 delimit_data.cdata[delimit_data.cdata_len].cd_offset = -1;
382 delimit_data.cdata_len += 1;
397 BMFace *f_a =
e->l->f, *f_b =
e->l->radial_next->f;
411 if (delimit_data->do_mat && (f_a->
mat_nr != f_b->mat_nr)) {
415 if (delimit_data->do_angle_face) {
416 if (
dot_v3v3(f_a->
no, f_b->no) < delimit_data->angle_face__cos) {
421 if (delimit_data->do_angle_shape) {
426 if (
is_quad_flip_v3(verts[0]->co, verts[1]->co, verts[2]->co, verts[3]->co)) {
430 float edge_vecs[4][3];
432 sub_v3_v3v3(edge_vecs[0], verts[0]->co, verts[1]->co);
433 sub_v3_v3v3(edge_vecs[1], verts[1]->co, verts[2]->co);
434 sub_v3_v3v3(edge_vecs[2], verts[2]->co, verts[3]->co);
435 sub_v3_v3v3(edge_vecs[3], verts[3]->co, verts[0]->co);
443 delimit_data->angle_shape) ||
445 delimit_data->angle_shape) ||
447 delimit_data->angle_shape) ||
449 delimit_data->angle_shape))
455 if (delimit_data->cdata_len) {
457 for (i = 0; i < delimit_data->cdata_len; i++) {
535 if (l_in_neighbor->
f->
len != 3) {
541 const int items_num_prev = neighbor_info.
items_num;
545 BMLoop *l_other_arr[2] = {l_in_neighbor->
prev, l_in_neighbor->
next};
546 for (
int i = 0; i <
ARRAY_SIZE(l_other_arr); i++) {
547 BMLoop *l_other = l_other_arr[i];
573 const BMVert *quad_verts[4],
575 const float plane_normal[3],
576 float r_quad_coordinates[4][3])
578#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
579 if (s.debug_this_step) {
586 float rotation_axis[3];
590 float quad_normal[3] = {0};
592 quad_normal, quad_verts[0]->co, quad_verts[1]->co, quad_verts[2]->co, quad_verts[3]->co);
596#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
597 if (s.debug_this_step) {
602 for (
int i = 0; i < 4; i++) {
603 if (
ELEM(quad_verts[i], l_shared->
v, l_shared->
next->
v)) {
606 copy_v3_v3(r_quad_coordinates[i], quad_verts[i]->co);
610 float local_coordinate[3];
611 sub_v3_v3v3(local_coordinate, quad_verts[i]->co, l_shared->
v->
co);
650 const float quad_a_vecs[4][3],
651 const BMVert *quad_b_verts[4],
653 const float plane_normal[3])
659 float quad_b_coordinates[4][3];
660 rotate_to_plane(s, quad_b_verts, l_shared, plane_normal, quad_b_coordinates);
662#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
663 if (s.debug_this_step) {
669 copy_v3_v3(
const_cast<BMVert *
>(quad_b_verts[0])->co, quad_b_coordinates[0]);
670 copy_v3_v3(
const_cast<BMVert *
>(quad_b_verts[1])->co, quad_b_coordinates[1]);
671 copy_v3_v3(
const_cast<BMVert *
>(quad_b_verts[2])->co, quad_b_coordinates[2]);
672 copy_v3_v3(
const_cast<BMVert *
>(quad_b_verts[3])->co, quad_b_coordinates[3]);
677 float quad_b_vecs[4][3];
678 sub_v3_v3v3(quad_b_vecs[0], quad_b_coordinates[0], quad_b_coordinates[1]);
679 sub_v3_v3v3(quad_b_vecs[1], quad_b_coordinates[1], quad_b_coordinates[2]);
680 sub_v3_v3v3(quad_b_vecs[2], quad_b_coordinates[2], quad_b_coordinates[3]);
681 sub_v3_v3v3(quad_b_vecs[3], quad_b_coordinates[3], quad_b_coordinates[0]);
700 float error[4] = {0.0f};
712 error[2] +=
M_PI - angle_a;
716 error[3] +=
M_PI - angle_b;
720 const float best_error = std::min({error[0], error[1], error[2], error[3]}) / 4.0f;
727 float alignment = 1.0f - (best_error / (
M_PI / 4.0f));
730 alignment = std::max(alignment, 0.0f);
769 float neighbor_quad_vecs[4][3],
770 const float neighbor_quad_error,
771 const float neighbor_quad_normal[3])
779 if (
node ==
nullptr) {
791 if (neighbor_quad_error > join_error_curr) {
793#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
802#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
803 if (s.debug_this_step) {
804 printf(
"Edge improved from ");
809 const BMVert *quad_verts_merge[4];
816 s, neighbor_quad_vecs, quad_verts_merge, l_shared, neighbor_quad_normal);
820 const float improvement = (neighbor_quad_error - join_error_curr);
855 float join_error_next = join_error_curr + (improvement * multiplier);
859#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
860 if (s.debug_this_step) {
861 printf(
"%f to %f with alignment of %f.\n", join_error_curr, join_error_next, alignment);
896 for (
int i = 0; i <
ARRAY_SIZE(l_quad); i++) {
906 float quad_vecs[4][3];
913 for (
int i = 0; i < neighbor_info.
items_num; i++) {
914#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
915 s.debug_this_step = (s.debug_merge_limit > 0 && s.debug_merge_count == s.debug_merge_limit &&
916 i + 1 == s.debug_neighbor) ||
917 (++s.debug_neighbor_global_count == s.debug_neighbor &&
918 s.debug_merge_limit == 0);
933#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
954#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
957 if (++s.debug_merge_count > s.debug_merge_limit && s.debug_merge_limit != -1) {
1000#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
1004 s.debug_merge_count = 0;
1005 s.debug_neighbor_global_count = 0;
1032 const BMVert *e_verts[4];
1035 e_verts[0]->co, e_verts[1]->co, e_verts[2]->co, e_verts[3]->co);
1064 f_verts[0]->co, f_verts[1]->co, f_verts[2]->co, f_verts[3]->co);
1091#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
1097#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
1100 if (s.debug_merge_limit != -1 && s.debug_merge_count == s.debug_merge_limit) {
1122#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
1125 if (s.debug_merge_limit != -1 && s.debug_merge_count >= s.debug_merge_limit) {
1131#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
1133 if (!(s.debug_merge_limit != -1 && s.debug_merge_count >= s.debug_merge_limit))
CustomData interface, see also DNA_customdata_types.h.
A min-heap / priority queue ADT.
Read Blender memory allocation and freeing.
#define BM_elem_index_get(ele)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
#define BMO_face_flag_enable(bm, e, oflag)
#define BMO_ITER(ele, iter, slot_args, slot_name, restrict_flag)
#define BMO_face_flag_disable(bm, e, oflag)
#define BMO_face_flag_test(bm, e, oflag)
#define ASSERT_VALID_ERROR_METRIC(val)
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
IMETHOD Vector diff(const Vector &a, const Vector &b, double dt)
MINLINE float min_ff(float a, float b)
static BMFace * bm_faces_join_pair_by_edge(BMesh *bm, BMEdge *e)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
float angle_normalized_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
int BMO_slot_int_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
void rotate_normalized_v3_v3v3fl(float out[3], const float p[3], const float axis[3], float angle)
void BM_face_as_array_loop_quad(BMFace *f, BMLoop *r_loops[4])
int CustomData_number_of_layers(const CustomData *data, eCustomDataType type)
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
void BM_face_as_array_vert_quad(BMFace *f, BMVert *r_verts[4])
ATTR_WARN_UNUSED_RESULT const BMLoop * l
float BMO_slot_float_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
void bmo_join_triangles_exec(BMesh *bm, BMOperator *op)
int CustomData_get_n_offset(const CustomData *data, eCustomDataType type, int n)
static void rotate_to_plane(const JoinEdgesState &s, const BMVert *quad_verts[4], const BMLoop *l_shared, const float plane_normal[3], float r_quad_coordinates[4][3])
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
int CustomData_sizeof(eCustomDataType type)
ATTR_WARN_UNUSED_RESULT const BMVert * v
static bool bm_edge_is_contiguous_loop_cd_all(const BMEdge *e, const DelimitData_CD *delimit_data)
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static void add_neighbors(JoinEdgesNeighborInfo &neighbor_info, BMLoop *l_in_quad)
static float quad_calc_error(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
float angle_signed_on_axis_v3v3_v3(const float v1[3], const float v2[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT
static bool bm_edge_is_delimit(const BMEdge *e, const DelimitData *delimit_data)
static bool bm_edge_delimit_cdata(CustomData *ldata, eCustomDataType type, DelimitData_CD *r_delim_cd)
static float compute_alignment(const JoinEdgesState &s, const float quad_a_vecs[4][3], const BMVert *quad_b_verts[4], const BMLoop *l_shared, const float plane_normal[3])
static void reprioritize_face_neighbors(JoinEdgesState &s, BMFace *f, float f_error)
float normal_quad_v3(float n[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
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()
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)
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
static void bm_edge_to_quad_verts(const BMEdge *e, const BMVert *r_v_quad[4])
static void reprioritize_join(JoinEdgesState &s, BMEdge *e_merge, BMLoop *l_shared, float neighbor_quad_vecs[4][3], const float neighbor_quad_error, const float neighbor_quad_normal[3])
BMFace * BM_face_exists(BMVert *const *varr, int len)
MINLINE float normalize_v3(float n[3])
constexpr float maximum_improvement
MINLINE void add_v3_v3(float r[3], const float a[3])
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
MINLINE void sub_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
static void add_without_duplicates(JoinEdgesNeighborInfo &neighbor_info, BMEdge *e, BMLoop *l)
void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value) ATTR_NONNULL(1
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE float max_ff(float a, float b)
float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Heap * BLI_heap_new() ATTR_WARN_UNUSED_RESULT
BMFace * BM_faces_join_pair(BMesh *bm, BMLoop *l_a, BMLoop *l_b, const bool do_del, BMFace **r_double)
Faces Join Pair.
int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
static DelimitData bm_edge_delmimit_data_from_op(BMesh *bm, BMOperator *op)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
bool BM_edge_is_contiguous_loop_cd(const BMEdge *e, const int cd_loop_type, const int cd_loop_offset)
void void float BLI_heap_node_value(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
struct BMLoop * radial_next
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]
JoinEdgesNeighborItem items[8]
HeapNode ** edge_queue_nodes
struct BMLoop * radial_next