code.vuplus.com Git - vuplus_webkit/blob - Source/ThirdParty/glu/libtess/normal.c

   1 /*
   2 ** License Applicability. Except to the extent portions of this file are
   3 ** made subject to an alternative license as permitted in the SGI Free
   4 ** Software License B, Version 1.1 (the "License"), the contents of this
   5 ** file are subject only to the provisions of the License. You may not use
   6 ** this file except in compliance with the License. You may obtain a copy
   7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
   8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
   9 **
  10 ** http://oss.sgi.com/projects/FreeB
  11 **
  12 ** Note that, as provided in the License, the Software is distributed on an
  13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
  14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
  15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
  16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
  17 **
  18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
  19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
  20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
  21 ** Copyright in any portions created by third parties is as indicated
  22 ** elsewhere herein. All Rights Reserved.
  23 **
  24 ** Additional Notice Provisions: The application programming interfaces
  25 ** established by SGI in conjunction with the Original Code are The
  26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
  27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
  28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
  29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
  30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
  31 ** published by SGI, but has not been independently verified as being
  32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
  33 **
  34 */
  35 /*
  36 ** Author: Eric Veach, July 1994.
  37 **
  38 ** $Date$ $Revision$
  39 ** $Header: //depot/main/gfx/lib/glu/libtess/normal.c#5 $
  40 */
  41
  42 #include "gluos.h"
  43 #include "mesh.h"
  44 #include "tess.h"
  45 #include "normal.h"
  46 #include <math.h>
  47 #include <assert.h>
  48
  49 #define TRUE 1
  50 #define FALSE 0
  51
  52 #define Dot(u,v)        (u[0]*v[0] + u[1]*v[1] + u[2]*v[2])
  53
  54 #if defined(FOR_TRITE_TEST_PROGRAM) || defined(TRUE_PROJECT)
  55 static void Normalize( GLdouble v[3] )
  56 {
  57   GLdouble len = v[0]*v[0] + v[1]*v[1] + v[2]*v[2];
  58
  59   assert( len > 0 );
  60   len = sqrt( len );
  61   v[0] /= len;
  62   v[1] /= len;
  63   v[2] /= len;
  64 }
  65 #endif
  66
  67 #define ABS(x)  ((x) < 0 ? -(x) : (x))
  68
  69 static int LongAxis( GLdouble v[3] )
  70 {
  71   int i = 0;
  72
  73   if( ABS(v[1]) > ABS(v[0]) ) { i = 1; }
  74   if( ABS(v[2]) > ABS(v[i]) ) { i = 2; }
  75   return i;
  76 }
  77
  78 static void ComputeNormal( GLUtesselator *tess, GLdouble norm[3] )
  79 {
  80   GLUvertex *v, *v1, *v2;
  81   GLdouble c, tLen2, maxLen2;
  82   GLdouble maxVal[3], minVal[3], d1[3], d2[3], tNorm[3];
  83   GLUvertex *maxVert[3], *minVert[3];
  84   GLUvertex *vHead = &tess->mesh->vHead;
  85   int i;
  86
  87   maxVal[0] = maxVal[1] = maxVal[2] = -2 * GLU_TESS_MAX_COORD;
  88   minVal[0] = minVal[1] = minVal[2] = 2 * GLU_TESS_MAX_COORD;
  89
  90   for( v = vHead->next; v != vHead; v = v->next ) {
  91     for( i = 0; i < 3; ++i ) {
  92       c = v->coords[i];
  93       if( c < minVal[i] ) { minVal[i] = c; minVert[i] = v; }
  94       if( c > maxVal[i] ) { maxVal[i] = c; maxVert[i] = v; }
  95     }
  96   }
  97
  98   /* Find two vertices separated by at least 1/sqrt(3) of the maximum
  99    * distance between any two vertices
 100    */
 101   i = 0;
 102   if( maxVal[1] - minVal[1] > maxVal[0] - minVal[0] ) { i = 1; }
 103   if( maxVal[2] - minVal[2] > maxVal[i] - minVal[i] ) { i = 2; }
 104   if( minVal[i] >= maxVal[i] ) {
 105     /* All vertices are the same -- normal doesn't matter */
 106     norm[0] = 0; norm[1] = 0; norm[2] = 1;
 107     return;
 108   }
 109
 110   /* Look for a third vertex which forms the triangle with maximum area
 111    * (Length of normal == twice the triangle area)
 112    */
 113   maxLen2 = 0;
 114   v1 = minVert[i];
 115   v2 = maxVert[i];
 116   d1[0] = v1->coords[0] - v2->coords[0];
 117   d1[1] = v1->coords[1] - v2->coords[1];
 118   d1[2] = v1->coords[2] - v2->coords[2];
 119   for( v = vHead->next; v != vHead; v = v->next ) {
 120     d2[0] = v->coords[0] - v2->coords[0];
 121     d2[1] = v->coords[1] - v2->coords[1];
 122     d2[2] = v->coords[2] - v2->coords[2];
 123     tNorm[0] = d1[1]*d2[2] - d1[2]*d2[1];
 124     tNorm[1] = d1[2]*d2[0] - d1[0]*d2[2];
 125     tNorm[2] = d1[0]*d2[1] - d1[1]*d2[0];
 126     tLen2 = tNorm[0]*tNorm[0] + tNorm[1]*tNorm[1] + tNorm[2]*tNorm[2];
 127     if( tLen2 > maxLen2 ) {
 128       maxLen2 = tLen2;
 129       norm[0] = tNorm[0];
 130       norm[1] = tNorm[1];
 131       norm[2] = tNorm[2];
 132     }
 133   }
 134
 135   if( maxLen2 <= 0 ) {
 136     /* All points lie on a single line -- any decent normal will do */
 137     norm[0] = norm[1] = norm[2] = 0;
 138     norm[LongAxis(d1)] = 1;
 139   }
 140 }
 141
 142
 143 static void CheckOrientation( GLUtesselator *tess )
 144 {
 145   GLdouble area;
 146   GLUface *f, *fHead = &tess->mesh->fHead;
 147   GLUvertex *v, *vHead = &tess->mesh->vHead;
 148   GLUhalfEdge *e;
 149
 150   /* When we compute the normal automatically, we choose the orientation
 151    * so that the the sum of the signed areas of all contours is non-negative.
 152    */
 153   area = 0;
 154   for( f = fHead->next; f != fHead; f = f->next ) {
 155     e = f->anEdge;
 156     if( e->winding <= 0 ) continue;
 157     do {
 158       area += (e->Org->s - e->Dst->s) * (e->Org->t + e->Dst->t);
 159       e = e->Lnext;
 160     } while( e != f->anEdge );
 161   }
 162   if( area < 0 ) {
 163     /* Reverse the orientation by flipping all the t-coordinates */
 164     for( v = vHead->next; v != vHead; v = v->next ) {
 165       v->t = - v->t;
 166     }
 167     tess->tUnit[0] = - tess->tUnit[0];
 168     tess->tUnit[1] = - tess->tUnit[1];
 169     tess->tUnit[2] = - tess->tUnit[2];
 170   }
 171 }
 172
 173 #ifdef FOR_TRITE_TEST_PROGRAM
 174 #include <stdlib.h>
 175 extern int RandomSweep;
 176 #define S_UNIT_X        (RandomSweep ? (2*drand48()-1) : 1.0)
 177 #define S_UNIT_Y        (RandomSweep ? (2*drand48()-1) : 0.0)
 178 #else
 179 #if defined(SLANTED_SWEEP)
 180 /* The "feature merging" is not intended to be complete.  There are
 181  * special cases where edges are nearly parallel to the sweep line
 182  * which are not implemented.  The algorithm should still behave
 183  * robustly (ie. produce a reasonable tesselation) in the presence
 184  * of such edges, however it may miss features which could have been
 185  * merged.  We could minimize this effect by choosing the sweep line
 186  * direction to be something unusual (ie. not parallel to one of the
 187  * coordinate axes).
 188  */
 189 #define S_UNIT_X        0.50941539564955385     /* Pre-normalized */
 190 #define S_UNIT_Y        0.86052074622010633
 191 #else
 192 #define S_UNIT_X        1.0
 193 #define S_UNIT_Y        0.0
 194 #endif
 195 #endif
 196
 197 /* Determine the polygon normal and project vertices onto the plane
 198  * of the polygon.
 199  */
 200 void __gl_projectPolygon( GLUtesselator *tess )
 201 {
 202   GLUvertex *v, *vHead = &tess->mesh->vHead;
 203   GLdouble norm[3];
 204   GLdouble *sUnit, *tUnit;
 205   int i, computedNormal = FALSE;
 206
 207   norm[0] = tess->normal[0];
 208   norm[1] = tess->normal[1];
 209   norm[2] = tess->normal[2];
 210   if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) {
 211     ComputeNormal( tess, norm );
 212     computedNormal = TRUE;
 213   }
 214   sUnit = tess->sUnit;
 215   tUnit = tess->tUnit;
 216   i = LongAxis( norm );
 217
 218 #if defined(FOR_TRITE_TEST_PROGRAM) || defined(TRUE_PROJECT)
 219   /* Choose the initial sUnit vector to be approximately perpendicular
 220    * to the normal.
 221    */
 222   Normalize( norm );
 223
 224   sUnit[i] = 0;
 225   sUnit[(i+1)%3] = S_UNIT_X;
 226   sUnit[(i+2)%3] = S_UNIT_Y;
 227
 228   /* Now make it exactly perpendicular */
 229   w = Dot( sUnit, norm );
 230   sUnit[0] -= w * norm[0];
 231   sUnit[1] -= w * norm[1];
 232   sUnit[2] -= w * norm[2];
 233   Normalize( sUnit );
 234
 235   /* Choose tUnit so that (sUnit,tUnit,norm) form a right-handed frame */
 236   tUnit[0] = norm[1]*sUnit[2] - norm[2]*sUnit[1];
 237   tUnit[1] = norm[2]*sUnit[0] - norm[0]*sUnit[2];
 238   tUnit[2] = norm[0]*sUnit[1] - norm[1]*sUnit[0];
 239   Normalize( tUnit );
 240 #else
 241   /* Project perpendicular to a coordinate axis -- better numerically */
 242   sUnit[i] = 0;
 243   sUnit[(i+1)%3] = S_UNIT_X;
 244   sUnit[(i+2)%3] = S_UNIT_Y;
 245
 246   tUnit[i] = 0;
 247   tUnit[(i+1)%3] = (norm[i] > 0) ? -S_UNIT_Y : S_UNIT_Y;
 248   tUnit[(i+2)%3] = (norm[i] > 0) ? S_UNIT_X : -S_UNIT_X;
 249 #endif
 250
 251   /* Project the vertices onto the sweep plane */
 252   for( v = vHead->next; v != vHead; v = v->next ) {
 253     v->s = Dot( v->coords, sUnit );
 254     v->t = Dot( v->coords, tUnit );
 255   }
 256   if( computedNormal ) {
 257     CheckOrientation( tess );
 258   }
 259 }