converted more mixed tab/space indentations to tabs. only whitespace changes.
[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                                 /* replace vert with its copy in visited_faces */
946                                 repdata.find = vert;
947                                 repdata.replace = vert2;
948                                 BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
949                         }
950                 } else {
951                         /* edge is not loose, so it must be sharp; split it */
952                         split_edge(edge, vert, mesh);
953                 }
954         }
955
956         BLI_linklist_free(visited_faces, NULL);
957 #ifdef EDGESPLIT_DEBUG_1
958         printf("=== END === propagate_split(edge = %4d, vert = %4d)\n",
959                         edge->newIndex, vert->newIndex);
960 #endif
961 }
962
963 static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
964 {
965         SmoothEdge *edge2;
966         SmoothVert *vert2;
967         ReplaceData repdata;
968         /* the list of faces traversed while looking for a sharp edge */
969         LinkNode *visited_faces = NULL;
970 #ifdef EDGESPLIT_DEBUG_1
971         printf("=== START === split_edge(edge = %4d, vert = %4d)\n",
972                         edge->newIndex, vert->newIndex);
973 #endif
974
975         edge2 = find_other_sharp_edge(vert, edge, &visited_faces);
976
977         if(!edge2) {
978                 /* didn't find a sharp or loose edge, so try the other vert */
979                 vert2 = other_vert(edge, vert);
980                 push_propagate_stack(edge, vert2, mesh);
981         } else if(!edge_is_loose(edge2)) {
982                 /* edge2 is not loose, so it must be sharp */
983                 SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
984                 SmoothEdge *copy_edge2 = smoothedge_copy(edge2, mesh);
985                 SmoothVert *vert2;
986
987                 /* replace edge with its copy in visited_faces */
988                 repdata.find = edge;
989                 repdata.replace = copy_edge;
990                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
991
992                 /* replace edge2 with its copy in visited_faces */
993                 repdata.find = edge2;
994                 repdata.replace = copy_edge2;
995                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
996
997                 vert2 = smoothvert_copy(vert, mesh);
998
999                 /* replace vert with its copy in visited_faces (must be done after
1000                 * edge replacement so edges have correct vertices)
1001                 */
1002                 repdata.find = vert;
1003                 repdata.replace = vert2;
1004                 BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
1005
1006                 /* all copying and replacing is done; the mesh should be consistent.
1007                 * now propagate the split to the vertices at either end
1008                 */
1009                 push_propagate_stack(copy_edge, other_vert(copy_edge, vert2), mesh);
1010                 push_propagate_stack(copy_edge2, other_vert(copy_edge2, vert2), mesh);
1011
1012                 if(smoothedge_has_vert(edge, vert))
1013                         push_propagate_stack(edge, vert, mesh);
1014         } else {
1015                 /* edge2 is loose */
1016                 SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
1017                 SmoothVert *vert2;
1018
1019                 /* replace edge with its copy in visited_faces */
1020                 repdata.find = edge;
1021                 repdata.replace = copy_edge;
1022                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
1023
1024                 vert2 = smoothvert_copy(vert, mesh);
1025
1026                 /* replace vert with its copy in visited_faces (must be done after
1027                 * edge replacement so edges have correct vertices)
1028                 */
1029                 repdata.find = vert;
1030                 repdata.replace = vert2;
1031                 BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
1032
1033                 /* copying and replacing is done; the mesh should be consistent.
1034                 * now propagate the split to the vertex at the other end
1035                 */
1036                 push_propagate_stack(copy_edge, other_vert(copy_edge, vert2), mesh);
1037
1038                 if(smoothedge_has_vert(edge, vert))
1039                         push_propagate_stack(edge, vert, mesh);
1040         }
1041
1042         BLI_linklist_free(visited_faces, NULL);
1043 #ifdef EDGESPLIT_DEBUG_1
1044         printf("=== END === split_edge(edge = %4d, vert = %4d)\n",
1045                         edge->newIndex, vert->newIndex);
1046 #endif
1047 }
1048
1049 static void tag_and_count_extra_edges(SmoothMesh *mesh, float split_angle,
1050                                           int flags, int *extra_edges)
1051 {
1052         /* if normal1 dot normal2 < threshold, angle is greater, so split */
1053         /* FIXME not sure if this always works */
1054         /* 0.00001 added for floating-point rounding */
1055         float threshold = cos((split_angle + 0.00001f) * (float)M_PI / 180.0f);
1056         int i;
1057
1058         *extra_edges = 0;
1059
1060         /* loop through edges, counting potential new ones */
1061         for(i = 0; i < mesh->num_edges; i++) {
1062                 SmoothEdge *edge = &mesh->edges[i];
1063                 int sharp = 0;
1064
1065                 /* treat all non-manifold edges (3 or more faces) as sharp */
1066                 if(edge->faces && edge->faces->next && edge->faces->next->next) {
1067                         LinkNode *node;
1068
1069                         /* this edge is sharp */
1070                         sharp = 1;
1071
1072                         /* add an extra edge for every face beyond the first */
1073                         *extra_edges += 2;
1074                         for(node = edge->faces->next->next->next; node; node = node->next)
1075                                 (*extra_edges)++;
1076                 } else if((flags & (MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG))
1077                                          && !edge_is_loose(edge)) {
1078                         /* (the edge can only be sharp if we're checking angle or flag,
1079                         * and it has at least 2 faces) */
1080
1081                         /* if we're checking the sharp flag and it's set, good */
1082                         if((flags & MOD_EDGESPLIT_FROMFLAG) && (edge->flag & ME_SHARP)) {
1083                                 /* this edge is sharp */
1084                                 sharp = 1;
1085
1086                                 (*extra_edges)++;
1087                         } else if(flags & MOD_EDGESPLIT_FROMANGLE) {
1088                                 /* we know the edge has 2 faces, so check the angle */
1089                                 SmoothFace *face1 = edge->faces->link;
1090                                 SmoothFace *face2 = edge->faces->next->link;
1091                                 float edge_angle_cos = dot_v3v3(face1->normal,
1092                                 face2->normal);
1093
1094                                 if(edge_angle_cos < threshold) {
1095                                         /* this edge is sharp */
1096                                         sharp = 1;
1097
1098                                         (*extra_edges)++;
1099                                 }
1100                         }
1101                 }
1102
1103                 /* set/clear sharp flag appropriately */
1104                 if(sharp) edge->flag |= ME_SHARP;
1105                 else edge->flag &= ~ME_SHARP;
1106         }
1107 }
1108
1109 static void split_sharp_edges(SmoothMesh *mesh, float split_angle, int flags)
1110 {
1111         SmoothVert *vert;
1112         int i;
1113         /* if normal1 dot normal2 < threshold, angle is greater, so split */
1114         /* FIXME not sure if this always works */
1115         /* 0.00001 added for floating-point rounding */
1116         mesh->threshold = cosf((split_angle + 0.00001f) * (float)M_PI / 180.0f);
1117         mesh->flags = flags;
1118
1119         /* loop through edges, splitting sharp ones */
1120         /* can't use an iterator here, because we'll be adding edges */
1121         for(i = 0; i < mesh->num_edges; i++) {
1122                 SmoothEdge *edge = &mesh->edges[i];
1123
1124                 if(edge_is_sharp(edge)) {
1125                         split_edge(edge, edge->verts[0], mesh);
1126
1127                         do {
1128                                 pop_propagate_stack(&edge, &vert, mesh);
1129                                 if(edge && smoothedge_has_vert(edge, vert))
1130                                         propagate_split(edge, vert, mesh);
1131                         } while(edge);
1132                 }
1133         }
1134 }
1135
1136 static int count_bridge_verts(SmoothMesh *mesh)
1137 {
1138         int i, j, count = 0;
1139
1140         for(i = 0; i < mesh->num_faces; i++) {
1141                 SmoothFace *face = &mesh->faces[i];
1142
1143                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
1144                         SmoothEdge *edge = face->edges[j];
1145                         SmoothEdge *next_edge;
1146                         SmoothVert *vert = edge->verts[1 - face->flip[j]];
1147                         int next = (j + 1) % SMOOTHFACE_MAX_EDGES;
1148
1149                         /* wrap next around if at last edge */
1150                         if(!face->edges[next]) next = 0;
1151
1152                         next_edge = face->edges[next];
1153
1154                         /* if there are other faces sharing this vertex but not
1155                         * these edges, the vertex will be split, so count it
1156                         */
1157                         /* vert has to have at least one face (this one), so faces != 0 */
1158                         if(!edge->faces->next && !next_edge->faces->next
1159                                                  && vert->faces->next) {
1160                                 count++;
1161                                                  }
1162                 }
1163         }
1164
1165         /* each bridge vert will be counted once per face that uses it,
1166         * so count is too high, but it's ok for now
1167         */
1168         return count;
1169 }
1170
1171 static void split_bridge_verts(SmoothMesh *mesh)
1172 {
1173         int i,j;
1174
1175         for(i = 0; i < mesh->num_faces; i++) {
1176                 SmoothFace *face = &mesh->faces[i];
1177
1178                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
1179                         SmoothEdge *edge = face->edges[j];
1180                         SmoothEdge *next_edge;
1181                         SmoothVert *vert = edge->verts[1 - face->flip[j]];
1182                         int next = (j + 1) % SMOOTHFACE_MAX_EDGES;
1183
1184                         /* wrap next around if at last edge */
1185                         if(!face->edges[next]) next = 0;
1186
1187                         next_edge = face->edges[next];
1188
1189                         /* if there are other faces sharing this vertex but not
1190                         * these edges, split the vertex
1191                         */
1192                         /* vert has to have at least one face (this one), so faces != 0 */
1193                         if(!edge->faces->next && !next_edge->faces->next
1194                                                  && vert->faces->next)
1195                                 /* FIXME this needs to find all faces that share edges with
1196                                 * this one and split off together
1197                                 */
1198                                 split_single_vert(vert, face, mesh);
1199                 }
1200         }
1201 }
1202
1203 static DerivedMesh *edgesplitModifier_do(EdgeSplitModifierData *emd, DerivedMesh *dm)
1204 {
1205         SmoothMesh *mesh;
1206         DerivedMesh *result;
1207         int max_verts, max_edges;
1208
1209         if(!(emd->flags & (MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG)))
1210                 return dm;
1211
1212         /* 1. make smoothmesh with initial number of elements */
1213         mesh = smoothmesh_from_derivedmesh(dm);
1214
1215         /* 2. count max number of elements to add */
1216         tag_and_count_extra_edges(mesh, emd->split_angle, emd->flags, &max_edges);
1217         max_verts = max_edges * 2 + mesh->max_verts;
1218         max_verts += count_bridge_verts(mesh);
1219         max_edges += mesh->max_edges;
1220
1221         /* 3. reallocate smoothmesh arrays & copy elements across */
1222         /* 4. remap copied elements' pointers to point into the new arrays */
1223         smoothmesh_resize_verts(mesh, max_verts);
1224         smoothmesh_resize_edges(mesh, max_edges);
1225
1226 #ifdef EDGESPLIT_DEBUG_1
1227         printf("********** Pre-split **********\n");
1228         smoothmesh_print(mesh);
1229 #endif
1230
1231         split_sharp_edges(mesh, emd->split_angle, emd->flags);
1232 #ifdef EDGESPLIT_DEBUG_1
1233         printf("********** Post-edge-split **********\n");
1234         smoothmesh_print(mesh);
1235 #endif
1236
1237         split_bridge_verts(mesh);
1238
1239 #ifdef EDGESPLIT_DEBUG_1
1240         printf("********** Post-vert-split **********\n");
1241         smoothmesh_print(mesh);
1242 #endif
1243
1244 #ifdef EDGESPLIT_DEBUG_0
1245         printf("Edgesplit: Estimated %d verts & %d edges, "
1246                         "found %d verts & %d edges\n", max_verts, max_edges,
1247                         mesh->num_verts, mesh->num_edges);
1248 #endif
1249
1250         result = CDDM_from_smoothmesh(mesh);
1251         smoothmesh_free(mesh);
1252
1253         return result;
1254 }
1255
1256 static DerivedMesh *applyModifier(ModifierData *md, Object *UNUSED(ob),
1257                                                 DerivedMesh *derivedData,
1258                                                 int UNUSED(useRenderParams),
1259                                                 int UNUSED(isFinalCalc))
1260 {
1261         DerivedMesh *result;
1262         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
1263
1264         result = edgesplitModifier_do(emd, derivedData);
1265
1266         if(result != derivedData)
1267                 CDDM_calc_normals(result);
1268
1269         return result;
1270 }
1271
1272 static DerivedMesh *applyModifierEM(ModifierData *md, Object *ob,
1273                                                 struct EditMesh *UNUSED(editData),
1274                                                 DerivedMesh *derivedData)
1275 {
1276         return applyModifier(md, ob, derivedData, 0, 1);
1277 }
1278
1279
1280 ModifierTypeInfo modifierType_EdgeSplit = {
1281         /* name */              "EdgeSplit",
1282         /* structName */        "EdgeSplitModifierData",
1283         /* structSize */        sizeof(EdgeSplitModifierData),
1284         /* type */              eModifierTypeType_Constructive,
1285         /* flags */             eModifierTypeFlag_AcceptsMesh
1286                                                         | eModifierTypeFlag_AcceptsCVs
1287                                                         | eModifierTypeFlag_SupportsMapping
1288                                                         | eModifierTypeFlag_SupportsEditmode
1289                                                         | eModifierTypeFlag_EnableInEditmode,
1290
1291         /* copyData */          copyData,
1292         /* deformVerts */       NULL,
1293         /* deformMatrices */    NULL,
1294         /* deformVertsEM */     NULL,
1295         /* deformMatricesEM */  NULL,
1296         /* applyModifier */     applyModifier,
1297         /* applyModifierEM */   applyModifierEM,
1298         /* initData */          initData,
1299         /* requiredDataMask */  NULL,
1300         /* freeData */          NULL,
1301         /* isDisabled */        NULL,
1302         /* updateDepgraph */    NULL,
1303         /* dependsOnTime */     NULL,
1304         /* dependsOnNormals */  NULL,
1305         /* foreachObjectLink */ NULL,
1306         /* foreachIDLink */     NULL,
1307 };