Made Object-level copy constraints work the same as for bones now too
[blender.git] / source / blender / blenkernel / intern / modifier.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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19 *
20 * The Original Code is Copyright (C) 2005 by the Blender Foundation.
21 * All rights reserved.
22 *
23 * The Original Code is: all of this file.
24 *
25 * Contributor(s): Daniel Dunbar
26 *                 Ton Roosendaal,
27 *                 Ben Batt,
28 *                 Brecht Van Lommel,
29 *                 Campbell Barton
30 *
31 * ***** END GPL LICENSE BLOCK *****
32 *
33 * Modifier stack implementation.
34 *
35 * BKE_modifier.h contains the function prototypes for this file.
36 *
37 */
38
39 #include "string.h"
40 #include "stdarg.h"
41 #include "math.h"
42 #include "float.h"
43 #include "ctype.h"
44
45 #include "BLI_arithb.h"
46 #include "BLI_blenlib.h"
47 #include "BLI_kdopbvh.h"
48 #include "BLI_kdtree.h"
49 #include "BLI_linklist.h"
50 #include "BLI_rand.h"
51 #include "BLI_edgehash.h"
52 #include "BLI_ghash.h"
53 #include "BLI_memarena.h"
54
55 #include "MEM_guardedalloc.h"
56
57 #include "DNA_action_types.h"
58 #include "DNA_armature_types.h"
59 #include "DNA_camera_types.h"
60 #include "DNA_cloth_types.h"
61 #include "DNA_curve_types.h"
62 #include "DNA_effect_types.h"
63 #include "DNA_material_types.h"
64 #include "DNA_mesh_types.h"
65 #include "DNA_meshdata_types.h"
66 #include "DNA_modifier_types.h"
67 #include "DNA_object_types.h"
68 #include "DNA_object_force.h"
69 #include "DNA_particle_types.h"
70 #include "DNA_scene_types.h"
71 #include "DNA_texture_types.h"
72
73 #include "BLI_editVert.h"
74
75 #include "MTC_matrixops.h"
76 #include "MTC_vectorops.h"
77
78 #include "BKE_main.h"
79 #include "BKE_anim.h"
80 #include "BKE_bad_level_calls.h"
81 #include "BKE_bmesh.h"
82 #include "BKE_booleanops.h"
83 #include "BKE_cloth.h"
84 #include "BKE_collision.h"
85 #include "BKE_cdderivedmesh.h"
86 #include "BKE_curve.h"
87 #include "BKE_customdata.h"
88 #include "BKE_DerivedMesh.h"
89 #include "BKE_displist.h"
90 #include "BKE_fluidsim.h"
91 #include "BKE_global.h"
92 #include "BKE_lattice.h"
93 #include "BKE_library.h"
94 #include "BKE_material.h"
95 #include "BKE_mesh.h"
96 #include "BKE_modifier.h"
97 #include "BKE_object.h"
98 #include "BKE_particle.h"
99 #include "BKE_pointcache.h"
100 #include "BKE_softbody.h"
101 #include "BKE_subsurf.h"
102 #include "BKE_texture.h"
103 #include "BKE_utildefines.h"
104
105 #include "depsgraph_private.h"
106 #include "BKE_deform.h"
107 #include "BKE_shrinkwrap.h"
108
109 #include "LOD_DependKludge.h"
110 #include "LOD_decimation.h"
111
112 #include "CCGSubSurf.h"
113
114 #include "RE_shader_ext.h"
115
116 /***/
117
118 static int noneModifier_isDisabled(ModifierData *md)
119 {
120         return 1;
121 }
122
123 /* Curve */
124
125 static void curveModifier_initData(ModifierData *md)
126 {
127         CurveModifierData *cmd = (CurveModifierData*) md;
128
129         cmd->defaxis = MOD_CURVE_POSX;
130 }
131
132 static void curveModifier_copyData(ModifierData *md, ModifierData *target)
133 {
134         CurveModifierData *cmd = (CurveModifierData*) md;
135         CurveModifierData *tcmd = (CurveModifierData*) target;
136
137         tcmd->defaxis = cmd->defaxis;
138         tcmd->object = cmd->object;
139         strncpy(tcmd->name, cmd->name, 32);
140 }
141
142 CustomDataMask curveModifier_requiredDataMask(ModifierData *md)
143 {
144         CurveModifierData *cmd = (CurveModifierData *)md;
145         CustomDataMask dataMask = 0;
146
147         /* ask for vertexgroups if we need them */
148         if(cmd->name[0]) dataMask |= (1 << CD_MDEFORMVERT);
149
150         return dataMask;
151 }
152
153 static int curveModifier_isDisabled(ModifierData *md)
154 {
155         CurveModifierData *cmd = (CurveModifierData*) md;
156
157         return !cmd->object;
158 }
159
160 static void curveModifier_foreachObjectLink(
161                                             ModifierData *md, Object *ob,
162          void (*walk)(void *userData, Object *ob, Object **obpoin),
163                 void *userData)
164 {
165         CurveModifierData *cmd = (CurveModifierData*) md;
166
167         walk(userData, ob, &cmd->object);
168 }
169
170 static void curveModifier_updateDepgraph(
171                                          ModifierData *md, DagForest *forest,
172       Object *ob, DagNode *obNode)
173 {
174         CurveModifierData *cmd = (CurveModifierData*) md;
175
176         if (cmd->object) {
177                 DagNode *curNode = dag_get_node(forest, cmd->object);
178
179                 dag_add_relation(forest, curNode, obNode,
180                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Curve Modifier");
181         }
182 }
183
184 static void curveModifier_deformVerts(
185                                       ModifierData *md, Object *ob, DerivedMesh *derivedData,
186           float (*vertexCos)[3], int numVerts)
187 {
188         CurveModifierData *cmd = (CurveModifierData*) md;
189
190         curve_deform_verts(cmd->object, ob, derivedData, vertexCos, numVerts,
191                            cmd->name, cmd->defaxis);
192 }
193
194 static void curveModifier_deformVertsEM(
195                                         ModifierData *md, Object *ob, EditMesh *editData,
196      DerivedMesh *derivedData, float (*vertexCos)[3], int numVerts)
197 {
198         DerivedMesh *dm = derivedData;
199
200         if(!derivedData) dm = CDDM_from_editmesh(editData, ob->data);
201
202         curveModifier_deformVerts(md, ob, dm, vertexCos, numVerts);
203
204         if(!derivedData) dm->release(dm);
205 }
206
207 /* Lattice */
208
209 static void latticeModifier_copyData(ModifierData *md, ModifierData *target)
210 {
211         LatticeModifierData *lmd = (LatticeModifierData*) md;
212         LatticeModifierData *tlmd = (LatticeModifierData*) target;
213
214         tlmd->object = lmd->object;
215         strncpy(tlmd->name, lmd->name, 32);
216 }
217
218 CustomDataMask latticeModifier_requiredDataMask(ModifierData *md)
219 {
220         LatticeModifierData *lmd = (LatticeModifierData *)md;
221         CustomDataMask dataMask = 0;
222
223         /* ask for vertexgroups if we need them */
224         if(lmd->name[0]) dataMask |= (1 << CD_MDEFORMVERT);
225
226         return dataMask;
227 }
228
229 static int latticeModifier_isDisabled(ModifierData *md)
230 {
231         LatticeModifierData *lmd = (LatticeModifierData*) md;
232
233         return !lmd->object;
234 }
235
236 static void latticeModifier_foreachObjectLink(
237                                               ModifierData *md, Object *ob,
238            void (*walk)(void *userData, Object *ob, Object **obpoin),
239                   void *userData)
240 {
241         LatticeModifierData *lmd = (LatticeModifierData*) md;
242
243         walk(userData, ob, &lmd->object);
244 }
245
246 static void latticeModifier_updateDepgraph(ModifierData *md, DagForest *forest,
247                                            Object *ob, DagNode *obNode)
248 {
249         LatticeModifierData *lmd = (LatticeModifierData*) md;
250
251         if(lmd->object) {
252                 DagNode *latNode = dag_get_node(forest, lmd->object);
253
254                 dag_add_relation(forest, latNode, obNode,
255                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Lattice Modifier");
256         }
257 }
258
259 static void modifier_vgroup_cache(ModifierData *md, float (*vertexCos)[3])
260 {
261         md= md->next;
262         if(md) {
263                 if(md->type==eModifierType_Armature) {
264                         ArmatureModifierData *amd = (ArmatureModifierData*) md;
265                         if(amd->multi)
266                                 amd->prevCos= MEM_dupallocN(vertexCos);
267                 }
268                 /* lattice/mesh modifier too */
269         }
270 }
271
272
273 static void latticeModifier_deformVerts(
274                                         ModifierData *md, Object *ob, DerivedMesh *derivedData,
275      float (*vertexCos)[3], int numVerts)
276 {
277         LatticeModifierData *lmd = (LatticeModifierData*) md;
278
279
280         modifier_vgroup_cache(md, vertexCos); /* if next modifier needs original vertices */
281         
282         lattice_deform_verts(lmd->object, ob, derivedData,
283                              vertexCos, numVerts, lmd->name);
284 }
285
286 static void latticeModifier_deformVertsEM(
287                                           ModifierData *md, Object *ob, EditMesh *editData,
288        DerivedMesh *derivedData, float (*vertexCos)[3], int numVerts)
289 {
290         DerivedMesh *dm = derivedData;
291
292         if(!derivedData) dm = CDDM_from_editmesh(editData, ob->data);
293
294         latticeModifier_deformVerts(md, ob, dm, vertexCos, numVerts);
295
296         if(!derivedData) dm->release(dm);
297 }
298
299 /* Subsurf */
300
301 static void subsurfModifier_initData(ModifierData *md)
302 {
303         SubsurfModifierData *smd = (SubsurfModifierData*) md;
304
305         smd->levels = 1;
306         smd->renderLevels = 2;
307         smd->flags |= eSubsurfModifierFlag_SubsurfUv;
308 }
309
310 static void subsurfModifier_copyData(ModifierData *md, ModifierData *target)
311 {
312         SubsurfModifierData *smd = (SubsurfModifierData*) md;
313         SubsurfModifierData *tsmd = (SubsurfModifierData*) target;
314
315         tsmd->flags = smd->flags;
316         tsmd->levels = smd->levels;
317         tsmd->renderLevels = smd->renderLevels;
318         tsmd->subdivType = smd->subdivType;
319 }
320
321 static void subsurfModifier_freeData(ModifierData *md)
322 {
323         SubsurfModifierData *smd = (SubsurfModifierData*) md;
324
325         if(smd->mCache) {
326                 ccgSubSurf_free(smd->mCache);
327         }
328         if(smd->emCache) {
329                 ccgSubSurf_free(smd->emCache);
330         }
331 }
332
333 static DerivedMesh *subsurfModifier_applyModifier(
334                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
335   int useRenderParams, int isFinalCalc)
336 {
337         SubsurfModifierData *smd = (SubsurfModifierData*) md;
338         DerivedMesh *result;
339
340         result = subsurf_make_derived_from_derived(derivedData, smd,
341                         useRenderParams, NULL,
342    isFinalCalc, 0);
343
344         return result;
345 }
346
347 static DerivedMesh *subsurfModifier_applyModifierEM(
348                 ModifierData *md, Object *ob, EditMesh *editData,
349   DerivedMesh *derivedData)
350 {
351         SubsurfModifierData *smd = (SubsurfModifierData*) md;
352         DerivedMesh *result;
353
354         result = subsurf_make_derived_from_derived(derivedData, smd, 0,
355                         NULL, 0, 1);
356
357         return result;
358 }
359
360 /* Build */
361
362 static void buildModifier_initData(ModifierData *md)
363 {
364         BuildModifierData *bmd = (BuildModifierData*) md;
365
366         bmd->start = 1.0;
367         bmd->length = 100.0;
368 }
369
370 static void buildModifier_copyData(ModifierData *md, ModifierData *target)
371 {
372         BuildModifierData *bmd = (BuildModifierData*) md;
373         BuildModifierData *tbmd = (BuildModifierData*) target;
374
375         tbmd->start = bmd->start;
376         tbmd->length = bmd->length;
377         tbmd->randomize = bmd->randomize;
378         tbmd->seed = bmd->seed;
379 }
380
381 static int buildModifier_dependsOnTime(ModifierData *md)
382 {
383         return 1;
384 }
385
386 static DerivedMesh *buildModifier_applyModifier(ModifierData *md, Object *ob,
387                 DerivedMesh *derivedData,
388   int useRenderParams, int isFinalCalc)
389 {
390         DerivedMesh *dm = derivedData;
391         DerivedMesh *result;
392         BuildModifierData *bmd = (BuildModifierData*) md;
393         int i;
394         int numFaces, numEdges;
395         int maxVerts, maxEdges, maxFaces;
396         int *vertMap, *edgeMap, *faceMap;
397         float frac;
398         GHashIterator *hashIter;
399         /* maps vert indices in old mesh to indices in new mesh */
400         GHash *vertHash = BLI_ghash_new(BLI_ghashutil_inthash,
401                                         BLI_ghashutil_intcmp);
402         /* maps edge indices in new mesh to indices in old mesh */
403         GHash *edgeHash = BLI_ghash_new(BLI_ghashutil_inthash,
404                                         BLI_ghashutil_intcmp);
405
406         maxVerts = dm->getNumVerts(dm);
407         vertMap = MEM_callocN(sizeof(*vertMap) * maxVerts,
408                               "build modifier vertMap");
409         for(i = 0; i < maxVerts; ++i) vertMap[i] = i;
410
411         maxEdges = dm->getNumEdges(dm);
412         edgeMap = MEM_callocN(sizeof(*edgeMap) * maxEdges,
413                               "build modifier edgeMap");
414         for(i = 0; i < maxEdges; ++i) edgeMap[i] = i;
415
416         maxFaces = dm->getNumFaces(dm);
417         faceMap = MEM_callocN(sizeof(*faceMap) * maxFaces,
418                               "build modifier faceMap");
419         for(i = 0; i < maxFaces; ++i) faceMap[i] = i;
420
421         if (ob) {
422                 frac = bsystem_time(ob, (float)G.scene->r.cfra,
423                                     bmd->start - 1.0f) / bmd->length;
424         } else {
425                 frac = G.scene->r.cfra - bmd->start / bmd->length;
426         }
427         CLAMP(frac, 0.0, 1.0);
428
429         numFaces = dm->getNumFaces(dm) * frac;
430         numEdges = dm->getNumEdges(dm) * frac;
431
432         /* if there's at least one face, build based on faces */
433         if(numFaces) {
434                 int maxEdges;
435
436                 if(bmd->randomize)
437                         BLI_array_randomize(faceMap, sizeof(*faceMap),
438                                             maxFaces, bmd->seed);
439
440                 /* get the set of all vert indices that will be in the final mesh,
441                 * mapped to the new indices
442                 */
443                 for(i = 0; i < numFaces; ++i) {
444                         MFace mf;
445                         dm->getFace(dm, faceMap[i], &mf);
446
447                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v1)))
448                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v1),
449                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
450                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v2)))
451                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v2),
452                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
453                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v3)))
454                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v3),
455                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
456                         if(mf.v4 && !BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v4)))
457                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v4),
458                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
459                 }
460
461                 /* get the set of edges that will be in the new mesh (i.e. all edges
462                 * that have both verts in the new mesh)
463                 */
464                 maxEdges = dm->getNumEdges(dm);
465                 for(i = 0; i < maxEdges; ++i) {
466                         MEdge me;
467                         dm->getEdge(dm, i, &me);
468
469                         if(BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1))
470                                                 && BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)))
471                                 BLI_ghash_insert(edgeHash,
472                                         SET_INT_IN_POINTER(BLI_ghash_size(edgeHash)), SET_INT_IN_POINTER(i));
473                 }
474         } else if(numEdges) {
475                 if(bmd->randomize)
476                         BLI_array_randomize(edgeMap, sizeof(*edgeMap),
477                                             maxEdges, bmd->seed);
478
479                 /* get the set of all vert indices that will be in the final mesh,
480                 * mapped to the new indices
481                 */
482                 for(i = 0; i < numEdges; ++i) {
483                         MEdge me;
484                         dm->getEdge(dm, edgeMap[i], &me);
485
486                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1)))
487                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me.v1),
488                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
489                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)))
490                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me.v2),
491                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
492                 }
493
494                 /* get the set of edges that will be in the new mesh
495                 */
496                 for(i = 0; i < numEdges; ++i) {
497                         MEdge me;
498                         dm->getEdge(dm, edgeMap[i], &me);
499
500                         BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(BLI_ghash_size(edgeHash)),
501                                          SET_INT_IN_POINTER(edgeMap[i]));
502                 }
503         } else {
504                 int numVerts = dm->getNumVerts(dm) * frac;
505
506                 if(bmd->randomize)
507                         BLI_array_randomize(vertMap, sizeof(*vertMap),
508                                             maxVerts, bmd->seed);
509
510                 /* get the set of all vert indices that will be in the final mesh,
511                 * mapped to the new indices
512                 */
513                 for(i = 0; i < numVerts; ++i)
514                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(vertMap[i]), SET_INT_IN_POINTER(i));
515         }
516
517         /* now we know the number of verts, edges and faces, we can create
518         * the mesh
519         */
520         result = CDDM_from_template(dm, BLI_ghash_size(vertHash),
521                                     BLI_ghash_size(edgeHash), numFaces);
522
523         /* copy the vertices across */
524         for(hashIter = BLI_ghashIterator_new(vertHash);
525                    !BLI_ghashIterator_isDone(hashIter);
526                    BLI_ghashIterator_step(hashIter)) {
527                            MVert source;
528                            MVert *dest;
529                            int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
530                            int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
531
532                            dm->getVert(dm, oldIndex, &source);
533                            dest = CDDM_get_vert(result, newIndex);
534
535                            DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
536                            *dest = source;
537                    }
538                    BLI_ghashIterator_free(hashIter);
539
540                    /* copy the edges across, remapping indices */
541                    for(i = 0; i < BLI_ghash_size(edgeHash); ++i) {
542                            MEdge source;
543                            MEdge *dest;
544                            int oldIndex = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash, SET_INT_IN_POINTER(i)));
545
546                            dm->getEdge(dm, oldIndex, &source);
547                            dest = CDDM_get_edge(result, i);
548
549                            source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
550                            source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
551
552                            DM_copy_edge_data(dm, result, oldIndex, i, 1);
553                            *dest = source;
554                    }
555
556                    /* copy the faces across, remapping indices */
557                    for(i = 0; i < numFaces; ++i) {
558                            MFace source;
559                            MFace *dest;
560                            int orig_v4;
561
562                            dm->getFace(dm, faceMap[i], &source);
563                            dest = CDDM_get_face(result, i);
564
565                            orig_v4 = source.v4;
566
567                            source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
568                            source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
569                            source.v3 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v3)));
570                            if(source.v4)
571                                    source.v4 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v4)));
572
573                            DM_copy_face_data(dm, result, faceMap[i], i, 1);
574                            *dest = source;
575
576                            test_index_face(dest, &result->faceData, i, (orig_v4 ? 4 : 3));
577                    }
578
579                    CDDM_calc_normals(result);
580
581                    BLI_ghash_free(vertHash, NULL, NULL);
582                    BLI_ghash_free(edgeHash, NULL, NULL);
583
584                    MEM_freeN(vertMap);
585                    MEM_freeN(edgeMap);
586                    MEM_freeN(faceMap);
587
588                    return result;
589 }
590
591 /* Mask */
592
593 static void maskModifier_copyData(ModifierData *md, ModifierData *target)
594 {
595         MaskModifierData *mmd = (MaskModifierData*) md;
596         MaskModifierData *tmmd = (MaskModifierData*) target;
597         
598         strcpy(tmmd->vgroup, mmd->vgroup);
599 }
600
601 static CustomDataMask maskModifier_requiredDataMask(ModifierData *md)
602 {
603         return (1 << CD_MDEFORMVERT);
604 }
605
606 static void maskModifier_foreachObjectLink(
607                                               ModifierData *md, Object *ob,
608            void (*walk)(void *userData, Object *ob, Object **obpoin),
609                   void *userData)
610 {
611         MaskModifierData *mmd = (MaskModifierData *)md;
612         walk(userData, ob, &mmd->ob_arm);
613 }
614
615 static void maskModifier_updateDepgraph(ModifierData *md, DagForest *forest,
616                                            Object *ob, DagNode *obNode)
617 {
618         MaskModifierData *mmd = (MaskModifierData *)md;
619
620         if (mmd->ob_arm) 
621         {
622                 DagNode *armNode = dag_get_node(forest, mmd->ob_arm);
623                 
624                 dag_add_relation(forest, armNode, obNode,
625                                 DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Mask Modifier");
626         }
627 }
628
629 static DerivedMesh *maskModifier_applyModifier(ModifierData *md, Object *ob,
630                 DerivedMesh *derivedData,
631   int useRenderParams, int isFinalCalc)
632 {
633         MaskModifierData *mmd= (MaskModifierData *)md;
634         DerivedMesh *dm= derivedData, *result= NULL;
635         GHash *vertHash=NULL, *edgeHash, *faceHash;
636         GHashIterator *hashIter;
637         MDeformVert *dvert= NULL;
638         int numFaces=0, numEdges=0, numVerts=0;
639         int maxVerts, maxEdges, maxFaces;
640         int i;
641         
642         /* Overview of Method:
643          *      1. Get the vertices that are in the vertexgroup of interest 
644          *      2. Filter out unwanted geometry (i.e. not in vertexgroup), by populating mappings with new vs old indices
645          *      3. Make a new mesh containing only the mapping data
646          */
647         
648         /* get original number of verts, edges, and faces */
649         maxVerts= dm->getNumVerts(dm);
650         maxEdges= dm->getNumEdges(dm);
651         maxFaces= dm->getNumFaces(dm);
652         
653         /* check if we can just return the original mesh 
654          *      - must have verts and therefore verts assigned to vgroups to do anything useful
655          */
656         if ( !(ELEM(mmd->mode, MOD_MASK_MODE_ARM, MOD_MASK_MODE_VGROUP)) ||
657                  (maxVerts == 0) || (ob->defbase.first == NULL) )
658         {
659                 return derivedData;
660         }
661         
662         /* if mode is to use selected armature bones, aggregate the bone groups */
663         if (mmd->mode == MOD_MASK_MODE_ARM) /* --- using selected bones --- */
664         {
665                 GHash *vgroupHash, *boneHash;
666                 Object *oba= mmd->ob_arm;
667                 bPoseChannel *pchan;
668                 bDeformGroup *def;
669                 
670                 /* check that there is armature object with bones to use, otherwise return original mesh */
671                 if (ELEM(NULL, mmd->ob_arm, mmd->ob_arm->pose))
672                         return derivedData;             
673                 
674                 /* hashes for finding mapping of:
675                  *      - vgroups to indicies -> vgroupHash  (string, int)
676                  *      - bones to vgroup indices -> boneHash (index of vgroup, dummy)
677                  */
678                 vgroupHash= BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp);
679                 boneHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
680                 
681                 /* build mapping of names of vertex groups to indices */
682                 for (i = 0, def = ob->defbase.first; def; def = def->next, i++) 
683                         BLI_ghash_insert(vgroupHash, def->name, SET_INT_IN_POINTER(i));
684                 
685                 /* get selected-posechannel <-> vertexgroup index mapping */
686                 for (pchan= oba->pose->chanbase.first; pchan; pchan= pchan->next) 
687                 {
688                         /* check if bone is selected */
689                         // TODO: include checks for visibility too?
690                         // FIXME: the depsgraph needs extensions to make this work in realtime...
691                         if ( (pchan->bone) && (pchan->bone->flag & BONE_SELECTED) ) 
692                         {
693                                 /* check if hash has group for this bone */
694                                 if (BLI_ghash_haskey(vgroupHash, pchan->name)) 
695                                 {
696                                         int defgrp_index= GET_INT_FROM_POINTER(BLI_ghash_lookup(vgroupHash, pchan->name));
697                                         
698                                         /* add index to hash (store under key only) */
699                                         BLI_ghash_insert(boneHash, SET_INT_IN_POINTER(defgrp_index), pchan);
700                                 }
701                         }
702                 }
703                 
704                 /* if no bones selected, free hashes and return original mesh */
705                 if (BLI_ghash_size(boneHash) == 0)
706                 {
707                         BLI_ghash_free(vgroupHash, NULL, NULL);
708                         BLI_ghash_free(boneHash, NULL, NULL);
709                         
710                         return derivedData;
711                 }
712                 
713                 /* repeat the previous check, but for dverts */
714                 dvert= dm->getVertDataArray(dm, CD_MDEFORMVERT);
715                 if (dvert == NULL)
716                 {
717                         BLI_ghash_free(vgroupHash, NULL, NULL);
718                         BLI_ghash_free(boneHash, NULL, NULL);
719                         
720                         return derivedData;
721                 }
722                 
723                 /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
724                 vertHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
725                 
726                 /* add vertices which exist in vertexgroups into vertHash for filtering */
727                 for (i = 0; i < maxVerts; i++) 
728                 {
729                         MDeformWeight *def_weight = NULL;
730                         int j;
731                         
732                         for (j= 0; j < dvert[i].totweight; j++) 
733                         {
734                                 if (BLI_ghash_haskey(boneHash, SET_INT_IN_POINTER(dvert[i].dw[j].def_nr))) 
735                                 {
736                                         def_weight = &dvert[i].dw[j];
737                                         break;
738                                 }
739                         }
740                         
741                         /* check if include vert in vertHash */
742                         if (mmd->flag & MOD_MASK_INV) {
743                                 /* if this vert is in the vgroup, don't include it in vertHash */
744                                 if (def_weight) continue;
745                         }
746                         else {
747                                 /* if this vert isn't in the vgroup, don't include it in vertHash */
748                                 if (!def_weight) continue;
749                         }
750                         
751                         /* add to ghash for verts (numVerts acts as counter for mapping) */
752                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numVerts));
753                         numVerts++;
754                 }
755                 
756                 /* free temp hashes */
757                 BLI_ghash_free(vgroupHash, NULL, NULL);
758                 BLI_ghash_free(boneHash, NULL, NULL);
759         }
760         else            /* --- Using Nominated VertexGroup only --- */ 
761         {
762                 int defgrp_index = -1;
763                 
764                 /* get index of vertex group */
765                 if (mmd->vgroup[0]) 
766                 {
767                         bDeformGroup *def;
768                         
769                         /* find index by comparing names - SLOW... */
770                         for (i = 0, def = ob->defbase.first; def; def = def->next, i++) 
771                         {
772                                 if (!strcmp(def->name, mmd->vgroup)) 
773                                 {
774                                         defgrp_index = i;
775                                         break;
776                                 }
777                         }
778                 }
779                 
780                 /* get dverts */
781                 if (defgrp_index >= 0)
782                         dvert = dm->getVertDataArray(dm, CD_MDEFORMVERT);
783                         
784                 /* if no vgroup (i.e. dverts) found, return the initial mesh */
785                 if ((defgrp_index < 0) || (dvert == NULL))
786                         return dm;
787                         
788                 /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
789                 vertHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
790                 
791                 /* add vertices which exist in vertexgroup into ghash for filtering */
792                 for (i = 0; i < maxVerts; i++) 
793                 {
794                         MDeformWeight *def_weight = NULL;
795                         int j;
796                         
797                         for (j= 0; j < dvert[i].totweight; j++) 
798                         {
799                                 if (dvert[i].dw[j].def_nr == defgrp_index) 
800                                 {
801                                         def_weight = &dvert[i].dw[j];
802                                         break;
803                                 }
804                         }
805                         
806                         /* check if include vert in vertHash */
807                         if (mmd->flag & MOD_MASK_INV) {
808                                 /* if this vert is in the vgroup, don't include it in vertHash */
809                                 if (def_weight) continue;
810                         }
811                         else {
812                                 /* if this vert isn't in the vgroup, don't include it in vertHash */
813                                 if (!def_weight) continue;
814                         }
815                         
816                         /* add to ghash for verts (numVerts acts as counter for mapping) */
817                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numVerts));
818                         numVerts++;
819                 }
820         }
821         
822         /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
823         edgeHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
824         faceHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
825         
826         /* loop over edges and faces, and do the same thing to 
827          * ensure that they only reference existing verts 
828          */
829         for (i = 0; i < maxEdges; i++) 
830         {
831                 MEdge me;
832                 dm->getEdge(dm, i, &me);
833                 
834                 /* only add if both verts will be in new mesh */
835                 if ( BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1)) &&
836                          BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)) )
837                 {
838                         BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numEdges));
839                         numEdges++;
840                 }
841         }
842         for (i = 0; i < maxFaces; i++) 
843         {
844                 MFace mf;
845                 dm->getFace(dm, i, &mf);
846                 
847                 /* all verts must be available */
848                 if ( BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v1)) &&
849                          BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v2)) &&
850                          BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v3)) &&
851                         (mf.v4==0 || BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v4))) )
852                 {
853                         BLI_ghash_insert(faceHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numFaces));
854                         numFaces++;
855                 }
856         }
857         
858         
859         /* now we know the number of verts, edges and faces, 
860          * we can create the new (reduced) mesh
861          */
862         result = CDDM_from_template(dm, numVerts, numEdges, numFaces);
863         
864         
865         /* using ghash-iterators, map data into new mesh */
866                 /* vertices */
867         for ( hashIter = BLI_ghashIterator_new(vertHash);
868                   !BLI_ghashIterator_isDone(hashIter);
869                   BLI_ghashIterator_step(hashIter) ) 
870         {
871                 MVert source;
872                 MVert *dest;
873                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
874                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
875                 
876                 dm->getVert(dm, oldIndex, &source);
877                 dest = CDDM_get_vert(result, newIndex);
878                 
879                 DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
880                 *dest = source;
881         }
882         BLI_ghashIterator_free(hashIter);
883                 
884                 /* edges */
885         for ( hashIter = BLI_ghashIterator_new(edgeHash);
886                   !BLI_ghashIterator_isDone(hashIter);
887                   BLI_ghashIterator_step(hashIter) ) 
888         {
889                 MEdge source;
890                 MEdge *dest;
891                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
892                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
893                 
894                 dm->getEdge(dm, oldIndex, &source);
895                 dest = CDDM_get_edge(result, newIndex);
896                 
897                 source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
898                 source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
899                 
900                 DM_copy_edge_data(dm, result, oldIndex, newIndex, 1);
901                 *dest = source;
902         }
903         BLI_ghashIterator_free(hashIter);
904         
905                 /* faces */
906         for ( hashIter = BLI_ghashIterator_new(faceHash);
907                   !BLI_ghashIterator_isDone(hashIter);
908                   BLI_ghashIterator_step(hashIter) ) 
909         {
910                 MFace source;
911                 MFace *dest;
912                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
913                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
914                 int orig_v4;
915                 
916                 dm->getFace(dm, oldIndex, &source);
917                 dest = CDDM_get_face(result, newIndex);
918                 
919                 orig_v4 = source.v4;
920                 
921                 source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
922                 source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
923                 source.v3 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v3)));
924                 if (source.v4)
925                    source.v4 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v4)));
926                 
927                 DM_copy_face_data(dm, result, oldIndex, newIndex, 1);
928                 *dest = source;
929                 
930                 test_index_face(dest, &result->faceData, newIndex, (orig_v4 ? 4 : 3));
931         }
932         BLI_ghashIterator_free(hashIter);
933         
934         /* recalculate normals */
935         CDDM_calc_normals(result);
936         
937         /* free hashes */
938         BLI_ghash_free(vertHash, NULL, NULL);
939         BLI_ghash_free(edgeHash, NULL, NULL);
940         BLI_ghash_free(faceHash, NULL, NULL);
941         
942         /* return the new mesh */
943         return result;
944 }
945
946 /* Array */
947 /* Array modifier: duplicates the object multiple times along an axis
948 */
949
950 static void arrayModifier_initData(ModifierData *md)
951 {
952         ArrayModifierData *amd = (ArrayModifierData*) md;
953
954         /* default to 2 duplicates distributed along the x-axis by an
955         offset of 1 object-width
956         */
957         amd->start_cap = amd->end_cap = amd->curve_ob = amd->offset_ob = NULL;
958         amd->count = 2;
959         amd->offset[0] = amd->offset[1] = amd->offset[2] = 0;
960         amd->scale[0] = 1;
961         amd->scale[1] = amd->scale[2] = 0;
962         amd->length = 0;
963         amd->merge_dist = 0.01;
964         amd->fit_type = MOD_ARR_FIXEDCOUNT;
965         amd->offset_type = MOD_ARR_OFF_RELATIVE;
966         amd->flags = 0;
967 }
968
969 static void arrayModifier_copyData(ModifierData *md, ModifierData *target)
970 {
971         ArrayModifierData *amd = (ArrayModifierData*) md;
972         ArrayModifierData *tamd = (ArrayModifierData*) target;
973
974         tamd->start_cap = amd->start_cap;
975         tamd->end_cap = amd->end_cap;
976         tamd->curve_ob = amd->curve_ob;
977         tamd->offset_ob = amd->offset_ob;
978         tamd->count = amd->count;
979         VECCOPY(tamd->offset, amd->offset);
980         VECCOPY(tamd->scale, amd->scale);
981         tamd->length = amd->length;
982         tamd->merge_dist = amd->merge_dist;
983         tamd->fit_type = amd->fit_type;
984         tamd->offset_type = amd->offset_type;
985         tamd->flags = amd->flags;
986 }
987
988 static void arrayModifier_foreachObjectLink(
989                                             ModifierData *md, Object *ob,
990          void (*walk)(void *userData, Object *ob, Object **obpoin),
991                 void *userData)
992 {
993         ArrayModifierData *amd = (ArrayModifierData*) md;
994
995         walk(userData, ob, &amd->start_cap);
996         walk(userData, ob, &amd->end_cap);
997         walk(userData, ob, &amd->curve_ob);
998         walk(userData, ob, &amd->offset_ob);
999 }
1000
1001 static void arrayModifier_updateDepgraph(ModifierData *md, DagForest *forest,
1002                                          Object *ob, DagNode *obNode)
1003 {
1004         ArrayModifierData *amd = (ArrayModifierData*) md;
1005
1006         if (amd->start_cap) {
1007                 DagNode *curNode = dag_get_node(forest, amd->start_cap);
1008
1009                 dag_add_relation(forest, curNode, obNode,
1010                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1011         }
1012         if (amd->end_cap) {
1013                 DagNode *curNode = dag_get_node(forest, amd->end_cap);
1014
1015                 dag_add_relation(forest, curNode, obNode,
1016                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1017         }
1018         if (amd->curve_ob) {
1019                 DagNode *curNode = dag_get_node(forest, amd->curve_ob);
1020
1021                 dag_add_relation(forest, curNode, obNode,
1022                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1023         }
1024         if (amd->offset_ob) {
1025                 DagNode *curNode = dag_get_node(forest, amd->offset_ob);
1026
1027                 dag_add_relation(forest, curNode, obNode,
1028                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1029         }
1030 }
1031
1032 float vertarray_size(MVert *mvert, int numVerts, int axis)
1033 {
1034         int i;
1035         float min_co, max_co;
1036
1037         /* if there are no vertices, width is 0 */
1038         if(numVerts == 0) return 0;
1039
1040         /* find the minimum and maximum coordinates on the desired axis */
1041         min_co = max_co = mvert->co[axis];
1042         ++mvert;
1043         for(i = 1; i < numVerts; ++i, ++mvert) {
1044                 if(mvert->co[axis] < min_co) min_co = mvert->co[axis];
1045                 if(mvert->co[axis] > max_co) max_co = mvert->co[axis];
1046         }
1047
1048         return max_co - min_co;
1049 }
1050
1051 typedef struct IndexMapEntry {
1052         /* the new vert index that this old vert index maps to */
1053         int new;
1054         /* -1 if this vert isn't merged, otherwise the old vert index it
1055         * should be replaced with
1056         */
1057         int merge;
1058         /* 1 if this vert's first copy is merged with the last copy of its
1059         * merge target, otherwise 0
1060         */
1061         short merge_final;
1062 } IndexMapEntry;
1063
1064 /* indexMap - an array of IndexMap entries
1065  * oldIndex - the old index to map
1066  * copyNum - the copy number to map to (original = 0, first copy = 1, etc.)
1067  */
1068 static int calc_mapping(IndexMapEntry *indexMap, int oldIndex, int copyNum)
1069 {
1070         if(indexMap[oldIndex].merge < 0) {
1071                 /* vert wasn't merged, so use copy of this vert */
1072                 return indexMap[oldIndex].new + copyNum;
1073         } else if(indexMap[oldIndex].merge == oldIndex) {
1074                 /* vert was merged with itself */
1075                 return indexMap[oldIndex].new;
1076         } else {
1077                 /* vert was merged with another vert */
1078                 /* follow the chain of merges to the end, or until we've passed
1079                 * a number of vertices equal to the copy number
1080                 */
1081                 if(copyNum <= 0)
1082                         return indexMap[oldIndex].new;
1083                 else
1084                         return calc_mapping(indexMap, indexMap[oldIndex].merge,
1085                                             copyNum - 1);
1086         }
1087 }
1088
1089 static DerivedMesh *arrayModifier_doArray(ArrayModifierData *amd,
1090                                           Object *ob, DerivedMesh *dm,
1091        int initFlags)
1092 {
1093         int i, j;
1094         /* offset matrix */
1095         float offset[4][4];
1096         float final_offset[4][4];
1097         float tmp_mat[4][4];
1098         float length = amd->length;
1099         int count = amd->count;
1100         int numVerts, numEdges, numFaces;
1101         int maxVerts, maxEdges, maxFaces;
1102         int finalVerts, finalEdges, finalFaces;
1103         DerivedMesh *result, *start_cap = NULL, *end_cap = NULL;
1104         MVert *mvert, *src_mvert;
1105         MEdge *medge;
1106         MFace *mface;
1107
1108         IndexMapEntry *indexMap;
1109
1110         EdgeHash *edges;
1111
1112         /* need to avoid infinite recursion here */
1113         if(amd->start_cap && amd->start_cap != ob)
1114                 start_cap = mesh_get_derived_final(amd->start_cap, CD_MASK_MESH);
1115         if(amd->end_cap && amd->end_cap != ob)
1116                 end_cap = mesh_get_derived_final(amd->end_cap, CD_MASK_MESH);
1117
1118         MTC_Mat4One(offset);
1119
1120         indexMap = MEM_callocN(sizeof(*indexMap) * dm->getNumVerts(dm),
1121                                "indexmap");
1122
1123         src_mvert = dm->getVertArray(dm);
1124
1125         maxVerts = dm->getNumVerts(dm);
1126
1127         if(amd->offset_type & MOD_ARR_OFF_CONST)
1128                 VecAddf(offset[3], offset[3], amd->offset);
1129         if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
1130                 for(j = 0; j < 3; j++)
1131                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert,
1132                                         maxVerts, j);
1133         }
1134
1135         if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
1136                 float obinv[4][4];
1137                 float result_mat[4][4];
1138
1139                 if(ob)
1140                         MTC_Mat4Invert(obinv, ob->obmat);
1141                 else
1142                         MTC_Mat4One(obinv);
1143
1144                 MTC_Mat4MulSerie(result_mat, offset,
1145                                  obinv, amd->offset_ob->obmat,
1146      NULL, NULL, NULL, NULL, NULL);
1147                 MTC_Mat4CpyMat4(offset, result_mat);
1148         }
1149
1150         if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
1151                 Curve *cu = amd->curve_ob->data;
1152                 if(cu) {
1153                         float tmp_mat[3][3];
1154                         float scale;
1155                         
1156                         object_to_mat3(amd->curve_ob, tmp_mat);
1157                         scale = Mat3ToScalef(tmp_mat);
1158                                 
1159                         if(!cu->path) {
1160                                 cu->flag |= CU_PATH; // needed for path & bevlist
1161                                 makeDispListCurveTypes(amd->curve_ob, 0);
1162                         }
1163                         if(cu->path)
1164                                 length = scale*cu->path->totdist;
1165                 }
1166         }
1167
1168         /* calculate the maximum number of copies which will fit within the
1169         prescribed length */
1170         if(amd->fit_type == MOD_ARR_FITLENGTH
1171                   || amd->fit_type == MOD_ARR_FITCURVE) {
1172                 float dist = sqrt(MTC_dot3Float(offset[3], offset[3]));
1173
1174                 if(dist > 1e-6f)
1175                         /* this gives length = first copy start to last copy end
1176                         add a tiny offset for floating point rounding errors */
1177                         count = (length + 1e-6f) / dist;
1178                 else
1179                         /* if the offset has no translation, just make one copy */
1180                         count = 1;
1181                   }
1182
1183                   if(count < 1)
1184                           count = 1;
1185
1186         /* allocate memory for count duplicates (including original) plus
1187                   * start and end caps
1188         */
1189                   finalVerts = dm->getNumVerts(dm) * count;
1190                   finalEdges = dm->getNumEdges(dm) * count;
1191                   finalFaces = dm->getNumFaces(dm) * count;
1192                   if(start_cap) {
1193                           finalVerts += start_cap->getNumVerts(start_cap);
1194                           finalEdges += start_cap->getNumEdges(start_cap);
1195                           finalFaces += start_cap->getNumFaces(start_cap);
1196                   }
1197                   if(end_cap) {
1198                           finalVerts += end_cap->getNumVerts(end_cap);
1199                           finalEdges += end_cap->getNumEdges(end_cap);
1200                           finalFaces += end_cap->getNumFaces(end_cap);
1201                   }
1202                   result = CDDM_from_template(dm, finalVerts, finalEdges, finalFaces);
1203
1204                   /* calculate the offset matrix of the final copy (for merging) */ 
1205                   MTC_Mat4One(final_offset);
1206
1207                   for(j=0; j < count - 1; j++) {
1208                           MTC_Mat4MulMat4(tmp_mat, final_offset, offset);
1209                           MTC_Mat4CpyMat4(final_offset, tmp_mat);
1210                   }
1211
1212                   numVerts = numEdges = numFaces = 0;
1213                   mvert = CDDM_get_verts(result);
1214
1215                   for (i = 0; i < maxVerts; i++) {
1216                           indexMap[i].merge = -1; /* default to no merge */
1217                           indexMap[i].merge_final = 0; /* default to no merge */
1218                   }
1219
1220                   for (i = 0; i < maxVerts; i++) {
1221                           MVert *inMV;
1222                           MVert *mv = &mvert[numVerts];
1223                           MVert *mv2;
1224                           float co[3];
1225
1226                           inMV = &src_mvert[i];
1227
1228                           DM_copy_vert_data(dm, result, i, numVerts, 1);
1229                           *mv = *inMV;
1230                           numVerts++;
1231
1232                           indexMap[i].new = numVerts - 1;
1233
1234                           VECCOPY(co, mv->co);
1235                 
1236                 /* Attempts to merge verts from one duplicate with verts from the
1237                           * next duplicate which are closer than amd->merge_dist.
1238                           * Only the first such vert pair is merged.
1239                           * If verts are merged in the first duplicate pair, they are merged
1240                           * in all pairs.
1241                 */
1242                           if((count > 1) && (amd->flags & MOD_ARR_MERGE)) {
1243                                   float tmp_co[3];
1244                                   VECCOPY(tmp_co, mv->co);
1245                                   MTC_Mat4MulVecfl(offset, tmp_co);
1246
1247                                   for(j = 0; j < maxVerts; j++) {
1248                                           /* if vertex already merged, don't use it */
1249                                           if( indexMap[j].merge != -1 ) continue;
1250
1251                                           inMV = &src_mvert[j];
1252                                           /* if this vert is within merge limit, merge */
1253                                           if(VecLenCompare(tmp_co, inMV->co, amd->merge_dist)) {
1254                                                   indexMap[i].merge = j;
1255
1256                                                   /* test for merging with final copy of merge target */
1257                                                   if(amd->flags & MOD_ARR_MERGEFINAL) {
1258                                                           VECCOPY(tmp_co, inMV->co);
1259                                                           inMV = &src_mvert[i];
1260                                                           MTC_Mat4MulVecfl(final_offset, tmp_co);
1261                                                           if(VecLenCompare(tmp_co, inMV->co, amd->merge_dist))
1262                                                                   indexMap[i].merge_final = 1;
1263                                                   }
1264                                                   break;
1265                                           }
1266                                   }
1267                           }
1268
1269                           /* if no merging, generate copies of this vert */
1270                           if(indexMap[i].merge < 0) {
1271                                   for(j=0; j < count - 1; j++) {
1272                                           mv2 = &mvert[numVerts];
1273
1274                                           DM_copy_vert_data(result, result, numVerts - 1, numVerts, 1);
1275                                           *mv2 = *mv;
1276                                           numVerts++;
1277
1278                                           MTC_Mat4MulVecfl(offset, co);
1279                                           VECCOPY(mv2->co, co);
1280                                   }
1281                           } else if(indexMap[i].merge != i && indexMap[i].merge_final) {
1282                         /* if this vert is not merging with itself, and it is merging
1283                                   * with the final copy of its merge target, remove the first copy
1284                         */
1285                                   numVerts--;
1286                                   DM_free_vert_data(result, numVerts, 1);
1287                           }
1288                   }
1289
1290                   /* make a hashtable so we can avoid duplicate edges from merging */
1291                   edges = BLI_edgehash_new();
1292
1293                   maxEdges = dm->getNumEdges(dm);
1294                   medge = CDDM_get_edges(result);
1295                   for(i = 0; i < maxEdges; i++) {
1296                           MEdge inMED;
1297                           MEdge med;
1298                           MEdge *med2;
1299                           int vert1, vert2;
1300
1301                           dm->getEdge(dm, i, &inMED);
1302
1303                           med = inMED;
1304                           med.v1 = indexMap[inMED.v1].new;
1305                           med.v2 = indexMap[inMED.v2].new;
1306
1307                 /* if vertices are to be merged with the final copies of their
1308                           * merge targets, calculate that final copy
1309                 */
1310                           if(indexMap[inMED.v1].merge_final) {
1311                                   med.v1 = calc_mapping(indexMap, indexMap[inMED.v1].merge,
1312                                                   count - 1);
1313                           }
1314                           if(indexMap[inMED.v2].merge_final) {
1315                                   med.v2 = calc_mapping(indexMap, indexMap[inMED.v2].merge,
1316                                                   count - 1);
1317                           }
1318
1319                           if(med.v1 == med.v2) continue;
1320
1321                           if (initFlags) {
1322                                   med.flag |= ME_EDGEDRAW | ME_EDGERENDER;
1323                           }
1324
1325                           if(!BLI_edgehash_haskey(edges, med.v1, med.v2)) {
1326                                   DM_copy_edge_data(dm, result, i, numEdges, 1);
1327                                   medge[numEdges] = med;
1328                                   numEdges++;
1329
1330                                   BLI_edgehash_insert(edges, med.v1, med.v2, NULL);
1331                           }
1332
1333                           for(j = 1; j < count; j++)
1334                           {
1335                                   vert1 = calc_mapping(indexMap, inMED.v1, j);
1336                                   vert2 = calc_mapping(indexMap, inMED.v2, j);
1337                                   /* avoid duplicate edges */
1338                                   if(!BLI_edgehash_haskey(edges, vert1, vert2)) {
1339                                           med2 = &medge[numEdges];
1340
1341                                           DM_copy_edge_data(dm, result, i, numEdges, 1);
1342                                           *med2 = med;
1343                                           numEdges++;
1344
1345                                           med2->v1 = vert1;
1346                                           med2->v2 = vert2;
1347
1348                                           BLI_edgehash_insert(edges, med2->v1, med2->v2, NULL);
1349                                   }
1350                           }
1351                   }
1352
1353                   maxFaces = dm->getNumFaces(dm);
1354                   mface = CDDM_get_faces(result);
1355                   for (i=0; i < maxFaces; i++) {
1356                           MFace inMF;
1357                           MFace *mf = &mface[numFaces];
1358
1359                           dm->getFace(dm, i, &inMF);
1360
1361                           DM_copy_face_data(dm, result, i, numFaces, 1);
1362                           *mf = inMF;
1363
1364                           mf->v1 = indexMap[inMF.v1].new;
1365                           mf->v2 = indexMap[inMF.v2].new;
1366                           mf->v3 = indexMap[inMF.v3].new;
1367                           if(inMF.v4)
1368                                   mf->v4 = indexMap[inMF.v4].new;
1369
1370                 /* if vertices are to be merged with the final copies of their
1371                           * merge targets, calculate that final copy
1372                 */
1373                           if(indexMap[inMF.v1].merge_final)
1374                                   mf->v1 = calc_mapping(indexMap, indexMap[inMF.v1].merge, count-1);
1375                           if(indexMap[inMF.v2].merge_final)
1376                                   mf->v2 = calc_mapping(indexMap, indexMap[inMF.v2].merge, count-1);
1377                           if(indexMap[inMF.v3].merge_final)
1378                                   mf->v3 = calc_mapping(indexMap, indexMap[inMF.v3].merge, count-1);
1379                           if(inMF.v4 && indexMap[inMF.v4].merge_final)
1380                                   mf->v4 = calc_mapping(indexMap, indexMap[inMF.v4].merge, count-1);
1381
1382                           if(test_index_face(mf, &result->faceData, numFaces, inMF.v4?4:3) < 3)
1383                                   continue;
1384
1385                           numFaces++;
1386
1387                           /* if the face has fewer than 3 vertices, don't create it */
1388                           if(mf->v3 == 0 || (mf->v1 && (mf->v1 == mf->v3 || mf->v1 == mf->v4))) {
1389                                   numFaces--;
1390                                   DM_free_face_data(result, numFaces, 1);
1391                           }
1392
1393                           for(j = 1; j < count; j++)
1394                           {
1395                                   MFace *mf2 = &mface[numFaces];
1396
1397                                   DM_copy_face_data(dm, result, i, numFaces, 1);
1398                                   *mf2 = *mf;
1399
1400                                   mf2->v1 = calc_mapping(indexMap, inMF.v1, j);
1401                                   mf2->v2 = calc_mapping(indexMap, inMF.v2, j);
1402                                   mf2->v3 = calc_mapping(indexMap, inMF.v3, j);
1403                                   if (inMF.v4)
1404                                           mf2->v4 = calc_mapping(indexMap, inMF.v4, j);
1405
1406                                   test_index_face(mf2, &result->faceData, numFaces, inMF.v4?4:3);
1407                                   numFaces++;
1408
1409                                   /* if the face has fewer than 3 vertices, don't create it */
1410                                   if(mf2->v3 == 0 || (mf2->v1 && (mf2->v1 == mf2->v3 || mf2->v1 ==
1411                                                                  mf2->v4))) {
1412                                           numFaces--;
1413                                           DM_free_face_data(result, numFaces, 1);
1414                                                                  }
1415                           }
1416                   }
1417
1418                   /* add start and end caps */
1419                   if(start_cap) {
1420                           float startoffset[4][4];
1421                           MVert *cap_mvert;
1422                           MEdge *cap_medge;
1423                           MFace *cap_mface;
1424                           int *origindex;
1425                           int *vert_map;
1426                           int capVerts, capEdges, capFaces;
1427
1428                           capVerts = start_cap->getNumVerts(start_cap);
1429                           capEdges = start_cap->getNumEdges(start_cap);
1430                           capFaces = start_cap->getNumFaces(start_cap);
1431                           cap_mvert = start_cap->getVertArray(start_cap);
1432                           cap_medge = start_cap->getEdgeArray(start_cap);
1433                           cap_mface = start_cap->getFaceArray(start_cap);
1434
1435                           Mat4Invert(startoffset, offset);
1436
1437                           vert_map = MEM_callocN(sizeof(*vert_map) * capVerts,
1438                                           "arrayModifier_doArray vert_map");
1439
1440                           origindex = result->getVertDataArray(result, CD_ORIGINDEX);
1441                           for(i = 0; i < capVerts; i++) {
1442                                   MVert *mv = &cap_mvert[i];
1443                                   short merged = 0;
1444
1445                                   if(amd->flags & MOD_ARR_MERGE) {
1446                                           float tmp_co[3];
1447                                           MVert *in_mv;
1448                                           int j;
1449
1450                                           VECCOPY(tmp_co, mv->co);
1451                                           Mat4MulVecfl(startoffset, tmp_co);
1452
1453                                           for(j = 0; j < maxVerts; j++) {
1454                                                   in_mv = &src_mvert[j];
1455                                                   /* if this vert is within merge limit, merge */
1456                                                   if(VecLenCompare(tmp_co, in_mv->co, amd->merge_dist)) {
1457                                                           vert_map[i] = calc_mapping(indexMap, j, 0);
1458                                                           merged = 1;
1459                                                           break;
1460                                                   }
1461                                           }
1462                                   }
1463
1464                                   if(!merged) {
1465                                           DM_copy_vert_data(start_cap, result, i, numVerts, 1);
1466                                           mvert[numVerts] = *mv;
1467                                           Mat4MulVecfl(startoffset, mvert[numVerts].co);
1468                                           origindex[numVerts] = ORIGINDEX_NONE;
1469
1470                                           vert_map[i] = numVerts;
1471
1472                                           numVerts++;
1473                                   }
1474                           }
1475                           origindex = result->getEdgeDataArray(result, CD_ORIGINDEX);
1476                           for(i = 0; i < capEdges; i++) {
1477                                   int v1, v2;
1478
1479                                   v1 = vert_map[cap_medge[i].v1];
1480                                   v2 = vert_map[cap_medge[i].v2];
1481
1482                                   if(!BLI_edgehash_haskey(edges, v1, v2)) {
1483                                           DM_copy_edge_data(start_cap, result, i, numEdges, 1);
1484                                           medge[numEdges] = cap_medge[i];
1485                                           medge[numEdges].v1 = v1;
1486                                           medge[numEdges].v2 = v2;
1487                                           origindex[numEdges] = ORIGINDEX_NONE;
1488
1489                                           numEdges++;
1490                                   }
1491                           }
1492                           origindex = result->getFaceDataArray(result, CD_ORIGINDEX);
1493                           for(i = 0; i < capFaces; i++) {
1494                                   DM_copy_face_data(start_cap, result, i, numFaces, 1);
1495                                   mface[numFaces] = cap_mface[i];
1496                                   mface[numFaces].v1 = vert_map[mface[numFaces].v1];
1497                                   mface[numFaces].v2 = vert_map[mface[numFaces].v2];
1498                                   mface[numFaces].v3 = vert_map[mface[numFaces].v3];
1499                                   if(mface[numFaces].v4) {
1500                                           mface[numFaces].v4 = vert_map[mface[numFaces].v4];
1501
1502                                           test_index_face(&mface[numFaces], &result->faceData,
1503                                                           numFaces, 4);
1504                                   }
1505                                   else
1506                                   {
1507                                           test_index_face(&mface[numFaces], &result->faceData,
1508                                                           numFaces, 3);
1509                                   }
1510
1511                                   origindex[numFaces] = ORIGINDEX_NONE;
1512
1513                                   numFaces++;
1514                           }
1515
1516                           MEM_freeN(vert_map);
1517                           start_cap->release(start_cap);
1518                   }
1519
1520                   if(end_cap) {
1521                           float endoffset[4][4];
1522                           MVert *cap_mvert;
1523                           MEdge *cap_medge;
1524                           MFace *cap_mface;
1525                           int *origindex;
1526                           int *vert_map;
1527                           int capVerts, capEdges, capFaces;
1528
1529                           capVerts = end_cap->getNumVerts(end_cap);
1530                           capEdges = end_cap->getNumEdges(end_cap);
1531                           capFaces = end_cap->getNumFaces(end_cap);
1532                           cap_mvert = end_cap->getVertArray(end_cap);
1533                           cap_medge = end_cap->getEdgeArray(end_cap);
1534                           cap_mface = end_cap->getFaceArray(end_cap);
1535
1536                           Mat4MulMat4(endoffset, final_offset, offset);
1537
1538                           vert_map = MEM_callocN(sizeof(*vert_map) * capVerts,
1539                                           "arrayModifier_doArray vert_map");
1540
1541                           origindex = result->getVertDataArray(result, CD_ORIGINDEX);
1542                           for(i = 0; i < capVerts; i++) {
1543                                   MVert *mv = &cap_mvert[i];
1544                                   short merged = 0;
1545
1546                                   if(amd->flags & MOD_ARR_MERGE) {
1547                                           float tmp_co[3];
1548                                           MVert *in_mv;
1549                                           int j;
1550
1551                                           VECCOPY(tmp_co, mv->co);
1552                                           Mat4MulVecfl(offset, tmp_co);
1553
1554                                           for(j = 0; j < maxVerts; j++) {
1555                                                   in_mv = &src_mvert[j];
1556                                                   /* if this vert is within merge limit, merge */
1557                                                   if(VecLenCompare(tmp_co, in_mv->co, amd->merge_dist)) {
1558                                                           vert_map[i] = calc_mapping(indexMap, j, count - 1);
1559                                                           merged = 1;
1560                                                           break;
1561                                                   }
1562                                           }
1563                                   }
1564
1565                                   if(!merged) {
1566                                           DM_copy_vert_data(end_cap, result, i, numVerts, 1);
1567                                           mvert[numVerts] = *mv;
1568                                           Mat4MulVecfl(endoffset, mvert[numVerts].co);
1569                                           origindex[numVerts] = ORIGINDEX_NONE;
1570
1571                                           vert_map[i] = numVerts;
1572
1573                                           numVerts++;
1574                                   }
1575                           }
1576                           origindex = result->getEdgeDataArray(result, CD_ORIGINDEX);
1577                           for(i = 0; i < capEdges; i++) {
1578                                   int v1, v2;
1579
1580                                   v1 = vert_map[cap_medge[i].v1];
1581                                   v2 = vert_map[cap_medge[i].v2];
1582
1583                                   if(!BLI_edgehash_haskey(edges, v1, v2)) {
1584                                           DM_copy_edge_data(end_cap, result, i, numEdges, 1);
1585                                           medge[numEdges] = cap_medge[i];
1586                                           medge[numEdges].v1 = v1;
1587                                           medge[numEdges].v2 = v2;
1588                                           origindex[numEdges] = ORIGINDEX_NONE;
1589
1590                                           numEdges++;
1591                                   }
1592                           }
1593                           origindex = result->getFaceDataArray(result, CD_ORIGINDEX);
1594                           for(i = 0; i < capFaces; i++) {
1595                                   DM_copy_face_data(end_cap, result, i, numFaces, 1);
1596                                   mface[numFaces] = cap_mface[i];
1597                                   mface[numFaces].v1 = vert_map[mface[numFaces].v1];
1598                                   mface[numFaces].v2 = vert_map[mface[numFaces].v2];
1599                                   mface[numFaces].v3 = vert_map[mface[numFaces].v3];
1600                                   if(mface[numFaces].v4) {
1601                                           mface[numFaces].v4 = vert_map[mface[numFaces].v4];
1602
1603                                           test_index_face(&mface[numFaces], &result->faceData,
1604                                                           numFaces, 4);
1605                                   }
1606                                   else
1607                                   {
1608                                           test_index_face(&mface[numFaces], &result->faceData,
1609                                                           numFaces, 3);
1610                                   }
1611                                   origindex[numFaces] = ORIGINDEX_NONE;
1612
1613                                   numFaces++;
1614                           }
1615
1616                           MEM_freeN(vert_map);
1617                           end_cap->release(end_cap);
1618                   }
1619
1620                   BLI_edgehash_free(edges, NULL);
1621                   MEM_freeN(indexMap);
1622
1623                   CDDM_lower_num_verts(result, numVerts);
1624                   CDDM_lower_num_edges(result, numEdges);
1625                   CDDM_lower_num_faces(result, numFaces);
1626
1627                   return result;
1628 }
1629
1630 static DerivedMesh *arrayModifier_applyModifier(
1631                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
1632   int useRenderParams, int isFinalCalc)
1633 {
1634         DerivedMesh *result;
1635         ArrayModifierData *amd = (ArrayModifierData*) md;
1636
1637         result = arrayModifier_doArray(amd, ob, derivedData, 0);
1638
1639         if(result != derivedData)
1640                 CDDM_calc_normals(result);
1641
1642         return result;
1643 }
1644
1645 static DerivedMesh *arrayModifier_applyModifierEM(
1646                 ModifierData *md, Object *ob, EditMesh *editData,
1647   DerivedMesh *derivedData)
1648 {
1649         return arrayModifier_applyModifier(md, ob, derivedData, 0, 1);
1650 }
1651
1652 /* Mirror */
1653
1654 static void mirrorModifier_initData(ModifierData *md)
1655 {
1656         MirrorModifierData *mmd = (MirrorModifierData*) md;
1657
1658         mmd->flag |= (MOD_MIR_AXIS_X | MOD_MIR_VGROUP);
1659         mmd->tolerance = 0.001;
1660         mmd->mirror_ob = NULL;
1661 }
1662
1663 static void mirrorModifier_copyData(ModifierData *md, ModifierData *target)
1664 {
1665         MirrorModifierData *mmd = (MirrorModifierData*) md;
1666         MirrorModifierData *tmmd = (MirrorModifierData*) target;
1667
1668         tmmd->axis = mmd->axis;
1669         tmmd->flag = mmd->flag;
1670         tmmd->tolerance = mmd->tolerance;
1671         tmmd->mirror_ob = mmd->mirror_ob;;
1672 }
1673
1674 static void mirrorModifier_foreachObjectLink(
1675                                              ModifierData *md, Object *ob,
1676           void (*walk)(void *userData, Object *ob, Object **obpoin),
1677                  void *userData)
1678 {
1679         MirrorModifierData *mmd = (MirrorModifierData*) md;
1680
1681         walk(userData, ob, &mmd->mirror_ob);
1682 }
1683
1684 static void mirrorModifier_updateDepgraph(ModifierData *md, DagForest *forest,
1685                                           Object *ob, DagNode *obNode)
1686 {
1687         MirrorModifierData *mmd = (MirrorModifierData*) md;
1688
1689         if(mmd->mirror_ob) {
1690                 DagNode *latNode = dag_get_node(forest, mmd->mirror_ob);
1691
1692                 dag_add_relation(forest, latNode, obNode,
1693                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Mirror Modifier");
1694         }
1695 }
1696
1697 /* finds the best possible flipped name. For renaming; check for unique names afterwards */
1698 /* if strip_number: removes number extensions */
1699 void vertgroup_flip_name (char *name, int strip_number)
1700 {
1701         int     len;
1702         char    prefix[128]={""};   /* The part before the facing */
1703         char    suffix[128]={""};   /* The part after the facing */
1704         char    replace[128]={""};  /* The replacement string */
1705         char    number[128]={""};   /* The number extension string */
1706         char    *index=NULL;
1707
1708         len= strlen(name);
1709         if(len<3) return; // we don't do names like .R or .L
1710
1711         /* We first check the case with a .### extension, let's find the last period */
1712         if(isdigit(name[len-1])) {
1713                 index= strrchr(name, '.'); // last occurrance
1714                 if (index && isdigit(index[1]) ) { // doesnt handle case bone.1abc2 correct..., whatever!
1715                         if(strip_number==0) 
1716                                 strcpy(number, index);
1717                         *index= 0;
1718                         len= strlen(name);
1719                 }
1720         }
1721
1722         strcpy (prefix, name);
1723
1724 #define IS_SEPARATOR(a) ((a)=='.' || (a)==' ' || (a)=='-' || (a)=='_')
1725
1726         /* first case; separator . - _ with extensions r R l L  */
1727         if( IS_SEPARATOR(name[len-2]) ) {
1728                 switch(name[len-1]) {
1729                         case 'l':
1730                                 prefix[len-1]= 0;
1731                                 strcpy(replace, "r");
1732                                 break;
1733                         case 'r':
1734                                 prefix[len-1]= 0;
1735                                 strcpy(replace, "l");
1736                                 break;
1737                         case 'L':
1738                                 prefix[len-1]= 0;
1739                                 strcpy(replace, "R");
1740                                 break;
1741                         case 'R':
1742                                 prefix[len-1]= 0;
1743                                 strcpy(replace, "L");
1744                                 break;
1745                 }
1746         }
1747         /* case; beginning with r R l L , with separator after it */
1748         else if( IS_SEPARATOR(name[1]) ) {
1749                 switch(name[0]) {
1750                         case 'l':
1751                                 strcpy(replace, "r");
1752                                 strcpy(suffix, name+1);
1753                                 prefix[0]= 0;
1754                                 break;
1755                         case 'r':
1756                                 strcpy(replace, "l");
1757                                 strcpy(suffix, name+1);
1758                                 prefix[0]= 0;
1759                                 break;
1760                         case 'L':
1761                                 strcpy(replace, "R");
1762                                 strcpy(suffix, name+1);
1763                                 prefix[0]= 0;
1764                                 break;
1765                         case 'R':
1766                                 strcpy(replace, "L");
1767                                 strcpy(suffix, name+1);
1768                                 prefix[0]= 0;
1769                                 break;
1770                 }
1771         }
1772         else if(len > 5) {
1773                 /* hrms, why test for a separator? lets do the rule 'ultimate left or right' */
1774                 index = BLI_strcasestr(prefix, "right");
1775                 if (index==prefix || index==prefix+len-5) {
1776                         if(index[0]=='r') 
1777                                 strcpy (replace, "left");
1778                         else {
1779                                 if(index[1]=='I') 
1780                                         strcpy (replace, "LEFT");
1781                                 else
1782                                         strcpy (replace, "Left");
1783                         }
1784                         *index= 0;
1785                         strcpy (suffix, index+5);
1786                 }
1787                 else {
1788                         index = BLI_strcasestr(prefix, "left");
1789                         if (index==prefix || index==prefix+len-4) {
1790                                 if(index[0]=='l') 
1791                                         strcpy (replace, "right");
1792                                 else {
1793                                         if(index[1]=='E') 
1794                                                 strcpy (replace, "RIGHT");
1795                                         else
1796                                                 strcpy (replace, "Right");
1797                                 }
1798                                 *index= 0;
1799                                 strcpy (suffix, index+4);
1800                         }
1801                 }
1802         }
1803
1804 #undef IS_SEPARATOR
1805
1806         sprintf (name, "%s%s%s%s", prefix, replace, suffix, number);
1807 }
1808
1809 static DerivedMesh *doMirrorOnAxis(MirrorModifierData *mmd,
1810                 Object *ob,
1811                 DerivedMesh *dm,
1812                 int initFlags,
1813                 int axis)
1814 {
1815         int i;
1816         float tolerance = mmd->tolerance;
1817         DerivedMesh *result;
1818         int numVerts, numEdges, numFaces;
1819         int maxVerts = dm->getNumVerts(dm);
1820         int maxEdges = dm->getNumEdges(dm);
1821         int maxFaces = dm->getNumFaces(dm);
1822         int vector_size=0, j, a, b;
1823         bDeformGroup *def, *defb;
1824         bDeformGroup **vector_def = NULL;
1825         int (*indexMap)[2];
1826         float mtx[4][4], imtx[4][4];
1827
1828         numVerts = numEdges = numFaces = 0;
1829
1830         indexMap = MEM_mallocN(sizeof(*indexMap) * maxVerts, "indexmap");
1831
1832         result = CDDM_from_template(dm, maxVerts * 2, maxEdges * 2, maxFaces * 2);
1833
1834
1835         if (mmd->flag & MOD_MIR_VGROUP) {
1836                 /* calculate the number of deformedGroups */
1837                 for(vector_size = 0, def = ob->defbase.first; def;
1838                     def = def->next, vector_size++);
1839
1840                 /* load the deformedGroups for fast access */
1841                 vector_def =
1842                     (bDeformGroup **)MEM_mallocN(sizeof(bDeformGroup*) * vector_size,
1843                                                  "group_index");
1844                 for(a = 0, def = ob->defbase.first; def; def = def->next, a++) {
1845                         vector_def[a] = def;
1846                 }
1847         }
1848
1849         if (mmd->mirror_ob) {
1850                 float obinv[4][4];
1851                 
1852                 Mat4Invert(obinv, mmd->mirror_ob->obmat);
1853                 Mat4MulMat4(mtx, ob->obmat, obinv);
1854                 Mat4Invert(imtx, mtx);
1855         }
1856
1857         for(i = 0; i < maxVerts; i++) {
1858                 MVert inMV;
1859                 MVert *mv = CDDM_get_vert(result, numVerts);
1860                 int isShared;
1861                 float co[3];
1862                 
1863                 dm->getVert(dm, i, &inMV);
1864                 
1865                 VecCopyf(co, inMV.co);
1866                 
1867                 if (mmd->mirror_ob) {
1868                         VecMat4MulVecfl(co, mtx, co);
1869                 }
1870                 isShared = ABS(co[axis])<=tolerance;
1871                 
1872                 /* Because the topology result (# of vertices) must be the same if
1873                 * the mesh data is overridden by vertex cos, have to calc sharedness
1874                 * based on original coordinates. This is why we test before copy.
1875                 */
1876                 DM_copy_vert_data(dm, result, i, numVerts, 1);
1877                 *mv = inMV;
1878                 numVerts++;
1879                 
1880                 indexMap[i][0] = numVerts - 1;
1881                 indexMap[i][1] = !isShared;
1882                 
1883                 if(isShared) {
1884                         co[axis] = 0;
1885                         if (mmd->mirror_ob) {
1886                                 VecMat4MulVecfl(co, imtx, co);
1887                         }
1888                         VecCopyf(mv->co, co);
1889                         
1890                         mv->flag |= ME_VERT_MERGED;
1891                 } else {
1892                         MVert *mv2 = CDDM_get_vert(result, numVerts);
1893                         MDeformVert *dvert = NULL;
1894                         
1895                         DM_copy_vert_data(dm, result, i, numVerts, 1);
1896                         *mv2 = *mv;
1897                         
1898                         co[axis] = -co[axis];
1899                         if (mmd->mirror_ob) {
1900                                 VecMat4MulVecfl(co, imtx, co);
1901                         }
1902                         VecCopyf(mv2->co, co);
1903                         
1904                         if (mmd->flag & MOD_MIR_VGROUP){
1905                                 dvert = DM_get_vert_data(result, numVerts, CD_MDEFORMVERT);
1906                                 
1907                                 if (dvert)
1908                                 {
1909                                         for(j = 0; j < dvert[0].totweight; ++j)
1910                                         {
1911                                                 char tmpname[32];
1912                                                 
1913                                                 if(dvert->dw[j].def_nr < 0 ||
1914                                                    dvert->dw[j].def_nr >= vector_size)
1915                                                         continue;
1916                                                 
1917                                                 def = vector_def[dvert->dw[j].def_nr];
1918                                                 strcpy(tmpname, def->name);
1919                                                 vertgroup_flip_name(tmpname,0);
1920                                                 
1921                                                 for(b = 0, defb = ob->defbase.first; defb;
1922                                                     defb = defb->next, b++)
1923                                                 {
1924                                                         if(!strcmp(defb->name, tmpname))
1925                                                         {
1926                                                                 dvert->dw[j].def_nr = b;
1927                                                                 break;
1928                                                         }
1929                                                 }
1930                                         }
1931                                 }
1932                         }
1933                         
1934                         numVerts++;
1935                 }
1936         }
1937
1938         for(i = 0; i < maxEdges; i++) {
1939                 MEdge inMED;
1940                 MEdge *med = CDDM_get_edge(result, numEdges);
1941                 
1942                 dm->getEdge(dm, i, &inMED);
1943                 
1944                 DM_copy_edge_data(dm, result, i, numEdges, 1);
1945                 *med = inMED;
1946                 numEdges++;
1947                 
1948                 med->v1 = indexMap[inMED.v1][0];
1949                 med->v2 = indexMap[inMED.v2][0];
1950                 if(initFlags)
1951                         med->flag |= ME_EDGEDRAW | ME_EDGERENDER;
1952                 
1953                 if(indexMap[inMED.v1][1] || indexMap[inMED.v2][1]) {
1954                         MEdge *med2 = CDDM_get_edge(result, numEdges);
1955                         
1956                         DM_copy_edge_data(dm, result, i, numEdges, 1);
1957                         *med2 = *med;
1958                         numEdges++;
1959                         
1960                         med2->v1 += indexMap[inMED.v1][1];
1961                         med2->v2 += indexMap[inMED.v2][1];
1962                 }
1963         }
1964
1965         for(i = 0; i < maxFaces; i++) {
1966                 MFace inMF;
1967                 MFace *mf = CDDM_get_face(result, numFaces);
1968                 
1969                 dm->getFace(dm, i, &inMF);
1970                 
1971                 DM_copy_face_data(dm, result, i, numFaces, 1);
1972                 *mf = inMF;
1973                 numFaces++;
1974                 
1975                 mf->v1 = indexMap[inMF.v1][0];
1976                 mf->v2 = indexMap[inMF.v2][0];
1977                 mf->v3 = indexMap[inMF.v3][0];
1978                 mf->v4 = indexMap[inMF.v4][0];
1979                 
1980                 if(indexMap[inMF.v1][1]
1981                                  || indexMap[inMF.v2][1]
1982                                  || indexMap[inMF.v3][1]
1983                                  || (mf->v4 && indexMap[inMF.v4][1])) {
1984                         MFace *mf2 = CDDM_get_face(result, numFaces);
1985                         static int corner_indices[4] = {2, 1, 0, 3};
1986                         
1987                         DM_copy_face_data(dm, result, i, numFaces, 1);
1988                         *mf2 = *mf;
1989                         
1990                         mf2->v1 += indexMap[inMF.v1][1];
1991                         mf2->v2 += indexMap[inMF.v2][1];
1992                         mf2->v3 += indexMap[inMF.v3][1];
1993                         if(inMF.v4) mf2->v4 += indexMap[inMF.v4][1];
1994                         
1995                         /* mirror UVs if enabled */
1996                         if(mmd->flag & (MOD_MIR_MIRROR_U | MOD_MIR_MIRROR_V)) {
1997                                 MTFace *tf = result->getFaceData(result, numFaces, CD_MTFACE);
1998                                 if(tf) {
1999                                         int j;
2000                                         for(j = 0; j < 4; ++j) {
2001                                                 if(mmd->flag & MOD_MIR_MIRROR_U)
2002                                                         tf->uv[j][0] = 1.0f - tf->uv[j][0];
2003                                                 if(mmd->flag & MOD_MIR_MIRROR_V)
2004                                                         tf->uv[j][1] = 1.0f - tf->uv[j][1];
2005                                         }
2006                                 }
2007                         }
2008                         
2009                         /* Flip face normal */
2010                         SWAP(int, mf2->v1, mf2->v3);
2011                         DM_swap_face_data(result, numFaces, corner_indices);
2012                         
2013                         test_index_face(mf2, &result->faceData, numFaces, inMF.v4?4:3);
2014                         numFaces++;
2015                 }
2016         }
2017
2018         if (vector_def) MEM_freeN(vector_def);
2019
2020         MEM_freeN(indexMap);
2021
2022         CDDM_lower_num_verts(result, numVerts);
2023         CDDM_lower_num_edges(result, numEdges);
2024         CDDM_lower_num_faces(result, numFaces);
2025
2026         return result;
2027 }
2028
2029 static DerivedMesh *mirrorModifier__doMirror(MirrorModifierData *mmd,
2030                                             Object *ob, DerivedMesh *dm,
2031                                                 int initFlags)
2032 {
2033         DerivedMesh *result = dm;
2034
2035         /* check which axes have been toggled and mirror accordingly */
2036         if(mmd->flag & MOD_MIR_AXIS_X) {
2037                 result = doMirrorOnAxis(mmd, ob, result, initFlags, 0);
2038         }
2039         if(mmd->flag & MOD_MIR_AXIS_Y) {
2040                 DerivedMesh *tmp = result;
2041                 result = doMirrorOnAxis(mmd, ob, result, initFlags, 1);
2042                 if(tmp != dm) tmp->release(tmp); /* free intermediate results */
2043         }
2044         if(mmd->flag & MOD_MIR_AXIS_Z) {
2045                 DerivedMesh *tmp = result;
2046                 result = doMirrorOnAxis(mmd, ob, result, initFlags, 2);
2047                 if(tmp != dm) tmp->release(tmp); /* free intermediate results */
2048         }
2049
2050         return result;
2051 }
2052
2053 static DerivedMesh *mirrorModifier_applyModifier(
2054                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
2055   int useRenderParams, int isFinalCalc)
2056 {
2057         DerivedMesh *result;
2058         MirrorModifierData *mmd = (MirrorModifierData*) md;
2059
2060         result = mirrorModifier__doMirror(mmd, ob, derivedData, 0);
2061
2062         if(result != derivedData)
2063                 CDDM_calc_normals(result);
2064         
2065         return result;
2066 }
2067
2068 static DerivedMesh *mirrorModifier_applyModifierEM(
2069                 ModifierData *md, Object *ob, EditMesh *editData,
2070   DerivedMesh *derivedData)
2071 {
2072         return mirrorModifier_applyModifier(md, ob, derivedData, 0, 1);
2073 }
2074
2075 /* EdgeSplit */
2076 /* EdgeSplit modifier: Splits edges in the mesh according to sharpness flag
2077  * or edge angle (can be used to achieve autosmoothing)
2078 */
2079 #if 0
2080 #define EDGESPLIT_DEBUG_3
2081 #define EDGESPLIT_DEBUG_2
2082 #define EDGESPLIT_DEBUG_1
2083 #define EDGESPLIT_DEBUG_0
2084 #endif
2085
2086 static void edgesplitModifier_initData(ModifierData *md)
2087 {
2088         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
2089
2090         /* default to 30-degree split angle, sharpness from both angle & flag
2091         */
2092         emd->split_angle = 30;
2093         emd->flags = MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG;
2094 }
2095
2096 static void edgesplitModifier_copyData(ModifierData *md, ModifierData *target)
2097 {
2098         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
2099         EdgeSplitModifierData *temd = (EdgeSplitModifierData*) target;
2100
2101         temd->split_angle = emd->split_angle;
2102         temd->flags = emd->flags;
2103 }
2104
2105 /* Mesh data for edgesplit operation */
2106 typedef struct SmoothVert {
2107         LinkNode *faces;     /* all faces which use this vert */
2108         int oldIndex; /* the index of the original DerivedMesh vert */
2109         int newIndex; /* the index of the new DerivedMesh vert */
2110 } SmoothVert;
2111
2112 #define SMOOTHEDGE_NUM_VERTS 2
2113
2114 typedef struct SmoothEdge {
2115         SmoothVert *verts[SMOOTHEDGE_NUM_VERTS]; /* the verts used by this edge */
2116         LinkNode *faces;     /* all faces which use this edge */
2117         int oldIndex; /* the index of the original DerivedMesh edge */
2118         int newIndex; /* the index of the new DerivedMesh edge */
2119         short flag; /* the flags from the original DerivedMesh edge */
2120 } SmoothEdge;
2121
2122 #define SMOOTHFACE_MAX_EDGES 4
2123
2124 typedef struct SmoothFace {
2125         SmoothEdge *edges[SMOOTHFACE_MAX_EDGES]; /* nonexistent edges == NULL */
2126         int flip[SMOOTHFACE_MAX_EDGES]; /* 1 = flip edge dir, 0 = don't flip */
2127         float normal[3]; /* the normal of this face */
2128         int oldIndex; /* the index of the original DerivedMesh face */
2129         int newIndex; /* the index of the new DerivedMesh face */
2130 } SmoothFace;
2131
2132 typedef struct SmoothMesh {
2133         SmoothVert *verts;
2134         SmoothEdge *edges;
2135         SmoothFace *faces;
2136         int num_verts, num_edges, num_faces;
2137         int max_verts, max_edges, max_faces;
2138         DerivedMesh *dm;
2139         float threshold; /* the cosine of the smoothing angle */
2140         int flags;
2141 } SmoothMesh;
2142
2143 static SmoothVert *smoothvert_copy(SmoothVert *vert, SmoothMesh *mesh)
2144 {
2145         SmoothVert *copy = &mesh->verts[mesh->num_verts];
2146
2147         if(mesh->num_verts >= mesh->max_verts) {
2148                 printf("Attempted to add a SmoothMesh vert beyond end of array\n");
2149                 return NULL;
2150         }
2151
2152         *copy = *vert;
2153         copy->faces = NULL;
2154         copy->newIndex = mesh->num_verts;
2155         ++mesh->num_verts;
2156
2157 #ifdef EDGESPLIT_DEBUG_2
2158         printf("copied vert %4d to vert %4d\n", vert->newIndex, copy->newIndex);
2159 #endif
2160         return copy;
2161 }
2162
2163 static SmoothEdge *smoothedge_copy(SmoothEdge *edge, SmoothMesh *mesh)
2164 {
2165         SmoothEdge *copy = &mesh->edges[mesh->num_edges];
2166
2167         if(mesh->num_edges >= mesh->max_edges) {
2168                 printf("Attempted to add a SmoothMesh edge beyond end of array\n");
2169                 return NULL;
2170         }
2171
2172         *copy = *edge;
2173         copy->faces = NULL;
2174         copy->newIndex = mesh->num_edges;
2175         ++mesh->num_edges;
2176
2177 #ifdef EDGESPLIT_DEBUG_2
2178         printf("copied edge %4d to edge %4d\n", edge->newIndex, copy->newIndex);
2179 #endif
2180         return copy;
2181 }
2182
2183 static int smoothedge_has_vert(SmoothEdge *edge, SmoothVert *vert)
2184 {
2185         int i;
2186         for(i = 0; i < SMOOTHEDGE_NUM_VERTS; i++)
2187                 if(edge->verts[i] == vert) return 1;
2188
2189         return 0;
2190 }
2191
2192 static SmoothMesh *smoothmesh_new(int num_verts, int num_edges, int num_faces,
2193                                   int max_verts, int max_edges, int max_faces)
2194 {
2195         SmoothMesh *mesh = MEM_callocN(sizeof(*mesh), "smoothmesh");
2196         mesh->verts = MEM_callocN(sizeof(*mesh->verts) * max_verts,
2197                                   "SmoothMesh.verts");
2198         mesh->edges = MEM_callocN(sizeof(*mesh->edges) * max_edges,
2199                                   "SmoothMesh.edges");
2200         mesh->faces = MEM_callocN(sizeof(*mesh->faces) * max_faces,
2201                                   "SmoothMesh.faces");
2202
2203         mesh->num_verts = num_verts;
2204         mesh->num_edges = num_edges;
2205         mesh->num_faces = num_faces;
2206
2207         mesh->max_verts = max_verts;
2208         mesh->max_edges = max_edges;
2209         mesh->max_faces = max_faces;
2210
2211         return mesh;
2212 }
2213
2214 static void smoothmesh_free(SmoothMesh *mesh)
2215 {
2216         int i;
2217
2218         for(i = 0; i < mesh->num_verts; ++i)
2219                 BLI_linklist_free(mesh->verts[i].faces, NULL);
2220
2221         for(i = 0; i < mesh->num_edges; ++i)
2222                 BLI_linklist_free(mesh->edges[i].faces, NULL);
2223
2224         MEM_freeN(mesh->verts);
2225         MEM_freeN(mesh->edges);
2226         MEM_freeN(mesh->faces);
2227         MEM_freeN(mesh);
2228 }
2229
2230 static void smoothmesh_resize_verts(SmoothMesh *mesh, int max_verts)
2231 {
2232         int i;
2233         SmoothVert *tmp;
2234
2235         if(max_verts <= mesh->max_verts) return;
2236
2237         tmp = MEM_callocN(sizeof(*tmp) * max_verts, "SmoothMesh.verts");
2238
2239         memcpy(tmp, mesh->verts, sizeof(*tmp) * mesh->num_verts);
2240
2241         /* remap vert pointers in edges */
2242         for(i = 0; i < mesh->num_edges; ++i) {
2243                 int j;
2244                 SmoothEdge *edge = &mesh->edges[i];
2245
2246                 for(j = 0; j < SMOOTHEDGE_NUM_VERTS; ++j)
2247                         /* pointer arithmetic to get vert array index */
2248                         edge->verts[j] = &tmp[edge->verts[j] - mesh->verts];
2249         }
2250
2251         MEM_freeN(mesh->verts);
2252         mesh->verts = tmp;
2253         mesh->max_verts = max_verts;
2254 }
2255
2256 static void smoothmesh_resize_edges(SmoothMesh *mesh, int max_edges)
2257 {
2258         int i;
2259         SmoothEdge *tmp;
2260
2261         if(max_edges <= mesh->max_edges) return;
2262
2263         tmp = MEM_callocN(sizeof(*tmp) * max_edges, "SmoothMesh.edges");
2264
2265         memcpy(tmp, mesh->edges, sizeof(*tmp) * mesh->num_edges);
2266
2267         /* remap edge pointers in faces */
2268         for(i = 0; i < mesh->num_faces; ++i) {
2269                 int j;
2270                 SmoothFace *face = &mesh->faces[i];
2271
2272                 for(j = 0; j < SMOOTHFACE_MAX_EDGES; ++j)
2273                         if(face->edges[j])
2274                                 /* pointer arithmetic to get edge array index */
2275                                 face->edges[j] = &tmp[face->edges[j] - mesh->edges];
2276         }
2277
2278         MEM_freeN(mesh->edges);
2279         mesh->edges = tmp;
2280         mesh->max_edges = max_edges;
2281 }
2282
2283 #ifdef EDGESPLIT_DEBUG_0
2284 static void smoothmesh_print(SmoothMesh *mesh)
2285 {
2286         int i, j;
2287         DerivedMesh *dm = mesh->dm;
2288
2289         printf("--- SmoothMesh ---\n");
2290         printf("--- Vertices ---\n");
2291         for(i = 0; i < mesh->num_verts; i++) {
2292                 SmoothVert *vert = &mesh->verts[i];
2293                 LinkNode *node;
2294                 MVert mv;
2295
2296                 dm->getVert(dm, vert->oldIndex, &mv);
2297
2298                 printf("%3d: ind={%3d, %3d}, pos={% 5.1f, % 5.1f, % 5.1f}",
2299                        i, vert->oldIndex, vert->newIndex,
2300          mv.co[0], mv.co[1], mv.co[2]);
2301                 printf(", faces={");
2302                 for(node = vert->faces; node != NULL; node = node->next) {
2303                         printf(" %d", ((SmoothFace *)node->link)->newIndex);
2304                 }
2305                 printf("}\n");
2306         }
2307
2308         printf("\n--- Edges ---\n");
2309         for(i = 0; i < mesh->num_edges; i++) {
2310                 SmoothEdge *edge = &mesh->edges[i];
2311                 LinkNode *node;
2312
2313                 printf("%4d: indices={%4d, %4d}, verts={%4d, %4d}",
2314                        i,
2315          edge->oldIndex, edge->newIndex,
2316   edge->verts[0]->newIndex, edge->verts[1]->newIndex);
2317                 if(edge->verts[0] == edge->verts[1]) printf(" <- DUPLICATE VERTEX");
2318                 printf(", faces={");
2319                 for(node = edge->faces; node != NULL; node = node->next) {
2320                         printf(" %d", ((SmoothFace *)node->link)->newIndex);
2321                 }
2322                 printf("}\n");
2323         }
2324
2325         printf("\n--- Faces ---\n");
2326         for(i = 0; i < mesh->num_faces; i++) {
2327                 SmoothFace *face = &mesh->faces[i];
2328
2329                 printf("%4d: indices={%4d, %4d}, edges={", i,
2330                        face->oldIndex, face->newIndex);
2331                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
2332                         if(face->flip[j])
2333                                 printf(" -%-2d", face->edges[j]->newIndex);
2334                         else
2335                                 printf("  %-2d", face->edges[j]->newIndex);
2336                 }
2337                 printf("}, verts={");
2338                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
2339                         printf(" %d", face->edges[j]->verts[face->flip[j]]->newIndex);
2340                 }
2341                 printf("}\n");
2342         }
2343 }
2344 #endif
2345
2346 static SmoothMesh *smoothmesh_from_derivedmesh(DerivedMesh *dm)
2347 {
2348         SmoothMesh *mesh;
2349         EdgeHash *edges = BLI_edgehash_new();
2350         int i;
2351         int totvert, totedge, totface;
2352
2353         totvert = dm->getNumVerts(dm);
2354         totedge = dm->getNumEdges(dm);
2355         totface = dm->getNumFaces(dm);
2356
2357         mesh = smoothmesh_new(totvert, totedge, totface,
2358                               totvert, totedge, totface);
2359
2360         mesh->dm = dm;
2361
2362         for(i = 0; i < totvert; i++) {
2363                 SmoothVert *vert = &mesh->verts[i];
2364
2365                 vert->oldIndex = vert->newIndex = i;
2366         }
2367
2368         for(i = 0; i < totedge; i++) {
2369                 SmoothEdge *edge = &mesh->edges[i];
2370                 MEdge med;
2371
2372                 dm->getEdge(dm, i, &med);
2373                 edge->verts[0] = &mesh->verts[med.v1];
2374                 edge->verts[1] = &mesh->verts[med.v2];
2375                 edge->oldIndex = edge->newIndex = i;
2376                 edge->flag = med.flag;
2377
2378                 BLI_edgehash_insert(edges, med.v1, med.v2, edge);
2379         }
2380
2381         for(i = 0; i < totface; i++) {
2382                 SmoothFace *face = &mesh->faces[i];
2383                 MFace mf;
2384                 MVert v1, v2, v3;
2385                 int j;
2386
2387                 dm->getFace(dm, i, &mf);
2388
2389                 dm->getVert(dm, mf.v1, &v1);
2390                 dm->getVert(dm, mf.v2, &v2);
2391                 dm->getVert(dm, mf.v3, &v3);
2392                 face->edges[0] = BLI_edgehash_lookup(edges, mf.v1, mf.v2);
2393                 if(face->edges[0]->verts[1]->oldIndex == mf.v1) face->flip[0] = 1;
2394                 face->edges[1] = BLI_edgehash_lookup(edges, mf.v2, mf.v3);
2395                 if(face->edges[1]->verts[1]->oldIndex == mf.v2) face->flip[1] = 1;
2396                 if(mf.v4) {
2397                         MVert v4;
2398                         dm->getVert(dm, mf.v4, &v4);
2399                         face->edges[2] = BLI_edgehash_lookup(edges, mf.v3, mf.v4);
2400                         if(face->edges[2]->verts[1]->oldIndex == mf.v3) face->flip[2] = 1;
2401                         face->edges[3] = BLI_edgehash_lookup(edges, mf.v4, mf.v1);
2402                         if(face->edges[3]->verts[1]->oldIndex == mf.v4) face->flip[3] = 1;
2403                         CalcNormFloat4(v1.co, v2.co, v3.co, v4.co, face->normal);
2404                 } else {
2405                         face->edges[2] = BLI_edgehash_lookup(edges, mf.v3, mf.v1);
2406                         if(face->edges[2]->verts[1]->oldIndex == mf.v3) face->flip[2] = 1;
2407                         face->edges[3] = NULL;
2408                         CalcNormFloat(v1.co, v2.co, v3.co, face->normal);
2409                 }
2410
2411                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
2412                         SmoothEdge *edge = face->edges[j];
2413                         BLI_linklist_prepend(&edge->faces, face);
2414                         BLI_linklist_prepend(&edge->verts[face->flip[j]]->faces, face);
2415                 }
2416
2417                 face->oldIndex = face->newIndex = i;
2418         }
2419
2420         BLI_edgehash_free(edges, NULL);
2421
2422         return mesh;
2423 }
2424
2425 static DerivedMesh *CDDM_from_smoothmesh(SmoothMesh *mesh)
2426 {
2427         DerivedMesh *result = CDDM_from_template(mesh->dm,
2428                         mesh->num_verts,
2429    mesh->num_edges,
2430    mesh->num_faces);
2431         MVert *new_verts = CDDM_get_verts(result);
2432         MEdge *new_edges = CDDM_get_edges(result);
2433         MFace *new_faces = CDDM_get_faces(result);
2434         int i;
2435
2436         for(i = 0; i < mesh->num_verts; ++i) {
2437                 SmoothVert *vert = &mesh->verts[i];
2438                 MVert *newMV = &new_verts[vert->newIndex];
2439
2440                 DM_copy_vert_data(mesh->dm, result,
2441                                   vert->oldIndex, vert->newIndex, 1);
2442                 mesh->dm->getVert(mesh->dm, vert->oldIndex, newMV);
2443         }
2444
2445         for(i = 0; i < mesh->num_edges; ++i) {
2446                 SmoothEdge *edge = &mesh->edges[i];
2447                 MEdge *newME = &new_edges[edge->newIndex];
2448
2449                 DM_copy_edge_data(mesh->dm, result,
2450                                   edge->oldIndex, edge->newIndex, 1);
2451                 mesh->dm->getEdge(mesh->dm, edge->oldIndex, newME);
2452                 newME->v1 = edge->verts[0]->newIndex;
2453                 newME->v2 = edge->verts[1]->newIndex;
2454         }
2455
2456         for(i = 0; i < mesh->num_faces; ++i) {
2457                 SmoothFace *face = &mesh->faces[i];
2458                 MFace *newMF = &new_faces[face->newIndex];
2459
2460                 DM_copy_face_data(mesh->dm, result,
2461                                   face->oldIndex, face->newIndex, 1);
2462                 mesh->dm->getFace(mesh->dm, face->oldIndex, newMF);
2463
2464                 newMF->v1 = face->edges[0]->verts[face->flip[0]]->newIndex;
2465                 newMF->v2 = face->edges[1]->verts[face->flip[1]]->newIndex;
2466                 newMF->v3 = face->edges[2]->verts[face->flip[2]]->newIndex;
2467
2468                 if(face->edges[3]) {
2469                         newMF->v4 = face->edges[3]->verts[face->flip[3]]->newIndex;
2470                 } else {
2471                         newMF->v4 = 0;
2472                 }
2473         }
2474
2475         return result;
2476 }
2477
2478 /* returns the other vert in the given edge
2479  */
2480 static SmoothVert *other_vert(SmoothEdge *edge, SmoothVert *vert)
2481 {
2482         if(edge->verts[0] == vert) return edge->verts[1];
2483         else return edge->verts[0];
2484 }
2485
2486 /* returns the other edge in the given face that uses the given vert
2487  * returns NULL if no other edge in the given face uses the given vert
2488  * (this should never happen)
2489  */
2490 static SmoothEdge *other_edge(SmoothFace *face, SmoothVert *vert,
2491                               SmoothEdge *edge)
2492 {
2493         int i,j;
2494         for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++) {
2495                 SmoothEdge *tmp_edge = face->edges[i];
2496                 if(tmp_edge == edge) continue;
2497
2498                 for(j = 0; j < SMOOTHEDGE_NUM_VERTS; j++)
2499                         if(tmp_edge->verts[j] == vert) return tmp_edge;
2500         }
2501
2502         /* if we get to here, something's wrong (there should always be 2 edges
2503         * which use the same vert in a face)
2504         */
2505         return NULL;
2506 }
2507
2508 /* returns a face attached to the given edge which is not the given face.
2509  * returns NULL if no other faces use this edge.
2510  */
2511 static SmoothFace *other_face(SmoothEdge *edge, SmoothFace *face)
2512 {
2513         LinkNode *node;
2514
2515         for(node = edge->faces; node != NULL; node = node->next)
2516                 if(node->link != face) return node->link;
2517
2518         return NULL;
2519 }
2520
2521 #if 0
2522 /* copies source list to target, overwriting target (target is not freed)
2523  * nodes in the copy will be in the same order as in source
2524  */
2525 static void linklist_copy(LinkNode **target, LinkNode *source)
2526 {
2527         LinkNode *node = NULL;
2528         *target = NULL;
2529
2530         for(; source; source = source->next) {
2531                 if(node) {
2532                         node->next = MEM_mallocN(sizeof(*node->next), "nlink_copy");
2533                                                                                 node = node->next;
2534 } else {
2535                                                                                 node = *target = MEM_mallocN(sizeof(**target), "nlink_copy");
2536 }
2537                                                                                 node->link = source->link;
2538                                                                                 node->next = NULL;
2539 }
2540 }
2541 #endif
2542
2543                                                                                 /* appends source to target if it's not already in target */
2544                                                                                 static void linklist_append_unique(LinkNode **target, void *source) 
2545 {
2546         LinkNode *node;
2547         LinkNode *prev = NULL;
2548
2549         /* check if source value is already in the list */
2550         for(node = *target; node; prev = node, node = node->next)
2551                 if(node->link == source) return;
2552
2553         node = MEM_mallocN(sizeof(*node), "nlink");
2554         node->next = NULL;
2555         node->link = source;
2556
2557         if(prev) prev->next = node;
2558         else *target = node;
2559 }
2560
2561 /* appends elements of source which aren't already in target to target */
2562 static void linklist_append_list_unique(LinkNode **target, LinkNode *source)
2563 {
2564         for(; source; source = source->next)
2565                 linklist_append_unique(target, source->link);
2566 }
2567
2568 #if 0 /* this is no longer used, it should possibly be removed */
2569 /* prepends prepend to list - doesn't copy nodes, just joins the lists */
2570 static void linklist_prepend_linklist(LinkNode **list, LinkNode *prepend)
2571 {
2572         if(prepend) {
2573                 LinkNode *node = prepend;
2574                 while(node->next) node = node->next;
2575
2576                 node->next = *list;
2577                 *list = prepend;
2578 }
2579 }
2580 #endif
2581
2582 /* returns 1 if the linked list contains the given pointer, 0 otherwise
2583  */
2584 static int linklist_contains(LinkNode *list, void *ptr)
2585 {
2586         LinkNode *node;
2587
2588         for(node = list; node; node = node->next)
2589                 if(node->link == ptr) return 1;
2590
2591         return 0;
2592 }
2593
2594 /* returns 1 if the first linked list is a subset of the second (comparing
2595  * pointer values), 0 if not
2596  */
2597 static int linklist_subset(LinkNode *list1, LinkNode *list2)
2598 {
2599         for(; list1; list1 = list1->next)
2600                 if(!linklist_contains(list2, list1->link))
2601                         return 0;
2602
2603         return 1;
2604 }
2605
2606 #if 0
2607 /* empties the linked list
2608  * frees pointers with freefunc if freefunc is not NULL
2609  */
2610 static void linklist_empty(LinkNode **list, LinkNodeFreeFP freefunc)
2611 {
2612         BLI_linklist_free(*list, freefunc);
2613         *list = NULL;
2614 }
2615 #endif
2616
2617 /* removes the first instance of value from the linked list
2618  * frees the pointer with freefunc if freefunc is not NULL
2619  */
2620 static void linklist_remove_first(LinkNode **list, void *value,
2621                                   LinkNodeFreeFP freefunc)
2622 {
2623         LinkNode *node = *list;
2624         LinkNode *prev = NULL;
2625
2626         while(node && node->link != value) {
2627                 prev = node;
2628                 node = node->next;
2629         }
2630
2631         if(node) {
2632                 if(prev)
2633                         prev->next = node->next;
2634                 else
2635                         *list = node->next;
2636
2637                 if(freefunc)
2638                         freefunc(node->link);
2639
2640                 MEM_freeN(node);
2641         }
2642 }
2643
2644 /* removes all elements in source from target */
2645 static void linklist_remove_list(LinkNode **target, LinkNode *source,
2646                                  LinkNodeFreeFP freefunc)
2647 {
2648         for(; source; source = source->next)
2649                 linklist_remove_first(target, source->link, freefunc);
2650 }
2651
2652 #ifdef EDGESPLIT_DEBUG_0
2653 static void print_ptr(void *ptr)
2654 {
2655         printf("%p\n", ptr);
2656 }
2657
2658 static void print_edge(void *ptr)
2659 {
2660         SmoothEdge *edge = ptr;
2661         printf(" %4d", edge->newIndex);
2662 }
2663
2664 static void print_face(void *ptr)
2665 {
2666         SmoothFace *face = ptr;
2667         printf(" %4d", face->newIndex);
2668 }
2669 #endif
2670
2671 typedef struct ReplaceData {
2672         void *find;
2673         void *replace;
2674 } ReplaceData;
2675
2676 static void edge_replace_vert(void *ptr, void *userdata)
2677 {
2678         SmoothEdge *edge = ptr;
2679         SmoothVert *find = ((ReplaceData *)userdata)->find;
2680         SmoothVert *replace = ((ReplaceData *)userdata)->replace;
2681         int i;
2682
2683 #ifdef EDGESPLIT_DEBUG_3
2684         printf("replacing vert %4d with %4d in edge %4d",
2685                find->newIndex, replace->newIndex, edge->newIndex);
2686         printf(": {%4d, %4d}", edge->verts[0]->newIndex, edge->verts[1]->newIndex);
2687 #endif
2688
2689         for(i = 0; i < SMOOTHEDGE_NUM_VERTS; i++) {
2690                 if(edge->verts[i] == find) {
2691                         linklist_append_list_unique(&replace->faces, edge->faces);
2692                         linklist_remove_list(&find->faces, edge->faces, NULL);
2693
2694                         edge->verts[i] = replace;
2695                 }
2696         }
2697
2698 #ifdef EDGESPLIT_DEBUG_3
2699         printf(" -> {%4d, %4d}\n", edge->verts[0]->newIndex, edge->verts[1]->newIndex);
2700 #endif
2701 }
2702
2703 static void face_replace_vert(void *ptr, void *userdata)
2704 {
2705         SmoothFace *face = ptr;
2706         int i;
2707
2708         for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++)
2709                 edge_replace_vert(face->edges[i], userdata);
2710 }
2711
2712 static void face_replace_edge(void *ptr, void *userdata)
2713 {
2714         SmoothFace *face = ptr;
2715         SmoothEdge *find = ((ReplaceData *)userdata)->find;
2716         SmoothEdge *replace = ((ReplaceData *)userdata)->replace;
2717         int i;
2718
2719 #ifdef EDGESPLIT_DEBUG_3
2720         printf("replacing edge %4d with %4d in face %4d",
2721                find->newIndex, replace->newIndex, face->newIndex);
2722         if(face->edges[3])
2723                 printf(": {%2d %2d %2d %2d}",
2724                        face->edges[0]->newIndex, face->edges[1]->newIndex,
2725          face->edges[2]->newIndex, face->edges[3]->newIndex);
2726         else
2727                 printf(": {%2d %2d %2d}",
2728                        face->edges[0]->newIndex, face->edges[1]->newIndex,
2729          face->edges[2]->newIndex);
2730 #endif
2731
2732         for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++) {
2733                 if(face->edges[i] == find) {
2734                         linklist_remove_first(&face->edges[i]->faces, face, NULL);
2735                         BLI_linklist_prepend(&replace->faces, face);
2736                         face->edges[i] = replace;
2737                 }
2738         }
2739
2740 #ifdef EDGESPLIT_DEBUG_3
2741         if(face->edges[3])
2742                 printf(" -> {%2d %2d %2d %2d}\n",
2743                        face->edges[0]->newIndex, face->edges[1]->newIndex,
2744          face->edges[2]->newIndex, face->edges[3]->newIndex);
2745         else
2746                 printf(" -> {%2d %2d %2d}\n",
2747                        face->edges[0]->newIndex, face->edges[1]->newIndex,
2748          face->edges[2]->newIndex);
2749 #endif
2750 }
2751
2752 static int edge_is_loose(SmoothEdge *edge)
2753 {
2754         return !(edge->faces && edge->faces->next);
2755 }
2756
2757 static int edge_is_sharp(SmoothEdge *edge, int flags,
2758                          float threshold)
2759 {
2760 #ifdef EDGESPLIT_DEBUG_1
2761         printf("edge %d: ", edge->newIndex);
2762 #endif
2763         if(edge->flag & ME_SHARP) {
2764                 /* edge can only be sharp if it has at least 2 faces */
2765                 if(!edge_is_loose(edge)) {
2766 #ifdef EDGESPLIT_DEBUG_1
2767                         printf("sharp\n");
2768 #endif
2769                         return 1;
2770                 } else {
2771                         /* edge is loose, so it can't be sharp */
2772                         edge->flag &= ~ME_SHARP;
2773                 }
2774         }
2775
2776 #ifdef EDGESPLIT_DEBUG_1
2777         printf("not sharp\n");
2778 #endif
2779         return 0;
2780 }
2781
2782 /* finds another sharp edge which uses vert, by traversing faces around the
2783  * vert until it does one of the following:
2784  * - hits a loose edge (the edge is returned)
2785  * - hits a sharp edge (the edge is returned)
2786  * - returns to the start edge (NULL is returned)
2787  */
2788 static SmoothEdge *find_other_sharp_edge(SmoothVert *vert, SmoothEdge *edge,
2789                                          LinkNode **visited_faces, float threshold, int flags)
2790 {
2791         SmoothFace *face = NULL;
2792         SmoothEdge *edge2 = NULL;
2793         /* holds the edges we've seen so we can avoid looping indefinitely */
2794         LinkNode *visited_edges = NULL;
2795 #ifdef EDGESPLIT_DEBUG_1
2796         printf("=== START === find_other_sharp_edge(edge = %4d, vert = %4d)\n",
2797                edge->newIndex, vert->newIndex);
2798 #endif
2799
2800         /* get a face on which to start */
2801         if(edge->faces) face = edge->faces->link;
2802         else return NULL;
2803
2804         /* record this edge as visited */
2805         BLI_linklist_prepend(&visited_edges, edge);
2806
2807         /* get the next edge */
2808         edge2 = other_edge(face, vert, edge);
2809
2810         /* record this face as visited */
2811         if(visited_faces)
2812                 BLI_linklist_prepend(visited_faces, face);
2813
2814         /* search until we hit a loose edge or a sharp edge or an edge we've
2815         * seen before
2816         */
2817         while(face && !edge_is_sharp(edge2, flags, threshold)
2818                      && !linklist_contains(visited_edges, edge2)) {
2819 #ifdef EDGESPLIT_DEBUG_3
2820                 printf("current face %4d; current edge %4d\n", face->newIndex,
2821                        edge2->newIndex);
2822 #endif
2823                 /* get the next face */
2824                 face = other_face(edge2, face);
2825
2826                 /* if face == NULL, edge2 is a loose edge */
2827                 if(face) {
2828                         /* record this face as visited */
2829                         if(visited_faces)
2830                                 BLI_linklist_prepend(visited_faces, face);
2831
2832                         /* record this edge as visited */
2833                         BLI_linklist_prepend(&visited_edges, edge2);
2834
2835                         /* get the next edge */
2836                         edge2 = other_edge(face, vert, edge2);
2837 #ifdef EDGESPLIT_DEBUG_3
2838                         printf("next face %4d; next edge %4d\n",
2839                                face->newIndex, edge2->newIndex);
2840                 } else {
2841                         printf("loose edge: %4d\n", edge2->newIndex);
2842 #endif
2843                 }
2844                      }
2845
2846                      /* either we came back to the start edge or we found a sharp/loose edge */
2847                      if(linklist_contains(visited_edges, edge2))
2848                              /* we came back to the start edge */
2849                              edge2 = NULL;
2850
2851                      BLI_linklist_free(visited_edges, NULL);
2852
2853 #ifdef EDGESPLIT_DEBUG_1
2854                      printf("=== END === find_other_sharp_edge(edge = %4d, vert = %4d), "
2855                                      "returning edge %d\n",
2856          edge->newIndex, vert->newIndex, edge2 ? edge2->newIndex : -1);
2857 #endif
2858                      return edge2;
2859 }
2860
2861 static void split_single_vert(SmoothVert *vert, SmoothFace *face,
2862                               SmoothMesh *mesh)
2863 {
2864         SmoothVert *copy_vert;
2865         ReplaceData repdata;
2866
2867         copy_vert = smoothvert_copy(vert, mesh);
2868
2869         repdata.find = vert;
2870         repdata.replace = copy_vert;
2871         face_replace_vert(face, &repdata);
2872 }
2873
2874 static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh);
2875
2876 static void propagate_split(SmoothEdge *edge, SmoothVert *vert,
2877                             SmoothMesh *mesh)
2878 {
2879         SmoothEdge *edge2;
2880         LinkNode *visited_faces = NULL;
2881 #ifdef EDGESPLIT_DEBUG_1
2882         printf("=== START === propagate_split(edge = %4d, vert = %4d)\n",
2883                edge->newIndex, vert->newIndex);
2884 #endif
2885
2886         edge2 = find_other_sharp_edge(vert, edge, &visited_faces,
2887                                       mesh->threshold, mesh->flags);
2888
2889         if(!edge2) {
2890                 /* didn't find a sharp or loose edge, so we've hit a dead end */
2891         } else if(!edge_is_loose(edge2)) {
2892                 /* edge2 is not loose, so it must be sharp */
2893                 if(edge_is_loose(edge)) {
2894                         /* edge is loose, so we can split edge2 at this vert */
2895                         split_edge(edge2, vert, mesh);
2896                 } else if(edge_is_sharp(edge, mesh->flags, mesh->threshold)) {
2897                         /* both edges are sharp, so we can split the pair at vert */
2898                         split_edge(edge, vert, mesh);
2899                 } else {
2900                         /* edge is not sharp, so try to split edge2 at its other vert */
2901                         split_edge(edge2, other_vert(edge2, vert), mesh);
2902                 }
2903         } else { /* edge2 is loose */
2904                 if(edge_is_loose(edge)) {
2905                         SmoothVert *vert2;
2906                         ReplaceData repdata;
2907
2908                         /* can't split edge, what should we do with vert? */
2909                         if(linklist_subset(vert->faces, visited_faces)) {
2910                                 /* vert has only one fan of faces attached; don't split it */
2911                         } else {
2912                                 /* vert has more than one fan of faces attached; split it */
2913                                 vert2 = smoothvert_copy(vert, mesh);
2914
2915                                 /* replace vert with its copy in visited_faces */
2916                                 repdata.find = vert;
2917                                 repdata.replace = vert2;
2918                                 BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
2919                         }
2920                 } else {
2921                         /* edge is not loose, so it must be sharp; split it */
2922                         split_edge(edge, vert, mesh);
2923                 }
2924         }
2925
2926         BLI_linklist_free(visited_faces, NULL);
2927 #ifdef EDGESPLIT_DEBUG_1
2928         printf("=== END === propagate_split(edge = %4d, vert = %4d)\n",
2929                edge->newIndex, vert->newIndex);
2930 #endif
2931 }
2932
2933 static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
2934 {
2935         SmoothEdge *edge2;
2936         SmoothVert *vert2;
2937         ReplaceData repdata;
2938         /* the list of faces traversed while looking for a sharp edge */
2939         LinkNode *visited_faces = NULL;
2940 #ifdef EDGESPLIT_DEBUG_1
2941         printf("=== START === split_edge(edge = %4d, vert = %4d)\n",
2942                edge->newIndex, vert->newIndex);
2943 #endif
2944
2945         edge2 = find_other_sharp_edge(vert, edge, &visited_faces,
2946                                       mesh->threshold, mesh->flags);
2947
2948         if(!edge2) {
2949                 /* didn't find a sharp or loose edge, so try the other vert */
2950                 vert2 = other_vert(edge, vert);
2951                 propagate_split(edge, vert2, mesh);
2952         } else if(!edge_is_loose(edge2)) {
2953                 /* edge2 is not loose, so it must be sharp */
2954                 SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
2955                 SmoothEdge *copy_edge2 = smoothedge_copy(edge2, mesh);
2956                 SmoothVert *vert2;
2957
2958                 /* replace edge with its copy in visited_faces */
2959                 repdata.find = edge;
2960                 repdata.replace = copy_edge;
2961                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
2962
2963                 /* replace edge2 with its copy in visited_faces */
2964                 repdata.find = edge2;
2965                 repdata.replace = copy_edge2;
2966                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
2967
2968                 vert2 = smoothvert_copy(vert, mesh);
2969
2970                 /* replace vert with its copy in visited_faces (must be done after
2971                 * edge replacement so edges have correct vertices)
2972                 */
2973                 repdata.find = vert;
2974                 repdata.replace = vert2;
2975                 BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
2976
2977                 /* all copying and replacing is done; the mesh should be consistent.
2978                 * now propagate the split to the vertices at either end
2979                 */
2980                 propagate_split(copy_edge, other_vert(copy_edge, vert2), mesh);
2981                 propagate_split(copy_edge2, other_vert(copy_edge2, vert2), mesh);
2982
2983                 if(smoothedge_has_vert(edge, vert))
2984                         propagate_split(edge, vert, mesh);
2985         } else {
2986                 /* edge2 is loose */
2987                 SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
2988                 SmoothVert *vert2;
2989
2990                 /* replace edge with its copy in visited_faces */
2991                 repdata.find = edge;
2992                 repdata.replace = copy_edge;
2993                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
2994
2995                 vert2 = smoothvert_copy(vert, mesh);
2996
2997                 /* replace vert with its copy in visited_faces (must be done after
2998                 * edge replacement so edges have correct vertices)
2999                 */
3000                 repdata.find = vert;
3001                 repdata.replace = vert2;
3002                 BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
3003
3004                 /* copying and replacing is done; the mesh should be consistent.
3005                 * now propagate the split to the vertex at the other end
3006                 */
3007                 propagate_split(copy_edge, other_vert(copy_edge, vert2), mesh);
3008
3009                 if(smoothedge_has_vert(edge, vert))
3010                         propagate_split(edge, vert, mesh);
3011         }
3012
3013         BLI_linklist_free(visited_faces, NULL);
3014 #ifdef EDGESPLIT_DEBUG_1
3015         printf("=== END === split_edge(edge = %4d, vert = %4d)\n",
3016                edge->newIndex, vert->newIndex);
3017 #endif
3018 }
3019
3020 static void tag_and_count_extra_edges(SmoothMesh *mesh, float split_angle,
3021                                       int flags, int *extra_edges)
3022 {
3023         /* if normal1 dot normal2 < threshold, angle is greater, so split */
3024         /* FIXME not sure if this always works */
3025         /* 0.00001 added for floating-point rounding */
3026         float threshold = cos((split_angle + 0.00001) * M_PI / 180.0);
3027         int i;
3028
3029         *extra_edges = 0;
3030
3031         /* loop through edges, counting potential new ones */
3032         for(i = 0; i < mesh->num_edges; i++) {
3033                 SmoothEdge *edge = &mesh->edges[i];
3034                 int sharp = 0;
3035
3036                 /* treat all non-manifold edges (3 or more faces) as sharp */
3037                 if(edge->faces && edge->faces->next && edge->faces->next->next) {
3038                         LinkNode *node;
3039
3040                         /* this edge is sharp */
3041                         sharp = 1;
3042
3043                         /* add an extra edge for every face beyond the first */
3044                         *extra_edges += 2;
3045                         for(node = edge->faces->next->next->next; node; node = node->next)
3046                                 (*extra_edges)++;
3047                 } else if((flags & (MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG))
3048                                          && !edge_is_loose(edge)) {
3049                         /* (the edge can only be sharp if we're checking angle or flag,
3050                         * and it has at least 2 faces) */
3051
3052                                                  /* if we're checking the sharp flag and it's set, good */
3053                                                  if((flags & MOD_EDGESPLIT_FROMFLAG) && (edge->flag & ME_SHARP)) {
3054                                                          /* this edge is sharp */
3055                                                          sharp = 1;
3056
3057                                                          (*extra_edges)++;
3058                                                  } else if(flags & MOD_EDGESPLIT_FROMANGLE) {
3059                                                          /* we know the edge has 2 faces, so check the angle */
3060                                                          SmoothFace *face1 = edge->faces->link;
3061                                                          SmoothFace *face2 = edge->faces->next->link;
3062                                                          float edge_angle_cos = MTC_dot3Float(face1->normal,
3063                                                                          face2->normal);
3064
3065                                                          if(edge_angle_cos < threshold) {
3066                                                                  /* this edge is sharp */
3067