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