Subversion Repositories orsoc_graphics_accelerator

/*
 * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
 * http://code.google.com/p/poly2tri/
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 * * Redistributions of source code must retain the above copyright notice,
 *   this list of conditions and the following disclaimer.
 * * Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimer in the documentation
 *   and/or other materials provided with the distribution.
 * * Neither the name of Poly2Tri nor the names of its contributors may be
 *   used to endorse or promote products derived from this software without specific
 *   prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
// Include guard
#ifndef SHAPES_H
#define SHAPES_H
 
#include <vector>
#include <cstddef>
#include <assert.h>
#include <cmath>
 
namespace p2t {
 
struct Edge;
 
struct Point {
 
  double x, y;
 
  /// Default constructor does nothing (for performance).
  Point()
  {
    x = 0.0;
    y = 0.0;
  }
 
  /// The edges this point constitutes an upper ending point
  std::vector<Edge*> edge_list;
 
  /// Construct using coordinates.
  Point(double x, double y) : x(x), y(y) {}
 
  /// Set this point to all zeros.
  void set_zero()
  {
    x = 0.0;
    y = 0.0;
  }
 
  /// Set this point to some specified coordinates.
  void set(double x_, double y_)
  {
    x = x_;
    y = y_;
  }
 
  /// Negate this point.
  Point operator -() const
  {
    Point v;
    v.set(-x, -y);
    return v;
  }
 
  /// Add a point to this point.
  void operator +=(const Point& v)
  {
    x += v.x;
    y += v.y;
  }
 
  /// Subtract a point from this point.
  void operator -=(const Point& v)
  {
    x -= v.x;
    y -= v.y;
  }
 
  /// Multiply this point by a scalar.
  void operator *=(double a)
  {
    x *= a;
    y *= a;
  }
 
  /// Get the length of this point (the norm).
  double Length() const
  {
    return sqrt(x * x + y * y);
  }
 
  /// Convert this point into a unit point. Returns the Length.
  double Normalize()
  {
    double len = Length();
    x /= len;
    y /= len;
    return len;
  }
 
};
 
// Represents a simple polygon's edge
struct Edge {
 
  Point* p, *q;
 
  /// Constructor
  Edge(Point& p1, Point& p2) : p(&p1), q(&p2)
  {
    if (p1.y > p2.y) {
      q = &p1;
      p = &p2;
    } else if (p1.y == p2.y) {
      if (p1.x > p2.x) {
        q = &p1;
        p = &p2;
      } else if (p1.x == p2.x) {
        // Repeat points
        assert(false);
      }
    }
 
    q->edge_list.push_back(this);
  }
};
 
// Triangle-based data structures are know to have better performance than quad-edge structures
// See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator"
//      "Triangulations in CGAL"
class Triangle {
public:
 
/// Constructor
Triangle(Point& a, Point& b, Point& c);
 
/// Flags to determine if an edge is a Constrained edge
bool constrained_edge[3];
/// Flags to determine if an edge is a Delauney edge
bool delaunay_edge[3];
 
Point* GetPoint(const int& index);
Point* PointCW(Point& point);
Point* PointCCW(Point& point);
Point* OppositePoint(Triangle& t, Point& p);
 
Triangle* GetNeighbor(const int& index);
void MarkNeighbor(Point* p1, Point* p2, Triangle* t);
void MarkNeighbor(Triangle& t);
 
void MarkConstrainedEdge(const int index);
void MarkConstrainedEdge(Edge& edge);
void MarkConstrainedEdge(Point* p, Point* q);
 
int Index(const Point* p);
int EdgeIndex(const Point* p1, const Point* p2);
 
Triangle* NeighborCW(Point& point);
Triangle* NeighborCCW(Point& point);
bool GetConstrainedEdgeCCW(Point& p);
bool GetConstrainedEdgeCW(Point& p);
void SetConstrainedEdgeCCW(Point& p, bool ce);
void SetConstrainedEdgeCW(Point& p, bool ce);
bool GetDelunayEdgeCCW(Point& p);
bool GetDelunayEdgeCW(Point& p);
void SetDelunayEdgeCCW(Point& p, bool e);
void SetDelunayEdgeCW(Point& p, bool e);
 
bool Contains(Point* p);
bool Contains(const Edge& e);
bool Contains(Point* p, Point* q);
void Legalize(Point& point);
void Legalize(Point& opoint, Point& npoint);
/**
 * Clears all references to all other triangles and points
 */
void Clear();
void ClearNeighbor(Triangle *triangle );
void ClearNeighbors();
void ClearDelunayEdges();
 
inline bool IsInterior();
inline void IsInterior(bool b);
 
Triangle& NeighborAcross(Point& opoint);
 
void DebugPrint();
 
private:
 
/// Triangle points
Point* points_[3];
/// Neighbor list
Triangle* neighbors_[3];
 
/// Has this triangle been marked as an interior triangle?
bool interior_;
};
 
inline bool cmp(const Point* a, const Point* b)
{
  if (a->y < b->y) {
    return true;
  } else if (a->y == b->y) {
    // Make sure q is point with greater x value
    if (a->x < b->x) {
      return true;
    }
  }
  return false;
}
 
/// Add two points_ component-wise.
inline Point operator +(const Point& a, const Point& b)
{
  return Point(a.x + b.x, a.y + b.y);
}
 
/// Subtract two points_ component-wise.
inline Point operator -(const Point& a, const Point& b)
{
  return Point(a.x - b.x, a.y - b.y);
}
 
/// Multiply point by scalar
inline Point operator *(double s, const Point& a)
{
  return Point(s * a.x, s * a.y);
}
 
inline bool operator ==(const Point& a, const Point& b)
{
  return a.x == b.x && a.y == b.y;
}
 
inline bool operator !=(const Point& a, const Point& b)
{
  return a.x != b.x && a.y != b.y;
}
 
/// Peform the dot product on two vectors.
inline double Dot(const Point& a, const Point& b)
{
  return a.x * b.x + a.y * b.y;
}
 
/// Perform the cross product on two vectors. In 2D this produces a scalar.
inline double Cross(const Point& a, const Point& b)
{
  return a.x * b.y - a.y * b.x;
}
 
/// Perform the cross product on a point and a scalar. In 2D this produces
/// a point.
inline Point Cross(const Point& a, double s)
{
  return Point(s * a.y, -s * a.x);
}
 
/// Perform the cross product on a scalar and a point. In 2D this produces
/// a point.
inline Point Cross(const double s, const Point& a)
{
  return Point(-s * a.y, s * a.x);
}
 
inline Point* Triangle::GetPoint(const int& index)
{
  return points_[index];
}
 
inline Triangle* Triangle::GetNeighbor(const int& index)
{
  return neighbors_[index];
}
 
inline bool Triangle::Contains(Point* p)
{
  return p == points_[0] || p == points_[1] || p == points_[2];
}
 
inline bool Triangle::Contains(const Edge& e)
{
  return Contains(e.p) && Contains(e.q);
}
 
inline bool Triangle::Contains(Point* p, Point* q)
{
  return Contains(p) && Contains(q);
}
 
inline bool Triangle::IsInterior()
{
  return interior_;
}
 
inline void Triangle::IsInterior(bool b)
{
  interior_ = b;
}
 
}
 
#endif