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