/*+-------------+-------------------------------------------------------------*\
 *|  |  |_|_|_|_|     Fraunhofer-Institut fuer Graphische Datenverarbeitung   *
 *|__|__|_|_|_|_|         (Fraunhofer Institute for Computer Graphics)        *
 *|  |  |_|_|_|_|                                                             *
 *|__|__|_|_|_|_|     Volker Coors                                            *
 *|  __ |    ___|     Fraunhofer-IGD         e-mail: Volker.Coors@igd.fhg.de  *
 *| /_  /_  / _ |     Rundeturmstr. 6 *
 *|/   / / /__/ |     64283 Darmstadt, Germany                                *
 *+-------------+-------------------------------------------------------------*
 *	ProGIS                                                                *
 *                                 Version 0.1                                *
 *                                 Copyright 2000                             *
 *----------------------------------------------------------------------------*
 *       Author: Volker Coors                                            
 *       $Locker:  $    
 *       $Revision: 1.3 $     
 *       $Log: Feature.java,v $
 *----------------------------------------------------------------------------*/

import java.io.*;
import java.util.Vector;
//import com.sun.utils.geometry.Sphere;   //extends primitive
import java.util.Enumeration;
import java.util.Random;                // added by Anna
import java.lang.Math;                  // added by Anna
import javax.vecmath.*;
//import javax.vecmath.Color3f;
import com.sun.j3d.utils.universe.*;
import com.sun.j3d.utils.behaviors.mouse.*;
import javax.media.j3d.*;
import java.awt.*;

import Display;
import NewTriLoader;


/**
  edgebreaker compression
*/
public class Compression {
    final int C=0;
    final int L=1;
    final int E=2;
    final int R=3;
    final int S=4;
    final int INIT=5;
    
    final Color3f[] CLERSCOLOR = { new Color3f(1f, 0f, 0f),   // C red
	    			   new Color3f(0f, 1f, 0f),   // L green
				   new Color3f(0f, 0f, 1f),   // E blue
				   new Color3f(1f, 1f, 0f),   // R yellow
				   new Color3f(1f, 0f, 1f),   // S magenta
				   new Color3f(0f, 0f, 0f)};  // init black 
    
    final Color3f violet = new Color3f( 0.75f, 0f, 1f );
    final Color3f yellow = new Color3f( 0.75f, 1f, 0f );
				  
    final char[] CLERSSYMBOL = {'C', 'L', 'E', 'R', 'S'};
    
    
    //===============================================================

    /** default constructor */
    public Compression() {
    }

    //===============================================================    
    /**
    *    assume clean mesh :-)
    *    t[3*i], t[3*i+1], t[3*i+2],  bilden Dreieck ccw
    *    Create opposite table _o
    **/
    
    public void setMesh(Point3d[] p, int[] t) 
    {
        // creates opposite table
        // test, damit die cow laeuft...
        // cow model ueberschreibt wahrscheinlich seed dreieck ...???
        // ne, seed ist zu sehen !!!

	_o = new int[t.length];
	_vindex = new int[t.length];

	for (int i=0; i<_o.length; i++) {
	    _o[i]=-3;  // not set yet 
	    _vindex[i]=t[i];
	}
	  
	_clers=new int [t.length/3-1];
	_next_clers=0;
	_tm=new boolean[t.length/3];   //# of triangles
	_vm=new boolean[p.length];     //# of vertices
	_vertices=p;
	_delta=new Vector(p.length);

	for (int i=0; i<_tm.length; i++) {
	    _tm[i]=false;
	}

	for (int i=0; i<_vm.length; i++) {
	    _vm[i]=false;
	}
        
        System.out.println("setMesh init:");
        System.out.println("VertexCount "+p.length);
        System.out.println("VertexIndexCount "+t.length);
        System.out.println("TriangleCount "+t.length/3);
        System.out.println("_o.length= "+_o.length);
        System.out.println("_clers.length= "+_clers.length);
            	
	// build _o
	
	// search opposite of 01
	int o=-1;
	for (int c=0; c<_o.length; c++) {

	    if (_o[c] == -3) {
		o=searchOppositeCorner(c, t);
		if (o>=0) {
		    _o[c]=o;
		    _o[o]=c;
		}else {
		    // darf nicht passieren
		    System.err.println("shared egde not found");
		}
	    } //if
	} //for

	// check
	// assert simple mesh
	// Euler: T+V-E=2
	float euler = t.length/3 + p.length - (float)_o.length/2f;
	System.out.println("Euler: "+euler);	

    } //setmesh
    
    //===============================================================

