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