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