source/blender/blenkernel/intern/modifier.c

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