/*
** Copyright (C) 2005 Antonin Stefanutti <info@alpha-sigma.net>
**  
** 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
/////////////////////////////////////////////////////////////////////////////////////////

class SBuffer {
	//line count
	private var nl:Number;
	//segment count
	private var ns:Number;
	//line array
	private var line:Array;
	//segment array
	private var seg:Array;
	//current segment count in the S-Buffer
	private var n:Number;
	//thickness
	public var t:Number;
	//skip
	public var s:Number;
	//alpha
	public var a:Number;
	
/////////////////////////////////////////////////////////////////////////////////////////
	//constructor
	public function SBuffer() {
		n = 0;
		nl = 0;
		ns = 0;
		setRender(1,1,100);
	}

/////////////////////////////////////////////////////////////////////////////////////////
	//set the line & segment buffers
	public function set(i:Number,j:Number):Void {
		if (seg) delete seg;
		if (line) delete line;
		nl = i;
		ns = j;
		seg = new Array(ns);
		for (var s = 0; s < ns; s++){
			seg[s] = new Segment3D();
		}
		line = new Array(nl);
		for (var l = 0; l < nl; l++){
			line[l] = new Scanline();
		}
	}

/////////////////////////////////////////////////////////////////////////////////////////
	//insert a segment into the S-Buffer
	public function ins(S:Segment3D,y:Number):Void {
		var L:Scanline = line[y];
		var C:Segment3D = L.first;
		var c0:Segment3D;
		var i:Number = 0;
		while(i < L.n){
			//CASE 1 --------------------------------------------------------------------
			if(S.x1 <= C.x0){
				var s0:Segment3D = seg[n++];
				if (C.prev)
					C.prev.next = s0;
				else
					L.first = s0;
				L.n++;
				s0.prev = C.prev;
				s0.next = C;
				s0.x0 = S.x0;
				s0.x1 = S.x1;
				s0.z0 = S.z0;
				s0.dzdx = S.dzdx;
				s0.c = S.c;
				s0.o = S.o;
				C.prev = s0;
				return;
			}
			//CASE 2 --------------------------------------------------------------------
			else if (S.x0 >= C.x1){
				c0 = C;
				C = C.next;
				i++;
				continue;
			}
			//CASE 3 --------------------------------------------------------------------
			else if ((S.x1 > C.x0) && (S.x1 < C.x1) && (S.x0 < C.x0)){
				var x:Number = (S.dzdx == C.dzdx)? -1 : (S.z0 - C.z0) / (C.dzdx - S.dzdx);
				if ((x > C.x0) && (x < S.x1)){
					//if ((C.z0 - 0x1000*C.dzdx) < (S.z0 - 0x1000*S.dzdx)){
					if ((C.z0 - 0x1000*C.dzdx) > (S.z0 - 0x1000*S.dzdx)){
						var s0:Segment3D = seg[n++];
						if (C.prev)
							C.prev.next = s0;
						else
							L.first = s0;
						L.n++;
						s0.prev = C.prev;
						s0.next = C;
						s0.x0 = S.x0;
						s0.x1 = x;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						C.prev = s0;
						C.x0 = x;
						return;
					}
					else {
						var s0:Segment3D = seg[n++];
						var s1:Segment3D = seg[n++];
						var s2:Segment3D = seg[n++];
						if (C.prev)
							C.prev.next = s0;
						else
							L.first = s0;
						L.n += 3;
						s0.prev = C.prev;
						s0.next = s1;
						s0.x0 = S.x0;
						s0.x1 = C.x0;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						s1.prev = s0;
						s1.next = s2;
						s1.x0 = s0.x1;
						s1.x1 = x;
						s1.z0 = C.z0;
						s1.dzdx = C.dzdx;
						s1.c = C.c;
						s1.o = C.o;
						s2.prev = s1;
						s2.next = C;
						s2.x0 = x;
						s2.x1 = S.x1;
						s2.z0 = S.z0;
						s2.dzdx = S.dzdx;
						s2.c = S.c;
						s2.o = S.o;
						C.x0 = s2.x1;
						C.prev = s2;
						return;
					}
				}
				else {
					var s0:Segment3D = seg[n++];
					if (C.prev)
						C.prev.next = s0;
					else
						L.first = s0;
					L.n++;
					s0.prev = C.prev;
					s0.next = C;
					C.prev = s0;
					s0.x0 = S.x0;
					var mx:Number = (C.x0 + S.x1)/2;
					//if ((C.z0 + mx*C.dzdx) < (S.z0 + mx*S.dzdx)){
					if ((C.z0 + mx*C.dzdx) > (S.z0 + mx*S.dzdx)){
						s0.x1 = C.x0 = S.x1;
					}
					else {
						s0.x1 = C.x0;
					}
					s0.z0 = S.z0;
					s0.dzdx = S.dzdx;
					s0.c = S.c;
					s0.o = S.o;
					return;
				}
			}
			//CASE 4 --------------------------------------------------------------------
			else if ((S.x0 > C.x0) && (S.x0 < C.x1) && (S.x1 > C.x1)){
				var x:Number = (S.dzdx == C.dzdx)? -1 : (S.z0 - C.z0) / (C.dzdx - S.dzdx);
				if ((x > S.x0) && (x < C.x1)){
					//if ((C.z0 - 0x1000*C.dzdx) < (S.z0 - 0x1000*S.dzdx)){
					if ((C.z0 - 0x1000*C.dzdx) > (S.z0 - 0x1000*S.dzdx)){
						var s0:Segment3D = seg[n++];
						var s1:Segment3D = seg[n++];
						L.n += 2;
						s0.prev = C;
						s0.next = s1;
						s0.x0 = S.x0;
						s0.x1 = x;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						s1.prev = s0;
						s1.next = C.next;
						if (s1.next) s1.next.prev = s1;
						s1.x0 = x;
						s1.x1 = C.x1;
						s1.z0 = C.z0;
						s1.dzdx = C.dzdx;
						s1.c = C.c;
						s1.o = C.o;
						S.x0 = C.x1;
						C.next = s0;
						C.x1 = s0.x0;
						c0 = s1;
						C = s1.next;
						i += 3;
						continue;
					}
					else {
						S.x0 = C.x1 = x;
						c0 = C;
						C = C.next;
						i++;
						continue;
					}
				}
				else {
					var mx:Number = (S.x0 + C.x1)/2;
					//if ((C.z0 + mx*C.dzdx) < (S.z0 + mx*S.dzdx)){
					if ((C.z0 + mx*C.dzdx) > (S.z0 + mx*S.dzdx)){
						C.x1 = S.x0;
					}
					else {
						S.x0 = C.x1;
					}
					c0 = C;
					C = C.next;
					i++;
					continue;
				}
			}
			//CASE 5 --------------------------------------------------------------------
			else if ((S.x0 > C.x0) && (S.x1 < C.x1)){
				var x:Number = (S.dzdx == C.dzdx)? -1 : (S.z0 - C.z0) / (C.dzdx - S.dzdx);
				if ((x > S.x0) && (x < S.x1)){
					//if ((C.z0 - 0x1000*C.dzdx) < (S.z0 - 0x1000*S.dzdx)){
					var s0:Segment3D = seg[n++];
					var s1:Segment3D = seg[n++];
					L.n += 2;
					s0.prev = C;
					s0.next = s1;
					s1.x1 = C.x1;
					if ((C.z0 - 0x1000*C.dzdx) > (S.z0 - 0x1000*S.dzdx)){
						C.x1 = s0.x0 = S.x0;
						s1.x0 = s0.x1 = x;
					}
					else {
						C.x1 = s0.x0 = x;
						s1.x0 = s0.x1 = S.x1;
					}
					s0.z0 = S.z0;
					s0.dzdx = S.dzdx;
					s0.c = S.c;
					s0.o = S.o;
					s1.prev = s0;
					s1.next = C.next;
					if (s1.next) s1.next.prev = s1;
					s1.z0 = C.z0;
					s1.dzdx = C.dzdx;
					s1.c = C.c;
					s1.o = C.o;
					C.next = s0;
					return;
				}
				else {
					var mx:Number = (S.x0 + S.x1)/2;
					//if ((C.z0 + S.x0*C.dzdx) < (S.z0 + S.x0*S.dzdx)){
					if ((C.z0 + mx*C.dzdx) > (S.z0 + mx*S.dzdx)){
						var s0:Segment3D = seg[n++];
						var s1:Segment3D = seg[n++];
						L.n += 2;
						s0.prev = C;
						s0.next = s1;
						s0.x0 = S.x0;
						s0.x1 = S.x1;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						s1.prev = s0;
						s1.next = C.next;
						if (s1.next) s1.next.prev = s1;
						s1.x0 = s0.x1;
						s1.x1 = C.x1;
						s1.z0 = C.z0;
						s1.dzdx = C.dzdx;
						s1.c = C.c;
						s1.o = C.o;
						C.next = s0;
						C.x1 = s0.x0;
						return;
					}
					return;
				}
			}
			//CASE 6 --------------------------------------------------------------------
			else if ((S.x0 < C.x0) && (S.x1 > C.x1)){
				var x:Number = (S.dzdx == C.dzdx)? -1 : (S.z0 - C.z0) / (C.dzdx - S.dzdx);
				if ((x > C.x0) && (x < C.x1)){
					var s0:Segment3D = seg[n++];
					if (C.prev){
						C.prev.next = s0;
					}
					else{
						L.first = s0;
					}
					L.n++;
					s0.prev = C.prev;
					s0.next = C;
					s0.x0 = S.x0;
					//if ((C.z0 - 0x1000*C.dzdx) < (S.z0 - 0x1000*S.dzdx)){
					if ((C.z0 - 0x1000*C.dzdx) > (S.z0 - 0x1000*S.dzdx)){
						C.x0 = s0.x1 = x;
						S.x0 = C.x1;
					}
					else {
						s0.x1 = C.x0;
						S.x0 = C.x1 = x;
					}
					s0.z0 = S.z0;
					s0.dzdx = S.dzdx;
					s0.c = S.c;
					s0.o = S.o;
					C.prev = s0;
					c0 = C;
					C = C.next;
					i += 2;
					continue;
				}
				else {
					var mx:Number = (C.x0 + C.x1)/2;
					//if ((C.z0 + C.x0*C.dzdx) < (S.z0 + C.x0*S.dzdx)){
					if ((C.z0 + mx*C.dzdx) > (S.z0 + mx*S.dzdx)){
						if (C.prev){
							C.prev.next = C.next;
							c0 = C.next.prev = C.prev;
						}
						else {
							L.first = C.next;
							C.next.prev = null;
						}
						L.n--;
						C = C.next;
						continue;
					}
					else {
						var s0:Segment3D = seg[n++];
						if (C.prev)
							C.prev.next = s0;
						else
							L.first = s0;
						L.n++;
						s0.prev = C.prev;
						s0.next = C;
						s0.x0 = S.x0;
						s0.x1 = C.x0;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						S.x0 = C.x1;
						C.prev = s0;
						c0 = C;
						C = C.next;
						i += 2;
						continue;
					}
				}
			}
			//CASE 7a --------------------------------------------------------------------
			else if ((S.x0 == C.x0) && (S.x1 < C.x1)){
				var x:Number = (S.dzdx == C.dzdx)? -1 : (S.z0 - C.z0) / (C.dzdx - S.dzdx);
				if ((x > S.x0) && (x < S.x1)){
					//if ((C.z0 - 0x1000*C.dzdx) < (S.z0 - 0x1000*S.dzdx)){
					if ((C.z0 - 0x1000*C.dzdx) > (S.z0 - 0x1000*S.dzdx)){
						var s0:Segment3D = seg[n++];
						if (C.prev)
							C.prev.next = s0;
						else
							L.first = s0;
						L.n++;
						s0.prev = C.prev;
						s0.next = C;
						s0.x0 = S.x0;
						s0.x1 = x;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						C.prev = s0;
						C.x0 = x;
						return;
					}
					else {
						var s0:Segment3D = seg[n++];
						var s1:Segment3D = seg[n++];
						L.n += 2;
						s0.prev = C;
						s0.next = s1;
						s0.x0 = x;
						s0.x1 = S.x1;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						s1.prev = s0;
						s1.next = C.next;
						if (s1.next) s1.next.prev = s1;
						s1.x0 = s0.x1;
						s1.x1 = C.x1;
						s1.z0 = C.z0;
						s1.dzdx = C.dzdx;
						s1.c = C.c;
						s1.o = C.o;
						C.next = s0;
						C.x1 = x;
						return;
					}
				}
				else {
					var mx:Number = (S.x0 + S.x1)/2;
					//if ((C.z0 + S.x0*C.dzdx) < (S.z0 + S.x0*S.dzdx)){
					if ((C.z0 + mx*C.dzdx) > (S.z0 + mx*S.dzdx)){
						var s0:Segment3D = seg[n++];
						if (C.prev)
							C.prev.next = s0;
						else
							L.first = s0;
						L.n++;
						s0.prev = C.prev;
						s0.next = C;
						s0.x0 = S.x0;
						s0.x1 = S.x1;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						C.prev = s0;
						C.x0 = s0.x1;
						return;
					}
					return;
				}
			}
			//CASE 7b --------------------------------------------------------------------
			else if ((S.x0 == C.x0) && (S.x1 > C.x1)){
				var x:Number = (S.dzdx == C.dzdx)? -1 : (S.z0 - C.z0) / (C.dzdx - S.dzdx);
				if ((x > C.x0) && (x < C.x1)){
					//if ((C.z0 - 0x1000*C.dzdx) < (S.z0 - 0x1000*S.dzdx)){
					if ((C.z0 - 0x1000*C.dzdx) > (S.z0 - 0x1000*S.dzdx)){
						var s0:Segment3D = seg[n++];
						if (C.prev)
							C.prev.next = s0;
						else
							L.first = s0;
						L.n++;
						s0.prev = C.prev;
						s0.next = C;
						s0.x0 = S.x0;
						s0.x1 = x;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						C.x0 = x;
						S.x0 = C.x1;
						C.prev = s0;
						c0 = C;
						C = C.next;
						i += 2;
						continue;
					}
					else {
						S.x0 = C.x1 = x;
						c0 = C;
						C = C.next;
						i++;
						continue;
					}
				}
				else {
					var mx:Number = (C.x0 + C.x1)/2;
					//if ((C.z0 + C.x0*C.dzdx) < (S.z0 + C.x0*S.dzdx)){
					if ((C.z0 + mx*C.dzdx) > (S.z0 + mx*S.dzdx)){
						if (C.prev){
							C.prev.next = C.next;
							c0 = C.next.prev = C.prev;
						}
						else {
							L.first = C.next;
							C.next.prev = null;
						}
						L.n--;
						C = C.next;
						continue;
					}
					else {
						S.x0 = C.x1;
						c0 = C;
						C = C.next;
						i++;
						continue;
					}
				}
			}
			//CASE 8a --------------------------------------------------------------------
			else if ((S.x0 > C.x0) && (S.x1 == C.x1)){
				var x:Number = (S.dzdx == C.dzdx)? -1 : (S.z0 - C.z0) / (C.dzdx - S.dzdx);
				if ((x > S.x0) && (x < S.x1)){
					//if ((C.z0 - 0x1000*C.dzdx) < (S.z0 - 0x1000*S.dzdx)){
					if ((C.z0 - 0x1000*C.dzdx) > (S.z0 - 0x1000*S.dzdx)){
						var s0:Segment3D = seg[n++];
						var s1:Segment3D = seg[n++];
						L.n += 2;
						s0.prev = C;
						s0.next = s1;
						s0.x0 = S.x0;
						s0.x1 = x;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						s1.prev = s0;
						s1.next = C.next;
						if (s1.next) s1.next.prev = s1;
						s1.x0 = x;
						s1.x1 = C.x1;
						s1.z0 = C.z0;
						s1.dzdx = C.dzdx;
						s1.c = C.c;
						s1.o = C.o;
						C.next = s0;
						C.x1 = s0.x0;
						return;
					}
					else {
						var s0:Segment3D = seg[n++];
						L.n++;
						s0.prev = C;
						s0.next = C.next;
						if (s0.next) s0.next.prev = s0;
						s0.x0 = x;
						s0.x1 = S.x1;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						C.next = s0;
						C.x1 = x;
						return;
					}
				}
				else {
					var mx:Number = (S.x0 + S.x1)/2;
					//if ((C.z0 + S.x0*C.dzdx) < (S.z0 + S.x0*S.dzdx)){
					if ((C.z0 + mx*C.dzdx) > (S.z0 + mx*S.dzdx)){
						var s0:Segment3D = seg[n++];
						L.n++;
						s0.prev = C;
						s0.next = C.next;
						if (s0.next) s0.next.prev = s0;
						s0.x0 = S.x0;
						s0.x1 = S.x1;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						C.next = s0;
						C.x1 = s0.x0;
						return;
					}
					return;
				}
			}
			//CASE 8b --------------------------------------------------------------------
			else if ((S.x0 < C.x0) && (S.x1 == C.x1)){
				var x:Number = (S.dzdx == C.dzdx)? -1 : (S.z0 - C.z0) / (C.dzdx - S.dzdx);
				if ((x > C.x0) && (x < C.x1)){
					//if ((C.z0 - 0x1000*C.dzdx) < (S.z0 - 0x1000*S.dzdx)){
					if ((C.z0 - 0x1000*C.dzdx) > (S.z0 - 0x1000*S.dzdx)){
						var s0:Segment3D = seg[n++];
						if (C.prev)
							C.prev.next = s0;
						else
							L.first = s0;
						L.n++;
						s0.prev = C.prev;
						s0.next = C;
						s0.x0 = S.x0;
						s0.x1 = x;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						C.prev = s0;
						C.x0 = x;
						return;
					}
					else {
						var s0:Segment3D = seg[n++];
						var s1:Segment3D = seg[n++];
						L.n += 2;
						if (C.prev)
							C.prev.next = s0;
						else
							L.first = s0;
						s0.prev = C.prev;
						s0.next = C;
						s0.x0 = S.x0;
						s0.x1 = C.x0;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						s1.prev = C;
						s1.next = C.next;
						if (s0.next) s1.next.prev = s1;
						s1.x0 = x;
						s1.x1 = S.x1;
						s1.z0 = S.z0;
						s1.dzdx = S.dzdx;
						s1.c = S.c;
						s1.o = S.o;
						C.x1 = x;
						C.prev = s0;
						C.next = s1;
						return;
					}
				}
				else {
					var mx:Number = (C.x0 + C.x1)/2;
					//if ((C.z0 + S.x0*C.dzdx) < (S.z0 + S.x0*S.dzdx)){
					if ((C.z0 + mx*C.dzdx) > (S.z0 + mx*S.dzdx)){
						C.x0 = S.x0;
						//C.x1 = S.x1;
						C.z0 = S.z0;
						C.dzdx = S.dzdx;
						C.c = S.c;
						return;
					}
					else {
						var s0:Segment3D = seg[n++];
						if (C.prev)
							C.prev.next = s0;
						else
							L.first = s0;
						L.n++;
						s0.prev = C.prev;
						s0.next = C;
						s0.x0 = S.x0;
						s0.x1 = C.x0;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						C.prev = s0;
						return;
					}
				}
			}
			//CASE 9 --------------------------------------------------------------------
			else if ((S.x0 == C.x0) && (S.x1 == C.x1)){
				var x:Number = (S.dzdx == C.dzdx)? -1 : (S.z0 - C.z0) / (C.dzdx - S.dzdx);
				if ((x > S.x0) && (x < S.x1)){
					//if ((C.z0 - 0x1000*C.dzdx) < (S.z0 - 0x1000*S.dzdx)){
					if ((C.z0 - 0x1000*C.dzdx) > (S.z0 - 0x1000*S.dzdx)){
						var s0:Segment3D = seg[n++];
						if (C.prev)
							C.prev.next = s0;
						else
							L.first = s0;
						L.n++;
						s0.prev = C.prev;
						s0.next = C;
						s0.x0 = S.x0;
						s0.x1 = x;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						C.prev = s0;
						C.x0 = x;
						return;
					}
					else {
						var s0:Segment3D = seg[n++];
						L.n++;
						s0.prev = C;
						s0.next = C.next;
						if (s0.next) s0.next.prev = s0;
						s0.x0 = x;
						s0.x1 = S.x1;
						s0.z0 = S.z0;
						s0.dzdx = S.dzdx;
						s0.c = S.c;
						s0.o = S.o;
						C.next = s0;
						C.x1 = x;
						return;
					}
				}
				else {
					var mx:Number = (C.x0 + C.x1)/2;
					//if ((C.z0 + mx*C.dzdx) < (S.z0 + mx*S.dzdx)){
					if ((C.z0 + mx*C.dzdx) > (S.z0 + mx*S.dzdx)){
						C.z0 = S.z0;
						C.dzdx = S.dzdx;
						C.c = S.c;
						return;
					}
					return;
				}
			}
			//---------------------------------------------------------------------------
		}
		var s0:Segment3D = seg[n++];
		//if (i){
		if (L.n){
			c0.next = s0;
			s0.prev = c0;
		}
		else {
			L.first = s0;
			s0.prev = null;
		}
		s0.next = null;
		L.n++;
		s0.x0 = S.x0;
		s0.x1 = S.x1;
		s0.z0 = S.z0;
		s0.dzdx = S.dzdx;
		s0.c = S.c;
		s0.o = S.o;
	}

/////////////////////////////////////////////////////////////////////////////////////////

	public function reset():Void {
		n = 0;
		for (var i in line) line[i].n = 0;
	}

/////////////////////////////////////////////////////////////////////////////////////////
	
	public function setRender(t:Number, s:Number, a:Number):Void {
		this.t = t;
		this.s = s;
		this.a = a;
	}
	
/////////////////////////////////////////////////////////////////////////////////////////

	public function render():Void {
		//trace(n);
		var i:Number = 0;
		while(i < nl){
			var l:Number = -1;
			var S:Segment3D = line[i].first;
			while (++l < line[i].n){
				S.o.lineStyle(t,S.c,a);
				S.o.moveTo(S.x0,i);
				S.o.lineTo(S.x1,i);
				S = S.next;
			}
			i += s;
		}
	}

/////////////////////////////////////////////////////////////////////////////////////////

}