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