/*
* $Id$
*
* ***** 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 "DNA_meshdata_types.h"

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

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

#include "MEM_guardedalloc.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];

	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, int flags,
			 float threshold)
{
#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, float threshold, int flags)
{
	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, flags, threshold)
			 && !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);

	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,
					  mesh->threshold, mesh->flags);

	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, mesh->flags, mesh->threshold)) {
			/* 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);

				/* 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,
					  mesh->threshold, mesh->flags);

	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);

		/* 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.00001) * M_PI / 180.0);
	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 = cos((split_angle + 0.00001) * M_PI / 180.0);
	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, flags, mesh->threshold)) {
			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,
					 Object *ob, 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 *ob, DerivedMesh *derivedData,
  int useRenderParams, int isFinalCalc)
{
	DerivedMesh *result;
	EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;

	result = edgesplitModifier_do(emd, ob, derivedData);

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

	return result;
}

static DerivedMesh *applyModifierEM(
		ModifierData *md, Object *ob, struct EditMesh *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 */       0,
	/* deformVertsEM */     0,
	/* deformMatricesEM */  0,
	/* applyModifier */     applyModifier,
	/* applyModifierEM */   applyModifierEM,
	/* initData */          initData,
	/* requiredDataMask */  0,
	/* freeData */          0,
	/* isDisabled */        0,
	/* updateDepgraph */    0,
	/* dependsOnTime */     0,
	/* foreachObjectLink */ 0,
	/* foreachIDLink */     0,
};