MOD_edgesplit.c

Go to the documentation of this file.

/*
 * ***** BEGIN GPL LICENSE BLOCK *****
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software  Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * The Original Code is Copyright (C) 2005 by the Blender Foundation.
 * All rights reserved.
 *
 * Contributor(s): Daniel Dunbar
 *                 Ton Roosendaal,
 *                 Ben Batt,
 *                 Brecht Van Lommel,
 *                 Campbell Barton
 *
 * ***** END GPL LICENSE BLOCK *****
 *
 */

/* EdgeSplit modifier: Splits edges in the mesh according to sharpness flag
 * or edge angle (can be used to achieve autosmoothing) */

#include <assert.h>

#include "DNA_meshdata_types.h"

#include "BLI_listbase.h"
#include "BLI_memarena.h"
#include "BLI_edgehash.h"
#include "BLI_math.h"
#include "BLI_utildefines.h"
#include "BLI_linklist.h"

#include "MEM_guardedalloc.h"

#include "BKE_cdderivedmesh.h"
#include "BKE_modifier.h"
#include "BKE_particle.h"


#include "MOD_util.h"

#if 0
#define EDGESPLIT_DEBUG_3
#define EDGESPLIT_DEBUG_2
#define EDGESPLIT_DEBUG_1
#define EDGESPLIT_DEBUG_0
#endif

static void initData(ModifierData *md)
{
    EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;

    /* default to 30-degree split angle, sharpness from both angle & flag
    */
    emd->split_angle = 30;
    emd->flags = MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG;
}

static void copyData(ModifierData *md, ModifierData *target)
{
    EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
    EdgeSplitModifierData *temd = (EdgeSplitModifierData*) target;

    temd->split_angle = emd->split_angle;
    temd->flags = emd->flags;
}

/* Mesh data for edgesplit operation */
typedef struct SmoothVert {
    LinkNode *faces;     /* all faces which use this vert */
    int oldIndex; /* the index of the original DerivedMesh vert */
    int newIndex; /* the index of the new DerivedMesh vert */
} SmoothVert;

#define SMOOTHEDGE_NUM_VERTS 2

typedef struct SmoothEdge {
    SmoothVert *verts[SMOOTHEDGE_NUM_VERTS]; /* the verts used by this edge */
    LinkNode *faces;     /* all faces which use this edge */
    int oldIndex; /* the index of the original DerivedMesh edge */
    int newIndex; /* the index of the new DerivedMesh edge */
    short flag; /* the flags from the original DerivedMesh edge */
} SmoothEdge;

#define SMOOTHFACE_MAX_EDGES 4

typedef struct SmoothFace {
    SmoothEdge *edges[SMOOTHFACE_MAX_EDGES]; /* nonexistent edges == NULL */
    int flip[SMOOTHFACE_MAX_EDGES]; /* 1 = flip edge dir, 0 = don't flip */
    float normal[3]; /* the normal of this face */
    int oldIndex; /* the index of the original DerivedMesh face */
    int newIndex; /* the index of the new DerivedMesh face */
} SmoothFace;

typedef struct SmoothMesh {
    SmoothVert *verts;
    SmoothEdge *edges;
    SmoothFace *faces;
    int num_verts, num_edges, num_faces;
    int max_verts, max_edges, max_faces;
    DerivedMesh *dm;
    float threshold; /* the cosine of the smoothing angle */
    int flags;
    MemArena *arena;
    ListBase propagatestack, reusestack;
} SmoothMesh;

static SmoothVert *smoothvert_copy(SmoothVert *vert, SmoothMesh *mesh)
{
    SmoothVert *copy = &mesh->verts[mesh->num_verts];

    assert(vert != NULL);

    if(mesh->num_verts >= mesh->max_verts) {
        printf("Attempted to add a SmoothMesh vert beyond end of array\n");
        return NULL;
    }

    *copy = *vert;
    copy->faces = NULL;
    copy->newIndex = mesh->num_verts;
    ++mesh->num_verts;

#ifdef EDGESPLIT_DEBUG_2
    printf("copied vert %4d to vert %4d\n", vert->newIndex, copy->newIndex);
#endif
    return copy;
}

static SmoothEdge *smoothedge_copy(SmoothEdge *edge, SmoothMesh *mesh)
{
    SmoothEdge *copy = &mesh->edges[mesh->num_edges];

    if(mesh->num_edges >= mesh->max_edges) {
        printf("Attempted to add a SmoothMesh edge beyond end of array\n");
        return NULL;
    }

    *copy = *edge;
    copy->faces = NULL;
    copy->newIndex = mesh->num_edges;
    ++mesh->num_edges;

#ifdef EDGESPLIT_DEBUG_2
    printf("copied edge %4d to edge %4d\n", edge->newIndex, copy->newIndex);
#endif
    return copy;
}

static int smoothedge_has_vert(SmoothEdge *edge, SmoothVert *vert)
{
    int i;
    for(i = 0; i < SMOOTHEDGE_NUM_VERTS; i++)
        if(edge->verts[i] == vert) return 1;

    return 0;
}

