Panorama 360 iPod Touch & iPhone

/*
 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice including the dates of first publication and
 * either this permission notice or a reference to
 * http://oss.sgi.com/projects/FreeB/
 * shall be included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 *
 * Except as contained in this notice, the name of Silicon Graphics, Inc.
 * shall not be used in advertising or otherwise to promote the sale, use or
 * other dealings in this Software without prior written authorization from
 * Silicon Graphics, Inc.
 */
/*
** Author: Eric Veach, July 1994.
**
*/

#include "mesh.h"
#include "tess.h"
#include "normal.h"
#include <math.h>
#include <assert.h>

#define TRUE 1
#define FALSE 0

#define Dot(u, v) (u[0]*v[0]+u[1]*v[1]+u[2]*v[2])

#undef ABS
#define ABS(x) ((x)<0 ? -(x) : (x))

static int LongAxis(GLfloat v[3])
{
   int i=0;

   if (ABS(v[1])>ABS(v[0]))
   {
      i=1;
   }
   if (ABS(v[2])>ABS(v[i]))
   {
      i=2;
   }

   return i;
}

static void ComputeNormal(GLUtesselator* tess, GLfloat norm[3])
{
   GLUvertex* v, *v1, *v2;
   GLfloat c, tLen2, maxLen2;
   GLfloat maxVal[3], minVal[3], d1[3], d2[3], tNorm[3];
   GLUvertex* maxVert[3], *minVert[3];
   GLUvertex* vHead=&tess->mesh->vHead;
   int i;

   maxVal[0]=maxVal[1]=maxVal[2]=-2*GLU_TESS_MAX_COORD;
   minVal[0]=minVal[1]=minVal[2]=2*GLU_TESS_MAX_COORD;

   for (v=vHead->next; v!=vHead; v=v->next)
   {
      for (i=0; i<3; ++i)
      {
         c=v->coords[i];
         if (c<minVal[i])
         {
            minVal[i]=c;
            minVert[i]=v;
         }
         if (c>maxVal[i])
         {
            maxVal[i]=c;
            maxVert[i]=v;
         }
      }
   }

   /* Find two vertices separated by at least 1/sqrt(3) of the maximum
    * distance between any two vertices
    */
   i=0;
   if (maxVal[1]-minVal[1]>maxVal[0]-minVal[0])
   {
      i=1;
   }
   if (maxVal[2]-minVal[2]>maxVal[i]-minVal[i])
   {
      i=2;
   }
   if (minVal[i]>=maxVal[i])
   {
      /* All vertices are the same -- normal doesn't matter */
      norm[0]=0; norm[1]=0; norm[2]=1;
      return;
   }

   /* Look for a third vertex which forms the triangle with maximum area
    * (Length of normal == twice the triangle area)
    */
   maxLen2 = 0;
   v1=minVert[i];
   v2=maxVert[i];
   d1[0]=v1->coords[0]-v2->coords[0];
   d1[1]=v1->coords[1]-v2->coords[1];
   d1[2]=v1->coords[2]-v2->coords[2];
   for (v=vHead->next; v!=vHead; v=v->next)
   {
      d2[0]=v->coords[0]-v2->coords[0];
      d2[1]=v->coords[1]-v2->coords[1];
      d2[2]=v->coords[2]-v2->coords[2];
      tNorm[0]=d1[1]*d2[2]-d1[2]*d2[1];
      tNorm[1]=d1[2]*d2[0]-d1[0]*d2[2];
      tNorm[2]=d1[0]*d2[1]-d1[1]*d2[0];
      tLen2=tNorm[0]*tNorm[0]+tNorm[1]*tNorm[1]+tNorm[2]*tNorm[2];
      if (tLen2>maxLen2)
      {
         maxLen2=tLen2;
         norm[0]=tNorm[0];
         norm[1]=tNorm[1];
         norm[2]=tNorm[2];
      }
   }

   if (maxLen2<=0)
   {
      /* All points lie on a single line -- any decent normal will do */
      norm[0]=norm[1]=norm[2]=0;
      norm[LongAxis(d1)]=1;
   }
}

