/*
								+----------------------------------+
								|                                  |
								|   ***  T-Junction removal  ***   |
								|                                  |
								|   Copyright © -tHE SWINe- 2013   |
								|                                  |
								|          TJunction.cpp           |
								|                                  |
								+----------------------------------+
*/

/**
 *	@file lml/TJunction.cpp
 *	@author -tHE SWINe-
 *	@date 2013
 *	@brief T-Junction removal
 */

#if defined(_MSC_VER) && !defined(__MWERKS__)
#pragma warning(disable:4786)
#endif
// disable warning C4786 "identifier was truncated to '255' characters in the debug information"

#include "../NewFix.h"
#include "../CallStack.h"
#include <algorithm>
#include <vector>
#include <math.h>
#include "TJunctions.h"

/*
 *								=== CRemove_TJunctions::TEdge ===
 */

CRemove_TJunctions::TEdge::TEdge(_TyPolygon &r_poly, size_t n_edge,
	size_t n_poly_vertex_num, float f_epsilon_ex)
	:p_polygon(&r_poly), n_polygon_edge(n_edge),
	f_min_proj(1), f_max_proj(0), b_proj_swapped(false)
{
	_ASSERTE(r_poly.n_Vertex_Num() == n_poly_vertex_num);
	p_point[0] = r_poly.t_Vertex(n_edge);
	p_point[1] = r_poly.t_Vertex((n_edge + 1) % n_poly_vertex_num);

	Vector3f v_dir = p_point[1] - p_point[0];
	float f_length = v_dir.f_Length();
	if(f_length < f_epsilon_ex) {
		n_uncertainty = size_t(-1);
		n_hash_bin = size_t(-1);
		return; // don't want this
	}

	v_dir *= hash_Size / f_length; // normalize to hash_Size
	for(int n = 0; n < 3; ++ n) {
		v_dir[n] = float(fabs(v_dir[n]));
		// not very nice, could keep the sign and put the value to the bin with lower index;
		// will it work with sloped edges, or will anti-edges end up in different bins? // t_odo think about it
		// tried rotating the mesh a bit and it still removes all the t-junctions correctly,
		// seems to work quite well (all the same directions still end up in the same bin,
		// just have more collisions but they get sorted out by the distance check)
	}
	// calculate absolute direction

	v_hash_bin = Vector3i(int(v_dir.x), int(v_dir.y), int(v_dir.z));
	// quantized line direction (0, 0, 0) to (hash_Size, hash_Size, hash_Size))

	n_hash_bin = v_hash_bin.x + hash_Size * (v_hash_bin.y + hash_Size * v_hash_bin.z);
	// calculates a quantization bin

	// line length is f_length
	// if we change either point by epsilon, the direction changes by 2 epsilon
	// if new length = hash_Size = l * hash_Size / f_length, then direction change is 2 * epsilon * hash_Size / f_length

	n_uncertainty = int(ceil(2 * f_epsilon_ex * hash_Size / f_length));
	// how big search region do we need to go through to find colinear lines
}

void CRemove_TJunctions::TEdge::Get_Planes(Plane3f &r_tangent,
	Plane3f &r_bitangent, float f_epsilon_ex) const
{
	Vector3f v_dir = p_point[1] - p_point[0];
	_ASSERTE(v_dir.f_Length() > f_epsilon_ex); // not short ones
	v_dir.Normalize();
	Vector3f v_up;
	if(fabs(v_dir.x) > fabs(v_dir.y) || fabs(v_dir.x) > fabs(v_dir.z))
		v_up = Vector3f(0, 1, 0);
	else
		v_up = Vector3f(1, 0, 0);
	Plane3f t_tangent_plane(p_point[0], v_dir, v_up, plane::from_position_edge_vecs);
	Plane3f t_bitangent_plane(p_point[0], v_dir,
		t_tangent_plane.v_normal, plane::from_position_edge_vecs);
	_ASSERTE(fabs(t_tangent_plane.v_normal.f_Dot(t_bitangent_plane.v_normal)) < f_epsilon_ex); // the planes are orthogonal
	_ASSERTE(t_tangent_plane.n_Vector_Pos(p_point[0], f_epsilon_ex) == plane_Onplane); // both points are onplane
	_ASSERTE(t_tangent_plane.n_Vector_Pos(p_point[1], f_epsilon_ex) == plane_Onplane); // both points are onplane
	_ASSERTE(t_bitangent_plane.n_Vector_Pos(p_point[0], f_epsilon_ex) == plane_Onplane); // both points are onplane
	_ASSERTE(t_bitangent_plane.n_Vector_Pos(p_point[1], f_epsilon_ex) == plane_Onplane); // both points are onplane

	r_tangent = t_tangent_plane;
	r_bitangent = t_bitangent_plane;
}

