/*
 * ***** 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.
 *
 * Contributor(s): Campbell Barton
 *
 * ***** END GPL LICENSE BLOCK *****
 */

/** \file blender/bmesh/operators/bmo_offset_edgeloops.c
 *  \ingroup bmesh
 *
 * Simple edge offset functionality.
 *
 * \note Actual offset is done by edge-slide.
 * (this only changes topology)
 */

#include "MEM_guardedalloc.h"

#include "BLI_math.h"
#include "BLI_alloca.h"
#include "BLI_stackdefines.h"

#include "BKE_customdata.h"

#include "bmesh.h"

#include "intern/bmesh_operators_private.h" /* own include */

#define USE_CAP_OPTION

#define ELE_NEW			(1 << 0)

#ifdef USE_CAP_OPTION
#define ELE_VERT_ENDPOINT	(1 << 1)
#endif

/* set for debugging */
#define OFFSET 0.0f

static BMFace *bm_face_split_walk_back(
        BMesh *bm, BMLoop *l_src,
        BMLoop **r_l)
{
	float (*cos)[3];
	BMLoop *l_dst;
	BMFace *f;
	int num, i;

	for (l_dst = l_src->prev, num = 0; BM_elem_index_get(l_dst->prev->v) != -1; l_dst = l_dst->prev, num++) {
		/* pass */
	}

	BLI_assert(num != 0);

	cos = BLI_array_alloca(
	          cos, num);

	for (l_dst = l_src->prev, i = 0; BM_elem_index_get(l_dst->prev->v) != -1; l_dst = l_dst->prev, i++) {
		copy_v3_v3(cos[num - (i + 1)], l_dst->v->co);
	}

	f = BM_face_split_n( bm, l_src->f, l_dst->prev, l_src->next, cos, num, r_l, NULL);

	return f;
}

