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