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
projectionaxis_better(float axis,float other)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
projectionaxis_for_normal(const Vector3 & normal)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 {
indexremap_tindexremap_t61 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
indexremap_for_projectionaxis(const ProjectionAxis axis)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
WindingWinding111 Winding() : numpoints(0)
112 {
113 }
WindingWinding114 Winding(std::size_t size) : numpoints(0), points(size)
115 {
116 }
resizeWinding117 void resize(std::size_t size)
118 {
119 points.resize(size);
120 numpoints = 0;
121 }
122
beginWinding123 iterator begin()
124 {
125 return points.begin();
126 }
beginWinding127 const_iterator begin() const
128 {
129 return points.begin();
130 }
endWinding131 iterator end()
132 {
133 return points.begin() + numpoints;
134 }
endWinding135 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
push_backWinding151 void push_back(const WindingVertex& point)
152 {
153 points[numpoints] = point;
154 ++numpoints;
155 }
eraseWinding156 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
FixedWindingVertex(const DoubleVector3 & vertex_,const DoubleLine & edge_,std::size_t adjacent_)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
FixedWindingFixedWinding193 FixedWinding()
194 {
195 points.reserve(MAX_POINTS_ON_WINDING);
196 }
197
frontFixedWinding198 FixedWindingVertex& front()
199 {
200 return points.front();
201 }
frontFixedWinding202 const FixedWindingVertex& front() const
203 {
204 return points.front();
205 }
backFixedWinding206 FixedWindingVertex& back()
207 {
208 return points.back();
209 }
backFixedWinding210 const FixedWindingVertex& back() const
211 {
212 return points.back();
213 }
214
clearFixedWinding215 void clear()
216 {
217 points.clear();
218 }
219
push_backFixedWinding220 void push_back(const FixedWindingVertex& point)
221 {
222 points.push_back(point);
223 }
sizeFixedWinding224 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
Winding_forFixedWinding(Winding & winding,const FixedWinding & fixed)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
Winding_wrap(const Winding & winding,std::size_t i)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
Winding_next(const Winding & winding,std::size_t i)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.
Edge_isDegenerate(const Vector3 & x,const Vector3 & y)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 {
brushsplit_tbrushsplit_t284 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
Winding_printConnectivity(Winding & winding)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
323