    protected int searchOppositeCorner (int c, int[] t) {
        int t_no;                   // triangle number
        int nv;                     // next vertex
        int pv;                     //previous vertex
        // search shared edge ab
        int a=v(p(c));
        int b=v(n(c));

	for (int i=c+1; i<t.length; i++ ) {
	    if (t[i] == a) {
	        t_no = i/3;         // ganzzahlige DIV
	        nv=i+1;

	        if (nv/3 > t_no) { // a=t_no+2 -> nv=t_no;
		    nv-=3;    
	        }

	        if (t[nv] == b) {
		    // gemeisame Kante gefunden
		    // opposite vertex is free vertex of triangle
		    pv=nv+1;
		    if (pv/3 > t_no) { // nv=t_no+2 -> pv=t_no;
			pv-=3;    
		    }
		    return pv;
	        }
	    }//if
    
        }// for
	return -1; // opposite corner not found

    }// Search opposite corner
    
    //===============================================================

    public void setTriangleCount(int t) 
    {
    	// set number of triangles in mesh
    	_o=new int[3*t];
    	_vindex=new int[3*t];
	_clers=new int[t-1]; // clers sequence,
	_tm=new boolean[t];

	for (int i=0; i<_tm.length; i++) {
	    _tm[i]=false;
	}//for

    }// setTriangleCount
    
    //===============================================================

    public void setVertices(Point3d[] v) 
    {
	_vertices=v;    
	_vm=new boolean[v.length];
	_delta=new Vector(v.length);
	for (int i=0; i<_vm.length; i++) {
	    _vm[i]=false;
	}
    }
    
    /******************************************************************
    *     C O M P R E S S
    ******************************************************************/
    
    public void initCompression() 
    {
	// init tables for marking visited vertices and triangles

	for (int i=0; i<_tm.length; i++) {
	    _tm[i] = false; // triangle not marked
	}

	for (int i=0; i<_vm.length; i++) {
	    _vm[i] = false; // vertex not marked
	}
	
	int c=1;

	// store first vertex
	writeDelta(new Point3d(g(v(p(c)))));

	// store second vertex (difference vector)
	_ptmp.sub(g(v(c)), g(v(p(c))));

	// don't use predictor 
	writeDelta(new Point3d(_ptmp));

	// store third vertex (difference vector)
	_ptmp.sub(g(v(n(c))), g(v(c))); 

	writeDelta(new Point3d(_ptmp)); 
	markVertex(v(c));
	markVertex(v(n(c)));
	markVertex(v(p(c)));
	markTriangle(t(c));
	changeColor(t(c), CLERSCOLOR[INIT]);

	//System.out.println("Debug: mark vertex:" + v(c));
	//System.out.println("Debug: mark vertex:" + v(n(c)));
	//System.out.println("Debug: mark vertex:" + v(p(c)));

	compress (o(c));

	if (_quant) {
	    double[] x=new double[3*_delta.size()];

	    // distribution of coordinates
	    for (int i=0; i<x.length; i+=3) {
		x[i]=((Point3d)_delta.elementAt(i/3)).x;
		x[i+1]=((Point3d)_delta.elementAt(i/3)).y;
		x[i+2]=((Point3d)_delta.elementAt(i/3)).z;
	    } 
	    quantize(x,12, 0.0001);
	}

	// remove _vertices (not necessary, 
	// just to be sure that they are calculated by decompression
	   
	for (int i=0; i<_vertices.length; i++) {
	    _vertices[i].x=0;
	    _vertices[i].y=0;
	    _vertices[i].z=0;
	}// for
	    
    }// initCompression

    //===============================================================
    int count=0;
    int step=0;
    int stopat=0;
    boolean _changecolor=true;
    
    //===============================================================
    protected void compress(int c) 
    {
	// DEBUG: read steps 
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	String l;
	// end DEBUG

	for (;;) {
	    // DEBUG
	    if (count == stopat) {
		// read new step from user
		try {
		    System.out.println("How many steps to process? ");
		    l=in.readLine();
		    step = (new Integer(l)).intValue();
		}//try
		catch (IOException e) {
		    System.out.println("IOException "+e);
		    step=1;
		}// catch
		stopat+=step;
		System.out.println ("Process next " + step + 
				    "steps. Stop at " + stopat);
		
	    }//if

	    count++;
	    markTriangle(t(c));
	    //drawDirection(c);

	    if (!_vm[v(c)]) {    // tip vertex not visited 

		// parallelogramm prediction and correction
		writeDelta(calcDelta(c)); 

		//writeDelta(g(v(c)));     // coordinate
		writeClers(C);
		markVertex(v(c));
		c=r(c);    // continue with the right neighbour
	    }//if
	    else if ( _tm[t(r(c))]) {   // right triangle visited
		if (_tm[t(l(c))]) {    // left triangle visited
		    writeClers(E); 
		    break;
		}//if
		else {
		    writeClers(R);
		    c=l(c);
		}//else
	    }// else if
	    else if (_tm[t(l(c))]) {    // left triangle visited 
		writeClers(L);
		c=r(c);
	    }// else if

	    else {	   
		writeClers(S);
		compress (r(c));
		c = l(c);
	    }// else
	}// for
		
    }// compress
    
        
    /******************************************************************
    *    Q U A N T I S A T I O N
    ******************************************************************/
    double _a, _b;
    int _B;
    int[] _qx;

