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