static void CheckOrientation(GLUtesselator* tess)
{
   GLfloat area;
   GLUface* f, *fHead=&tess->mesh->fHead;
   GLUvertex* v, *vHead=&tess->mesh->vHead;
   GLUhalfEdge* e;

   /* When we compute the normal automatically, we choose the orientation
    * so that the the sum of the signed areas of all contours is non-negative.
    */
   area=0;
   for (f=fHead->next; f!=fHead; f=f->next)
   {
      e=f->anEdge;
      if (e->winding<=0)
      {
         continue;
      }

      do {
         area+=(e->Org->s-e->Dst->s)*(e->Org->t+e->Dst->t);
         e=e->Lnext;
      } while(e!=f->anEdge);
   }
   if (area<0)
   {
      /* Reverse the orientation by flipping all the t-coordinates */
      for (v=vHead->next; v!=vHead; v=v->next)
      {
         v->t=-v->t;
      }
      tess->tUnit[0]=-tess->tUnit[0];
      tess->tUnit[1]=-tess->tUnit[1];
      tess->tUnit[2]=-tess->tUnit[2];
   }
}

#ifdef FOR_TRITE_TEST_PROGRAM
#include <stdlib.h>

extern int RandomSweep;
#define S_UNIT_X (RandomSweep ? (2*drand48()-1) : 1.0f)
#define S_UNIT_Y (RandomSweep ? (2*drand48()-1) : 0.0f)
#else /* FOR_TRITE_TEST_PROGRAM */
#if defined(SLANTED_SWEEP)
/* The "feature merging" is not intended to be complete.  There are
 * special cases where edges are nearly parallel to the sweep line
 * which are not implemented.  The algorithm should still behave
 * robustly (ie. produce a reasonable tesselation) in the presence
 * of such edges, however it may miss features which could have been
 * merged.  We could minimize this effect by choosing the sweep line
 * direction to be something unusual (ie. not parallel to one of the
 * coordinate axes).
 */
#define S_UNIT_X 0.50941539564955385f /* Pre-normalized */
#define S_UNIT_Y 0.86052074622010633f
#else /* SLANTED_SWEEP */
#define S_UNIT_X 1.0f
#define S_UNIT_Y 0.0f
#endif /* SLANTED_SWEEP */
#endif /* FOR_TRITE_TEST_PROGRAM */

/* Determine the polygon normal and project vertices onto the plane
 * of the polygon.
 */
void __gl_projectPolygon(GLUtesselator* tess)
{
   GLUvertex *v, *vHead=&tess->mesh->vHead;
   GLfloat norm[3];
   GLfloat* sUnit;
   GLfloat* tUnit;
   int i;
   int computedNormal=FALSE;

   norm[0]=tess->normal[0];
   norm[1]=tess->normal[1];
   norm[2]=tess->normal[2];

   if (norm[0]==0 && norm[1]==0 && norm[2]==0)
   {
      ComputeNormal(tess, norm);
      computedNormal=TRUE;
   }
   sUnit=tess->sUnit;
   tUnit=tess->tUnit;
   i=LongAxis(norm);

#if defined(FOR_TRITE_TEST_PROGRAM) || defined(TRUE_PROJECT)
   /* Choose the initial sUnit vector to be approximately perpendicular
    * to the normal.
    */
   Normalize(norm);

   sUnit[i]=0;
   sUnit[(i+1)%3]=S_UNIT_X;
   sUnit[(i+2)%3]=S_UNIT_Y;

   /* Now make it exactly perpendicular */
   w=Dot(sUnit, norm);
   sUnit[0]-=w*norm[0];
   sUnit[1]-=w*norm[1];
   sUnit[2]-=w*norm[2];
   Normalize(sUnit);

   /* Choose tUnit so that (sUnit,tUnit,norm) form a right-handed frame */
   tUnit[0]=norm[1]*sUnit[2]-norm[2]*sUnit[1];
   tUnit[1]=norm[2]*sUnit[0]-norm[0]*sUnit[2];
   tUnit[2]=norm[0]*sUnit[1]-norm[1]*sUnit[0];
   Normalize(tUnit);
#else /* FOR_TRITE_TEST_PROGRAM || TRUE_PROJECT */
   /* Project perpendicular to a coordinate axis -- better numerically */
   sUnit[i]=0;
   sUnit[(i+1)%3]=S_UNIT_X;
   sUnit[(i+2)%3]=S_UNIT_Y;

   tUnit[i]=0;
   tUnit[(i+1)%3]=(norm[i]>0) ? -S_UNIT_Y :  S_UNIT_Y;
   tUnit[(i+2)%3]=(norm[i]>0) ?  S_UNIT_X : -S_UNIT_X;
#endif /* FOR_TRITE_TEST_PROGRAM || TRUE_PROJECT */

   /* Project the vertices onto the sweep plane */
   for (v=vHead->next; v!=vHead; v=v->next)
   {
      v->s=Dot(v->coords, sUnit);
      v->t=Dot(v->coords, tUnit);
   }
   if (computedNormal)
   {
      CheckOrientation(tess);
   }
}