/*
 * @(#)ThreeD.java	1.7 98/03/23
 *
 * Copyright (c) 1995-1997 Sun Microsystems, Inc. All Rights Reserved.
 *
 * Sun grants you ("Licensee") a non-exclusive, royalty free, license to use,
 * modify and redistribute this software in source and binary code form,
 * provided that i) this copyright notice and license appear on all copies of
 * the software; and ii) Licensee does not utilize the software in a manner
 * which is disparaging to Sun.
 *
 * This software is provided "AS IS," without a warranty of any kind. ALL
 * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING ANY
 * IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE OR
 * NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN AND ITS LICENSORS SHALL NOT BE
 * LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING
 * OR DISTRIBUTING THE SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR ITS
 * LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT,
 * INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER
 * CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF
 * OR INABILITY TO USE SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGES.
 *
 * This software is not designed or intended for use in on-line control of
 * aircraft, air traffic, aircraft navigation or aircraft communications; or in
 * the design, construction, operation or maintenance of any nuclear
 * facility. Licensee represents and warrants that it will not use or
 * redistribute the Software for such purposes.
 */

/* A set of classes to parse, represent and display 3D wireframe models
   represented in Wavefront .obj format. */

import java.applet.Applet;
import java.awt.Graphics;
import java.awt.Color;
import java.awt.Event;
import java.awt.event.*;
import java.io.*;
import java.net.URL;
// ^^$ begin JWP
import java.util.Vector;
import java.awt.*;
// ^^$ end

class FileFormatException extends Exception {
    public FileFormatException(String s) {
	super(s);
    }
}

// ^^$ begin JPW
class Vertex
{
    int p;
	
    Vertex(int v)
    {
	p = v;
    }
}
// ^^$ end

/** The representation of a 3D model */
class Model3D {
    float vert[];
    int tvert[];
    int nvert, maxvert;
    int con[];
    int ncon, maxcon;
    boolean transformed;
    // ^^$ begin JPW
    boolean wire_frame;
    Vector selected_nodes, faces;
    int mspos[];
    float pr[];
    int tpr[];
    boolean projected;
    // ^^$
    Matrix3D mat;

    float xmin, xmax, ymin, ymax, zmin, zmax;

