/************************************************************************
Yutaka Ohtake 

Simplifier.h
Simplification methods

Copyright (c) 1999-2001 
The University of Aizu. All Rights Reserved.
************************************************************************/

#if !defined(AFX_SIMPLIFIER_H__203780DD_2138_4F20_A705_0545554A8049__INCLUDED_)
#define AFX_SIMPLIFIER_H__203780DD_2138_4F20_A705_0545554A8049__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "MeshData.h"
#include "Node.h"
#include "math.h"

#define EPSILON2 0.000001

class Simplifier  
{
public:
	MeshData* mesh;
	BOOL* tag;
	//Node **ridge_edge, **ravine_edge;
	Node **both_edge;
	Node **ridge_cluster, **ravine_cluster;

public:
	void GralandWithCluster(float rate);
	//BOOL Simplifier::contractEdge(int i1, int i2, float new_vertex[], int &i3, int &i4);
	void Simplifier::Garland(float rate, BOOL mesure_err);
	void halfEdgeCollapse(int until);
	void halfEdgeCollapse(float T, BOOL is_ridge);
	BOOL contractEdge(int i1, int i2, float new_vertex[], int &i3, int &i4);
	void cutMeddleTagEdge();
	void connectNearEdge(float T);
	void deleteSmallCycle(float T);
	void deleteShortFeature(float T);
	void setTagEdgesAngle(float T);
	BOOL DK2(float T, float A);
	BOOL vertexRemoveTagEdge(int index, float T, float A);
	void setTagEdges();
	void setRavineAsTag();
	BOOL vertexRemoveCarefully(int index);
	void setRidgeAsTag();
	void quickSort(int* index, float* w, int start, int end);
	void setMeshData(MeshData* mesh);
	BOOL DK(int iter);
	BOOL edgeCollapse(int index1, int index2);
	BOOL vertexRemove(int index);
	Simplifier();
	virtual ~Simplifier();
	
public:
	void downheap(float *a, int N, int k, int *p, int *q);
	void upheap(float *a, int N, int k, int *p, int *q);
	int checkSmallRavineCycle(int start, int previous, int next, float len, float T);
	int checkSmallRidgeCycle(int start, int previous, int next, float len, float T);

	static inline float SHAPE(float p1[3], float p2[3], float p3[3]){
		double l1 = (p1[0]-p2[0])*(p1[0]-p2[0])+(p1[1]-p2[1])*(p1[1]-p2[1])+(p1[2]-p2[2])*(p1[2]-p2[2]);
		double l2 = (p2[0]-p3[0])*(p2[0]-p3[0])+(p2[1]-p3[1])*(p2[1]-p3[1])+(p2[2]-p3[2])*(p2[2]-p3[2]);
		double l3 = (p3[0]-p1[0])*(p3[0]-p1[0])+(p3[1]-p1[1])*(p3[1]-p1[1])+(p3[2]-p1[2])*(p3[2]-p1[2]);
		double area = MeshData::AREA(p1, p2, p3);
		return (float)(4.0*sqrt(3.0)*area/(l1 + l2 + l3));
	}

	static inline BOOL INVERSE(double B[10], double A[10]){
		double d = DET(A);
		if(fabs(d) < EPSILON2)
			return false;
		B[0] = (A[3]*A[5] - A[4]*A[4])/d;
		B[1] = (A[2]*A[4] - A[1]*A[5])/d;
		B[2] = (A[1]*A[4] - A[2]*A[3])/d;
		B[3] = (A[0]*A[5] - A[2]*A[2])/d;
		B[4] = (A[1]*A[2] - A[0]*A[4])/d;
		B[5] = (A[0]*A[3] - A[1]*A[1])/d;
		return true;
	}

	static inline double DET(double A[10]){
		return A[0]*A[3]*A[5] + 2.0*A[1]*A[4]*A[2] 
			-A[2]*A[2]*A[3] - A[1]*A[1]*A[5] - A[4]*A[4]*A[0];
	}

	static inline void MATRIX(double A[10], double n[3], double d){
		A[0] = n[0]*n[0];
		A[1] = n[0]*n[1];
		A[2] = n[0]*n[2];
		A[3] = n[1]*n[1];
		A[4] = n[1]*n[2];
		A[5] = n[2]*n[2];
		A[6] = d*n[0];
		A[7] = d*n[1];
		A[8] = d*n[2];
		A[9] = d*d;
	}

	static inline void MAT_TIMES(double A[10], double k){
		A[0] *= k;
		A[1] *= k;
		A[2] *= k;
		A[3] *= k;
		A[4] *= k;
		A[5] *= k;
		A[6] *= k;
		A[7] *= k;
		A[8] *= k;
		A[9] *= k;
	}

	static inline void MAT_SUM(double B[6], double A[6]){
		B[0] += A[0];
		B[1] += A[1];
		B[2] += A[2];
		B[3] += A[3];
		B[4] += A[4];
		B[5] += A[5];
		B[6] += A[6];
		B[7] += A[7];
		B[8] += A[8];
		B[9] += A[9];
	}

	static inline void MAT_BY_VEC(double v[3], double A[10], double b[3]){
		v[0] = A[0]*b[0] + A[1]*b[1] + A[2]*b[2];
		v[1] = A[1]*b[0] + A[3]*b[1] + A[4]*b[2];
		v[2] = A[2]*b[0] + A[4]*b[1] + A[5]*b[2];
	}

	static inline void MAT_INIT(double A[10]){
		A[0] = A[1] = A[2] = A[3] = A[4] = A[5] = A[6] = A[7] = A[8] = A[9] = 0;
	}

	static inline void MAT_PLUS(double C[10], double A[10], double B[10]){
		C[0] = A[0] + B[0];
		C[1] = A[1] + B[1];
		C[2] = A[2] + B[2];
		C[3] = A[3] + B[3];
		C[4] = A[4] + B[4];
		C[5] = A[5] + B[5];
		C[6] = A[6] + B[6];
		C[7] = A[7] + B[7];
		C[8] = A[8] + B[8];
		C[9] = A[9] + B[9];
	}

	static inline void MAT_COPY(double A[10], double B[10]){
		A[0] = B[0];
		A[1] = B[1];
		A[2] = B[2];
		A[3] = B[3];
		A[4] = B[4];
		A[5] = B[5];
		A[6] = B[6];
		A[7] = B[7];
		A[8] = B[8];
		A[9] = B[9];
	}

	static inline double Q_ERR(double A[10], double v[3]){
		return v[0]*(A[0]*v[0] + A[1]*v[1] + A[2]*v[2]) +
			   v[1]*(A[1]*v[0] + A[3]*v[1] + A[4]*v[2]) +
			   v[2]*(A[2]*v[0] + A[4]*v[1] + A[5]*v[2]) +
			   2.0*(A[6]*v[0] + A[7]*v[1] + A[8]*v[2]) + 
			   A[9];
	}
};

#endif // !defined(AFX_SIMPLIFIER_H__203780DD_2138_4F20_A705_0545554A8049__INCLUDED_)