static SmoothMesh *smoothmesh_new(int num_verts, int num_edges, int num_faces,
                  int max_verts, int max_edges, int max_faces)
{
    SmoothMesh *mesh = MEM_callocN(sizeof(*mesh), "smoothmesh");
    mesh->verts = MEM_callocN(sizeof(*mesh->verts) * max_verts,
            "SmoothMesh.verts");
    mesh->edges = MEM_callocN(sizeof(*mesh->edges) * max_edges,
            "SmoothMesh.edges");
    mesh->faces = MEM_callocN(sizeof(*mesh->faces) * max_faces,
            "SmoothMesh.faces");

    mesh->num_verts = num_verts;
    mesh->num_edges = num_edges;
    mesh->num_faces = num_faces;

    mesh->max_verts = max_verts;
    mesh->max_edges = max_edges;
    mesh->max_faces = max_faces;

    return mesh;
}

static void smoothmesh_free(SmoothMesh *mesh)
{
    int i;

    for(i = 0; i < mesh->num_verts; ++i)
        BLI_linklist_free(mesh->verts[i].faces, NULL);

    for(i = 0; i < mesh->num_edges; ++i)
        BLI_linklist_free(mesh->edges[i].faces, NULL);
    
    if(mesh->arena)
        BLI_memarena_free(mesh->arena);

    MEM_freeN(mesh->verts);
    MEM_freeN(mesh->edges);
    MEM_freeN(mesh->faces);
    MEM_freeN(mesh);
}

static void smoothmesh_resize_verts(SmoothMesh *mesh, int max_verts)
{
    int i;
    SmoothVert *tmp;

    if(max_verts <= mesh->max_verts) return;

    tmp = MEM_callocN(sizeof(*tmp) * max_verts, "SmoothMesh.verts");

    memcpy(tmp, mesh->verts, sizeof(*tmp) * mesh->num_verts);

    /* remap vert pointers in edges */
    for(i = 0; i < mesh->num_edges; ++i) {
        int j;
        SmoothEdge *edge = &mesh->edges[i];

        for(j = 0; j < SMOOTHEDGE_NUM_VERTS; ++j)
            /* pointer arithmetic to get vert array index */
            edge->verts[j] = &tmp[edge->verts[j] - mesh->verts];
    }

    MEM_freeN(mesh->verts);
    mesh->verts = tmp;
    mesh->max_verts = max_verts;
}

static void smoothmesh_resize_edges(SmoothMesh *mesh, int max_edges)
{
    int i;
    SmoothEdge *tmp;

    if(max_edges <= mesh->max_edges) return;

    tmp = MEM_callocN(sizeof(*tmp) * max_edges, "SmoothMesh.edges");

    memcpy(tmp, mesh->edges, sizeof(*tmp) * mesh->num_edges);

    /* remap edge pointers in faces */
    for(i = 0; i < mesh->num_faces; ++i) {
        int j;
        SmoothFace *face = &mesh->faces[i];

        for(j = 0; j < SMOOTHFACE_MAX_EDGES; ++j)
            if(face->edges[j])
                /* pointer arithmetic to get edge array index */
                face->edges[j] = &tmp[face->edges[j] - mesh->edges];
    }

    MEM_freeN(mesh->edges);
    mesh->edges = tmp;
    mesh->max_edges = max_edges;
}

#ifdef EDGESPLIT_DEBUG_0
static void smoothmesh_print(SmoothMesh *mesh)
{
    int i, j;
    DerivedMesh *dm = mesh->dm;

    printf("--- SmoothMesh ---\n");
    printf("--- Vertices ---\n");
    for(i = 0; i < mesh->num_verts; i++) {
        SmoothVert *vert = &mesh->verts[i];
        LinkNode *node;
        MVert mv;

        dm->getVert(dm, vert->oldIndex, &mv);

        printf("%3d: ind={%3d, %3d}, pos={% 5.1f, % 5.1f, % 5.1f}",
            i, vert->oldIndex, vert->newIndex,
            mv.co[0], mv.co[1], mv.co[2]);
        printf(", faces={");
        for(node = vert->faces; node != NULL; node = node->next) {
            printf(" %d", ((SmoothFace *)node->link)->newIndex);
        }
        printf("}\n");
    }

    printf("\n--- Edges ---\n");
    for(i = 0; i < mesh->num_edges; i++) {
        SmoothEdge *edge = &mesh->edges[i];
        LinkNode *node;

        printf("%4d: indices={%4d, %4d}, verts={%4d, %4d}",
            i,
            edge->oldIndex, edge->newIndex,
            edge->verts[0]->newIndex, edge->verts[1]->newIndex);
        if(edge->verts[0] == edge->verts[1]) printf(" <- DUPLICATE VERTEX");
        printf(", faces={");
        for(node = edge->faces; node != NULL; node = node->next) {
            printf(" %d", ((SmoothFace *)node->link)->newIndex);
        }
        printf("}\n");
    }

    printf("\n--- Faces ---\n");
    for(i = 0; i < mesh->num_faces; i++) {
        SmoothFace *face = &mesh->faces[i];

        printf("%4d: indices={%4d, %4d}, edges={", i,
            face->oldIndex, face->newIndex);
        for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
            if(face->flip[j])
                printf(" -%-2d", face->edges[j]->newIndex);
            else
                printf("  %-2d", face->edges[j]->newIndex);
        }
        printf("}, verts={");
        for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
            printf(" %d", face->edges[j]->verts[face->flip[j]]->newIndex);
        }
        printf("}\n");
    }
}
#endif

