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