//---------------------------------------------------------------------------
//  Shapes.cpp
//
//  (C) COPYRIGHT John Henckel, mailto:henckel@iname.com         Aug 1998
//
//  Permission to use, copy, modify, distribute and sell this software
//  and its documentation for any purpose is hereby granted without fee,
//  provided that the above copyright notice appear in all copies.
//
//  Visit my website!  http://www.GeoCities.com/Paris/6502

#include "stdafx.h"
#include "Shapes.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

//---------------------------------------------------------------------------
//  This macro provides complete implementation for the trivial shape types

IMPLSHAPE1(Sphere)
IMPLSHAPE1(Teapot)
IMPLSHAPE1(Icosahedron)
IMPLSHAPE1(Octahedron)
IMPLSHAPE1(Tetrahedron)
IMPLSHAPE1(Dodecahedron)

//---------------------------------------------------------------------------
//  This macro provides partial implementation for the other shape types

IMPLSHAPE2(Box)
IMPLSHAPE2(Cone)
IMPLSHAPE2(Cylinder)
IMPLSHAPE2(Torus)
IMPLSHAPE2(Text)
IMPLSHAPE2(ConvexSolid)
IMPLSHAPE2(Camera)


//---------------------------------------------------------------------------
//  This is the main shape factory function

Shape* Shape::CreateFromString(CString& data, int linenum, CString& errmsg)
{
  CString name = data.SpanExcluding("\t {");
  CString msg;
  Shape* sh;

  if (name == "Camera")
    sh = new Camera();
  else if (name == "Box")
    sh = new Box();
  else if (name == "Torus")
    sh = new Torus();
  else if (name == "Sphere")
    sh = new Sphere();
  else if (name == "Cylinder")
    sh = new Cylinder();
  else if (name == "Text")
    sh = new Text();
  else if (name == "Cone")
    sh = new Cone();
  else if (name == "ConvexSolid")
    sh = new ConvexSolid();
  else if (name == "Teapot")
    sh = new Teapot();
  else if (name == "Octahedron" || name == "P8")
    sh = new Octahedron();
  else if (name == "Tetrahedron" || name == "P4")
    sh = new Tetrahedron();
  else if (name == "Dodecahedron" || name == "P12")
    sh = new Dodecahedron();
  else if (name == "Icosahedron" || name == "P20")
    sh = new Icosahedron();
  else {
    msg.Format("Unknown shape '%s' on line %d.\n",name,linenum);
    errmsg += msg;
    return NULL;
  }
  sh->linenum = linenum;
  return sh;
}

//----------------------------------------------------------------------
//  This does the generic "pre draw" operations for shapes

void Shape::PreDraw(int flags)             // Default PreDraw
{
  glTranslated(location.x, location.y, location.z);
  glMultMatrixd(rotation.AsMatrix());
  if (flags & DRAW_MONO)
    glMaterialfv(GL_FRONT, GL_DIFFUSE, Color(1,1,1)); 
  else
    glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, color); 

  glMateriali(GL_FRONT, GL_SHININESS, (int)(shine * 128));

  Color white(1,1,1);
  glMaterialfv(GL_FRONT, GL_SPECULAR, white); 
}

//---------------------------------------------------------------------------
//  Shape::Step
//
//  return 0 if no change, else return 1.

int Shape::Step() 
{
  if (speed.IsZero() && spin.IsZero())
    return 0;
  location += speed;
  rotation *= spin;
  if (!moment.IsDiagonal()) {
    Vect w = spin.SpinVector();        // get the angular velocity vector
    Vect dw = w.EulerDelta(moment);
    w += dw;
    double h = w.Length();
    w.Normalize();
    spin = Quat(h, w.x, w.y, w.z);
  }
  return 1;
}

//---------------------------------------------------------------------------
//  Shape::Title

CString Shape::Title()
{
  if (title != "") 
    return title;
  CString result;
  result.Format("%s (line %d)", TypeString(), linenum);
  return result;
}

//---------------------------------------------------------------------------

