skip assigning vars for inline bmesh flag funcs, just cast.
[blender.git] / source / blender / bmesh / operators / edgesplitop.c
1 /**
2  * $Id:
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.  
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * Contributor(s): Joseph Eagar
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 #include "MEM_guardedalloc.h"
29
30 #include "BKE_utildefines.h"
31 #include "BKE_tessmesh.h"
32
33 #include "BLI_math.h"
34 #include "BLI_rand.h"
35 #include "BLI_ghash.h"
36 #include "BLI_array.h"
37
38 #include "DNA_object_types.h"
39
40 #include "ED_mesh.h"
41
42 #include "bmesh.h"
43 #include "mesh_intern.h"
44 #include "subdivideop.h"
45
46 #include "bmesh_operators_private.h" /* own include */
47
48 #include <stdio.h>
49 #include <stdlib.h>
50 #include <string.h>
51 #include <math.h>
52
53 typedef struct EdgeTag {
54         BMVert *newv1, *newv2;
55         BMEdge *newe1, *newe2;
56         int tag;
57 } EdgeTag;
58
59 #define EDGE_SEAM       1
60 #define EDGE_DEL        2
61 #define EDGE_MARK       4
62 #define EDGE_RET1       8
63 #define EDGE_RET2       16
64
65 #define FACE_DEL        1
66 #define FACE_NEW        2
67
68 static BMFace *remake_face(BMesh *bm, EdgeTag *etags, BMFace *f, BMVert **verts)
69 {
70         BMIter liter1, liter2;
71         EdgeTag *et;
72         BMFace *f2;
73         BMLoop *l, *l2;
74         BMEdge **edges = (BMEdge**) verts; /*he he, can reuse this, sneaky! ;)*/
75         BMVert *lastv1, *lastv2, *v1, *v2;
76         int i;
77
78         /*we do final edge last*/
79         lastv1 = verts[f->len-1];
80         lastv2 = verts[0];
81         v1 = verts[0];
82         v2 = verts[1];
83         for (i=0; i<f->len-1; i++) {
84                 edges[i] = BM_Make_Edge(bm, verts[i], verts[i+1], NULL, 1);
85
86                 if (!edges[i])
87                         return NULL;
88         }
89         
90         edges[i] = BM_Make_Edge(bm, lastv1, lastv2, NULL, 1);
91
92         f2 = BM_Make_Ngon(bm, v1, v2, edges, f->len, 0);
93         if (!f2)
94                 return NULL;
95         
96         BM_Copy_Attributes(bm, bm, f, f2);
97
98         l = BMIter_New(&liter1, bm, BM_LOOPS_OF_FACE, f);
99         l2 = BMIter_New(&liter2, bm, BM_LOOPS_OF_FACE, f2);
100         for (; l && l2; l=BMIter_Step(&liter1), l2=BMIter_Step(&liter2)) {
101                 BM_Copy_Attributes(bm, bm, l, l2);
102                 if (l->e != l2->e) {
103                         /*set up data for figuring out the two sides of
104                           the splits*/
105                         BM_SetIndex(l2->e, BM_GetIndex(l->e));
106                         et = etags + BM_GetIndex(l->e);
107                         
108                         if (!et->newe1) et->newe1 = l2->e;
109                         else et->newe2 = l2->e;
110
111                         if (BMO_TestFlag(bm, l->e, EDGE_SEAM))
112                                 BMO_SetFlag(bm, l2->e, EDGE_SEAM);
113
114                         BM_Copy_Attributes(bm, bm, l->e, l2->e);
115                 }
116
117                 BMO_SetFlag(bm, l->e, EDGE_MARK);
118                 BMO_SetFlag(bm, l2->e, EDGE_MARK);
119         }
120
121         return f2;
122 }
123
124 static void tag_out_edges(BMesh *bm, EdgeTag *etags, BMOperator *UNUSED(op))
125 {
126         EdgeTag *et;
127         BMIter iter;
128         BMLoop *l, *startl;
129         BMEdge *e;
130         BMVert *v;
131         int i, ok;
132         
133         ok=0;
134         while (ok++ < 100000) {         
135                 BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
136                         if (!BMO_TestFlag(bm, e, EDGE_SEAM))
137                                 continue;
138
139                         et = etags + BM_GetIndex(e);
140                         if (!et->tag && e->l) {
141                                 break;
142                         }
143                 }
144                 
145                 if (!e)
146                         break;
147
148                 /*ok we found an edge, part of a region of splits we need
149                   to identify.  now walk along it.*/
150                 for (i=0; i<2; i++) {
151                         l = e->l;
152                         
153                         v = i ? ((BMLoop*)l->next)->v : l->v;
154
155                         while (1) {
156                                 et = etags + BM_GetIndex(l->e);
157                                 if (et->newe1 == l->e) {
158                                         if (et->newe1) {
159                                                 BMO_SetFlag(bm, et->newe1, EDGE_RET1);
160                                                 BMO_ClearFlag(bm, et->newe1, EDGE_SEAM);
161                                         }
162                                         if (et->newe2) {
163                                                 BMO_SetFlag(bm, et->newe2, EDGE_RET2);
164                                                 BMO_ClearFlag(bm, et->newe2, EDGE_SEAM);
165                                         }
166                                 } else {
167                                         if (et->newe1) {
168                                                 BMO_SetFlag(bm, et->newe1, EDGE_RET2);
169                                                 BMO_ClearFlag(bm, et->newe1, EDGE_SEAM);
170                                         }
171                                         if (et->newe2) {
172                                                 BMO_SetFlag(bm, et->newe2, EDGE_RET1);
173                                                 BMO_ClearFlag(bm, et->newe2, EDGE_SEAM);
174                                         }
175                                 }
176
177                                 startl = l;
178                                 do {
179                                         l = BM_OtherFaceLoop(l->e, l->f, v);
180                                         if (BM_Edge_FaceCount(l->e) != 2)
181                                                 break;
182                                         l = (BMLoop*) l->radial_next;
183                                 } while (l != startl && !BMO_TestFlag(bm, l->e, EDGE_SEAM));
184                                 
185                                 if (l == startl || !BMO_TestFlag(bm, l->e, EDGE_SEAM))
186                                         break;
187
188                                 if (l->v == v) {
189                                         v = ((BMLoop*)l->next)->v;
190                                 } else v = l->v;
191                         }
192                 }
193         }
194 }
195
196 void bmesh_edgesplitop_exec(BMesh *bm, BMOperator *op)
197 {
198         EdgeTag *etags, *et;
199         BMIter iter, liter;
200         BMOIter siter;
201         BMFace *f, *f2;
202         BMLoop *l, *nextl, *prevl, *l2, *l3;
203         BMEdge *e, *e2;
204         BLI_array_declare(verts);
205         BMVert *v, *v2, **verts = NULL;
206         int i, j;
207
208         BMO_Flag_Buffer(bm, op, "edges", EDGE_SEAM, BM_EDGE);
209         
210         /*single marked edges unconnected to any other marked edges
211           are illegal, go through and unmark them*/
212         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
213                 for (i=0; i<2; i++) {
214                         BM_ITER(e2, &iter, bm, BM_EDGES_OF_VERT, i ? e->v2 : e->v1) {
215                                 if (e != e2 && BMO_TestFlag(bm, e2, EDGE_SEAM))
216                                         break;
217                         }
218                         if (e2)
219                                 break;
220                 }
221                 if (!e2)
222                         BMO_ClearFlag(bm, e, EDGE_SEAM);
223         }
224
225         etags = MEM_callocN(sizeof(EdgeTag)*bm->totedge, "EdgeTag");
226         
227         i = 0;
228         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
229                 BM_SetIndex(e, i);
230                 i++;
231         }
232
233 #ifdef ETV
234 #undef ETV
235 #endif
236 #ifdef SETETV
237 #undef SETETV
238 #endif
239
240 #define ETV(et, v, l) (l->e->v1 == v ? et->newv1 : et->newv2)
241 #define SETETV(et, v, l, vs) l->e->v1 == v ? (et->newv1 = vs) : (et->newv2 = vs)
242
243         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
244                 if (BMO_TestFlag(bm, f, FACE_NEW))
245                         continue;
246                 
247                 BLI_array_empty(verts);
248                 BLI_array_growitems(verts, f->len);
249                 memset(verts, 0, sizeof(BMVert*)*f->len);
250                 
251                 i = 0;
252                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
253                         if (!BMO_TestFlag(bm, l->e, EDGE_SEAM)) {
254                                 if (!verts[i]) {
255                                         et = etags + BM_GetIndex(l->e);
256                                         if (ETV(et, l->v, l))
257                                                 verts[i] = ETV(et, l->v, l);
258                                         else verts[i] = l->v;
259                                 }
260                                 i++;
261                                 continue;
262                         }
263
264                         nextl = (BMLoop*) l->next;
265                         prevl = (BMLoop*) l->prev;
266                         
267                         for (j=0; j<2; j++) {
268                                 l2 = j ? nextl : prevl;
269                                 v = j ? l2->v : l->v;
270
271                                 if (BMO_TestFlag(bm, l2->e, EDGE_SEAM)) {
272                                         if (!verts[j ? (i+1) % f->len : i]) {
273                                                 /*make unique vert here for this face only*/
274                                                 v2 = BM_Make_Vert(bm, v->co, NULL);
275                                                 copy_v3_v3(v2->no, v->no);
276                                                 BM_Copy_Attributes(bm, bm, v, v2);
277
278                                                 verts[j ? (i+1) % f->len : i] = v2;
279                                         } else v2 = verts[j ? (i+1) % f->len : i];
280                                 } else {
281                                         /*generate unique vert for non-seam edge(s)
282                                           around the manifold vert fan if necassary*/
283
284                                         /*first check that we have two seam edges
285                                           somewhere within this fan*/
286                                         l3 = l2;
287                                         do {
288                                                 if (BM_Edge_FaceCount(l3->e) != 2) {
289                                                         /*if we hit a boundary edge, tag
290                                                           l3 as null so we know to disconnect
291                                                           it*/
292                                                         if (BM_Edge_FaceCount(l3->e) == 1)
293                                                                 l3 = NULL;
294                                                         break;
295                                                 }
296
297                                                 l3 = (BMLoop*)l3->radial_next;
298                                                 l3 = BM_OtherFaceLoop(l3->e, l3->f, v);
299                                         } while (l3 != l2 && !BMO_TestFlag(bm, l3->e, EDGE_SEAM));
300
301                                         if (l3 == NULL || (BMO_TestFlag(bm, l3->e, EDGE_SEAM) && l3->e != l->e)) {
302                                                 et = etags + BM_GetIndex(l2->e);
303                                                 if (ETV(et, v, l2) == NULL) {
304                                                         v2 = BM_Make_Vert(bm, v->co, NULL);
305                                                         copy_v3_v3(v2->no, v->no);
306                                                         BM_Copy_Attributes(bm, bm, v, v2);
307                                                         
308                                                         l3 = l2;
309                                                         do {
310                                                                 SETETV(et, v, l3, v2);
311                                                                 if (BM_Edge_FaceCount(l3->e) != 2)
312                                                                         break;
313
314                                                                 l3 = (BMLoop*)l3->radial_next;
315                                                                 l3 = BM_OtherFaceLoop(l3->e, l3->f, v);
316                                                                 
317                                                                 et = etags + BM_GetIndex(l3->e);
318                                                         } while (l3 != l2 && !BMO_TestFlag(bm, l3->e, EDGE_SEAM));
319                                                 } else v2 = ETV(et, v, l2);
320
321                                                 verts[j ? (i+1) % f->len : i] = v2;
322                                         } else verts[j ? (i+1) % f->len : i] = v;
323                                 }
324                         }
325
326                         i++;
327                 }
328
329                 f2 = remake_face(bm, etags, f, verts);
330                 if (!f2)
331                         continue;
332
333                 BMO_SetFlag(bm, f, FACE_DEL);
334                 BMO_SetFlag(bm, f2, FACE_NEW);
335         }
336         
337         BMO_CallOpf(bm, "del geom=%ff context=%i", FACE_DEL, DEL_ONLYFACES);
338
339         /*test EDGE_MARK'd edges if we need to delete them, EDGE_MARK
340           is set in remake_face*/
341         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
342                 if (BMO_TestFlag(bm, e, EDGE_MARK)) {
343                         if (!e->l)
344                                 BMO_SetFlag(bm, e, EDGE_DEL);
345                 }
346         }
347
348         BMO_CallOpf(bm, "del geom=%fe context=%i", EDGE_DEL, DEL_EDGES);
349         
350         tag_out_edges(bm, etags, op);
351         BMO_Flag_To_Slot(bm, op, "edgeout1", EDGE_RET1, BM_EDGE);
352         BMO_Flag_To_Slot(bm, op, "edgeout2", EDGE_RET2, BM_EDGE);
353
354         BLI_array_free(verts);
355         if (etags) MEM_freeN(etags);
356 }
357
358 #undef ETV
359 #undef SETETV