summaryrefslogtreecommitdiff
path: root/src/mesh/assimp-master/contrib/clipper/clipper.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/mesh/assimp-master/contrib/clipper/clipper.hpp')
-rw-r--r--src/mesh/assimp-master/contrib/clipper/clipper.hpp306
1 files changed, 306 insertions, 0 deletions
diff --git a/src/mesh/assimp-master/contrib/clipper/clipper.hpp b/src/mesh/assimp-master/contrib/clipper/clipper.hpp
new file mode 100644
index 0000000..7cdac6c
--- /dev/null
+++ b/src/mesh/assimp-master/contrib/clipper/clipper.hpp
@@ -0,0 +1,306 @@
+/*******************************************************************************
+* *
+* Author : Angus Johnson *
+* Version : 4.8.8 *
+* Date : 30 August 2012 *
+* Website : http://www.angusj.com *
+* Copyright : Angus Johnson 2010-2012 *
+* *
+* License: *
+* Use, modification & distribution is subject to Boost Software License Ver 1. *
+* http://www.boost.org/LICENSE_1_0.txt *
+* *
+* Attributions: *
+* The code in this library is an extension of Bala Vatti's clipping algorithm: *
+* "A generic solution to polygon clipping" *
+* Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. *
+* http://portal.acm.org/citation.cfm?id=129906 *
+* *
+* Computer graphics and geometric modeling: implementation and algorithms *
+* By Max K. Agoston *
+* Springer; 1 edition (January 4, 2005) *
+* http://books.google.com/books?q=vatti+clipping+agoston *
+* *
+* See also: *
+* "Polygon Offsetting by Computing Winding Numbers" *
+* Paper no. DETC2005-85513 pp. 565-575 *
+* ASME 2005 International Design Engineering Technical Conferences *
+* and Computers and Information in Engineering Conference (IDETC/CIE2005) *
+* September 24-28, 2005 , Long Beach, California, USA *
+* http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf *
+* *
+*******************************************************************************/
+
+#ifndef clipper_hpp
+#define clipper_hpp
+
+#include <vector>
+#include <stdexcept>
+#include <cstring>
+#include <cstdlib>
+#include <ostream>
+
+namespace ClipperLib {
+
+enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor };
+enum PolyType { ptSubject, ptClip };
+//By far the most widely used winding rules for polygon filling are
+//EvenOdd & NonZero (GDI, GDI+, XLib, OpenGL, Cairo, AGG, Quartz, SVG, Gr32)
+//Others rules include Positive, Negative and ABS_GTR_EQ_TWO (only in OpenGL)
+//see http://glprogramming.com/red/chapter11.html
+enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative };
+
+typedef signed long long long64;
+typedef unsigned long long ulong64;
+
+struct IntPoint {
+public:
+ long64 X;
+ long64 Y;
+ IntPoint(long64 x = 0, long64 y = 0): X(x), Y(y) {};
+ friend std::ostream& operator <<(std::ostream &s, IntPoint &p);
+};
+
+typedef std::vector< IntPoint > Polygon;
+typedef std::vector< Polygon > Polygons;
+
+std::ostream& operator <<(std::ostream &s, Polygon &p);
+std::ostream& operator <<(std::ostream &s, Polygons &p);
+
+struct ExPolygon {
+ Polygon outer;
+ Polygons holes;
+};
+typedef std::vector< ExPolygon > ExPolygons;
+
+enum JoinType { jtSquare, jtRound, jtMiter };
+
+bool Orientation(const Polygon &poly);
+double Area(const Polygon &poly);
+void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys,
+ double delta, JoinType jointype = jtSquare, double MiterLimit = 2);
+void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillType fillType = pftEvenOdd);
+void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFillType fillType = pftEvenOdd);
+void SimplifyPolygons(Polygons &polys, PolyFillType fillType = pftEvenOdd);
+
+void ReversePolygon(Polygon& p);
+void ReversePolygons(Polygons& p);
+
+//used internally ...
+enum EdgeSide { esNeither = 0, esLeft = 1, esRight = 2, esBoth = 3 };
+enum IntersectProtects { ipNone = 0, ipLeft = 1, ipRight = 2, ipBoth = 3 };
+
+struct TEdge {
+ long64 xbot;
+ long64 ybot;
+ long64 xcurr;
+ long64 ycurr;
+ long64 xtop;
+ long64 ytop;
+ double dx;
+ long64 tmpX;
+ PolyType polyType;
+ EdgeSide side;
+ int windDelta; //1 or -1 depending on winding direction
+ int windCnt;
+ int windCnt2; //winding count of the opposite polytype
+ int outIdx;
+ TEdge *next;
+ TEdge *prev;
+ TEdge *nextInLML;
+ TEdge *nextInAEL;
+ TEdge *prevInAEL;
+ TEdge *nextInSEL;
+ TEdge *prevInSEL;
+};
+
+struct IntersectNode {
+ TEdge *edge1;
+ TEdge *edge2;
+ IntPoint pt;
+ IntersectNode *next;
+};
+
+struct LocalMinima {
+ long64 Y;
+ TEdge *leftBound;
+ TEdge *rightBound;
+ LocalMinima *next;
+};
+
+struct Scanbeam {
+ long64 Y;
+ Scanbeam *next;
+};
+
+struct OutPt; //forward declaration
+
+struct OutRec {
+ int idx;
+ bool isHole;
+ OutRec *FirstLeft;
+ OutRec *AppendLink;
+ OutPt *pts;
+ OutPt *bottomPt;
+ OutPt *bottomFlag;
+ EdgeSide sides;
+};
+
+struct OutPt {
+ int idx;
+ IntPoint pt;
+ OutPt *next;
+ OutPt *prev;
+};
+
+struct JoinRec {
+ IntPoint pt1a;
+ IntPoint pt1b;
+ int poly1Idx;
+ IntPoint pt2a;
+ IntPoint pt2b;
+ int poly2Idx;
+};
+
+struct HorzJoinRec {
+ TEdge *edge;
+ int savedIdx;
+};
+
+struct IntRect { long64 left; long64 top; long64 right; long64 bottom; };
+
+typedef std::vector < OutRec* > PolyOutList;
+typedef std::vector < TEdge* > EdgeList;
+typedef std::vector < JoinRec* > JoinList;
+typedef std::vector < HorzJoinRec* > HorzJoinList;
+
+//ClipperBase is the ancestor to the Clipper class. It should not be
+//instantiated directly. This class simply abstracts the conversion of sets of
+//polygon coordinates into edge objects that are stored in a LocalMinima list.
+class ClipperBase
+{
+public:
+ ClipperBase();
+ virtual ~ClipperBase();
+ bool AddPolygon(const Polygon &pg, PolyType polyType);
+ bool AddPolygons( const Polygons &ppg, PolyType polyType);
+ virtual void Clear();
+ IntRect GetBounds();
+protected:
+ void DisposeLocalMinimaList();
+ TEdge* AddBoundsToLML(TEdge *e);
+ void PopLocalMinima();
+ virtual void Reset();
+ void InsertLocalMinima(LocalMinima *newLm);
+ LocalMinima *m_CurrentLM;
+ LocalMinima *m_MinimaList;
+ bool m_UseFullRange;
+ EdgeList m_edges;
+};
+
+class Clipper : public virtual ClipperBase
+{
+public:
+ Clipper();
+ ~Clipper();
+ bool Execute(ClipType clipType,
+ Polygons &solution,
+ PolyFillType subjFillType = pftEvenOdd,
+ PolyFillType clipFillType = pftEvenOdd);
+ bool Execute(ClipType clipType,
+ ExPolygons &solution,
+ PolyFillType subjFillType = pftEvenOdd,
+ PolyFillType clipFillType = pftEvenOdd);
+ void Clear();
+ bool ReverseSolution() {return m_ReverseOutput;};
+ void ReverseSolution(bool value) {m_ReverseOutput = value;};
+protected:
+ void Reset();
+ virtual bool ExecuteInternal(bool fixHoleLinkages);
+private:
+ PolyOutList m_PolyOuts;
+ JoinList m_Joins;
+ HorzJoinList m_HorizJoins;
+ ClipType m_ClipType;
+ Scanbeam *m_Scanbeam;
+ TEdge *m_ActiveEdges;
+ TEdge *m_SortedEdges;
+ IntersectNode *m_IntersectNodes;
+ bool m_ExecuteLocked;
+ PolyFillType m_ClipFillType;
+ PolyFillType m_SubjFillType;
+ bool m_ReverseOutput;
+ void DisposeScanbeamList();
+ void SetWindingCount(TEdge& edge);
+ bool IsEvenOddFillType(const TEdge& edge) const;
+ bool IsEvenOddAltFillType(const TEdge& edge) const;
+ void InsertScanbeam(const long64 Y);
+ long64 PopScanbeam();
+ void InsertLocalMinimaIntoAEL(const long64 botY);
+ void InsertEdgeIntoAEL(TEdge *edge);
+ void AddEdgeToSEL(TEdge *edge);
+ void CopyAELToSEL();
+ void DeleteFromSEL(TEdge *e);
+ void DeleteFromAEL(TEdge *e);
+ void UpdateEdgeIntoAEL(TEdge *&e);
+ void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2);
+ bool IsContributing(const TEdge& edge) const;
+ bool IsTopHorz(const long64 XPos);
+ void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2);
+ void DoMaxima(TEdge *e, long64 topY);
+ void ProcessHorizontals();
+ void ProcessHorizontal(TEdge *horzEdge);
+ void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
+ void AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
+ void AppendPolygon(TEdge *e1, TEdge *e2);
+ void DoEdge1(TEdge *edge1, TEdge *edge2, const IntPoint &pt);
+ void DoEdge2(TEdge *edge1, TEdge *edge2, const IntPoint &pt);
+ void DoBothEdges(TEdge *edge1, TEdge *edge2, const IntPoint &pt);
+ void IntersectEdges(TEdge *e1, TEdge *e2,
+ const IntPoint &pt, IntersectProtects protects);
+ OutRec* CreateOutRec();
+ void AddOutPt(TEdge *e, const IntPoint &pt);
+ void DisposeBottomPt(OutRec &outRec);
+ void DisposeAllPolyPts();
+ void DisposeOutRec(PolyOutList::size_type index);
+ bool ProcessIntersections(const long64 botY, const long64 topY);
+ void AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt);
+ void BuildIntersectList(const long64 botY, const long64 topY);
+ void ProcessIntersectList();
+ void ProcessEdgesAtTopOfScanbeam(const long64 topY);
+ void BuildResult(Polygons& polys);
+ void BuildResultEx(ExPolygons& polys);
+ void SetHoleState(TEdge *e, OutRec *OutRec);
+ void DisposeIntersectNodes();
+ bool FixupIntersections();
+ void FixupOutPolygon(OutRec &outRec);
+ bool IsHole(TEdge *e);
+ void FixHoleLinkage(OutRec *outRec);
+ void CheckHoleLinkages1(OutRec *outRec1, OutRec *outRec2);
+ void CheckHoleLinkages2(OutRec *outRec1, OutRec *outRec2);
+ void AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx = -1, int e2OutIdx = -1);
+ void ClearJoins();
+ void AddHorzJoin(TEdge *e, int idx);
+ void ClearHorzJoins();
+ void JoinCommonEdges(bool fixHoleLinkages);
+};
+
+//------------------------------------------------------------------------------
+//------------------------------------------------------------------------------
+
+class clipperException : public std::exception
+{
+ public:
+ clipperException(const char* description): m_descr(description) {}
+ virtual ~clipperException() throw() {}
+ virtual const char* what() const throw() {return m_descr.c_str();}
+ private:
+ std::string m_descr;
+};
+//------------------------------------------------------------------------------
+
+} //ClipperLib namespace
+
+#endif //clipper_hpp
+
+
generated by cgit v1.2.1 (git 2.18.0) at 2024-12-26 13:05:43 +0000