import java.awt.*;
class Triangles {
    PointyPoint vertices_[] = null,
        extras_[] = null;
	Shape qualities_[] = null;
    int faces_[] = null;
    int nv_,nf_,nx_;
    
    Triangles(int N, int NX) {
        vertices_ = new PointyPoint[N];
        faces_ = new int[N];
		qualities_ = new Shape[N];
        if(NX>0) {
            extras_ = new PointyPoint[NX];
            for(int i = 0; i<NX; ++i)
                extras_[i] = new PointyPoint();
        }        
        reset();
    }
    Triangles(int N) {
        this(N,0);
    }
    void reset() {
        for(int i=0; i<nv_; ++i)
            vertices_[i] = null;
        nv_ = nf_ = nx_ = 0;
    }
    void addShape(Shape sh) {
        int vofs = nv_;
        for(int i = 0; i<sh.vertices_.length; ++i) {
			qualities_[nv_] = sh;
            vertices_[nv_++] = sh.transformed_[i];
		}
        for(int i = 0; i<sh.faces_.length; ++i)
            if(sh.faces_[i].length==3) {
                for(int j=0; j<3; ++j)
                    faces_[nf_*3+j] = sh.faces_[i][j];
                ++nf_;
            }
            else {
                assert sh.faces_[i].length>3;
                for(int j=1; j<sh.faces_[i].length-1; ++j) {
                    faces_[nf_*3  ] = sh.faces_[i][0]+vofs;
                    faces_[nf_*3+1] = sh.faces_[i][j]+vofs;
                    faces_[nf_*3+2] = sh.faces_[i][j+1]+vofs;
                    ++nf_;
                }
            }       
    }
	
	// hmmph what are three of the stages of rendering doing inside the data structure?
	
    static Vector3D tempV_ = new Vector3D();
    void toScreen(Matrix3D perspectiviewport) {
        //System.out.println("toScreen nf "+nf_+" nv "+nv_);
        for(int i = 0; i<nv_; ++i) {
			PointyPoint v = vertices_[i];
            if(v==null)
                continue;
            if(v.pt.z()>0.)
                System.out.println("FAILURE TO CLIP! "+v.pt.z());
            //System.out.println("before persp: "+v.pt);
            perspectiviewport.transform(v.pt,tempV_);
            tempV_.divide(tempV_.w(),v.pt);
            //System.out.println("after persp("+tempV_.w()+"): "+v.pt);
        }
    }
	
	void hAVEqUALITY() {
		for(int i=0; i<nv_; ++i) 
			if(vertices_[i] !=null && qualities_[i]==null)
				throw new IllegalStateException("lack of quality");
	}
	void colorize(Colorizer zer) {
        for(int i = 0; i<nv_; ++i) {
			PointyPoint v = vertices_[i];
            if(v==null)
                continue;
			Shape qual = qualities_[i];
			if(qual==null) 
				System.out.println("I barf.");
			zer.colorize(v.v,qual,v.v);
		}
	}

