[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [60793] trunk/blender/source/blender/bmesh : split operators/bmo_beautify.c into tools/bmesh_beautify.c
Dalai Felinto
dfelinto at gmail.com
Wed Oct 16 05:24:38 CEST 2013
Revision: 60793
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=60793
Author: dfelinto
Date: 2013-10-16 03:24:38 +0000 (Wed, 16 Oct 2013)
Log Message:
-----------
split operators/bmo_beautify.c into tools/bmesh_beautify.c
This is a proper design if we want to use the beautify routine elsewhere
(e.g., in the triangulate modifier)
Modified Paths:
--------------
trunk/blender/source/blender/bmesh/CMakeLists.txt
trunk/blender/source/blender/bmesh/bmesh_tools.h
trunk/blender/source/blender/bmesh/operators/bmo_beautify.c
Added Paths:
-----------
trunk/blender/source/blender/bmesh/tools/bmesh_beautify.c
trunk/blender/source/blender/bmesh/tools/bmesh_beautify.h
Modified: trunk/blender/source/blender/bmesh/CMakeLists.txt
===================================================================
--- trunk/blender/source/blender/bmesh/CMakeLists.txt 2013-10-16 03:21:55 UTC (rev 60792)
+++ trunk/blender/source/blender/bmesh/CMakeLists.txt 2013-10-16 03:24:38 UTC (rev 60793)
@@ -119,6 +119,8 @@
intern/bmesh_operator_api.h
intern/bmesh_error.h
+ tools/bmesh_beautify.c
+ tools/bmesh_beautify.h
tools/bmesh_bevel.c
tools/bmesh_bevel.h
tools/bmesh_bisect_plane.c
Modified: trunk/blender/source/blender/bmesh/bmesh_tools.h
===================================================================
--- trunk/blender/source/blender/bmesh/bmesh_tools.h 2013-10-16 03:21:55 UTC (rev 60792)
+++ trunk/blender/source/blender/bmesh/bmesh_tools.h 2013-10-16 03:24:38 UTC (rev 60793)
@@ -34,6 +34,7 @@
extern "C" {
#endif
+#include "tools/bmesh_beautify.h"
#include "tools/bmesh_bevel.h"
#include "tools/bmesh_bisect_plane.h"
#include "tools/bmesh_decimate.h"
Modified: trunk/blender/source/blender/bmesh/operators/bmo_beautify.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_beautify.c 2013-10-16 03:21:55 UTC (rev 60792)
+++ trunk/blender/source/blender/bmesh/operators/bmo_beautify.c 2013-10-16 03:24:38 UTC (rev 60793)
@@ -25,426 +25,19 @@
*
* Beautify the mesh by rotating edges between triangles
* to more attractive positions until no more rotations can be made.
- *
- * In principle this is very simple however there is the possibility of
- * going into an eternal loop where edges keep rotating.
- * To avoid this - each edge stores a set of it previous
- * states so as not to rotate back.
- *
- * TODO
- * - Take face normals into account.
*/
#include "BLI_math.h"
-#include "BLI_heap.h"
#include "MEM_guardedalloc.h"
#include "bmesh.h"
+#include "bmesh_tools.h"
#include "intern/bmesh_operators_private.h"
-#include "BLI_strict_flags.h"
-
-// #define DEBUG_TIME
-
-#ifdef DEBUG_TIME
-# include "PIL_time.h"
-# include "PIL_time_utildefines.h"
-#endif
-
-enum {
- VERT_RESTRICT_TAG = (1 << 0),
-};
-
-/* -------------------------------------------------------------------- */
-/* GSet for edge rotation */
-
-typedef struct EdRotState {
- int v1, v2; /* edge vert, small -> large */
- int f1, f2; /* face vert, small -> large */
-} EdRotState;
-
-static unsigned int erot_gsetutil_hash(const void *ptr)
-{
- const EdRotState *e_state = (const EdRotState *)ptr;
- unsigned int
- hash = BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->v1));
- hash ^= BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->v2));
- hash ^= BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->f1));
- hash ^= BLI_ghashutil_inthash(SET_INT_IN_POINTER(e_state->f2));
- return hash;
-}
-static int erot_gsetutil_cmp(const void *a, const void *b)
-{
- const EdRotState *e_state_a = (const EdRotState *)a;
- const EdRotState *e_state_b = (const EdRotState *)b;
- if (e_state_a->v1 < e_state_b->v1) return -1;
- else if (e_state_a->v1 > e_state_b->v1) return 1;
- else if (e_state_a->v2 < e_state_b->v2) return -1;
- else if (e_state_a->v2 > e_state_b->v2) return 1;
- else if (e_state_a->f1 < e_state_b->f1) return -1;
- else if (e_state_a->f1 > e_state_b->f1) return 1;
- else if (e_state_a->f2 < e_state_b->f2) return -1;
- else if (e_state_a->f2 > e_state_b->f2) return 1;
- else return 0;
-}
-
-static GSet *erot_gset_new(void)
-{
- return BLI_gset_new(erot_gsetutil_hash, erot_gsetutil_cmp, __func__);
-}
-
-/* ensure v0 is smaller */
-#define EDGE_ORD(v0, v1) \
- if (v0 > v1) { \
- v0 ^= v1; \
- v1 ^= v0; \
- v0 ^= v1; \
- } (void)0
-
-static void erot_state_ex(const BMEdge *e, int v_index[2], int f_index[2])
-{
- BLI_assert(BM_edge_is_manifold((BMEdge *)e));
- BLI_assert(BM_vert_in_edge(e, e->l->prev->v) == false);
- BLI_assert(BM_vert_in_edge(e, e->l->radial_next->prev->v) == false);
-
- /* verts of the edge */
- v_index[0] = BM_elem_index_get(e->v1);
- v_index[1] = BM_elem_index_get(e->v2);
- EDGE_ORD(v_index[0], v_index[1]);
-
- /* verts of each of the 2 faces attached to this edge
- * (that are not apart of this edge) */
- f_index[0] = BM_elem_index_get(e->l->prev->v);
- f_index[1] = BM_elem_index_get(e->l->radial_next->prev->v);
- EDGE_ORD(f_index[0], f_index[1]);
-}
-
-static void erot_state_current(const BMEdge *e, EdRotState *e_state)
-{
- erot_state_ex(e, &e_state->v1, &e_state->f1);
-}
-
-static void erot_state_alternate(const BMEdge *e, EdRotState *e_state)
-{
- erot_state_ex(e, &e_state->f1, &e_state->v1);
-}
-
-/* -------------------------------------------------------------------- */
-/* Calculate the improvement of rotating the edge */
-
-/**
- * \return a negative value means the edge can be rotated.
- */
-static float bm_edge_calc_rotate_beauty__area(
- const float v1[3], const float v2[3], const float v3[3], const float v4[3])
-{
- /* not a loop (only to be able to break out) */
- do {
- float v1_xy[2], v2_xy[2], v3_xy[2], v4_xy[2];
-
- /* first get the 2d values */
- {
- bool is_zero_a, is_zero_b;
- float no[3];
- float axis_mat[3][3];
-
- // printf("%p %p %p %p - %p %p\n", v1, v2, v3, v4, e->l->f, e->l->radial_next->f);
- BLI_assert((ELEM3(v1, v2, v3, v4) == false) &&
- (ELEM3(v2, v1, v3, v4) == false) &&
- (ELEM3(v3, v1, v2, v4) == false) &&
- (ELEM3(v4, v1, v2, v3) == false));
-
- is_zero_a = area_tri_v3(v2, v3, v4) <= FLT_EPSILON;
- is_zero_b = area_tri_v3(v2, v4, v1) <= FLT_EPSILON;
-
- if (LIKELY(is_zero_a == false && is_zero_b == false)) {
- float no_a[3], no_b[3];
- normal_tri_v3(no_a, v2, v3, v4); /* a */
- normal_tri_v3(no_b, v2, v4, v1); /* b */
- add_v3_v3v3(no, no_a, no_b);
- if (UNLIKELY(normalize_v3(no) <= FLT_EPSILON)) {
- break;
- }
- }
- else if (is_zero_a == false) {
- normal_tri_v3(no, v2, v3, v4); /* a */
- }
- else if (is_zero_b == false) {
- normal_tri_v3(no, v2, v4, v1); /* b */
- }
- else {
- /* both zero area, no useful normal can be calculated */
- break;
- }
-
- // { float a = angle_normalized_v3v3(no_a, no_b); printf("~ %.7f\n", a); fflush(stdout);}
-
- axis_dominant_v3_to_m3(axis_mat, no);
- mul_v2_m3v3(v1_xy, axis_mat, v1);
- mul_v2_m3v3(v2_xy, axis_mat, v2);
- mul_v2_m3v3(v3_xy, axis_mat, v3);
- mul_v2_m3v3(v4_xy, axis_mat, v4);
- }
-
- // printf("%p %p %p %p - %p %p\n", v1, v2, v3, v4, e->l->f, e->l->radial_next->f);
-
- if (is_quad_convex_v2(v1_xy, v2_xy, v3_xy, v4_xy)) {
- /* testing rule: the area divided by the perimeter,
- * check if (1-3) beats the existing (2-4) edge rotation */
- float area_a, area_b;
- float prim_a, prim_b;
- float fac_24, fac_13;
-
- float len_12, len_23, len_34, len_41, len_24, len_13;
-
- /* edges around the quad */
- len_12 = len_v2v2(v1_xy, v2_xy);
- len_23 = len_v2v2(v2_xy, v3_xy);
- len_34 = len_v2v2(v3_xy, v4_xy);
- len_41 = len_v2v2(v4_xy, v1_xy);
- /* edges crossing the quad interior */
- len_13 = len_v2v2(v1_xy, v3_xy);
- len_24 = len_v2v2(v2_xy, v4_xy);
-
- /* edge (2-4), current state */
- area_a = area_tri_v2(v2_xy, v3_xy, v4_xy);
- area_b = area_tri_v2(v2_xy, v4_xy, v1_xy);
- prim_a = len_23 + len_34 + len_24;
- prim_b = len_24 + len_41 + len_12;
- fac_24 = (area_a / prim_a) + (area_b / prim_b);
-
- /* edge (1-3), new state */
- area_a = area_tri_v2(v1_xy, v2_xy, v3_xy);
- area_b = area_tri_v2(v1_xy, v3_xy, v4_xy);
- prim_a = len_12 + len_23 + len_13;
- prim_b = len_34 + len_41 + len_13;
- fac_13 = (area_a / prim_a) + (area_b / prim_b);
-
- /* negative number if (1-3) is an improved state */
- return fac_24 - fac_13;
- }
- } while (false);
-
- return FLT_MAX;
-}
-
-static float bm_edge_calc_rotate_beauty__angle(
- const float v1[3], const float v2[3], const float v3[3], const float v4[3])
-{
- /* not a loop (only to be able to break out) */
- do {
- float no_a[3], no_b[3];
- float angle_24, angle_13;
-
- /* edge (2-4), current state */
- normal_tri_v3(no_a, v2, v3, v4);
- normal_tri_v3(no_b, v2, v4, v1);
- angle_24 = angle_normalized_v3v3(no_a, no_b);
-
- /* edge (1-3), new state */
- /* only check new state for degenerate outcome */
- if ((normal_tri_v3(no_a, v1, v2, v3) == 0.0f) ||
- (normal_tri_v3(no_b, v1, v3, v4) == 0.0f))
- {
- break;
- }
- angle_13 = angle_normalized_v3v3(no_a, no_b);
-
- return angle_13 - angle_24;
- } while (false);
-
- return FLT_MAX;
-}
-
-static float bm_edge_calc_rotate_beauty(const BMEdge *e, const short flag, const short method)
-{
- /* not a loop (only to be able to break out) */
- do {
- const float *v1, *v2, *v3, *v4;
-
- v1 = e->l->prev->v->co; /* first face co */
- v2 = e->l->v->co; /* e->v1 or e->v2*/
- v3 = e->l->radial_next->prev->v->co; /* second face co */
- v4 = e->l->next->v->co; /* e->v1 or e->v2*/
-
- if (flag & VERT_RESTRICT_TAG) {
- BMVert *v_a = e->l->prev->v, *v_b = e->l->radial_next->prev->v;
- if (BM_elem_flag_test(v_a, BM_ELEM_TAG) == BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
- break;
- }
- }
-
- if (UNLIKELY(v1 == v3)) {
- // printf("This should never happen, but does sometimes!\n");
- break;
- }
-
- switch (method) {
- case 0:
- return bm_edge_calc_rotate_beauty__area(v1, v2, v3, v4);
- default:
- return bm_edge_calc_rotate_beauty__angle(v1, v2, v3, v4);
- }
- } while (false);
-
- return FLT_MAX;
-}
-
-/* -------------------------------------------------------------------- */
-/* Update the edge cost of rotation in the heap */
-
-/* recalc an edge in the heap (surrounding geometry has changed) */
-static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GSet **edge_state_arr,
- const short flag, const short method)
-{
- if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
- const int i = BM_elem_index_get(e);
- GSet *e_state_set = edge_state_arr[i];
-
- if (eheap_table[i]) {
- BLI_heap_remove(eheap, eheap_table[i]);
- eheap_table[i] = NULL;
- }
-
- /* check if we can add it back */
- BLI_assert(BM_edge_is_manifold(e) == true);
- //BLI_assert(BMO_elem_flag_test(bm, e->l->f, FACE_MARK) &&
- // BMO_elem_flag_test(bm, e->l->radial_next->f, FACE_MARK));
-
- /* check we're not moving back into a state we have been in before */
- if (e_state_set != NULL) {
- EdRotState e_state_alt;
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list