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