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