    protected void quantize (double[] x, int B, double eps) 
    {
	double a, b; // xi E [a,b]
        // get interval
        a=x[0];
        b=x[0];

        for (int i=1; i<x.length; i++) {
            if (x[i] < a){
                a=x[i];
            }
            else if (x[i] > b) {
                b=x[i];
            }
        }// for

	if (B<=0) {
            // choose B from given Error e
            // eps <= (b-a)/(2^B-1)
            // B >= log2((b-a)/eps +1)
            // ln2(x) = ln(x)/ln(2)
            B=(int) Math.ceil(Math.log((b-a)/eps+1)/Math.log(2));
            System.out.println("given error: "+eps+ " choose B= "+B);
        }//if
        
	// transform
        int[] qx = new int[x.length];
        double l=b-a;
        double s=Math.pow(2, (double) B)-1;
        double test;

        for (int i=0; i<x.length; i++) {
            qx[i]=(int) ((x[i]-a)/l * s);
            test = qx[i]/s*l+a;
            //System.out.println("x: "+x[i]+" qx: "+qx[i]+"rx: "+test);
        }// for
        
        // get interval
        int min=qx[0];
        int max=qx[0];

        for (int i=1; i<qx.length; i++) {
            if (qx[i] < min){
                min=qx[i];
            }
            else if (qx[i] > max) {
                max=qx[i];
            }
        }// for

        System.out.println("qx min="+min+" max="+max);
        System.out.println("Entropy="+entropy(qx, B));

        _a=a;
        _b=b;
        _B=B;
        _qx=qx;

    }//quantize
    

    /******************************************************************
    *    E N T R O P Y
    ******************************************************************/

    /**
    *  calculates entropy of x0,x1,...,xn-1; xE[0, 2^B-1]
    **/
    protected double entropy (int[] x, int B) 
    {
        // count nk: #x=k
        int[] n=new int[(int) Math.pow(2, (double) B)];

        for (int i=0;i<n.length; i++) {
            n[i]=0;
        }

        for (int i=0; i<x.length; i++) {
            n[x[i]]++;
        }

        // 
        // - sum (nk/(n0+n1+...+nk) * log2(nk/(n0+n1+...+nk))
        //           --------------
        //                = sn
        //

        int sn=0;
        double p;
        double sum=0;

        for (int k=0; k<n.length; k++) {
            if (n[k] >0) {
                //System.out.println("Distribution x="+k+" #x="+n[k]);
                sn+=n[k];
                p=(double)n[k]/(double)sn;
                sum += p* Math.log(p)/Math.log(2);
            }
        }// for

        return -sum;        
    }
    

    /******************************************************************
    *                  D E C O M P R E S S
    ******************************************************************/

    public void initDecompression() 
    {
        _vindex[0]=0;
	_vindex[1]=1;
	_vindex[2]=2;

	for (int i=3; i<_vindex.length; i++) {
	    _vindex[i]=-1;      // not set yet
	}
	
	for (int i=0; i<_o.length; i++) {
	    _o[i] = -3;
	}
	
	_o[0]=-1; // start decompression with c=1
	_o[2]=-1;
	_t=0;
	_n=2;

	decompressConnectivity(1);
	
	// progressive geometry refinement
	// simuliert durch #bits, die zum rekonstruieren von 
	// _delta verwendet werden 
	
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	for (int bits=1; bits<=_B; bits++) {
            try {
		System.out.println( "Used geometry bits: " + bits + 
				    ". Hit any key to continue");
		in.readLine();
	    }
	    catch (IOException e) {
		System.out.println( "IOException " + e );
	    }// catch

	    _t=0;
	    _n=2;
	    restoreDelta(_qx, _a, _b, _B, bits);

	    // write vertices
	    Point3d p = new Point3d();

	    _vertices[0] = readDelta(0);
	    p.add (readDelta(0), readDelta(1));

	    _vertices[1] = new Point3d(p);
	    p.add (_vertices[1], readDelta(2)); 

	    _vertices[2] = new Point3d(p);

	    for (int i=3; i<_vertices.length; i++) {
		_vertices[i]=null;
	    }

	    decompressGeometry(1);
	    dis.updateMesh(); // draw new mesh
	}// for
	    
    }
    
