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