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