static SmoothMesh *smoothmesh_from_derivedmesh(DerivedMesh *dm)
{
    SmoothMesh *mesh;
    EdgeHash *edges = BLI_edgehash_new();
    int i;
    int totvert, totedge, totface;

    totvert = dm->getNumVerts(dm);
    totedge = dm->getNumEdges(dm);
    totface = dm->getNumFaces(dm);

    mesh = smoothmesh_new(totvert, totedge, totface,
            totvert, totedge, totface);

    mesh->dm = dm;

    for(i = 0; i < totvert; i++) {
        SmoothVert *vert = &mesh->verts[i];

        vert->oldIndex = vert->newIndex = i;
    }

    for(i = 0; i < totedge; i++) {
        SmoothEdge *edge = &mesh->edges[i];
        MEdge med;

        dm->getEdge(dm, i, &med);
        edge->verts[0] = &mesh->verts[med.v1];
        edge->verts[1] = &mesh->verts[med.v2];
        edge->oldIndex = edge->newIndex = i;
        edge->flag = med.flag;

        BLI_edgehash_insert(edges, med.v1, med.v2, edge);
    }

    for(i = 0; i < totface; i++) {
        SmoothFace *face = &mesh->faces[i];
        MFace mf;
        MVert v1, v2, v3;
        int j;

        dm->getFace(dm, i, &mf);

        dm->getVert(dm, mf.v1, &v1);
        dm->getVert(dm, mf.v2, &v2);
        dm->getVert(dm, mf.v3, &v3);
        face->edges[0] = BLI_edgehash_lookup(edges, mf.v1, mf.v2);
        if(face->edges[0]->verts[1]->oldIndex == mf.v1) face->flip[0] = 1;
        face->edges[1] = BLI_edgehash_lookup(edges, mf.v2, mf.v3);
        if(face->edges[1]->verts[1]->oldIndex == mf.v2) face->flip[1] = 1;
        if(mf.v4) {
            MVert v4;
            dm->getVert(dm, mf.v4, &v4);
            face->edges[2] = BLI_edgehash_lookup(edges, mf.v3, mf.v4);
            if(face->edges[2]->verts[1]->oldIndex == mf.v3) face->flip[2] = 1;
            face->edges[3] = BLI_edgehash_lookup(edges, mf.v4, mf.v1);
            if(face->edges[3]->verts[1]->oldIndex == mf.v4) face->flip[3] = 1;
            normal_quad_v3( face->normal,v1.co, v2.co, v3.co, v4.co);
        } else {
            face->edges[2] = BLI_edgehash_lookup(edges, mf.v3, mf.v1);
            if(face->edges[2]->verts[1]->oldIndex == mf.v3) face->flip[2] = 1;
            face->edges[3] = NULL;
            normal_tri_v3( face->normal,v1.co, v2.co, v3.co);
        }

        for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
            SmoothEdge *edge = face->edges[j];
            BLI_linklist_prepend(&edge->faces, face);
            BLI_linklist_prepend(&edge->verts[face->flip[j]]->faces, face);
        }

        face->oldIndex = face->newIndex = i;
    }

    BLI_edgehash_free(edges, NULL);

    return mesh;
}

static DerivedMesh *CDDM_from_smoothmesh(SmoothMesh *mesh)
{
    DerivedMesh *result = CDDM_from_template(mesh->dm,
            mesh->num_verts,
            mesh->num_edges,
            mesh->num_faces);
    MVert *new_verts = CDDM_get_verts(result);
    MEdge *new_edges = CDDM_get_edges(result);
    MFace *new_faces = CDDM_get_faces(result);
    int i;

    for(i = 0; i < mesh->num_verts; ++i) {
        SmoothVert *vert = &mesh->verts[i];
        MVert *newMV = &new_verts[vert->newIndex];

        DM_copy_vert_data(mesh->dm, result,
                vert->oldIndex, vert->newIndex, 1);
        mesh->dm->getVert(mesh->dm, vert->oldIndex, newMV);
    }

    for(i = 0; i < mesh->num_edges; ++i) {
        SmoothEdge *edge = &mesh->edges[i];
        MEdge *newME = &new_edges[edge->newIndex];

        DM_copy_edge_data(mesh->dm, result,
                edge->oldIndex, edge->newIndex, 1);
        mesh->dm->getEdge(mesh->dm, edge->oldIndex, newME);
        newME->v1 = edge->verts[0]->newIndex;
        newME->v2 = edge->verts[1]->newIndex;
    }

    for(i = 0; i < mesh->num_faces; ++i) {
        SmoothFace *face = &mesh->faces[i];
        MFace *newMF = &new_faces[face->newIndex];

        DM_copy_face_data(mesh->dm, result,
                face->oldIndex, face->newIndex, 1);
        mesh->dm->getFace(mesh->dm, face->oldIndex, newMF);

        newMF->v1 = face->edges[0]->verts[face->flip[0]]->newIndex;
        newMF->v2 = face->edges[1]->verts[face->flip[1]]->newIndex;
        newMF->v3 = face->edges[2]->verts[face->flip[2]]->newIndex;

        if(face->edges[3]) {
            newMF->v4 = face->edges[3]->verts[face->flip[3]]->newIndex;
        } else {
            newMF->v4 = 0;
        }
    }

    return result;
}

/* returns the other vert in the given edge
 */
static SmoothVert *other_vert(SmoothEdge *edge, SmoothVert *vert)
{
    if(edge->verts[0] == vert) return edge->verts[1];
    else return edge->verts[0];
}

