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