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