    //===============================================================

    public int _t;
    public int _n;
    
    protected void decompressConnectivity( int c ) 
    {
        boolean end=false;
	Point3d p = new Point3d();

	// zip and wrap
	for (;;) 
        {	    
	    _t++;
	    //System.out.println("symbol: "+(_t-1)+" "+CLERSSYMBOL[_clers[_t-1]]);
	    _o[c]=3*_t;
	    _o[3*_t]=c;
	    _vindex[3*_t+1]=v(p(c));
	    _vindex[3*_t+2]=v(n(c));
	    c=n(o(c));
	    
	    switch (_clers[_t-1]) {
	      case C: {
		  _o[n(c)] = -1;
		  _vindex[3*_t]=++_n;
		  break;
	      }
	      case L: {
		  _o[n(c)]=-2;
		  zip (n(c));
		  break;
	      }
              case R: {
		  _o[c]=-2;
		  c = n(c);
		  //zip (p(c));
		  break;
	      }
	      case S: {
		  decompressConnectivity (c); c = n(c);
		  break;
	      }
              case E: {
		  _o[c]=-2;
		  _o[n(c)]=-2;
		  zip (n(c));
		  end=true;
		  break;
	      }
	    }// switch

	    if( end )
		break;
	}// for

	//System.out.println("end decompress");
    }// decompressConnectivity
    
    //===============================================================

    protected void zip (int c) 
    {
      int b=n(c);

      while (o(b)>=0) {
	  b=n(o(b));
      }

      if (o(b) != -1) {
	  return;
      }
      
      _o[c]=b;
      _o[b]=c;
      int a = p(c);
      _vindex[p(a)]=v(p(b));

      while (o(a)>0 && b!=a) {
	  a=p(o(a));
	  _vindex[p(a)]=v(p(b));
      }

      c=p(c);

      while (o(c)>=0 && c!=b) {
	  c=p(o(c));
      }

      if (o(c) == -2) {
	  zip(c);
      }
        
    }// zip
    
    //===============================================================

    public void decompressGeometry (int c) 
    {
        boolean end=false;
	Point3d p = new Point3d();
    	
	for (;;) 
        {
	    _t++;
    	    c=n(o(c));

	    switch (_clers[_t-1]) {
	        case C: {
		    // kein predictor
		    _n++;
		    _vertices[_n]=getCoordinate(c);
		    break;
	        }
	        case L: {
		    break;
	        }
	        case R: {
		    c = n(c);
		    //zip (p(c));
		    break;
	        }
	        case S: {
		    decompressGeometry (c); c = n(c);
		    break;
	        }
	        case E: {
		    end=true;
		    break;
	        }
	    }// switch

	    if (end) break;
	}// for

	//System.out.println("end decompress");
    }//decompressGeometry

    //===============================================================
    
    /**
    *   gesucht ist die Koordinate von c.p.v !!!
    */

    Point3d getCoordinate(int c) {
        return new Point3d(readDelta(_n));
    }

    //===============================================================
    
    /** 
    *    restore _delta from quantized coordinates
    */
    public void restoreDelta(int[] qx, double a, double b, int B) 
    {
        //Point3d[] _delta_decompressed = new Point3d[x.length/3];
        // transform
        double l=b-a;
        double s=Math.pow(2, (double) B)-1;
        double test;
        
        _delta.clear(); // clear Vector
        
	for (int i=0; i<qx.length; i+=3) {
            _delta.addElement( new Point3d(qx[i]/s*l+a, 
					   qx[i+1]/s*l+a, 
					   qx[i+2]/s*l+a));  
        } //for
    }// restoreDelta
    
    //===============================================================

    /** 
     *    restore _delta from quantized coordinates
     */
    protected void restoreDelta( int[] qx, double a, double b, int B, 
				 int bits ) 
    {
        System.out.println("restoreDelta: bits="+bits);
        if (bits>=B || bits <=0) {
            // nothing to refine
            restoreDelta (qx, a, b, B);
            return;
        }// if

        // use only first bits to reconstruct _delta
        // transform

        double l = b-a;
        double s = Math.pow(2, (double) B)-1;
        double test;
        int r = (int) Math.pow(2, (double) B-bits);  
        
        _delta.clear(); // clear Vector

        int x, y, z;
        for (int i=0; i<qx.length; i+=3) {
            // qx DIV 2^(B-bits) -> nur die ersten bits verwenden !
            x=qx[i]/r;  // DIV !!!
            y=qx[i+1]/r;
            z=qx[i+2]/r;
            x=x*r;
            y=y*r;
            z=z*r;
            _delta.addElement(new Point3d(x/s*l+a, y/s*l+a, z/s*l+a));  
        }// for
    }//restoreDelta

