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