034151fa584a505821a6aa919e697f7d13a3e54b
[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 bool tag_only,
87         BMOperator *op, BMOpSlot *slot_facemap_out, BMOpSlot *slot_facemap_double_out)
88 {
89         BMIter iter;
90         BMFace *face;
91         MemArena *pf_arena;
92         Heap *pf_heap;
93
94         pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
95
96         if (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY) {
97                 pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE);
98         }
99         else {
100                 pf_heap = NULL;
101         }
102
103         if (slot_facemap_out) {
104                 /* same as below but call: bm_face_triangulate_mapping() */
105                 BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
106                         if (face->len > 3) {
107                                 if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
108                                         bm_face_triangulate_mapping(
109                                                 bm, face,
110                                                 quad_method, ngon_method, tag_only,
111                                                 op, slot_facemap_out, slot_facemap_double_out,
112                                                 pf_arena, pf_heap);
113                                 }
114                         }
115                 }
116         }
117         else {
118                 LinkNode *faces_double = NULL;
119
120                 BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
121                         if (face->len > 3) {
122                                 if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
123                                         BM_face_triangulate(
124                                                 bm, face,
125                                                 NULL, NULL,
126                                                 NULL, NULL,
127                                                 &faces_double,
128                                                 quad_method, ngon_method, tag_only,
129                                                 pf_arena, pf_heap);
130                                 }
131                         }
132                 }
133
134                 while (faces_double) {
135                         LinkNode *next = faces_double->next;
136                         BM_face_kill(bm, faces_double->link);
137                         MEM_freeN(faces_double);
138                         faces_double = next;
139                 }
140         }
141
142         BLI_memarena_free(pf_arena);
143
144         if (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY) {
145                 BLI_heap_free(pf_heap, NULL);
146         }
147 }