Algorithms.hh

00001 /*===========================================================================*\
00002  *                                                                           *
00003  *                              OpenFlipper                                  *
00004  *      Copyright (C) 2001-2011 by Computer Graphics Group, RWTH Aachen      *
00005  *                           www.openflipper.org                             *
00006  *                                                                           *
00007  *---------------------------------------------------------------------------*
00008  *  This file is part of OpenFlipper.                                        *
00009  *                                                                           *
00010  *  OpenFlipper is free software: you can redistribute it and/or modify      *
00011  *  it under the terms of the GNU Lesser General Public License as           *
00012  *  published by the Free Software Foundation, either version 3 of           *
00013  *  the License, or (at your option) any later version with the              *
00014  *  following exceptions:                                                    *
00015  *                                                                           *
00016  *  If other files instantiate templates or use macros                       *
00017  *  or inline functions from this file, or you compile this file and         *
00018  *  link it with other files to produce an executable, this file does        *
00019  *  not by itself cause the resulting executable to be covered by the        *
00020  *  GNU Lesser General Public License. This exception does not however       *
00021  *  invalidate any other reasons why the executable file might be            *
00022  *  covered by the GNU Lesser General Public License.                        *
00023  *                                                                           *
00024  *  OpenFlipper is distributed in the hope that it will be useful,           *
00025  *  but WITHOUT ANY WARRANTY; without even the implied warranty of           *
00026  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
00027  *  GNU Lesser General Public License for more details.                      *
00028  *                                                                           *
00029  *  You should have received a copy of the GNU LesserGeneral Public          *
00030  *  License along with OpenFlipper. If not,                                  *
00031  *  see <http://www.gnu.org/licenses/>.                                      *
00032  *                                                                           *
00033 \*===========================================================================*/
00034 
00035 /*===========================================================================*\
00036  *                                                                           *
00037  *   $Revision: 10745 $                                                       *
00038  *   $Author: moebius $                                                      *
00039  *   $Date: 2011-01-26 10:23:50 +0100 (Mi, 26 Jan 2011) $                   *
00040  *                                                                           *
00041 \*===========================================================================*/
00042 
00043 
00044 
00045 
00046 #ifndef GEO_ALGORITHMS_HH
00047 #define GEO_ALGORITHMS_HH
00048 
00049 
00050 //== INCLUDES =================================================================
00051 
00052 #include <float.h>
00053 #include "../Math/VectorT.hh"
00054 
00055 
00056 namespace ACG {
00057 namespace Geometry {
00058 
00059 
00060 //== 3D STUFF =================================================================
00061 
00062  
00063 
00065 template<typename Scalar>
00066 bool
00067 circumCenter( const VectorT<Scalar,3>&  _v0,
00068               const VectorT<Scalar,3>&  _v1,
00069               const VectorT<Scalar,3>&  _v2,
00070               const VectorT<Scalar,3>&  _v3,
00071               VectorT<Scalar,3>&        _result );
00072 
00073 
00075 template<typename Scalar>
00076 Scalar
00077 circumRadiusSquared( const VectorT<Scalar,3>&  _v0,
00078                      const VectorT<Scalar,3>&  _v1,
00079                      const VectorT<Scalar,3>&  _v2,
00080                      const VectorT<Scalar,3>&  _v3 )
00081 {
00082   VectorT<Scalar,3> cc;
00083   return circumCenter(_v0, _v1, _v2, _v3, cc) ? (cc-_v0).sqrnorm() : FLT_MAX;
00084 }
00085 
00086 
00088 template<typename Scalar>
00089 Scalar
00090 circumRadius( const VectorT<Scalar,3>&  _v0,
00091               const VectorT<Scalar,3>&  _v1,
00092               const VectorT<Scalar,3>&  _v2,
00093               const VectorT<Scalar,3>&  _v3 )
00094 {
00095   return sqrt(circumRadiusSquared(_v0, _v1, _v2, _v3));
00096 }
00097 
00098 
00100 template <typename Scalar>
00101 VectorT<Scalar,3>
00102 perpendicular( const VectorT<Scalar,3>&  _v );
00103 
00104 
00119 template<typename Vec>
00120 bool
00121 triangleIntersection( const Vec&  _o,
00122                       const Vec&  _dir,
00123                       const Vec&  _v0,
00124                       const Vec&  _v1,
00125                       const Vec&  _v2,
00126                       typename Vec::value_type& _t,
00127                       typename Vec::value_type& _u,
00128                       typename Vec::value_type& _v );
00129       
00130 
00142 template<typename Vec>
00143 bool
00144 axisAlignedBBIntersection( const Vec&  _o,
00145                   const Vec&  _dir,
00146                   const Vec& _bbmin,
00147                   const Vec& _bbmax,
00148                   typename Vec::value_type& _t0,
00149                   typename Vec::value_type& _t1 );
00150 
00151 
00152 //== 2D STUFF =================================================================
00153 
00155 template<typename Scalar>
00156 Scalar
00157 pointLineOrientation( const VectorT<Scalar,2>&  _p,
00158                       const VectorT<Scalar,2>&  _v0,
00159                       const VectorT<Scalar,2>&  _v1 )
00160 {
00161   VectorT<Scalar,2> d1(_p-_v0), d2(_v1-_v0);
00162   return (d1[0]*d2[1]-d1[1]*d2[0]);
00163 }
00164 
00165 
00167 template<typename Scalar>
00168 bool
00169 isCCW( const VectorT<Scalar,2>&  _v0,
00170        const VectorT<Scalar,2>&  _v1,
00171        const VectorT<Scalar,2>&  _v2 )
00172 {
00173   return ( pointLineOrientation(_v0, _v1, _v2) < Scalar(0.0) );
00174 }
00175 
00176 
00178 template<typename Scalar>
00179 bool
00180 isCW( const VectorT<Scalar,2>&  _v0,
00181       const VectorT<Scalar,2>&  _v1,
00182       const VectorT<Scalar,2>&  _v2 )
00183 {
00184   return ( pointLineOrientation(_v0, _v1, _v2) > Scalar(0.0) );
00185 }
00186 
00187 
00189 template<typename Scalar>
00190 bool
00191 lineIntersection( const VectorT<Scalar,2>&  _v0,
00192                   const VectorT<Scalar,2>&  _v1,
00193                   const VectorT<Scalar,2>&  _v2,
00194                   const VectorT<Scalar,2>&  _v3,
00195                   Scalar& _t1,
00196                   Scalar& _t2 );
00197 
00198 
00199 //===========================================================================
00202 //===========================================================================     
00203 
00205 template<class Vec>
00206 typename Vec::value_type
00207 distPointLine( const Vec& _p,
00208                const Vec& _v0,
00209                const Vec& _v1,
00210                Vec*       _min_v=0 )
00211 { return sqrt(distPointLineSquared(_p, _v0, _v1, _min_v)); }
00212 
00213 
00215 template<class Vec>
00216 typename Vec::value_type
00217 distPointLineSquared( const Vec& _p,
00218                       const Vec& _v0,
00219                       const Vec& _v1,
00220                       Vec*       _min_v=0);
00221 
00223 template <class Vec>
00224 typename Vec::value_type
00225 distPointTriangle( const Vec& _p,
00226                    const Vec& _v0,
00227                    const Vec& _v1,
00228                    const Vec& _v2,
00229                    Vec& _nearestPoint )
00230 { return sqrt(distPointTriangleSquared(_p, _v0, _v1, _v2, _nearestPoint)); }
00231 
00232 
00234 template <class Vec>
00235 typename Vec::value_type
00236 distPointTriangleSquared( const Vec& _p,
00237                           const Vec& _v0,
00238                           const Vec& _v1,
00239                           const Vec& _v2,
00240                           Vec& _nearestPoint );
00241                           
00250 template < typename VectorT , typename ValueT >
00251 inline
00252 ValueT 
00253 distPointPlane(const VectorT& _porigin, 
00254                const VectorT& _pnormal, 
00255                const VectorT&  _point);                          
00256 
00257           
00260 //===========================================================================
00263 //===========================================================================                             
00264                           
00266 template<typename Scalar>
00267 Scalar
00268 distLineLineSquared( const VectorT<Scalar,3>& _v00,
00269                      const VectorT<Scalar,3>& _v01,
00270                      const VectorT<Scalar,3>& _v10,
00271                      const VectorT<Scalar,3>& _v11,
00272                      VectorT<Scalar,3>*       _min_v0=0,
00273                      VectorT<Scalar,3>*       _min_v1=0,
00274                      bool                          _fastApprox=false );
00275 
00276 
00278 template<typename Scalar>
00279 Scalar
00280 distLineLine( const VectorT<Scalar,3>& _v00,
00281               const VectorT<Scalar,3>& _v01,
00282               const VectorT<Scalar,3>& _v10,
00283               const VectorT<Scalar,3>& _v11,
00284               VectorT<Scalar,3>*       _min_v0=0,
00285               VectorT<Scalar,3>*       _min_v1=0 )
00286 {
00287   return sqrt(distLineLineSquared(_v00, _v01, _v10, _v11,
00288                                   _min_v0, _min_v1));
00289 }
00290 
00294 //===========================================================================
00297 //===========================================================================      
00298 
00299 
00306 template < typename VectorT >
00307 VectorT projectToEdge(const VectorT& _start , 
00308                       const VectorT& _end , 
00309                       const VectorT& _point );
00310                       
00311                       
00318 template < typename VectorT >
00319 inline
00320 VectorT
00321 projectToPlane(const VectorT& _porigin, 
00322                const VectorT& _pnormal, 
00323                const VectorT&  _point);                      
00324               
00327 //===========================================================================
00330 //===========================================================================   
00331 
00336 
00337 template<typename Scalar>
00338 bool
00339 baryCoord( const VectorT<Scalar,2>&  _p,
00340            const VectorT<Scalar,2>&  _u,
00341            const VectorT<Scalar,2>&  _v,
00342            const VectorT<Scalar,2>&  _w,
00343            VectorT<Scalar,3>&        _result );
00344            
00345 
00347 template<typename Scalar>
00348 bool
00349 isInTriangle( const VectorT<Scalar,2>&  _p,
00350               const VectorT<Scalar,2>&  _u,
00351               const VectorT<Scalar,2>&  _v,
00352               const VectorT<Scalar,2>&  _w )
00353 {
00354   VectorT<Scalar,3> bary;
00355   if (baryCoord(_p, _u, _v, _w, bary)) 
00356     return ((bary[0]>0.0) && (bary[1]>0.0) && (bary[2]>0.0));
00357   else {
00358     std::cerr << "point in triangle error\n";
00359     return false;
00360   }
00361 }
00362 
00363 template<typename Scalar>
00364 bool
00365 circumCenter( const VectorT<Scalar,2>&  _v0,
00366               const VectorT<Scalar,2>&  _v1,
00367               const VectorT<Scalar,2>&  _v2,
00368               VectorT<Scalar,2>&        _result );
00369 
00372 //===========================================================================
00375 //===========================================================================  
00376  
00379 template<typename Scalar>
00380 bool
00381 baryCoord( const VectorT<Scalar,3>&  _p,
00382            const VectorT<Scalar,3>&  _u,
00383            const VectorT<Scalar,3>&  _v,
00384            const VectorT<Scalar,3>&  _w,
00385            VectorT<Scalar,3>&        _result );
00386 
00387 
00389 template<typename Scalar>
00390 bool
00391 minSphere(const VectorT<Scalar,3>&  _v0,
00392           const VectorT<Scalar,3>&  _v1,
00393           const VectorT<Scalar,3>&  _v2,
00394           VectorT<Scalar,3>&        _center,
00395           Scalar&                   _radius);
00396 
00397 
00399 template<typename Scalar>
00400 Scalar
00401 minRadiusSquared( const VectorT<Scalar,3>&  _v0,
00402                   const VectorT<Scalar,3>&  _v1,
00403                   const VectorT<Scalar,3>&  _v2 );
00404 
00405   
00407 template<typename Scalar>
00408 Scalar
00409 minRadius( const VectorT<Scalar,3>&  _v0,
00410            const VectorT<Scalar,3>&  _v1,
00411            const VectorT<Scalar,3>&  _v2 )
00412 {
00413   return sqrt(minRadiusSquared(_v0, _v1, _v2));
00414 }
00415 
00416 
00418 template<typename Scalar>
00419 bool
00420 circumCenter( const VectorT<Scalar,3>&  _v0,
00421               const VectorT<Scalar,3>&  _v1,
00422               const VectorT<Scalar,3>&  _v2,
00423               VectorT<Scalar,3>&        _result );
00424 
00425 
00427 template<typename Scalar>
00428 Scalar
00429 circumRadiusSquared( const VectorT<Scalar,3>&  _v0,
00430                      const VectorT<Scalar,3>&  _v1,
00431                      const VectorT<Scalar,3>&  _v2 );
00432 
00433 
00435 template<typename Scalar>
00436 Scalar
00437 circumRadius( const VectorT<Scalar,3>&  _v0,
00438               const VectorT<Scalar,3>&  _v1,
00439               const VectorT<Scalar,3>&  _v2 )
00440 {
00441   return sqrt(circumRadiusSquared(_v0, _v1, _v2));
00442 }
00443 
00451 template<class VectorT>
00452 int isObtuse(const VectorT& _p0,
00453              const VectorT& _p1,
00454              const VectorT& _p2 );
00455 
00458 //===========================================================================
00461 //===========================================================================   
00462 
00463 
00467 template <class Vec>
00468 typename Vec::value_type
00469 triangleArea( const Vec& _v0,
00470               const Vec& _v1,
00471               const Vec& _v2 )
00472 {
00473   return sqrt(triangleAreaSquared(_v0,_v1,_v2));
00474 }
00475   
00476 
00480 template <class Vec>
00481 typename Vec::value_type
00482 triangleAreaSquared( const Vec& _v0,
00483                      const Vec& _v1,
00484                      const Vec& _v2 );
00485 
00486 
00487 
00491 template <typename Scalar, int N>
00492 Scalar
00493 aspectRatio( const VectorT<Scalar, N>& _v0,
00494              const VectorT<Scalar, N>& _v1,
00495              const VectorT<Scalar, N>& _v2 );
00496 
00500 template <typename Scalar, int N>
00501 Scalar
00502 roundness( const VectorT<Scalar, N>& _v0,
00503            const VectorT<Scalar, N>& _v1,
00504            const VectorT<Scalar, N>& _v2 );
00505 
00508 //=============================================================================
00509 } // namespace Geometry
00510 } // namespace ACG
00511 //=============================================================================
00512 #if defined(INCLUDE_TEMPLATES) && !defined(GEO_ALGORITHMS_C)
00513 #define GEO_ALGORITHMS_TEMPLATES
00514 #include "Algorithms.cc"
00515 #endif
00516 //=============================================================================
00517 #endif // GEO_ALGORITHMS_HH defined
00518 //=============================================================================
00519