package com.exh.bevel.algo;

import com.exh.bevel.support.QuadEntry;
import com.exh.bevel.support.QuadList;
import com.exh.bevel.support.RayIntersectsSurface;
import com.exh.bevel.support.Spotlight;
import com.exh.math.RayIntersectsQuad;
import com.exh.math.primitive.Geo;
import com.exh.math.primitive.Point3;
import com.exh.math.primitive.Polygon;
import com.exh.math.primitive.Quad;
import com.exh.math.primitive.Segment;

/* Store a list of slices made to a single quad.  This is the heart of the quad clipping
 * algorithm.  The line of intersection is found and subtraction is handled (see slice()),
 * and the results are converted back to polygons (see results()).
 */
final class QuadClipList {
	private Quad						mQ = null;
	
	private final Polygon				mPoly = new Polygon(),
										mPolyB = new Polygon();
	private final PolygonClipper				mClipper = new PolygonClipper(false);
	
	private final Segment				mBisector = new Segment();
	
	private final RayIntersectsSurface	mRIS = new RayIntersectsSurface();
	
	// When building the results, these are the start and end indexes
	private int							mResS = 0, mResE = 0;
	
	private final Point3				mPt = new Point3();
	private final Segment				mRay = new Segment();
	private final int[]					mF = new int[5];
	private int							mBiIdx = 0;
	
	void start(final Quad q) {
		mQ = q;
		mPoly.rewind();
	}
	
	private void start() {
		mPoly.add(0, mQ.mPt[0].z, 0);
		mPoly.add(0, mQ.mPt[1].z, 0);
		mPoly.add(1, mQ.mPt[2].z, 0);
		mPoly.add(1, mQ.mPt[3].z, 0);
	}

	// Given a quad b, find where it intersects my quad, and
	// add the intersection (if any) to my list.
	void slice(final Quad q, final Spotlight spot) {
		// Find where the edge of each quad intersects the other quad.
		findBisector(mQ, q);
		if (mBiIdx < 2) return;

		double			startP = getPos(mBisector.mPt[0], mQ),
						endP = getPos(mBisector.mPt[1], mQ);
		// If the intersection is just along a line, bail
		if (startP == endP) return;
		// If the slice is not in the same order as the quad, flip
		if (endP < startP) {
			final double	tp = startP;	startP = endP;	endP = tp;
			mBisector.reverse();
		}

		if (mPoly.mSize < 1) start();

		final double	maxZ = Math.max(mQ.mPt[1].z, mQ.mPt[2].z) + Geo.EPS + 1;
	
		// Build a polygon out of the new slice, normalized to
		// my local coords.  Note that the subtracted polygon is
		// essentially flipped on the Y -- that is, it's low values
		// are the z's and its high values are infinite.
		mPolyB.rewind();
		mPolyB.add(startP, mBisector.mPt[0].z, 0);
		mPolyB.add(startP, maxZ, 0);
		mPolyB.add(endP, maxZ, 0);
		mPolyB.add(endP, mBisector.mPt[1].z, 0);
		mClipper.on(mPoly, mPolyB, mPoly);

		if (spot.mActive) spot.pushSegment(mBisector);
	}

	// Shoot rays through all my cases until I find the intersections.
	// Need to be smart about the order in which I do this, so duplicates
	// don't mess the results up.
	private void findBisector(final Quad a, final Quad b) {
		mBiIdx = 0;
		
		find(a.mPt[0], a.mPt[1], b, 0);
		if (find(a.mPt[3], a.mPt[2], b, 1)) return;
		// Cases where only a corner of a juts into b
		if (mF[0] == RayIntersectsQuad.INTERSECT_QUAD) {
			if (find(a.mPt[1], a.mPt[2], b, 4)) return;
		}
		if (mF[1] == RayIntersectsQuad.INTERSECT_QUAD) {
			if (find(a.mPt[2], a.mPt[1], b, 4)) return;
		}
		// Cases where the edges of b intersect a
		if (find(b.mPt[0], b.mPt[1], a, 2)) return;
		if (find(b.mPt[3], b.mPt[2], a, 3)) return;
		// Cases where only a corner of b juts into a
		if (mF[2] == RayIntersectsQuad.INTERSECT_QUAD) {
			if (find(b.mPt[1], b.mPt[2], a, 4)) return;
		}
		if (mF[3] == RayIntersectsQuad.INTERSECT_QUAD) {
			if (find(b.mPt[2], b.mPt[1], a, 4)) return;
		}
	}
	
