Modifiers: add minimum number of vertices to triangulate modifier.
[blender.git] / source / blender / bmesh / tools / bmesh_triangulate.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file
18  * \ingroup bmesh
19  *
20  * Triangulate.
21  */
22
23 #include "DNA_modifier_types.h"  /* for MOD_TRIANGULATE_NGON_BEAUTY only */
24
25 #include "MEM_guardedalloc.h"
26
27 #include "BLI_utildefines.h"
28 #include "BLI_alloca.h"
29 #include "BLI_memarena.h"
30 #include "BLI_heap.h"
31 #include "BLI_linklist.h"
32
33 /* only for defines */
34 #include "BLI_polyfill_2d.h"
35 #include "BLI_polyfill_2d_beautify.h"
36
37 #include "bmesh.h"
38
39 #include "bmesh_triangulate.h"  /* own include */
40
41 /**
42  * a version of #BM_face_triangulate that maps to #BMOpSlot
43  */
44 static void bm_face_triangulate_mapping(
45         BMesh *bm, BMFace *face,
46         const int quad_method, const int ngon_method,
47         const bool use_tag,
48         BMOperator *op, BMOpSlot *slot_facemap_out, BMOpSlot *slot_facemap_double_out,
49
50         MemArena *pf_arena,
51         /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */
52         struct Heap *pf_heap)
53 {
54         int faces_array_tot = face->len - 3;
55         BMFace  **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
56         LinkNode *faces_double = NULL;
57         BLI_assert(face->len > 3);
58
59         BM_face_triangulate(
60                 bm, face,
61                 faces_array, &faces_array_tot,
62                 NULL, NULL,
63                 &faces_double,
64                 quad_method, ngon_method, use_tag,
65                 pf_arena,
66                 pf_heap);
67
68         if (faces_array_tot) {
69                 int i;
70                 BMO_slot_map_elem_insert(op, slot_facemap_out, face, face);
71                 for (i = 0; i < faces_array_tot; i++) {
72                         BMO_slot_map_elem_insert(op, slot_facemap_out, faces_array[i], face);
73                 }
74
75                 while (faces_double) {
76                         LinkNode *next = faces_double->next;
77                         BMO_slot_map_elem_insert(op, slot_facemap_double_out, faces_double->link, face);
78                         MEM_freeN(faces_double);
79                         faces_double = next;
80                 }
81         }
82 }
83
84
85 void BM_mesh_triangulate(
86         BMesh *bm, const int quad_method, const int ngon_method, const int min_vertices,
87         const bool tag_only, BMOperator *op, BMOpSlot *slot_facemap_out,
88         BMOpSlot *slot_facemap_double_out)
89 {
90         BMIter iter;
91         BMFace *face;
92         MemArena *pf_arena;
93         Heap *pf_heap;
94
95         pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
96
97         if (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY) {
98                 pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE);
99         }
100         else {
101                 pf_heap = NULL;
102         }
103
104         if (slot_facemap_out) {
105                 /* same as below but call: bm_face_triangulate_mapping() */
106                 BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
107                         if (face->len >= min_vertices) {
108                                 if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
109                                         bm_face_triangulate_mapping(
110                                                 bm, face,
111                                                 quad_method, ngon_method, tag_only,
112                                                 op, slot_facemap_out, slot_facemap_double_out,
113                                                 pf_arena, pf_heap);
114                                 }
115                         }
116                 }
117         }
118         else {
119                 LinkNode *faces_double = NULL;
120
121                 BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
122                         if (face->len >= min_vertices) {
123                                 if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
124                                         BM_face_triangulate(
125                                                 bm, face,
126                                                 NULL, NULL,
127                                                 NULL, NULL,
128                                                 &faces_double,
129                                                 quad_method, ngon_method, tag_only,
130                                                 pf_arena, pf_heap);
131                                 }
132                         }
133                 }
134
135                 while (faces_double) {
136                         LinkNode *next = faces_double->next;
137                         BM_face_kill(bm, faces_double->link);
138                         MEM_freeN(faces_double);
139                         faces_double = next;
140                 }
141         }
142
143         BLI_memarena_free(pf_arena);
144
145         if (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY) {
146                 BLI_heap_free(pf_heap, NULL);
147         }
148 }