2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
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.
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.
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
22 #if !defined( INCLUDED_WINDING_H )
23 #define INCLUDED_WINDING_H
25 #include "debugging/debugging.h"
29 #include "math/vector.h"
30 #include "container/array.h"
39 const float ProjectionAxisEpsilon = static_cast<float>( 0.0001 );
41 inline bool projectionaxis_better( float axis, float other ){
42 return fabs( axis ) > fabs( other ) + ProjectionAxisEpsilon;
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] ) )
51 : ( projectionaxis_better( normal[eProjectionAxisX], normal[eProjectionAxisZ] ) )
59 indexremap_t( std::size_t _x, std::size_t _y, std::size_t _z )
60 : x( _x ), y( _y ), z( _z ){
65 inline indexremap_t indexremap_for_projectionaxis( const ProjectionAxis axis ){
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 );
74 enum PlaneClassification
81 #define MAX_POINTS_ON_WINDING 64
82 const std::size_t c_brush_maxFaces = 1024;
99 typedef Array<WindingVertex> container_type;
101 std::size_t numpoints;
102 container_type points;
104 typedef container_type::iterator iterator;
105 typedef container_type::const_iterator const_iterator;
107 Winding() : numpoints( 0 ){
109 Winding( std::size_t size ) : numpoints( 0 ), points( size ){
111 void resize( std::size_t size ){
112 points.resize( size );
117 return points.begin();
119 const_iterator begin() const {
120 return points.begin();
123 return points.begin() + numpoints;
125 const_iterator end() const {
126 return points.begin() + numpoints;
129 WindingVertex& operator[]( std::size_t index ){
130 ASSERT_MESSAGE( index < points.size(), "winding: index out of bounds" );
131 return points[index];
133 const WindingVertex& operator[]( std::size_t index ) const {
134 ASSERT_MESSAGE( index < points.size(), "winding: index out of bounds" );
135 return points[index];
138 void push_back( const WindingVertex& point ){
139 points[numpoints] = point;
142 void erase( iterator point ){
143 for ( iterator i = point + 1; i != end(); point = i, ++i )
151 typedef BasicVector3<double> DoubleVector3;
156 DoubleVector3 origin;
157 DoubleVector3 direction;
160 class FixedWindingVertex
163 DoubleVector3 vertex;
165 std::size_t adjacent;
167 FixedWindingVertex( const DoubleVector3& vertex_, const DoubleLine& edge_, std::size_t adjacent_ )
168 : vertex( vertex_ ), edge( edge_ ), adjacent( adjacent_ ){
174 typedef std::vector<FixedWindingVertex> Points;
178 points.reserve( MAX_POINTS_ON_WINDING );
181 FixedWindingVertex& front(){
182 return points.front();
184 const FixedWindingVertex& front() const {
185 return points.front();
187 FixedWindingVertex& back(){
188 return points.back();
190 const FixedWindingVertex& back() const {
191 return points.back();
198 void push_back( const FixedWindingVertex& point ){
199 points.push_back( point );
201 std::size_t size() const {
202 return points.size();
205 FixedWindingVertex& operator[]( std::size_t index ){
206 //ASSERT_MESSAGE(index < MAX_POINTS_ON_WINDING, "winding: index out of bounds");
207 return points[index];
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];
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 )
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;
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;
234 inline std::size_t Winding_next( const Winding& winding, std::size_t i ){
235 return Winding_wrap( winding, ++i );
241 void Winding_createInfinite( FixedWinding& w, const Plane3& plane, double infinity );
243 const double ON_EPSILON = 1.0 / ( 1 << 8 );
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 );
250 void Winding_Clip( const FixedWinding& winding, const Plane3& plane, const Plane3& clipPlane, std::size_t adjacent, FixedWinding& clipped );
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];
265 std::size_t counts[3];
268 brushsplit_t Winding_ClassifyPlane( const Winding& w, const Plane3& plane );
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 );
273 std::size_t Winding_FindAdjacent( const Winding& w, std::size_t face );
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 );
278 void Winding_Centroid( const Winding& w, const Plane3& plane, Vector3& centroid );
281 inline void Winding_printConnectivity( Winding& winding ){
282 for ( Winding::iterator i = winding.begin(); i != winding.end(); ++i )
284 std::size_t vertexIndex = std::distance( winding.begin(), i );
285 globalOutputStream() << "vertex: " << Unsigned( vertexIndex ) << " adjacent: " << Unsigned( ( *i ).adjacent ) << "\n";