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