#define PARSE1d(attr,a1) \
  if (name == attr) { \
    char* buf = data.GetBuffer(0) + sizeof attr; \
    a1 = 0.0; a1 = strtod(buf, &buf); return; }

#define PARSE2d(attr,a1,a2) \
  if (name == attr) { \
    char* buf = data.GetBuffer(0) + sizeof attr; \
    a1 = a2 = 0.0; \
    a1 = strtod(buf, &buf); \
    a2 = strtod(buf, &buf); \
    return; }

#define PARSE3d(attr,vv) \
  if (name == attr) { \
    char* buf = data.GetBuffer(0) + sizeof attr; \
    vv.x = strtod(buf, &buf); \
    vv.y = strtod(buf, &buf); \
    vv.z = strtod(buf, &buf); \
    return; }

#define PARSE4Color(attr,c) \
  if (name == attr) { \
    char* buf = data.GetBuffer(0) + sizeof attr; \
    c = Color(); \
    c.r = (GLfloat)strtod(buf, &buf); \
    c.g = (GLfloat)strtod(buf, &buf); \
    c.b = (GLfloat)strtod(buf, &buf); \
    c.a = (GLfloat)strtod(buf, &buf); \
    return; }

#define PARSE4Quat(attr,q) \
  if (name == attr) { \
    ParseQuat(data,q); \
    return; }

//---------------------------------------------------------------------------
//  Utility function to parse string data

static void ParseText(CString& data, CString& tx) 
{
  tx = "";
  int n = data.FindOneOf("\t ");
  if (n == -1) 
    return;
  tx = data.Mid(n);
  tx.TrimLeft();
}

//---------------------------------------------------------------------------
//  Utility function to parse a quaternion
//
//  The input data should be as the VRML rotation.  It has a vector and
//  an angle.  Like "0 1 0 3.14" is a rotation 180 degrees around the y-axis.
//  The vector need not be normalized, but the magnitude is insignificant.

static void ParseQuat(CString& data, Quat& q) 
{
  int n = data.FindOneOf("\t ");
  q = Quat();               // default value
  if (n == -1) 
    return;
  char* buf = data.GetBuffer(0) + n;
  double t,x,y,z,r; 
  t=x=y=0.0, z=1.0; 
  x = strtod(buf, &buf); 
  y = strtod(buf, &buf); 
  z = strtod(buf, &buf); 
  t = strtod(buf, &buf); 
  r = sqrt(x*x + y*y + z*z); 
  if (r < EPSILON)
    return;
  q = Quat(t,x/r,y/r,z/r);
}


//---------------------------------------------------------------------------
//  Shape::ParseAttr

void Shape::ParseAttr(CString& data, int linenum, CString& errmsg)
{
  CString name = data.SpanExcluding("\t ");

  PARSE3d("location", location);
  PARSE4Quat("rotation",rotation);
  PARSE3d("speed", speed);
  PARSE4Color("color", color);
  PARSE4Quat("spin", spin);
  PARSE1d("shine", shine);
  PARSE1d("size", radius);
  PARSE1d("radius", radius);
  PARSE1d("mass", mass);
  PARSE3d("moment", moment);
  if (name=="title" || name=="name") {
    ParseText(data, title);
    return;
  }

  CString msg;
  msg.Format("Unknown attribute '%s' on line %d.\n",name,linenum);
  errmsg += msg;
}


//---------------------------------------------------------------------------
//  Set the rotation so that it will look at a particular point.
//
//  This assumes that the shape initially is oriented with +y up and -z ahead.
//  If tilt is zero, +y up is preserved.

void Shape::LookAt(const Vect& v, double tilt, double alpha) 
{
  Vect p = v - location;       // new lookat direction

  double yaw = atan2(-p.x, -p.z);
  Quat r2(yaw, 0, 1, 0);

  double r = sqrt(p.x*p.x + p.z*p.z);
  double pitch = atan2(p.y, r);
  r2 *= Quat(pitch, 1, 0, 0);

  if (fabs(tilt) > EPSILON)
    r2 *= Quat(tilt, 0, 0, 1);

  if (alpha == 1.0)
    rotation = r2;
  else
    rotation.Slerp(r2, alpha);
}


