merge with/from trunk at r35190
[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 #include "DNA_windowmanager_types.h"
40
41 #include "ED_mesh.h"
42
43 #include "bmesh.h"
44 #include "mesh_intern.h"
45 #include "subdivideop.h"
46
47 #include <stdio.h>
48 #include <stdlib.h>
49 #include <string.h>
50 #include <math.h>
51
52 typedef struct EdgeTag {
53         BMVert *newv1, *newv2;
54         BMEdge *newe1, *newe2;
55         int tag;
56 } EdgeTag;
57
58 #define EDGE_SEAM       1
59 #define EDGE_DEL        2
60 #define EDGE_MARK       4
61 #define EDGE_RET1       8
62 #define EDGE_RET2       16
63
64 #define FACE_DEL        1
65 #define FACE_NEW        2
66
67 static BMFace *remake_face(BMesh *bm, EdgeTag *etags, BMFace *f, BMVert **verts)
68 {
69         BMIter liter1, liter2;
70         EdgeTag *et;
71         BMFace *f2;
72         BMLoop *l, *l2;
73         BMEdge **edges = (BMEdge**) verts; /*he he, can reuse this, sneaky! ;)*/
74         BMVert *lastv1, *lastv2, *v1, *v2;
75         int i;
76
77         /*we do final edge last*/
78         lastv1 = verts[f->len-1];
79         lastv2 = verts[0];
80         v1 = verts[0];
81         v2 = verts[1];
82         for (i=0; i<f->len-1; i++) {
83                 edges[i] = BM_Make_Edge(bm, verts[i], verts[i+1], NULL, 1);
84
85                 if (!edges[i])
86                         return NULL;
87         }
88         
89         edges[i] = BM_Make_Edge(bm, lastv1, lastv2, NULL, 1);
90
91         f2 = BM_Make_Ngon(bm, v1, v2, edges, f->len, 0);
92         if (!f2)
93                 return NULL;
94         
95         BM_Copy_Attributes(bm, bm, f, f2);
96
97         l = BMIter_New(&liter1, bm, BM_LOOPS_OF_FACE, f);
98         l2 = BMIter_New(&liter2, bm, BM_LOOPS_OF_FACE, f2);
99         for (; l && l2; l=BMIter_Step(&liter1), l2=BMIter_Step(&liter2)) {
100                 BM_Copy_Attributes(bm, bm, l, l2);
101                 if (l->e != l2->e) {
102                         /*set up data for figuring out the two sides of
103                           the splits*/
104                         BMINDEX_SET(l2->e, BMINDEX_GET(l->e));
105                         et = etags + BMINDEX_GET(l->e);
106                         
107                         if (!et->newe1) et->newe1 = l2->e;
108                         else et->newe2 = l2->e;
109
110                         if (BMO_TestFlag(bm, l->e, EDGE_SEAM))
111                                 BMO_SetFlag(bm, l2->e, EDGE_SEAM);
112
113                         BM_Copy_Attributes(bm, bm, l->e, l2->e);
114                 }
115
116                 BMO_SetFlag(bm, l->e, EDGE_MARK);
117                 BMO_SetFlag(bm, l2->e, EDGE_MARK);
118         }
119
120         return f2;
121 }
122
123 void tag_out_edges(BMesh *bm, EdgeTag *etags, BMOperator *op)
124 {
125         EdgeTag *et;
126         BMIter iter;
127         BMLoop *l, *startl;
128         BMEdge *e;
129         BMVert *v;
130         int i, ok;
131         
132         ok=0;
133         while (ok++ < 100000) {         
134                 BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
135                         if (!BMO_TestFlag(bm, e, EDGE_SEAM))
136                                 continue;
137
138                         et = etags + BMINDEX_GET(e);
139                         if (!et->tag && e->l) {
140                                 break;
141                         }
142                 }
143                 
144                 if (!e)
145                         break;
146
147                 /*ok we found an edge, part of a region of splits we need
148                   to identify.  now walk along it.*/
149                 for (i=0; i<2; i++) {
150                         l = e->l;
151                         
152                         v = i ? ((BMLoop*)l->next)->v : l->v;
153
154                         while (1) {
155                                 et = etags + BMINDEX_GET(l->e);
156                                 if (et->newe1 == l->e) {
157                                         if (et->newe1) {
158                                                 BMO_SetFlag(bm, et->newe1, EDGE_RET1);
159                                                 BMO_ClearFlag(bm, et->newe1, EDGE_SEAM);
160                                         }
161                                         if (et->newe2) {
162                                                 BMO_SetFlag(bm, et->newe2, EDGE_RET2);
163                                                 BMO_ClearFlag(bm, et->newe2, EDGE_SEAM);
164                                         }
165                                 } else {
166                                         if (et->newe1) {
167                                                 BMO_SetFlag(bm, et->newe1, EDGE_RET2);
168                                                 BMO_ClearFlag(bm, et->newe1, EDGE_SEAM);
169                                         }
170                                         if (et->newe2) {
171                                                 BMO_SetFlag(bm, et->newe2, EDGE_RET1);
172                                                 BMO_ClearFlag(bm, et->newe2, EDGE_SEAM);
173                                         }
174                                 }
175
176                                 startl = l;
177                                 do {
178                                         l = BM_OtherFaceLoop(l->e, l->f, v);
179                                         if (BM_Edge_FaceCount(l->e) != 2)
180                                                 break;
181                                         l = (BMLoop*) l->radial_next;
182                                 } while (l != startl && !BMO_TestFlag(bm, l->e, EDGE_SEAM));
183                                 
184                                 if (l == startl || !BMO_TestFlag(bm, l->e, EDGE_SEAM))
185                                         break;
186
187                                 if (l->v == v) {
188                                         v = ((BMLoop*)l->next)->v;
189                                 } else v = l->v;
190                         }
191                 }
192         }
193 }
194
195 void bmesh_edgesplitop_exec(BMesh *bm, BMOperator *op)
196 {
197         EdgeTag *etags, *et;
198         BMIter iter, liter;
199         BMOIter siter;
200         BMFace *f, *f2;
201         BMLoop *l, *nextl, *prevl, *l2, *l3;
202         BMEdge *e, *e2;
203         BLI_array_declare(verts);
204         BMVert *v, *v2, **verts = NULL;
205         int i, j;
206
207         BMO_Flag_Buffer(bm, op, "edges", EDGE_SEAM, BM_EDGE);
208         
209         /*single marked edges unconnected to any other marked edges
210           are illegal, go through and unmark them*/
211         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
212                 for (i=0; i<2; i++) {
213                         BM_ITER(e2, &iter, bm, BM_EDGES_OF_VERT, i ? e->v2 : e->v1) {
214                                 if (e != e2 && BMO_TestFlag(bm, e2, EDGE_SEAM))
215                                         break;
216                         }
217                         if (e2)
218                                 break;
219                 }
220                 if (!e2)
221                         BMO_ClearFlag(bm, e, EDGE_SEAM);
222         }
223
224         etags = MEM_callocN(sizeof(EdgeTag)*bm->totedge, "EdgeTag");
225         
226         i = 0;
227         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
228                 BMINDEX_SET(e, i);
229                 i++;
230         }
231
232 #ifdef ETV
233 #undef ETV
234 #endif
235 #ifdef SETETV
236 #undef SETETV
237 #endif
238
239 #define ETV(et, v, l) (l->e->v1 == v ? et->newv1 : et->newv2)
240 #define SETETV(et, v, l, vs) l->e->v1 == v ? (et->newv1 = vs) : (et->newv2 = vs)
241
242         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
243                 if (BMO_TestFlag(bm, f, FACE_NEW))
244                         continue;
245                 
246                 BLI_array_empty(verts);
247                 BLI_array_growitems(verts, f->len);
248                 memset(verts, 0, sizeof(BMVert*)*f->len);
249                 
250                 i = 0;
251                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
252                         if (!BMO_TestFlag(bm, l->e, EDGE_SEAM)) {
253                                 if (!verts[i]) {
254                                         et = etags + BMINDEX_GET(l->e);
255                                         if (ETV(et, l->v, l))
256                                                 verts[i] = ETV(et, l->v, l);
257                                         else verts[i] = l->v;
258                                 }
259                                 i++;
260                                 continue;
261                         }
262
263                         BMO_SetFlag(bm, l->e, EDGE_DEL);
264
265                         nextl = (BMLoop*) l->next;
266                         prevl = (BMLoop*) l->prev;
267                         
268                         for (j=0; j<2; j++) {
269                                 l2 = j ? nextl : prevl;
270                                 v = j ? l2->v : l->v;
271
272                                 if (BMO_TestFlag(bm, l2->e, EDGE_SEAM)) {
273                                         if (!verts[j ? (i+1) % f->len : i]) {
274                                                 /*make unique vert here for this face only*/
275                                                 v2 = BM_Make_Vert(bm, v->co, NULL);
276                                                 copy_v3_v3(v2->no, v->no);
277                                                 BM_Copy_Attributes(bm, bm, v, v2);
278
279                                                 verts[j ? (i+1) % f->len : i] = v2;
280                                         } else v2 = verts[j ? (i+1) % f->len : i];
281                                 } else {
282                                         /*generate unique vert for non-seam edge(s)
283                                           around the manifold vert fan if necassary*/
284
285                                         /*first check that we have two seam edges
286                                           somewhere within this fan*/
287                                         l3 = l2;
288                                         do {
289                                                 if (BM_Edge_FaceCount(l3->e) != 2) {
290                                                         /*if we hit a boundary edge, tag
291                                                           l3 as null so we know to disconnect
292                                                           it*/
293                                                         if (BM_Edge_FaceCount(l3->e) == 1)
294                                                                 l3 = NULL;
295                                                         break;
296                                                 }
297
298                                                 l3 = (BMLoop*)l3->radial_next;
299                                                 l3 = BM_OtherFaceLoop(l3->e, l3->f, v);
300                                         } while (l3 != l2 && !BMO_TestFlag(bm, l3->e, EDGE_SEAM));
301
302                                         if (l3 == NULL || (BMO_TestFlag(bm, l3->e, EDGE_SEAM) && l3->e != l->e)) {
303                                                 et = etags + BMINDEX_GET(l2->e);
304                                                 if (ETV(et, v, l2) == NULL) {
305                                                         v2 = BM_Make_Vert(bm, v->co, NULL);
306                                                         copy_v3_v3(v2->no, v->no);
307                                                         BM_Copy_Attributes(bm, bm, v, v2);
308                                                         
309                                                         l3 = l2;
310                                                         do {
311                                                                 SETETV(et, v, l3, v2);
312                                                                 if (BM_Edge_FaceCount(l3->e) != 2)
313                                                                         break;
314
315                                                                 l3 = (BMLoop*)l3->radial_next;
316                                                                 l3 = BM_OtherFaceLoop(l3->e, l3->f, v);
317                                                                 
318                                                                 et = etags + BMINDEX_GET(l3->e);
319                                                         } while (l3 != l2 && !BMO_TestFlag(bm, l3->e, EDGE_SEAM));
320                                                 } else v2 = ETV(et, v, l2);
321
322                                                 verts[j ? (i+1) % f->len : i] = v2;
323                                         } else verts[j ? (i+1) % f->len : i] = v;
324                                 }
325                         }
326
327                         i++;
328                 }
329
330                 f2 = remake_face(bm, etags, f, verts);
331                 if (!f2)
332                         continue;
333
334                 BMO_SetFlag(bm, f, FACE_DEL);
335                 BMO_SetFlag(bm, f2, FACE_NEW);
336         }
337         
338         BMO_CallOpf(bm, "del geom=%ff context=%i", FACE_DEL, DEL_ONLYFACES);
339
340         /*test EDGE_MARK'd edges if we need to delete them, EDGE_MARK
341           is set in remake_face*/
342         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
343                 if (BMO_TestFlag(bm, e, EDGE_MARK)) {
344                         if (!e->l)
345                                 BMO_SetFlag(bm, e, EDGE_DEL);
346                 }
347         }
348
349         BMO_CallOpf(bm, "del geom=%fe context=%i", EDGE_DEL, DEL_EDGES);
350         
351         tag_out_edges(bm, etags, op);
352         BMO_Flag_To_Slot(bm, op, "edgeout1", EDGE_RET1, BM_EDGE);
353         BMO_Flag_To_Slot(bm, op, "edgeout2", EDGE_RET2, BM_EDGE);
354
355         BLI_array_free(verts);
356         if (etags) MEM_freeN(etags);
357 }
358
359 #undef ETV
360 #undef SETETV