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