//---------------------------------------------------------------------------
//  Box::Box

Box::Box() : size(1,1,1)
{
  // do nothing
}

//---------------------------------------------------------------------------
//  Box::ParseAttr

void Box::ParseAttr(CString& data, int linenum, CString& errmsg)
{
  CString name = data.SpanExcluding("\t ");
  PARSE3d("size", size);
  Shape::ParseAttr(data,linenum,errmsg);
}

//---------------------------------------------------------------------------
//  Box::Draw

void Box::Draw(int flags)
{
  PreDraw(flags);
  if (flags & DRAW_WIRE)
    auxWireBox(size.x, size.y, size.z);
  else
    auxSolidBox(size.x, size.y, size.z);
}

//---------------------------------------------------------------------------
//  Box::FinishInit

void Box::FinishInit()
{
  size.x = fabs(size.x);
  size.y = fabs(size.y);
  size.z = fabs(size.z);

  radius = 0.5 * size.Length();
}


//---------------------------------------------------------------------------
//  Torus::Torus

Torus::Torus() 
{
  rad2 = 0.5;
}

//---------------------------------------------------------------------------
//  Torus::ParseAttr

void Torus::ParseAttr(CString& data, int linenum, CString& errmsg)
{
  CString name = data.SpanExcluding("\t ");
  PARSE1d("radius2",rad2);
  Shape::ParseAttr(data,linenum,errmsg);
}

//---------------------------------------------------------------------------
//  Torus::Draw

void Torus::Draw(int flags)
{
  PreDraw(flags);
  if (flags & DRAW_WIRE)
    auxWireTorus(rad2, rad1);
  else
    auxSolidTorus(rad2, rad1);
}

//---------------------------------------------------------------------------
//  Torus::FinishInit

void Torus::FinishInit()
{
  if (rad1 < 0) rad1 = -rad1;
  if (radius < 0) radius = -radius;

  rad1 = radius;
  radius += rad2;
}


//---------------------------------------------------------------------------
//  Cylinder::Cylinder

Cylinder::Cylinder() 
{
  len = rad = 1.0;
}

//---------------------------------------------------------------------------
//  Cylinder::ParseAttr

void Cylinder::ParseAttr(CString& data, int linenum, CString& errmsg)
{
  CString name = data.SpanExcluding("\t ");
  PARSE1d("length",len);
  PARSE1d("height",len);
  Shape::ParseAttr(data,linenum,errmsg);
}

//---------------------------------------------------------------------------
//  Cylinder::Draw

void Cylinder::Draw(int flags)
{
  PreDraw(flags);
  if (flags & DRAW_WIRE)
    auxWireCylinder(len, rad);
  else
    auxSolidCylinder(len, rad);
}

//---------------------------------------------------------------------------
//  Cylinder::FinishInit

void Cylinder::FinishInit()
{
  if (len < 0) len = -len;
  if (radius < 0) radius = -radius;

  rad = radius;
  if (radius < len) radius = len;
}


//---------------------------------------------------------------------------
//  Cone::Cone

Cone::Cone() 
{
  len = rad = 1.0;
}

//---------------------------------------------------------------------------
//  Cone::ParseAttr

void Cone::ParseAttr(CString& data, int linenum, CString& errmsg)
{
  CString name = data.SpanExcluding("\t ");
  PARSE1d("height",len);
  Shape::ParseAttr(data,linenum,errmsg);
}

//---------------------------------------------------------------------------
//  Cone::Draw

void Cone::Draw(int flags)
{
  PreDraw(flags);
  if (flags & DRAW_WIRE)
    auxWireCone(len, rad);
  else
    auxSolidCone(len, rad);
}

//---------------------------------------------------------------------------
//  Cone::FinishInit

void Cone::FinishInit()
{
  if (len < 0) len = -len;
  if (radius < 0) radius = -radius;

  rad = radius;
  if (radius < len) radius = len;
}


