src/triSurface/faceTriangulation/faceTriangulation.H

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   4    \\    /   O peration     |
   5     \\  /    A nd           | Copyright (C) 1991-2008 OpenCFD Ltd.
   6      \\/     M anipulation  |
   7 -------------------------------------------------------------------------------
   8 License
   9     This file is part of OpenFOAM.
  10
  11     OpenFOAM is free software; you can redistribute it and/or modify it
  12     under the terms of the GNU General Public License as published by the
  13     Free Software Foundation; either version 2 of the License, or (at your
  14     option) any later version.
  15
  16     OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
  17     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19     for more details.
  20
  21     You should have received a copy of the GNU General Public License
  22     along with OpenFOAM; if not, write to the Free Software Foundation,
  23     Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  24
  25 Class
  26     Foam::faceTriangulation
  27
  28 Description
  29     Triangulation of faces. Handles concave polygons as well
  30     (inefficiently)
  31
  32     Works by trying to subdivide the face at the vertex with 'flattest'
  33     internal angle (i.e. closest to 180 deg).
  34
  35     Based on routine 'Diagonal' in
  36     @verbatim
  37         "Efficient Triangulation of Simple Polygons"
  38         Godfried Toussaint, McGill University.
  39     @endverbatim
  40
  41     After construction is the list of triangles the face is decomposed into.
  42     (Or empty list if no valid triangulation could be found).
  43
  44
  45 SourceFiles
  46     faceTriangulation.C
  47
  48 \*---------------------------------------------------------------------------*/
  49
  50 #ifndef faceTriangulation_H
  51 #define faceTriangulation_H
  52
  53 #include "triFaceList.H"
  54 #include "pointField.H"
  55
  56 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
  57
  58 namespace Foam
  59 {
  60
  61 // Forward declaration of classes
  62
  63 /*---------------------------------------------------------------------------*\
  64                            Class faceTriangulation Declaration
  65 \*---------------------------------------------------------------------------*/
  66
  67 class faceTriangulation
  68 :
  69     public triFaceList
  70 {
  71     // Static Data
  72
  73         //- Relative tolerance on edge.
  74         static const scalar edgeRelTol;
  75
  76
  77     // Static Member Functions
  78
  79         //- Edge to the right of face vertex i
  80         static label right(const label size, label i);
  81
  82         //- Edge to the left of face vertex i
  83         static label left(const label size, label i);
  84
  85         //- Calculate normalized edge vectors
  86         static tmp<vectorField> calcEdges(const face&, const pointField&);
  87
  88         //- Calculates half angle components of angle from e0 to e1
  89         //  in plane given by normal.
  90         static void calcHalfAngle
  91         (
  92             const vector& normal,
  93             const vector& e0,
  94             const vector& e1,
  95             scalar& cosHalfAngle,
  96             scalar& sinHalfAngle
  97         );
  98
  99         //- Calculate intersection point between edge p1-p2 and ray (in 2D).
 100         // Return true and intersection point if intersection between p1 and p2.
 101         static pointHit rayEdgeIntersect
 102         (
 103             const vector& normal,
 104             const point& rayOrigin,
 105             const vector& rayDir,
 106             const point& p1,
 107             const point& p2,
 108             scalar& posOnEdge
 109         );
 110
 111         // Return true if triangle given its three points
 112         // (anticlockwise ordered) contains point
 113         static bool triangleContainsPoint
 114         (
 115             const vector& n,
 116             const point& p0,
 117             const point& p1,
 118             const point& p2,
 119             const point& pt
 120         );
 121
 122         //- Starting from startIndex find diagonal. Return in index1, index2.
 123         //  Index1 always startIndex except when convex polygon
 124         static void findDiagonal
 125         (
 126             const pointField& points,
 127             const face& f,
 128             const vectorField& edges,
 129             const vector& normal,
 130             const label startIndex,
 131             label& index1,
 132             label& index2
 133         );
 134
 135         //- Find label of vertex to start splitting from. This will be the
 136         //  vertex with edge angle:
 137         //     1] flattest concave angle
 138         //     2] flattest convex angle if no concave angles.
 139         static label findStart
 140         (
 141             const face& f,
 142             const vectorField& edges,
 143             const vector& normal
 144         );
 145
 146
 147     // Private Member Functions
 148
 149         //- Split face f into triangles. Handles all simple (convex & concave)
 150         //  polygons. Returns false if could not produce valid split.
 151         bool split
 152         (
 153             const bool fallBack,
 154             const pointField& points,
 155             const face& f,
 156             const vector& normal,
 157             label& triI
 158         );
 159
 160 public:
 161
 162     // Constructors
 163
 164         //- Construct null
 165         faceTriangulation();
 166
 167         //- Construct from face and points. Decomposition based on average
 168         //  normal. After construction *this is size 0 or holds the triangles.
 169         //  If fallBack and triangulation fails does naive triangulation
 170         //  and never returns 0 size.
 171         faceTriangulation
 172         (
 173             const pointField& points,
 174             const face& f,
 175             const bool fallBack = false
 176         );
 177
 178         //- Construct from face and points and user supplied (unit) normal.
 179         //  After construction *this is size 0 or holds the triangles.
 180         //  If fallBack and triangulation fails does naive triangulation
 181         //  and never returns 0 size.
 182         faceTriangulation
 183         (
 184             const pointField& points,
 185             const face& f,
 186             const vector& n,
 187             const bool fallBack = false
 188         );
 189
 190         //- Construct from Istream
 191         faceTriangulation(Istream&);
 192 };
 193
 194
 195 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 196
 197 } // End namespace Foam
 198
 199 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 200
 201 #endif
 202
 203 // ************************************************************************* //