OSGNormalQuantifier.cpp

Go to the documentation of this file.
00001 /*---------------------------------------------------------------------------*\
00002  *                                OpenSG                                     *
00003  *                                                                           *
00004  *                                                                           *
00005  *                Copyright (C) 2000-2003 by the OpenSG Forum                *
00006  *                                                                           *
00007  *                            www.opensg.org                                 *
00008  *                                                                           *
00009  *   contact: dirk@opensg.org, gerrit.voss@vossg.org, jbehr@zgdv.de          *
00010  *                                                                           *
00011 \*---------------------------------------------------------------------------*/
00012 /*---------------------------------------------------------------------------*\
00013  *                                License                                    *
00014  *                                                                           *
00015  * This library is free software; you can redistribute it and/or modify it   *
00016  * under the terms of the GNU Library General Public License as published    *
00017  * by the Free Software Foundation, version 2.                               *
00018  *                                                                           *
00019  * This library is distributed in the hope that it will be useful, but       *
00020  * WITHOUT ANY WARRANTY; without even the implied warranty of                *
00021  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
00022  * Library General Public License for more details.                          *
00023  *                                                                           *
00024  * You should have received a copy of the GNU Library General Public         *
00025  * License along with this library; if not, write to the Free Software       *
00026  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 *
00027  *                                                                           *
00028 \*---------------------------------------------------------------------------*/
00029 /*---------------------------------------------------------------------------*\
00030  *                                Changes                                    *
00031  *                                                                           *
00032  *  initial version: based on code from P. Reuter (preuter@labri.fr)         *
00033  *                                                                           *
00034  *                                                                           *
00035  *                                                                           *
00036  *                                                                           *
00037 \*---------------------------------------------------------------------------*/
00038
00039 //---------------------------------------------------------------------------
00040 //  Includes
00041 //---------------------------------------------------------------------------
00042
00043 #include <cstdlib>
00044 #include <cstdio>
00045
00046 #include "OSGNormalQuantifier.h"
00047 #include "OSGLog.h"
00048
00049 #define EPSILON 0.0000001
00050 
00051 OSG_BEGIN_NAMESPACE
00052
00053
00054 /*--------------------------- Constructors --------------------------------*/
00055
00056 NormalQuantifier::NormalQuantifier(UInt32 numberSubdivisions)
00057 {
00058     build(numberSubdivisions);
00059 }
00060
00061 /*---------------------------- Destructor ---------------------------------*/
00062
00063 NormalQuantifier::~NormalQuantifier(void)
00064 {
00065 }
00066
00067 /*---------------------------- get ----------------------------------------*/
00068
00072 UInt32 NormalQuantifier::getIndex(Vec3f  &normal,
00073                                   UInt32  numberSubdivisions) const
00074 {
00075     UInt32 index;
00076     UInt32 nS;
00077     UInt32 octant;
00078     Int32 xoctant;
00079     Int32 yoctant;
00080     Int32 zoctant;
00081
00082     Vec3f point1;
00083     Vec3f point2;
00084     Vec3f point3;
00085
00086     if(numberSubdivisions == 0)
00087     {
00088         nS = _numberSubdivisions;
00089     }
00090     else if(numberSubdivisions > _numberSubdivisions)
00091     {
00092         nS = _numberSubdivisions;
00093     }
00094     else
00095     {
00096         nS = numberSubdivisions;
00097     }
00098
00099     octant =
00100         (((normal.x() >= 0) ? 0 : 1) << 2) |
00101         (((normal.y() >= 0) ? 0 : 1) << 1) |
00102         ( (normal.z() >= 0) ? 0 : 1);
00103
00104     xoctant = (octant & 4) ? -1 : 1;
00105     yoctant = (octant & 2) ? -1 : 1;
00106     zoctant = (octant & 1) ? -1 : 1;
00107
00108     point1.setValues(0.f * xoctant, 0.f * yoctant, 1.f * zoctant);
00109     point2.setValues(1.f * xoctant, 0.f * yoctant, 0.f * zoctant);
00110     point3.setValues(0.f * xoctant, 1.f * yoctant, 0.f * zoctant);
00111
00112     index = getSubIndex(normal, point1, point2, point3, nS);
00113
00114     index = (octant << (2 * nS)) + index;
00115
00116     return index;
00117 }
00118
00119 /*---------------------------- Build --------------------------------------*/
00120
00124 void NormalQuantifier::build (UInt32 numberSubdivisions)
00125 {
00126     UInt32 index = 0;
00127     UInt32 nN    = ((1 << (2 * numberSubdivisions)) * 8);
00128
00129     _numberSubdivisions = numberSubdivisions;
00130
00131     _normalTable.resize(nN);
00132
00133     if(_numberSubdivisions != 0)
00134     {
00135         for(UInt32 octant = 0; octant < 8; octant++)
00136         {
00137             Int32 xoctant = (octant & 4)>0?-1:1;
00138             Int32 yoctant = (octant & 2)>0?-1:1;
00139             Int32 zoctant = (octant & 1)>0?-1:1;
00140
00141             Vec3f point1(0.f * xoctant, 0.f * yoctant, 1.f * zoctant);
00142             Vec3f point2(1.f * xoctant, 0.f * yoctant, 0.f * zoctant);
00143             Vec3f point3(0.f * xoctant, 1.f * yoctant, 0.f * zoctant);
00144
00145             subdivide(point1, point2, point3, _numberSubdivisions+1, index);
00146         }
00147
00148         if(index != nN)
00149         {
00150             FFATAL(("NormalQuantifier::build() index missmatch!\n"));
00151         }
00152         else
00153         {
00154             FLOG(("NormalQuantifier init: %d subdivision, %"PRISize" normal\n",
00155                   _numberSubdivisions, _normalTable.size()));
00156         }
00157     }
00158 }
00159
00160 /*---------------------------- Helper -------------------------------------*/
00161
00162 // ----------------------------------------------
00163 // RayTriangle Intersection Function
00164 // by RealTime Rendering:
00165 // http://www.acm.org/jgt/papers/MollerTrumbore97/
00166 // date: December 12th, 2000
00167 // ----------------------------------------------
00168 bool NormalQuantifier::rayTriangle ( const Vec3f & dir,
00169                                      const Vec3f & vert0,
00170                                      const Vec3f & vert1,
00171                                      const Vec3f & vert2 ) const
00172 {
00173   Vec3f edge1, edge2, tvec, pvec, qvec;
00174   float det,inv_det;
00175   float u,v;
00176   Vec3f orig(0,0,0);
00177
00178   /* find vectors for two edges sharing vert0 */
00179   edge1 = vert1 - vert0;
00180   edge2 = vert2 - vert0;
00181
00182   /* begin calculating determinant - also used to calculate U parameter */
00183   pvec = dir.cross(edge2);
00184
00185   /* if determinant is near zero, ray lies in plane of triangle */
00186   det = edge1.dot(pvec);
00187
00188   /* the non-culling branch */
00189   if (det > -EPSILON && det < EPSILON)
00190     return false;
00191
00192   inv_det = 1.0f / det;
00193
00194   /* calculate distance from vert0 to ray origin */
00195   tvec = orig - vert0;
00196
00197   /* calculate U parameter and test bounds */
00198   u = tvec.dot(pvec) *inv_det;
00199
00200   if (u < 0.0 || u > 1.0)
00201     return false;
00202
00203   /* prepare to test V parameter */
00204   qvec = tvec.cross(edge1);
00205
00206   /* calculate V parameter and test bounds */
00207   v = dir.dot(qvec) * inv_det;
00208
00209   if (v < 0.0 || u + v > 1.0)
00210     return false;
00211
00212   /* calculate t, ray intersects triangle */
00213   //t = edge2.dot(qvec) * inv_det;
00214
00215   return true;
00216 };
00217
00218
00222 void NormalQuantifier::subdivide(Vec3f   point1,
00223                                  Vec3f   point2,
00224                                  Vec3f   point3,
00225                                  UInt32  number,
00226                                  UInt32 &index )
00227 {
00228     number--;
00229
00230     if(number == 0)
00231     {
00232         Vec3f newPoint = point1;
00233
00234         newPoint += point2;
00235         newPoint += point3;
00236         newPoint /= 3;
00237
00238         newPoint.normalize();
00239
00240         _normalTable[index] = newPoint;
00241         ++index;
00242     }
00243     else
00244     {
00245         Vec3f newPoint1 = point1;
00246
00247         newPoint1 += point2;
00248         newPoint1 /= 2;
00249         newPoint1.normalize();
00250
00251         Vec3f newPoint2 = point1;
00252
00253         newPoint2 += point3;
00254         newPoint2 /= 2;
00255         newPoint2.normalize();
00256
00257         Vec3f newPoint3 = point2;
00258
00259         newPoint3 += point3;
00260         newPoint3 /= 2;
00261         newPoint3.normalize();
00262
00263         subdivide(point1   , newPoint1, newPoint2, number, index);
00264         subdivide(newPoint1, point2   , newPoint3, number, index);
00265         subdivide(newPoint1, newPoint2, newPoint3, number, index);
00266         subdivide(newPoint2, newPoint3, point3   , number, index);
00267     }
00268 }
00269
00273 UInt32 NormalQuantifier::getSubIndex(Vec3f point,
00274                                      Vec3f point1,
00275                                      Vec3f point2,
00276                                      Vec3f point3,
00277                                      UInt32 number) const
00278 {
00279     int intersect = -1, index = 0;
00280   Vec3f newPoint1(point1);
00281   Vec3f newPoint2(point1);
00282   Vec3f newPoint3(point2);
00283
00284     //newPoint1 = (point1+point2)/2; newPoint1.normalize();
00285     //newPoint2 = (point1+point3)/2; newPoint2.normalize();
00286     //newPoint3 = (point2+point3)/2; newPoint3.normalize();
00287
00288   newPoint1 += point2;
00289   newPoint1 /= 2;
00290   newPoint1.normalize();
00291
00292   newPoint2 += point3;
00293   newPoint2 /=2;
00294   newPoint2.normalize();
00295
00296   newPoint3 += point3;
00297   newPoint3 /= 2;
00298   newPoint3.normalize();
00299
00300     number--;
00301
00302   if (rayTriangle(point, point1, newPoint1, newPoint2))
00303     intersect = 0;
00304   else
00305     if (rayTriangle(point, newPoint1, point2, newPoint3))
00306       intersect = 1;
00307     else
00308       if ( rayTriangle(point, newPoint1, newPoint2, newPoint3))
00309         intersect = 2;
00310       else
00311         if ( rayTriangle(point, newPoint2, newPoint3, point3))
00312           intersect = 3;
00313
00314   if ( intersect >= 0 ) {
00315
00316     index = intersect;
00317
00318     if (number != 0) {
00319
00320       index = index << (number*2);
00321
00322       switch (intersect) {
00323       case 0:
00324         index += getSubIndex(point, point1, newPoint1, newPoint2, number);
00325         break;
00326       case 1:
00327         index += getSubIndex(point, newPoint1, point2, newPoint3, number);
00328         break;
00329       case 2:
00330         index += getSubIndex(point, newPoint1, newPoint2, newPoint3, number);
00331         break;
00332       case 3:
00333         index += getSubIndex(point, newPoint2, newPoint3, point3, number);
00334         break;
00335       }
00336     }
00337   }
00338   else {
00339     FFATAL (( "Intersect < 0 in NormalQuantifier::getSubIndex()\n"));
00340   }
00341
00342   return index;
00343 }
00344
00345 OSG_END_NAMESPACE