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