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