void bmo_offset_edgeloops_exec(BMesh *bm, BMOperator *op)
{
	const int edges_num = BMO_slot_buffer_count(op->slots_in, "edges");
	BMVert **verts;
	STACK_DECLARE(verts);
	int i;

#ifdef USE_CAP_OPTION
	bool use_cap_endpoint = BMO_slot_bool_get(op->slots_in,  "use_cap_endpoint");
	int v_edges_max = 0;
#endif

	BMOIter oiter;

	/* only so we can detect new verts (index == -1) */
	BM_mesh_elem_index_ensure(bm, BM_VERT);

	BM_mesh_elem_hflag_disable_all(bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_TAG, false);

	/* over alloc */
	verts = MEM_mallocN(sizeof(*verts) * (edges_num * 2), __func__);

	STACK_INIT(verts, (edges_num * 2));

	{
		BMEdge *e;
		BMO_ITER (e, &oiter, op->slots_in, "edges", BM_EDGE) {
			int j;

			BM_elem_flag_enable(e, BM_ELEM_TAG);

			for (j = 0; j < 2; j++) {
				BMVert *v_edge = *(&(e->v1) + j);
				if (!BM_elem_flag_test(v_edge, BM_ELEM_TAG)) {
					BM_elem_flag_enable(v_edge, BM_ELEM_TAG);
					STACK_PUSH(verts, v_edge);
				}
			}
		}
	}


	/* -------------------------------------------------------------------- */
	/* Remove verts only used by tagged edges */

	for (i = 0; i < STACK_SIZE(verts); i++) {
		BMIter iter;
		int flag = 0;
		BMEdge *e;

		BM_ITER_ELEM (e, &iter, verts[i], BM_EDGES_OF_VERT) {
			flag |= BM_elem_flag_test(e, BM_ELEM_TAG) ? 1 : 2;
			if (flag == (1 | 2)) {
				break;
			}
		}

		/* only boundary verts are interesting */
		if (flag != (1 | 2)) {
			STACK_REMOVE(verts, i);
		}
	}

	/* possible but unlikely we have no mixed vertices */
	if (UNLIKELY(STACK_SIZE(verts) == 0)) {
		MEM_freeN(verts);
		return;
	}

	/* main loop */
	for (i = 0; i < STACK_SIZE(verts); i++) {
		int v_edges_num = 0;
		int v_edges_num_untag = 0;
		BMVert *v = verts[i];
		BMIter iter;
		BMEdge *e;

		BM_ITER_ELEM (e, &iter, verts[i], BM_EDGES_OF_VERT) {
			if (!BM_elem_flag_test(e, BM_ELEM_TAG)) {
				BMVert *v_other;
				BMIter liter;
				BMLoop *l;

				BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) {
					BM_elem_flag_enable(l->f, BM_ELEM_TAG);
				}

				v_other = BM_edge_other_vert(e, v);
				BM_edge_split(bm, e, v_other, NULL, 1.0f - OFFSET);
			}
			else {
				v_edges_num_untag += 1;
			}

			v_edges_num += 1;
		}

#ifdef USE_CAP_OPTION
		if (v_edges_num_untag == 1) {
			BMO_vert_flag_enable(bm, v, ELE_VERT_ENDPOINT);
		}

		CLAMP_MIN(v_edges_max, v_edges_num);
#endif

	}


	for (i = 0; i < STACK_SIZE(verts); i++) {
		BMVert *v = verts[i];
		BMIter liter;
		BMLoop *l;

		BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
			if (BM_elem_flag_test(l->f, BM_ELEM_TAG) &&
			    (l->f->len != 3))
			{
				BMFace *f_cmp = l->f;
				if ((BM_elem_index_get(l->next->v) == -1) &&
				    (BM_elem_index_get(l->prev->v) == -1))
				{
#ifdef USE_CAP_OPTION
					if (use_cap_endpoint || (BMO_vert_flag_test(bm, v, ELE_VERT_ENDPOINT) == 0))
#endif
					{
						BMLoop *l_new;
						BM_face_split(bm, l->f, l->prev, l->next, &l_new, NULL, true);
						BLI_assert(f_cmp == l->f);
						BLI_assert(f_cmp != l_new->f);
						UNUSED_VARS_NDEBUG(f_cmp);
						BMO_edge_flag_enable(bm, l_new->e, ELE_NEW);
					}
				}
				else if (l->f->len > 4) {
					if (BM_elem_flag_test(l->e,       BM_ELEM_TAG) !=
					    BM_elem_flag_test(l->prev->e, BM_ELEM_TAG))
					{
						if (BM_elem_index_get(l->next->v) == -1) {
							if (BM_elem_index_get(l->prev->prev->v) == -1) {
								BMLoop *l_new;
								BM_face_split(bm, l->f, l->prev->prev, l->next, &l_new, NULL, true);
								BLI_assert(f_cmp == l->f);
								BLI_assert(f_cmp != l_new->f);
								BMO_edge_flag_enable(bm, l_new->e, ELE_NEW);
								BM_elem_flag_disable(l->f, BM_ELEM_TAG);
							}
							else {
								/* walk backwards */
								BMLoop *l_new;
								bm_face_split_walk_back(bm, l, &l_new);
								do {
									BMO_edge_flag_enable(bm, l_new->e, ELE_NEW);
									l_new = l_new->next;
								} while (BM_vert_is_edge_pair(l_new->v));
								BM_elem_flag_disable(l->f, BM_ELEM_TAG);
							}
						}

						/* Note: instead of duplicate code in alternate direction,
						 * we can be sure to hit the other vertex, so the code above runs. */
#if 0
						else if (BM_elem_index_get(l->prev->v) == -1) {
							if (BM_elem_index_get(l->next->next->v) == -1) {
							}
						}
#endif
					}
				}
			}
		}
	}

#ifdef USE_CAP_OPTION
	if (use_cap_endpoint == false) {
		BMVert **varr = BLI_array_alloca(varr, v_edges_max);
		STACK_DECLARE(varr);
		BMVert *v;

		for (i = 0; i < STACK_SIZE(verts); i++) {
			BMIter iter;
			BMEdge *e;

			v = verts[i];

			STACK_INIT(varr, v_edges_max);

			BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
				BMVert *v_other;
				v_other = BM_edge_other_vert(e, v);
				if (BM_elem_index_get(v_other) == -1) {
					if (BM_vert_is_edge_pair(v_other)) {
						/* defer bmesh_kernel_join_edge_kill_vert to avoid looping over data we're removing */
						v_other->e = e;
						STACK_PUSH(varr, v_other);
					}
				}
			}

			while ((v = STACK_POP(varr))) {
				bmesh_kernel_join_edge_kill_vert(bm, v->e, v, true, false, false);
			}
		}
	}
#endif

	MEM_freeN(verts);

	BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, ELE_NEW);
}