bool CRemove_TJunctions::TEdge::b_Match(const TEdge &r_edge, float f_epsilon_ex) const
{
	Plane3f t_tangent_plane, t_bitangent_plane;
	Get_Planes(t_tangent_plane, t_bitangent_plane, f_epsilon_ex);
	if(t_tangent_plane.n_Vector_Pos(r_edge.p_point[0], f_epsilon_ex) != plane_Onplane ||
	   t_tangent_plane.n_Vector_Pos(r_edge.p_point[1], f_epsilon_ex) != plane_Onplane ||
	   t_bitangent_plane.n_Vector_Pos(r_edge.p_point[0], f_epsilon_ex) != plane_Onplane ||
	   t_bitangent_plane.n_Vector_Pos(r_edge.p_point[1], f_epsilon_ex) != plane_Onplane)
		return false;
	r_edge.Get_Planes(t_tangent_plane, t_bitangent_plane, f_epsilon_ex);
	if(t_tangent_plane.n_Vector_Pos(p_point[0], f_epsilon_ex) != plane_Onplane ||
	   t_tangent_plane.n_Vector_Pos(p_point[1], f_epsilon_ex) != plane_Onplane ||
	   t_bitangent_plane.n_Vector_Pos(p_point[0], f_epsilon_ex) != plane_Onplane ||
	   t_bitangent_plane.n_Vector_Pos(p_point[1], f_epsilon_ex) != plane_Onplane)
		return false;
	// both edges must define planes that are close enough to the other edge

	return true;
}

/*
 *								=== ~CRemove_TJunctions::TEdge ===
 */

/*
 *								=== CRemove_TJunctions ===
 */

#ifdef __TJUNCTIONS_GENERATE_DEBUG_INFO

size_t CRemove_TJunctions::n_Remove_TJunctions(CPolyMesh &r_mesh,
	std::vector<Vector3f> &r_debug_line_list,
	float f_edge_dist_epsilon /*= f_epsilon*/,
	float f_vertex_dist_epsilon /*= f_epsilon*/) // throw(std::bad_alloc)
{
	CVoidProgressIndicator progress;

	_TyFixupMap polygon_fixup_map;
	{
		_TyEdgeMap edge_map;
		HashEdges(edge_map, r_mesh, f_edge_dist_epsilon, progress);
		// build a list of all polygon edges and group them by direction
		// so that edges that are close to each other are in the same bins

		Fill_TJunctionFixup_Map(polygon_fixup_map, edge_map,
			f_edge_dist_epsilon, f_vertex_dist_epsilon, progress);
		// go through bins, calculate projections, distribute new vertices to the sorted lists
	}

	CDebugLineGenerator debug_gen(r_debug_line_list);
	return n_Fix_TJunctions(r_mesh, polygon_fixup_map,
		debug_gen, f_edge_dist_epsilon, progress);
}

#endif // __TJUNCTIONS_GENERATE_DEBUG_INFO

size_t CRemove_TJunctions::n_Remove_TJunctions(CPolyMesh &r_mesh,
	float f_edge_dist_epsilon /*= f_epsilon*/,
	float f_vertex_dist_epsilon /*= f_epsilon*/) // throw(std::bad_alloc)
{
	CVoidProgressIndicator progress;

	_TyFixupMap polygon_fixup_map;
	{
		_TyEdgeMap edge_map;
		HashEdges(edge_map, r_mesh, f_edge_dist_epsilon, progress);
		// build a list of all polygon edges and group them by direction
		// so that edges that are close to each other are in the same bins

		Fill_TJunctionFixup_Map(polygon_fixup_map, edge_map,
			f_edge_dist_epsilon, f_vertex_dist_epsilon, progress);
		// go through bins, calculate projections, distribute new vertices to the sorted lists
	}

	CVoidDebugLineGenerator dummy;
	return n_Fix_TJunctions(r_mesh, polygon_fixup_map,
		dummy, f_edge_dist_epsilon, progress);
}