/* returns the other edge in the given face that uses the given vert
 * returns NULL if no other edge in the given face uses the given vert
 * (this should never happen)
 */
static SmoothEdge *other_edge(SmoothFace *face, SmoothVert *vert,
                  SmoothEdge *edge)
{
    int i,j;
    for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++) {
        SmoothEdge *tmp_edge = face->edges[i];
        if(tmp_edge == edge) continue;

        for(j = 0; j < SMOOTHEDGE_NUM_VERTS; j++)
            if(tmp_edge->verts[j] == vert) return tmp_edge;
    }

    /* if we get to here, something's wrong (there should always be 2 edges
    * which use the same vert in a face)
    */
    return NULL;
}

/* returns a face attached to the given edge which is not the given face.
 * returns NULL if no other faces use this edge.
 */
static SmoothFace *other_face(SmoothEdge *edge, SmoothFace *face)
{
    LinkNode *node;

    for(node = edge->faces; node != NULL; node = node->next)
        if(node->link != face) return node->link;

    return NULL;
}

#if 0
/* copies source list to target, overwriting target (target is not freed)
 * nodes in the copy will be in the same order as in source
 */
static void linklist_copy(LinkNode **target, LinkNode *source)
{
    LinkNode *node = NULL;
    *target = NULL;

    for(; source; source = source->next) {
        if(node) {
            node->next = MEM_mallocN(sizeof(*node->next), "nlink_copy");
            node = node->next;
        } else {
            node = *target = MEM_mallocN(sizeof(**target), "nlink_copy");
        }
        node->link = source->link;
        node->next = NULL;
    }
}
#endif

/* appends source to target if it's not already in target */
static void linklist_append_unique(LinkNode **target, void *source)
{
    LinkNode *node;
    LinkNode *prev = NULL;

    /* check if source value is already in the list */
    for(node = *target; node; prev = node, node = node->next)
        if(node->link == source) return;

    node = MEM_mallocN(sizeof(*node), "nlink");
    node->next = NULL;
    node->link = source;

    if(prev) prev->next = node;
    else *target = node;
}

/* appends elements of source which aren't already in target to target */
static void linklist_append_list_unique(LinkNode **target, LinkNode *source)
{
    for(; source; source = source->next)
        linklist_append_unique(target, source->link);
}

#if 0 /* this is no longer used, it should possibly be removed */
/* prepends prepend to list - doesn't copy nodes, just joins the lists */
static void linklist_prepend_linklist(LinkNode **list, LinkNode *prepend)
{
    if(prepend) {
        LinkNode *node = prepend;
        while(node->next) node = node->next;

        node->next = *list;
        *list = prepend;
    }
}
#endif

/* returns 1 if the linked list contains the given pointer, 0 otherwise
 */
static int linklist_contains(LinkNode *list, void *ptr)
{
    LinkNode *node;

    for(node = list; node; node = node->next)
        if(node->link == ptr) return 1;

    return 0;
}

/* returns 1 if the first linked list is a subset of the second (comparing
 * pointer values), 0 if not
 */
static int linklist_subset(LinkNode *list1, LinkNode *list2)
{
    for(; list1; list1 = list1->next)
        if(!linklist_contains(list2, list1->link))
            return 0;

    return 1;
}

#if 0
/* empties the linked list
 * frees pointers with freefunc if freefunc is not NULL
 */
static void linklist_empty(LinkNode **list, LinkNodeFreeFP freefunc)
{
    BLI_linklist_free(*list, freefunc);
    *list = NULL;
}
#endif

/* removes the first instance of value from the linked list
 * frees the pointer with freefunc if freefunc is not NULL
 */
static void linklist_remove_first(LinkNode **list, void *value,
                  LinkNodeFreeFP freefunc)
{
    LinkNode *node = *list;
    LinkNode *prev = NULL;

    while(node && node->link != value) {
        prev = node;
        node = node->next;
    }

    if(node) {
        if(prev)
            prev->next = node->next;
        else
            *list = node->next;

        if(freefunc)
            freefunc(node->link);

        MEM_freeN(node);
    }
}

/* removes all elements in source from target */
static void linklist_remove_list(LinkNode **target, LinkNode *source,
                 LinkNodeFreeFP freefunc)
{
    for(; source; source = source->next)
        linklist_remove_first(target, source->link, freefunc);
}

#ifdef EDGESPLIT_DEBUG_0
static void print_ptr(void *ptr)
{
    printf("%p\n", ptr);
}

static void print_edge(void *ptr)
{
    SmoothEdge *edge = ptr;
    printf(" %4d", edge->newIndex);
}

static void print_face(void *ptr)
{
    SmoothFace *face = ptr;
    printf(" %4d", face->newIndex);
}
#endif

typedef struct ReplaceData {
    void *find;
    void *replace;
} ReplaceData;

