import java.awt.*;
class Triangles {
    PointyPoint vertices_[] = null,
        extras_[] = null;
    int faces_[] = null;
    int nv_,nf_,nx_;
    Color colors_[] = null;
    
    Triangles(int N, int NX) {
        vertices_ = new PointyPoint[N];
        faces_ = new int[N];
        colors_ = new Color[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)
            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;
                    colors_[nf_] = sh.color_;
                    ++nf_;
                }
            }       
    }
    static Vector3D tempV_ = new Vector3D();
    void toScreen(Matrix3D perspectiviewport) {
        //System.out.println("toScreen nf "+nf_+" nv "+nv_);
        for(int i = 0; i<nv_; ++i) {
            if(vertices_[i]==null)
                continue;
            if(vertices_[i].pt.z()>0.)
                System.out.println("FAILURE TO CLIP! "+vertices_[i].pt.z());
            //System.out.println("before persp: "+vertices_[i].pt);
            perspectiviewport.transform(vertices_[i].pt,tempV_);
            tempV_.divide(tempV_.w());
            vertices_[i].pt.copy(tempV_); 
            //System.out.println("after persp: "+vertices_[i].pt);
        }
    }
    void render(int array[], int zbuf[], int W, int H) {
        double fix = 1<<12;
        //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]];
            /*
            array[(int)a.pt.y()*W+(int)a.pt.x()] = 
                array[(int)b.pt.y()*W+(int)b.pt.x()] = 
                    array[(int)c.pt.y()*W+(int)c.pt.x()] = MISApplet.pack(0,0,255);
             */
            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),
                top,bot,dy,
                lx,rx,lz,rz,dlx,drx,dlz,drz;
            //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;
                if(bx<cx) {
                    dlx = (bx-ax)/dy;
                    drx = (cx-ax)/dy;
                    dlz = (bz-az)/dy;
                    drz = (cz-az)/dy;
                }
                else {
                    dlx = (cx-ax)/dy;
                    drx = (bx-ax)/dy;
                    dlz = (cz-az)/dy;
                    drz = (bz-az)/dy;
                }
            }
            else {
                top = by;
                bot = ay+1;
                dy = bot-top;
                if(bx<cx) {
                    lx = bx;
                    rx = cx;
                    lz = bz;
                    rz = cz;
                    dlx = (ax-bx)/dy;
                    drx = (ax-cx)/dy;
                    dlz = (az-bz)/dy;
                    drz = (az-cz)/dy;
                }
                else {
                    lx = cx;
                    rx = bx;
                    lz = cz;
                    rz = bz;
                    dlx = (ax-cx)/dy;
                    drx = (ax-bx)/dy;
                    dlz = (az-cz)/dy;
                    drz = (az-bz)/dy;
                }
            }
            if(bot<0 || top >= W)
                continue;
            for(int y = top; y<bot; ++y,
                                    lx += dlx,
                                    rx += drx,
                                    lz += dlz,
                                    rz += drz) {
                if(y<0||y>=H)
                    continue;
                int rofs = y*W,
                    plx = lx>>12, prx = (rx>>12) + 1;
                if(plx==prx)
                    continue;
                int dx = prx-plx,
                    dz = (rz-lz)/dx,
                    x,z;
                if(prx<0 || plx>=W)
                    continue;
                //System.out.println("Something happens.");
                for(x = plx, 
                    z = lz; 
                        x<prx; 
                            ++x,
                            z += dz) {
                    if(x<0||x>=W)
                        continue;
                    if(zbuf[rofs+x]>z)
                        continue;
                    zbuf[rofs+x] = z;
                    if(x<plx+2 || x>prx-3)
                        array[rofs+x] = MISApplet.pack(200,12,12);
                    else
                        array[rofs+x] = MISApplet.pack(54,0,0);                        
                }
            }
        }
    }
    void draw(Graphics g) {
        //System.out.println("nf "+nf_+" nv "+nv_);
        g.setColor(Color.black);//colors_[i]?
        for(int i = 0; i<nf_; ++i) {
            for(int j = 0; j<3; ++j) {
                int k = (j+1)%3,
                    x1 = (int)vertices_[faces_[i*3+j]].pt.x(),
                    y1 = (int)vertices_[faces_[i*3+j]].pt.y(),
                    x2 = (int)vertices_[faces_[i*3+k]].pt.x(),
                    y2 = (int)vertices_[faces_[i*3+k]].pt.y();
                g.drawLine(x1,y1,x2,y2);
                //System.out.println("line " + x1 + "," + y1 + "," + x2 + ","+ y2);
            }
        }
    }
}