    //===============================================================

    /**
    *	triangle is needed for visualization of mesh CLERS sequence
    */
  
    protected void writeClers(int symbol) 
    {	
	if (_changecolor){
	    changeColor(_lastmarkedtriangle, CLERSCOLOR[symbol]);
	}
	
	//System.out.println("clersindex: "+_next_clers);
	if (_next_clers < _clers.length) {
	    _clers[_next_clers++]= symbol;
	}
	else {
	    System.out.println("array out of bounds clersindex: "+_next_clers);
	}
    }// writeClers
    
    //===============================================================

    protected void writeDelta(Point3d p) 
    {
	//System.out.println ("delta: " +p);
	_delta.addElement(p); 
    }

    //===============================================================

    protected Point3d calcDelta (int c) 
    {
        // no predicion, use coordiante
	return new Point3d(g(v(c)));
    }
    
    //===============================================================

    protected int r( int corner ) 
    {
	return o(n(corner));
    }

    //===============================================================
    
    protected int l(int corner) 
    {
	return o(p(corner));
    }

    //===============================================================
    
    /**
    *    corresponding triangle 
    */
    protected int t(int corner) 
    {
    	return corner/3;
    }

    //===============================================================    

    /** 
    *   previous corner
    *   corners oriented counterclockwise
    */
    protected int p(int corner) 
    {
	int previous=0;
	int t = corner/3;       

	previous = corner-3*t;  // p E [0,2]
	previous--;

	if (previous==-1)
	    previous=2;

	// offset wieder drauf
 	previous +=3*t;
	
      	return previous;
    }// previous

    //===============================================================

    /** 
    *   next corner
    *   corners oriented counterclockwise
    */
    protected int n(int corner) 
    {
	int next=0;
	// integer-values: / is same as DIV
 	
	int t=corner/3;
	next = corner-3*t;
	
	// modulo 
	next++;
	
	if (next==3)
	    next=0;
	
	// offset wieder drauf 
	next+=3*t;
	
	//System.out.println("DEBUG: corner "+ corner+" next corner "+next);
	return next;
    }// next

    //===============================================================    

    /**
     * returns the opposite corner
     */
    protected int o(int corner) 
    {
        return _o[corner];
    }

    //===============================================================
    
    /** 
    *    corresponding vertex
    **/
    protected int v(int corner) 
    {
        return _vindex[corner];
    }
    
    //===============================================================    
    
    /**
    *   returns coordinates of vertex
    **/ 
    protected Point3d g(int vertex) {
        return _vertices[vertex];
    }
    
    //===============================================================

    /**
    *    mark vertex as visited
    **/
    protected void markVertex (int vertex) 
    {
        _vm[vertex] = true;
    }

    //===============================================================
    
    protected boolean isVertexMarked(int vertex) 
    {
        return _vm[vertex];
    }
    
    //===============================================================
    
    /**
    *    mark triangle as visited
    **/
    protected void markTriangle (int t) 
    {
        _tm[t] = true;
	_lastmarkedtriangle=t;
    }
    
    //===============================================================

    public void setVertexTable(int[] vt) 
    {
      _vindex=vt;
    }

    //===============================================================
    
    public void setOppositeCornerTable(int[] ct) {
	_o=ct;
    }

    //========================================================================
    // Anna's code goes here
    //========================================================================

    /*
     * Prompts the user with the passed promptStr and converts user's
     * input into double
     * The input should be in the range between 0 and 1.
     * @param promtStr String to prompt the user
     * @return integer value of the string
     * <br>
     */
    private double promptDouble( String promptStr )
    {
	BufferedReader in = new BufferedReader( new 
	                                        InputStreamReader(System.in));
	String sInput = ""; // text input
	double dInput = 1;  // integer value of sInput

	boolean flag = false;

	while( flag == false ){
	    try {
		System.out.println( promptStr );
		sInput = in.readLine();
		dInput = Double.parseDouble( sInput );

		if( (dInput < 0) || (dInput > 1) ){
		    System.out.println( "\nI N V A L I D  input, try again" );
		    continue;
		}
		flag = true;
	    }//try
	    catch (IOException e) {
		System.out.println( e );
	    }// catch
	}//while

	return dInput;
    }// promptDouble

