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