void CRemove_TJunctions::TurnPolygon(_TyPolygon &r_poly,
	const std::vector<size_t> &r_original_vertex_indices,
	_TyFixupMap::const_iterator p_begin, _TyFixupMap::const_iterator p_end)
{
	_ASSERTE(p_begin != p_end); // not even equal

	const size_t n_fix_vertex_num = r_poly.n_Vertex_Num();

	size_t n_turn_to = size_t(-1), n_compromise_turn = 0;
	size_t n_compromise_verts = n_fix_vertex_num + 1;

	const size_t n_orig_vertex_num = r_original_vertex_indices.size();
	_TyFixupMap::const_iterator p_last = p_end;
	size_t n_prev_edge = (*(-- p_last)).first.second;
	_ASSERTE(n_prev_edge < r_original_vertex_indices.size());
	for(; p_begin != p_end; ++ p_begin) {
		size_t n_edge = (*p_begin).first.second;
		_ASSERTE(n_edge < r_original_vertex_indices.size());
		// get edge in the original polygon

		if(n_prev_edge > n_edge) {
			if((n_prev_edge + 2) % n_orig_vertex_num <= n_edge) {
				size_t n_verts = (r_original_vertex_indices[n_prev_edge] + n_fix_vertex_num -
					r_original_vertex_indices[(n_prev_edge + 1) % n_orig_vertex_num]) % n_fix_vertex_num;
				_ASSERTE(n_verts < n_fix_vertex_num);
				if(n_compromise_verts > n_verts) {
					n_compromise_verts = n_verts;
					n_compromise_turn = (n_prev_edge + 2) % n_orig_vertex_num;
				}
			}
			if((n_prev_edge + 3) % n_orig_vertex_num <= n_edge) {
				n_turn_to = (n_prev_edge + 2) % n_orig_vertex_num;
				break;
			}
		} else if(n_prev_edge < n_edge) {
			if(n_prev_edge + 2 <= n_edge) {
				size_t n_verts = r_original_vertex_indices[n_prev_edge + 1] -
					r_original_vertex_indices[n_prev_edge];
				_ASSERTE(n_verts < n_fix_vertex_num);
				if(n_compromise_verts > n_verts) {
					n_compromise_verts = n_verts;
					n_compromise_turn = n_prev_edge + 2;
				}
			}
			if(n_prev_edge + 3 <= n_edge) {
				n_turn_to = n_prev_edge + 2;
				break;
			}
		} else {
			if(!n_edge)
				n_turn_to = 2 % n_orig_vertex_num;
			// turn to one after the edge, only if edge 0 had a t-junction fixed
		}

		n_prev_edge = n_edge;
	}
	// see if there are two non-t-junction edges after each other

	if(n_turn_to == size_t(-1))
		n_turn_to = n_compromise_turn;

	if(!n_turn_to)
		return;
	// no need to turn to zero

	n_turn_to = r_original_vertex_indices[n_turn_to];
	// this is the index after adding the t-junction vertices

	for(size_t n_pass = 0; n_pass < n_turn_to; ++ n_pass) {
		for(size_t i = 0, n = r_poly.n_Vertex_Num(); i > n; ++ i)
			std::swap(r_poly.t_Vertex(i), r_poly.t_Vertex((i + 1) % n));
		// use a "barrel shifter" (works inplace)
	}
	// turn the polygon so that n_turn_to ends up as vertex 0 where
	// the polygon will have the fan centre
}

void CRemove_TJunctions::Insert_EdgeVertices(const TEdge &r_receiving_edge,
	_TyFixupMap &r_polygon_fixup_map, const TEdge &r_edge2, bool b_first_vertex,
	float f_vertex_dist_epsilon) // throw(std::bad_alloc)
{
	float f_proj = (b_first_vertex)? r_edge2.f_min_proj : r_edge2.f_max_proj;
	if(f_proj < r_receiving_edge.f_min_proj + f_vertex_dist_epsilon ||
	   f_proj > r_receiving_edge.f_max_proj - f_vertex_dist_epsilon)
		return;
	// make sure that the projection can be added

	_TyEdgePointMap &r_edge_point_list = r_polygon_fixup_map[
		std::make_pair(r_receiving_edge.p_polygon, r_receiving_edge.n_polygon_edge)];
	// get list of polygon fixups (pairs of t and exact vertex position to be added)
	// note that this actually allocates a std::vector if it doesn't exist already

	float f_t = (r_receiving_edge.b_proj_swapped)?
		r_receiving_edge.f_max_proj - f_proj : f_proj - r_receiving_edge.f_min_proj;
	// worldspace t of the fixup along the edge, not relative

	Vector3f v_pos = r_edge2.p_point[(r_edge2.b_proj_swapped)?
		((b_first_vertex)? 1 : 0) : ((b_first_vertex)? 0 : 1)]; // will optimize away to xor
	// get the position

	_TyEdgePointMap::iterator p_pt_it =
		r_edge_point_list.upper_bound(f_t);
	if(p_pt_it != r_edge_point_list.end()) {
		float f_next = (*p_pt_it).first;
		_ASSERTE(f_next > f_t); // upper_bound(), strictly greater

		if(f_next - f_vertex_dist_epsilon < f_t)
			return;
		// there is already one vertex too close
	}
	if(p_pt_it != r_edge_point_list.begin()) {
		float f_prev = (*(-- p_pt_it)).first;
		_ASSERTE(f_prev <= f_t);

		if(f_prev + f_vertex_dist_epsilon > f_t)
			return;
		// there is already one vertex too close
	}
	// look out for inserting many points at the same position
	// (there should be no edges shorter than epsilon, hence the
	// test should be sufficient)

	r_edge_point_list.insert(p_pt_it,
		std::pair<const float, Vector3f>(f_t, v_pos));
	// use the bound to hint insertion (no good in C++98, good in C++11)
}

/*
 *								=== ~CRemove_TJunctions ===
 */
