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