    //========================================================================
    /*
     * Prompts the user with the passed promptStr and converts user's
     * input into integer
     * @param promtStr String to prompt the user
     * @return integer value of the string
     * <br>
     */
    private int promptInteger( String promptStr )
    {
	BufferedReader in = new BufferedReader( new 
	                                        InputStreamReader(System.in));
	String sInput;  // text input
	int iInput;     // integer value of sInput

	try {
	    System.out.println( promptStr );
	    sInput = in.readLine();
	    iInput = Integer.parseInt( sInput );
	}//try
	catch (IOException e) {
	    System.out.println("IOException " + e);
	    iInput = -1;
	}// catch

	return iInput;
    }// promptInteger

    //===============================================================

    int _m[] = null;  //this table sets the new vertices to 0, existing to 1
    int numFixed =0;  // number of fixed points in the model (depends on step)

    //===============================================================
    /**
     * creates _m table with user-defined step
     * does NOT change the _vertices table
     */
    private void create_M_table()
    {
	int step = promptInteger( "Please input distance between " +
				  "fixed points (step): " );
	if( step < 0 ){
	    return;
	}

	numFixed = _vertices.length / step + 1;
	_m = new int[ _vertices.length ];

	// init the _m table
	for( int i=0; i<_m.length; i += step ){
	    _m[i]=0;
	}// for init _m

	int random;
	random = promptInteger( "If you'd like a random order type 1, else 0: ");
	if( random == 1 ){
	    int pos;
	    for( int i=0; i<numFixed; i++ ) { 
		pos = get_rand( _vertices.length );
		if( _m[ pos ] == 1 ){  //vertex selected, try again
		    i--;
		} else
		    _m[ pos ]=1;  // save vertex
	    }// for
	}else{
	    // set every stepth triangle to 1
	    for( int i=0; i<_m.length; i += step ) { 
		_m[i]=1;  // save vertex
	    }// for
	}
    }//create_M_table

    //===============================================================

    /**
     * resets the coordinates of nonfixed point to zero if user so desires
     */
    private void init_m_to_zero()
    {
	Point3d zero = new Point3d( 0.0, 0.0, 0.0 );
	
	int prompt = promptInteger( "If you want to reset coordinates of " +
				    "non fixed points to zero, press 1,\n" +
				    " else press 0" );
	if( prompt == 1 ){
	    for( int i=0; i<_m.length; i++ ){
		if( _m[i] == 0 )
		    _vertices[i] = zero;
	    }//for
	}//if reset

    }//init_m_to_zero

    //===============================================================

    /**
     * For the given corner, compute the center of gravity from all of
     * the neighbors, and set the _vertices table entry for this corner
     * (coordinates) to the new compluted value.  The updated model is 
     * then displayed.
     */
    private Point3d computeCenterOfGravity( int c )
    {
	Point3d sum = new Point3d( 0.0, 0.0, 0.0 );
	int numNeighbors = 0;   // number of triangles incident on c
	int next;               // dummy looping variable
	int start = n( c );	// a corner of a triangle incident on c (!=c)

	sum.add( sum, _vertices[ v( start ) ] );
	next = p( o( start ) );               //c.n.o.p
	numNeighbors++;
	changeColor( t( start ), violet ); 

	while( next != start ) {
	    changeColor( t( next ), violet ); 
	    sum.add( sum, _vertices[ v( next ) ] );
	    numNeighbors++;
	    next = p( o( next ) );     //next.n.o.p -- reset for next iteration
	}
	
	//compute center of gravity
	if( numNeighbors != 0 ){
	    sum.scale( 1.0/ ((double)numNeighbors) );
	}

	return sum;

    }// computeCeneterOfGravity

    //===============================================================

    /**
     * this method is used instead of one in the library of Point3d,
     * which does not work properly, and sets 2 arrays instead of one.
     */
    private Point3d add( Point3d a, Point3d b )
    {
	return (new Point3d( a.x + b.x, a.y + b.y, a.z + b.z ));
    }//add


    //===============================================================

    /**
     * this method is used instead of one in the library of Point3d,
     * which does not work properly, and sets 2 arrays instead of one.
     */
    private Point3d sub( Point3d a, Point3d b )
    {
	return (new Point3d( a.x - b.x, a.y - b.y, a.z - b.z ));
    }//add

    //===============================================================

