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