Line data    Source code

       1             : /**
       2             : Copyright (c) 2022 Roman Katuntsev <sbkarr@stappler.org>
       3             : Copyright (c) 2023 Stappler LLC <admin@stappler.dev>
       4             : 
       5             : Permission is hereby granted, free of charge, to any person obtaining a copy
       6             : of this software and associated documentation files (the "Software"), to deal
       7             : in the Software without restriction, including without limitation the rights
       8             : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
       9             : copies of the Software, and to permit persons to whom the Software is
      10             : furnished to do so, subject to the following conditions:
      11             : 
      12             : The above copyright notice and this permission notice shall be included in
      13             : all copies or substantial portions of the Software.
      14             : 
      15             : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
      16             : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
      17             : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
      18             : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
      19             : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
      20             : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
      21             : THE SOFTWARE.
      22             : **/
      23             : 
      24             : #ifndef STAPPLER_TESS_SPTESSTYPES_H_
      25             : #define STAPPLER_TESS_SPTESSTYPES_H_
      26             : 
      27             : #include "SPVec4.h"
      28             : #include "SPTess.h"
      29             : 
      30             : namespace STAPPLER_VERSIONIZED stappler::geom {
      31             : 
      32             : struct Vertex;
      33             : struct FaceEdge;
      34             : struct HalfEdge;
      35             : struct Edge;
      36             : 
      37             : using QueueHandle = int32_t;
      38             : 
      39             : static constexpr uint32_t VertexSetPrealloc = 64;
      40             : static constexpr uint32_t EdgeSetPrealloc = 64;
      41             : static constexpr uint32_t VertexAllocBatch = 32;
      42             : static constexpr uint32_t EdgeAllocBatch = 32;
      43             : 
      44             : extern int TessVerboseInfo;
      45             : 
      46             : enum class VertexType {
      47             :         Start, // right non-convex angle
      48             :         End, // left non-convex angle
      49             :         Split, // right convex angle
      50             :         Merge, // left convex angle
      51             :         RegularTop, // boundary below vertex
      52             :         RegularBottom, // boundary above vertex
      53             : };
      54             : 
      55             : struct Helper {
      56             :         HalfEdge *e1 = nullptr;
      57             :         HalfEdge *e2 = nullptr;
      58             :         VertexType type = VertexType::Start;
      59             : };
      60             : 
      61             : struct EdgeDictNode {
      62             :         Vec2 org;
      63             :         Vec2 norm;
      64             :         mutable Vec4 value; // value, dst
      65             :         Edge *edge = nullptr;
      66             :         int16_t windingAbove = 0;
      67             :         bool horizontal = false;
      68             : 
      69             :         mutable Helper helper;
      70             : 
      71   209130958 :         Vec2 current() const { return Vec2(value.x, value.y); }
      72   209165344 :         Vec2 dst() const { return Vec2(value.z, value.w); }
      73             :         float dstX() const { return value.z; }
      74             :         float dstY() const { return value.w; }
      75             : 
      76             :         bool operator < (const EdgeDictNode &other) const;
      77             :         bool operator < (const Edge &other) const;
      78             :         bool operator < (const Vec2 &other) const;
      79             :         bool operator <= (const EdgeDictNode &other) const;
      80             :         bool operator== (const EdgeDictNode &other) const;
      81             : };
      82             : 
      83             : struct Vertex {
      84             :         HalfEdge *_edge = nullptr;  /* a half-edge with this origin */
      85             :         Vec2 _origin;
      86             :         uint32_t _uniqueIdx = maxOf<uint32_t>(); /* to allow identify unique vertices */
      87             :         QueueHandle _queueHandle = maxOf<QueueHandle>(); /* to allow deletion from priority queue */
      88             :         uint32_t _exportIdx = maxOf<uint32_t>();
      89             : 
      90             :         void insertBefore(HalfEdge *eOrig);
      91             :         void removeFromList(Vertex *newOrg);
      92             : 
      93             :         void foreach(const Callback<void(const HalfEdge &)> &) const;
      94             : 
      95             :         void relocate(const Vec2 &);
      96             : };
      97             : 
      98             : struct FaceEdge : memory::AllocPool {
      99             :         FaceEdge *_next = nullptr;
     100             :         Vertex *_vertex = nullptr;
     101             :         Vec2 _origin;
     102             :         Vec2 _displaced;
     103             :         float _value = 0.0f;
     104             :         float _direction = 0.0f;
     105             :         bool _splitVertex = false;
     106             :         bool _degenerate = false;
     107             : 
     108             :         void foreach(const Callback<void(const FaceEdge &)> &) const;
     109             : };
     110             : 
     111             : struct HalfEdge {
     112             :         HalfEdge *_originNext = nullptr; /* next edge CCW around origin */
     113             :         HalfEdge *_leftNext = nullptr; /* next edge CCW around left face */
     114             :         Vec2 origin;
     115             :         uint32_t vertex = maxOf<uint32_t>(); // normally, we should not access vertex directly to improve data locality
     116             :         int16_t _realWinding = 0;
     117             :         int16_t isRight : 2 = 0; // -1 or 1
     118             :         int16_t edgeOffset : 2 = 0; // 0 or 1
     119             :         int16_t _winding : 2 = 0; /* change in winding number when crossing from the right face to the left face */
     120             :         int16_t _mark : 10 = 0;
     121             : 
     122             :         static void splitEdgeLoops(HalfEdge *eOrg, HalfEdge *eNew, Vertex *v);
     123             :         static void joinEdgeLoops(HalfEdge *eOrg, HalfEdge *oPrev);
     124             : 
     125             :         HalfEdge *sym() const; // uses `this` pointer and isLeft to find Sym edge
     126             : 
     127             :         uint32_t getIndex() const;
     128             : 
     129             :         void setOrigin(const Vertex *);
     130             :         void copyOrigin(const HalfEdge *);
     131             : 
     132             :         HalfEdge *getOriginNext() const;
     133             :         HalfEdge *getOriginPrev() const;
     134             : 
     135             :         HalfEdge *getDestinationNext() const;
     136             :         HalfEdge *getDestinationPrev() const;
     137             : 
     138             :         HalfEdge *getLeftLoopNext() const;
     139             :         HalfEdge *getLeftLoopPrev() const;
     140             : 
     141             :         HalfEdge *getRightLoopNext() const;
     142             :         HalfEdge *getRightLoopPrev() const;
     143             : 
     144             :         const Vec2 &getOrgVec() const;
     145             :         const Vec2 &getDstVec() const;
     146    12190757 :         Vec2 getNormVec() const { return getDstVec() - getOrgVec(); }
     147             : 
     148             :         float getLength() const;
     149             : 
     150             :         Edge *getEdge() const;
     151             : 
     152             :         // edge info should be updated
     153             :         bool goesLeft() const; // right edge goes left
     154             :         bool goesRight() const; // left edge goes right
     155             : 
     156             :         void foreachOnFace(const Callback<void(HalfEdge &)> &);
     157             :         void foreachOnVertex(const Callback<void(HalfEdge &)> &);
     158             : 
     159             :         void foreachOnFace(const Callback<void(const HalfEdge &)> &) const;
     160             :         void foreachOnVertex(const Callback<void(const HalfEdge &)> &) const;
     161             : 
     162             :         float getDirection() const;
     163             : };
     164             : 
     165             : struct Edge {
     166             :         HalfEdge left;
     167             :         HalfEdge right;
     168             :         const EdgeDictNode *node = nullptr;
     169             :         float direction = nan();
     170             :         bool inverted = false; // inverted means left edge goes right
     171             :         bool invalidated = false;
     172             : 
     173             :         Edge();
     174             : 
     175             :         const Vec2 &getLeftVec() const;
     176             :         const Vec2 &getRightVec() const;
     177             : 
     178             :         const Vec2 &getOrgVec() const;
     179             :         const Vec2 &getDstVec() const;
     180             : 
     181             :         uint32_t getLeftOrg() const;
     182             :         uint32_t getRightOrg() const;
     183             : 
     184             :         void updateInfo();
     185             : 
     186             :         int16_t getLeftWinding() const;
     187             :         int16_t getRightWinding() const;
     188             : 
     189             :         // halfedge in positive sweep direction
     190        1449 :         HalfEdge *getPostitive() { return (inverted) ? &right : &left; }
     191             : 
     192             :         // halfedge in negative sweep direction
     193         241 :         HalfEdge *getNegative() { return (inverted) ? &left : &right; }
     194             : };
     195             : 
     196             : struct ObjectAllocator : public memory::AllocPool {
     197             :         memory::pool_t *_pool = nullptr;
     198             : 
     199             :         Vertex *_freeVertexes = nullptr;
     200             :         Edge *_freeEdges = nullptr;
     201             :         FaceEdge *_freeFaces = nullptr;
     202             : 
     203             :         memory::vector<Vertex *> _vertexes;
     204             :         memory::vector<Vertex *> _exportVertexes;
     205             :         memory::vector<HalfEdge *> _edgesOfInterests;
     206             :         memory::vector<HalfEdge *> _faceEdges;
     207             : 
     208             :         memory::vector<FaceEdge *> _boundaries;
     209             : 
     210             :         uint32_t _vertexOffset = 0;
     211             : 
     212             :         ObjectAllocator(memory::pool_t *pool);
     213             : 
     214             :         Edge *allocEdge();
     215             :         Vertex *allocVertex();
     216             :         FaceEdge *allocFaceEdge();
     217             : 
     218             :         void releaseEdge(Edge *);
     219             :         void releaseVertex(uint32_t, uint32_t);
     220             :         void releaseVertex(Vertex *);
     221             :         void trimVertexes();
     222             : 
     223             :         void preallocateVertexes(uint32_t n);
     224             :         void preallocateEdges(uint32_t n);
     225             :         void preallocateFaceEdges(uint32_t n);
     226             : 
     227             :         void removeEdgeFromVec(memory::vector<HalfEdge *> &, HalfEdge *);
     228             : };
     229             : 
     230             : struct VertexPriorityQueue {
     231             :         using Handle = QueueHandle;
     232             :         using Key = Vertex *;
     233             : 
     234             :         static constexpr Handle InvalidHandle = maxOf<Handle>();
     235             : 
     236             :         struct Node {
     237             :                 Handle handle;
     238             :         };
     239             : 
     240             :         struct Elem {
     241             :                 Key key;
     242             :                 Handle node;
     243             :         };
     244             : 
     245             :         struct Heap {
     246             :                 Node *nodes = nullptr;
     247             :                 Elem *handles = nullptr;
     248             :                 uint32_t size = 0, max = 0;
     249             :                 Handle freeList = 0;
     250             :                 bool initialized = false;
     251             :                 memory::pool_t *pool;
     252             : 
     253             :                 Heap(memory::pool_t *, uint32_t);
     254             :                 ~Heap();
     255             : 
     256             :                 void init();
     257    17996181 :                 bool empty() const { return size == 0; }
     258      576760 :                 Key getMin() const { return handles[nodes[1].handle].key; }
     259             : 
     260             :                 Handle insert(Key keyNew);
     261             :                 Key extractMin();
     262             :                 void remove(Handle hCurr);
     263             : 
     264             :                 void floatDown(int curr);
     265             :                 void floatUp(int curr);
     266             :         };
     267             : 
     268             :         Heap heap;
     269             :         Key *keys = nullptr;
     270             :         Key **order = nullptr;
     271             :         uint32_t size = 0, max = 0;
     272             :         bool initialized = false;
     273             :         memory::pool_t *pool = nullptr;
     274             :         Handle freeList = 0;
     275             : 
     276             :         VertexPriorityQueue(memory::pool_t *, const memory::vector<Vertex *> &);
     277             :         ~VertexPriorityQueue();
     278             : 
     279             :         bool init();
     280             : 
     281             :         bool empty() const;
     282             : 
     283             :         Handle insert(Key);
     284             :         void remove(Handle);
     285             : 
     286             :         Key extractMin();
     287             :         Key getMin() const;
     288             : };
     289             : 
     290             : enum class IntersectionEvent {
     291             :         Regular,
     292             :         EventIsIntersection, // intersection directly on event point, new edge should split old one
     293             :         EdgeConnection1, // connection, ends on old edge
     294             :         EdgeConnection2, // connection, ends on new edge
     295             : };
     296             : 
     297             : struct EdgeDict {
     298             :         Vec2 event;
     299             : 
     300             :         memory::set<EdgeDictNode> nodes;
     301             :         memory::pool_t *pool = nullptr;
     302             : 
     303             :         EdgeDict(memory::pool_t *, uint32_t size);
     304             : 
     305             :         const EdgeDictNode * push(Edge *, int16_t windingAbove);
     306             :         void pop(const EdgeDictNode *);
     307             : 
     308             :         void update(Vertex *, float tolerance);
     309             : 
     310             :         const EdgeDictNode * checkForIntersects(Vertex *, Vec2 &, IntersectionEvent &, float tolerance) const;
     311             :         const EdgeDictNode * checkForIntersects(HalfEdge *, Vec2 &, IntersectionEvent &, float tolerance) const;
     312             : 
     313             :         // find edge directly below edge (used for region winding)
     314             :         const EdgeDictNode * getEdgeBelow(const Edge *) const;
     315             : 
     316             :         // find edge directly below point (used for monotonize algo)
     317             :         const EdgeDictNode * getEdgeBelow(const Vec2 &, uint32_t vertex) const;
     318             : };
     319             : 
     320             : SP_ATTR_OPTIMIZE_INLINE_FN static inline bool VertLeq(const Vec2 &u, const Vec2 &v) {
     321    35843010 :         return ((u.x < v.x) || (u.x == v.x && u.y <= v.y));
     322             : }
     323             : 
     324             : SP_ATTR_OPTIMIZE_INLINE_FN static inline bool VertLeq(const Vertex *u, const Vertex *v) {
     325    82759688 :         return ((u->_origin.x < v->_origin.x) || (u->_origin.x == v->_origin.x && u->_origin.y <= v->_origin.y));
     326             : }
     327             : 
     328             : SP_ATTR_OPTIMIZE_INLINE_FN static inline bool VertEq(const Vec2 &u, const Vec2 &v, float tolerance) {
     329   414153811 :         return u.fuzzyEquals(v, tolerance);
     330             : }
     331             : 
     332             : SP_ATTR_OPTIMIZE_INLINE_FN static inline bool FloatEq(float u, float v, float tolerance) {
     333    46990303 :         return u - tolerance <= v && v <= u + tolerance;
     334             : }
     335             : 
     336             : SP_ATTR_OPTIMIZE_INLINE_FN static inline bool VertEq(const Vertex *u, const Vertex *v, float tolerance) {
     337     9127899 :         return VertEq(u->_origin, v->_origin, tolerance);
     338             : }
     339             : 
     340             : SP_ATTR_OPTIMIZE_INLINE_FN static inline bool EdgeGoesRight(const HalfEdge *e) {
     341    18259756 :         return VertLeq(e->origin, e->sym()->origin);
     342             : }
     343             : 
     344             : SP_ATTR_OPTIMIZE_INLINE_FN static inline bool EdgeGoesLeft(const HalfEdge *e) {
     345             :         return !VertLeq(e->origin, e->sym()->origin);
     346             : }
     347             : 
     348             : SP_ATTR_OPTIMIZE_INLINE_FN static inline bool AngleIsConvex(const HalfEdge *a, const HalfEdge *b) {
     349     8021042 :         return a->getEdge()->direction > b->getEdge()->direction;
     350             : }
     351             : 
     352             : 
     353             : // fast synthetic tg|ctg function, returns range [-2.0, 2.0f]
     354             : // which monotonically grows with angle between vec and 0x as argument;
     355             : // norm.x assumed to be positive
     356             : SP_ATTR_OPTIMIZE_INLINE_FN static inline float EdgeDirection(const Vec2 &norm) {
     357    18332951 :         if (norm.y >= 0) {
     358     9966303 :                 return (norm.x > norm.y) ? (norm.y / norm.x) : (2.0f - norm.x / norm.y);
     359             :         } else {
     360     8366648 :                 return (norm.x > -norm.y) ? (norm.y / norm.x) : (-2.0f - norm.x / norm.y);
     361             :         }
     362             : }
     363             : 
     364             : // same method, map full angle with positive x axis to [0.0f, 8.0f)
     365             : SP_ATTR_OPTIMIZE_INLINE_FN static inline float EdgeAngle(const Vec2 &norm) {
     366     9988472 :         if (norm.x >= 0 && norm.y >= 0) {
     367             :                 // [0.0, 2.0]
     368     3531014 :                 return (norm.x > norm.y) ? (norm.y / norm.x) : (2.0f - norm.x / norm.y);
     369     6457458 :         } else if (norm.x < 0 && norm.y >= 0) {
     370             :                 // (2.0, 4.0]
     371     2049762 :                 return (-norm.x > norm.y) ? (4.0 + norm.y / norm.x) : (2.0f - norm.x / norm.y);
     372     4407696 :         } else if (norm.x < 0 && norm.y < 0) {
     373             :                 // (4.0, 6.0)
     374     1988392 :                 return (norm.x < norm.y) ? (4.0 + norm.y / norm.x) : (6.0f - norm.x / norm.y);
     375             :         } else {
     376             :                 // [6.0, 8.0)
     377     2419304 :                 return (norm.x > -norm.y) ? (8.0 + norm.y / norm.x) : (6.0f - norm.x / norm.y);
     378             :         }
     379             : }
     380             : 
     381             : SP_ATTR_OPTIMIZE_INLINE_FN static inline float EdgeAngle(const Vec2 &from, const Vec2 &to) {
     382     6095568 :         if (from == to) {
     383             :                 return 8.0f;
     384             :         }
     385             : 
     386             :         auto fromA = EdgeAngle(from);
     387             :         auto toA = EdgeAngle(to);
     388             : 
     389     4994236 :         if (std::isnan(fromA) || std::isnan(toA)) {
     390         525 :                 std::cerr << "EdgeAngle (NaN): " << from << " " << to << "\n";
     391         525 :                 return 0.0f;
     392             :         }
     393             : 
     394     4993689 :         if (fromA <= toA) {
     395     2949672 :                 return toA - fromA;
     396             :         } else {
     397     2044017 :                 return 8.0 - (fromA - toA);
     398             :         }
     399             : }
     400             : 
     401             : SP_ATTR_OPTIMIZE_INLINE_FN static inline bool EdgeAngleIsBelowTolerance(float A, float tolerance) {
     402     3738355 :         return A < tolerance || 8.0f - A < tolerance;
     403             : }
     404             : 
     405             : std::ostream &operator<<(std::ostream &out, const Vertex &v);
     406             : std::ostream &operator<<(std::ostream &out, const HalfEdge &e);
     407             : std::ostream &operator<<(std::ostream &out, const FaceEdge &e);
     408             : std::ostream &operator<<(std::ostream &out, VerboseFlag e);
     409             : std::ostream &operator<<(std::ostream &out, const EdgeDictNode &e);
     410             : std::ostream &operator<<(std::ostream &out, const Edge &e);
     411             : 
     412             : inline std::ostream &
     413             : operator << (std::ostream & os, const IntersectionEvent & ev) {
     414             :         switch (ev) {
     415             :         case IntersectionEvent::Regular: os << "Regular"; break;
     416             :         case IntersectionEvent::EventIsIntersection: os << "EventIsIntersection"; break;
     417             :         case IntersectionEvent::EdgeConnection1: os << "EdgeConnection1"; break;
     418             :         case IntersectionEvent::EdgeConnection2: os << "EdgeConnection2"; break;
     419             :         }
     420             :         return os;
     421             : }
     422             : 
     423    34070519 : inline bool isWindingInside(Winding w, int16_t n) {
     424    34070519 :         switch (w) {
     425     8897199 :         case Winding::EvenOdd: return (n & 1); break;
     426    25173320 :         case Winding::NonZero: return (n != 0); break;
     427           0 :         case Winding::Positive: return (n > 0); break;
     428           0 :         case Winding::Negative: return (n < 0); break;
     429           0 :         case Winding::AbsGeqTwo: return (n >= 2) || (n <= -2); break;
     430             :         }
     431             :         return false;
     432             : }
     433             : 
     434             : }
     435             : 
     436             : #endif /* STAPPLER_TESS_SPTESSTYPES_H_ */