add option so operators can be called with a flag, currently the only flag is to...
[blender.git] / source / blender / modifiers / intern / MOD_skin.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software  Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Nicholas Bishop
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  *
22  */
23
24 /** \file blender/modifiers/intern/MOD_skin.c
25  *  \ingroup modifiers
26  */
27
28 /* Implementation based in part off the paper "B-Mesh: A Fast Modeling
29  * System for Base Meshes of 3D Articulated Shapes" (Zhongping Ji,
30  * Ligang Liu, Yigang Wang)
31  * 
32  * Note that to avoid confusion with Blender's BMesh data structure,
33  * this tool is renamed as the Skin modifier.
34  *
35  * The B-Mesh paper is current available here:
36  * http://www.math.zju.edu.cn/ligangliu/CAGD/Projects/BMesh/
37  *
38  * The main missing features in this code compared to the paper are:
39  * 
40  * + No mesh evolution. The paper suggests iteratively subsurfing the
41  *   skin output and adapting the output to better conform with the
42  *   spheres of influence surrounding each vertex.
43  *
44  * + No mesh fairing. The paper suggests re-aligning output edges to
45  *   follow principal mesh curvatures.
46  *
47  * + No auxiliary balls. These would serve to influence mesh
48  *   evolution, which as noted above is not implemented.
49  *
50  * The code also adds some features not present in the paper:
51  *
52  * + Loops in the input edge graph.
53  *
54  * + Concave surfaces around branch nodes. The paper does not discuss
55  *   how to handle non-convex regions; this code adds a number of
56  *   cleanup operations to handle many (though not all) of these
57  *   cases.
58  */
59
60 #include "MEM_guardedalloc.h"
61
62 #include "DNA_mesh_types.h"
63 #include "DNA_meshdata_types.h"
64 #include "DNA_object_types.h"
65 #include "DNA_modifier_types.h"
66
67 #include "BLI_utildefines.h"
68 #include "BLI_array.h"
69 #include "BLI_heap.h"
70 #include "BLI_listbase.h"
71 #include "BLI_math.h"
72 #include "BLI_string.h"
73
74 #include "BKE_cdderivedmesh.h"
75 #include "BKE_deform.h"
76 #include "BKE_DerivedMesh.h"
77 #include "BKE_mesh.h"
78 #include "BKE_modifier.h"
79 #include "BKE_tessmesh.h"
80
81 #include "MOD_util.h"
82
83 typedef struct {
84         float mat[3][3];
85         /* Vert that edge is pointing away from, no relation to
86          * MEdge.v1 */
87         int origin;
88 } EMat;
89
90 typedef enum {
91         CAP_START = 1,
92         CAP_END = 2,
93         SEAM_FRAME = 4,
94         ROOT = 8
95 } SkinNodeFlag;
96
97 typedef struct Frame {
98         /* Index in the MVert array */
99         BMVert *verts[4];
100         /* Location of each corner */
101         float co[4][3];
102         /* Indicates which corners have been merged with another
103          * frame's corner (so they share an MVert index) */
104         struct {
105                 /* Merge to target frame/corner (no merge if frame is null) */
106                 struct Frame *frame;
107                 int corner;
108         } merge[4];
109
110         /* For hull frames, whether each vertex is detached or not */
111         int inside_hull[4];
112         /* Whether any part of the frame (corner or edge) is detached */
113         int detached;
114 } Frame;
115
116 #define MAX_SKIN_NODE_FRAMES 2
117 typedef struct {
118         Frame frames[MAX_SKIN_NODE_FRAMES];
119         int totframe;
120
121         SkinNodeFlag flag;
122
123         /* Used for hulling a loop seam */
124         int seam_edges[2];
125 } SkinNode;
126
127 typedef struct {
128         BMesh *bm;
129         SkinModifierData *smd;
130         int mat_nr;
131 } SkinOutput;
132
133 static void add_poly(SkinOutput *so,
134                      BMVert *v1,
135                      BMVert *v2,
136                      BMVert *v3,
137                      BMVert *v4);
138
139 /***************************** Convex Hull ****************************/
140
141 static int is_quad_symmetric(BMVert *quad[4],
142                              const SkinModifierData *smd)
143 {
144         const float threshold = 0.0001f;
145         int axis;
146
147         for (axis = 0; axis < 3; axis++) {
148                 if (smd->symmetry_axes & (1 << axis)) {
149                         float a[3];
150
151                         copy_v3_v3(a, quad[0]->co);
152                         a[axis] = -a[axis];
153
154                         if (len_v3v3(a, quad[1]->co) < threshold) {
155                                 copy_v3_v3(a, quad[2]->co);
156                                 a[axis] = -a[axis];
157                                 if (len_v3v3(a, quad[3]->co) < threshold)
158                                         return 1;
159                         }
160                         else if (len_v3v3(a, quad[3]->co) < threshold) {
161                                 copy_v3_v3(a, quad[2]->co);
162                                 a[axis] = -a[axis];
163                                 if (len_v3v3(a, quad[1]->co) < threshold)
164                                         return 1;
165                         }
166                 }
167         }
168
169         return 0;
170 }
171
172 /* Returns true if the quad crosses the plane of symmetry, false otherwise */
173 static int quad_crosses_symmetry_plane(BMVert *quad[4],
174                                        const SkinModifierData *smd)
175 {
176         int axis;
177
178         for (axis = 0; axis < 3; axis++) {
179                 if (smd->symmetry_axes & (1 << axis)) {
180                         int i, left = 0, right = 0;
181
182                         for (i = 0; i < 4; i++) {
183                                 if (quad[i]->co[axis] < 0)
184                                         left = 1;
185                                 else if (quad[i]->co[axis] > 0)
186                                         right = 1;
187
188                                 if (left && right)
189                                         return TRUE;
190                         }
191                 }
192         }
193
194         return FALSE;
195 }
196
197 /* Returns true if the frame is filled by precisely two faces (and
198  * outputs those faces to fill_faces), otherwise returns false. */
199 static int skin_frame_find_contained_faces(const Frame *frame,
200                                            BMFace *fill_faces[2])
201 {
202         BMEdge *diag;
203
204         /* See if the frame is bisected by a diagonal edge */
205         diag = BM_edge_exists(frame->verts[0], frame->verts[2]);
206         if (!diag)
207                 diag = BM_edge_exists(frame->verts[1], frame->verts[3]);
208
209         if (diag)
210                 return BM_edge_face_pair(diag, &fill_faces[0], &fill_faces[1]);
211         else
212                 return FALSE;
213 }
214
215 /* Returns TRUE if hull is successfully built, FALSE otherwise */
216 static int build_hull(SkinOutput *so, Frame **frames, int totframe)
217 {
218         BMesh *bm = so->bm;
219         BMOperator op;
220         BMIter iter;
221         BMOIter oiter;
222         BMVert *v;
223         BMFace *f;
224         BMEdge *e;
225         int i, j;
226
227         BM_mesh_elem_hflag_disable_all(bm, BM_VERT, BM_ELEM_TAG, FALSE);
228
229         for (i = 0; i < totframe; i++) {
230                 for (j = 0; j < 4; j++) {
231                         BM_elem_flag_enable(frames[i]->verts[j], BM_ELEM_TAG);
232                 }
233         }
234
235         /* Deselect all faces so that only new hull output faces are
236          * selected after the operator is run */
237         BM_mesh_elem_hflag_disable_all(bm, BM_ALL, BM_ELEM_SELECT, 0);
238
239         BMO_op_initf(bm, &op, (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE),
240                      "convex_hull input=%hv", BM_ELEM_TAG);
241         BMO_op_exec(bm, &op);
242
243         if (BMO_error_occurred(bm)) {
244                 BMO_op_finish(bm, &op);
245                 return FALSE;
246         }
247
248         /* Apply face attributes to hull output */
249         BMO_ITER (f, &oiter, bm, &op, "geomout", BM_FACE) {
250                 if (so->smd->flag & MOD_SKIN_SMOOTH_SHADING)
251                         BM_elem_flag_enable(f, BM_ELEM_SMOOTH);
252                 f->mat_nr = so->mat_nr;
253         }
254
255         /* Mark interior frames */
256         BMO_ITER (v, &oiter, bm, &op, "interior_geom", BM_VERT) {
257                 for (i = 0; i < totframe; i++) {
258                         Frame *frame = frames[i];
259                         
260                         if (!frame->detached) {
261                                 for (j = 0; j < 4; j++) {
262                                         if (frame->verts[j] == v) {
263                                                 frame->inside_hull[j] = TRUE;
264                                                 frame->detached = TRUE;
265                                                 break;
266                                         }
267                                 }
268                         }
269                 }
270         }
271
272         /* Also mark frames as interior if an edge is not in the hull */
273         for (i = 0; i < totframe; i++) {
274                 Frame *frame = frames[i];
275
276                 if (!frame->detached &&
277                     (!BM_edge_exists(frame->verts[0], frame->verts[1]) ||
278                      !BM_edge_exists(frame->verts[1], frame->verts[2]) ||
279                      !BM_edge_exists(frame->verts[2], frame->verts[3]) ||
280                      !BM_edge_exists(frame->verts[3], frame->verts[0])))
281                 {
282                         frame->detached = TRUE;
283                 }
284         }
285         
286         /* Remove triangles that would fill the original frames -- skip if
287          * frame is partially detached */
288         BM_mesh_elem_hflag_disable_all(bm, BM_ALL, BM_ELEM_TAG, FALSE);
289         for (i = 0; i < totframe; i++) {
290                 Frame *frame = frames[i];
291                 if (!frame->detached) {
292                         BMFace *fill_faces[2];
293
294                         /* Check if the frame is filled by precisely two
295                          * triangles. If so, delete the triangles and their shared
296                          * edge. Otherwise, give up and mark the frame as
297                          * detached. */
298                         if (skin_frame_find_contained_faces(frame, fill_faces)) {
299                                 BM_elem_flag_enable(fill_faces[0], BM_ELEM_TAG);
300                                 BM_elem_flag_enable(fill_faces[1], BM_ELEM_TAG);
301                         }
302                         else
303                                 frame->detached = TRUE;
304                 }
305         }
306
307         /* Check if removing triangles above will create wire triangles,
308          * mark them too */
309         BMO_ITER (e, &oiter, bm, &op, "geomout", BM_EDGE) {
310                 int is_wire = TRUE;
311                 BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
312                         if (!BM_elem_flag_test(f, BM_ELEM_TAG)) {
313                                 is_wire = FALSE;
314                                 break;
315                         }
316                 }
317                 if (is_wire)
318                         BM_elem_flag_enable(e, BM_ELEM_TAG);
319         }
320
321         BMO_op_finish(bm, &op);
322
323         BMO_op_callf(bm, BMO_FLAG_DEFAULTS,
324                      "delete geom=%hef context=%i",
325                      BM_ELEM_TAG, DEL_ONLYTAGGED);
326
327         return TRUE;
328 }
329
330 /* Returns the average frame side length (frames are rectangular, so
331  * just the average of two adjacent edge lengths) */
332 static float frame_len(const Frame *frame)
333 {
334         return (len_v3v3(frame->co[0], frame->co[1]) +
335                 len_v3v3(frame->co[1], frame->co[2])) * 0.5f;
336 }
337
338 static void merge_frame_corners(Frame **frames, int totframe)
339 {
340         float dist, side_a, side_b, thresh, mid[3];
341         int i, j, k, l;
342
343         for (i = 0; i < totframe; i++) {
344                 side_a = frame_len(frames[i]);
345
346                 /* For each corner of each frame... */
347                 for (j = 0; j < 4; j++) {
348
349                         /* Ensure the merge target is not itself a merge target */
350                         if (frames[i]->merge[j].frame)
351                                 continue;
352
353                         for (k = i + 1; k < totframe; k++) {
354                                 BLI_assert(frames[i] != frames[k]);
355
356                                 side_b = frame_len(frames[k]);
357                                 thresh = MIN2(side_a, side_b) / 2.0f;
358
359                                 /* Compare with each corner of all other frames... */
360                                 for (l = 0; l < 4; l++) {
361                                         if (frames[k]->merge[l].frame)
362                                                 continue;
363
364                                         /* Some additional concerns that could be checked
365                                          * further:
366                                          *
367                                          * + Vertex coords are being used for the
368                                          *   edge-length test, but are also being
369                                          *   modified, might cause symmetry problems.
370                                          *
371                                          * + A frame could be merged diagonally across
372                                          *   another, would generate a weird (bad) T
373                                          *   junction
374                                          */
375
376                                         /* Check if corners are near each other, where
377                                          * 'near' is based in the frames' minimum side
378                                          * length */
379                                         dist = len_v3v3(frames[i]->co[j],
380                                                         frames[k]->co[l]);
381                                         if (dist < thresh) {
382                                                 mid_v3_v3v3(mid,
383                                                             frames[i]->co[j],
384                                                             frames[k]->co[l]);
385
386                                                 copy_v3_v3(frames[i]->co[j], mid);
387                                                 copy_v3_v3(frames[k]->co[l], mid);
388
389                                                 frames[k]->merge[l].frame = frames[i];
390                                                 frames[k]->merge[l].corner = j;
391
392                                                 /* Can't merge another corner into the same
393                                                  * frame corner, so move on to frame k+1 */
394                                                 break;
395                                         }
396                                 }
397                         }
398                 }
399         }
400 }
401
402 static Frame **collect_hull_frames(int v, SkinNode *frames,
403                                    const MeshElemMap *emap, const MEdge *medge,
404                                    int *tothullframe)
405 {
406         SkinNode *f;
407         Frame **hull_frames;
408         int nbr, i;
409
410         (*tothullframe) = emap[v].count;
411         hull_frames = MEM_callocN(sizeof(Frame * *) * (*tothullframe),
412                                   "hull_from_frames.hull_frames");
413         i = 0;
414         for (nbr = 0; nbr < emap[v].count; nbr++) {
415                 const MEdge *e = &medge[emap[v].indices[nbr]];
416                 f = &frames[BKE_mesh_edge_other_vert(e, v)];
417                 /* Can't have adjacent branch nodes yet */
418                 if (f->totframe)
419                         hull_frames[i++] = &f->frames[0];
420                 else
421                         (*tothullframe)--;
422         }
423
424         return hull_frames;
425 }
426
427
428 /**************************** Create Frames ***************************/
429
430 static void node_frames_init(SkinNode *nf, int totframe)
431 {
432         int i;
433
434         nf->totframe = totframe;
435         memset(nf->frames, 0, sizeof(nf->frames));
436         
437         nf->flag = 0;
438         for (i = 0; i < 2; i++)
439                 nf->seam_edges[i] = -1;
440 }
441
442 static void create_frame(Frame *frame, const float co[3],
443                          const float radius[2],
444                          float mat[3][3], float offset)
445 {
446         float rx[3], ry[3], rz[3];
447         int i;
448
449         mul_v3_v3fl(ry, mat[1], radius[0]);
450         mul_v3_v3fl(rz, mat[2], radius[1]);
451         
452         add_v3_v3v3(frame->co[3], co, ry);
453         add_v3_v3v3(frame->co[3], frame->co[3], rz);
454
455         sub_v3_v3v3(frame->co[2], co, ry);
456         add_v3_v3v3(frame->co[2], frame->co[2], rz);
457
458         sub_v3_v3v3(frame->co[1], co, ry);
459         sub_v3_v3v3(frame->co[1], frame->co[1], rz);
460
461         add_v3_v3v3(frame->co[0], co, ry);
462         sub_v3_v3v3(frame->co[0], frame->co[0], rz);
463
464         mul_v3_v3fl(rx, mat[0], offset);
465         for (i = 0; i < 4; i++)
466                 add_v3_v3v3(frame->co[i], frame->co[i], rx);
467 }
468
469 static float half_v2(const float v[2])
470 {
471         return (v[0] + v[1]) * 0.5f;
472 }
473
474 static void end_node_frames(int v, SkinNode *skin_nodes, const MVert *mvert,
475                             const MVertSkin *nodes, const MeshElemMap *emap,
476                             EMat *emat)
477 {
478         const float *rad = nodes[v].radius;
479         float mat[3][3];
480
481         if (emap[v].count == 0) {
482                 float avg = half_v2(rad);
483
484                 /* For solitary nodes, just build a box (two frames) */
485                 node_frames_init(&skin_nodes[v], 2);
486                 skin_nodes[v].flag |= (CAP_START | CAP_END);
487
488                 /* Hardcoded basis */
489                 zero_m3(mat);
490                 mat[0][2] = mat[1][0] = mat[2][1] = 1;
491
492                 /* Caps */
493                 create_frame(&skin_nodes[v].frames[0], mvert[v].co, rad, mat, avg);
494                 create_frame(&skin_nodes[v].frames[1], mvert[v].co, rad, mat, -avg);
495         }
496         else {
497                 /* For nodes with an incoming edge, create a single (capped) frame */
498                 node_frames_init(&skin_nodes[v], 1);
499                 skin_nodes[v].flag |= CAP_START;
500
501                 /* Use incoming edge for orientation */
502                 copy_m3_m3(mat, emat[emap[v].indices[0]].mat);
503                 if (emat[emap[v].indices[0]].origin != v)
504                         negate_v3(mat[0]);
505
506                 /* End frame */
507                 create_frame(&skin_nodes[v].frames[0], mvert[v].co, rad, mat, 0);
508         }
509
510         if (nodes[v].flag & MVERT_SKIN_ROOT)
511                 skin_nodes[v].flag |= ROOT;
512 }
513
514 /* Returns 1 for seam, 0 otherwise */
515 static int connection_node_mat(float mat[3][3], int v, const MeshElemMap *emap, EMat *emat)
516 {
517         float axis[3], angle, ine[3][3], oute[3][3];
518         EMat *e1, *e2;
519
520         e1 = &emat[emap[v].indices[0]];
521         e2 = &emat[emap[v].indices[1]];
522
523         if (e1->origin != v && e2->origin == v) {
524                 copy_m3_m3(ine, e1->mat);
525                 copy_m3_m3(oute, e2->mat);
526         }
527         else if (e1->origin == v && e2->origin != v) {
528                 copy_m3_m3(ine, e2->mat);
529                 copy_m3_m3(oute, e1->mat);
530         }
531         else
532                 return 1;
533
534         /* Get axis and angle to rotate frame by */
535         angle = angle_normalized_v3v3(ine[0], oute[0]) / 2.0f;
536         cross_v3_v3v3(axis, ine[0], oute[0]);
537
538         /* Build frame matrix (don't care about X axis here) */
539         copy_v3_v3(mat[0], ine[0]);
540         rotate_normalized_v3_v3v3fl(mat[1], ine[1], axis, angle);
541         rotate_normalized_v3_v3v3fl(mat[2], ine[2], axis, angle);
542
543         return 0;
544 }
545
546 static void connection_node_frames(int v, SkinNode *skin_nodes, const MVert *mvert,
547                                    const MVertSkin *nodes, const MeshElemMap *emap,
548                                    EMat *emat)
549 {
550         const float *rad = nodes[v].radius;
551         float mat[3][3];
552         EMat *e1, *e2;
553
554         if (connection_node_mat(mat, v, emap, emat)) {
555                 float avg = half_v2(rad);
556
557                 /* Get edges */
558                 e1 = &emat[emap[v].indices[0]];
559                 e2 = &emat[emap[v].indices[1]];
560
561                 /* Handle seam separately to avoid twisting */
562                 /* Create two frames, will be hulled to neighbors later */
563                 node_frames_init(&skin_nodes[v], 2);
564                 skin_nodes[v].flag |= SEAM_FRAME;
565
566                 copy_m3_m3(mat, e1->mat);
567                 if (e1->origin != v) negate_v3(mat[0]);
568                 create_frame(&skin_nodes[v].frames[0], mvert[v].co, rad, mat, avg);
569                 skin_nodes[v].seam_edges[0] = emap[v].indices[0];
570
571                 copy_m3_m3(mat, e2->mat);
572                 if (e2->origin != v) negate_v3(mat[0]);
573                 create_frame(&skin_nodes[v].frames[1], mvert[v].co, rad, mat, avg);
574                 skin_nodes[v].seam_edges[1] = emap[v].indices[1];
575
576                 return;
577         }
578
579         /* Build regular frame */
580         node_frames_init(&skin_nodes[v], 1);
581         create_frame(&skin_nodes[v].frames[0], mvert[v].co, rad, mat, 0);
582 }
583
584 static SkinNode *build_frames(const MVert *mvert, int totvert,
585                               const MVertSkin *nodes, const MeshElemMap *emap,
586                               EMat *emat)
587 {
588         SkinNode *skin_nodes;
589         int v;
590
591         skin_nodes = MEM_callocN(sizeof(SkinNode) * totvert, "build_frames.skin_nodes");
592
593         for (v = 0; v < totvert; v++) {
594                 if (emap[v].count <= 1)
595                         end_node_frames(v, skin_nodes, mvert, nodes, emap, emat);
596                 else if (emap[v].count == 2)
597                         connection_node_frames(v, skin_nodes, mvert, nodes, emap, emat);
598                 else {
599                         /* Branch node generates no frames */
600                 }
601         }
602
603         return skin_nodes;
604 }
605
606 /**************************** Edge Matrices ***************************/
607
608 static void calc_edge_mat(float mat[3][3], const float a[3], const float b[3])
609 {
610         const float z_up[3] = {0, 0, 1};
611         float dot;
612
613         /* X = edge direction */
614         sub_v3_v3v3(mat[0], b, a);
615         normalize_v3(mat[0]);
616
617         dot = dot_v3v3(mat[0], z_up);
618         if (dot > -1 + FLT_EPSILON && dot < 1 - FLT_EPSILON) {
619                 /* Y = Z cross x */
620                 cross_v3_v3v3(mat[1], z_up, mat[0]);
621                 normalize_v3(mat[1]);
622
623                 /* Z = x cross y */
624                 cross_v3_v3v3(mat[2], mat[0], mat[1]);
625                 normalize_v3(mat[2]);
626         }
627         else {
628                 mat[1][0] = 1;
629                 mat[1][1] = 0;
630                 mat[1][2] = 0;
631                 mat[2][0] = 0;
632                 mat[2][1] = 1;
633                 mat[2][2] = 0;
634         }
635 }
636
637 static void build_emats_rec(int *visited_e, EMat *emat,
638                             const MeshElemMap *emap, const MEdge *medge,
639                             const MVertSkin *vs, const MVert *mvert,
640                             int parent_v, float parent_mat[3][3])
641 {
642         float axis[3], angle;
643         int i, e, v, parent_is_branch;
644
645         parent_is_branch = ((emap[parent_v].count > 2) ||
646                             (vs[parent_v].flag & MVERT_SKIN_ROOT));
647
648         for (i = 0; i < emap[parent_v].count; i++) {
649                 e = emap[parent_v].indices[i];
650
651                 /* Ignore edge if already visited */
652                 if (visited_e[e]) continue;
653                 visited_e[e] = 1;
654
655                 v = BKE_mesh_edge_other_vert(&medge[e], parent_v);
656                 emat[e].origin = parent_v;
657
658                 /* If parent is a branch node, start a new edge chain */
659                 if (parent_is_branch) {
660                         calc_edge_mat(emat[e].mat, mvert[parent_v].co,
661                                       mvert[v].co);
662                 }
663                 else {
664                         /* Build edge matrix guided by parent matrix */
665                         sub_v3_v3v3(emat[e].mat[0], mvert[v].co, mvert[parent_v].co);
666                         normalize_v3(emat[e].mat[0]);
667                         angle = angle_normalized_v3v3(parent_mat[0], emat[e].mat[0]);
668                         cross_v3_v3v3(axis, parent_mat[0], emat[e].mat[0]);
669                         normalize_v3(axis);
670                         rotate_normalized_v3_v3v3fl(emat[e].mat[1], parent_mat[1], axis, angle);
671                         rotate_normalized_v3_v3v3fl(emat[e].mat[2], parent_mat[2], axis, angle);
672                 }
673
674                 build_emats_rec(visited_e, emat, emap, medge,
675                                 vs, mvert, v, emat[e].mat);
676         }
677 }
678
679 static EMat *build_edge_mats(MVertSkin *vs, MVert *mvert, int totvert,
680                              MEdge *medge, MeshElemMap *emap, int totedge)
681 {
682         EMat *emat;
683         float mat[3][3];
684         int *visited_e, v;
685
686         visited_e = MEM_callocN(sizeof(int) * totedge, "build_edge_mats.visited_e");
687         emat = MEM_callocN(sizeof(EMat) * totedge, "build_edge_mats.emat");
688
689         /* Build edge matrices recursively from the root nodes */
690         for (v = 0; v < totvert; v++) {
691                 if (vs[v].flag & MVERT_SKIN_ROOT) {
692                         if (emap[v].count >= 1) {
693                                 const MEdge *e = &medge[emap[v].indices[0]];
694                                 calc_edge_mat(mat, mvert[v].co,
695                                               mvert[BKE_mesh_edge_other_vert(e, v)].co);
696                                 build_emats_rec(visited_e, emat, emap, medge, vs, mvert, v, mat);
697                         }
698                 }
699         }
700
701         MEM_freeN(visited_e);
702
703         return emat;
704 }
705
706
707 /************************** Input Subdivision *************************/
708
709 /* Returns number of edge subdivisions, taking into account the radius
710  * of the endpoints and the edge length. If both endpoints are branch
711  * nodes, at least two intermediate frames are required. (This avoids
712  * having any special cases for dealing with sharing a frame between
713  * two hulls.) */
714 static int calc_edge_subdivisions(const MVert *mvert, const MVertSkin *nodes,
715                                   const MEdge *e, int *degree)
716 {
717         const MVertSkin *evs[2] = {&nodes[e->v1], &nodes[e->v2]};
718         float edge_len, avg[2];
719         int v1_branch = degree[e->v1] > 2;
720         int v2_branch = degree[e->v2] > 2;
721         int num_subdivisions;
722
723         /* If either end is a branch node marked 'loose', don't subdivide
724          * the edge (or subdivide just twice if both are branches) */
725         if ((v1_branch && (evs[0]->flag & MVERT_SKIN_LOOSE)) ||
726             (v2_branch && (evs[1]->flag & MVERT_SKIN_LOOSE)))
727         {
728                 if (v1_branch && v2_branch)
729                         return 2;
730                 else
731                         return 0;
732         }
733
734         edge_len = len_v3v3(mvert[e->v1].co, mvert[e->v2].co);
735
736         avg[0] = half_v2(evs[0]->radius);
737         avg[1] = half_v2(evs[1]->radius);
738         num_subdivisions = (int)((float)edge_len / (avg[0] + avg[1]));
739
740         /* If both ends are branch nodes, two intermediate nodes are
741          * required */
742         if (num_subdivisions < 2 && v1_branch && v2_branch)
743                 num_subdivisions = 2;
744
745         return num_subdivisions;
746 }
747
748 /* Take a DerivedMesh and subdivide its edges to keep skin nodes
749  * reasonably close. */
750 static DerivedMesh *subdivide_base(DerivedMesh *orig)
751 {
752         DerivedMesh *dm;
753         MVertSkin *orignode, *outnode;
754         MVert *origvert, *outvert;
755         MEdge *origedge, *outedge, *e;
756         MDeformVert *origdvert, *outdvert;
757         int totorigvert, totorigedge;
758         int totsubd, *degree, *edge_subd;
759         int i, j, k, u, v;
760         float radrat;
761
762         orignode = CustomData_get_layer(&orig->vertData, CD_MVERT_SKIN);
763         origvert = orig->getVertArray(orig);
764         origedge = orig->getEdgeArray(orig);
765         origdvert = orig->getVertDataArray(orig, CD_MDEFORMVERT);
766         totorigvert = orig->getNumVerts(orig);
767         totorigedge = orig->getNumEdges(orig);
768
769         /* Get degree of all vertices */
770         degree = MEM_callocN(sizeof(int) * totorigvert, "degree");
771         for (i = 0; i < totorigedge; i++) {
772                 degree[origedge[i].v1]++;
773                 degree[origedge[i].v2]++;
774         }
775
776         /* Per edge, store how many subdivisions are needed */
777         edge_subd = MEM_callocN(sizeof(int) * totorigedge, "edge_subd");
778         for (i = 0, totsubd = 0; i < totorigedge; i++) {
779                 edge_subd[i] += calc_edge_subdivisions(origvert, orignode,
780                                                        &origedge[i], degree);
781                 totsubd += edge_subd[i];
782         }
783
784         MEM_freeN(degree);
785
786         /* Allocate output derivedmesh */
787         dm = CDDM_from_template(orig,
788                                 totorigvert + totsubd,
789                                 totorigedge + totsubd,
790                                 0, 0, 0);
791
792         outvert = dm->getVertArray(dm);
793         outedge = dm->getEdgeArray(dm);
794         outnode = CustomData_get_layer(&dm->vertData, CD_MVERT_SKIN);
795         outdvert = CustomData_get_layer(&dm->vertData, CD_MDEFORMVERT);
796
797         /* Copy original vertex data */
798         CustomData_copy_data(&orig->vertData,
799                              &dm->vertData,
800                              0, 0, totorigvert);
801
802         /* Subdivide edges */
803         for (i = 0, v = totorigvert; i < totorigedge; i++) {
804                 struct {
805                         /* Vertex group number */
806                         int def_nr;
807                         float w1, w2;
808                 } *vgroups = NULL, *vg;
809                 int totvgroup = 0;
810
811                 e = &origedge[i];
812
813                 if (origdvert) {
814                         const MDeformVert *dv1 = &origdvert[e->v1];
815                         const MDeformVert *dv2 = &origdvert[e->v2];
816                         vgroups = MEM_callocN(sizeof(*vgroups) * dv1->totweight, "vgroup");
817
818                         /* Only want vertex groups used by both vertices */
819                         for (j = 0; j < dv1->totweight; j++) {
820                                 vg = NULL;
821                                 for (k = 0; k < dv2->totweight; k++) {
822                                         if (dv1->dw[j].def_nr == dv2->dw[k].def_nr) {
823                                                 vg = &vgroups[totvgroup];
824                                                 totvgroup++;
825                                                 break;
826                                         }
827                                 }
828
829                                 if (vg) {
830                                         vg->def_nr = dv1->dw[j].def_nr;
831                                         vg->w1 = dv1->dw[j].weight;
832                                         vg->w1 = dv2->dw[k].weight;
833                                 }
834                         }
835                 }
836
837                 u = e->v1;
838                 radrat = (half_v2(outnode[e->v2].radius) /
839                           half_v2(outnode[e->v1].radius));
840                 radrat = (radrat + 1) / 2;
841
842                 /* Add vertices and edge segments */
843                 for (j = 0; j < edge_subd[i]; j++, v++, outedge++) {
844                         float r = (j + 1) / (float)(edge_subd[i] + 1);
845                         float t = powf(r, radrat);
846
847                         /* Interpolate vertex coord */
848                         interp_v3_v3v3(outvert[v].co, outvert[e->v1].co,
849                                        outvert[e->v2].co, t);
850
851                         /* Interpolate skin radii */
852                         interp_v3_v3v3(outnode[v].radius,
853                                        orignode[e->v1].radius,
854                                        orignode[e->v2].radius, t);
855
856                         /* Interpolate vertex group weights */
857                         for (k = 0; k < totvgroup; k++) {
858                                 float weight;
859                                 
860                                 vg = &vgroups[k];
861                                 weight = interpf(vg->w2, vg->w1, t);
862
863                                 if (weight > 0)
864                                         defvert_add_index_notest(&outdvert[v], vg->def_nr, weight);
865                         }
866                         
867                         outedge->v1 = u;
868                         outedge->v2 = v;
869                         u = v;
870                 }
871
872                 if (vgroups)
873                         MEM_freeN(vgroups);
874                 
875                 /* Link up to final vertex */
876                 outedge->v1 = u;
877                 outedge->v2 = e->v2;
878                 outedge++;
879         }
880
881         MEM_freeN(edge_subd);
882
883         return dm;
884 }
885
886 /******************************* Output *******************************/
887
888 /* Can be either quad or triangle */
889 static void add_poly(SkinOutput *so,
890                      BMVert *v1,
891                      BMVert *v2,
892                      BMVert *v3,
893                      BMVert *v4)
894 {
895         BMVert *verts[4] = {v1, v2, v3, v4};
896         BMEdge *edges[4];
897         BMFace *f;
898         
899         BLI_assert(v1 != v2 && v1 != v3 && v1 != v4);
900         BLI_assert(v2 != v3 && v2 != v4);
901         BLI_assert(v3 != v4);
902         BLI_assert(v1 && v2 && v3);
903
904         edges[0] = BM_edge_create(so->bm, v1, v2, NULL, TRUE);
905         edges[1] = BM_edge_create(so->bm, v2, v3, NULL, TRUE);
906         if (v4) {
907                 edges[2] = BM_edge_create(so->bm, v3, v4, NULL, TRUE);
908                 edges[3] = BM_edge_create(so->bm, v4, v1, NULL, TRUE);
909         }
910         else {
911                 edges[2] = BM_edge_create(so->bm, v3, v1, NULL, TRUE);
912                 edges[3] = NULL;
913         }
914
915         f = BM_face_create(so->bm, verts, edges, v4 ? 4 : 3, TRUE);
916         if (so->smd->flag & MOD_SKIN_SMOOTH_SHADING)
917                 BM_elem_flag_enable(f, BM_ELEM_SMOOTH);
918         f->mat_nr = so->mat_nr;
919 }
920
921 static void connect_frames(SkinOutput *so,
922                            BMVert *frame1[4],
923                            BMVert *frame2[4])
924 {
925         BMVert *q[4][4] = {{frame2[0], frame2[1], frame1[1], frame1[0]},
926                                            {frame2[1], frame2[2], frame1[2], frame1[1]},
927                                            {frame2[2], frame2[3], frame1[3], frame1[2]},
928                                            {frame2[3], frame2[0], frame1[0], frame1[3]}};
929         float p[3], no[3];
930         int i, swap;
931
932         /* Check if frame normals need swap */
933         sub_v3_v3v3(p, q[3][0]->co, q[0][0]->co);
934         normal_quad_v3(no,
935                        q[0][0]->co, q[0][1]->co,
936                        q[0][2]->co, q[0][3]->co);
937         swap = dot_v3v3(no, p) > 0;
938
939         for (i = 0; i < 4; i++) {
940                 if (swap)
941                         add_poly(so, q[i][3], q[i][2], q[i][1], q[i][0]);
942                 else
943                         add_poly(so, q[i][0], q[i][1], q[i][2], q[i][3]);
944         }
945 }
946
947 static void output_frames(BMesh *bm,
948                           SkinNode *sn,
949                           const MDeformVert *input_dvert)
950 {
951         Frame *f;
952         int i, j;
953
954         /* Output all frame verts */
955         for (i = 0; i < sn->totframe; i++) {
956                 f = &sn->frames[i];
957                 for (j = 0; j < 4; j++) {
958                         if (!f->merge[j].frame) {
959                                 BMVert *v = f->verts[j] = BM_vert_create(bm, f->co[j], NULL);
960
961                                 if (input_dvert) {
962                                         MDeformVert *dv;
963                                         dv = CustomData_bmesh_get(&bm->vdata,
964                                                                   v->head.data,
965                                                                   CD_MDEFORMVERT);
966                                         
967                                         BLI_assert(dv->totweight == 0);
968                                         defvert_copy(dv, input_dvert);
969                                 }
970                         }
971                 }
972         }
973 }
974
975 #define PRINT_HOLE_INFO 0
976
977 static void calc_frame_center(float center[3], const Frame *frame)
978 {
979         add_v3_v3v3(center, frame->verts[0]->co, frame->verts[1]->co);
980         add_v3_v3(center, frame->verts[2]->co);
981         add_v3_v3(center, frame->verts[3]->co);
982         mul_v3_fl(center, 0.25f);
983 }
984
985 /* Does crappy fan triangulation of poly, may not be so accurate for
986  * concave faces */
987 static int isect_ray_poly(const float ray_start[3],
988                           const float ray_dir[3],
989                           BMFace *f,
990                           float *r_lambda)
991 {
992         BMVert *v, *v_first = NULL, *v_prev = NULL;
993         BMIter iter;
994         float best_dist = FLT_MAX;
995         int hit = 0;
996         
997         BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
998                 if (!v_first)
999                         v_first = v;
1000                 else if (v_prev != v_first) {
1001                         float dist;
1002                         int curhit;
1003                         
1004                         curhit = isect_ray_tri_v3(ray_start, ray_dir,
1005                                                   v_first->co, v_prev->co, v->co,
1006                                                   &dist, NULL);
1007                         if (curhit && dist < best_dist) {
1008                                 hit = TRUE;
1009                                 best_dist = dist;
1010                         }
1011                 }
1012
1013                 v_prev = v;
1014         }
1015
1016         *r_lambda = best_dist;
1017         return hit;
1018 }
1019
1020 /* Reduce the face down to 'n' corners by collapsing the edges;
1021  * returns the new face.
1022  *
1023  * The orig_verts should contain the vertices of 'f'
1024  */
1025 static BMFace *collapse_face_corners(BMesh *bm, BMFace *f, int n,
1026                                      BMVert **orig_verts)
1027 {
1028         int orig_len = f->len;
1029
1030         BLI_assert(n >= 3);
1031         BLI_assert(f->len > n);
1032         if (f->len <= n)
1033                 return f;
1034
1035         /* Collapse shortest edge for now */
1036         while (f->len > n) {
1037                 BMFace *vf;
1038                 BMEdge *shortest_edge;
1039                 BMVert *v_safe, *v_merge;
1040                 BMOperator op;
1041                 BMIter iter;
1042                 int i;
1043
1044                 shortest_edge = BM_face_find_shortest_loop(f)->e;
1045                 BMO_op_initf(bm, &op, (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE), "weld_verts");
1046
1047                 /* Note: could probably calculate merges in one go to be
1048                  * faster */
1049
1050                 v_safe = shortest_edge->v1;
1051                 v_merge = shortest_edge->v2;
1052                 mid_v3_v3v3(v_safe->co, v_safe->co, v_merge->co);
1053                 BMO_slot_map_ptr_insert(bm, &op, "targetmap", v_merge, v_safe);
1054                 BMO_op_exec(bm, &op);
1055                 BMO_op_finish(bm, &op);
1056
1057                 /* Find the new face */
1058                 f = NULL;
1059                 BM_ITER_ELEM (vf, &iter, v_safe, BM_FACES_OF_VERT) {
1060                         int wrong_face = FALSE;
1061                         
1062                         for (i = 0; i < orig_len; i++) {
1063                                 if (orig_verts[i] == v_merge)
1064                                         orig_verts[i] = NULL;
1065                                 else if (orig_verts[i] &&
1066                                          !BM_vert_in_face(vf, orig_verts[i]))
1067                                 {
1068                                         wrong_face = TRUE;
1069                                         break;
1070                                 }
1071                         }
1072
1073                         if (!wrong_face) {
1074                                 f = vf;
1075                                 break;
1076                         }
1077                 }
1078
1079                 BLI_assert(f);
1080         }
1081
1082         return f;
1083 }
1084
1085 /* Choose a good face to merge the frame with, used in case the frame
1086  * is completely inside the hull. */
1087 static BMFace *skin_hole_target_face(BMesh *bm, Frame *frame)
1088 {
1089         BMFace *f, *isect_target_face, *center_target_face;
1090         BMIter iter;
1091         float frame_center[3];
1092         float frame_normal[3];
1093         float best_isect_dist = FLT_MAX;
1094         float best_center_dist = FLT_MAX;
1095
1096         calc_frame_center(frame_center, frame);
1097         normal_quad_v3(frame_normal, frame->verts[3]->co,
1098                        frame->verts[2]->co, frame->verts[1]->co,
1099                        frame->verts[0]->co);
1100
1101         /* Use a line intersection test and nearest center test against
1102          * all faces */
1103         isect_target_face = center_target_face = NULL;
1104         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
1105                 float dist, poly_center[3];
1106                 int hit;
1107
1108                 /* Intersection test */
1109                 hit = isect_ray_poly(frame_center, frame_normal, f, &dist);
1110                 if (hit && dist < best_isect_dist) {
1111                         isect_target_face = f;
1112                         best_isect_dist = dist;
1113                 }
1114
1115                 /* Nearest test */
1116                 BM_face_calc_center_mean(f, poly_center);
1117                 dist = len_v3v3(frame_center, poly_center);
1118                 if (dist < best_center_dist) {
1119                         center_target_face = f;
1120                         best_center_dist = dist;
1121                 }
1122         }
1123
1124         f = isect_target_face;
1125         if (!f || best_center_dist < best_isect_dist / 2)
1126                 f = center_target_face;
1127
1128         /* This case is unlikely now, but could still happen. Should look
1129          * into splitting edges to make new faces. */
1130 #if PRINT_HOLE_INFO
1131         if (!f) {
1132                 printf("no good face found\n");
1133         }
1134 #endif
1135
1136         return f;
1137 }
1138
1139 /* Use edge-length heuristic to choose from eight possible polygon bridges */
1140 static void skin_choose_quad_bridge_order(BMVert *a[4], BMVert *b[4],
1141                                           int best_order[4])
1142 {
1143         int orders[8][4];
1144         float shortest_len;
1145         int i, j;
1146
1147         /* Enumerate all valid orderings */
1148         for (i = 0; i < 4; i++) {
1149                 for (j = 0; j < 4; j++) {
1150                         orders[i][j] = (j + i) % 4;
1151                         orders[i + 4][j] = 3 - ((j + i) % 4);
1152                 }
1153         }
1154
1155         shortest_len = FLT_MAX;
1156         for (i = 0; i < 8; i++) {
1157                 float len = 0;
1158                 
1159                 /* Get total edge length for this configuration */
1160                 for (j = 0; j < 4; j++)
1161                         len += len_squared_v3v3(a[j]->co, b[orders[i][j]]->co);
1162
1163                 if (len < shortest_len) {
1164                         shortest_len = len;
1165                         memcpy(best_order, orders[i], sizeof(int) * 4);
1166                 }
1167         }
1168 }
1169
1170 static void skin_fix_hole_no_good_verts(BMesh *bm, Frame *frame, BMFace *split_face)
1171 {
1172         BMFace *f;
1173         BMVert *verts[4];
1174         BMVert **vert_buf = NULL;
1175         BLI_array_declare(vert_buf);
1176         BMOIter oiter;
1177         BMOperator op;
1178         int i, best_order[4];
1179
1180         BLI_assert(split_face->len >= 3);
1181
1182         /* Extrude the split face */
1183         BM_mesh_elem_hflag_disable_all(bm, BM_FACE, BM_ELEM_TAG, FALSE);
1184         BM_elem_flag_enable(split_face, BM_ELEM_TAG);
1185         BMO_op_initf(bm, &op, (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE),
1186                      "extrude_discrete_faces faces=%hf", BM_ELEM_TAG);
1187         BMO_op_exec(bm, &op);
1188
1189         /* Update split face (should only be one new face created
1190          * during extrusion) */
1191         split_face = NULL;
1192         BMO_ITER (f, &oiter, bm, &op, "faceout", BM_FACE) {
1193                 BLI_assert(!split_face);
1194                 split_face = f;
1195         }
1196
1197         BMO_op_finish(bm, &op);
1198
1199         if (split_face->len == 3) {
1200                 BMEdge *longest_edge;
1201
1202                 /* Need at least four ring edges, so subdivide longest edge if
1203                  * face is a triangle */
1204                 longest_edge = BM_face_find_longest_loop(split_face)->e;
1205                 
1206                 BM_mesh_elem_hflag_disable_all(bm, BM_EDGE, BM_ELEM_TAG, FALSE);
1207                 BM_elem_flag_enable(longest_edge, BM_ELEM_TAG);
1208
1209                 BMO_op_callf(bm, BMO_FLAG_DEFAULTS,
1210                              "subdivide_edges edges=%he numcuts=%i quadcornertype=%i",
1211                              BM_ELEM_TAG, 1, SUBD_STRAIGHT_CUT);
1212         }
1213         else if (split_face->len > 4) {
1214                 /* Maintain a dynamic vert array containing the split_face's
1215                  * vertices, avoids frequent allocs in collapse_face_corners() */
1216                 if (BLI_array_count(vert_buf) < split_face->len) {
1217                         BLI_array_grow_items(vert_buf, (split_face->len -
1218                                                         BLI_array_count(vert_buf)));
1219                 }
1220
1221                 /* Get split face's verts */
1222                 BM_iter_as_array(bm, BM_VERTS_OF_FACE, split_face,
1223                                  (void **)vert_buf, split_face->len);
1224
1225                 /* Earlier edge split operations may have turned some quads
1226                  * into higher-degree faces */
1227                 split_face = collapse_face_corners(bm, split_face, 4, vert_buf);
1228         }
1229
1230         /* Done with dynamic array, split_face must now be a quad */
1231         BLI_array_free(vert_buf);
1232         BLI_assert(split_face->len == 4);
1233         if (split_face->len != 4)
1234                 return;
1235
1236         /* Get split face's verts */
1237         BM_iter_as_array(bm, BM_VERTS_OF_FACE, split_face, (void **)verts, 4);
1238         skin_choose_quad_bridge_order(verts, frame->verts, best_order);
1239
1240         /* Delete split face and merge */
1241         BM_face_kill(bm, split_face);
1242         BMO_op_init(bm, &op, (BMO_FLAG_DEFAULTS & ~BMO_FLAG_RESPECT_HIDE),
1243                     "weld_verts");
1244         for (i = 0; i < 4; i++) {
1245                 BMO_slot_map_ptr_insert(bm, &op, "targetmap",
1246                                         verts[i], frame->verts[best_order[i]]);
1247         }
1248         BMO_op_exec(bm, &op);
1249         BMO_op_finish(bm, &op);
1250 }
1251
1252 /* If the frame has some vertices that are inside the hull (detached)
1253  * and some attached, duplicate the attached vertices and take the
1254  * whole frame off the hull. */
1255 static void skin_hole_detach_partially_attached_frame(BMesh *bm, Frame *frame)
1256 {
1257         int i, attached[4], totattached = 0;
1258
1259         /* Get/count attached frame corners */
1260         for (i = 0; i < 4; i++) {
1261                 if (!frame->inside_hull[i])
1262                         attached[totattached++] = i;
1263         }
1264
1265         /* Detach everything */
1266         for (i = 0; i < totattached; i++) {
1267                 BMVert **av = &frame->verts[attached[i]];
1268                 (*av) = BM_vert_create(bm, (*av)->co, *av);
1269         }
1270 }
1271
1272
1273 static void quad_from_tris(BMesh *bm, BMEdge *e, BMFace *adj[2], BMVert *ndx[4])
1274 {
1275         BMVert *tri[2][3];
1276         BMVert *opp = NULL;
1277         int i, j;
1278
1279         BLI_assert(adj[0]->len == 3 && adj[1]->len == 3);
1280         
1281         BM_iter_as_array(bm, BM_VERTS_OF_FACE, adj[0], (void **)tri[0], 3);
1282         BM_iter_as_array(bm, BM_VERTS_OF_FACE, adj[1], (void **)tri[1], 3);
1283
1284         /* Find what the second tri has that the first doesn't */
1285         for (i = 0; i < 3; i++) {
1286                 if (tri[1][i] != tri[0][0] &&
1287                     tri[1][i] != tri[0][1] &&
1288                     tri[1][i] != tri[0][2])
1289                 {
1290                         opp = tri[1][i];
1291                         break;
1292                 }
1293         }
1294         BLI_assert(opp);
1295
1296         for (i = 0, j = 0; i < 3; i++, j++) {
1297                 ndx[j] = tri[0][i];
1298                 /* When the triangle edge cuts across our quad-to-be,
1299                  * throw in the second triangle's vertex */
1300                 if ((tri[0][i] == e->v1 || tri[0][i] == e->v2) &&
1301                     (tri[0][(i + 1) % 3] == e->v1 || tri[0][(i + 1) % 3] == e->v2))
1302                 {
1303                         j++;
1304                         ndx[j] = opp;
1305                 }
1306         }
1307 }
1308
1309 static void add_quad_from_tris(SkinOutput *so, BMEdge *e, BMFace *adj[2])
1310 {
1311         BMVert *quad[4];
1312
1313         quad_from_tris(so->bm, e, adj, quad);
1314
1315         add_poly(so, quad[0], quad[1], quad[2], quad[3]);
1316 }
1317
1318 /* Returns the number of faces that are adjacent to both f1 and f2 */
1319 static int BM_face_share_face_count(BMFace *f1, BMFace *f2)
1320 {
1321         BMIter iter1, iter2;
1322         BMEdge *e;
1323         BMFace *f;
1324         int count = 0;
1325
1326         BM_ITER_ELEM (e, &iter1, f1, BM_EDGES_OF_FACE) {
1327                 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
1328                         if (f != f1 && f != f2 && BM_face_share_edge_count(f, f2))
1329                                 count++;
1330                 }
1331         }
1332
1333         return count;
1334 }
1335
1336 static void hull_merge_triangles(SkinOutput *so, const SkinModifierData *smd)
1337 {
1338         BMIter iter;
1339         BMEdge *e;
1340         Heap *heap;
1341         float score;
1342
1343         heap = BLI_heap_new();
1344
1345         BM_mesh_elem_hflag_disable_all(so->bm, BM_FACE, BM_ELEM_TAG, FALSE);
1346
1347         /* Build heap */
1348         BM_ITER_MESH (e, &iter, so->bm, BM_EDGES_OF_MESH) {
1349                 BMFace *adj[2];
1350
1351                 /* Only care if the edge is used by exactly two triangles */
1352                 if (BM_edge_face_pair(e, &adj[0], &adj[1])) {
1353                         if (adj[0]->len == 3 && adj[1]->len == 3) {
1354                                 BMVert *quad[4];
1355
1356                                 /* Construct quad using the two triangles adjacent to
1357                                  * the edge */
1358                                 quad_from_tris(so->bm, e, adj, quad);
1359
1360                                 /* Calculate a score for the quad, higher score for
1361                                  * triangles being closer to coplanar */
1362                                 score = ((BM_face_calc_area(adj[0]) +
1363                                           BM_face_calc_area(adj[1])) *
1364                                          dot_v3v3(adj[0]->no, adj[1]->no));
1365
1366                                 /* Check if quad crosses the axis of symmetry */
1367                                 if (quad_crosses_symmetry_plane(quad, smd)) {
1368                                         /* Increase score if the triangles form a
1369                                          * symmetric quad, otherwise don't use it */
1370                                         if (is_quad_symmetric(quad, smd))
1371                                                 score *= 10;
1372                                         else
1373                                                 continue;
1374                                 }
1375
1376                                 /* Don't use the quad if it's concave */
1377                                 if (!is_quad_convex_v3(quad[0]->co, quad[1]->co,
1378                                                        quad[2]->co, quad[3]->co))
1379                                 {
1380                                         continue;
1381                                 }
1382
1383                                 BLI_heap_insert(heap, -score, e);
1384                         }
1385                 }
1386         }
1387
1388         while (!BLI_heap_empty(heap)) {
1389                 BMFace *adj[2];
1390
1391                 e = BLI_heap_popmin(heap);
1392
1393                 if (BM_edge_face_pair(e, &adj[0], &adj[1])) {
1394                         /* If both triangles still free, and if they don't already
1395                          * share a border with another face, output as a quad */
1396                         if (!BM_elem_flag_test(adj[0], BM_ELEM_TAG) &&
1397                             !BM_elem_flag_test(adj[1], BM_ELEM_TAG) &&
1398                             !BM_face_share_face_count(adj[0], adj[1]))
1399                         {
1400                                 add_quad_from_tris(so, e, adj);
1401                                 BM_elem_flag_enable(adj[0], BM_ELEM_TAG);
1402                                 BM_elem_flag_enable(adj[1], BM_ELEM_TAG);
1403                                 BM_elem_flag_enable(e, BM_ELEM_TAG);
1404                         }
1405                 }
1406         }
1407
1408         BMO_op_callf(so->bm, BMO_FLAG_DEFAULTS,
1409                      "delete geom=%hef context=%i",
1410                      BM_ELEM_TAG, DEL_ONLYTAGGED);
1411
1412         BLI_heap_free(heap, NULL);
1413 }
1414
1415 static void skin_merge_close_frame_verts(SkinNode *skin_nodes, int totvert,
1416                                          const MeshElemMap *emap,
1417                                          const MEdge *medge)
1418 {
1419         Frame **hull_frames;
1420         int v, tothullframe;
1421         
1422         for (v = 0; v < totvert; v++) {
1423                 /* Only check branch nodes */
1424                 if (!skin_nodes[v].totframe) {
1425                         hull_frames = collect_hull_frames(v, skin_nodes,
1426                                                           emap, medge,
1427                                                           &tothullframe);
1428                         merge_frame_corners(hull_frames, tothullframe);
1429                         MEM_freeN(hull_frames);
1430                 }
1431         }
1432 }
1433
1434 static void skin_update_merged_vertices(SkinNode *skin_nodes, int totvert)
1435 {
1436         int v;
1437         
1438         for (v = 0; v < totvert; ++v) {
1439                 SkinNode *sn = &skin_nodes[v];
1440                 int i, j;
1441                 
1442                 for (i = 0; i < sn->totframe; i++) {
1443                         Frame *f = &sn->frames[i];
1444
1445                         for (j = 0; j < 4; j++) {
1446                                 if (f->merge[j].frame) {
1447                                         /* Merge chaining not allowed */
1448                                         BLI_assert(!f->merge[j].frame->merge[f->merge[j].corner].frame);
1449
1450                                         f->verts[j] = f->merge[j].frame->verts[f->merge[j].corner];
1451                                 }
1452                         }
1453                 }
1454         }
1455 }
1456
1457 static void skin_fix_hull_topology(BMesh *bm, SkinNode *skin_nodes,
1458                                    int totvert)
1459 {
1460         int v;
1461         
1462         for (v = 0; v < totvert; v++) {
1463                 SkinNode *sn = &skin_nodes[v];
1464                 int j;
1465                 
1466                 for (j = 0; j < sn->totframe; j++) {
1467                         Frame *f = &sn->frames[j];
1468
1469                         if (f->detached) {
1470                                 BMFace *target_face;
1471                                 
1472                                 skin_hole_detach_partially_attached_frame(bm, f);
1473                                 
1474                                 target_face = skin_hole_target_face(bm, f);
1475                                 if (target_face)
1476                                         skin_fix_hole_no_good_verts(bm, f, target_face);
1477                         }
1478                 }
1479         }
1480 }
1481
1482 static void skin_output_end_nodes(SkinOutput *so, SkinNode *skin_nodes,
1483                                   int totvert)
1484 {
1485         int v;
1486         
1487         for (v = 0; v < totvert; ++v) {
1488                 SkinNode *sn = &skin_nodes[v];
1489                 /* Assuming here just two frames */
1490                 if (sn->flag & SEAM_FRAME) {
1491                         BMVert *v_order[4];
1492                         int i, order[4];
1493                         
1494                         skin_choose_quad_bridge_order(sn->frames[0].verts,
1495                                                       sn->frames[1].verts,
1496                                                       order);
1497                         for (i = 0; i < 4; i++)
1498                                 v_order[i] = sn->frames[1].verts[order[i]];
1499                         connect_frames(so, sn->frames[0].verts, v_order);
1500                 }
1501                 else if (sn->totframe == 2) {
1502                         connect_frames(so,
1503                                        sn->frames[0].verts,
1504                                        sn->frames[1].verts);
1505                 }
1506
1507                 if (sn->flag & CAP_START) {
1508                         if (sn->flag & ROOT) {
1509                                 add_poly(so,
1510                                                  sn->frames[0].verts[0],
1511                                                  sn->frames[0].verts[1],
1512                                                  sn->frames[0].verts[2],
1513                                                  sn->frames[0].verts[3]);
1514                         }
1515                         else {
1516                                 add_poly(so,
1517                                                  sn->frames[0].verts[3],
1518                                                  sn->frames[0].verts[2],
1519                                                  sn->frames[0].verts[1],
1520                                                  sn->frames[0].verts[0]);
1521                         }
1522                 }
1523                 if (sn->flag & CAP_END) {
1524                         add_poly(so,
1525                                  sn->frames[1].verts[0],
1526                                  sn->frames[1].verts[1],
1527                                  sn->frames[1].verts[2],
1528                                  sn->frames[1].verts[3]);
1529                 }
1530         }
1531 }
1532
1533 static void skin_output_connections(SkinOutput *so, SkinNode *skin_nodes,
1534                                     const MEdge *medge,
1535                                     int totedge)
1536 {
1537         int e;
1538         
1539         for (e = 0; e < totedge; e++) {
1540                 SkinNode *a, *b;
1541                 a = &skin_nodes[medge[e].v1];
1542                 b = &skin_nodes[medge[e].v2];
1543
1544                 if (a->totframe && b->totframe) {
1545                         if ((a->flag & SEAM_FRAME) || (b->flag & SEAM_FRAME)) {
1546                                 Frame *fr[2] = {&a->frames[0], &b->frames[0]};
1547                                 BMVert *v_order[4];
1548                                 int i, order[4];
1549
1550                                 if ((a->flag & SEAM_FRAME) && (e != a->seam_edges[0]))
1551                                         fr[0]++;
1552                                 if ((b->flag & SEAM_FRAME) && (e != b->seam_edges[0]))
1553                                         fr[1]++;
1554                         
1555                                 skin_choose_quad_bridge_order(fr[0]->verts, fr[1]->verts, order);
1556                                 for (i = 0; i < 4; i++)
1557                                         v_order[i] = fr[1]->verts[order[i]];
1558                                 connect_frames(so, fr[0]->verts, v_order);
1559                         }
1560                         else {
1561                                 connect_frames(so,
1562                                                a->frames[0].verts,
1563                                                b->frames[0].verts);
1564                         }
1565                 }
1566         }
1567 }
1568
1569 static void skin_smooth_hulls(BMesh *bm, SkinNode *skin_nodes,
1570                               int totvert, const SkinModifierData *smd)
1571 {
1572         BMIter iter, eiter;
1573         BMVert *v;
1574         int i, j, k, skey;
1575
1576         if (smd->branch_smoothing == 0)
1577                 return;
1578
1579         /* Mark all frame vertices */
1580         BM_mesh_elem_hflag_disable_all(bm, BM_VERT, BM_ELEM_TAG, FALSE);
1581         for (i = 0; i < totvert; i++) {
1582                 for (j = 0; j < skin_nodes[i].totframe; j++) {
1583                         Frame *frame = &skin_nodes[i].frames[j];
1584
1585                         for (k = 0; k < 4; k++)
1586                                 BM_elem_flag_enable(frame->verts[k], BM_ELEM_TAG);
1587                 }
1588         }
1589
1590         /* Add temporary shapekey layer to store original coordinates */
1591         BM_data_layer_add(bm, &bm->vdata, CD_SHAPEKEY);
1592         skey = CustomData_number_of_layers(&bm->vdata, CD_SHAPEKEY) - 1;
1593         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1594                 copy_v3_v3(CustomData_bmesh_get_n(&bm->vdata, v->head.data,
1595                                                   CD_SHAPEKEY, skey), v->co);
1596         }
1597
1598         /* Smooth vertices, weight unmarked vertices more strongly (helps
1599          * to smooth frame vertices, but don't want to alter them too
1600          * much) */
1601         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1602                 BMEdge *e;
1603                 float avg[3];
1604                 float weight = smd->branch_smoothing;
1605                 int totv = 1;
1606
1607                 if (BM_elem_flag_test(v, BM_ELEM_TAG))
1608                         weight *= 0.5f;
1609
1610                 copy_v3_v3(avg, v->co);
1611                 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
1612                         BMVert *other = BM_edge_other_vert(e, v);
1613
1614                         add_v3_v3(avg, CustomData_bmesh_get_n(&bm->vdata,
1615                                                               other->head.data,
1616                                                               CD_SHAPEKEY, skey));
1617                         totv++;
1618                 }
1619
1620                 if (totv > 1) {
1621                         mul_v3_fl(avg, 1.0f / (float)totv);
1622                         interp_v3_v3v3(v->co, v->co, avg, weight);
1623                 }
1624         }
1625
1626         /* Done with original coordinates */
1627         BM_data_layer_free_n(bm, &bm->vdata, CD_SHAPEKEY, skey);
1628 }
1629
1630 /* Returns TRUE if all hulls are successfully built, FALSE otherwise */
1631 static int skin_output_branch_hulls(SkinOutput *so, SkinNode *skin_nodes,
1632                                     int totvert, const MeshElemMap *emap,
1633                                     const MEdge *medge)
1634 {
1635         int result = TRUE, v;
1636         
1637         for (v = 0; v < totvert; v++) {
1638                 SkinNode *sn = &skin_nodes[v];
1639                 
1640                 /* Branch node hulls */
1641                 if (!sn->totframe) {
1642                         Frame **hull_frames;
1643                         int tothullframe;
1644                         
1645                         hull_frames = collect_hull_frames(v, skin_nodes,
1646                                                           emap, medge,
1647                                                           &tothullframe);
1648                         if (!build_hull(so, hull_frames, tothullframe))
1649                                 result = FALSE;
1650
1651                         MEM_freeN(hull_frames);
1652                 }
1653         }
1654
1655         return result;
1656 }
1657
1658 static BMesh *build_skin(SkinNode *skin_nodes,
1659                          int totvert, const MeshElemMap *emap,
1660                          const MEdge *medge, int totedge,
1661                          const MDeformVert *input_dvert,
1662                          SkinModifierData *smd)
1663 {
1664         SkinOutput so;
1665         int v;
1666
1667         so.smd = smd;
1668         so.bm = BM_mesh_create(&bm_mesh_allocsize_default);
1669         so.mat_nr = 0;
1670         
1671         if (input_dvert)
1672                 BM_data_layer_add(so.bm, &so.bm->vdata, CD_MDEFORMVERT);
1673
1674         /* Check for mergeable frame corners around hulls before
1675          * outputting vertices */
1676         skin_merge_close_frame_verts(skin_nodes, totvert, emap, medge);
1677
1678         /* Write out all frame vertices to the mesh */
1679         for (v = 0; v < totvert; ++v) {
1680                 if (skin_nodes[v].totframe)
1681                         output_frames(so.bm, &skin_nodes[v],
1682                                       input_dvert ? &input_dvert[v] : NULL);
1683         }
1684
1685         /* Update vertex pointers for merged frame corners */
1686         skin_update_merged_vertices(skin_nodes, totvert);
1687
1688         if (!skin_output_branch_hulls(&so, skin_nodes, totvert, emap, medge))
1689                 modifier_setError(&smd->modifier, "Hull error");
1690
1691         /* Merge triangles here in the hope of providing better target
1692          * faces for skin_fix_hull_topology() to connect to */
1693         hull_merge_triangles(&so, smd);
1694
1695         /* Using convex hulls may not generate a nice manifold mesh. Two
1696          * problems can occur: an input frame's edges may be inside the
1697          * hull, and/or an input frame's vertices may be inside the hull.
1698          *
1699          * General fix to produce manifold mesh: for any frame that is
1700          * partially detached, first detach it fully, then find a suitable
1701          * existing face to merge with. (Note that we do this after
1702          * creating all hull faces, but before creating any other
1703          * faces.
1704          */
1705         skin_fix_hull_topology(so.bm, skin_nodes, totvert);
1706
1707         skin_smooth_hulls(so.bm, skin_nodes, totvert, smd);
1708
1709         skin_output_end_nodes(&so, skin_nodes, totvert);
1710         skin_output_connections(&so, skin_nodes, medge, totedge);
1711         hull_merge_triangles(&so, smd);
1712
1713         return so.bm;
1714 }
1715
1716 static void skin_set_orig_indices(DerivedMesh *dm)
1717 {
1718         int *orig, totpoly, i;
1719
1720         totpoly = dm->getNumPolys(dm);
1721         orig = CustomData_add_layer(&dm->polyData, CD_ORIGINDEX,
1722                                     CD_CALLOC, 0, totpoly);
1723         for (i = 0; i < totpoly; i++)
1724                 orig[i] = ORIGINDEX_NONE;
1725 }
1726
1727 /*
1728  * 0) Subdivide edges (in caller)
1729  * 1) Generate good edge matrices (uses root nodes)
1730  * 2) Generate node frames
1731  * 3) Output vertices and polygons from frames, connections, and hulls
1732  */
1733 static DerivedMesh *base_skin(DerivedMesh *origdm,
1734                               SkinModifierData *smd)
1735 {
1736         BMEditMesh fake_em;
1737         DerivedMesh *result;
1738         MVertSkin *nodes;
1739         BMesh *bm;
1740         EMat *emat;
1741         SkinNode *skin_nodes;
1742         MeshElemMap *emap;
1743         int *emapmem;
1744         MVert *mvert;
1745         MEdge *medge;
1746         MDeformVert *dvert;
1747         int totvert, totedge;
1748
1749         nodes = CustomData_get_layer(&origdm->vertData, CD_MVERT_SKIN);
1750
1751         mvert = origdm->getVertArray(origdm);
1752         dvert = origdm->getVertDataArray(origdm, CD_MDEFORMVERT);
1753         medge = origdm->getEdgeArray(origdm);
1754         totvert = origdm->getNumVerts(origdm);
1755         totedge = origdm->getNumEdges(origdm);
1756
1757         create_vert_edge_map(&emap, &emapmem, medge, totvert, totedge);
1758
1759         emat = build_edge_mats(nodes, mvert, totvert, medge, emap, totedge);
1760         skin_nodes = build_frames(mvert, totvert, nodes, emap, emat);
1761         MEM_freeN(emat);
1762         emat = NULL;
1763
1764         bm = build_skin(skin_nodes, totvert, emap, medge, totedge, dvert, smd);
1765
1766         MEM_freeN(skin_nodes);
1767         MEM_freeN(emap);
1768         MEM_freeN(emapmem);
1769
1770         if (!bm)
1771                 return NULL;
1772         
1773         fake_em.bm = bm;
1774         result = CDDM_from_BMEditMesh(&fake_em, NULL, FALSE, FALSE);
1775         BM_mesh_free(bm);
1776
1777         CDDM_calc_edges(result);
1778         CDDM_calc_normals(result);
1779
1780         skin_set_orig_indices(result);
1781
1782         return result;
1783 }
1784
1785 static DerivedMesh *final_skin(SkinModifierData *smd,
1786                                DerivedMesh *origdm)
1787 {
1788         DerivedMesh *dm;
1789
1790         /* Skin node layer is required */
1791         if (!CustomData_get_layer(&origdm->vertData, CD_MVERT_SKIN))
1792                 return origdm;
1793
1794         origdm = subdivide_base(origdm);
1795         dm = base_skin(origdm, smd);
1796
1797         origdm->release(origdm);
1798
1799         return dm;
1800 }
1801
1802
1803 /**************************** Skin Modifier ***************************/
1804
1805 static void initData(ModifierData *md)
1806 {
1807         SkinModifierData *smd = (SkinModifierData *) md;
1808         
1809         /* Enable in editmode by default */
1810         md->mode |= eModifierMode_Editmode;
1811
1812         smd->branch_smoothing = 0;
1813         smd->flag = 0;
1814         smd->symmetry_axes = MOD_SKIN_SYMM_X;
1815 }
1816
1817 static void copyData(ModifierData *md, ModifierData *target)
1818 {
1819         SkinModifierData *smd = (SkinModifierData *) md;
1820         SkinModifierData *tsmd = (SkinModifierData *) target;
1821
1822         *tsmd = *smd;
1823 }
1824
1825 static DerivedMesh *applyModifierEM(ModifierData *md,
1826                                     Object *UNUSED(ob),
1827                                     BMEditMesh *UNUSED(em),
1828                                     DerivedMesh *dm)
1829 {
1830         DerivedMesh *result;
1831
1832         if (!(result = final_skin((SkinModifierData *)md, dm)))
1833                 return dm;
1834         return result;
1835 }
1836
1837 static DerivedMesh *applyModifier(ModifierData *md,
1838                                   Object *UNUSED(ob),
1839                                   DerivedMesh *dm,
1840                                   ModifierApplyFlag UNUSED(flag))
1841 {
1842         DerivedMesh *result;
1843
1844         if (!(result = final_skin((SkinModifierData *)md, dm)))
1845                 return dm;
1846         return result;
1847 }
1848
1849 static CustomDataMask requiredDataMask(Object *UNUSED(ob),
1850                                        ModifierData *UNUSED(md))
1851 {
1852         return CD_MASK_MVERT_SKIN | CD_MASK_MDEFORMVERT;
1853 }
1854
1855 ModifierTypeInfo modifierType_Skin = {
1856         /* name */              "Skin",
1857         /* structName */        "SkinModifierData",
1858         /* structSize */        sizeof(SkinModifierData),
1859         /* type */              eModifierTypeType_Constructive,
1860         /* flags */             eModifierTypeFlag_AcceptsMesh | eModifierTypeFlag_SupportsEditmode,
1861
1862         /* copyData */          copyData,
1863         /* deformVerts */       NULL,
1864         /* deformMatrices */    NULL,
1865         /* deformVertsEM */     NULL,
1866         /* deformMatricesEM */  NULL,
1867         /* applyModifier */     applyModifier,
1868         /* applyModifierEM */   applyModifierEM,
1869         /* initData */          initData,
1870         /* requiredDataMask */  requiredDataMask,
1871         /* freeData */          NULL,
1872         /* isDisabled */        NULL,
1873         /* updateDepgraph */    NULL,
1874         /* dependsOnTime */     NULL,
1875         /* dependsOnNormals */  NULL,
1876         /* foreachObjectLink */ NULL,
1877         /* foreachIDLink */     NULL,
1878 };