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