migrated NDOF code from soc-2010-merwin, SpaceNavigator now works on Mac blender
[blender.git] / source / blender / modifiers / intern / MOD_edgesplit.c
1 /*
2 * $Id$
3 *
4 * ***** BEGIN GPL LICENSE BLOCK *****
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software  Foundation,
18 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 *
20 * The Original Code is Copyright (C) 2005 by the Blender Foundation.
21 * All rights reserved.
22 *
23 * Contributor(s): Daniel Dunbar
24 *                 Ton Roosendaal,
25 *                 Ben Batt,
26 *                 Brecht Van Lommel,
27 *                 Campbell Barton
28 *
29 * ***** END GPL LICENSE BLOCK *****
30 *
31 */
32
33 /** \file blender/modifiers/intern/MOD_edgesplit.c
34  *  \ingroup modifiers
35  */
36
37
38 /* EdgeSplit modifier: Splits edges in the mesh according to sharpness flag
39  * or edge angle (can be used to achieve autosmoothing) */
40
41 #include <assert.h>
42
43 #include "DNA_meshdata_types.h"
44
45 #include "BLI_listbase.h"
46 #include "BLI_memarena.h"
47 #include "BLI_edgehash.h"
48 #include "BLI_math.h"
49 #include "BLI_utildefines.h"
50
51
52 #include "BKE_cdderivedmesh.h"
53 #include "BKE_modifier.h"
54 #include "BKE_particle.h"
55
56 #include "MEM_guardedalloc.h"
57
58 #include "MOD_util.h"
59
60 #if 0
61 #define EDGESPLIT_DEBUG_3
62 #define EDGESPLIT_DEBUG_2
63 #define EDGESPLIT_DEBUG_1
64 #define EDGESPLIT_DEBUG_0
65 #endif
66
67 static void initData(ModifierData *md)
68 {
69         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
70
71         /* default to 30-degree split angle, sharpness from both angle & flag
72         */
73         emd->split_angle = 30;
74         emd->flags = MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG;
75 }
76
77 static void copyData(ModifierData *md, ModifierData *target)
78 {
79         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
80         EdgeSplitModifierData *temd = (EdgeSplitModifierData*) target;
81
82         temd->split_angle = emd->split_angle;
83         temd->flags = emd->flags;
84 }
85
86 /* Mesh data for edgesplit operation */
87 typedef struct SmoothVert {
88         LinkNode *faces;     /* all faces which use this vert */
89         int oldIndex; /* the index of the original DerivedMesh vert */
90         int newIndex; /* the index of the new DerivedMesh vert */
91 } SmoothVert;
92
93 #define SMOOTHEDGE_NUM_VERTS 2
94
95 typedef struct SmoothEdge {
96         SmoothVert *verts[SMOOTHEDGE_NUM_VERTS]; /* the verts used by this edge */
97         LinkNode *faces;     /* all faces which use this edge */
98         int oldIndex; /* the index of the original DerivedMesh edge */
99         int newIndex; /* the index of the new DerivedMesh edge */
100         short flag; /* the flags from the original DerivedMesh edge */
101 } SmoothEdge;
102
103 #define SMOOTHFACE_MAX_EDGES 4
104
105 typedef struct SmoothFace {
106         SmoothEdge *edges[SMOOTHFACE_MAX_EDGES]; /* nonexistent edges == NULL */
107         int flip[SMOOTHFACE_MAX_EDGES]; /* 1 = flip edge dir, 0 = don't flip */
108         float normal[3]; /* the normal of this face */
109         int oldIndex; /* the index of the original DerivedMesh face */
110         int newIndex; /* the index of the new DerivedMesh face */
111 } SmoothFace;
112
113 typedef struct SmoothMesh {
114         SmoothVert *verts;
115         SmoothEdge *edges;
116         SmoothFace *faces;
117         int num_verts, num_edges, num_faces;
118         int max_verts, max_edges, max_faces;
119         DerivedMesh *dm;
120         float threshold; /* the cosine of the smoothing angle */
121         int flags;
122         MemArena *arena;
123         ListBase propagatestack, reusestack;
124 } SmoothMesh;
125
126 static SmoothVert *smoothvert_copy(SmoothVert *vert, SmoothMesh *mesh)
127 {
128         SmoothVert *copy = &mesh->verts[mesh->num_verts];
129
130         assert(vert != NULL);
131
132         if(mesh->num_verts >= mesh->max_verts) {
133                 printf("Attempted to add a SmoothMesh vert beyond end of array\n");
134                 return NULL;
135         }
136
137         *copy = *vert;
138         copy->faces = NULL;
139         copy->newIndex = mesh->num_verts;
140         ++mesh->num_verts;
141
142 #ifdef EDGESPLIT_DEBUG_2
143         printf("copied vert %4d to vert %4d\n", vert->newIndex, copy->newIndex);
144 #endif
145         return copy;
146 }
147
148 static SmoothEdge *smoothedge_copy(SmoothEdge *edge, SmoothMesh *mesh)
149 {
150         SmoothEdge *copy = &mesh->edges[mesh->num_edges];
151
152         if(mesh->num_edges >= mesh->max_edges) {
153                 printf("Attempted to add a SmoothMesh edge beyond end of array\n");
154                 return NULL;
155         }
156
157         *copy = *edge;
158         copy->faces = NULL;
159         copy->newIndex = mesh->num_edges;
160         ++mesh->num_edges;
161
162 #ifdef EDGESPLIT_DEBUG_2
163         printf("copied edge %4d to edge %4d\n", edge->newIndex, copy->newIndex);
164 #endif
165         return copy;
166 }
167
168 static int smoothedge_has_vert(SmoothEdge *edge, SmoothVert *vert)
169 {
170         int i;
171         for(i = 0; i < SMOOTHEDGE_NUM_VERTS; i++)
172                 if(edge->verts[i] == vert) return 1;
173
174         return 0;
175 }
176
177 static SmoothMesh *smoothmesh_new(int num_verts, int num_edges, int num_faces,
178                                   int max_verts, int max_edges, int max_faces)
179 {
180         SmoothMesh *mesh = MEM_callocN(sizeof(*mesh), "smoothmesh");
181         mesh->verts = MEM_callocN(sizeof(*mesh->verts) * max_verts,
182                         "SmoothMesh.verts");
183         mesh->edges = MEM_callocN(sizeof(*mesh->edges) * max_edges,
184                         "SmoothMesh.edges");
185         mesh->faces = MEM_callocN(sizeof(*mesh->faces) * max_faces,
186                         "SmoothMesh.faces");
187
188         mesh->num_verts = num_verts;
189         mesh->num_edges = num_edges;
190         mesh->num_faces = num_faces;
191
192         mesh->max_verts = max_verts;
193         mesh->max_edges = max_edges;
194         mesh->max_faces = max_faces;
195
196         return mesh;
197 }
198
199 static void smoothmesh_free(SmoothMesh *mesh)
200 {
201         int i;
202
203         for(i = 0; i < mesh->num_verts; ++i)
204                 BLI_linklist_free(mesh->verts[i].faces, NULL);
205
206         for(i = 0; i < mesh->num_edges; ++i)
207                 BLI_linklist_free(mesh->edges[i].faces, NULL);
208         
209         if(mesh->arena)
210                 BLI_memarena_free(mesh->arena);
211
212         MEM_freeN(mesh->verts);
213         MEM_freeN(mesh->edges);
214         MEM_freeN(mesh->faces);
215         MEM_freeN(mesh);
216 }
217
218 static void smoothmesh_resize_verts(SmoothMesh *mesh, int max_verts)
219 {
220         int i;
221         SmoothVert *tmp;
222
223         if(max_verts <= mesh->max_verts) return;
224
225         tmp = MEM_callocN(sizeof(*tmp) * max_verts, "SmoothMesh.verts");
226
227         memcpy(tmp, mesh->verts, sizeof(*tmp) * mesh->num_verts);
228
229         /* remap vert pointers in edges */
230         for(i = 0; i < mesh->num_edges; ++i) {
231                 int j;
232                 SmoothEdge *edge = &mesh->edges[i];
233
234                 for(j = 0; j < SMOOTHEDGE_NUM_VERTS; ++j)
235                         /* pointer arithmetic to get vert array index */
236                         edge->verts[j] = &tmp[edge->verts[j] - mesh->verts];
237         }
238
239         MEM_freeN(mesh->verts);
240         mesh->verts = tmp;
241         mesh->max_verts = max_verts;
242 }
243
244 static void smoothmesh_resize_edges(SmoothMesh *mesh, int max_edges)
245 {
246         int i;
247         SmoothEdge *tmp;
248
249         if(max_edges <= mesh->max_edges) return;
250
251         tmp = MEM_callocN(sizeof(*tmp) * max_edges, "SmoothMesh.edges");
252
253         memcpy(tmp, mesh->edges, sizeof(*tmp) * mesh->num_edges);
254
255         /* remap edge pointers in faces */
256         for(i = 0; i < mesh->num_faces; ++i) {
257                 int j;
258                 SmoothFace *face = &mesh->faces[i];
259
260                 for(j = 0; j < SMOOTHFACE_MAX_EDGES; ++j)
261                         if(face->edges[j])
262                                 /* pointer arithmetic to get edge array index */
263                                 face->edges[j] = &tmp[face->edges[j] - mesh->edges];
264         }
265
266         MEM_freeN(mesh->edges);
267         mesh->edges = tmp;
268         mesh->max_edges = max_edges;
269 }
270
271 #ifdef EDGESPLIT_DEBUG_0
272 static void smoothmesh_print(SmoothMesh *mesh)
273 {
274         int i, j;
275         DerivedMesh *dm = mesh->dm;
276
277         printf("--- SmoothMesh ---\n");
278         printf("--- Vertices ---\n");
279         for(i = 0; i < mesh->num_verts; i++) {
280                 SmoothVert *vert = &mesh->verts[i];
281                 LinkNode *node;
282                 MVert mv;
283
284                 dm->getVert(dm, vert->oldIndex, &mv);
285
286                 printf("%3d: ind={%3d, %3d}, pos={% 5.1f, % 5.1f, % 5.1f}",
287                         i, vert->oldIndex, vert->newIndex,
288                         mv.co[0], mv.co[1], mv.co[2]);
289                 printf(", faces={");
290                 for(node = vert->faces; node != NULL; node = node->next) {
291                         printf(" %d", ((SmoothFace *)node->link)->newIndex);
292                 }
293                 printf("}\n");
294         }
295
296         printf("\n--- Edges ---\n");
297         for(i = 0; i < mesh->num_edges; i++) {
298                 SmoothEdge *edge = &mesh->edges[i];
299                 LinkNode *node;
300
301                 printf("%4d: indices={%4d, %4d}, verts={%4d, %4d}",
302                         i,
303                         edge->oldIndex, edge->newIndex,
304                         edge->verts[0]->newIndex, edge->verts[1]->newIndex);
305                 if(edge->verts[0] == edge->verts[1]) printf(" <- DUPLICATE VERTEX");
306                 printf(", faces={");
307                 for(node = edge->faces; node != NULL; node = node->next) {
308                         printf(" %d", ((SmoothFace *)node->link)->newIndex);
309                 }
310                 printf("}\n");
311         }
312
313         printf("\n--- Faces ---\n");
314         for(i = 0; i < mesh->num_faces; i++) {
315                 SmoothFace *face = &mesh->faces[i];
316
317                 printf("%4d: indices={%4d, %4d}, edges={", i,
318                         face->oldIndex, face->newIndex);
319                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
320                         if(face->flip[j])
321                                 printf(" -%-2d", face->edges[j]->newIndex);
322                         else
323                                 printf("  %-2d", face->edges[j]->newIndex);
324                 }
325                 printf("}, verts={");
326                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
327                         printf(" %d", face->edges[j]->verts[face->flip[j]]->newIndex);
328                 }
329                 printf("}\n");
330         }
331 }
332 #endif
333
334 static SmoothMesh *smoothmesh_from_derivedmesh(DerivedMesh *dm)
335 {
336         SmoothMesh *mesh;
337         EdgeHash *edges = BLI_edgehash_new();
338         int i;
339         int totvert, totedge, totface;
340
341         totvert = dm->getNumVerts(dm);
342         totedge = dm->getNumEdges(dm);
343         totface = dm->getNumFaces(dm);
344
345         mesh = smoothmesh_new(totvert, totedge, totface,
346                         totvert, totedge, totface);
347
348         mesh->dm = dm;
349
350         for(i = 0; i < totvert; i++) {
351                 SmoothVert *vert = &mesh->verts[i];
352
353                 vert->oldIndex = vert->newIndex = i;
354         }
355
356         for(i = 0; i < totedge; i++) {
357                 SmoothEdge *edge = &mesh->edges[i];
358                 MEdge med;
359
360                 dm->getEdge(dm, i, &med);
361                 edge->verts[0] = &mesh->verts[med.v1];
362                 edge->verts[1] = &mesh->verts[med.v2];
363                 edge->oldIndex = edge->newIndex = i;
364                 edge->flag = med.flag;
365
366                 BLI_edgehash_insert(edges, med.v1, med.v2, edge);
367         }
368
369         for(i = 0; i < totface; i++) {
370                 SmoothFace *face = &mesh->faces[i];
371                 MFace mf;
372                 MVert v1, v2, v3;
373                 int j;
374
375                 dm->getFace(dm, i, &mf);
376
377                 dm->getVert(dm, mf.v1, &v1);
378                 dm->getVert(dm, mf.v2, &v2);
379                 dm->getVert(dm, mf.v3, &v3);
380                 face->edges[0] = BLI_edgehash_lookup(edges, mf.v1, mf.v2);
381                 if(face->edges[0]->verts[1]->oldIndex == mf.v1) face->flip[0] = 1;
382                 face->edges[1] = BLI_edgehash_lookup(edges, mf.v2, mf.v3);
383                 if(face->edges[1]->verts[1]->oldIndex == mf.v2) face->flip[1] = 1;
384                 if(mf.v4) {
385                         MVert v4;
386                         dm->getVert(dm, mf.v4, &v4);
387                         face->edges[2] = BLI_edgehash_lookup(edges, mf.v3, mf.v4);
388                         if(face->edges[2]->verts[1]->oldIndex == mf.v3) face->flip[2] = 1;
389                         face->edges[3] = BLI_edgehash_lookup(edges, mf.v4, mf.v1);
390                         if(face->edges[3]->verts[1]->oldIndex == mf.v4) face->flip[3] = 1;
391                         normal_quad_v3( face->normal,v1.co, v2.co, v3.co, v4.co);
392                 } else {
393                         face->edges[2] = BLI_edgehash_lookup(edges, mf.v3, mf.v1);
394                         if(face->edges[2]->verts[1]->oldIndex == mf.v3) face->flip[2] = 1;
395                         face->edges[3] = NULL;
396                         normal_tri_v3( face->normal,v1.co, v2.co, v3.co);
397                 }
398
399                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
400                         SmoothEdge *edge = face->edges[j];
401                         BLI_linklist_prepend(&edge->faces, face);
402                         BLI_linklist_prepend(&edge->verts[face->flip[j]]->faces, face);
403                 }
404
405                 face->oldIndex = face->newIndex = i;
406         }
407
408         BLI_edgehash_free(edges, NULL);
409
410         return mesh;
411 }
412
413 static DerivedMesh *CDDM_from_smoothmesh(SmoothMesh *mesh)
414 {
415         DerivedMesh *result = CDDM_from_template(mesh->dm,
416                         mesh->num_verts,
417                         mesh->num_edges,
418                         mesh->num_faces);
419         MVert *new_verts = CDDM_get_verts(result);
420         MEdge *new_edges = CDDM_get_edges(result);
421         MFace *new_faces = CDDM_get_faces(result);
422         int i;
423
424         for(i = 0; i < mesh->num_verts; ++i) {
425                 SmoothVert *vert = &mesh->verts[i];
426                 MVert *newMV = &new_verts[vert->newIndex];
427
428                 DM_copy_vert_data(mesh->dm, result,
429                                 vert->oldIndex, vert->newIndex, 1);
430                 mesh->dm->getVert(mesh->dm, vert->oldIndex, newMV);
431         }
432
433         for(i = 0; i < mesh->num_edges; ++i) {
434                 SmoothEdge *edge = &mesh->edges[i];
435                 MEdge *newME = &new_edges[edge->newIndex];
436
437                 DM_copy_edge_data(mesh->dm, result,
438                                 edge->oldIndex, edge->newIndex, 1);
439                 mesh->dm->getEdge(mesh->dm, edge->oldIndex, newME);
440                 newME->v1 = edge->verts[0]->newIndex;
441                 newME->v2 = edge->verts[1]->newIndex;
442         }
443
444         for(i = 0; i < mesh->num_faces; ++i) {
445                 SmoothFace *face = &mesh->faces[i];
446                 MFace *newMF = &new_faces[face->newIndex];
447
448                 DM_copy_face_data(mesh->dm, result,
449                                 face->oldIndex, face->newIndex, 1);
450                 mesh->dm->getFace(mesh->dm, face->oldIndex, newMF);
451
452                 newMF->v1 = face->edges[0]->verts[face->flip[0]]->newIndex;
453                 newMF->v2 = face->edges[1]->verts[face->flip[1]]->newIndex;
454                 newMF->v3 = face->edges[2]->verts[face->flip[2]]->newIndex;
455
456                 if(face->edges[3]) {
457                         newMF->v4 = face->edges[3]->verts[face->flip[3]]->newIndex;
458                 } else {
459                         newMF->v4 = 0;
460                 }
461         }
462
463         return result;
464 }
465
466 /* returns the other vert in the given edge
467  */
468 static SmoothVert *other_vert(SmoothEdge *edge, SmoothVert *vert)
469 {
470         if(edge->verts[0] == vert) return edge->verts[1];
471         else return edge->verts[0];
472 }
473
474 /* returns the other edge in the given face that uses the given vert
475  * returns NULL if no other edge in the given face uses the given vert
476  * (this should never happen)
477  */
478 static SmoothEdge *other_edge(SmoothFace *face, SmoothVert *vert,
479                                   SmoothEdge *edge)
480 {
481         int i,j;
482         for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++) {
483                 SmoothEdge *tmp_edge = face->edges[i];
484                 if(tmp_edge == edge) continue;
485
486                 for(j = 0; j < SMOOTHEDGE_NUM_VERTS; j++)
487                         if(tmp_edge->verts[j] == vert) return tmp_edge;
488         }
489
490         /* if we get to here, something's wrong (there should always be 2 edges
491         * which use the same vert in a face)
492         */
493         return NULL;
494 }
495
496 /* returns a face attached to the given edge which is not the given face.
497  * returns NULL if no other faces use this edge.
498  */
499 static SmoothFace *other_face(SmoothEdge *edge, SmoothFace *face)
500 {
501         LinkNode *node;
502
503         for(node = edge->faces; node != NULL; node = node->next)
504                 if(node->link != face) return node->link;
505
506         return NULL;
507 }
508
509 #if 0
510 /* copies source list to target, overwriting target (target is not freed)
511  * nodes in the copy will be in the same order as in source
512  */
513 static void linklist_copy(LinkNode **target, LinkNode *source)
514 {
515         LinkNode *node = NULL;
516         *target = NULL;
517
518         for(; source; source = source->next) {
519                 if(node) {
520                         node->next = MEM_mallocN(sizeof(*node->next), "nlink_copy");
521                         node = node->next;
522                 } else {
523                         node = *target = MEM_mallocN(sizeof(**target), "nlink_copy");
524                 }
525                 node->link = source->link;
526                 node->next = NULL;
527         }
528 }
529 #endif
530
531 /* appends source to target if it's not already in target */
532 static void linklist_append_unique(LinkNode **target, void *source)
533 {
534         LinkNode *node;
535         LinkNode *prev = NULL;
536
537         /* check if source value is already in the list */
538         for(node = *target; node; prev = node, node = node->next)
539                 if(node->link == source) return;
540
541         node = MEM_mallocN(sizeof(*node), "nlink");
542         node->next = NULL;
543         node->link = source;
544
545         if(prev) prev->next = node;
546         else *target = node;
547 }
548
549 /* appends elements of source which aren't already in target to target */
550 static void linklist_append_list_unique(LinkNode **target, LinkNode *source)
551 {
552         for(; source; source = source->next)
553                 linklist_append_unique(target, source->link);
554 }
555
556 #if 0 /* this is no longer used, it should possibly be removed */
557 /* prepends prepend to list - doesn't copy nodes, just joins the lists */
558 static void linklist_prepend_linklist(LinkNode **list, LinkNode *prepend)
559 {
560         if(prepend) {
561                 LinkNode *node = prepend;
562                 while(node->next) node = node->next;
563
564                 node->next = *list;
565                 *list = prepend;
566         }
567 }
568 #endif
569
570 /* returns 1 if the linked list contains the given pointer, 0 otherwise
571  */
572 static int linklist_contains(LinkNode *list, void *ptr)
573 {
574         LinkNode *node;
575
576         for(node = list; node; node = node->next)
577                 if(node->link == ptr) return 1;
578
579         return 0;
580 }
581
582 /* returns 1 if the first linked list is a subset of the second (comparing
583  * pointer values), 0 if not
584  */
585 static int linklist_subset(LinkNode *list1, LinkNode *list2)
586 {
587         for(; list1; list1 = list1->next)
588                 if(!linklist_contains(list2, list1->link))
589                         return 0;
590
591         return 1;
592 }
593
594 #if 0
595 /* empties the linked list
596  * frees pointers with freefunc if freefunc is not NULL
597  */
598 static void linklist_empty(LinkNode **list, LinkNodeFreeFP freefunc)
599 {
600         BLI_linklist_free(*list, freefunc);
601         *list = NULL;
602 }
603 #endif
604
605 /* removes the first instance of value from the linked list
606  * frees the pointer with freefunc if freefunc is not NULL
607  */
608 static void linklist_remove_first(LinkNode **list, void *value,
609                                   LinkNodeFreeFP freefunc)
610 {
611         LinkNode *node = *list;
612         LinkNode *prev = NULL;
613
614         while(node && node->link != value) {
615                 prev = node;
616                 node = node->next;
617         }
618
619         if(node) {
620                 if(prev)
621                         prev->next = node->next;
622                 else
623                         *list = node->next;
624
625                 if(freefunc)
626                         freefunc(node->link);
627
628                 MEM_freeN(node);
629         }
630 }
631
632 /* removes all elements in source from target */
633 static void linklist_remove_list(LinkNode **target, LinkNode *source,
634                                  LinkNodeFreeFP freefunc)
635 {
636         for(; source; source = source->next)
637                 linklist_remove_first(target, source->link, freefunc);
638 }
639
640 #ifdef EDGESPLIT_DEBUG_0
641 static void print_ptr(void *ptr)
642 {
643         printf("%p\n", ptr);
644 }
645
646 static void print_edge(void *ptr)
647 {
648         SmoothEdge *edge = ptr;
649         printf(" %4d", edge->newIndex);
650 }
651
652 static void print_face(void *ptr)
653 {
654         SmoothFace *face = ptr;
655         printf(" %4d", face->newIndex);
656 }
657 #endif
658
659 typedef struct ReplaceData {
660         void *find;
661         void *replace;
662 } ReplaceData;
663
664 static void edge_replace_vert(void *ptr, void *userdata)
665 {
666         SmoothEdge *edge = ptr;
667         SmoothVert *find = ((ReplaceData *)userdata)->find;
668         SmoothVert *replace = ((ReplaceData *)userdata)->replace;
669         int i;
670
671 #ifdef EDGESPLIT_DEBUG_3
672         printf("replacing vert %4d with %4d in edge %4d",
673                 find->newIndex, replace->newIndex, edge->newIndex);
674         printf(": {%4d, %4d}", edge->verts[0]->newIndex, edge->verts[1]->newIndex);
675 #endif
676
677         for(i = 0; i < SMOOTHEDGE_NUM_VERTS; i++) {
678                 if(edge->verts[i] == find) {
679                         linklist_append_list_unique(&replace->faces, edge->faces);
680                         linklist_remove_list(&find->faces, edge->faces, NULL);
681
682                         edge->verts[i] = replace;
683                 }
684         }
685
686 #ifdef EDGESPLIT_DEBUG_3
687         printf(" -> {%4d, %4d}\n", edge->verts[0]->newIndex, edge->verts[1]->newIndex);
688 #endif
689 }
690
691 static void face_replace_vert(void *ptr, void *userdata)
692 {
693         SmoothFace *face = ptr;
694         int i;
695
696         for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++)
697                 edge_replace_vert(face->edges[i], userdata);
698 }
699
700 static void face_replace_edge(void *ptr, void *userdata)
701 {
702         SmoothFace *face = ptr;
703         SmoothEdge *find = ((ReplaceData *)userdata)->find;
704         SmoothEdge *replace = ((ReplaceData *)userdata)->replace;
705         int i;
706
707 #ifdef EDGESPLIT_DEBUG_3
708         printf("replacing edge %4d with %4d in face %4d",
709                 find->newIndex, replace->newIndex, face->newIndex);
710         if(face->edges[3])
711                 printf(": {%2d %2d %2d %2d}",
712                         face->edges[0]->newIndex, face->edges[1]->newIndex,
713                         face->edges[2]->newIndex, face->edges[3]->newIndex);
714         else
715                 printf(": {%2d %2d %2d}",
716                         face->edges[0]->newIndex, face->edges[1]->newIndex,
717                         face->edges[2]->newIndex);
718 #endif
719
720         for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++) {
721                 if(face->edges[i] == find) {
722                         linklist_remove_first(&face->edges[i]->faces, face, NULL);
723                         BLI_linklist_prepend(&replace->faces, face);
724                         face->edges[i] = replace;
725                 }
726         }
727
728 #ifdef EDGESPLIT_DEBUG_3
729         if(face->edges[3])
730                 printf(" -> {%2d %2d %2d %2d}\n",
731                         face->edges[0]->newIndex, face->edges[1]->newIndex,
732                         face->edges[2]->newIndex, face->edges[3]->newIndex);
733         else
734                 printf(" -> {%2d %2d %2d}\n",
735                         face->edges[0]->newIndex, face->edges[1]->newIndex,
736                         face->edges[2]->newIndex);
737 #endif
738 }
739
740 static int edge_is_loose(SmoothEdge *edge)
741 {
742         return !(edge->faces && edge->faces->next);
743 }
744
745 static int edge_is_sharp(SmoothEdge *edge)
746 {
747 #ifdef EDGESPLIT_DEBUG_1
748         printf("edge %d: ", edge->newIndex);
749 #endif
750         if(edge->flag & ME_SHARP) {
751                 /* edge can only be sharp if it has at least 2 faces */
752                 if(!edge_is_loose(edge)) {
753 #ifdef EDGESPLIT_DEBUG_1
754                         printf("sharp\n");
755 #endif
756                         return 1;
757                 } else {
758                         /* edge is loose, so it can't be sharp */
759                         edge->flag &= ~ME_SHARP;
760                 }
761         }
762
763 #ifdef EDGESPLIT_DEBUG_1
764         printf("not sharp\n");
765 #endif
766         return 0;
767 }
768
769 /* finds another sharp edge which uses vert, by traversing faces around the
770  * vert until it does one of the following:
771  * - hits a loose edge (the edge is returned)
772  * - hits a sharp edge (the edge is returned)
773  * - returns to the start edge (NULL is returned)
774  */
775 static SmoothEdge *find_other_sharp_edge(SmoothVert *vert, SmoothEdge *edge, LinkNode **visited_faces)
776 {
777         SmoothFace *face = NULL;
778         SmoothEdge *edge2 = NULL;
779         /* holds the edges we've seen so we can avoid looping indefinitely */
780         LinkNode *visited_edges = NULL;
781 #ifdef EDGESPLIT_DEBUG_1
782         printf("=== START === find_other_sharp_edge(edge = %4d, vert = %4d)\n",
783                 edge->newIndex, vert->newIndex);
784 #endif
785
786         /* get a face on which to start */
787         if(edge->faces) face = edge->faces->link;
788         else return NULL;
789
790         /* record this edge as visited */
791         BLI_linklist_prepend(&visited_edges, edge);
792
793         /* get the next edge */
794         edge2 = other_edge(face, vert, edge);
795
796         /* record this face as visited */
797         if(visited_faces)
798                 BLI_linklist_prepend(visited_faces, face);
799
800         /* search until we hit a loose edge or a sharp edge or an edge we've
801         * seen before
802         */
803         while(face && !edge_is_sharp(edge2)
804                          && !linklist_contains(visited_edges, edge2)) {
805 #ifdef EDGESPLIT_DEBUG_3
806                 printf("current face %4d; current edge %4d\n", face->newIndex,
807                         edge2->newIndex);
808 #endif
809                 /* get the next face */
810                 face = other_face(edge2, face);
811
812                 /* if face == NULL, edge2 is a loose edge */
813                 if(face) {
814                         /* record this face as visited */
815                         if(visited_faces)
816                                 BLI_linklist_prepend(visited_faces, face);
817
818                         /* record this edge as visited */
819                         BLI_linklist_prepend(&visited_edges, edge2);
820
821                         /* get the next edge */
822                         edge2 = other_edge(face, vert, edge2);
823 #ifdef EDGESPLIT_DEBUG_3
824                         printf("next face %4d; next edge %4d\n",
825                                 face->newIndex, edge2->newIndex);
826                 } else {
827                         printf("loose edge: %4d\n", edge2->newIndex);
828 #endif
829                 }
830         }
831
832         /* either we came back to the start edge or we found a sharp/loose edge */
833         if(linklist_contains(visited_edges, edge2))
834                 /* we came back to the start edge */
835                 edge2 = NULL;
836
837         BLI_linklist_free(visited_edges, NULL);
838
839 #ifdef EDGESPLIT_DEBUG_1
840         printf("=== END === find_other_sharp_edge(edge = %4d, vert = %4d), "
841                 "returning edge %d\n",
842                 edge->newIndex, vert->newIndex, edge2 ? edge2->newIndex : -1);
843 #endif
844         return edge2;
845 }
846
847 static void split_single_vert(SmoothVert *vert, SmoothFace *face,
848                                   SmoothMesh *mesh)
849 {
850         SmoothVert *copy_vert;
851         ReplaceData repdata;
852
853         copy_vert = smoothvert_copy(vert, mesh);
854
855         if(copy_vert == NULL) {
856                 /* bug [#26316], this prevents a segfault
857                  * but this still needs fixing */
858                 return;
859         }
860
861         repdata.find = vert;
862         repdata.replace = copy_vert;
863         face_replace_vert(face, &repdata);
864 }
865
866 typedef struct PropagateEdge {
867         struct PropagateEdge *next, *prev;
868         SmoothEdge *edge;
869         SmoothVert *vert;
870 } PropagateEdge;
871
872 static void push_propagate_stack(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
873 {
874         PropagateEdge *pedge = mesh->reusestack.first;
875
876         if(pedge) {
877                 BLI_remlink(&mesh->reusestack, pedge);
878         }
879         else {
880                 if(!mesh->arena) {
881                         mesh->arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "edgesplit arena");
882                         BLI_memarena_use_calloc(mesh->arena);
883                 }
884
885                 pedge = BLI_memarena_alloc(mesh->arena, sizeof(PropagateEdge));
886         }
887
888         pedge->edge = edge;
889         pedge->vert = vert;
890         BLI_addhead(&mesh->propagatestack, pedge);
891 }
892
893 static void pop_propagate_stack(SmoothEdge **edge, SmoothVert **vert, SmoothMesh *mesh)
894 {
895         PropagateEdge *pedge = mesh->propagatestack.first;
896
897         if(pedge) {
898                 *edge = pedge->edge;
899                 *vert = pedge->vert;
900                 BLI_remlink(&mesh->propagatestack, pedge);
901                 BLI_addhead(&mesh->reusestack, pedge);
902         }
903         else {
904                 *edge = NULL;
905                 *vert = NULL;
906         }
907 }
908
909 static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh);
910
911 static void propagate_split(SmoothEdge *edge, SmoothVert *vert,
912                                 SmoothMesh *mesh)
913 {
914         SmoothEdge *edge2;
915         LinkNode *visited_faces = NULL;
916 #ifdef EDGESPLIT_DEBUG_1
917         printf("=== START === propagate_split(edge = %4d, vert = %4d)\n",
918                 edge->newIndex, vert->newIndex);
919 #endif
920
921         edge2 = find_other_sharp_edge(vert, edge, &visited_faces);
922
923         if(!edge2) {
924                 /* didn't find a sharp or loose edge, so we've hit a dead end */
925         } else if(!edge_is_loose(edge2)) {
926                 /* edge2 is not loose, so it must be sharp */
927                 if(edge_is_loose(edge)) {
928                         /* edge is loose, so we can split edge2 at this vert */
929                         split_edge(edge2, vert, mesh);
930                 } else if(edge_is_sharp(edge)) {
931                         /* both edges are sharp, so we can split the pair at vert */
932                         split_edge(edge, vert, mesh);
933                 } else {
934                         /* edge is not sharp, so try to split edge2 at its other vert */
935                         split_edge(edge2, other_vert(edge2, vert), mesh);
936                 }
937         } else { /* edge2 is loose */
938                 if(edge_is_loose(edge)) {
939                         SmoothVert *vert2;
940                         ReplaceData repdata;
941
942                         /* can't split edge, what should we do with vert? */
943                         if(linklist_subset(vert->faces, visited_faces)) {
944                                 /* vert has only one fan of faces attached; don't split it */
945                         } else {
946                                 /* vert has more than one fan of faces attached; split it */
947                                 vert2 = smoothvert_copy(vert, mesh);
948
949                                 /* fails in rare cases, see [#26993] */
950                                 if(vert2) {
951                                         /* replace vert with its copy in visited_faces */
952                                         repdata.find = vert;
953                                         repdata.replace = vert2;
954                                         BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
955                                 }
956                         }
957                 } else {
958                         /* edge is not loose, so it must be sharp; split it */
959                         split_edge(edge, vert, mesh);
960                 }
961         }
962
963         BLI_linklist_free(visited_faces, NULL);
964 #ifdef EDGESPLIT_DEBUG_1
965         printf("=== END === propagate_split(edge = %4d, vert = %4d)\n",
966                 edge->newIndex, vert->newIndex);
967 #endif
968 }
969
970 static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
971 {
972         SmoothEdge *edge2;
973         SmoothVert *vert2;
974         ReplaceData repdata;
975         /* the list of faces traversed while looking for a sharp edge */
976         LinkNode *visited_faces = NULL;
977 #ifdef EDGESPLIT_DEBUG_1
978         printf("=== START === split_edge(edge = %4d, vert = %4d)\n",
979                 edge->newIndex, vert->newIndex);
980 #endif
981
982         edge2 = find_other_sharp_edge(vert, edge, &visited_faces);
983
984         if(!edge2) {
985                 /* didn't find a sharp or loose edge, so try the other vert */
986                 vert2 = other_vert(edge, vert);
987                 push_propagate_stack(edge, vert2, mesh);
988         } else if(!edge_is_loose(edge2)) {
989                 /* edge2 is not loose, so it must be sharp */
990                 SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
991                 SmoothEdge *copy_edge2 = smoothedge_copy(edge2, mesh);
992                 SmoothVert *vert2;
993
994                 /* replace edge with its copy in visited_faces */
995                 repdata.find = edge;
996                 repdata.replace = copy_edge;
997                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
998
999                 /* replace edge2 with its copy in visited_faces */
1000                 repdata.find = edge2;
1001                 repdata.replace = copy_edge2;
1002                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
1003
1004                 vert2 = smoothvert_copy(vert, mesh);
1005
1006                 /* replace vert with its copy in visited_faces (must be done after
1007                 * edge replacement so edges have correct vertices)
1008                 */
1009                 repdata.find = vert;
1010                 repdata.replace = vert2;
1011                 BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
1012
1013                 /* all copying and replacing is done; the mesh should be consistent.
1014                 * now propagate the split to the vertices at either end
1015                 */
1016                 push_propagate_stack(copy_edge, other_vert(copy_edge, vert2), mesh);
1017                 push_propagate_stack(copy_edge2, other_vert(copy_edge2, vert2), mesh);
1018
1019                 if(smoothedge_has_vert(edge, vert))
1020                         push_propagate_stack(edge, vert, mesh);
1021         } else {
1022                 /* edge2 is loose */
1023                 SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
1024                 SmoothVert *vert2;
1025
1026                 /* replace edge with its copy in visited_faces */
1027                 repdata.find = edge;
1028                 repdata.replace = copy_edge;
1029                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
1030
1031                 vert2 = smoothvert_copy(vert, mesh);
1032
1033                 /* replace vert with its copy in visited_faces (must be done after
1034                 * edge replacement so edges have correct vertices)
1035                 */
1036                 repdata.find = vert;
1037                 repdata.replace = vert2;
1038                 BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
1039
1040                 /* copying and replacing is done; the mesh should be consistent.
1041                 * now propagate the split to the vertex at the other end
1042                 */
1043                 push_propagate_stack(copy_edge, other_vert(copy_edge, vert2), mesh);
1044
1045                 if(smoothedge_has_vert(edge, vert))
1046                         push_propagate_stack(edge, vert, mesh);
1047         }
1048
1049         BLI_linklist_free(visited_faces, NULL);
1050 #ifdef EDGESPLIT_DEBUG_1
1051         printf("=== END === split_edge(edge = %4d, vert = %4d)\n",
1052                 edge->newIndex, vert->newIndex);
1053 #endif
1054 }
1055
1056 static void tag_and_count_extra_edges(SmoothMesh *mesh, float split_angle,
1057                                           int flags, int *extra_edges)
1058 {
1059         /* if normal1 dot normal2 < threshold, angle is greater, so split */
1060         /* FIXME not sure if this always works */
1061         /* 0.00001 added for floating-point rounding */
1062         float threshold = cos((split_angle + 0.00001f) * (float)M_PI / 180.0f);
1063         int i;
1064
1065         *extra_edges = 0;
1066
1067         /* loop through edges, counting potential new ones */
1068         for(i = 0; i < mesh->num_edges; i++) {
1069                 SmoothEdge *edge = &mesh->edges[i];
1070                 int sharp = 0;
1071
1072                 /* treat all non-manifold edges (3 or more faces) as sharp */
1073                 if(edge->faces && edge->faces->next && edge->faces->next->next) {
1074                         LinkNode *node;
1075
1076                         /* this edge is sharp */
1077                         sharp = 1;
1078
1079                         /* add an extra edge for every face beyond the first */
1080                         *extra_edges += 2;
1081                         for(node = edge->faces->next->next->next; node; node = node->next)
1082                                 (*extra_edges)++;
1083                 } else if((flags & (MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG))
1084                                          && !edge_is_loose(edge)) {
1085                         /* (the edge can only be sharp if we're checking angle or flag,
1086                         * and it has at least 2 faces) */
1087
1088                         /* if we're checking the sharp flag and it's set, good */
1089                         if((flags & MOD_EDGESPLIT_FROMFLAG) && (edge->flag & ME_SHARP)) {
1090                                 /* this edge is sharp */
1091                                 sharp = 1;
1092
1093                                 (*extra_edges)++;
1094                         } else if(flags & MOD_EDGESPLIT_FROMANGLE) {
1095                                 /* we know the edge has 2 faces, so check the angle */
1096                                 SmoothFace *face1 = edge->faces->link;
1097                                 SmoothFace *face2 = edge->faces->next->link;
1098                                 float edge_angle_cos = dot_v3v3(face1->normal,
1099                                 face2->normal);
1100
1101                                 if(edge_angle_cos < threshold) {
1102                                         /* this edge is sharp */
1103                                         sharp = 1;
1104
1105                                         (*extra_edges)++;
1106                                 }
1107                         }
1108                 }
1109
1110                 /* set/clear sharp flag appropriately */
1111                 if(sharp) edge->flag |= ME_SHARP;
1112                 else edge->flag &= ~ME_SHARP;
1113         }
1114 }
1115
1116 static void split_sharp_edges(SmoothMesh *mesh, float split_angle, int flags)
1117 {
1118         SmoothVert *vert;
1119         int i;
1120         /* if normal1 dot normal2 < threshold, angle is greater, so split */
1121         /* FIXME not sure if this always works */
1122         /* 0.00001 added for floating-point rounding */
1123         mesh->threshold = cosf((split_angle + 0.00001f) * (float)M_PI / 180.0f);
1124         mesh->flags = flags;
1125
1126         /* loop through edges, splitting sharp ones */
1127         /* can't use an iterator here, because we'll be adding edges */
1128         for(i = 0; i < mesh->num_edges; i++) {
1129                 SmoothEdge *edge = &mesh->edges[i];
1130
1131                 if(edge_is_sharp(edge)) {
1132                         split_edge(edge, edge->verts[0], mesh);
1133
1134                         do {
1135                                 pop_propagate_stack(&edge, &vert, mesh);
1136                                 if(edge && smoothedge_has_vert(edge, vert))
1137                                         propagate_split(edge, vert, mesh);
1138                         } while(edge);
1139                 }
1140         }
1141 }
1142
1143 static int count_bridge_verts(SmoothMesh *mesh)
1144 {
1145         int i, j, count = 0;
1146
1147         for(i = 0; i < mesh->num_faces; i++) {
1148                 SmoothFace *face = &mesh->faces[i];
1149
1150                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
1151                         SmoothEdge *edge = face->edges[j];
1152                         SmoothEdge *next_edge;
1153                         SmoothVert *vert = edge->verts[1 - face->flip[j]];
1154                         int next = (j + 1) % SMOOTHFACE_MAX_EDGES;
1155
1156                         /* wrap next around if at last edge */
1157                         if(!face->edges[next]) next = 0;
1158
1159                         next_edge = face->edges[next];
1160
1161                         /* if there are other faces sharing this vertex but not
1162                         * these edges, the vertex will be split, so count it
1163                         */
1164                         /* vert has to have at least one face (this one), so faces != 0 */
1165                         if(!edge->faces->next && !next_edge->faces->next
1166                                                  && vert->faces->next) {
1167                                 count++;
1168                                                  }
1169                 }
1170         }
1171
1172         /* each bridge vert will be counted once per face that uses it,
1173         * so count is too high, but it's ok for now
1174         */
1175         return count;
1176 }
1177
1178 static void split_bridge_verts(SmoothMesh *mesh)
1179 {
1180         int i,j;
1181
1182         for(i = 0; i < mesh->num_faces; i++) {
1183                 SmoothFace *face = &mesh->faces[i];
1184
1185                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
1186                         SmoothEdge *edge = face->edges[j];
1187                         SmoothEdge *next_edge;
1188                         SmoothVert *vert = edge->verts[1 - face->flip[j]];
1189                         int next = (j + 1) % SMOOTHFACE_MAX_EDGES;
1190
1191                         /* wrap next around if at last edge */
1192                         if(!face->edges[next]) next = 0;
1193
1194                         next_edge = face->edges[next];
1195
1196                         /* if there are other faces sharing this vertex but not
1197                         * these edges, split the vertex
1198                         */
1199                         /* vert has to have at least one face (this one), so faces != 0 */
1200                         if(!edge->faces->next && !next_edge->faces->next
1201                                                  && vert->faces->next)
1202                                 /* FIXME this needs to find all faces that share edges with
1203                                 * this one and split off together
1204                                 */
1205                                 split_single_vert(vert, face, mesh);
1206                 }
1207         }
1208 }
1209
1210 static DerivedMesh *edgesplitModifier_do(EdgeSplitModifierData *emd, DerivedMesh *dm)
1211 {
1212         SmoothMesh *mesh;
1213         DerivedMesh *result;
1214         int max_verts, max_edges;
1215
1216         if(!(emd->flags & (MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG)))
1217                 return dm;
1218
1219         /* 1. make smoothmesh with initial number of elements */
1220         mesh = smoothmesh_from_derivedmesh(dm);
1221
1222         /* 2. count max number of elements to add */
1223         tag_and_count_extra_edges(mesh, emd->split_angle, emd->flags, &max_edges);
1224         max_verts = max_edges * 2 + mesh->max_verts;
1225         max_verts += count_bridge_verts(mesh);
1226         max_edges += mesh->max_edges;
1227
1228         /* 3. reallocate smoothmesh arrays & copy elements across */
1229         /* 4. remap copied elements' pointers to point into the new arrays */
1230         smoothmesh_resize_verts(mesh, max_verts);
1231         smoothmesh_resize_edges(mesh, max_edges);
1232
1233 #ifdef EDGESPLIT_DEBUG_1
1234         printf("********** Pre-split **********\n");
1235         smoothmesh_print(mesh);
1236 #endif
1237
1238         split_sharp_edges(mesh, emd->split_angle, emd->flags);
1239 #ifdef EDGESPLIT_DEBUG_1
1240         printf("********** Post-edge-split **********\n");
1241         smoothmesh_print(mesh);
1242 #endif
1243
1244         split_bridge_verts(mesh);
1245
1246 #ifdef EDGESPLIT_DEBUG_1
1247         printf("********** Post-vert-split **********\n");
1248         smoothmesh_print(mesh);
1249 #endif
1250
1251 #ifdef EDGESPLIT_DEBUG_0
1252         printf("Edgesplit: Estimated %d verts & %d edges, "
1253                 "found %d verts & %d edges\n", max_verts, max_edges,
1254                 mesh->num_verts, mesh->num_edges);
1255 #endif
1256
1257         result = CDDM_from_smoothmesh(mesh);
1258         smoothmesh_free(mesh);
1259
1260         return result;
1261 }
1262
1263 static DerivedMesh *applyModifier(ModifierData *md, Object *UNUSED(ob),
1264                                                 DerivedMesh *derivedData,
1265                                                 int UNUSED(useRenderParams),
1266                                                 int UNUSED(isFinalCalc))
1267 {
1268         DerivedMesh *result;
1269         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
1270
1271         result = edgesplitModifier_do(emd, derivedData);
1272
1273         if(result != derivedData)
1274                 CDDM_calc_normals(result);
1275
1276         return result;
1277 }
1278
1279 static DerivedMesh *applyModifierEM(ModifierData *md, Object *ob,
1280                                                 struct EditMesh *UNUSED(editData),
1281                                                 DerivedMesh *derivedData)
1282 {
1283         return applyModifier(md, ob, derivedData, 0, 1);
1284 }
1285
1286
1287 ModifierTypeInfo modifierType_EdgeSplit = {
1288         /* name */              "EdgeSplit",
1289         /* structName */        "EdgeSplitModifierData",
1290         /* structSize */        sizeof(EdgeSplitModifierData),
1291         /* type */              eModifierTypeType_Constructive,
1292         /* flags */             eModifierTypeFlag_AcceptsMesh
1293                                                         | eModifierTypeFlag_AcceptsCVs
1294                                                         | eModifierTypeFlag_SupportsMapping
1295                                                         | eModifierTypeFlag_SupportsEditmode
1296                                                         | eModifierTypeFlag_EnableInEditmode,
1297
1298         /* copyData */          copyData,
1299         /* deformVerts */       NULL,
1300         /* deformMatrices */    NULL,
1301         /* deformVertsEM */     NULL,
1302         /* deformMatricesEM */  NULL,
1303         /* applyModifier */     applyModifier,
1304         /* applyModifierEM */   applyModifierEM,
1305         /* initData */          initData,
1306         /* requiredDataMask */  NULL,
1307         /* freeData */          NULL,
1308         /* isDisabled */        NULL,
1309         /* updateDepgraph */    NULL,
1310         /* dependsOnTime */     NULL,
1311         /* dependsOnNormals */  NULL,
1312         /* foreachObjectLink */ NULL,
1313         /* foreachIDLink */     NULL,
1314 };