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