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