//---------------------------------------------------------------------------
//  ConvexSolid::ConvexSolid()

ConvexSolid::ConvexSolid()
{
  scale = 1.0;
}

//---------------------------------------------------------------------------
//  ConvexSolid::ParseAttr

void ConvexSolid::ParseAttr(CString& data, int linenum, CString& errmsg)
{
  CString name = data.SpanExcluding("\t ");
  if (name == "point") { 
    char* buf = data.GetBuffer(0) + 5; 
    Vect v;
    while (*buf) {
      if (*buf > '9') {
        CString msg;
        msg.Format("Unexpected point data '%.32s' on line %d.\n",buf,linenum);
        errmsg += msg;
        break;
      }
      v.x = strtod(buf, &buf);      // Parse the vertex and store it.
      v.y = strtod(buf, &buf); 
      v.z = strtod(buf, &buf); 
      vert.Add(v);

      if (*buf) ++buf;
    }
    return; 
  }
  if (name == "generate") {   // radius, noise, slices, stacks, height
    char* buf = data.GetBuffer(0) + 8; 
    Vect v;
    double rad, noiz, slice, stak, h, r;
    rad = strtod(buf, &buf);
    noiz = strtod(buf, &buf);
    slice = strtod(buf, &buf);
    stak = strtod(buf, &buf);
    h = strtod(buf, &buf);

    if (rad <= 0) rad = 1.0;
    if (slice <= 0) slice = 6.0;
    if (stak <= 0) stak = 3.0;
    if (h <= 0) h = rad*2;

    h /= rad*2;
    double t,w,t1,w1;
    t1 = M_PI*(slice-1)/slice;
    w1 = M_PI*(stak-1)/stak/2;
    for (t=-t1; t < (t1+EPSILON); t+=2*M_PI/slice) {
      for (w=-w1; w < (w1+EPSILON); w+=M_PI/stak) { 
        r = rad + random(noiz);
        v.x = cos(t)*cos(w)*r;
        v.y = sin(w)*h*r;
        v.z = sin(t)*cos(w)*r;
        vert.Add(v);
      }
    }
    return; 
  }
  PARSE3d("center", center);
  PARSE1d("scale",scale);
  Shape::ParseAttr(data,linenum,errmsg);
}

//---------------------------------------------------------------------------
//  ConvexSolid::Draw

void ConvexSolid::Draw(int flags)
{
  PreDraw(flags);
  if (flags & DRAW_WIRE) {          // Draw edges only
    int n,i;
    n = edge.GetSize();
		glBegin(GL_LINES);
    for (i=0; i<n; ++i) {
 			glVertex3dv(vert[edge[i].p1]);
 			glVertex3dv(vert[edge[i].p2]);
    }
 		glEnd();
  }
  else {                            // Draw polygon faces
    int n,m,i,j;
    n = face.GetSize();
    for (i=0; i<n; ++i) {
  		glBegin(GL_POLYGON);
			glNormal3dv(face[i].normal);
      m = face[i].vert.GetSize();   // number of vertices on the face
      for (j=0; j<m; ++j)
  			glVertex3dv(vert[face[i].vert[j]]);
  		glEnd();
    }
  }
}

//---------------------------------------------------------------------------
// Helper class for sorting vertices on a face.

struct FacePoint {
  FacePoint(int a=0,double b=0.0):p(a), d(b) {}
  int p; double d;
};

int FPcompare( const void *arg1, const void *arg2 ) 
{
  double r = ((FacePoint*)arg1)->d - ((FacePoint*)arg2)->d;
  return (r < 0) ? 1 : (r > 0) ? -1 : 0;
}

int FindEdge(const EdgeArray& ea, Edge e) 
{
  int i, n = ea.GetSize();
  for (i=0; i<n; ++i)
    if (ea[i] == e) return i;
  return -1;
}

void RemoveEdge(EdgeArray& ea, int i) 
{
  int n = ea.GetSize() - 1;
  ASSERT(i <= n);
  if (i < n) ea[i] = ea[n];
  ea.RemoveAt(n);
}