static void edge_replace_vert(void *ptr, void *userdata)
{
    SmoothEdge *edge = ptr;
    SmoothVert *find = ((ReplaceData *)userdata)->find;
    SmoothVert *replace = ((ReplaceData *)userdata)->replace;
    int i;

#ifdef EDGESPLIT_DEBUG_3
    printf("replacing vert %4d with %4d in edge %4d",
        find->newIndex, replace->newIndex, edge->newIndex);
    printf(": {%4d, %4d}", edge->verts[0]->newIndex, edge->verts[1]->newIndex);
#endif

    for(i = 0; i < SMOOTHEDGE_NUM_VERTS; i++) {
        if(edge->verts[i] == find) {
            linklist_append_list_unique(&replace->faces, edge->faces);
            linklist_remove_list(&find->faces, edge->faces, NULL);

            edge->verts[i] = replace;
        }
    }

#ifdef EDGESPLIT_DEBUG_3
    printf(" -> {%4d, %4d}\n", edge->verts[0]->newIndex, edge->verts[1]->newIndex);
#endif
}

static void face_replace_vert(void *ptr, void *userdata)
{
    SmoothFace *face = ptr;
    int i;

    for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++)
        edge_replace_vert(face->edges[i], userdata);
}

static void face_replace_edge(void *ptr, void *userdata)
{
    SmoothFace *face = ptr;
    SmoothEdge *find = ((ReplaceData *)userdata)->find;
    SmoothEdge *replace = ((ReplaceData *)userdata)->replace;
    int i;

#ifdef EDGESPLIT_DEBUG_3
    printf("replacing edge %4d with %4d in face %4d",
        find->newIndex, replace->newIndex, face->newIndex);
    if(face->edges[3])
        printf(": {%2d %2d %2d %2d}",
            face->edges[0]->newIndex, face->edges[1]->newIndex,
            face->edges[2]->newIndex, face->edges[3]->newIndex);
    else
        printf(": {%2d %2d %2d}",
            face->edges[0]->newIndex, face->edges[1]->newIndex,
            face->edges[2]->newIndex);
#endif

    for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++) {
        if(face->edges[i] == find) {
            linklist_remove_first(&face->edges[i]->faces, face, NULL);
            BLI_linklist_prepend(&replace->faces, face);
            face->edges[i] = replace;
        }
    }

#ifdef EDGESPLIT_DEBUG_3
    if(face->edges[3])
        printf(" -> {%2d %2d %2d %2d}\n",
            face->edges[0]->newIndex, face->edges[1]->newIndex,
            face->edges[2]->newIndex, face->edges[3]->newIndex);
    else
        printf(" -> {%2d %2d %2d}\n",
            face->edges[0]->newIndex, face->edges[1]->newIndex,
            face->edges[2]->newIndex);
#endif
}

static int edge_is_loose(SmoothEdge *edge)
{
    return !(edge->faces && edge->faces->next);
}

static int edge_is_sharp(SmoothEdge *edge)
{
#ifdef EDGESPLIT_DEBUG_1
    printf("edge %d: ", edge->newIndex);
#endif
    if(edge->flag & ME_SHARP) {
        /* edge can only be sharp if it has at least 2 faces */
        if(!edge_is_loose(edge)) {
#ifdef EDGESPLIT_DEBUG_1
            printf("sharp\n");
#endif
            return 1;
        } else {
            /* edge is loose, so it can't be sharp */
            edge->flag &= ~ME_SHARP;
        }
    }

#ifdef EDGESPLIT_DEBUG_1
    printf("not sharp\n");
#endif
    return 0;
}

/* finds another sharp edge which uses vert, by traversing faces around the
 * vert until it does one of the following:
 * - hits a loose edge (the edge is returned)
 * - hits a sharp edge (the edge is returned)
 * - returns to the start edge (NULL is returned)
 */
static SmoothEdge *find_other_sharp_edge(SmoothVert *vert, SmoothEdge *edge, LinkNode **visited_faces)
{
    SmoothFace *face = NULL;
    SmoothEdge *edge2 = NULL;
    /* holds the edges we've seen so we can avoid looping indefinitely */
    LinkNode *visited_edges = NULL;
#ifdef EDGESPLIT_DEBUG_1
    printf("=== START === find_other_sharp_edge(edge = %4d, vert = %4d)\n",
        edge->newIndex, vert->newIndex);
#endif

    /* get a face on which to start */
    if(edge->faces) face = edge->faces->link;
    else return NULL;

    /* record this edge as visited */
    BLI_linklist_prepend(&visited_edges, edge);

    /* get the next edge */
    edge2 = other_edge(face, vert, edge);

    /* record this face as visited */
    if(visited_faces)
        BLI_linklist_prepend(visited_faces, face);

    /* search until we hit a loose edge or a sharp edge or an edge we've
    * seen before
    */
    while(face && !edge_is_sharp(edge2)
             && !linklist_contains(visited_edges, edge2)) {
#ifdef EDGESPLIT_DEBUG_3
        printf("current face %4d; current edge %4d\n", face->newIndex,
            edge2->newIndex);
#endif
        /* get the next face */
        face = other_face(edge2, face);

        /* if face == NULL, edge2 is a loose edge */
        if(face) {
            /* record this face as visited */
            if(visited_faces)
                BLI_linklist_prepend(visited_faces, face);

            /* record this edge as visited */
            BLI_linklist_prepend(&visited_edges, edge2);

            /* get the next edge */
            edge2 = other_edge(face, vert, edge2);
#ifdef EDGESPLIT_DEBUG_3
            printf("next face %4d; next edge %4d\n",
                face->newIndex, edge2->newIndex);
        } else {
            printf("loose edge: %4d\n", edge2->newIndex);
#endif
        }
    }

    /* either we came back to the start edge or we found a sharp/loose edge */
    if(linklist_contains(visited_edges, edge2))
        /* we came back to the start edge */
        edge2 = NULL;

    BLI_linklist_free(visited_edges, NULL);

#ifdef EDGESPLIT_DEBUG_1
    printf("=== END === find_other_sharp_edge(edge = %4d, vert = %4d), "
        "returning edge %d\n",
        edge->newIndex, vert->newIndex, edge2 ? edge2->newIndex : -1);
#endif
    return edge2;
}

