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