//---------------------------------------------------------------------------
//  ConvexSolid::FinishInit
//
//  This computes the edges and faces of the ConvexSolid based on the
//  vertices.

void ConvexSolid::FinishInit()
{
  int i,n;
  int p1,p2,p3;
  double md, d; 
  p1=p2=p3=-1;

  n = vert.GetSize();
  if (n == 0)
    return;

  // Make one pass over the points to (1) adjust the center and scale, 
  // (2) compute the radius of the bounding sphere, (3) find an extreme
  // point in some random direction.  This will be used for the initial edge.

  Vect va, vb, vc;
  Vect vn;
  vn.Random();
  vn.Normalize();
  radius = 0;
  if (scale == 0.0) scale = 1.0;

  for (i=0; i<n; ++i) {
    vert[i] -= center;
    vert[i] *= scale;
    d = vert[i].Length();
    if (d > radius) radius = d;

    d = vn.Dot(vert[i]);
    if (!i || d > md) {
      md = d; p1 = i;
    }
  }

  //  Find another point, p2, to use for the initial edge.  Choose p2
  //  with the smallest angle to the normal plane at p1.

  md = 2;
  p2 = -1;
  for (i=0; i<n; ++i) {
    if (i != p1) {
      va = vert[p1] - vert[i];
      d = vn.Dot(va) / va.Length();
      if (d < md) {
        md = d; p2 = i;
      }
    }
  }

  ASSERT(p2 >= 0);

  //  For each edge (p1, p2), build two faces

  CArray <FacePoint,FacePoint&> plane;
  EdgeArray todo;
  Face f;
  Edge e(p1,p2);
  int pp3,j, nt = 1;         // nt means "number to do"

  todo.Add(e);
  if (p1<p2) edge.Add(e);
  else edge.Add(Edge(p2,p1));

  while (nt > 0) {

    p1 = todo[nt-1].p1;
    p2 = todo[nt-1].p2;

    va = vert[p1] - vert[p2];

    //  Choose any non-collinear vertex for the initial value of p3

    for (p3=0; p3<n; ++p3) {
      if (p3!=p1 && p3!=p2) {     // next vertex not equal to p1 or p2
        vb = vert[p3] - vert[p2];
        vn = va.Cross(vb);
        if (vn.Length() > EPSILON) break;     // if non-collinear, stop loop
      }
    }

    ASSERT(p3 < n);        // all points are collinear

    for (j=0; j<n; ++j) {
      vn.Normalize();

      md=0; 
      pp3=p3;
      plane.RemoveAll();

      for (i=0; i<n; ++i) {
        if (i != p1 && i != p2) {
          d = (vert[i] - vert[p2]).Dot(vn);  // distance to 'i' in direction 'vn'
          if (fabs(d) < 0.0001) // d < EPSILON && -d < EPSILON)
            plane.Add(FacePoint(i));
          else if (d > md) {
            md = d; p3 = i;            // store maximum
          }
        }
      }
      if (pp3==p3) break;         // Success, no exterior points found.

      vb = vert[p3] - vert[p2];
      vn = va.Cross(vb);
    }

    ASSERT(pp3==p3);      // p2 must be an INTERIOR point.

    // Construct the face using p1, p2 and all the plane points.

    int a1, a2, np = plane.GetSize();

    ASSERT(np > 0);

    vb = vert[p1] + vert[p2];    // midpoint
    vb *= 0.5;

    for (i=0; i<np; ++i) {
      vc = vert[plane[i].p] - vb;
      vc.Normalize();
      plane[i].d = va.Dot(vc);
    }

    qsort(plane.GetData(), np, sizeof(FacePoint), FPcompare);

    for (i=-2; i<np; ++i) {

      if (i==-2) {
        a1 = p2; 
        a2 = plane[np-1].p;
      }
      else if (i==-1) {
        a1 = p1; 
        a2 = p2;
      }
      else {
        a1 = plane[i].p;
        a2 = p1;
        p1 = a1; 
      }
      f.vert.Add(a1);

      Edge e(a1,a2);
      if (a1 > a2) e = Edge(a2,a1);

      if (FindEdge(edge, e) >=0) {
        int x = FindEdge(todo, Edge(a1,a2));
        if (x >= 0)
          RemoveEdge(todo,x);
      }
      else {
        edge.Add(e);
        todo.Add(Edge(a2,a1));
      }
    }
    f.normal = vn;
    face.Add(f);

    /********************** FOR DEBUGGING *******************
    CString tmsg;
    CString temp;
    tmsg = Title() + " face";
    for (i=0; i<f.vert.GetSize(); ++i) {
      temp.Format(" %d,", f.vert[i]); 
      tmsg += temp;
    }
    temp.Format(" N=%g %g %g", f.normal.x, f.normal.y, f.normal.z); 
    tmsg += temp;
    AfxMessageBox(tmsg);
    **********************************************************/

    f.vert.RemoveAll();
    nt = todo.GetSize();
  }
  /************************
  CString tmsg;
  tmsg.Format("%s has %d vertices, %d edges, and %d faces.",
                 Title(),vert.GetSize(),edge.GetSize(),face.GetSize());
  AfxMessageBox(tmsg);
  *************************/
}