	// Test the seg against both triangles for the target quad.
	// Return true if I've found my line of intersection.
	private boolean find(	final Point3 seg0, final Point3 seg1, final Quad q,
							final int idx) {
		mRay.mPt[0].set(seg0);
		mRay.mPt[1].set(seg1);
		mF[idx] = mRIS.on(mRay, q, mPt);
		if (mF[idx] < RayIntersectsQuad.INTERSECT_PLANE) mF[idx] = 0;
		if (mF[idx] == RayIntersectsQuad.INTERSECT_QUAD) {
			if (mBiIdx < 2) pushIntersection(mPt);
		}
		return mBiIdx > 1;
	}
	
	private void pushIntersection(final Point3 pt) {
		// Reject overlapping points.  I need distinct ones!
		for (int k=0; k<mBiIdx; k++) {
			if (mBisector.mPt[k].sameAs(pt)) return;
		}
		mBisector.mPt[mBiIdx++].set(pt);
	}

	// Generate results based on my slice list and place them on the out.
	// Pool is a global resource for recycling quad entries.  Note that
	// my original entry is immutable.
	void results(final QuadList out, final QuadList pool) {
		simplify(mPoly);
		
		if (mPoly.mSize < 2 || !findResultIndexes()) {
			out.push(pool.pop(mQ));
			return;
		}
		
		final Point3		a = mQ.mPt[0], d = mQ.mPt[3];
		Point3				prev = mPoly.mPt[mResS];
		mResS++;
		if (mResS >= mPoly.mSize) mResS = 0;
		
		while (mResS != mResE) {
			final Point3	next = mPoly.mPt[mResS];
			// Generate a new quad
			final QuadEntry	qe = pool.pop();
			qe.mQ.mPt[0].set(at(prev.x, getZ(prev.x, a, d)));
			qe.mQ.mPt[1].set(at(prev.x, prev.y));
			qe.mQ.mPt[2].set(at(next.x, next.y));
			qe.mQ.mPt[3].set(at(next.x, getZ(next.x, a, d)));
			out.push(qe);
			
			prev = next;
			mResS++;
			if (mResS >= mPoly.mSize) mResS = 0;
		}
	}

	// The polygon subtraction operation runs with a very high degree
	// of precision, but that means the results can be too much geometry
	// for the display.  Do this by looking at (roughly) the scaled value
	// of a single pixel, then combining pts within range.
	private void simplify(final Polygon p) {
		// To find the scaled pixel, take the largest distance and divide.
		final double		d0 = Geo.dist(mQ.mPt[0].x, mQ.mPt[0].y, mQ.mPt[3].x, mQ.mPt[3].y),
							d1 = Geo.dist(mQ.mPt[1].x, mQ.mPt[1].y, mQ.mPt[2].x, mQ.mPt[2].y);
//		final double		sPix = 1 / Math.max(d0, d1);
		final double		sPix = 0.1;
		final double		minZ = Math.max(mQ.mPt[0].z, mQ.mPt[3].z) + Geo.EPS;
		// Combine everyone within range
/*
System.out.println("SIMPLIFY ON SCALED PIX=" + sPix);
System.out.println("\td0=" + d0 + " " + mQ.mPt[0] + " to " + mQ.mPt[3]);
System.out.println("\td1=" + d1 + " " + mQ.mPt[1] + " to " + mQ.mPt[2]);
System.out.println("BEFORE");
p.print();
*/
		for (int k=1; k<p.mSize; k++) {
			final Point3	prv = p.mPt[k-1],
							nxt = p.mPt[k];
			// If not the endpoints, or one on the bottom line...
//	System.out.println("\t" + k + " prv=" + prv + " nxt="  + nxt);
			if (prv.y > minZ && nxt.y > minZ) {
				if (Math.abs(prv.x-nxt.x) <= sPix) {
//					System.out.println("\t" + k + " simplify " + prv + " " + nxt);
					// Always maintain the edges
					if (prv.x <= 0.5) {
						prv.y = Math.min(prv.y, nxt.y);
						p.remove(k);
						k--;
					} else {
						nxt.y = Math.min(prv.y, nxt.y);
						p.remove(k-1);
						k--;
					}
				}
			}
		}
//System.out.println("AFTER");
//p.print();
	}
	