static void split_single_vert(SmoothVert *vert, SmoothFace *face,
                  SmoothMesh *mesh)
{
    SmoothVert *copy_vert;
    ReplaceData repdata;

    copy_vert = smoothvert_copy(vert, mesh);

    if(copy_vert == NULL) {
        /* bug [#26316], this prevents a segfault
         * but this still needs fixing */
        return;
    }

    repdata.find = vert;
    repdata.replace = copy_vert;
    face_replace_vert(face, &repdata);
}

typedef struct PropagateEdge {
    struct PropagateEdge *next, *prev;
    SmoothEdge *edge;
    SmoothVert *vert;
} PropagateEdge;

static void push_propagate_stack(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
{
    PropagateEdge *pedge = mesh->reusestack.first;

    if(pedge) {
        BLI_remlink(&mesh->reusestack, pedge);
    }
    else {
        if(!mesh->arena) {
            mesh->arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "edgesplit arena");
            BLI_memarena_use_calloc(mesh->arena);
        }

        pedge = BLI_memarena_alloc(mesh->arena, sizeof(PropagateEdge));
    }

    pedge->edge = edge;
    pedge->vert = vert;
    BLI_addhead(&mesh->propagatestack, pedge);
}

static void pop_propagate_stack(SmoothEdge **edge, SmoothVert **vert, SmoothMesh *mesh)
{
    PropagateEdge *pedge = mesh->propagatestack.first;

    if(pedge) {
        *edge = pedge->edge;
        *vert = pedge->vert;
        BLI_remlink(&mesh->propagatestack, pedge);
        BLI_addhead(&mesh->reusestack, pedge);
    }
    else {
        *edge = NULL;
        *vert = NULL;
    }
}

static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh);

static void propagate_split(SmoothEdge *edge, SmoothVert *vert,
                SmoothMesh *mesh)
{
    SmoothEdge *edge2;
    LinkNode *visited_faces = NULL;
#ifdef EDGESPLIT_DEBUG_1
    printf("=== START === propagate_split(edge = %4d, vert = %4d)\n",
        edge->newIndex, vert->newIndex);
#endif

    edge2 = find_other_sharp_edge(vert, edge, &visited_faces);

    if(!edge2) {
        /* didn't find a sharp or loose edge, so we've hit a dead end */
    } else if(!edge_is_loose(edge2)) {
        /* edge2 is not loose, so it must be sharp */
        if(edge_is_loose(edge)) {
            /* edge is loose, so we can split edge2 at this vert */
            split_edge(edge2, vert, mesh);
        } else if(edge_is_sharp(edge)) {
            /* both edges are sharp, so we can split the pair at vert */
            split_edge(edge, vert, mesh);
        } else {
            /* edge is not sharp, so try to split edge2 at its other vert */
            split_edge(edge2, other_vert(edge2, vert), mesh);
        }
    } else { /* edge2 is loose */
        if(edge_is_loose(edge)) {
            SmoothVert *vert2;
            ReplaceData repdata;

            /* can't split edge, what should we do with vert? */
            if(linklist_subset(vert->faces, visited_faces)) {
                /* vert has only one fan of faces attached; don't split it */
            } else {
                /* vert has more than one fan of faces attached; split it */
                vert2 = smoothvert_copy(vert, mesh);

                /* fails in rare cases, see [#26993] */
                if(vert2) {
                    /* replace vert with its copy in visited_faces */
                    repdata.find = vert;
                    repdata.replace = vert2;
                    BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
                }
            }
        } else {
            /* edge is not loose, so it must be sharp; split it */
            split_edge(edge, vert, mesh);
        }
    }

    BLI_linklist_free(visited_faces, NULL);
#ifdef EDGESPLIT_DEBUG_1
    printf("=== END === propagate_split(edge = %4d, vert = %4d)\n",
        edge->newIndex, vert->newIndex);
#endif
}

