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