Blender  V3.3
Classes | Macros | Typedefs | Enumerations | Functions
bmesh_decimate_collapse.c File Reference
#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...
 

Detailed Description

BMesh decimator that uses an edge collapse method.

Definition in file bmesh_decimate_collapse.c.

Macro Definition Documentation

◆ BOUNDARY_PRESERVE_WEIGHT

#define BOUNDARY_PRESERVE_WEIGHT   100.0f

Definition at line 48 of file bmesh_decimate_collapse.c.

◆ CAN_LOOP_MERGE

#define CAN_LOOP_MERGE (   l)
Value:
(BM_loop_is_manifold(l) && ((l)->v != (l)->radial_next->v) && \
(l_a_index == BM_elem_index_get(l)) && (l_a_index == BM_elem_index_get((l)->radial_next)))
#define BM_elem_index_get(ele)
Definition: bmesh_inline.h:110
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert * v

◆ COST_INVALID

#define COST_INVALID   FLT_MAX

Definition at line 54 of file bmesh_decimate_collapse.c.

◆ OPTIMIZE_EPS

#define OPTIMIZE_EPS   1e-8

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.

◆ TOPOLOGY_FALLBACK_EPS

#define TOPOLOGY_FALLBACK_EPS   1e-12f

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.

◆ USE_CUSTOMDATA

#define USE_CUSTOMDATA

Definition at line 36 of file bmesh_decimate_collapse.c.

◆ USE_SYMMETRY

#define USE_SYMMETRY

Definition at line 30 of file bmesh_decimate_collapse.c.

◆ USE_TOPOLOGY_FALLBACK

#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.

◆ USE_TRIANGULATE

#define USE_TRIANGULATE

Definition at line 37 of file bmesh_decimate_collapse.c.

◆ USE_VERT_NORMAL_INTERP

#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 Documentation

◆ CD_UseFlag

typedef enum CD_UseFlag CD_UseFlag

Enumeration Type Documentation

◆ 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.

Function Documentation

◆ bm_decim_build_edge_cost()

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

◆ bm_decim_build_edge_cost_single()

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

◆ bm_decim_build_edge_cost_single__topology()

static float bm_decim_build_edge_cost_single__topology ( BMEdge e)
static

◆ bm_decim_build_edge_cost_single_squared__topology()

static float bm_decim_build_edge_cost_single_squared__topology ( BMEdge e)
static

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().

◆ bm_decim_build_quadrics()

static void bm_decim_build_quadrics ( BMesh bm,
Quadric vquadrics 
)
static

◆ bm_decim_calc_target_co_db()

static void bm_decim_calc_target_co_db ( BMEdge e,
double  optimize_co[3],
const Quadric vquadrics 
)
static

◆ bm_decim_calc_target_co_fl()

static void bm_decim_calc_target_co_fl ( BMEdge e,
float  optimize_co[3],
const Quadric vquadrics 
)
static

◆ bm_decim_edge_collapse()

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

◆ bm_decim_invalid_edge_cost_single()

static void bm_decim_invalid_edge_cost_single ( BMEdge e,
Heap eheap,
HeapNode **  eheap_table 
)
static

◆ bm_decim_triangulate_begin()

static bool bm_decim_triangulate_begin ( BMesh bm,
int *  r_edges_tri_tot 
)
static

◆ bm_decim_triangulate_end()

static void bm_decim_triangulate_end ( BMesh bm,
const int  edges_tri_tot 
)
static

◆ bm_edge_collapse()

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

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!

Parameters
r_e_clear_otherLet caller know what edges we remove besides e_clear
customdata_flagMerge 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().

◆ bm_edge_collapse_is_degenerate_flip()

static bool bm_edge_collapse_is_degenerate_flip ( BMEdge e,
const float  optimize_co[3] 
)
static

◆ bm_edge_collapse_is_degenerate_topology()

static bool bm_edge_collapse_is_degenerate_topology ( BMEdge e_first)
static

◆ bm_edge_collapse_loop_customdata()

static void bm_edge_collapse_loop_customdata ( BMesh bm,
BMLoop l,
BMVert v_clear,
BMVert v_other,
const float  customdata_fac 
)
static

◆ bm_edge_is_manifold_or_boundary()

BLI_INLINE int bm_edge_is_manifold_or_boundary ( BMLoop l)

◆ bm_edge_symmetry_check_cb()

static bool bm_edge_symmetry_check_cb ( void user_data,
int  index,
const float   UNUSEDco[3],
float   UNUSEDdist_sq 
)
static

◆ bm_edge_symmetry_map()

static int* bm_edge_symmetry_map ( BMesh bm,
uint  symmetry_axis,
float  limit 
)
static

◆ bm_edge_tag_disable()

static void bm_edge_tag_disable ( BMEdge e)
static

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().

◆ bm_edge_tag_enable()

static void bm_edge_tag_enable ( BMEdge e)
static

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().

◆ bm_edge_tag_test()

static bool bm_edge_tag_test ( BMEdge e)
static

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().

◆ bm_face_triangulate()

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

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.

Returns
true if any faces were triangulated.

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().

◆ BM_mesh_decimate_collapse()

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.

Parameters
bmThe mesh
factorface count multiplier [0 - 1]
vweightsOptional array of vertex aligned weights [0 - 1], a vertex group is the usual source for this.
symmetry_axisAxis of symmetry, -1 to disable mirror decimate.
symmetry_epsThreshold when matching mirror verts.
Note
The caller is responsible for recalculating face and vertex normals.
  • Vertex normals are maintained while decimating, although they won't necessarily match the final recalculated normals.
  • Face normals are not maintained at all.
Note
  • 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.
  • edges sharing a vertex are ignored, so the pivot vertex isn't moved to one side.

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().