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 {
  43   return fabs(axis) > fabs(other) + ProjectionAxisEpsilon;
  44 }
  45
  46 /// \brief Texture axis precedence: Z > X > Y
  47 inline ProjectionAxis projectionaxis_for_normal(const Vector3& normal)
  48 {
  49   return (projectionaxis_better(normal[eProjectionAxisY], normal[eProjectionAxisX]))
  50     ? (projectionaxis_better(normal[eProjectionAxisY], normal[eProjectionAxisZ]))
  51       ? eProjectionAxisY
  52       : eProjectionAxisZ
  53     : (projectionaxis_better(normal[eProjectionAxisX], normal[eProjectionAxisZ]))
  54       ? eProjectionAxisX
  55       : eProjectionAxisZ;
  56 }
  57
  58
  59 struct indexremap_t
  60 {
  61   indexremap_t(std::size_t _x, std::size_t _y, std::size_t _z)
  62     : x(_x), y(_y), z(_z)
  63   {
  64   }
  65   std::size_t x, y, z;
  66 };
  67
  68 inline indexremap_t indexremap_for_projectionaxis(const ProjectionAxis axis)
  69 {
  70   switch(axis)
  71   {
  72   case eProjectionAxisX: return indexremap_t(1, 2, 0);
  73   case eProjectionAxisY: return indexremap_t(2, 0, 1);
  74   default: return indexremap_t(0, 1, 2);
  75   }
  76 }
  77
  78 enum PlaneClassification
  79 {
  80   ePlaneFront = 0,
  81   ePlaneBack = 1,
  82   ePlaneOn = 2,
  83 };
  84
  85 #define MAX_POINTS_ON_WINDING 64
  86 const std::size_t c_brush_maxFaces = 1024;
  87
  88
  89 class WindingVertex
  90 {
  91 public:
  92   Vector3 vertex;
  93   Vector2 texcoord;
  94   Vector3 tangent;
  95   Vector3 bitangent;
  96   std::size_t adjacent;
  97 };
  98
  99
 100
 101 struct Winding
 102 {
 103   typedef Array<WindingVertex> container_type;
 104
 105   std::size_t numpoints;
 106   container_type points;
 107
 108   typedef container_type::iterator iterator;
 109   typedef container_type::const_iterator const_iterator;
 110
 111   Winding() : numpoints(0)
 112   {
 113   }
 114   Winding(std::size_t size) : numpoints(0), points(size)
 115   {
 116   }
 117   void resize(std::size_t size)
 118   {
 119     points.resize(size);
 120     numpoints = 0;
 121   }
 122
 123   iterator begin()
 124   {
 125     return points.begin();
 126   }
 127   const_iterator begin() const
 128   {
 129     return points.begin();
 130   }
 131   iterator end()
 132   {
 133     return points.begin() + numpoints;
 134   }
 135   const_iterator end() const
 136   {
 137     return points.begin() + numpoints;
 138   }
 139
 140   WindingVertex& operator[](std::size_t index)
 141   {
 142     ASSERT_MESSAGE(index < points.size(), "winding: index out of bounds");
 143     return points[index];
 144   }
 145   const WindingVertex& operator[](std::size_t index) const
 146   {
 147     ASSERT_MESSAGE(index < points.size(), "winding: index out of bounds");
 148     return points[index];
 149   }
 150
 151   void push_back(const WindingVertex& point)
 152   {
 153     points[numpoints] = point;
 154     ++numpoints;
 155   }
 156   void erase(iterator point)
 157   {
 158     for(iterator i = point + 1; i != end(); point = i, ++i)
 159     {
 160       *point = *i;
 161     }
 162     --numpoints;
 163   }
 164 };
 165
 166 typedef BasicVector3<double> DoubleVector3;
 167
 168 class DoubleLine
 169 {
 170 public:
 171   DoubleVector3 origin;
 172   DoubleVector3 direction;
 173 };
 174
 175 class FixedWindingVertex
 176 {
 177 public:
 178   DoubleVector3 vertex;
 179   DoubleLine edge;
 180   std::size_t adjacent;
 181
 182   FixedWindingVertex(const DoubleVector3& vertex_, const DoubleLine& edge_, std::size_t adjacent_)
 183     : vertex(vertex_), edge(edge_), adjacent(adjacent_)
 184   {
 185   }
 186 };
 187
 188 struct FixedWinding
 189 {
 190   typedef std::vector<FixedWindingVertex> Points;
 191   Points points;
 192
 193   FixedWinding()
 194   {
 195     points.reserve(MAX_POINTS_ON_WINDING);
 196   }
 197
 198   FixedWindingVertex& front()
 199   {
 200     return points.front();
 201   }
 202   const FixedWindingVertex& front() const
 203   {
 204     return points.front();
 205   }
 206   FixedWindingVertex& back()
 207   {
 208     return points.back();
 209   }
 210   const FixedWindingVertex& back() const
 211   {
 212     return points.back();
 213   }
 214
 215   void clear()
 216   {
 217     points.clear();
 218   }
 219
 220   void push_back(const FixedWindingVertex& point)
 221   {
 222     points.push_back(point);
 223   }
 224   std::size_t size() const
 225   {
 226     return points.size();
 227   }
 228
 229   FixedWindingVertex& operator[](std::size_t index)
 230   {
 231     //ASSERT_MESSAGE(index < MAX_POINTS_ON_WINDING, "winding: index out of bounds");
 232     return points[index];
 233   }
 234   const FixedWindingVertex& operator[](std::size_t index) const
 235   {
 236     //ASSERT_MESSAGE(index < MAX_POINTS_ON_WINDING, "winding: index out of bounds");
 237     return points[index];
 238   }
 239
 240 };
 241
 242
 243 inline void Winding_forFixedWinding(Winding& winding, const FixedWinding& fixed)
 244 {
 245   winding.resize(fixed.size());
 246   winding.numpoints = fixed.size();
 247   for(std::size_t i = 0; i < fixed.size(); ++i)
 248   {
 249     winding[i].vertex[0] = static_cast<float>(fixed[i].vertex[0]);
 250     winding[i].vertex[1] = static_cast<float>(fixed[i].vertex[1]);
 251     winding[i].vertex[2] = static_cast<float>(fixed[i].vertex[2]);
 252     winding[i].adjacent = fixed[i].adjacent;
 253   }
 254 }
 255
 256 inline std::size_t Winding_wrap(const Winding& winding, std::size_t i)
 257 {
 258   ASSERT_MESSAGE(winding.numpoints != 0, "Winding_wrap: empty winding");
 259   return i % winding.numpoints;
 260 }
 261
 262 inline std::size_t Winding_next(const Winding& winding, std::size_t i)
 263 {
 264   return Winding_wrap(winding, ++i);
 265 }
 266
 267
 268 class Plane3;
 269
 270 void Winding_createInfinite(FixedWinding& w, const Plane3& plane, double infinity);
 271
 272 const double ON_EPSILON = 1.0 / (1 << 8);
 273
 274 /// \brief Returns true if edge (\p x, \p y) is smaller than the epsilon used to classify winding points against a plane.
 275 inline bool Edge_isDegenerate(const Vector3& x, const Vector3& y)
 276 {
 277   return vector3_length_squared(y - x) < (ON_EPSILON * ON_EPSILON);
 278 }
 279
 280 void Winding_Clip(const FixedWinding& winding, const Plane3& plane, const Plane3& clipPlane, std::size_t adjacent, FixedWinding& clipped);
 281
 282 struct brushsplit_t
 283 {
 284   brushsplit_t()
 285   {
 286     counts[0] = 0;
 287     counts[1] = 0;
 288     counts[2] = 0;
 289   }
 290   brushsplit_t& operator+=(const brushsplit_t& other)
 291   {
 292     counts[0] += other.counts[0];
 293     counts[1] += other.counts[1];
 294     counts[2] += other.counts[2];
 295     return *this;
 296   }
 297   std::size_t counts[3];
 298 };
 299
 300 brushsplit_t Winding_ClassifyPlane(const Winding& w, const Plane3& plane);
 301
 302 bool Winding_PlanesConcave(const Winding& w1, const Winding& w2, const Plane3& plane1, const Plane3& plane2);
 303 bool Winding_TestPlane(const Winding& w, const Plane3& plane, bool flipped);
 304
 305 std::size_t Winding_FindAdjacent(const Winding& w, std::size_t face);
 306
 307 std::size_t Winding_Opposite(const Winding& w, const std::size_t index, const std::size_t other);
 308 std::size_t Winding_Opposite(const Winding& w, std::size_t index);
 309
 310 void Winding_Centroid(const Winding& w, const Plane3& plane, Vector3& centroid);
 311
 312
 313 inline void Winding_printConnectivity(Winding& winding)
 314 {
 315   for(Winding::iterator i = winding.begin(); i != winding.end(); ++i)
 316   {
 317     std::size_t vertexIndex = std::distance(winding.begin(), i);
 318     globalOutputStream() << "vertex: " << Unsigned(vertexIndex) << " adjacent: " << Unsigned((*i).adjacent) << "\n";
 319   }
 320 }
 321
 322 #endif