destruction of previous slot api. if it returns, it'll
[blender.git] / source / blender / bmesh / operators / subdivideop.c
1 #include "MEM_guardedalloc.h"
2
3 #include "BKE_utildefines.h"
4
5 #include "bmesh.h"
6 #include "BLI_arithb.h"
7
8 #include <stdio.h>
9
10 /*
11 note: this is a pattern-based edge subdivider.
12 it tries to match a pattern to edge selections on faces.
13 it was a fairly easy exercise to test the bmesh api; it
14 doesn't support multicuts, so it won't actually be used.
15
16 the patterns are defined as followed:
17
18 the patterns are defined for the state of the face after
19 initial splitting.  each edge that was split is flagged, as is
20 the new resulting edge.
21
22 subdpattern pattern = {
23         //boolean flags for if an edge should have been split or not
24         {1, 0, 0, 0},
25         //connection values for verts,
26         {2, -1, -1, -1},
27         //second stage split flags, splits newly created edges
28         {0, 0, 0, 0, 1},
29         //second stage connection values for verts, connects stuff again.
30         {-1, -1, -1, -1, 3},
31         4 //len of face before second stage splits, but after initial edge splits
32 };
33
34 */
35 typedef struct subdpattern {
36         int seledges[20]; //selected edges mask, for splitting
37         int connectverts[20]; //verts to connect;
38
39         int secondstage_splitedges[20];
40         //verts to connect afterwards.  size must be len + number 
41         //of edges split in secondstage_splitedges
42         int secondstage_connect[20];
43
44         int len; /*total number of verts*/
45 } subdpattern;
46
47 /*generic subdivision rules:
48   
49   * two selected edges in a face should make a link
50     between them.
51
52   * one edge should do, what? make pretty topology, or just
53     split the edge only?
54 */
55
56 /*note: the patterns are rotated as necassary to
57   match the input geometry.  they're also based on the
58   post-splitted state of the faces.  note that
59   second stage splitted stuff doesn't count
60   for pattern->len!*/
61
62 /*
63      v2
64     /  \
65 v1 s_e1 e2
66   /e0     \
67 v0---e3----v3
68
69 handle case of one edge selected.
70 */
71
72 subdpattern t_1edge = {
73         {1, 1, 0, 0},
74         {-1, 3, -1, -1},
75         {0},
76         {-1, -1, -1, -1, -1, -1, -1, -1, -1},
77         4
78 };
79
80
81 /*
82      v2
83     /  \e2
84 v1 e1   e3 v3
85   /e0     \
86 v0---e4----v4
87
88 handle case of two edges selected.
89 */
90 subdpattern t_2edge = {
91         {1, 1, 1, 1, 0},
92         {-1, 3, -1, -1, -1},
93         {0},
94         {-1, -1, -1, -1, -1, -1, -1, -1, -1},
95         5
96 };
97
98 /*
99      v2
100     /  \e2
101 v1 e1   e3 v3
102   /e0     \
103 v0--e5--e4-v4
104      v5
105
106 handle case of one edge selected.
107 make an edge between v1 and v5,
108 v5 and v3, and v3 and v1
109 */
110 subdpattern t_3edge = {
111         {1, 1, 1, 1, 1, 1},
112         {-1, 5, -1, 1, -1, 3}, //creates e6
113         {0},
114         {-1, -1, -1, -1, -1, -1, -1},
115         6
116 };
117
118 /*
119       e3
120 v4---------v3
121 |          |
122 |e4        | e2
123 |          |
124 |e0   e1   |
125 v0---v1----v2
126
127 connect v1 to v4 and v3
128
129 */
130 subdpattern q_1edge = {
131         {1, 1, 0, 0, 0},
132         {-1, 3, -1, -1, 1},
133         {0},
134         {-1, -1, -1, -1, -1, -1, -1, -1, -1},
135         5
136 };
137
138 /*
139       e4
140 v5---------v4
141 |          |
142 |e5        | e3
143 |          |v3
144 |e0   e1   | e2
145 v0---v1----v2
146
147 connect v1 to v3
148
149 */
150 subdpattern q_2adjedge = {
151         {1, 1, 1, 1, 0, 0},
152         {-1, 3, -1, -1, -1, -1},
153         {0, 0, 0, 0, 0, 0, 1},
154         {-1, -1, -1, -1, -1, 6, -1, -1, -1},
155         6
156 };
157
158
159 /*
160    e4 v4 e3
161 v5---------v3
162 |          |
163 |e5        |
164 |          | e2
165 |  e0   e1 |
166 v0---v1----v2
167
168 connect v1 to v4
169
170 */
171 subdpattern q_2opedge = {
172         {1, 1, 0, 1, 1, 0},
173         {-1, 4, -1, -1, -1, -1},
174         {0},
175         {-1, -1, -1, -1, -1, -1, -1, -1, -1},
176         6
177 };
178
179 /*
180    e5 v5 e4
181 v6---------v4
182 |          | 
183 |e6        | e3
184 |          | v3
185 |  e0   e1 | e2
186 v0---v1----v2
187
188 connect v1 to v5, v1 to v3, and v3 to v5
189
190 */
191 subdpattern q_3edge = {
192         {1, 1, 1, 1, 1, 1, 0},
193         {-1, 3, -1, 5, -1, 1, -1},
194         {0},
195         {-1, -1, -1, -1, -1, -1, -1, -1, -1},
196         7
197 };
198
199 /*
200    e5 v5 e4
201 v6---------v4
202 |          | 
203 |e6        | e3
204 |v7        | v3
205 |e7 e0  e1 | e2
206 v0---v1----v2
207
208 connect v1 to v5, split edge, than connect
209 v3 and v7 to v8 (new vert from split)
210
211 */
212 subdpattern q_4edge = {
213         {1, 1, 1, 1, 1, 1, 1, 1},
214         {-1, 5, -1, -1, -1, -1, -1, -1},
215         {0, 0, 0, 0, 0, 0, 0, 0, 1},
216         {-1, -1, -1, 8, -1, -1, -1, 8, -1},
217         8
218 };
219
220 subdpattern *patterns[] = {
221         &t_1edge,
222         &t_2edge,
223         &t_3edge,
224         &q_1edge,
225         &q_2adjedge,
226         &q_2opedge,
227         &q_3edge,
228         &q_4edge,
229 };
230
231 #define PLEN    (sizeof(patterns) / sizeof(void*))
232
233 #define SUBD_SPLIT      1
234 #define FACE_NEW        1
235 #define MAX_FACE        10
236
237 void esubdivide_exec(BMesh *bmesh, BMOperator *op)
238 {
239         BMOpSlot *einput;
240         BMEdge *edge, *nedge, *edges[MAX_FACE];
241         BMFace *face, *nf;
242         BMLoop *nl, *loop;
243         BMVert *v1, *verts[MAX_FACE], *lastv;
244         BMIter fiter, eiter;
245         subdpattern *pat;
246         int i, j, matched, a, b, newlen, newvlen;
247         
248         BMO_Flag_Buffer(bmesh, op, BMOP_ESUBDIVIDE_EDGES, SUBD_SPLIT);
249
250         einput = BMO_GetSlot(op, BMOP_ESUBDIVIDE_EDGES);
251
252         /*first go through and split edges*/
253         for (i=0; i<einput->len; i++) {
254                 edge = ((BMEdge**)einput->data.p)[i];
255                 v1 = BM_Split_Edge(bmesh, edge->v1, edge, &nedge, 0.5, 1);
256                 BMO_SetFlag(bmesh, v1, SUBD_SPLIT);
257                 BMO_SetFlag(bmesh, nedge, SUBD_SPLIT);
258         }
259
260         /*now go through all the faces and connect the new geometry*/
261         for (face = BMIter_New(&fiter, bmesh, BM_FACES, NULL); face; face=BMIter_Step(&fiter)) {
262                 matched = 0;
263                 if (BMO_TestFlag(bmesh, face, FACE_NEW)) continue;
264
265                 if (face->len < MAX_FACE) {
266                         /*try all possible pattern rotations*/
267                         for (i=0; i<PLEN; i++) {
268                                 if (patterns[i]->len != face->len) continue;
269                                 lastv = NULL;
270                                 for (j=0; j<patterns[i]->len; j++) {
271                                         for (a=0, loop=BMIter_New(&eiter, bmesh, BM_LOOPS_OF_FACE,face); loop; a++, loop=BMIter_Step(&eiter)) {
272                                                 b = (j + a) % patterns[i]->len;
273
274                                                 edge = loop->e;
275                                                 verts[b] = loop->v;
276                                                 edges[b] = edge;
277                                                 if (!(patterns[i]->seledges[b] == BMO_TestFlag(bmesh, edge, SUBD_SPLIT))) break;
278
279                                                 lastv = verts[b];
280                                         }
281
282                                         if (a == face->len) {
283                                                 matched = 1;
284                                                 pat = patterns[i];
285                                                 break;
286                                         }
287                                 }
288                                 if (matched) break;
289                         }
290                 }
291
292                 if (matched) {
293                         /*first stage*/
294                         newlen = pat->len;
295                         for (i=0; i<pat->len; i++) {
296                                 if (pat->connectverts[i] != -1) {
297                                         edges[newlen++] = BM_Connect_Verts(bmesh, verts[i], verts[pat->connectverts[i]], &nf);
298                                         BMO_SetFlag(bmesh, nf, FACE_NEW);
299                                 }
300                         }
301
302                         newvlen = pat->len;             
303                         /*second stage*/
304                         for (i; i<newlen; i++) {
305                                 if (pat->secondstage_splitedges[i]) {
306                                         v1 = BM_Split_Edge(bmesh, edges[i]->v1, edges[i], &nedge, 0.5, 1);
307                                         verts[newvlen++] = v1;
308                                 }
309                         }
310
311                         for (i=0; i<newvlen; i++) {
312                                 if (pat->secondstage_connect[i] != -1) {
313                                         edges[newlen++] = BM_Connect_Verts(bmesh, verts[i], verts[pat->secondstage_connect[i]], &nf);
314                                         BMO_SetFlag(bmesh, nf, FACE_NEW);
315                                 }
316                         }
317                 } else { /*no match in the pattern*/
318                         /*this should do some sort of generic subdivision*/
319                 }
320         }
321 }