Blender
V3.3
|
#include <stddef.h>
#include "MEM_guardedalloc.h"
#include "BLI_alloca.h"
#include "BLI_heap.h"
#include "BLI_linklist.h"
#include "BLI_math.h"
#include "BLI_memarena.h"
#include "BLI_polyfill_2d.h"
#include "BLI_polyfill_2d_beautify.h"
#include "BLI_quadric.h"
#include "BLI_utildefines_stack.h"
#include "BKE_customdata.h"
#include "bmesh.h"
#include "bmesh_decimate.h"
#include "../intern/bmesh_structure.h"
#include "BLI_kdtree.h"
Go to the source code of this file.
Classes | |
struct | KD_Symmetry_Data |
Macros | |
#define | USE_SYMMETRY |
#define | USE_CUSTOMDATA |
#define | USE_TRIANGULATE |
#define | USE_VERT_NORMAL_INTERP |
#define | USE_TOPOLOGY_FALLBACK |
#define | TOPOLOGY_FALLBACK_EPS 1e-12f |
#define | BOUNDARY_PRESERVE_WEIGHT 100.0f |
#define | OPTIMIZE_EPS 1e-8 |
#define | COST_INVALID FLT_MAX |
#define | CAN_LOOP_MERGE(l) |
Typedefs | |
typedef enum CD_UseFlag | CD_UseFlag |
Enumerations | |
enum | CD_UseFlag { CD_DO_VERT = (1 << 0) , CD_DO_EDGE = (1 << 1) , CD_DO_LOOP = (1 << 2) } |
Functions | |
static void | bm_decim_build_quadrics (BMesh *bm, Quadric *vquadrics) |
static void | bm_decim_calc_target_co_db (BMEdge *e, double optimize_co[3], const Quadric *vquadrics) |
static void | bm_decim_calc_target_co_fl (BMEdge *e, float optimize_co[3], const Quadric *vquadrics) |
static bool | bm_edge_collapse_is_degenerate_flip (BMEdge *e, const float optimize_co[3]) |
static float | bm_decim_build_edge_cost_single_squared__topology (BMEdge *e) |
static float | bm_decim_build_edge_cost_single__topology (BMEdge *e) |
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) |
static void | bm_decim_invalid_edge_cost_single (BMEdge *e, Heap *eheap, HeapNode **eheap_table) |
static void | bm_decim_build_edge_cost (BMesh *bm, const Quadric *vquadrics, const float *vweights, const float vweight_factor, Heap *eheap, HeapNode **eheap_table) |
static bool | bm_edge_symmetry_check_cb (void *user_data, int index, const float UNUSED(co[3]), float UNUSED(dist_sq)) |
static int * | bm_edge_symmetry_map (BMesh *bm, uint symmetry_axis, float limit) |
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) |
static bool | bm_decim_triangulate_begin (BMesh *bm, int *r_edges_tri_tot) |
static void | bm_decim_triangulate_end (BMesh *bm, const int edges_tri_tot) |
static void | bm_edge_collapse_loop_customdata (BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other, const float customdata_fac) |
static void | bm_edge_tag_enable (BMEdge *e) |
static void | bm_edge_tag_disable (BMEdge *e) |
static bool | bm_edge_tag_test (BMEdge *e) |
BLI_INLINE int | bm_edge_is_manifold_or_boundary (BMLoop *l) |
static bool | bm_edge_collapse_is_degenerate_topology (BMEdge *e_first) |
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) |
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_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. More... | |
BMesh decimator that uses an edge collapse method.
Definition in file bmesh_decimate_collapse.c.
#define BOUNDARY_PRESERVE_WEIGHT 100.0f |
Definition at line 48 of file bmesh_decimate_collapse.c.
#define COST_INVALID FLT_MAX |
Definition at line 54 of file bmesh_decimate_collapse.c.
Uses double precision, impacts behavior on near-flat surfaces, cane give issues with very small faces. 1e-2 is too big, see: T48154.
Definition at line 53 of file bmesh_decimate_collapse.c.
cost is calculated with double precision, it's ok to use a very small epsilon, see T48154.
Definition at line 45 of file bmesh_decimate_collapse.c.
#define USE_CUSTOMDATA |
Definition at line 36 of file bmesh_decimate_collapse.c.
#define USE_SYMMETRY |
Definition at line 30 of file bmesh_decimate_collapse.c.
#define USE_TOPOLOGY_FALLBACK |
if the cost from BLI_quadric_evaluate is 'noise', fallback to topology
Definition at line 42 of file bmesh_decimate_collapse.c.
#define USE_TRIANGULATE |
Definition at line 37 of file bmesh_decimate_collapse.c.
#define USE_VERT_NORMAL_INTERP |
Has the advantage that flipped faces don't mess up vertex normals.
Definition at line 39 of file bmesh_decimate_collapse.c.
typedef enum CD_UseFlag CD_UseFlag |
enum CD_UseFlag |
Enumerator | |
---|---|
CD_DO_VERT | |
CD_DO_EDGE | |
CD_DO_LOOP |
Definition at line 56 of file bmesh_decimate_collapse.c.
|
static |
Definition at line 329 of file bmesh_decimate_collapse.c.
References bm, bm_decim_build_edge_cost_single(), BM_EDGES_OF_MESH, BM_ITER_MESH_INDEX, e, and NULL.
Referenced by BM_mesh_decimate_collapse().
|
static |
Definition at line 225 of file bmesh_decimate_collapse.c.
References BLI_assert, BLI_heap_insert_or_update(), BLI_heap_remove(), BLI_quadric_evaluate(), bm_decim_build_edge_cost_single__topology(), bm_decim_build_edge_cost_single_squared__topology(), bm_decim_calc_target_co_db(), BM_edge_calc_length(), BM_edge_is_boundary(), BM_edge_is_manifold(), BM_elem_index_get, clear(), e, fabsf, NULL, q1, TOPOLOGY_FALLBACK_EPS, and UNLIKELY.
Referenced by bm_decim_build_edge_cost(), and bm_decim_edge_collapse().
Definition at line 217 of file bmesh_decimate_collapse.c.
References BMVert::co, dot_v3v3(), e, fabsf, len_v3v3(), min_ff(), and BMVert::no.
Referenced by bm_decim_build_edge_cost_single().
when the cost is so small that its not useful (flat surfaces), fallback to using a 'topology' cost.
This avoids cases where a flat (or near flat) areas get very un-even geometry.
Definition at line 212 of file bmesh_decimate_collapse.c.
References BMVert::co, dot_v3v3(), e, fabsf, len_squared_v3v3(), min_ff(), and BMVert::no.
Referenced by bm_decim_build_edge_cost_single().
vquadrics | must be calloc'd |
Definition at line 68 of file bmesh_decimate_collapse.c.
References BLI_quadric_add_qu_qu(), BLI_quadric_from_plane(), BLI_quadric_mul(), bm, BM_edge_is_boundary(), BM_EDGES_OF_MESH, BM_elem_index_get, BM_face_calc_center_median(), BM_FACE_FIRST_LOOP, BM_FACES_OF_MESH, BM_ITER_MESH, BOUNDARY_PRESERVE_WEIGHT, center, BMVert::co, copy_v3db_v3fl(), cross_v3_v3v3(), dot_v3db_v3fl(), e, mid_v3_v3v3(), BMLoop::next, BMFace::no, normalize_v3_db(), sub_v3_v3v3(), UNLIKELY, and BMLoop::v.
Referenced by BM_mesh_decimate_collapse().
|
static |
Definition at line 123 of file bmesh_decimate_collapse.c.
References BLI_quadric_add_qu_ququ(), BLI_quadric_optimize(), BM_elem_index_get, BMVert::co, double(), e, and OPTIMIZE_EPS.
Referenced by bm_decim_build_edge_cost_single(), and bm_decim_calc_target_co_fl().
|
static |
Definition at line 143 of file bmesh_decimate_collapse.c.
References bm_decim_calc_target_co_db(), copy_v3fl_v3db(), and e.
Referenced by bm_decim_edge_collapse(), and BM_mesh_decimate_collapse().
|
static |
Collapse e the edge, removing e->v2
Definition at line 1108 of file bmesh_decimate_collapse.c.
References BLI_assert, BLI_heap_remove(), BLI_quadric_add_qu_qu(), bm, bm_decim_build_edge_cost_single(), bm_decim_calc_target_co_fl(), bm_decim_invalid_edge_cost_single(), bm_edge_collapse(), bm_edge_collapse_is_degenerate_flip(), bm_edge_collapse_is_degenerate_topology(), BM_edge_find_double(), BM_elem_index_get, BM_ITER_ELEM, BM_LOOPS_OF_VERT, BM_vert_in_edge(), BM_vert_normal_update(), bmesh_disk_edge_next(), CLAMP, BMVert::co, compare_v3v3(), copy_v3_v3(), BMVert::e, BMLoop::e, e, BMLoop::f, interp_v3_v3v3(), interpf(), l, BMFace::len, LIKELY, line_point_factor_v3(), BMLoop::next, BMVert::no, normalize_v3(), NULL, BMLoop::prev, UNLIKELY, USE_SYMMETRY, and BMLoop::v.
Referenced by BM_mesh_decimate_collapse().
|
static |
Definition at line 323 of file bmesh_decimate_collapse.c.
References BLI_assert, BLI_heap_insert(), BM_elem_index_get, COST_INVALID, e, and NULL.
Referenced by bm_decim_edge_collapse(), and BM_mesh_decimate_collapse().
Definition at line 516 of file bmesh_decimate_collapse.c.
References BLI_assert, BLI_heap_free(), BLI_heap_new_ex(), BLI_memarena_free(), BLI_memarena_new(), BLI_POLYFILL_ALLOC_NGON_RESERVE, BLI_POLYFILL_ARENA_SIZE, bm, BM_EDGE, BM_elem_index_set, BM_FACE, BM_FACE_FIRST_LOOP, BM_face_kill(), bm_face_triangulate(), BM_FACES_OF_MESH, BM_ITER_MESH, BM_LOOP, BM_mesh_elem_index_ensure(), BM_VERT, BMesh::elem_index_dirty, BMFace::len, LinkNode::link, MEM_freeN, LinkNode::next, BMLoop::next, next, and NULL.
Referenced by BM_mesh_decimate_collapse().
Definition at line 593 of file bmesh_decimate_collapse.c.
References BLI_assert, bm, BM_edge_kill(), BM_edge_loop_pair(), BM_EDGES_OF_MESH, BM_elem_index_get, BM_faces_join(), BM_ITER_MESH, BM_vert_in_edge(), CAN_LOOP_MERGE, e, ELEM, BMLoop::f, is_quad_convex_v3(), l_b, BMFace::len, MEM_freeN, MEM_mallocN, MIN2, BMLoop::next, NULL, BMLoop::prev, STACK_DECLARE, STACK_INIT, STACK_PUSH, STACK_SIZE, BMesh::totedge, and BMLoop::v.
Referenced by BM_mesh_decimate_collapse().
|
static |
Special, highly limited edge collapse function intended for speed over flexibility. can only collapse edges connected to (1, 2) triangles.
Important - don't add vert/edge/face data on collapsing!
r_e_clear_other | Let caller know what edges we remove besides e_clear |
customdata_flag | Merge factor, scales from 0 - 1 ('v_clear' -> 'v_other') |
Definition at line 931 of file bmesh_decimate_collapse.c.
References BLI_assert, bm, BM_data_interp_from_edges(), BM_data_interp_from_verts(), bm_edge_collapse_loop_customdata(), BM_edge_is_boundary(), BM_edge_is_manifold(), BM_edge_kill(), BM_edge_loop_pair(), BM_edge_other_vert(), BM_edge_share_vert(), BM_edge_splice(), BM_elem_index_get, BM_vert_in_edge(), BM_vert_splice(), CD_DO_EDGE, CD_DO_LOOP, CD_DO_VERT, BMLoop::e, ELEM, BMLoop::f, BMVert::head, BMEdge::head, BMHeader::hflag, BMEdge::l, l_b, BMFace::len, BMLoop::next, NULL, BMLoop::prev, BMLoop::radial_next, and UNUSED_VARS_NDEBUG.
Referenced by bm_decim_edge_collapse().
Definition at line 150 of file bmesh_decimate_collapse.c.
References BM_ITER_ELEM, BM_LOOPS_OF_VERT, BMVert::co, cross_v3_v3v3(), dot_v3v3(), BMLoop::e, e, l, len_squared_v3(), BMLoop::next, normal_tri_v3(), BMLoop::prev, sub_v3_v3v3(), BMLoop::v, and v.
Referenced by bm_decim_edge_collapse(), and BM_mesh_decimate_collapse().
Definition at line 839 of file bmesh_decimate_collapse.c.
References BLI_assert, bm_edge_is_manifold_or_boundary(), bm_edge_tag_disable(), bm_edge_tag_enable(), bm_edge_tag_test(), BM_elem_flag_disable, BM_ELEM_TAG, BM_ITER_ELEM, BM_LOOPS_OF_EDGE, BM_VERTS_OF_FACE, bmesh_disk_edge_next(), BMLoop::f, BMEdge::l, l, BMFace::len, BMLoop::next, BMLoop::radial_next, v, BMEdge::v1, and BMEdge::v2.
Referenced by bm_decim_edge_collapse(), and BM_mesh_decimate_collapse().
|
static |
l | defines the vert to collapse into. |
Definition at line 674 of file bmesh_decimate_collapse.c.
References ARRAY_SIZE, BLI_assert, bm, BM_edge_is_manifold(), BM_vert_step_fan_loop(), CustomData_bmesh_interp_n(), CustomData_data_equals(), CustomData_layer_has_math(), BMHeader::data, BMLoop::e, BMLoop::f, BMLoop::head, l, CustomData::layers, BMesh::ldata, BMLoop::next, NULL, offset, CustomDataLayer::offset, POINTER_OFFSET, BMLoop::radial_next, src, CustomData::totlayer, type, CustomDataLayer::type, UNLIKELY, BMLoop::v, void, and w().
Referenced by bm_edge_collapse().
BLI_INLINE int bm_edge_is_manifold_or_boundary | ( | BMLoop * | l | ) |
Definition at line 828 of file bmesh_decimate_collapse.c.
References BM_edge_is_boundary(), BM_edge_is_manifold(), BMLoop::e, l, LIKELY, and BMLoop::radial_next.
Referenced by bm_edge_collapse_is_degenerate_topology().
|
static |
Definition at line 362 of file bmesh_decimate_collapse.c.
References BMVert::co, dot_v3v3(), KD_Symmetry_Data::e_dir, KD_Symmetry_Data::e_found_index, KD_Symmetry_Data::e_v1_co, KD_Symmetry_Data::e_v2_co, KD_Symmetry_Data::etable, len_squared_v3v3(), KD_Symmetry_Data::limit_sq, sub_v3_v3v3(), user_data, BMEdge::v1, and BMEdge::v2.
Referenced by bm_edge_symmetry_map().
Definition at line 391 of file bmesh_decimate_collapse.c.
References bm, bm_edge_symmetry_check_cb(), BM_EDGES_OF_MESH, BM_ITER_MESH_INDEX, BMVert::co, copy_v3_v3(), e, KD_Symmetry_Data::e_dir, KD_Symmetry_Data::e_found_index, KD_Symmetry_Data::e_v1_co, KD_Symmetry_Data::e_v2_co, KD_Symmetry_Data::etable, KD_Symmetry_Data::limit_sq, MEM_freeN, MEM_mallocN, mid_v3_v3v3(), square_f(), sub_v3_v3v3(), BMesh::totedge, and tree.
Referenced by BM_mesh_decimate_collapse().
Definition at line 806 of file bmesh_decimate_collapse.c.
References BM_elem_flag_disable, BM_ELEM_TAG, and e.
Referenced by bm_edge_collapse_is_degenerate_topology().
Check if the collapse will result in a degenerate mesh, that is - duplicate edges or faces.
This situation could be checked for when calculating collapse cost however its quite slow and a degenerate collapse could eventuate after the cost is calculated, so instead, check just before collapsing.
Definition at line 794 of file bmesh_decimate_collapse.c.
References BM_elem_flag_enable, BM_ELEM_TAG, and e.
Referenced by bm_edge_collapse_is_degenerate_topology().
Definition at line 818 of file bmesh_decimate_collapse.c.
References BM_elem_flag_test, BM_ELEM_TAG, and e.
Referenced by bm_edge_collapse_is_degenerate_topology().
|
static |
To keep things simple we can only collapse edges on triangulated data (limitation with edge collapse and error calculation functions).
But to avoid annoying users by only giving triangle results, we can triangulate, keeping a reference between the faces, then join after if the edges don't collapse, this will also allow more choices when collapsing edges so even has some advantage over decimating quads directly.
Definition at line 465 of file bmesh_decimate_collapse.c.
References BLI_array_alloca, bm, BM_elem_index_get, BM_elem_index_set, BM_face_normal_update(), BM_face_triangulate(), BMEdge::l, BMFace::len, and BMLoop::radial_next.
Referenced by bm_decim_triangulate_begin().
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.
bm | The mesh |
factor | face count multiplier [0 - 1] |
vweights | Optional array of vertex aligned weights [0 - 1], a vertex group is the usual source for this. |
symmetry_axis | Axis of symmetry, -1 to disable mirror decimate. |
symmetry_eps | Threshold when matching mirror verts. |
eheap_table[e_index_mirr]
is only removed from the heap at the last moment since its possible (in theory) for collapsing e
to remove e_mirr
.Definition at line 1264 of file bmesh_decimate_collapse.c.
References BLI_assert, BLI_heap_free(), BLI_heap_is_empty(), BLI_heap_new_ex(), BLI_heap_node_ptr(), BLI_heap_pop_min(), BLI_heap_remove(), BLI_heap_top_value(), bm, BM_ALL, bm_decim_build_edge_cost(), bm_decim_build_quadrics(), bm_decim_calc_target_co_fl(), bm_decim_edge_collapse(), bm_decim_invalid_edge_cost_single(), bm_decim_triangulate_begin(), bm_decim_triangulate_end(), bm_edge_collapse_is_degenerate_flip(), bm_edge_collapse_is_degenerate_topology(), BM_edge_share_vert_check(), bm_edge_symmetry_map(), BM_elem_index_get, CD_DO_EDGE, CD_DO_LOOP, CD_DO_VERT, COST_INVALID, CustomData_has_interp(), CustomData_has_math(), e, BMesh::edata, BMesh::elem_index_dirty, invalidate(), BMesh::ldata, LIKELY, MEM_callocN, MEM_freeN, MEM_mallocN, NULL, BMesh::totedge, BMesh::totface, BMesh::totvert, UNLIKELY, UNUSED_VARS, USE_SYMMETRY, BMesh::vdata, and void.
Referenced by edbm_decimate_exec(), and modifyMesh().