diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-09-06 02:24:12 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-09-06 02:24:12 +0400 |
commit | 7a38fe97fdf6971ed3f52bba08e942bf915112c7 (patch) | |
tree | cd8569ff5a689f2b86aaae3c9b791e26b3deaf4b /source | |
parent | 6cc3aec8bc3cde3a0007fd877e40a744ee44c2e2 (diff) |
sorting utility functions for simple cases - sorting pointers by float for example.
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenlib/BLI_sort_utils.h | 61 | ||||
-rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/sort_utils.c | 74 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_construct.c | 25 | ||||
-rw-r--r-- | source/blender/bmesh/operators/bmo_join_triangles.c | 23 |
5 files changed, 150 insertions, 35 deletions
diff --git a/source/blender/blenlib/BLI_sort_utils.h b/source/blender/blenlib/BLI_sort_utils.h new file mode 100644 index 00000000000..e08f4e5ac83 --- /dev/null +++ b/source/blender/blenlib/BLI_sort_utils.h @@ -0,0 +1,61 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2013 Blender Foundation. + * All rights reserved. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_SORT_UTILS_H__ +#define __BLI_SORT_UTILS_H__ + +/** \file BLI_sort_utils.h + * \ingroup bli + */ + +/** + * \note keep \a sort_value first, + * so cmp functions can be reused. + */ +struct SortPointerByFloat { + float sort_value; + void *data; +}; + +struct SortIntByFloat { + float sort_value; + int data; +}; + +struct SortPointerByInt { + int sort_value; + void *data; +}; + +struct SortIntByInt { + int sort_value; + int data; +}; + +int BLI_sortutil_cmp_float(const void *a_, const void *b_); +int BLI_sortutil_cmp_float_reverse(const void *a_, const void *b_); + +int BLI_sortutil_cmp_int(const void *a_, const void *b_); +int BLI_sortutil_cmp_int_reverse(const void *a_, const void *b_); + +#endif /* __BLI_SORT_UTILS_H__ */ diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index c5e2c0b298b..82f07268521 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -87,6 +87,7 @@ set(SRC intern/scanfill.c intern/smallhash.c intern/sort.c + intern/sort_utils.c intern/stack.c intern/storage.c intern/string.c @@ -150,6 +151,7 @@ set(SRC BLI_scanfill.h BLI_smallhash.h BLI_sort.h + BLI_sort_utils.h BLI_stack.h BLI_strict_flags.h BLI_string.h diff --git a/source/blender/blenlib/intern/sort_utils.c b/source/blender/blenlib/intern/sort_utils.c new file mode 100644 index 00000000000..c75e8e7455f --- /dev/null +++ b/source/blender/blenlib/intern/sort_utils.c @@ -0,0 +1,74 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2013 Blender Foundation. + * All rights reserved. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/sort_utils.c + * \ingroup bli + * + * Utility functions for sorting common types. + */ + +#include "BLI_sort_utils.h" /* own include */ + +struct SortAnyByFloat { + float sort_value; +}; + +struct SortAnyByInt { + int sort_value; +}; + +int BLI_sortutil_cmp_float(const void *a_, const void *b_) +{ + const struct SortAnyByFloat *a = a_; + const struct SortAnyByFloat *b = b_; + if (a->sort_value > b->sort_value) return 1; + else if (a->sort_value < b->sort_value) return -1; + else return 0; +} + +int BLI_sortutil_cmp_float_reverse(const void *a_, const void *b_) +{ + const struct SortAnyByFloat *a = a_; + const struct SortAnyByFloat *b = b_; + if (a->sort_value < b->sort_value) return 1; + else if (a->sort_value > b->sort_value) return -1; + else return 0; +} + +int BLI_sortutil_cmp_int(const void *a_, const void *b_) +{ + const struct SortAnyByInt *a = a_; + const struct SortAnyByInt *b = b_; + if (a->sort_value > b->sort_value) return 1; + else if (a->sort_value < b->sort_value) return -1; + else return 0; +} + +int BLI_sortutil_cmp_int_reverse(const void *a_, const void *b_) +{ + const struct SortAnyByInt *a = a_; + const struct SortAnyByInt *b = b_; + if (a->sort_value < b->sort_value) return 1; + else if (a->sort_value > b->sort_value) return -1; + else return 0; +} diff --git a/source/blender/bmesh/intern/bmesh_construct.c b/source/blender/bmesh/intern/bmesh_construct.c index bee5a7c7d39..60d9b62d6b9 100644 --- a/source/blender/bmesh/intern/bmesh_construct.c +++ b/source/blender/bmesh/intern/bmesh_construct.c @@ -35,6 +35,7 @@ #include "BLI_alloca.h" #include "BLI_math.h" +#include "BLI_sort_utils.h" #include "BKE_customdata.h" @@ -358,20 +359,6 @@ BMFace *BM_face_create_ngon_verts(BMesh *bm, BMVert **vert_arr, const int len, f_example, create_flag); } - -typedef struct AngleIndexPair { - float angle; - int index; -} AngleIndexPair; - -static int angle_index_pair_cmp(const void *e1, const void *e2) -{ - const AngleIndexPair *p1 = e1, *p2 = e2; - if (p1->angle > p2->angle) return 1; - else if (p1->angle < p2->angle) return -1; - else return 0; -} - /** * Makes an NGon from an un-ordered set of verts * @@ -391,7 +378,7 @@ static int angle_index_pair_cmp(const void *e1, const void *e2) BMFace *BM_face_create_ngon_vcloud(BMesh *bm, BMVert **vert_arr, int len, const BMFace *f_example, const eBMCreateFlag create_flag) { - AngleIndexPair *vang = BLI_array_alloca(vang, len); + struct SortIntByFloat *vang = BLI_array_alloca(vang, len); BMVert **vert_arr_map = BLI_array_alloca(vert_arr_map, len); BMFace *f; @@ -488,18 +475,18 @@ BMFace *BM_face_create_ngon_vcloud(BMesh *bm, BMVert **vert_arr, int len, angle = -angle; } - vang[i].angle = angle; - vang[i].index = i; + vang[i].sort_value = angle; + vang[i].data = i; } /* sort by angle and magic! - we have our ngon */ - qsort(vang, len, sizeof(AngleIndexPair), angle_index_pair_cmp); + qsort(vang, len, sizeof(*vang), BLI_sortutil_cmp_float); /* --- */ /* create edges and find the winding (if faces are attached to any existing edges) */ for (i = 0; i < len; i++) { - vert_arr_map[i] = vert_arr[vang[i].index]; + vert_arr_map[i] = vert_arr[vang[i].data]; } f = BM_face_create_ngon_verts(bm, vert_arr_map, len, f_example, create_flag, true, true); diff --git a/source/blender/bmesh/operators/bmo_join_triangles.c b/source/blender/bmesh/operators/bmo_join_triangles.c index 12065743136..6d4f257909c 100644 --- a/source/blender/bmesh/operators/bmo_join_triangles.c +++ b/source/blender/bmesh/operators/bmo_join_triangles.c @@ -34,6 +34,7 @@ #include "DNA_meshdata_types.h" #include "BLI_math.h" +#include "BLI_sort_utils.h" #include "BKE_customdata.h" @@ -181,10 +182,6 @@ static bool bm_edge_faces_cmp(BMesh *bm, BMEdge *e, const bool do_uv, const bool return true; } -typedef struct JoinEdge { - float weight; - BMEdge *e; -} JoinEdge; #define EDGE_MARK 1 #define EDGE_CHOSEN 2 @@ -192,14 +189,7 @@ typedef struct JoinEdge { #define FACE_MARK 1 #define FACE_INPUT 2 -static int fplcmp(const void *v1, const void *v2) -{ - const JoinEdge *e1 = (JoinEdge *)v1, *e2 = (JoinEdge *)v2; - if (e1->weight > e2->weight) return 1; - else if (e1->weight < e2->weight) return -1; - else return 0; -} void bmo_join_triangles_exec(BMesh *bm, BMOperator *op) { @@ -214,7 +204,8 @@ void bmo_join_triangles_exec(BMesh *bm, BMOperator *op) BMOIter siter; BMFace *f; BMEdge *e; - JoinEdge *jedges = NULL; + /* data: edge-to-join, sort_value: error weight */ + struct SortPointerByFloat *jedges; unsigned i, totedge; unsigned int totedge_tag = 0; @@ -271,19 +262,19 @@ void bmo_join_triangles_exec(BMesh *bm, BMOperator *op) measure = measure_facepair(v1->co, v2->co, v3->co, v4->co, limit); if (measure < limit) { - jedges[i].e = e; - jedges[i].weight = measure; + jedges[i].data = e; + jedges[i].sort_value = measure; i++; } } totedge = i; - qsort(jedges, totedge, sizeof(JoinEdge), fplcmp); + qsort(jedges, totedge, sizeof(*jedges), BLI_sortutil_cmp_float); for (i = 0; i < totedge; i++) { BMFace *f_a, *f_b; - e = jedges[i].e; + e = jedges[i].data; f_a = e->l->f; f_b = e->l->radial_next->f; |