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