    /**
     * This method is called when selected vertex (defined by corner c) is fixed
     * It lifts the neighbors of the vertex by difference between its position 
     * and the computed sum, then updates the display
     */
    private void lift_neighbors( int c, double thresh, Point3d sum )
    {
	// get the vertex coordinates for corner c
	Point3d lift = new Point3d( g( v( c ) ) );
	int next;                  // dummy looping variable
	int start = n( c );	   // a corner of a triangle incident on c (!=c)

	lift.sub( sum );           // subtract sum from lift
	lift.scale( thresh );      // lift * thresh

	if( _m[v( start )] == 0 ){
	    changeColor( t( start ), yellow ); 
	    set_vert( start,  add( lift, _vertices[ v( start ) ] ));
	}//if
	next = p( o( start ) );    //c.n.o.p

	while( next != start ) {
	    if( _m[v( next )] == 0 ){
		changeColor( t( next ), yellow ); 
		set_vert( next,  add( lift, _vertices[ v( next ) ] ));
	    }//if
	    next = p( o( next ) ); //next.n.o.p -- reset for next iteration
	}//while

    }//lift_neighbors

    //===============================================================

    /**
     * set the _vertices table entry for this corner to the new 
     * compluted value.  The updated model is then displayed.
     */
    private void set_vert( int corner, Point3d value )
    {
	_vertices[ v( corner ) ] = value;
	dis.updateMesh();
    }
    //===============================================================

    /**
     * returns random corner/vertex of the model depending on scale parameter
     */
    public int get_rand( int scale )
    {
	return (( int )java.lang.Math.floor( scale * rand.nextDouble() ));	
    }

    //===============================================================

    /**
     * set the _vertices table entry for this corner to the new 
     * compluted value.  The updated model is then displayed.
     * @param c -- corner id
     * @param thresh - threshold
     * @param sum - average position of the corner's neighbors
     */
    private void set_vert( int c, double thresh, Point3d sum )
    {
	// get the vertex coordinates for corner c
	int ind = v( c );      //vertex index
	Point3d move = new Point3d( g( ind ) ); 
	
	//compute distance for vertex movement
	move.sub( sum );       // pos - sum
	move.scale( thresh );  // move * thresh

	set_vert( c,  sub( _vertices[ ind ], move ));

    }//set_vert

    //===============================================================

    /**
     * This method finds the step from the user, and then shrinks the 
     * model by setting every point in the step to it's value, and 
     * finding the center of gravity to the rest of the points.
     */
    public void shrink()
    {
	int c = 24;   //random corner to shrink
	int repeat = 1;
	int numCorners = _o.length - 1; // used for random num generator
	Point3d sum;  //used for moving the vertices during shrink
	int seePrevious = 0;

	//prompt user to decide if to lift the neighbors when fixed vertex is hit
	int lift = promptInteger( "Please input 1 if you'd like to lift " + 
				  "neighbors of fixed vertices,\n" +
				  "else input 0: ");

	double thresh = promptDouble("Please input decimal threshold [0,1];\n" +
				     "0 will leave model unchanged: ");

	//prompt user for the number of collapses
	repeat = promptInteger( "Please input number of shrinks: " );

	while( repeat > 0 ){
	    for( int i=0; i<repeat; i++){

		c = get_rand( numCorners );
		//System.out.println( "corner: " + c );
		
		int vert = v(c); //identify a vertex that lies upon this corner
		sum = computeCenterOfGravity( c );

		if( _m[vert] == 0 ){
		    set_vert( c, thresh, sum );
		}//if
		else if( lift == 1 ){  //lift the neighbors, update display
		    lift_neighbors( c, thresh, sum );
		}
	    }//for
	    
	    seePrevious = 0;
	    while( true ){
		seePrevious = promptInteger( "If you'd like to see previous " +
					     "model state enter 1, else 0: ");
		if( seePrevious == 1 ){
		    swap_vert_and_previous();
		    dis.updateMesh();
		}else{
		    break;
		}
	    }
	    move_vert_to_previous();
	    repeat = promptInteger( "Please input number of shrinks: " );

	}//while
	System.exit(1);
    }//shrink

    //========================================================================
    // init the copy of prevous state of _vertices[] 

    private void init_vert_prev()
    {
	vert_prev = new Point3d[ _vertices.length ];
	//copy vertices into vert_prev
	move_vert_to_previous();
    }//

    //========================================================================
    /**
     * copy _vertices[] into vert_prev
     */
    private void move_vert_to_previous()
    {
	//copy vertices into vert_prev
	System.arraycopy( _vertices, 0, vert_prev, 0, _vertices.length );
    }//

    //========================================================================
    /**
     * copy _vertices[] into vert_prev
     */
    private void swap_vert_and_previous()
    {
	Point3d[] temp = new Point3d[ _vertices.length ];

	System.arraycopy( vert_prev, 0, temp, 0, _vertices.length );

	//copy vert_prev into vertices 
	System.arraycopy( _vertices, 0, vert_prev, 0, _vertices.length );
	_vertices = temp;
	System.out.println( "Swapping " );
    }//