static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
{
    SmoothEdge *edge2;
    SmoothVert *vert2;
    ReplaceData repdata;
    /* the list of faces traversed while looking for a sharp edge */
    LinkNode *visited_faces = NULL;
#ifdef EDGESPLIT_DEBUG_1
    printf("=== START === split_edge(edge = %4d, vert = %4d)\n",
        edge->newIndex, vert->newIndex);
#endif

    edge2 = find_other_sharp_edge(vert, edge, &visited_faces);

    if(!edge2) {
        /* didn't find a sharp or loose edge, so try the other vert */
        vert2 = other_vert(edge, vert);
        push_propagate_stack(edge, vert2, mesh);
    } else if(!edge_is_loose(edge2)) {
        /* edge2 is not loose, so it must be sharp */
        SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
        SmoothEdge *copy_edge2 = smoothedge_copy(edge2, mesh);
        SmoothVert *vert2;

        /* replace edge with its copy in visited_faces */
        repdata.find = edge;
        repdata.replace = copy_edge;
        BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);

        /* replace edge2 with its copy in visited_faces */
        repdata.find = edge2;
        repdata.replace = copy_edge2;
        BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);

        vert2 = smoothvert_copy(vert, mesh);

        /* replace vert with its copy in visited_faces (must be done after
        * edge replacement so edges have correct vertices)
        */
        repdata.find = vert;
        repdata.replace = vert2;
        BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);

        /* all copying and replacing is done; the mesh should be consistent.
        * now propagate the split to the vertices at either end
        */
        push_propagate_stack(copy_edge, other_vert(copy_edge, vert2), mesh);
        push_propagate_stack(copy_edge2, other_vert(copy_edge2, vert2), mesh);

        if(smoothedge_has_vert(edge, vert))
            push_propagate_stack(edge, vert, mesh);
    } else {
        /* edge2 is loose */
        SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
        SmoothVert *vert2;

        /* replace edge with its copy in visited_faces */
        repdata.find = edge;
        repdata.replace = copy_edge;
        BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);

        vert2 = smoothvert_copy(vert, mesh);

        /* bug [#29205] which is caused by exactly the same reason as [#26316]
           this check will only prevent crash without fixing actual issue and
           some vertices can stay unsplitted when they should (sergey) */
        if(vert2) {
            /* replace vert with its copy in visited_faces (must be done after
             * edge replacement so edges have correct vertices)
             */
            repdata.find = vert;
            repdata.replace = vert2;
            BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
        }

        /* copying and replacing is done; the mesh should be consistent.
        * now propagate the split to the vertex at the other end
        */
        push_propagate_stack(copy_edge, other_vert(copy_edge, vert2), mesh);

        if(smoothedge_has_vert(edge, vert))
            push_propagate_stack(edge, vert, mesh);
    }

    BLI_linklist_free(visited_faces, NULL);
#ifdef EDGESPLIT_DEBUG_1
    printf("=== END === split_edge(edge = %4d, vert = %4d)\n",
        edge->newIndex, vert->newIndex);
#endif
}

static void tag_and_count_extra_edges(SmoothMesh *mesh, float split_angle,
                      int flags, int *extra_edges)
{
    /* if normal1 dot normal2 < threshold, angle is greater, so split */
    /* FIXME not sure if this always works */
    /* 0.00001 added for floating-point rounding */
    float threshold = cos((split_angle + 0.00001f) * (float)M_PI / 180.0f);
    int i;

    *extra_edges = 0;

    /* loop through edges, counting potential new ones */
    for(i = 0; i < mesh->num_edges; i++) {
        SmoothEdge *edge = &mesh->edges[i];
        int sharp = 0;

        /* treat all non-manifold edges (3 or more faces) as sharp */
        if(edge->faces && edge->faces->next && edge->faces->next->next) {
            LinkNode *node;

            /* this edge is sharp */
            sharp = 1;

            /* add an extra edge for every face beyond the first */
            *extra_edges += 2;
            for(node = edge->faces->next->next->next; node; node = node->next)
                (*extra_edges)++;
        } else if((flags & (MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG))
                     && !edge_is_loose(edge)) {
            /* (the edge can only be sharp if we're checking angle or flag,
            * and it has at least 2 faces) */

            /* if we're checking the sharp flag and it's set, good */
            if((flags & MOD_EDGESPLIT_FROMFLAG) && (edge->flag & ME_SHARP)) {
                /* this edge is sharp */
                sharp = 1;

                (*extra_edges)++;
            } else if(flags & MOD_EDGESPLIT_FROMANGLE) {
                /* we know the edge has 2 faces, so check the angle */
                SmoothFace *face1 = edge->faces->link;
                SmoothFace *face2 = edge->faces->next->link;
                float edge_angle_cos = dot_v3v3(face1->normal,
                face2->normal);

                if(edge_angle_cos < threshold) {
                    /* this edge is sharp */
                    sharp = 1;

                    (*extra_edges)++;
                }
            }
        }

        /* set/clear sharp flag appropriately */
        if(sharp) edge->flag |= ME_SHARP;
        else edge->flag &= ~ME_SHARP;
    }
}

static void split_sharp_edges(SmoothMesh *mesh, float split_angle, int flags)
{
    SmoothVert *vert;
    int i;
    /* if normal1 dot normal2 < threshold, angle is greater, so split */
    /* FIXME not sure if this always works */
    /* 0.00001 added for floating-point rounding */
    mesh->threshold = cosf((split_angle + 0.00001f) * (float)M_PI / 180.0f);
    mesh->flags = flags;

    /* loop through edges, splitting sharp ones */
    /* can't use an iterator here, because we'll be adding edges */
    for(i = 0; i < mesh->num_edges; i++) {
        SmoothEdge *edge = &mesh->edges[i];

        if(edge_is_sharp(edge)) {
            split_edge(edge, edge->verts[0], mesh);

            do {
                pop_propagate_stack(&edge, &vert, mesh);
                if(edge && smoothedge_has_vert(edge, vert))
                    propagate_split(edge, vert, mesh);
            } while(edge);
        }
    }
}

