1 //----------------------------------------------------------------------------- 2 // Anything relating to plane polygons and triangles, and (generally, non- 3 // planar) meshes thereof. 4 // 5 // Copyright 2008-2013 Jonathan Westhues. 6 //----------------------------------------------------------------------------- 7 8 #ifndef __POLYGON_H 9 #define __POLYGON_H 10 11 class SPointList; 12 class SPolygon; 13 class SContour; 14 class SMesh; 15 class SBsp3; 16 class SOutlineList; 17 18 class SEdge { 19 public: 20 int tag; 21 int auxA, auxB; 22 Vector a, b; 23 24 static SEdge From(Vector a, Vector b); 25 bool EdgeCrosses(Vector a, Vector b, Vector *pi=NULL, SPointList *spl=NULL); 26 }; 27 28 class SEdgeList { 29 public: 30 List<SEdge> l; 31 32 void Clear(void); 33 void AddEdge(Vector a, Vector b, int auxA=0, int auxB=0); 34 bool AssemblePolygon(SPolygon *dest, SEdge *errorAt, bool keepDir=false); 35 bool AssembleContour(Vector first, Vector last, SContour *dest, 36 SEdge *errorAt, bool keepDir); 37 int AnyEdgeCrossings(Vector a, Vector b, 38 Vector *pi=NULL, SPointList *spl=NULL); 39 bool ContainsEdgeFrom(SEdgeList *sel); 40 bool ContainsEdge(SEdge *se); 41 void CullExtraneousEdges(void); 42 void MergeCollinearSegments(Vector a, Vector b); 43 }; 44 45 // A kd-tree element needs to go on a side of a node if it's when KDTREE_EPS 46 // of the boundary. So increasing this number never breaks anything, but may 47 // result in more duplicated elements. So it's conservative to be sloppy here. 48 #define KDTREE_EPS (20*LENGTH_EPS) 49 50 class SEdgeLl { 51 public: 52 SEdge *se; 53 SEdgeLl *next; 54 55 static SEdgeLl *Alloc(void); 56 }; 57 58 class SKdNodeEdges { 59 public: 60 int which; // whether c is x, y, or z 61 double c; 62 SKdNodeEdges *gt; 63 SKdNodeEdges *lt; 64 65 SEdgeLl *edges; 66 67 static SKdNodeEdges *From(SEdgeList *sel); 68 static SKdNodeEdges *From(SEdgeLl *sell); 69 static SKdNodeEdges *Alloc(void); 70 int AnyEdgeCrossings(Vector a, Vector b, int cnt, 71 Vector *pi=NULL, SPointList *spl=NULL); 72 }; 73 74 class SPoint { 75 public: 76 int tag; 77 78 enum { 79 UNKNOWN = 0, 80 NOT_EAR = 1, 81 EAR = 2 82 }; 83 int ear; 84 85 Vector p; 86 Vector auxv; 87 }; 88 89 class SPointList { 90 public: 91 List<SPoint> l; 92 93 void Clear(void); 94 bool ContainsPoint(Vector pt); 95 int IndexForPoint(Vector pt); 96 void IncrementTagFor(Vector pt); 97 void Add(Vector pt); 98 }; 99 100 class SContour { 101 public: 102 int tag; 103 int timesEnclosed; 104 Vector xminPt; 105 List<SPoint> l; 106 107 void AddPoint(Vector p); 108 void MakeEdgesInto(SEdgeList *el); 109 void Reverse(void); 110 Vector ComputeNormal(void); 111 double SignedAreaProjdToNormal(Vector n); 112 bool IsClockwiseProjdToNormal(Vector n); 113 bool ContainsPointProjdToNormal(Vector n, Vector p); 114 void OffsetInto(SContour *dest, double r); 115 void CopyInto(SContour *dest); 116 void FindPointWithMinX(void); 117 Vector AnyEdgeMidpoint(void); 118 119 bool IsEar(int bp, double scaledEps); 120 bool BridgeToContour(SContour *sc, SEdgeList *el, List<Vector> *vl); 121 void ClipEarInto(SMesh *m, int bp, double scaledEps); 122 void UvTriangulateInto(SMesh *m, SSurface *srf); 123 }; 124 125 typedef struct { 126 uint32_t face; 127 RgbaColor color; 128 } STriMeta; 129 130 class SPolygon { 131 public: 132 List<SContour> l; 133 Vector normal; 134 135 Vector ComputeNormal(void); 136 void AddEmptyContour(void); 137 int WindingNumberForPoint(Vector p); 138 double SignedArea(void); 139 bool ContainsPoint(Vector p); 140 void MakeEdgesInto(SEdgeList *el); 141 void FixContourDirections(void); 142 void Clear(void); 143 bool SelfIntersecting(Vector *intersectsAt); 144 bool IsEmpty(void); 145 Vector AnyPoint(void); 146 void OffsetInto(SPolygon *dest, double r); 147 void UvTriangulateInto(SMesh *m, SSurface *srf); 148 void UvGridTriangulateInto(SMesh *m, SSurface *srf); 149 }; 150 151 class STriangle { 152 public: 153 int tag; 154 STriMeta meta; 155 Vector a, b, c; 156 Vector an, bn, cn; 157 158 static STriangle From(STriMeta meta, Vector a, Vector b, Vector c); 159 Vector Normal(void); 160 void FlipNormal(void); 161 double MinAltitude(void); 162 int WindingNumberForPoint(Vector p); 163 bool ContainsPoint(Vector p); 164 bool ContainsPointProjd(Vector n, Vector p); 165 }; 166 167 class SBsp2 { 168 public: 169 Vector np; // normal to the plane 170 171 Vector no; // outer normal to the edge 172 double d; 173 SEdge edge; 174 175 SBsp2 *pos; 176 SBsp2 *neg; 177 178 SBsp2 *more; 179 180 enum { POS = 100, NEG = 101, COPLANAR = 200 }; 181 void InsertTriangleHow(int how, STriangle *tr, SMesh *m, SBsp3 *bsp3); 182 void InsertTriangle(STriangle *tr, SMesh *m, SBsp3 *bsp3); 183 Vector IntersectionWith(Vector a, Vector b); 184 void InsertEdge(SEdge *nedge, Vector nnp, Vector out); 185 static SBsp2 *InsertOrCreateEdge(SBsp2 *where, SEdge *nedge, Vector nnp, Vector out); 186 static SBsp2 *Alloc(void); 187 188 void DebugDraw(Vector n, double d); 189 }; 190 191 class SBsp3 { 192 public: 193 Vector n; 194 double d; 195 196 STriangle tri; 197 SBsp3 *pos; 198 SBsp3 *neg; 199 200 SBsp3 *more; 201 202 SBsp2 *edges; 203 204 static SBsp3 *Alloc(void); 205 static SBsp3 *FromMesh(SMesh *m); 206 207 Vector IntersectionWith(Vector a, Vector b); 208 209 enum { POS = 100, NEG = 101, COPLANAR = 200 }; 210 void InsertHow(int how, STriangle *str, SMesh *instead); 211 void Insert(STriangle *str, SMesh *instead); 212 static SBsp3 *InsertOrCreate(SBsp3 *where, STriangle *str, SMesh *instead); 213 214 void InsertConvexHow(int how, STriMeta meta, Vector *vertex, int n, 215 SMesh *instead); 216 SBsp3 *InsertConvex(STriMeta meta, Vector *vertex, int n, SMesh *instead); 217 218 void InsertInPlane(bool pos2, STriangle *tr, SMesh *m); 219 220 void GenerateInPaintOrder(SMesh *m); 221 222 void DebugDraw(void); 223 }; 224 225 class SMesh { 226 public: 227 List<STriangle> l; 228 229 bool flipNormal; 230 bool keepCoplanar; 231 bool atLeastOneDiscarded; 232 bool isTransparent; 233 234 void Clear(void); 235 void AddTriangle(STriangle *st); 236 void AddTriangle(STriMeta meta, Vector a, Vector b, Vector c); 237 void AddTriangle(STriMeta meta, Vector n, Vector a, Vector b, Vector c); 238 void DoBounding(Vector v, Vector *vmax, Vector *vmin); 239 void GetBounding(Vector *vmax, Vector *vmin); 240 241 void Simplify(int start); 242 243 void AddAgainstBsp(SMesh *srcm, SBsp3 *bsp3); 244 void MakeFromUnionOf(SMesh *a, SMesh *b); 245 void MakeFromDifferenceOf(SMesh *a, SMesh *b); 246 247 void MakeFromCopyOf(SMesh *a); 248 void MakeFromTransformationOf(SMesh *a, 249 Vector trans, Quaternion q, double scale); 250 void MakeFromAssemblyOf(SMesh *a, SMesh *b); 251 252 void MakeEdgesInPlaneInto(SEdgeList *sel, Vector n, double d); 253 void MakeCertainEdgesAndOutlinesInto(SEdgeList *sel, SOutlineList *sol, int type); 254 255 bool IsEmpty(void); 256 void RemapFaces(Group *g, int remap); 257 258 uint32_t FirstIntersectionWith(Point2d mp); 259 }; 260 261 // A linked list of triangles 262 class STriangleLl { 263 public: 264 STriangle *tri; 265 266 STriangleLl *next; 267 268 static STriangleLl *Alloc(void); 269 }; 270 271 class SOutline { 272 public: 273 int tag; 274 Vector a, b, nl, nr; 275 }; 276 277 class SOutlineList { 278 public: 279 List<SOutline> l; 280 281 void Clear(); 282 void AddEdge(Vector a, Vector b, Vector nl, Vector nr); 283 284 void MakeFromCopyOf(SOutlineList *ol); 285 286 void FillOutlineTags(Vector projDir); 287 }; 288 289 class SKdNode { 290 public: 291 struct EdgeOnInfo { 292 int count; 293 bool frontFacing; 294 bool intersectsMesh; 295 STriangle *tr; 296 int ai; 297 int bi; 298 }; 299 300 int which; // whether c is x, y, or z 301 double c; 302 303 SKdNode *gt; 304 SKdNode *lt; 305 306 STriangleLl *tris; 307 308 static SKdNode *Alloc(void); 309 static SKdNode *From(SMesh *m); 310 static SKdNode *From(STriangleLl *tll); 311 312 void AddTriangle(STriangle *tr); 313 void MakeMeshInto(SMesh *m); 314 void ListTrianglesInto(std::vector<STriangle *> *tl); 315 void ClearTags(void); 316 317 void FindEdgeOn(Vector a, Vector b, int cnt, bool coplanarIsInter, EdgeOnInfo *info); 318 enum { 319 NAKED_OR_SELF_INTER_EDGES = 100, 320 SELF_INTER_EDGES = 200, 321 TURNING_EDGES = 300, 322 EMPHASIZED_EDGES = 400, 323 SHARP_EDGES = 500, 324 }; 325 void MakeCertainEdgesInto(SEdgeList *sel, int how, bool coplanarIsInter, 326 bool *inter, bool *leaky, int auxA=0); 327 void MakeOutlinesInto(SOutlineList *sel); 328 329 void OcclusionTestLine(SEdge orig, SEdgeList *sel, int cnt, bool removeHidden); 330 void SplitLinesAgainstTriangle(SEdgeList *sel, STriangle *tr, bool removeHidden); 331 332 void SnapToMesh(SMesh *m); 333 void SnapToVertex(Vector v, SMesh *extras); 334 }; 335 336 #endif 337 338