	// Find the result indexes that will iterate over the polygon
	// as if it's a polyline, ignoring the bottom left and right corners,
	// only looking at the high z values.  Every result polygon will have
	// a (0, minZ) and a (1, minZ) point, so find them. 
	private boolean findResultIndexes() {
		mResS = -1;
		mResE = -1;
		final double		MATCH_TOL = 0.0001;
		double				matchS = 10000, matchE = 10000, match;
		final double		startZ = mQ.mPt[0].z, endZ = mQ.mPt[3].z;
		for (int k=0; k<mPoly.mSize; k++) {
			final Point3	pt = mPoly.mPt[k];
//			System.out.println("pt=" + pt + " matchS=" + resultQ(pt, startZ) + " matchE=" + resultQ(pt, endZ));
			if ((match=resultQ(pt, 0, startZ)) < MATCH_TOL && match < matchS) {
				mResS = k;
				matchS = match;
			} else if ((match=resultQ(pt, 1, endZ)) < MATCH_TOL && match < matchE) {
				mResE = k;
				matchE = match;
			}
		}
		// The value one past the start should be the start of the polyline.
		// If it's not at a pos of 0, something is wrong.
		if (mResS >= 0 && mResE >= 0) {
			mResS++;
			if (mResS >= mPoly.mSize) mResS = 0;
//	if (mPoly.mPt[mResS].x > MATCH_TOL) System.out.println("ERR hheeeere x=" + mPoly.mPt[mResS].x);
//			if (mPoly.mPt[mResS].x > MATCH_TOL) return false;
			// Weird error
			if (mResS == mResE) return false;
			return true;
		}
		return false;
	}
	
	private final static double resultQ(final Point3 pt, final double x, final double y) {
		// Searching for 0, minZ
		return (Math.abs(pt.x-x) + Math.abs(pt.y-y)) / 2;
	}

	private final static double getZ(final double pos, final Point3 a, final Point3 b) {
		return (a.z*(1-pos)) + (b.z*pos);
	}
	
	// Answer the normalized location of pt between the edges of a
	private double getPos(final Point3 pt, final Quad q) {
		final Point3		a = q.mPt[0], b = q.mPt[1], c = q.mPt[2], d = q.mPt[3];
		// Find the points on either edge at my current z.  Assumes
		// a.z is < b.z and d.z < c.z.
		final double		edgeAb = (pt.z - a.z) / (b.z - a.z),
							edgeCd = (pt.z - d.z) / (c.z - d.z);
		final double		abX = (a.x*(1-edgeAb)) + (b.x*edgeAb),
							abY = (a.y*(1-edgeAb)) + (b.y*edgeAb),
							cdX = (d.x*(1-edgeCd)) + (c.x*edgeCd),
							cdY = (d.y*(1-edgeCd)) + (c.y*edgeCd);
		// Find the distance between my point and its closest
		// edge points.
		final double		d0 = Geo.dist(pt.x, pt.y, abX, abY),
							d1 = Geo.dist(cdX, cdY, pt.x, pt.y);
		return d0 / (d0 + d1);
	}
	
	// Given a normalized location, find its x,y
	private Point3 at(final double pos, final double z) {
		final Point3		a = mQ.mPt[0], b = mQ.mPt[1], c = mQ.mPt[2], d = mQ.mPt[3];
		// Find the points on either edge at my current z.  Assumes
		// a.z is < b.z and d.z < c.z.
		final double		edgeAb = (z - a.z) / (b.z - a.z),
							edgeCd = (z - d.z) / (c.z - d.z);
		final double		abX = (a.x*(1-edgeAb)) + (b.x*edgeAb),
							abY = (a.y*(1-edgeAb)) + (b.y*edgeAb),
							cdX = (d.x*(1-edgeCd)) + (c.x*edgeCd),
							cdY = (d.y*(1-edgeCd)) + (c.y*edgeCd);
		mPt.set((abX*(1-pos)) + (cdX*pos), (abY*(1-pos)) + (cdY*pos), z);
		return mPt;
	}

}