radiant/winding.h

   1 /*
   2    Copyright (C) 1999-2006 Id Software, Inc. and contributors.
   3    For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5    This file is part of GtkRadiant.
   6
   7    GtkRadiant is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2 of the License, or
  10    (at your option) any later version.
  11
  12    GtkRadiant is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GtkRadiant; if not, write to the Free Software
  19    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20  */
  21
  22 #if !defined( INCLUDED_WINDING_H )
  23 #define INCLUDED_WINDING_H
  24
  25 #include "debugging/debugging.h"
  26
  27 #include <vector>
  28
  29 #include "math/vector.h"
  30 #include "container/array.h"
  31
  32 enum ProjectionAxis
  33 {
  34         eProjectionAxisX = 0,
  35         eProjectionAxisY = 1,
  36         eProjectionAxisZ = 2,
  37 };
  38
  39 const float ProjectionAxisEpsilon = static_cast<float>( 0.0001 );
  40
  41 inline bool projectionaxis_better( float axis, float other ){
  42         return fabs( axis ) > fabs( other ) + ProjectionAxisEpsilon;
  43 }
  44
  45 /// \brief Texture axis precedence: Z > X > Y
  46 inline ProjectionAxis projectionaxis_for_normal( const Vector3& normal ){
  47         return ( projectionaxis_better( normal[eProjectionAxisY], normal[eProjectionAxisX] ) )
  48                    ? ( projectionaxis_better( normal[eProjectionAxisY], normal[eProjectionAxisZ] ) )
  49                    ? eProjectionAxisY
  50                    : eProjectionAxisZ
  51                    : ( projectionaxis_better( normal[eProjectionAxisX], normal[eProjectionAxisZ] ) )
  52                    ? eProjectionAxisX
  53                    : eProjectionAxisZ;
  54 }
  55
  56
  57 struct indexremap_t
  58 {
  59         indexremap_t( std::size_t _x, std::size_t _y, std::size_t _z )
  60                 : x( _x ), y( _y ), z( _z ){
  61         }
  62         std::size_t x, y, z;
  63 };
  64
  65 inline indexremap_t indexremap_for_projectionaxis( const ProjectionAxis axis ){
  66         switch ( axis )
  67         {
  68         case eProjectionAxisX: return indexremap_t( 1, 2, 0 );
  69         case eProjectionAxisY: return indexremap_t( 2, 0, 1 );
  70         default: return indexremap_t( 0, 1, 2 );
  71         }
  72 }
  73
  74 enum PlaneClassification
  75 {
  76         ePlaneFront = 0,
  77         ePlaneBack = 1,
  78         ePlaneOn = 2,
  79 };
  80
  81 #define MAX_POINTS_ON_WINDING 64
  82 const std::size_t c_brush_maxFaces = 1024;
  83
  84
  85 class WindingVertex
  86 {
  87 public:
  88 Vector3 vertex;
  89 Vector2 texcoord;
  90 Vector3 tangent;
  91 Vector3 bitangent;
  92 std::size_t adjacent;
  93 };
  94
  95
  96
  97 struct Winding
  98 {
  99         typedef Array<WindingVertex> container_type;
 100
 101         std::size_t numpoints;
 102         container_type points;
 103
 104         typedef container_type::iterator iterator;
 105         typedef container_type::const_iterator const_iterator;
 106
 107         Winding() : numpoints( 0 ){
 108         }
 109         Winding( std::size_t size ) : numpoints( 0 ), points( size ){
 110         }
 111         void resize( std::size_t size ){
 112                 points.resize( size );
 113                 numpoints = 0;
 114         }
 115
 116         iterator begin(){
 117                 return points.begin();
 118         }
 119         const_iterator begin() const {
 120                 return points.begin();
 121         }
 122         iterator end(){
 123                 return points.begin() + numpoints;
 124         }
 125         const_iterator end() const {
 126                 return points.begin() + numpoints;
 127         }
 128
 129         WindingVertex& operator[]( std::size_t index ){
 130                 ASSERT_MESSAGE( index < points.size(), "winding: index out of bounds" );
 131                 return points[index];
 132         }
 133         const WindingVertex& operator[]( std::size_t index ) const {
 134                 ASSERT_MESSAGE( index < points.size(), "winding: index out of bounds" );
 135                 return points[index];
 136         }
 137
 138         void push_back( const WindingVertex& point ){
 139                 points[numpoints] = point;
 140                 ++numpoints;
 141         }
 142         void erase( iterator point ){
 143                 for ( iterator i = point + 1; i != end(); point = i, ++i )
 144                 {
 145                         *point = *i;
 146                 }
 147                 --numpoints;
 148         }
 149 };
 150
 151 typedef BasicVector3<double> DoubleVector3;
 152
 153 class DoubleLine
 154 {
 155 public:
 156 DoubleVector3 origin;
 157 DoubleVector3 direction;
 158 };
 159
 160 class FixedWindingVertex
 161 {
 162 public:
 163 DoubleVector3 vertex;
 164 DoubleLine edge;
 165 std::size_t adjacent;
 166
 167 FixedWindingVertex( const DoubleVector3& vertex_, const DoubleLine& edge_, std::size_t adjacent_ )
 168         : vertex( vertex_ ), edge( edge_ ), adjacent( adjacent_ ){
 169 }
 170 };
 171
 172 struct FixedWinding
 173 {
 174         typedef std::vector<FixedWindingVertex> Points;
 175         Points points;
 176
 177         FixedWinding(){
 178                 points.reserve( MAX_POINTS_ON_WINDING );
 179         }
 180
 181         FixedWindingVertex& front(){
 182                 return points.front();
 183         }
 184         const FixedWindingVertex& front() const {
 185                 return points.front();
 186         }
 187         FixedWindingVertex& back(){
 188                 return points.back();
 189         }
 190         const FixedWindingVertex& back() const {
 191                 return points.back();
 192         }
 193
 194         void clear(){
 195                 points.clear();
 196         }
 197
 198         void push_back( const FixedWindingVertex& point ){
 199                 points.push_back( point );
 200         }
 201         std::size_t size() const {
 202                 return points.size();
 203         }
 204
 205         FixedWindingVertex& operator[]( std::size_t index ){
 206                 //ASSERT_MESSAGE(index < MAX_POINTS_ON_WINDING, "winding: index out of bounds");
 207                 return points[index];
 208         }
 209         const FixedWindingVertex& operator[]( std::size_t index ) const {
 210                 //ASSERT_MESSAGE(index < MAX_POINTS_ON_WINDING, "winding: index out of bounds");
 211                 return points[index];
 212         }
 213
 214 };
 215
 216
 217 inline void Winding_forFixedWinding( Winding& winding, const FixedWinding& fixed ){
 218         winding.resize( fixed.size() );
 219         winding.numpoints = fixed.size();
 220         for ( std::size_t i = 0; i < fixed.size(); ++i )
 221         {
 222                 winding[i].vertex[0] = static_cast<float>( fixed[i].vertex[0] );
 223                 winding[i].vertex[1] = static_cast<float>( fixed[i].vertex[1] );
 224                 winding[i].vertex[2] = static_cast<float>( fixed[i].vertex[2] );
 225                 winding[i].adjacent = fixed[i].adjacent;
 226         }
 227 }
 228
 229 inline std::size_t Winding_wrap( const Winding& winding, std::size_t i ){
 230         ASSERT_MESSAGE( winding.numpoints != 0, "Winding_wrap: empty winding" );
 231         return i % winding.numpoints;
 232 }
 233
 234 inline std::size_t Winding_next( const Winding& winding, std::size_t i ){
 235         return Winding_wrap( winding, ++i );
 236 }
 237
 238
 239 class Plane3;
 240
 241 void Winding_createInfinite( FixedWinding& w, const Plane3& plane, double infinity );
 242
 243 const double ON_EPSILON = 1.0 / ( 1 << 8 );
 244
 245 /// \brief Returns true if edge (\p x, \p y) is smaller than the epsilon used to classify winding points against a plane.
 246 inline bool Edge_isDegenerate( const Vector3& x, const Vector3& y ){
 247         return vector3_length_squared( y - x ) < ( ON_EPSILON * ON_EPSILON );
 248 }
 249
 250 void Winding_Clip( const FixedWinding& winding, const Plane3& plane, const Plane3& clipPlane, std::size_t adjacent, FixedWinding& clipped );
 251
 252 struct brushsplit_t
 253 {
 254         brushsplit_t(){
 255                 counts[0] = 0;
 256                 counts[1] = 0;
 257                 counts[2] = 0;
 258         }
 259         brushsplit_t& operator+=( const brushsplit_t& other ){
 260                 counts[0] += other.counts[0];
 261                 counts[1] += other.counts[1];
 262                 counts[2] += other.counts[2];
 263                 return *this;
 264         }
 265         std::size_t counts[3];
 266 };
 267
 268 brushsplit_t Winding_ClassifyPlane( const Winding& w, const Plane3& plane );
 269
 270 bool Winding_PlanesConcave( const Winding& w1, const Winding& w2, const Plane3& plane1, const Plane3& plane2 );
 271 bool Winding_TestPlane( const Winding& w, const Plane3& plane, bool flipped );
 272
 273 std::size_t Winding_FindAdjacent( const Winding& w, std::size_t face );
 274
 275 std::size_t Winding_Opposite( const Winding& w, const std::size_t index, const std::size_t other );
 276 std::size_t Winding_Opposite( const Winding& w, std::size_t index );
 277
 278 void Winding_Centroid( const Winding& w, const Plane3& plane, Vector3& centroid );
 279
 280
 281 inline void Winding_printConnectivity( Winding& winding ){
 282         for ( Winding::iterator i = winding.begin(); i != winding.end(); ++i )
 283         {
 284                 std::size_t vertexIndex = std::distance( winding.begin(), i );
 285                 globalOutputStream() << "vertex: " << Unsigned( vertexIndex ) << " adjacent: " << Unsigned( ( *i ).adjacent ) << "\n";
 286         }
 287 }
 288
 289 #endif