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