    Model3D () {
	mat = new Matrix3D ();
	mat.xrot(20);
	mat.yrot(30);
	// ^^$ begin JPW
	selected_nodes = new Vector();
	faces = new Vector();
	mspos = new int[3];
	wire_frame = true;
	pr = new float[6];
	tpr = new int[6];
	// ^^$ end
    }
    /** Create a 3D model by parsing an input stream */
    Model3D (InputStream is) throws IOException, FileFormatException {
	this();
	// ^^$ begin JPW
	init_new_model(is);
    }

    
    void init_new_model(InputStream is) throws IOException, FileFormatException {
	nvert = 0;
	ncon =0;
	selected_nodes.removeAllElements();
	faces.removeAllElements();
	// ^^$ end
	StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(is)));
	st.eolIsSignificant(true);
	st.commentChar('#');
	projected = false;
    scan:
	while (true) {
	    switch (st.nextToken()) {
	    default:
		break scan;
	    case StreamTokenizer.TT_EOL:
		break;
	    case StreamTokenizer.TT_WORD:
		if ("v".equals(st.sval)) {
		    double x = 0, y = 0, z = 0;
		    if (st.nextToken() == StreamTokenizer.TT_NUMBER) {
			x = st.nval;
			if (st.nextToken() == StreamTokenizer.TT_NUMBER) {
			    y = st.nval;
			    if (st.nextToken() == StreamTokenizer.TT_NUMBER)
				z = st.nval;
			}
		    }
		    addVert((float) x, (float) y, (float) z);
		    while (st.ttype != StreamTokenizer.TT_EOL &&
			   st.ttype != StreamTokenizer.TT_EOF)
			st.nextToken();
		    // ^^$ begin JPW
		} else if ("f".equals(st.sval) || "fo".equals(st.sval)) {
		    int start = -1;
		    int prev = -1;
		    int n = -1;
		    Vector face = new Vector();
		    while (true)
			if (st.nextToken() == StreamTokenizer.TT_NUMBER) {
			    n = (int) st.nval;
			    if (prev >= 0)
				add(prev - 1, n - 1);
			    if (start < 0)
				start = n;
			    Vertex v = new Vertex(n);
			    face.addElement(v);		     
			    prev = n;
			} else if (st.ttype == '/')
			    st.nextToken();
			else
			    break;
		    if (start >= 0)
			{
			    add(start - 1, prev - 1);
			    faces.addElement(face);
			}
		    if (st.ttype != StreamTokenizer.TT_EOL)
			break scan;
		} else if ("l".equals(st.sval)) {
		    // ^^$ end
		    int start = -1;
		    int prev = -1;
		    int n = -1;
		    while (true)
			if (st.nextToken() == StreamTokenizer.TT_NUMBER) {
			    n = (int) st.nval;
			    if (prev >= 0)
				add(prev - 1, n - 1);
			    if (start < 0)
				start = n;
			    prev = n;
			} else if (st.ttype == '/')
			    st.nextToken();
			else
			    break;
		    if (start >= 0)
			add(start - 1, prev - 1);
		    if (st.ttype != StreamTokenizer.TT_EOL)
			break scan;
		} else {
		    while (st.nextToken() != StreamTokenizer.TT_EOL
			   && st.ttype != StreamTokenizer.TT_EOF);
		}
	    }
	}
	is.close();
	if (st.ttype != StreamTokenizer.TT_EOF)
	    throw new FileFormatException(st.toString());
    }

    /** Add a vertex to this model */
    int addVert(float x, float y, float z) {
	int i = nvert;
	if (i >= maxvert)
	    if (vert == null) {
		maxvert = 100;
		vert = new float[maxvert * 3];
	    } else {
		maxvert *= 2;
		float nv[] = new float[maxvert * 3];
		System.arraycopy(vert, 0, nv, 0, vert.length);
		vert = nv;
	    }
	i *= 3;
	vert[i] = x;
	vert[i + 1] = y;
	vert[i + 2] = z;
	return nvert++;
    }
    /** Add a line from vertex p1 to vertex p2 */
    void add(int p1, int p2) {
	int i = ncon;
	if (p1 >= nvert || p2 >= nvert)
	    return;
	if (i >= maxcon)
	    if (con == null) {
		maxcon = 100;
		con = new int[maxcon];
	    } else {
		maxcon *= 2;
		int nv[] = new int[maxcon];
		System.arraycopy(con, 0, nv, 0, con.length);
		con = nv;
	    }
	if (p1 > p2) {
	    int t = p1;
	    p1 = p2;
	    p2 = t;
	}
	con[i] = (p1 << 16) | p2;
	ncon = i + 1;
    }
    /** Transform all the points in this model */
    void transform() {
	if (transformed || nvert <= 0)
	    return;
	if (tvert == null || tvert.length < nvert * 3)
	    tvert = new int[nvert*3];
	mat.transform(vert, tvert, nvert);
	transformed = true;
    }

   /* Quick Sort implementation
    */
   private void quickSort(int a[], int left, int right)
   {
      int leftIndex = left;
      int rightIndex = right;
      int partionElement;
      if ( right > left)
      {

         /* Arbitrarily establishing partition element as the midpoint of
          * the array.
          */
         partionElement = a[ ( left + right ) / 2 ];

         // loop through the array until indices cross
         while( leftIndex <= rightIndex )
         {
            /* find the first element that is greater than or equal to 
             * the partionElement starting from the leftIndex.
             */
            while( ( leftIndex < right ) && ( a[leftIndex] < partionElement ) )
               ++leftIndex;

            /* find an element that is smaller than or equal to 
             * the partionElement starting from the rightIndex.
             */
            while( ( rightIndex > left ) && 
                   ( a[rightIndex] > partionElement ) )
               --rightIndex;

            // if the indexes have not crossed, swap
            if( leftIndex <= rightIndex ) 
            {
               swap(a, leftIndex, rightIndex);
               ++leftIndex;
               --rightIndex;
            }
         }

         /* If the right index has not reached the left side of array
          * must now sort the left partition.
          */
         if( left < rightIndex )
            quickSort( a, left, rightIndex );

         /* If the left index has not reached the right side of array
          * must now sort the right partition.
          */
         if( leftIndex < right )
            quickSort( a, leftIndex, right );

      }
   }

   private void swap(int a[], int i, int j)
   {
      int T;
      T = a[i]; 
      a[i] = a[j];
      a[j] = T;
   }


    /** eliminate duplicate lines */
    void compress() {
	int limit = ncon;
	int c[] = con;
	quickSort(con, 0, ncon - 1);
	int d = 0;
	int pp1 = -1;
	for (int i = 0; i < limit; i++) {
	    int p1 = c[i];
	    if (pp1 != p1) {
		c[d] = p1;
		d++;
	    }
	    pp1 = p1;
	}
	ncon = d;
    }

    static Color gr[], bl[];

    /** Paint this model to a graphics context.  It uses the matrix associated
	with this model to map from model space to screen space.
	The next version of the browser should have double buffering,
	which will make this *much* nicer */
    void paint(Graphics g) {
	if (vert == null || nvert <= 0)
	    return;
	transform();
	if (gr == null) {
	    gr = new Color[16];
	    for (int i = 0; i < 16; i++) {
		int grey = (int) (170*(1-Math.pow(i/15.0, 2.3)));
		gr[i] = new Color(grey, grey, grey);
	    }
	}
	// ^^$ begin JPW
	if (bl == null) {
	    bl = new Color[256];
	    for (int i = 0; i < 256; i++) {
		int blue = (int) (170*(1-Math.pow(i/256.0, 2.3)));
		bl[i] = new Color(0, 0, blue);
	    }
	}
	// ^^$ end
	int lg = 0;
	int lim = ncon;
	int c[] = con;
	int v[] = tvert;
	if (lim <= 0 || nvert <= 0)
	    // ^^$ begin JPW
	    {
		g.setColor(Color.red);
		for (int i = 0; i < nvert; ++i)
		    g.fillOval(v[3*i] -3, v[3*i + 1] -3, 6, 6);

		g.setColor(Color.blue);
		for (int i=0; i < selected_nodes.size(); i++)
		    {
			Integer Integernode = (Integer)(selected_nodes.elementAt(i));
			int node = 3 * Integernode.intValue();
			g.fillOval(v[node] -3, v[node + 1] -3, 6, 6);
		    }
		// ^^$ end
		return;
	    // ^^$ begin JPW
	    }

	if (!wire_frame)
	    {
		int max = -1, min = 65000;

		for (int i=0; i < nvert; i++)
		    if ( v[3*i+2] > max )
			max = v[3*i+2];
		    else if ( v[3*i+2] < min )
			min = v[3*i+2];

		for (int i=0; i < faces.size(); i++)
		    {
			Vector face = (Vector)(faces.elementAt(i));
			Polygon polygon_face = new Polygon();
			int blue = 0;

			for (int j=0; j < face.size(); j++)
			    {
				Vertex vt = (Vertex)(face.elementAt(j));
				//System.err.println( "vert = " + vt.p );
				blue += v[3*(vt.p-1)+2];
				polygon_face.addPoint(v[3*(vt.p-1)], v[3*(vt.p-1)+1]);
			    }
			//System.err.println( "max, min = " + max + " " + min );
			blue = (int)(256*((float)max*face.size()-blue)/
				     ((float)(max-min)*face.size()));
			//System.err.println( "blue = " + blue );
			if (blue < 0)
			    blue = 0;
			if (blue > 255)
			    blue = 255;
			g.setColor(bl[blue]);
			g.fillPolygon(polygon_face);
		    }
	    }
	else {
	    boolean showvert[];

	    showvert = new boolean[nvert];
	    for (int i=0; i < nvert; ++i)
		showvert[i] = true;

	    // ^^$ end
	    for (int i = 0; i < lim; i++) {
		int T = c[i];
		int p1 = ((T >> 16) & 0xFFFF) * 3;
		int p2 = (T & 0xFFFF) * 3;
		int grey = v[p1 + 2] + v[p2 + 2];
		// ^^$ begin JPW
		showvert[((T >> 16) & 0xFFFF)] = false;
		showvert[(T & 0xFFFF)] = false;
		grey = 0;
		// ^^$ end
		//if (grey < 0)
		//    grey = 0;
		//if (grey > 15)
		//    grey = 15;
		if (grey != lg) {
		    lg = grey;
		    g.setColor(gr[grey]);
		}
		g.drawLine(v[p1], v[p1 + 1],
			   v[p2], v[p2 + 1]);
	    }
	    // ^^$ begin JPW
	    g.setColor(Color.red);
	    for (int i = 0; i < nvert; ++i)
		if (showvert[i])
		    g.fillOval(v[3*i] -3, v[3*i + 1] -3, 6, 6);
	}

	g.setColor(Color.blue);
	for (int i=0; i < selected_nodes.size(); i++)
	    {
		Integer Integernode = (Integer)(selected_nodes.elementAt(i));
		int node = 3 * Integernode.intValue();
		g.fillOval(v[node] -3, v[node + 1] -3, 6, 6);
	    }

	g.setColor(Color.red);
	if (projected)
	    {
		mat.transform(pr, tpr, 2);
		g.fillOval(tpr[0] -3, tpr[1] -3, 6, 6);
		g.drawLine(tpr[0], tpr[1], tpr[3], tpr[4]);
	    }

	// ^^$ end JPW
    }

    /** Find the bounding box of this model */
    void findBB() {
	if (nvert <= 0)
	    return;
	float v[] = vert;
	float xmin = v[0], xmax = xmin;
	float ymin = v[1], ymax = ymin;
	float zmin = v[2], zmax = zmin;
	for (int i = nvert * 3; (i -= 3) > 0;) {
	    float x = v[i];
	    if (x < xmin)
		xmin = x;
	    if (x > xmax)
		xmax = x;
	    float y = v[i + 1];
	    if (y < ymin)
		ymin = y;
	    if (y > ymax)
		ymax = y;
	    float z = v[i + 2];
	    if (z < zmin)
		zmin = z;
	    if (z > zmax)
		zmax = z;
	}
	this.xmax = xmax;
	this.xmin = xmin;
	this.ymax = ymax;
	this.ymin = ymin;
	this.zmax = zmax;
	this.zmin = zmin;
    }

    // ^^$ begin JPW
    boolean MouseClicked(int x, int y, TextField xpos, TextField ypos, TextField zpos)
    {
	mspos[0] = x;
	mspos[1] = y;
	mspos[2] = 0;
	
	int[] v = tvert;
	int selected = -1;
	for (int i = 0; i < nvert; i++)
	    {
		int vertex = 3 * i;
		if ((Math.abs(v[vertex] - x) < 5) && (Math.abs(v[vertex + 1] - y) < 5))
		    selected = i;
	    }
	
	if (selected > -1)
	    {
		Integer Sel = new Integer(selected);
		if (!selected_nodes.contains(Sel))
		    {
			if (selected_nodes.size() <2)
			    {
				xpos.setText(String.valueOf(v[3*selected]));
				ypos.setText(String.valueOf(v[3*selected+1]));
				zpos.setText(String.valueOf(v[3*selected+2]));
				selected_nodes.addElement(Sel);
			    }
		    }
		else
		    {
			selected_nodes.removeElement(Sel);
		    }
		return true;
	    }
	return false;
    }


    boolean add_vertex()
    {
	int tpt[];
	float pt[] = new float[3];	
	tpt = mspos;
	mat.invtransform(tpt,pt);
	addVert(pt[0],pt[1],pt[2]);

	return true;
    }

    boolean connect_verticies()
    {
	if (selected_nodes.size() == 0 || selected_nodes.size() == 1)
	    return false;
	else if (selected_nodes.size() == 2)
	    {
		int p1 = ((Integer)selected_nodes.elementAt(0)).intValue();
		int p2 = ((Integer)selected_nodes.elementAt(1)).intValue();

		add(p1, p2);
		selected_nodes.removeAllElements();
	    }
	return true;
    }

    boolean modify_vertex(TextField xpos, TextField ypos, TextField zpos)
    {
	if (selected_nodes.size() != 1)
	    return false;
	
	String xstr = xpos.getText();
	String ystr = ypos.getText();
	String zstr = zpos.getText();

	int x = Integer.parseInt(xstr,10);
	int y = Integer.parseInt(ystr,10);
	int z = Integer.parseInt(zstr,10);
	
	int tpt[] = new int[3];
	float pt[] = new float[3];	

	tpt[0] = x;
	tpt[1] = y;
	tpt[2] = z;
	mat.invtransform(tpt,pt);

	int p = ((Integer)selected_nodes.elementAt(0)).intValue();

	vert[3*p]   = pt[0];
	vert[3*p+1] = pt[1];
	vert[3*p+2] = pt[2];
    
	selected_nodes.removeAllElements();

	return true;
    }

    boolean delete_vertex()
    {
	if (selected_nodes.size() == 0)
	    return false;
	else if (selected_nodes.size() == 1)
	    {
		boolean exvert[];
		int lim = ncon;
		int c[] = con;
		int v[] = tvert;

		exvert = new boolean[nvert];
		for (int i=0; i < nvert; ++i)
		    exvert[i] = true;

		for (int i = 0; i < lim; i++) {
		    int T = c[i];

		    exvert[((T >> 16) & 0xFFFF)] = false;
		    exvert[(T & 0xFFFF)] = false;
		}

		int p = ((Integer)selected_nodes.elementAt(0)).intValue();

		if (exvert[p] == true)
		    {
			float nv[] = new float[maxvert * 3];
			if (p>0)
			    System.arraycopy(vert, 0, nv, 0, 3*p);
			if (vert.length-3*(p+1)>0)
			    System.arraycopy(vert, 3*(p+1), nv, 3*p, vert.length-3*(p+1));
			--nvert;
			vert = nv;

			for (int i = 0; i < ncon; i++) {
			    int T = con[i];
			    int p1 = ((T >> 16) & 0xFFFF), p2 = (T & 0xFFFF);
			    
			    if ( p1 > p )
				--p1;
			    if ( p2 > p )
				--p2;
			    if (p1 > p2) {
				int t = p1;
				p1 = p2;
				p2 = t;
			    }
			    con[i] = (p1 << 16) | p2;
			}
			selected_nodes.removeAllElements();
			System.err.println( "vertex deleted: p = " + p + " nvert = " + nvert + "\n");
		    }
	    }
	else if (selected_nodes.size() == 2)
	    {
		int i, tmp;
		int p1 = ((Integer)selected_nodes.elementAt(0)).intValue();
		int p2 = ((Integer)selected_nodes.elementAt(1)).intValue();
		

		if (p1 > p2) {
		    int t = p1;
		    p1 = p2;
		    p2 = t;
		}
		tmp = (p1 << 16) | p2;
		for (i=0; i < ncon && con[i] != tmp; ++i)
		    ;
		if (i < ncon)
		    {
			int nv[] = new int[maxcon];
			System.arraycopy(con, 0, nv, 0, i);
			if (con.length-i-1>0)
			    System.arraycopy(con, i+1, nv, i, con.length-i-1);
			--ncon;
			con = nv;
			selected_nodes.removeAllElements();
		    }
	    }
	return true;
    }


    boolean findnvp()
    {
	if (nvert < 2)
	    return false;

	int lnvert = nvert;
	int lncon = ncon;
	float lvert[] = new float[3*lnvert];
	int lcon[] = new int[lncon];
	float norms[] = new float[3*(lncon*(lncon-1)+1)/2];
	int nnorms;
	int i, j, k, l;


	// make local copies of vert and con
	lvert = vert;
	lcon = con;

	// make norms
	nnorms = 0;
	for (i = 0; i < lncon; ++i)
	    {
		int T1 = lcon[i];
		int p11 = ((T1 >> 16) & 0xFFFF), p12 = (T1 & 0xFFFF);
		float e1[] = new float[3];
		e1[0] = lvert[3*p12] - lvert[3*p11];
		e1[1] = lvert[3*p12+1] - lvert[3*p11+1];
		e1[2] = lvert[3*p12+2] - lvert[3*p11+2];
		float len1 = (float)Math.sqrt(e1[0]*e1[0] + e1[1]*e1[1] +
					      e1[2]*e1[2]);
		for (j = i+1; j < lncon; ++j)
		    {
			int T2 = lcon[j];
			int p21 = ((T2 >> 16) & 0xFFFF), p22 = (T2 & 0xFFFF);
			float e2[] = new float[3];
			e2[0] = lvert[3*p22] - lvert[3*p21];
			e2[1] = lvert[3*p22+1] - lvert[3*p21+1];
			e2[2] = lvert[3*p22+2] - lvert[3*p21+2];
			float len2 = (float)Math.sqrt(e2[0]*e2[0] +
						      e2[1]*e2[1] +
						      e2[2]*e2[2]);

			float len;
			if (len1 < len2)
			    len = len1;
			else
			    len = len2;

			float norm[] = new float[3];
			norm[0] = e1[1]*e2[2] - e1[2]*e2[1];
			norm[1] = e1[2]*e2[0] - e1[0]*e2[2];
			norm[2] = e1[0]*e2[1] - e1[1]*e2[0];
			float length = (float)Math.sqrt(norm[0]*norm[0] +
							norm[1]*norm[1] +
							norm[2]*norm[2]);

			// 4 cases
			// case 1: e1 and e2 are edges with a common vertex
			// case 2: e1 and e2 and parallel
			// case 3: e1 and e2 intersect if lengthened
			// case 4: no intersection and not parallel
			//if ( length > 0.001*len )			
			if ( p11 == p21 || p11 == p22 ||
			     p12 == p21 || p12 == p22 )
			    ;
			else if ( length < 0.001*len )
			    {
				e2[0] = lvert[3*p22] - lvert[3*p11];
				e2[1] = lvert[3*p22+1] - lvert[3*p11+1];
				e2[2] = lvert[3*p22+2] - lvert[3*p11+2];

				norm[0] = e1[1]*e2[2] - e1[2]*e2[1];
				norm[1] = e1[2]*e2[0] - e1[0]*e2[2];
				norm[2] = e1[0]*e2[1] - e1[1]*e2[0];
				length = (float)Math.sqrt(norm[0]*norm[0] +
							  norm[1]*norm[1] +
							  norm[2]*norm[2]);
			    }
			else
			    {
				float dist;
				float diff[] = new float[3];
 
				diff[0] = lvert[3*p22] - lvert[3*p11];
				diff[1] = lvert[3*p22+1] - lvert[3*p11+1];
				diff[2] = lvert[3*p22+2] - lvert[3*p11+2];

				
				dist = (float)Math.abs(norm[0]*diff[0] +
						       norm[1]*diff[1] +
						       norm[2]*diff[2])/length;
				if (dist > 0.001)
				    continue;
			    }

			float invlen = 1.0f/length;
			norm[0] = invlen*norm[0];
			norm[1] = invlen*norm[1];
			norm[2] = invlen*norm[2];
			
			norms[3*nnorms] = norm[0];
			norms[3*nnorms+1] = norm[1];
			norms[3*nnorms+2] = norm[2];
			++nnorms;			    
			//System.err.println( "norm0b = (" + norm[0] +
			//", " + norm[1] + ", "
			//+ norm[2] + ")\n" );
		    }
	    }

	// compress norms
	float tmp[] = new float[3*nnorms];
	float dot;
	boolean keep;
	for ( i = 0, k = 0; i < nnorms; ++i )
	    {
		for (j = i+1, keep = true; j < nnorms; ++j)
		    if (Math.abs(norms[3*i]*norms[3*j] +
				 norms[3*i+1]*norms[3*j+1] +
				 norms[3*i+2]*norms[3*j+2]) > .999)
			keep = false;
		if (keep)
		    {
			tmp[3*k] = norms[3*i];
			tmp[3*k+1] = norms[3*i+1];
			tmp[3*k+2] = norms[3*i+2];
			++k;
		    }
	    }
	norms = tmp;
	nnorms = k;


	for (i = 0; i < nnorms; ++i)
	    System.err.println( "norm2 = (" + norms[3*i] + ", " +
				norms[3*i+1] + ", " + norms[3*i+2] + ")\n" );

	
	float biggest = 0;
	float dotprod;
	float p[] = new float[3];
	for (i = 0; i < nnorms; ++i)
	    for (j = i+1; j < nnorms; ++j)
		{
		    float p1[] = new float[3];
		    p1[0] = norms[3*i] + norms[3*j];
		    p1[1] = norms[3*i+1] + norms[3*j+1];
		    p1[2] = norms[3*i+2] + norms[3*j+2];
		    float p1l = (float)Math.sqrt(p1[0]*p1[0] + p1[1]*p1[1] +
						 p1[2]*p1[2]);
		    p1[0] /= p1l;
		    p1[1] /= p1l;
		    p1[2] /= p1l;

		    float p2[] = new float[3];
		    p2[0] = norms[3*i] - norms[3*j];
		    p2[1] = norms[3*i+1] - norms[3*j+1];
		    p2[2] = norms[3*i+2] - norms[3*j+2];
		    float p2l = (float)Math.sqrt(p2[0]*p2[0] + p2[1]*p2[1] +
						 p2[2]*p2[2]);
		    p2[0] /= p2l;
		    p2[1] /= p2l;
		    p2[2] /= p2l;

		    float p1rad = Math.abs(p1[0]*norms[3*j] +
					   p1[1]*norms[3*j+1] +
					   p1[2]*norms[3*j+2]);
		    float p2rad = Math.abs(p2[0]*norms[3*j] +
					   p2[1]*norms[3*j+1] +
					   p2[2]*norms[3*j+2]);

		    if (p1rad > biggest)
			{
			    boolean good = true;
			    for (k = 0; k < nnorms; ++k)
				if (k == i || k == j)
				    continue;
				else if ( Math.abs(p1[0]*norms[3*k] +
						   p1[1]*norms[3*k+1] +
						   p1[2]*norms[3*k+2]) <=
					  p1rad)
				    good = false;
			    if (good)
				{
				    biggest = p1rad;
				    p = p1;
				}
			}
		    if (p2rad > biggest)
			{
			    boolean good = true;
			    for (k = 0; k < nnorms; ++k)
				if (k == i || k == j)
				    continue;
				else if ( Math.abs(p2[0]*norms[3*k] +
						   p2[1]*norms[3*k+1] +
						   p2[2]*norms[3*k+2]) <=
					  p2rad)
				    good = false;
			    if (good)
				{
				    biggest = p2rad;
				    p = p2;
				}
			}
		}


	for (i = 0; i < nnorms; ++i)
	    for (j = i+1; j < nnorms; ++j)
		for (k = j+1; k < nnorms; ++k)
		    {
			float t1[] = new float[3];
			t1[0] = norms[3*i] - norms[3*j];
			t1[1] = norms[3*i+1] - norms[3*j+1];
			t1[2] = norms[3*i+2] - norms[3*j+2];

			float t2[] = new float[3];
			t2[0] = norms[3*i] - norms[3*k];
			t2[1] = norms[3*i+1] - norms[3*k+1];
			t2[2] = norms[3*i+2] - norms[3*k+2];

			float p1[] = new float[3];
			p1[0] = t1[1]*t2[2] - t1[2]*t2[1];
			p1[1] = t1[2]*t2[0] - t1[0]*t2[2];
			p1[2] = t1[0]*t2[1] - t1[1]*t2[0];
			float p1l = (float)Math.sqrt(p1[0]*p1[0] +
						     p1[1]*p1[1] +
						     p1[2]*p1[2]);
			p1[0] /= p1l;
			p1[1] /= p1l;
			p1[2] /= p1l;

			
			t1[0] = -norms[3*i] - norms[3*j];
			t1[1] = -norms[3*i+1] - norms[3*j+1];
			t1[2] = -norms[3*i+2] - norms[3*j+2];

			t2[0] = -norms[3*i] - norms[3*k];
			t2[1] = -norms[3*i+1] - norms[3*k+1];
			t2[2] = -norms[3*i+2] - norms[3*k+2];

			float p2[] = new float[3];
			p2[0] = t1[1]*t2[2] - t1[2]*t2[1];
			p2[1] = t1[2]*t2[0] - t1[0]*t2[2];
			p2[2] = t1[0]*t2[1] - t1[1]*t2[0];
			float p2l = (float)Math.sqrt(p2[0]*p2[0] +
						     p2[1]*p2[1] +
						     p2[2]*p2[2]);
			p2[0] /= p2l;
			p2[1] /= p2l;
			p2[2] /= p2l;


			t1[0] = norms[3*i] + norms[3*j];
			t1[1] = norms[3*i+1] + norms[3*j+1];
			t1[2] = norms[3*i+2] + norms[3*j+2];

			t2[0] = norms[3*i] - norms[3*k];
			t2[1] = norms[3*i+1] - norms[3*k+1];
			t2[2] = norms[3*i+2] - norms[3*k+2];

			float p3[] = new float[3];
			p3[0] = t1[1]*t2[2] - t1[2]*t2[1];
			p3[1] = t1[2]*t2[0] - t1[0]*t2[2];
			p3[2] = t1[0]*t2[1] - t1[1]*t2[0];
			float p3l = (float)Math.sqrt(p3[0]*p3[0] +
						     p3[1]*p3[1] +
						     p3[2]*p3[2]);
			p3[0] /= p3l;
			p3[1] /= p3l;
			p3[2] /= p3l;


			t1[0] = norms[3*i] - norms[3*j];
			t1[1] = norms[3*i+1] - norms[3*j+1];
			t1[2] = norms[3*i+2] - norms[3*j+2];

			t2[0] = norms[3*i] + norms[3*k];
			t2[1] = norms[3*i+1] + norms[3*k+1];
			t2[2] = norms[3*i+2] + norms[3*k+2];

			float p4[] = new float[3];
			p4[0] = t1[1]*t2[2] - t1[2]*t2[1];
			p4[1] = t1[2]*t2[0] - t1[0]*t2[2];
			p4[2] = t1[0]*t2[1] - t1[1]*t2[0];
			float p4l = (float)Math.sqrt(p4[0]*p4[0] +
						     p4[1]*p4[1] +
						     p4[2]*p4[2]);
			p4[0] /= p4l;
			p4[1] /= p4l;
			p4[2] /= p4l;


			float p1rad = Math.abs(p1[0]*norms[3*k] +
					       p1[1]*norms[3*k+1] +
					       p1[2]*norms[3*k+2]);
			float p2rad = Math.abs(p2[0]*norms[3*k] +
					       p2[1]*norms[3*k+1] +
					       p2[2]*norms[3*k+2]);
			float p3rad = Math.abs(p3[0]*norms[3*k] +
					       p3[1]*norms[3*k+1] +
					       p3[2]*norms[3*k+2]);
			float p4rad = Math.abs(p4[0]*norms[3*k] +
					       p4[1]*norms[3*k+1] +
					       p4[2]*norms[3*k+2]);

			if (p1rad > biggest)
			    {
				boolean good = true;
				for (l = 0; l < nnorms; ++l)
				    if (l == i || l == j || l == k)
					continue;
				    else if ( Math.abs(p1[0]*norms[3*l] +
						       p1[1]*norms[3*l+1] +
						       p1[2]*norms[3*l+2]) <=
					      p1rad)
					good = false;
				if (good)
				    {
					biggest = p1rad;
					p = p1;
				    }
			    }
			if (p2rad > biggest)
			    {
				boolean good = true;
				for (l = 0; l < nnorms; ++l)
				    if (l == i || l == j || l == k)
					continue;
				    else if ( Math.abs(p2[0]*norms[3*l] +
						       p2[1]*norms[3*l+1] +
						       p2[2]*norms[3*l+2]) <=
					      p2rad)
					good = false;
				if (good)
				    {
					biggest = p2rad;
					p = p2;
				    }
			    }
			if (p3rad > biggest)
			    {
				boolean good = true;
				for (l = 0; l < nnorms; ++l)
				    if (l == i || l == j || l == k)
					continue;
				    else if ( Math.abs(p3[0]*norms[3*l] +
						       p3[1]*norms[3*l+1] +
						       p3[2]*norms[3*l+2]) <=
					      p3rad)
					good = false;
				if (good)
				    {
					biggest = p3rad;
					p = p3;
				    }
			    }
			if (p4rad > biggest)
			    {
				boolean good = true;
				for (l = 0; l < nnorms; ++l)
				    if (l == i || l == j || l == k)
					continue;
				    else if ( Math.abs(p4[0]*norms[3*l] +
						       p4[1]*norms[3*l+1] +
						       p4[2]*norms[3*l+2]) <=
					      p4rad)
					good = false;
				if (good)
				    {
					biggest = p4rad;
					p = p4;
				    }
			    }
		    }
	
	pr[0] = 0.0f;
	pr[1] = 0.0f;
	pr[2] = 0.0f;
	pr[3] = p[0];
	pr[4] = p[1];
	pr[5] = p[2];
	projected = true;

	System.err.println( "vert = (" + p[0] + ", " + p[1] + ", " + p[2] + ")\n" );


	return true;
    }
    // ^^$ end
}

