merge with 2.5 at r18796. note I've customized the
[blender.git] / source / blender / bmesh / operators / subdivideop.c
1 #include "MEM_guardedalloc.h"
2
3 #include "BKE_utildefines.h"
4
5 #include "BLI_arithb.h"
6 #include "BLI_rand.h"
7
8 #include "DNA_object_types.h"
9
10 #include "ED_mesh.h"
11
12 #include "bmesh.h"
13 #include "mesh_intern.h"
14
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <string.h>
18 #include <math.h>
19
20 #define SUBD_SPLIT      1
21 #define FACE_NEW        1
22 #define MAX_FACE        800
23
24 /*
25 NOTE: beauty has been renamed to flag!
26 */
27
28 /*
29 note: this is a pattern-based edge subdivider.
30 it tries to match a pattern to edge selections on faces,
31 then executes functions to cut them.
32 */
33 typedef struct subdpattern {
34         int seledges[20]; //selected edges mask, for splitting
35
36         /*verts starts at the first new vert cut, not the first vert in the
37           face*/
38         void (*connectexec)(BMesh *bm, BMFace *face, BMVert **verts, 
39                             int numcuts, int flag, float rad);
40         int len; /*total number of verts*/
41 } subdpattern;
42
43 /*generic subdivision rules:
44   
45   * two selected edges in a face should make a link
46     between them.
47
48   * one edge should do, what? make pretty topology, or just
49     split the edge only?
50 */
51
52
53 /* calculates offset for co, based on fractal, sphere or smooth settings  */
54 static void alter_co(float *co, BMEdge *edge, float rad, int flag, float perc,
55                      BMVert *vsta, BMVert *vend)
56 {
57         float vec1[3], fac;
58         
59         if(flag & B_SMOOTH) {
60                 /* we calculate an offset vector vec1[], to be added to *co */
61                 float len, fac, nor[3], nor1[3], nor2[3];
62                 
63                 VecSubf(nor, vsta->co, vend->co);
64                 len= 0.5f*Normalize(nor);
65         
66                 VECCOPY(nor1, vsta->no);
67                 VECCOPY(nor2, vend->no);
68         
69                 /* cosine angle */
70                 fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
71                 
72                 vec1[0]= fac*nor1[0];
73                 vec1[1]= fac*nor1[1];
74                 vec1[2]= fac*nor1[2];
75         
76                 /* cosine angle */
77                 fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
78                 
79                 vec1[0]+= fac*nor2[0];
80                 vec1[1]+= fac*nor2[1];
81                 vec1[2]+= fac*nor2[2];
82                 
83                 vec1[0]*= rad*len;
84                 vec1[1]*= rad*len;
85                 vec1[2]*= rad*len;
86                 
87                 co[0] += vec1[0];
88                 co[1] += vec1[1];
89                 co[2] += vec1[2];
90         }
91         else {
92                 if(rad > 0.0) {   /* subdivide sphere */
93                         Normalize(co);
94                         co[0]*= rad;
95                         co[1]*= rad;
96                         co[2]*= rad;
97                 }
98                 else if(rad< 0.0) {  /* fractal subdivide */
99                         fac= rad* VecLenf(vsta->co, vend->co);
100                         vec1[0]= fac*(float)(0.5-BLI_drand());
101                         vec1[1]= fac*(float)(0.5-BLI_drand());
102                         vec1[2]= fac*(float)(0.5-BLI_drand());
103                         VecAddf(co, co, vec1);
104                 }
105
106         }
107 }
108
109 /* assumes in the edge is the correct interpolated vertices already */
110 /* percent defines the interpolation, rad and flag are for special options */
111 /* results in new vertex with correct coordinate, vertex normal and weight group info */
112 static BMVert *bm_subdivide_edge_addvert(BMesh *bm, BMEdge *edge, float rad, 
113                                          int flag, float percent, BMEdge **out,
114                                          BMVert *vsta, BMVert *vend)
115 {
116         BMVert *ev;
117 //      float co[3];
118         
119         ev = BM_Split_Edge(bm, edge->v1, edge, out, percent, 1);
120
121         /* offset for smooth or sphere or fractal */
122         alter_co(ev->co, edge, rad, flag, percent, vsta, vend);
123
124 #if 0 //TODO
125         /* clip if needed by mirror modifier */
126         if (edge->v1->f2) {
127                 if ( edge->v1->f2 & edge->v2->f2 & 1) {
128                         co[0]= 0.0f;
129                 }
130                 if ( edge->v1->f2 & edge->v2->f2 & 2) {
131                         co[1]= 0.0f;
132                 }
133                 if ( edge->v1->f2 & edge->v2->f2 & 4) {
134                         co[2]= 0.0f;
135                 }
136         }
137 #endif  
138         
139         return ev;
140 }
141
142 static BMVert *subdivideedgenum(BMesh *bm, BMEdge *edge, 
143                                 int curpoint, int totpoint, float rad, 
144                                 int flag, BMEdge **newe,
145                                 BMVert *vsta, BMVert *vend)
146 {
147         BMVert *ev;
148         float percent;
149          
150         if (flag & (B_PERCENTSUBD) && totpoint == 1)
151                 /*I guess the idea is vertices store what
152                   percent to use?*/
153                 //percent=(float)(edge->tmp.l)/32768.0f;
154                 percent= 1.0; //edge->tmp.fp;
155         else {
156                 percent= 1.0f/(float)(totpoint+1-curpoint);
157
158         }
159         
160         /*{
161                 float co[3], co2[3];
162                 VecSubf(co, edge->v2->co, edge->v1->co);
163                 VecMulf(co, 1.0f/(float)(totpoint+1-curpoint));
164                 VecAddf(co2, edge->v1->co, co);
165 */
166                 ev= bm_subdivide_edge_addvert(bm, edge, rad, flag, percent, 
167                                        newe, vsta, vend);
168 /*              VECCOPY(ev->co, co2);
169         }
170 */      
171         return ev;
172 }
173
174 static void bm_subdivide_multicut(BMesh *bm, BMEdge *edge, float rad,
175                                   int flag, int numcuts, 
176                                   BMVert *vsta, BMVert *vend) {
177         BMEdge *eed = edge, *newe;
178         BMVert *v;
179         int i;
180
181         for(i=0;i<numcuts;i++) {
182                 v = subdivideedgenum(bm, eed, i, numcuts, rad, 
183                         flag, &newe, vsta, vend);
184                 BMO_SetFlag(bm, v, SUBD_SPLIT);
185                 BMO_SetFlag(bm, eed, SUBD_SPLIT);
186         }
187 }
188
189 /*note: the patterns are rotated as necassary to
190   match the input geometry.  they're based on the
191   pre-split state of the  face*/
192
193 /*
194      
195 v3---------v2
196 |          |
197 |          |
198 |          |
199 |          |
200 v4---v0---v1
201
202 */
203 static void q_1edge_split(BMesh *bm, BMFace *face, BMVert **vlist, int numcuts,
204                           int flag, float rad) {
205         BMFace *nf;
206         int i, add;
207
208         /*if it's odd, the middle face is a quad, otherwise it's a triangle*/
209         if (numcuts % 2==0) {
210                 add = 2;
211                 for (i=0; i<numcuts; i++) {
212                         if (i == numcuts/2) add -= 1;
213                         BM_Connect_Verts(bm, vlist[i], vlist[numcuts+add], &nf);
214                 }
215         } else {
216                 add = 2;
217                 for (i=0; i<numcuts; i++) {
218                         BM_Connect_Verts(bm, vlist[i], vlist[numcuts+add], &nf);
219                         if (i == numcuts/2) {
220                                 add -= 1;
221                                 BM_Connect_Verts(bm, vlist[i], vlist[numcuts+add], &nf);
222                         }
223                 }
224
225         }
226 }
227
228 subdpattern q_1edge = {
229         {1, 0, 0, 0},
230         q_1edge_split,
231         4,
232 };
233
234
235 /*
236  
237 v4---v3---v2
238 |     s    |
239 |          |
240 |          |
241 |     s    |
242 v5---v0---v1
243
244 */
245 static void q_2edge_op_split(BMesh *bm, BMFace *face, BMVert **vlist, 
246                              int numcuts, int flag, float rad) {
247         BMFace *nf;
248         int i;
249         
250         for (i=0; i<numcuts; i++) {
251                 BM_Connect_Verts(bm, vlist[i], vlist[(numcuts-i-1)+numcuts+2], &nf);
252         }
253 }
254
255 subdpattern q_2edge_op = {
256         {1, 0, 1, 0},
257         q_2edge_op_split,
258         4,
259 };
260
261 /*
262 v6--------v5
263 |          |
264 |          |v4s
265 |          |v3s
266 |   s  s   |
267 v7-v0--v1-v2
268
269 */
270 static void q_2edge_split(BMesh *bm, BMFace *face, BMVert **vlist, 
271                              int numcuts, int flag, float rad) {
272         BMFace *nf;
273         int i;
274         
275         for (i=0; i<numcuts; i++) {
276                 BM_Connect_Verts(bm, vlist[i], vlist[numcuts+(numcuts-i)], &nf);
277         }
278         BM_Connect_Verts(bm, vlist[numcuts*2+3], vlist[numcuts*2+1], &nf);
279 }
280
281 subdpattern q_2edge = {
282         {1, 1, 0, 0},
283         q_2edge_split,
284         4,
285 };
286
287 /*  s   s
288 v8--v7--v6-v5
289 |          |
290 |          v4 s
291 |          |
292 |          v3 s
293 |   s  s   |
294 v9-v0--v1-v2
295
296 */
297 static void q_3edge_split(BMesh *bm, BMFace *face, BMVert **vlist, 
298                              int numcuts, int flag, float rad) {
299         BMFace *nf;
300         int i, add=0;
301         
302         for (i=0; i<numcuts; i++) {
303                 if (i == numcuts/2) {
304                         if (numcuts % 2 != 0) {
305                                 BM_Connect_Verts(bm, vlist[numcuts-i-1+add], vlist[i+numcuts+1], &nf);
306                         }
307                         add = numcuts*2+2;
308                 }
309                 BM_Connect_Verts(bm, vlist[numcuts-i-1+add], vlist[i+numcuts+1], &nf);
310         }
311
312         for (i=0; i<numcuts/2+1; i++) {
313                 BM_Connect_Verts(bm, vlist[i], vlist[(numcuts-i)+numcuts*2+1], &nf);
314         }
315 }
316
317 subdpattern q_3edge = {
318         {1, 1, 1, 0},
319         q_3edge_split,
320         4,
321 };
322
323 /*
324  
325            v8--v7-v6--v5
326            |     s    |
327            |v9 s     s|v4
328 first line |          |   last line
329            |v10s s   s|v3
330            v11-v0--v1-v2
331
332            it goes from bottom up
333 */
334 static void q_4edge_split(BMesh *bm, BMFace *face, BMVert **vlist, int numcuts,
335                           int flag, float rad) {
336         BMFace *nf;
337         BMVert *v, *v1, *v2;
338         BMEdge *e, *ne;
339         BMVert **lines = MEM_callocN(sizeof(BMVert*)*(numcuts+2)*(numcuts+2),
340                                      "q_4edge_split");
341         int i, j, a, b, s=numcuts+2, totv=numcuts*4+4;
342
343         /*build a 2-dimensional array of verts,
344           containing every vert (and all new ones)
345           in the face.*/
346
347         /*first line*/
348         for (i=0; i<numcuts+2; i++) {
349                 lines[i] = vlist[numcuts*3+2+(numcuts-i+1)];
350         }
351
352         /*last line*/
353         for (i=0; i<numcuts+2; i++) {
354                 lines[(s-1)*s+i] = vlist[numcuts+i];
355         }
356         
357         /*first and last members of middle lines*/
358         for (i=0; i<numcuts; i++) {
359                 a = i;
360                 b = numcuts + 1 + numcuts + 1 + (numcuts - i - 1);
361                 
362                 e = BM_Connect_Verts(bm, vlist[a], vlist[b], &nf);
363                 
364                 v1 = lines[(i+1)*s] = vlist[a];
365                 v2 = lines[(i+1)*s + s-1] = vlist[b];
366
367                 for (a=0; a<numcuts; a++) {
368                         v = subdivideedgenum(bm, e, a, numcuts, rad, flag, &ne,
369                                              v1, v2);
370                         lines[(i+1)*s+a+1] = v;
371                 }
372         }
373
374         for (i=1; i<numcuts+2; i++) {
375                 for (j=1; j<numcuts+1; j++) {
376                         a = i*s + j;
377                         b = (i-1)*s + j;
378                         BM_Connect_Verts(bm, lines[a], lines[b], &nf);
379                 }
380         }
381
382         MEM_freeN(lines);
383 }
384
385 subdpattern q_4edge = {
386         {1, 1, 1, 1},
387         q_4edge_split,
388         4,
389 };
390
391 subdpattern *patterns[] = {
392         &q_1edge,
393         &q_2edge_op,
394         &q_4edge,
395         &q_3edge,
396         &q_2edge,
397 };
398
399 #define PLEN    (sizeof(patterns) / sizeof(void*))
400
401 typedef struct subd_facedata {
402         BMVert *start; subdpattern *pat;
403 } subd_facedata;
404
405 void esubdivide_exec(BMesh *bmesh, BMOperator *op)
406 {
407         BMOpSlot *einput;
408         BMEdge *edge, *edges[MAX_FACE];
409         BMFace *face;
410         BMLoop *nl;
411         BMVert *verts[MAX_FACE];
412         BMIter fiter, liter;
413         subdpattern *pat;
414         float rad;
415         int i, j, matched, a, b, numcuts, flag, selaction;
416         subd_facedata *facedata = NULL;
417         V_DECLARE(facedata);
418         
419         BMO_Flag_Buffer(bmesh, op, BMOP_ESUBDIVIDE_EDGES, SUBD_SPLIT);
420         
421         numcuts = BMO_GetSlot(op, BMOP_ESUBDIVIDE_NUMCUTS)->data.i;
422         flag = BMO_GetSlot(op, BMOP_ESUBDIVIDE_FLAG)->data.i;
423         rad = BMO_GetSlot(op, BMOP_ESUBDIVIDE_RADIUS)->data.f;
424         selaction = BMO_GetSlot(op, BMOP_ESUBDIVIDE_SELACTION)->data.i;
425
426         einput = BMO_GetSlot(op, BMOP_ESUBDIVIDE_EDGES);
427         
428         /*first go through and split edges*/
429         for (i=0; i<einput->len; i++) {
430                 edge = ((BMEdge**)einput->data.p)[i];
431                 BMO_SetFlag(bmesh, edge, SUBD_SPLIT);
432         }
433         
434         for (face=BMIter_New(&fiter, bmesh, BM_FACES, NULL);
435              face; face=BMIter_Step(&fiter)) {
436                 /*figure out which pattern to use*/
437                 if (face->len > MAX_FACE) continue;
438
439                 i = 0;
440                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
441                      nl; nl=BMIter_Step(&liter)) {
442                         edges[i] = nl->e;
443                         verts[i] = nl->v;
444                         i++;
445                 }
446
447                 for (i=0; i<PLEN; i++) {
448                         pat = patterns[i];
449                         if (pat->len == face->len) {
450                                 for (a=0; a<pat->len; a++) {
451                                 matched = 1;
452                                 for (b=0; b<pat->len; b++) {
453                                         j = (b + a) % pat->len;
454                                         if ((!!BMO_TestFlag(bmesh, edges[j], SUBD_SPLIT))
455                                                 != (!!pat->seledges[b])) {
456                                                         matched = 0;
457                                                         break;
458                                         }
459                                 }
460                                 if (matched) break;
461                                 }
462                                 if (matched) {
463                                         V_GROW(facedata);
464                                         BMO_SetFlag(bmesh, face, SUBD_SPLIT);
465                                         j = V_COUNT(facedata) - 1;
466                                         facedata[j].pat = pat;
467                                         facedata[j].start = verts[a];
468                                         break;
469                                 }
470                         }
471                 }
472         }
473
474         /*go through and split edges*/
475         for (i=0; i<einput->len; i++) {
476                 edge = ((BMEdge**)einput->data.p)[i];
477                 bm_subdivide_multicut(bmesh, edge, rad, flag, numcuts,
478                                       edge->v1, edge->v2);
479                 //BM_Split_Edge_Multi(bmesh, edge, numcuts);
480         }
481
482         //if (facedata) V_FREE(facedata);
483         //return;
484
485         i = 0;
486         for (face=BMIter_New(&fiter, bmesh, BM_FACES, NULL);
487              face; face=BMIter_Step(&fiter)) {
488                 /*figure out which pattern to use*/
489                 if (face->len > MAX_FACE) continue;
490                 if (BMO_TestFlag(bmesh, face, SUBD_SPLIT) == 0) continue;
491                 
492                 pat = facedata[i].pat;
493                 if (!pat) continue;
494
495                 j = a = 0;
496                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
497                      nl; nl=BMIter_Step(&liter)) {
498                         if (nl->v == facedata[i].start) {
499                                 a = j+1;
500                                 break;
501                         }
502                         j++;
503                 }
504
505                 j = 0;
506                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
507                      nl; nl=BMIter_Step(&liter)) {
508                         b = (j-a+face->len) % face->len;
509                         verts[b] = nl->v;
510                         j += 1;
511                 }
512                 
513                 pat->connectexec(bmesh, face, verts, numcuts, flag, rad);
514                 i++;
515         }
516
517         if (facedata) V_FREE(facedata);
518 }
519
520 /*editmesh-emulating function*/
521 void BM_esubdivideflag(Object *obedit, BMesh *bm, int selflag, float rad, 
522                        int flag, int numcuts, int seltype) {
523         BMOperator op;
524
525         BMO_Init_Op(&op, BMOP_ESUBDIVIDE);
526         
527         BMO_Set_Int(&op, BMOP_ESUBDIVIDE_NUMCUTS, numcuts);
528         BMO_Set_Int(&op, BMOP_ESUBDIVIDE_FLAG, flag);
529         BMO_Set_Float(&op, BMOP_ESUBDIVIDE_RADIUS, rad);
530         BMO_Set_Int(&op, BMOP_ESUBDIVIDE_SELACTION, seltype);
531         BMO_HeaderFlag_To_Slot(bm, &op, BMOP_ESUBDIVIDE_EDGES, selflag, BM_EDGE);
532         
533         BMO_Exec_Op(bm, &op);
534         BMO_Finish_Op(bm, &op);
535 }
536
537 void BM_esubdivideflag_conv(Object *obedit,EditMesh *em,int selflag, float rad, 
538                        int flag, int numcuts, int seltype) {
539         BMesh *bm = editmesh_to_bmesh(em);
540         EditMesh *em2;
541
542         BM_esubdivideflag(obedit, bm, selflag, rad, flag, numcuts, seltype);
543         em2 = bmesh_to_editmesh(bm);
544         
545         free_editMesh(em);
546         *em = *em2;
547         MEM_freeN(em2);
548         BM_Free_Mesh(bm);
549 }