//---------------------------------------------------------------------------
//  Camera  constructor

Camera::Camera()
{
  fov = 45;               // field of view
  clipnear = 0.01;
  clipfar = 1000;
  background = Color(0,0,0);
  location = Vect(0,0,10);
  tilt = 99.99;               // dummy value
  look = FALSE;
}

//---------------------------------------------------------------------------
//  Camera::ParseAttr

void Camera::ParseAttr(CString& data, int linenum, CString& errmsg)
{
  CString name = data.SpanExcluding("\t ");

  PARSE1d("fov", fov);
  PARSE2d("clipping", clipnear, clipfar);
  PARSE4Color("background",background);
  if (name == "lookat") { 
    char* buf = data.GetBuffer(0) + sizeof "lookat";
    lookat.x = strtod(buf, &buf);
    lookat.y = strtod(buf, &buf);
    lookat.z = strtod(buf, &buf);
    tilt = strtod(buf, &buf);
    return;
  }
  Shape::ParseAttr(data,linenum,errmsg);
}

//---------------------------------------------------------------------------
//  Camera::FinishInit

void Camera::FinishInit()
{
  if (clipnear >= clipfar) {
    CString msg;
    msg.Format("Camera on line %d has clipping near=%g, and far=%g",
      linenum,clipnear,clipfar);
    AfxMessageBox(msg);
    clipfar = clipnear + 1;
  }
  look = (tilt != 99.99);
}

//---------------------------------------------------------------------------
//  Camera::Draw

void Camera::Draw(int flags) 
{ 
  // do nothing
}

//---------------------------------------------------------------------------
//  Camera::Step
//
//  The camera overrides the step method so that it can handle special
//  movement such as rotating the speed vector, and looking at something.

int Camera::Step() 
{ 
  int rc = Shape::Step();
  
  if (look) {
    LookAt(lookat,tilt,0.50);
    ++rc;
  }
  speed.Rotate(spin);        // cameras move in a curved path

  return rc;
}

//---------------------------------------------------------------------------
//  Text::Text

Text::Text() 
{
  text = "Default Text";
}

//---------------------------------------------------------------------------
//  Text::ParseAttr

void Text::ParseAttr(CString& data, int linenum, CString& errmsg)
{
  CString name = data.SpanExcluding("\t ");
  if (name=="text") {
    ParseText(data, text);
    return;
  }
  Shape::ParseAttr(data,linenum,errmsg);
}

//---------------------------------------------------------------------------
//  Text::Draw

void Text::Draw(int flags)
{
  PreDraw(flags);
  auxDrawStr(text);
}

//---------------------------------------------------------------------------
//  Text::FinishInit

void Text::FinishInit()
{
  // do nothing
}