/** An applet to put a 3D model into a page */
public class ThreeD extends Applet 
  implements Runnable, MouseListener, MouseMotionListener {
    Model3D md;
    boolean painted = true;
    float xfac;
    int prevx, prevy;
    float xtheta, ytheta;
    float scalefudge = 1;
    Matrix3D amat = new Matrix3D(), tmat = new Matrix3D();
    String mdname = null;
    String message = null;
    // ^^$ begin JPW
    CheckboxGroup frame;
    Checkbox wireframe, filled;
    List models;
    Label instructions, modellabel;
    Button addvert, convert, modvert, delvert, clear, findnvp;
    TextField xpos, ypos, zpos;
    // ^^$ end

    public void init() {
	mdname = getParameter("model");
	try {
	    scalefudge = Float.valueOf(getParameter("scale")).floatValue();
	}catch(Exception e){};
	amat.yrot(20);
	amat.xrot(20);
	if (mdname == null)
	    mdname = "model.obj";
	resize(getSize().width <= 20 ? 400 : getSize().width,
	       getSize().height <= 20 ? 400 : getSize().height);
	addMouseListener(this);
	addMouseMotionListener(this);

	// ^^$ begin JPW
	setLayout(new BorderLayout());

	Panel buttonPanel = new Panel();

	Panel adddeletePanel = new Panel();
	Panel modelPanel = new Panel();
	Panel Eastern = new Panel();

	Panel framePanel = new Panel();
	Panel instructionsPanel = new Panel();
	Panel Southern = new Panel();

	
	buttonPanel.setLayout(new FlowLayout(FlowLayout.CENTER,8,2));
	buttonPanel.setBackground(Color.green);

	adddeletePanel.setLayout(new GridLayout(10,1));
	modelPanel.setLayout(new GridLayout(1,1));
	Eastern.setLayout(new BorderLayout());
	
	framePanel.setLayout(new FlowLayout(FlowLayout.CENTER,8,2));
	//framePanel.setLayout(new GridLayout(2,2));
	framePanel.setBackground(Color.green);
	instructionsPanel.setLayout(new FlowLayout(FlowLayout.CENTER,8,2));
	instructionsPanel.setBackground(Color.green);
	Southern.setLayout(new GridLayout(3,1));

	addNotify();
	resize(400,400);
	
	addvert = new Button("Add");
	addvert.setFont(new Font("Dialog", Font.BOLD, 10));

	convert = new Button("Connect");
	convert.setFont(new Font("Dialog", Font.BOLD, 10));

	modvert = new Button("Modify");
	modvert.setFont(new Font("Dialog", Font.BOLD, 10));

	delvert = new Button("Delete");
	delvert.setFont(new Font("Dialog", Font.BOLD, 10));

	clear = new Button("Clear");
	clear.setFont(new Font("Dialog", Font.BOLD, 10));

	findnvp = new Button("Find NVP");
	findnvp.setFont(new Font("Dialog", Font.BOLD, 10));

	xpos = new TextField();
	ypos = new TextField();
	zpos = new TextField();

	modellabel = new Label("model :");

	models = new List(3,false);
	models.add("tetrahedron");
	models.add("cube");
	models.add("octahedron");
	models.add("dodecahedron");
	models.add("icosahedron");
	models.add("dinosaur");
	models.add("hughes");
	models.add("knoxS");
	models.add("man");
	models.add("buckyball");
	models.setEnabled(true);
	
	frame = new CheckboxGroup();

	wireframe = new Checkbox("Wire Frame", frame, true);	
	wireframe.setFont(new Font("Dialog", Font.BOLD, 12));	

	filled = new Checkbox("Filled Polygon", frame, false);
	filled.setFont(new Font("Dialog", Font.BOLD, 12));

	frame.setSelectedCheckbox(wireframe);
	
	// instructions
	instructions = new Label("Click on Vertices to Select them, Drag on image to rotate");

	//buttonPanel.add(modellabel);
	//buttonPanel.add(models);

	adddeletePanel.add(addvert);
	adddeletePanel.add(convert);
	adddeletePanel.add(modvert);
	adddeletePanel.add(delvert);
	adddeletePanel.add(clear);
	adddeletePanel.add(findnvp);
	adddeletePanel.add(xpos);
	adddeletePanel.add(ypos);
	adddeletePanel.add(zpos);	
	adddeletePanel.add(modellabel);

	modelPanel.add(models);

	framePanel.add(wireframe);
	framePanel.add(filled);
	framePanel.add(instructions);
	
	Eastern.add("North", adddeletePanel);
	Eastern.add("East", modelPanel);
	//Southern.add(framePanel);
	//Southern.add(instructionsPanel);
	//Southern.add(adddeletePanel);
	add("North", buttonPanel);
	add("South", framePanel);
	add("East", Eastern);
	// ^^$ end
    }
    // ^^$ begin JPW
    public boolean action(Event evt, Object arg)
    {
	try
	    {
		if(evt.target instanceof Checkbox)
		    {
			if (((Checkbox)evt.target) ==wireframe) 
			    md.wire_frame = true;
			else if(((Checkbox)evt.target) ==filled)
			    md.wire_frame = false;
			repaint();
		    }
		else if (evt.target instanceof Button)
		    {
			if (((Button)evt.target) ==addvert)
			    {
				if (md.add_vertex())
				    repaint();
			    }
			else if (((Button)evt.target) ==convert)
			    {
				if (md.connect_verticies())
				    repaint();
			    }
			else if (((Button)evt.target) ==modvert)
			    {
				if (md.modify_vertex(xpos,ypos,zpos))
				    repaint();
			    }
			else if (((Button)evt.target) ==delvert)
			    {
				if (md.delete_vertex())
				    repaint();
			    }
			else if (((Button)evt.target) ==clear) 
			    {
				mdname = "models/null.obj";	    
				InputStream is = new URL(getDocumentBase(), mdname).openStream();
				md.init_new_model(is);
				repaint();
			    }
			else if (((Button)evt.target) ==findnvp)
			    {
				if (md.findnvp())
				    repaint();
			    }
			repaint();
		    }
	    }
	catch(Exception e) {
	}
	return true;
    }	


    public boolean handleEvent(Event evt) {
	try {
	    if (evt.target instanceof List)
		{
		    List list = (List)evt.target;
		    int lIndex = ((Integer)evt.arg).intValue();
		    String object = list.getItem(lIndex);
		    
		    if (object == "tetrahedron")
			{
			    mdname = "models/tet.obj";
			}
		    else if (object == "cube")
			{
			    mdname = "models/cube.obj";
			}
		    else if (object == "octahedron")
			{
			    mdname = "models/oct.obj";
			}
		    else if (object == "dodecahedron")
			{
			    mdname = "models/dodec.obj";
			}
		    else if (object == "icosahedron")
			{
			    mdname = "models/icos.obj";
			}
		    else if (object == "dinosaur")
			{
			    mdname = "models/dinosaur.obj";
			}
		    else if (object == "hughes")
			{
			    mdname = "models/hughes_500.obj";
			}
		    else if (object == "knoxS")
			{
			    mdname = "models/knoxS.obj";
			}
		    else if (object == "man")
			{
			    mdname = "models/blobby_man.obj";
			}
		    else if (object == "buckyball")
			{
			    mdname = "models/bucky_c180.obj";
			}		    
		    InputStream is = new URL(getDocumentBase(), mdname).openStream();
		    md.init_new_model(is);
		    md.findBB();
		    md.compress();
		    float xw = md.xmax - md.xmin;
		    float yw = md.ymax - md.ymin;
		    float zw = md.zmax - md.zmin;
		    /*
		    if (yw > xw)
			xw = yw;
		    if (zw > xw)
			xw = zw;
		    float f1 = getSize().width / xw;
		    float f2 = getSize().height / xw;
		    */
		    float f = (float)Math.sqrt(xw*xw+yw*yw+zw*zw);
		    float f1 = getSize().width / f;
		    float f2 = getSize().height / f;
		    xfac = 0.7f * (f1 < f2 ? f1 : f2) * scalefudge;
		    repaint();
		}
	}
	catch(Exception e) {
	}
	return super.handleEvent(evt);
    }
    // ^^$ end

    public void destroy() {
        removeMouseListener(this);
        removeMouseMotionListener(this);
    }

    public void run() {
	InputStream is = null;
	try {
	    Thread.currentThread().setPriority(Thread.MIN_PRIORITY);
	    is = new URL(getDocumentBase(), mdname).openStream();
	    Model3D m = new Model3D (is);
	    md = m;
	    m.findBB();
	    m.compress();
	    float xw = m.xmax - m.xmin;
	    float yw = m.ymax - m.ymin;
	    float zw = m.zmax - m.zmin;
	    /*
	    if (yw > xw)
		xw = yw;
	    if (zw > xw)
		xw = zw;
	    float f1 = getSize().width / xw;
	    float f2 = getSize().height / xw;
	    */
	    float f = (float)Math.sqrt(xw*xw+yw*yw+zw*zw);
	    float f1 = getSize().width / f;
	    float f2 = getSize().height / f;
	    xfac = 0.7f * (f1 < f2 ? f1 : f2) * scalefudge;
	} catch(Exception e) {
	    md = null;
	    message = e.toString();
	}
	try {
	    if (is != null)
		is.close();
	} catch(Exception e) {
	}
	repaint();
    }

    public void start() {
	if (md == null && message == null)
	    new Thread(this).start();
    }

    public void stop() {
    }
    
    public  void mouseClicked(MouseEvent e) {
	// ^^$ begin JPW
	int x = e.getX();
        int y = e.getY();
	repaint();	
	if (md.MouseClicked(x,y,xpos,ypos,zpos))
	    repaint();	
	e.consume();
	// ^^$ end
    }
    
    public  void mousePressed(MouseEvent e) {
        prevx = e.getX();
        prevy = e.getY();
        e.consume();
    }

    public  void mouseReleased(MouseEvent e) {
    }

    public  void mouseEntered(MouseEvent e) {
    }

    public  void mouseExited(MouseEvent e) {
    }
    
    public  void mouseDragged(MouseEvent e) {
        int x = e.getX();
        int y = e.getY();

        tmat.unit();
        float xtheta = (prevy - y) * 360.0f / getSize().width;
        float ytheta = (x - prevx) * 360.0f / getSize().height;
        tmat.xrot(xtheta);
        tmat.yrot(ytheta);
        amat.mult(tmat);
        if (painted) {
            painted = false;
            repaint();
        }
        prevx = x;
        prevy = y;
        e.consume();      
    }
  
    public  void mouseMoved(MouseEvent e) {
    }

    public void paint(Graphics g) {
	if (md != null) {
	    md.mat.unit();
	    md.mat.translate(-(md.xmin + md.xmax) / 2,
			     -(md.ymin + md.ymax) / 2,
			     -(md.zmin + md.zmax) / 2);
	    md.mat.mult(amat);
	    //md.mat.scale(xfac, -xfac, 16 * xfac / getSize().width);
	    md.mat.scale(xfac, -xfac, xfac);
	    md.mat.translate(getSize().width / 2, getSize().height / 2, 0);
	    md.transformed = false;
	    md.paint(g);
	    setPainted();
	} else if (message != null) {
	    g.drawString("Error in model:", 3, 20);
	    g.drawString(message, 10, 40);
	}
    }

    private synchronized void setPainted() {
	painted = true;
	notifyAll();
    }
//    private synchronized void waitPainted() {
//	while (!painted)
//	    wait();
//	painted = false;
//    }

    public String getAppletInfo() {
        return "Title: ThreeD \nAuthor: James Gosling? \nAn applet to put a 3D model into a page.";
    }
    
    public String[][] getParameterInfo() {
        String[][] info = {
            {"model", "path string", "The path to the model to be displayed."},
            {"scale", "float", "The scale of the model.  Default is 1."}
        };
        return info;
    }
}