    void render(int array[], int zbuf[], int W, int H) {
        double fix = 1<<12,clrmult=fix*255.;
        //System.out.println("render nf "+nf_+" nv "+nv_);
        for(int i=0; i<nf_; ++i) {
            //System.out.println("("+faces_[i*3]+","+faces_[i*3+1]+","+faces_[i*3+2]+") p "+vertices_[faces_[nf_*3]]);
            PointyPoint 
                a = vertices_[faces_[i*3]],
                b = vertices_[faces_[i*3+1]],
                c = vertices_[faces_[i*3+2]];
			// yep this code is ridiculous - basically didn't want to risk any slowness for abstraction
            int ax = (int)(a.pt.x()*fix),
                bx = (int)(b.pt.x()*fix),
                cx = (int)(c.pt.x()*fix),
                ay = (int)a.pt.y(),
                by = (int)b.pt.y(),
                az = (int)(a.pt.z()*fix),
                bz = (int)(b.pt.z()*fix),
                cz = (int)(c.pt.z()*fix),
				ar = (int)(a.v.x()*clrmult),
				ag = (int)(a.v.y()*clrmult),
				ab = (int)(a.v.z()*clrmult),
				br = (int)(b.v.x()*clrmult),
				bg = (int)(b.v.y()*clrmult),
				bb = (int)(b.v.z()*clrmult),
				cr = (int)(c.v.x()*clrmult),
				cg = (int)(c.v.y()*clrmult),
				cb = (int)(c.v.z()*clrmult);
			//System.out.println("colors ("+ar+" "+ag+" "+ab+") ("+br+" "+bg+" "+bb+") ("+cr+" "+cg+" "+cb+")");
			int top,bot,
                lx,rx,dlx,drx,
				lz,rz,dlz,drz,
				lr,rr,dlr,drr,
				lg,rg,dlg,drg,
				lb,rb,dlb,drb;
			{
				int dy,
					ulx,ulz,ulr,ulg,ulb,
					urx,urz,urr,urg,urb,
					llx,llz,llr,llg,llb,
					lrx,lrz,lrr,lrg,lrb;
				if(ay<by) {
					top = ay;
					bot = by+1;
					ulx = urx = ax;
					ulz = urz = az;
					ulr = urr = ar;
					ulg = urg = ag;
					ulb = urb = ab;
					if(bx<cx) {
						llx = bx; llz = bz; llr = br; llg = bg; llb = bb;
						lrx = cx; lrz = cz; lrr = cr; lrg = cg; lrb = cb;
					}
					else {
						llx = cx; llz = cz; llr = cr; llg = cg; llb = cb;
						lrx = bx; lrz = bz; lrr = br; lrg = bg; lrb = bb;
					}
				}
				else {
					top = by;
					bot = ay+1;
					llx = lrx = ax;
					llz = lrz = az;
					llr = lrr = ar;
					llg = lrg = ag;
					llb = lrb = ab;
					if(bx<cx) {
						ulx = bx; ulz = bz; ulr = br; ulg = bg; ulb = bb;
						urx = cx; urz = cz; urr = cr; urg = cg; urb = cb;
					}
					else {
						ulx = cx; ulz = cz; ulr = cr; ulg = cg; ulb = cb;
						urx = bx; urz = bz; urr = br; urg = bg; urb = bb;
					}
				}
				dy = bot-top;
				lx = ulx; lz = ulz; lr = ulr; lg = ulg; lb = ulb;
				rx = urx; rz = urz; rr = urr; rg = urg; rb = urb;
				//System.out.println("dy "+dy+" ulx "+ulx+" urx "+urx+" llx "+llx+" lrx "+lrx+" top "+top+" bot "+bot);
				dlx = (llx-ulx)/dy;
				drx = (lrx-urx)/dy;
				dlz = (llz-ulz)/dy;
				drz = (lrz-urz)/dy;
				dlr = (llr-ulr)/dy;
				drr = (lrr-urr)/dy;
				dlg = (llg-ulg)/dy;
				drg = (lrg-urg)/dy;
				dlb = (llb-ulb)/dy;
				drb = (lrb-urb)/dy;
			}
			/*
            //System.out.println("some zs: "+az+" "+bz+" "+cz+" ");
            if(ay<by) {
                top = ay;
                bot = by+1;
                dy = bot-top;
				
                lx = rx = ax;
                lz = rz = az;
				
				lr = rr = ar;
				lg = rg = ag;
				lb = rb = ab;
				
                if(bx<cx) {
                    dlx = (bx-ax)/dy;
                    drx = (cx-ax)/dy;
                    dlz = (bz-az)/dy;
                    drz = (cz-az)/dy;
					
					dlr = (br-ar)/dy;
					drr = (cr-ar)/dy;
					dlg = (bg-ag)/dy;
					drg = (cg-ag)/dy;
					dlb = (bb-ab)/dy;
					drb = (cb-ab)/dy;
                }
                else {
                    dlx = (cx-ax)/dy;
                    drx = (bx-ax)/dy;
                    dlz = (cz-az)/dy;
                    drz = (bz-az)/dy;
					
					dlr = (cr-ar)/dy;
					drr = (br-ar)/dy;
					dlb = (cb-ab)/dy;
					drb = (bb-ab)/dy;
					dlg = (cg-ag)/dy;
					drg = (bg-ag)/dy;					
                }
            }
            else {
                top = by;
                bot = ay+1;
                dy = bot-top;
                if(bx<cx) {
                    lx = bx;
                    rx = cx;
					dlx = (ax-bx)/dy;
                    drx = (ax-cx)/dy;
                    lz = bz;
                    rz = cz;
                    dlz = (az-bz)/dy;
                    drz = (az-cz)/dy;

                    lr = br;
                    rr = cr;
                    dlr = (ar-br)/dy;
                    drr = (ar-cr)/dy;
                    lg = bg;
                    rg = cg;
                    dlg = (ag-bg)/dy;
                    drg = (ag-cg)/dy;
                    lb = bb;
                    rb = cb;
                    dlb = (ab-bb)/dy;
                    drb = (ab-cb)/dy;
                }
                else {
                    lx = cx;
                    rx = bx;
                    dlx = (ax-cx)/dy;
                    drx = (ax-bx)/dy;
                    lz = cz;
                    rz = bz;
                    dlz = (az-cz)/dy;
                    drz = (az-bz)/dy;

                    lr = cr;
                    rr = br;
                    dlr = (ar-cr)/dy;
                    drr = (ar-br)/dy;
                    lg = cg;
                    rg = bg;
                    dlg = (ag-cg)/dy;
                    drg = (ag-bg)/dy;
                    lb = cb;
                    rb = bb;
                    dlb = (ab-cb)/dy;
                    drb = (ab-bb)/dy;
                }
            }
			*/
            if(bot<0 || top >= W)
                continue;
            for(int y = top; y<bot; ++y,
                                    lx += dlx,
                                    rx += drx,
                                    lz += dlz,
                                    rz += drz,
									lr += dlr,
									rr += drr,
									lg += dlg,
									rg += drg,
									lb += dlb,
									rb += drb) {
                if(y<0||y>=H)
                    continue;
                int rofs = y*W,
                    plx = lx>>12, 
					prx = (rx>>12) + 2;
                if(plx>=prx) {
					System.out.println("HEY");
                    continue;
				}
                int dx = prx-plx,
                    dz = (rz-lz)/dx,
                    dr = (rr-lr)/dx,
                    dg = (rg-lg)/dx,
                    db = (rb-lb)/dx;
                if(prx<0 || plx>=W)
                    continue;
                //System.out.println("Something happens.");
				if(prx>W)
					prx = W;
				// can move even more out of this loop
                for(int 
					x = plx, 
                    z = lz,
					re = lr,
					gr = lg,
					bl = rb; 
                        x<prx; 
                            ++x,
                            z += dz,
							re += dr,
							gr += dg,
							bl += db) {
                    if(x<0 || z<zbuf[rofs+x])
                        continue;
                    zbuf[rofs+x] = z;
                    array[rofs+x] = 255<<24 | (re>>12)<<16 | (gr>>12)<< 8 | (bl>>12);
				}
            }
        }
    }
}