    //========================================================================
    // Anna's code ends here
    //========================================================================

    public void changeColor (int t, Color3f c) 
    {
	//System.out.println("paintTriangle "+t + " color "+c);
	Color3f color = new Color3f();
	((GeometryArray)_mesh.getGeometry()).getColor(3*t +1,color);

	if (color.x != 0.75) {
	    System.out.println ("Error: Triangle "+t+ " visited twice");
	    System.out.println ("old Color: "+color);
	    System.out.println ("new Color: "+color);
       	    System.exit(0);
	}

	((GeometryArray)_mesh.getGeometry()).setColor(3*t+2,c);	
	((GeometryArray)_mesh.getGeometry()).setColor(3*t+1,c);
	((GeometryArray)_mesh.getGeometry()).setColor(3*t,c);
    }// changeColor

    //===============================================================
    
    /**
    *  draw direction in mesh
    *  draw line crossing edge to tip
    */
    public void drawDirection (int c) 
    {
        // start: crossing edge, middle 
        Point3d a = new Point3d();
        a.add(g(v(n(c))), g(v(p(c))));
        a.scale(0.5);
        
	// end point in direction of tip
        Point3d b = new Point3d();
        b.add(g(v(c)), a);
        b.scale(0.5);
        
	// draw line (update line array)
        // t-1 directions !
        try {
            ((GeometryArray)_directions.getGeometry()).setCoordinate(2*t(c)-2,a);
            ((GeometryArray)_directions.getGeometry()).setCoordinate(2*t(c)-1,b);
        }
        catch (ArrayIndexOutOfBoundsException e) {
	    System.out.println ("Exception "+e);
            System.out.println ("corner: " + c + ", Index: " + 
				(2*t(c)-2) + " and " + (2*t(c)-1));
        }// try
    }// drawDirection

    
    //===============================================================    

    public Vector getDelta() 
    {
    	return _delta;
    }
    
    //===============================================================

    public void printDelta() 
    {
        for (int i=0; i<_delta.size(); i++) {
            System.out.println("delta["+i+"] "+readDelta(i));
        }
    }

    //===============================================================    

    public Point3d readDelta(int index) 
    {
        return (Point3d) _delta.elementAt(index);
    }
    
    //===============================================================
    
    public int[] getClers() 
    {
    	return _clers;
    }
    
    //===============================================================
    
    public String clersToString() {
        String s = new String();
        
	for (int i=0; i<_clers.length; i++) {	
	    s+=CLERSSYMBOL[_clers[i]];
	}
	return s;
    }// clersToString

    //===============================================================
    //                D E C L A R A T I O N S
    //===============================================================

    Point3d[] _vertices = null;  // vertex table (V)
    Point3d[] vert_prev = null;  // copy of the previous state ov vertex table
    
    Point3d _ptmp = new Point3d();
    int _o[] = null;             // opposite table (O)
    int _vindex[] = null;        // triangle table

    boolean[] _vm = null;        // table for marking visited vertices

    /**
     *  table for marking visited triangles
     */
    boolean[] _tm=null;
    
    /**
    *	CLERS sequence
    */
    int[] _clers=null;
    int _next_clers=0;
    
    /**
     *	point sequence
     */
    Vector _delta=null;
    
    Shape3D _mesh=null;
    Shape3D _directions = null;
    int _lastmarkedtriangle;
    boolean _quant = true;

    static Random rand;          // random number generator -- requires seed
    static Display dis; 
    
    //===============================================================    
    /**
     * Main method
     */
    public static void main(String argv[]) 
    {
	int[] t;  // triangle table
	Point3d[] p; // = new Point3d[4];
	rand = new Random();  	//seed random number generator		

	Compression c = new Compression();
	
	// try tetrahedron
	//c.setMesh(p, t);
	
	// try cow
	NewTriLoader l = new NewTriLoader();
	l.setFile("..\\3dmodels\\cow.tri");
	//      l.setFile("D:\\anna\\master\\cs8803e-jarek\\volker\\cow.tri");
	l.parse();

	p=l.getVertices();
	t=l.getConnectivity();
	
	c.setMesh(p,t);
	System.out.println( "Points: " + p.length + 
			    " Triangles: " + t.length/3);

	c.create_M_table();  // length = num vertices
	c.init_m_to_zero();  // sets nonfixed point coordinates to zero
	c.init_vert_prev();  // init the copy of prevous state of _vertices[] 
	dis = new Display( c );
	dis.drawmesh();
	c.shrink();          // shrink the model
    }// main

}// class compression