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