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