winding.h

Go to the documentation of this file.

/*
 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
 For a list of contributors, see the accompanying CONTRIBUTORS file.

 This file is part of GtkRadiant.

 GtkRadiant is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or
 (at your option) any later version.

 GtkRadiant is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with GtkRadiant; if not, write to the Free Software
 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

#if !defined(INCLUDED_WINDING_H)
#define INCLUDED_WINDING_H

#include "debugging/debugging.h"
#include "shared.h"

#include <vector>

#include "math/Vector2.h"
#include "math/Vector3.h"
#include "container/array.h"

enum ProjectionAxis
{
    eProjectionAxisX = 0, eProjectionAxisY = 1, eProjectionAxisZ = 2,
};

const float ProjectionAxisEpsilon = static_cast<float> (0.0001);

inline bool projectionaxis_better (float axis, float other)
{
    return fabs(axis) > fabs(other) + ProjectionAxisEpsilon;
}

inline ProjectionAxis projectionaxis_for_normal (const Vector3& normal)
{
    return (projectionaxis_better(normal[eProjectionAxisY], normal[eProjectionAxisX])) ? (projectionaxis_better(
            normal[eProjectionAxisY], normal[eProjectionAxisZ])) ? eProjectionAxisY : eProjectionAxisZ
            : (projectionaxis_better(normal[eProjectionAxisX], normal[eProjectionAxisZ])) ? eProjectionAxisX
                    : eProjectionAxisZ;
}

struct indexremap_t
{
        indexremap_t (std::size_t _x, std::size_t _y, std::size_t _z) :
            x(_x), y(_y), z(_z)
        {
        }
        std::size_t x, y, z;
};

inline indexremap_t indexremap_for_projectionaxis (const ProjectionAxis axis)
{
    switch (axis) {
    case eProjectionAxisX:
        return indexremap_t(1, 2, 0);
    case eProjectionAxisY:
        return indexremap_t(2, 0, 1);
    default:
        return indexremap_t(0, 1, 2);
    }
}

enum PlaneClassification
{
    ePlaneFront = 0, ePlaneBack = 1, ePlaneOn = 2,
};

#define MAX_POINTS_ON_WINDING 64
const std::size_t c_brush_maxFaces = 1024;

class WindingVertex
{
    public:
        Vector3 vertex;
        Vector2 texcoord;
        Vector3 tangent;
        Vector3 bitangent;
        std::size_t adjacent;
};

struct Winding
{
        typedef Array<WindingVertex> container_type;

        std::size_t numpoints;
        container_type points;

        typedef container_type::iterator iterator;
        typedef container_type::const_iterator const_iterator;

        Winding () :
            numpoints(0)
        {
        }
        Winding (std::size_t size) :
            numpoints(0), points(size)
        {
        }
        void resize (std::size_t size)
        {
            points.resize(size);
            numpoints = 0;
        }

        iterator begin ()
        {
            return points.begin();
        }
        const_iterator begin () const
        {
            return points.begin();
        }
        iterator end ()
        {
            return points.begin() + numpoints;
        }
        const_iterator end () const
        {
            return points.begin() + numpoints;
        }

        WindingVertex& operator[] (std::size_t index)
        {
            ASSERT_MESSAGE(index < points.size(), "winding: index out of bounds");
            return points[index];
        }
        const WindingVertex& operator[] (std::size_t index) const
        {
            ASSERT_MESSAGE(index < points.size(), "winding: index out of bounds");
            return points[index];
        }

        void push_back (const WindingVertex& point)
        {
            points[numpoints] = point;
            ++numpoints;
        }
        void erase (iterator point)
        {
            for (iterator i = point + 1; i != end(); point = i, ++i) {
                *point = *i;
            }
            --numpoints;
        }
};

typedef BasicVector3<double> DoubleVector3;

class DoubleLine
{
    public:
        DoubleVector3 origin;
        DoubleVector3 direction;
};

class FixedWindingVertex
{
    public:
        DoubleVector3 vertex;
        DoubleLine edge;
        std::size_t adjacent;

        FixedWindingVertex (const DoubleVector3& vertex_, const DoubleLine& edge_, std::size_t adjacent_) :
            vertex(vertex_), edge(edge_), adjacent(adjacent_)
        {
        }
};

struct FixedWinding
{
        typedef std::vector<FixedWindingVertex> Points;
        Points points;

        FixedWinding ()
        {
            points.reserve(MAX_POINTS_ON_WINDING);
        }

        FixedWindingVertex& front ()
        {
            return points.front();
        }
        const FixedWindingVertex& front () const
        {
            return points.front();
        }
        FixedWindingVertex& back ()
        {
            return points.back();
        }
        const FixedWindingVertex& back () const
        {
            return points.back();
        }

        void clear ()
        {
            points.clear();
        }

        void push_back (const FixedWindingVertex& point)
        {
            points.push_back(point);
        }
        std::size_t size () const
        {
            return points.size();
        }

        FixedWindingVertex& operator[] (std::size_t index)
        {
            //ASSERT_MESSAGE(index < MAX_POINTS_ON_WINDING, "winding: index out of bounds");
            return points[index];
        }
        const FixedWindingVertex& operator[] (std::size_t index) const
        {
            //ASSERT_MESSAGE(index < MAX_POINTS_ON_WINDING, "winding: index out of bounds");
            return points[index];
        }

};

inline void Winding_forFixedWinding (Winding& winding, const FixedWinding& fixed)
{
    winding.resize(fixed.size());
    winding.numpoints = fixed.size();
    for (std::size_t i = 0; i < fixed.size(); ++i) {
        winding[i].vertex[0] = static_cast<float> (fixed[i].vertex[0]);
        winding[i].vertex[1] = static_cast<float> (fixed[i].vertex[1]);
        winding[i].vertex[2] = static_cast<float> (fixed[i].vertex[2]);
        winding[i].adjacent = fixed[i].adjacent;
    }
}

inline std::size_t Winding_wrap (const Winding& winding, std::size_t i)
{
    ASSERT_MESSAGE(winding.numpoints != 0, "Winding_wrap: empty winding");
    return i % winding.numpoints;
}

inline std::size_t Winding_next (const Winding& winding, std::size_t i)
{
    return Winding_wrap(winding, ++i);
}

class Plane3;

void Winding_createInfinite (FixedWinding& w, const Plane3& plane, double infinity);

inline bool Edge_isDegenerate (const Vector3& x, const Vector3& y)
{
    return (y - x).getLengthSquared() < (ON_EPSILON * ON_EPSILON);
}

void Winding_Clip (const FixedWinding& winding, const Plane3& plane, const Plane3& clipPlane, std::size_t adjacent,
        FixedWinding& clipped);

struct BrushSplitType
{
        BrushSplitType ()
        {
            counts[0] = 0;
            counts[1] = 0;
            counts[2] = 0;
        }
        BrushSplitType& operator+= (const BrushSplitType& other)
        {
            counts[0] += other.counts[0];
            counts[1] += other.counts[1];
            counts[2] += other.counts[2];
            return *this;
        }
        std::size_t counts[3];
};

BrushSplitType Winding_ClassifyPlane (const Winding& w, const Plane3& plane);

bool Winding_PlanesConcave (const Winding& w1, const Winding& w2, const Plane3& plane1, const Plane3& plane2);
bool Winding_TestPlane (const Winding& w, const Plane3& plane, bool flipped);

std::size_t Winding_FindAdjacent (const Winding& w, std::size_t face);

std::size_t Winding_Opposite (const Winding& w, const std::size_t index, const std::size_t other);
std::size_t Winding_Opposite (const Winding& w, std::size_t index);

void Winding_Centroid (const Winding& w, const Plane3& plane, Vector3& centroid);

inline void Winding_printConnectivity (Winding& winding)
{
    for (Winding::iterator i = winding.begin(); i != winding.end(); ++i) {
        std::size_t vertexIndex = std::distance(winding.begin(), i);
        globalOutputStream() << "vertex: " << Unsigned(vertexIndex) << " adjacent: " << Unsigned((*i).adjacent) << "\n";
    }
}

#endif