static int count_bridge_verts(SmoothMesh *mesh)
{
    int i, j, count = 0;

    for(i = 0; i < mesh->num_faces; i++) {
        SmoothFace *face = &mesh->faces[i];

        for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
            SmoothEdge *edge = face->edges[j];
            SmoothEdge *next_edge;
            SmoothVert *vert = edge->verts[1 - face->flip[j]];
            int next = (j + 1) % SMOOTHFACE_MAX_EDGES;

            /* wrap next around if at last edge */
            if(!face->edges[next]) next = 0;

            next_edge = face->edges[next];

            /* if there are other faces sharing this vertex but not
            * these edges, the vertex will be split, so count it
            */
            /* vert has to have at least one face (this one), so faces != 0 */
            if(!edge->faces->next && !next_edge->faces->next
                         && vert->faces->next) {
                count++;
                         }
        }
    }

    /* each bridge vert will be counted once per face that uses it,
    * so count is too high, but it's ok for now
    */
    return count;
}

static void split_bridge_verts(SmoothMesh *mesh)
{
    int i,j;

    for(i = 0; i < mesh->num_faces; i++) {
        SmoothFace *face = &mesh->faces[i];

        for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
            SmoothEdge *edge = face->edges[j];
            SmoothEdge *next_edge;
            SmoothVert *vert = edge->verts[1 - face->flip[j]];
            int next = (j + 1) % SMOOTHFACE_MAX_EDGES;

            /* wrap next around if at last edge */
            if(!face->edges[next]) next = 0;

            next_edge = face->edges[next];

            /* if there are other faces sharing this vertex but not
            * these edges, split the vertex
            */
            /* vert has to have at least one face (this one), so faces != 0 */
            if(!edge->faces->next && !next_edge->faces->next
                         && vert->faces->next)
                /* FIXME this needs to find all faces that share edges with
                * this one and split off together
                */
                split_single_vert(vert, face, mesh);
        }
    }
}

static DerivedMesh *edgesplitModifier_do(EdgeSplitModifierData *emd, DerivedMesh *dm)
{
    SmoothMesh *mesh;
    DerivedMesh *result;
    int max_verts, max_edges;

    if(!(emd->flags & (MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG)))
        return dm;

    /* 1. make smoothmesh with initial number of elements */
    mesh = smoothmesh_from_derivedmesh(dm);

    /* 2. count max number of elements to add */
    tag_and_count_extra_edges(mesh, emd->split_angle, emd->flags, &max_edges);
    max_verts = max_edges * 2 + mesh->max_verts;
    max_verts += count_bridge_verts(mesh);
    max_edges += mesh->max_edges;

    /* 3. reallocate smoothmesh arrays & copy elements across */
    /* 4. remap copied elements' pointers to point into the new arrays */
    smoothmesh_resize_verts(mesh, max_verts);
    smoothmesh_resize_edges(mesh, max_edges);

#ifdef EDGESPLIT_DEBUG_1
    printf("********** Pre-split **********\n");
    smoothmesh_print(mesh);
#endif

    split_sharp_edges(mesh, emd->split_angle, emd->flags);
#ifdef EDGESPLIT_DEBUG_1
    printf("********** Post-edge-split **********\n");
    smoothmesh_print(mesh);
#endif

    split_bridge_verts(mesh);

#ifdef EDGESPLIT_DEBUG_1
    printf("********** Post-vert-split **********\n");
    smoothmesh_print(mesh);
#endif

#ifdef EDGESPLIT_DEBUG_0
    printf("Edgesplit: Estimated %d verts & %d edges, "
        "found %d verts & %d edges\n", max_verts, max_edges,
        mesh->num_verts, mesh->num_edges);
#endif

    result = CDDM_from_smoothmesh(mesh);
    smoothmesh_free(mesh);

    return result;
}

static DerivedMesh *applyModifier(ModifierData *md, Object *UNUSED(ob),
                        DerivedMesh *derivedData,
                        int UNUSED(useRenderParams),
                        int UNUSED(isFinalCalc))
{
    DerivedMesh *result;
    EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;

    result = edgesplitModifier_do(emd, derivedData);

    if(result != derivedData)
        CDDM_calc_normals(result);

    return result;
}

static DerivedMesh *applyModifierEM(ModifierData *md, Object *ob,
                        struct EditMesh *UNUSED(editData),
                        DerivedMesh *derivedData)
{
    return applyModifier(md, ob, derivedData, 0, 1);
}


ModifierTypeInfo modifierType_EdgeSplit = {
    /* name */              "EdgeSplit",
    /* structName */        "EdgeSplitModifierData",
    /* structSize */        sizeof(EdgeSplitModifierData),
    /* type */              eModifierTypeType_Constructive,
    /* flags */             eModifierTypeFlag_AcceptsMesh
                            | eModifierTypeFlag_AcceptsCVs
                            | eModifierTypeFlag_SupportsMapping
                            | eModifierTypeFlag_SupportsEditmode
                            | eModifierTypeFlag_EnableInEditmode,

    /* copyData */          copyData,
    /* deformVerts */       NULL,
    /* deformMatrices */    NULL,
    /* deformVertsEM */     NULL,
    /* deformMatricesEM */  NULL,
    /* applyModifier */     applyModifier,
    /* applyModifierEM */   applyModifierEM,
    /* initData */          initData,
    /* requiredDataMask */  NULL,
    /* freeData */          NULL,
    /* isDisabled */        NULL,
    /* updateDepgraph */    NULL,
    /* dependsOnTime */     NULL,
    /* dependsOnNormals */  NULL,
    /* foreachObjectLink */ NULL,
    /* foreachIDLink */     NULL,
    /* foreachTexLink */    NULL,
};