1 //----------------------------------------------------------------------------- 2 // Functions relating to rational polynomial surfaces, which are trimmed by 3 // curves (either rational polynomial curves, or piecewise linear 4 // approximations to curves of intersection that can't be represented 5 // exactly in ratpoly form), and assembled into watertight shells. 6 // 7 // Copyright 2008-2013 Jonathan Westhues. 8 //----------------------------------------------------------------------------- 9 10 #ifndef __SURFACE_H 11 #define __SURFACE_H 12 13 // Utility functions, Bernstein polynomials of order 1-3 and their derivatives. 14 double Bernstein(int k, int deg, double t); 15 double BernsteinDerivative(int k, int deg, double t); 16 17 class SSurface; 18 class SCurvePt; 19 20 // Utility data structure, a two-dimensional BSP to accelerate polygon 21 // operations. 22 class SBspUv { 23 public: 24 Point2d a, b; 25 26 SBspUv *pos; 27 SBspUv *neg; 28 29 SBspUv *more; 30 31 enum { 32 INSIDE = 100, 33 OUTSIDE = 200, 34 EDGE_PARALLEL = 300, 35 EDGE_ANTIPARALLEL = 400, 36 EDGE_OTHER = 500 37 }; 38 39 static SBspUv *Alloc(void); 40 static SBspUv *From(SEdgeList *el, SSurface *srf); 41 42 void ScalePoints(Point2d *pt, Point2d *a, Point2d *b, SSurface *srf); 43 double ScaledSignedDistanceToLine(Point2d pt, Point2d a, Point2d b, 44 SSurface *srf); 45 double ScaledDistanceToLine(Point2d pt, Point2d a, Point2d b, bool seg, 46 SSurface *srf); 47 48 void InsertEdge(Point2d a, Point2d b, SSurface *srf); 49 static SBspUv *InsertOrCreateEdge(SBspUv *where, const Point2d &ea, const Point2d &eb, SSurface *srf); 50 int ClassifyPoint(Point2d p, Point2d eb, SSurface *srf); 51 int ClassifyEdge(Point2d ea, Point2d eb, SSurface *srf); 52 double MinimumDistanceToEdge(Point2d p, SSurface *srf); 53 }; 54 55 // Now the data structures to represent a shell of trimmed rational polynomial 56 // surfaces. 57 58 class SShell; 59 60 class hSSurface { 61 public: 62 uint32_t v; 63 }; 64 65 class hSCurve { 66 public: 67 uint32_t v; 68 }; 69 70 // Stuff for rational polynomial curves, of degree one to three. These are 71 // our inputs, and are also calculated for certain exact surface-surface 72 // intersections. 73 class SBezier { 74 public: 75 int tag; 76 int auxA, auxB; 77 78 int deg; 79 Vector ctrl[4]; 80 double weight[4]; 81 uint32_t entity; 82 83 Vector PointAt(double t); 84 Vector TangentAt(double t); 85 void ClosestPointTo(Vector p, double *t, bool converge=true); 86 void SplitAt(double t, SBezier *bef, SBezier *aft); 87 bool PointOnThisAndCurve(SBezier *sbb, Vector *p); 88 89 Vector Start(void); 90 Vector Finish(void); 91 bool Equals(SBezier *b); 92 void MakePwlInto(SEdgeList *sel, double chordTol=0); 93 void MakePwlInto(List<SCurvePt> *l, double chordTol=0); 94 void MakePwlInto(SContour *sc, double chordTol=0); 95 void MakePwlInto(List<Vector> *l, double chordTol=0); 96 void MakePwlWorker(List<Vector> *l, double ta, double tb, double chordTol); 97 void MakePwlInitialWorker(List<Vector> *l, double ta, double tb, double chordTol); 98 99 void AllIntersectionsWith(SBezier *sbb, SPointList *spl); 100 void GetBoundingProjd(Vector u, Vector orig, double *umin, double *umax); 101 void Reverse(void); 102 103 bool IsInPlane(Vector n, double d); 104 bool IsCircle(Vector axis, Vector *center, double *r); 105 bool IsRational(void); 106 107 SBezier TransformedBy(Vector t, Quaternion q, double scale); 108 SBezier InPerspective(Vector u, Vector v, Vector n, 109 Vector origin, double cameraTan); 110 void ScaleSelfBy(double s); 111 112 static SBezier From(Vector p0, Vector p1, Vector p2, Vector p3); 113 static SBezier From(Vector p0, Vector p1, Vector p2); 114 static SBezier From(Vector p0, Vector p1); 115 static SBezier From(Vector4 p0, Vector4 p1, Vector4 p2, Vector4 p3); 116 static SBezier From(Vector4 p0, Vector4 p1, Vector4 p2); 117 static SBezier From(Vector4 p0, Vector4 p1); 118 }; 119 120 class SBezierList { 121 public: 122 List<SBezier> l; 123 124 void Clear(void); 125 void ScaleSelfBy(double s); 126 void CullIdenticalBeziers(void); 127 void AllIntersectionsWith(SBezierList *sblb, SPointList *spl); 128 bool GetPlaneContainingBeziers(Vector *p, Vector *u, Vector *v, 129 Vector *notCoplanarAt); 130 }; 131 132 class SBezierLoop { 133 public: 134 int tag; 135 List<SBezier> l; 136 Clear(void)137 inline void Clear(void) { l.Clear(); } 138 bool IsClosed(void); 139 void Reverse(void); 140 void MakePwlInto(SContour *sc, double chordTol=0); 141 void GetBoundingProjd(Vector u, Vector orig, double *umin, double *umax); 142 143 static SBezierLoop FromCurves(SBezierList *spcl, 144 bool *allClosed, SEdge *errorAt); 145 }; 146 147 class SBezierLoopSet { 148 public: 149 List<SBezierLoop> l; 150 Vector normal; 151 Vector point; 152 153 static SBezierLoopSet From(SBezierList *spcl, SPolygon *poly, 154 double chordTol, 155 bool *allClosed, SEdge *errorAt, 156 SBezierList *openContours); 157 158 void GetBoundingProjd(Vector u, Vector orig, double *umin, double *umax); 159 void MakePwlInto(SPolygon *sp); 160 void Clear(void); 161 }; 162 163 class SBezierLoopSetSet { 164 public: 165 List<SBezierLoopSet> l; 166 167 void FindOuterFacesFrom(SBezierList *sbl, SPolygon *spxyz, SSurface *srfuv, 168 double chordTol, 169 bool *allClosed, SEdge *notClosedAt, 170 bool *allCoplanar, Vector *notCoplanarAt, 171 SBezierList *openContours); 172 void AddOpenPath(SBezier *sb); 173 void Clear(void); 174 }; 175 176 // Stuff for the surface trim curves: piecewise linear 177 class SCurvePt { 178 public: 179 int tag; 180 Vector p; 181 bool vertex; 182 }; 183 184 class SCurve { 185 public: 186 hSCurve h; 187 188 // In a Boolean, C = A op B. The curves in A and B get copied into C, and 189 // therefore must get new hSCurves assigned. For the curves in A and B, 190 // we use newH to record their new handle in C. 191 hSCurve newH; 192 enum { 193 FROM_A = 100, 194 FROM_B = 200, 195 FROM_INTERSECTION = 300 196 }; 197 int source; 198 199 bool isExact; 200 SBezier exact; 201 202 List<SCurvePt> pts; 203 204 hSSurface surfA; 205 hSSurface surfB; 206 207 static SCurve FromTransformationOf(SCurve *a, Vector t, Quaternion q, 208 double scale); 209 SCurve MakeCopySplitAgainst(SShell *agnstA, SShell *agnstB, 210 SSurface *srfA, SSurface *srfB); 211 void RemoveShortSegments(SSurface *srfA, SSurface *srfB); 212 SSurface *GetSurfaceA(SShell *a, SShell *b); 213 SSurface *GetSurfaceB(SShell *a, SShell *b); 214 215 void Clear(void); 216 }; 217 218 // A segment of a curve by which a surface is trimmed: indicates which curve, 219 // by its handle, and the starting and ending points of our segment of it. 220 // The vector out points out of the surface; it, the surface outer normal, 221 // and a tangent to the beginning of the curve are all orthogonal. 222 class STrimBy { 223 public: 224 hSCurve curve; 225 bool backwards; 226 // If a trim runs backwards, then start and finish still correspond to 227 // the actual start and finish, but they appear in reverse order in 228 // the referenced curve. 229 Vector start; 230 Vector finish; 231 232 static STrimBy EntireCurve(SShell *shell, hSCurve hsc, bool bkwds); 233 }; 234 235 // An intersection point between a line and a surface 236 class SInter { 237 public: 238 int tag; 239 Vector p; 240 SSurface *srf; 241 Point2d pinter; 242 Vector surfNormal; // of the intersecting surface, at pinter 243 bool onEdge; // pinter is on edge of trim poly 244 }; 245 246 // A rational polynomial surface in Bezier form. 247 class SSurface { 248 public: 249 int tag; 250 hSSurface h; 251 252 // Same as newH for the curves; record what a surface gets renamed to 253 // when I copy things over. 254 hSSurface newH; 255 256 RgbaColor color; 257 uint32_t face; 258 259 int degm, degn; 260 Vector ctrl[4][4]; 261 double weight[4][4]; 262 263 List<STrimBy> trim; 264 265 // For testing whether a point (u, v) on the surface lies inside the trim 266 SBspUv *bsp; 267 SEdgeList edges; 268 269 // For caching our initial (u, v) when doing Newton iterations to project 270 // a point into our surface. 271 Point2d cached; 272 273 static SSurface FromExtrusionOf(SBezier *spc, Vector t0, Vector t1); 274 static SSurface FromRevolutionOf(SBezier *sb, Vector pt, Vector axis, 275 double thetas, double thetaf); 276 static SSurface FromPlane(Vector pt, Vector u, Vector v); 277 static SSurface FromTransformationOf(SSurface *a, Vector t, Quaternion q, 278 double scale, 279 bool includingTrims); 280 void ScaleSelfBy(double s); 281 282 void EdgeNormalsWithinSurface(Point2d auv, Point2d buv, 283 Vector *pt, Vector *enin, Vector *enout, 284 Vector *surfn, 285 uint32_t auxA, 286 SShell *shell, SShell *sha, SShell *shb); 287 void FindChainAvoiding(SEdgeList *src, SEdgeList *dest, SPointList *avoid); 288 SSurface MakeCopyTrimAgainst(SShell *parent, SShell *a, SShell *b, 289 SShell *into, int type); 290 void TrimFromEdgeList(SEdgeList *el, bool asUv); 291 void IntersectAgainst(SSurface *b, SShell *agnstA, SShell *agnstB, 292 SShell *into); 293 void AddExactIntersectionCurve(SBezier *sb, SSurface *srfB, 294 SShell *agnstA, SShell *agnstB, SShell *into); 295 296 typedef struct { 297 int tag; 298 Point2d p; 299 } Inter; 300 void WeightControlPoints(void); 301 void UnWeightControlPoints(void); 302 void CopyRowOrCol(bool row, int this_ij, SSurface *src, int src_ij); 303 void BlendRowOrCol(bool row, int this_ij, SSurface *a, int a_ij, 304 SSurface *b, int b_ij); 305 double DepartureFromCoplanar(void); 306 void SplitInHalf(bool byU, SSurface *sa, SSurface *sb); 307 void AllPointsIntersecting(Vector a, Vector b, 308 List<SInter> *l, 309 bool seg, bool trimmed, bool inclTangent); 310 void AllPointsIntersectingUntrimmed(Vector a, Vector b, 311 int *cnt, int *level, 312 List<Inter> *l, bool segment, 313 SSurface *sorig); 314 315 void ClosestPointTo(Vector p, Point2d *puv, bool converge=true); 316 void ClosestPointTo(Vector p, double *u, double *v, bool converge=true); 317 bool ClosestPointNewton(Vector p, double *u, double *v, bool converge=true); 318 319 bool PointIntersectingLine(Vector p0, Vector p1, double *u, double *v); 320 Vector ClosestPointOnThisAndSurface(SSurface *srf2, Vector p); 321 void PointOnSurfaces(SSurface *s1, SSurface *s2, double *u, double *v); 322 Vector PointAt(double u, double v); 323 Vector PointAt(Point2d puv); 324 void TangentsAt(double u, double v, Vector *tu, Vector *tv); 325 Vector NormalAt(Point2d puv); 326 Vector NormalAt(double u, double v); 327 bool LineEntirelyOutsideBbox(Vector a, Vector b, bool segment); 328 void GetAxisAlignedBounding(Vector *ptMax, Vector *ptMin); 329 bool CoincidentWithPlane(Vector n, double d); 330 bool CoincidentWith(SSurface *ss, bool sameNormal); 331 bool IsExtrusion(SBezier *of, Vector *along); 332 bool IsCylinder(Vector *axis, Vector *center, double *r, 333 Vector *start, Vector *finish); 334 335 void TriangulateInto(SShell *shell, SMesh *sm); 336 337 // these are intended as bitmasks, even though there's just one now 338 enum { 339 AS_UV = 0x01, 340 AS_XYZ = 0x00 341 }; 342 void MakeTrimEdgesInto(SEdgeList *sel, int flags, SCurve *sc, STrimBy *stb); 343 void MakeEdgesInto(SShell *shell, SEdgeList *sel, int flags, 344 SShell *useCurvesFrom=NULL); 345 346 Vector ExactSurfaceTangentAt(Vector p, SSurface *srfA, SSurface *srfB, 347 Vector dir); 348 void MakeSectionEdgesInto(SShell *shell, SEdgeList *sel, SBezierList *sbl); 349 void MakeClassifyingBsp(SShell *shell, SShell *useCurvesFrom); 350 double ChordToleranceForEdge(Vector a, Vector b); 351 void MakeTriangulationGridInto(List<double> *l, double vs, double vf, 352 bool swapped); 353 Vector PointAtMaybeSwapped(double u, double v, bool swapped); 354 355 void Reverse(void); 356 void Clear(void); 357 }; 358 359 class SShell { 360 public: 361 IdList<SCurve,hSCurve> curve; 362 IdList<SSurface,hSSurface> surface; 363 364 bool booleanFailed; 365 366 void MakeFromExtrusionOf(SBezierLoopSet *sbls, Vector t0, Vector t1, 367 RgbaColor color); 368 void MakeFromRevolutionOf(SBezierLoopSet *sbls, Vector pt, Vector axis, 369 RgbaColor color, Group *group); 370 371 void MakeFromUnionOf(SShell *a, SShell *b); 372 void MakeFromDifferenceOf(SShell *a, SShell *b); 373 enum { 374 AS_UNION = 10, 375 AS_DIFFERENCE = 11, 376 AS_INTERSECT = 12 377 }; 378 void MakeFromBoolean(SShell *a, SShell *b, int type); 379 void CopyCurvesSplitAgainst(bool opA, SShell *agnst, SShell *into); 380 void CopySurfacesTrimAgainst(SShell *sha, SShell *shb, SShell *into, 381 int type); 382 void MakeIntersectionCurvesAgainst(SShell *against, SShell *into); 383 void MakeClassifyingBsps(SShell *useCurvesFrom); 384 void AllPointsIntersecting(Vector a, Vector b, List<SInter> *il, 385 bool seg, bool trimmed, bool inclTangent); 386 void MakeCoincidentEdgesInto(SSurface *proto, bool sameNormal, 387 SEdgeList *el, SShell *useCurvesFrom); 388 void RewriteSurfaceHandlesForCurves(SShell *a, SShell *b); 389 void CleanupAfterBoolean(void); 390 391 // Definitions when classifying regions of a surface; it is either inside, 392 // outside, or coincident (with parallel or antiparallel normal) with a 393 // shell. 394 enum { 395 INSIDE = 100, 396 OUTSIDE = 200, 397 COINC_SAME = 300, 398 COINC_OPP = 400 399 }; 400 static const double DOTP_TOL; 401 int ClassifyRegion(Vector edge_n, Vector inter_surf_n, Vector edge_surf_n); 402 bool ClassifyEdge(int *indir, int *outdir, 403 Vector ea, Vector eb, 404 Vector p, 405 Vector edge_n_in, Vector edge_n_out, Vector surf_n); 406 407 void MakeFromCopyOf(SShell *a); 408 void MakeFromTransformationOf(SShell *a, 409 Vector trans, Quaternion q, double scale); 410 void MakeFromAssemblyOf(SShell *a, SShell *b); 411 void MergeCoincidentSurfaces(void); 412 413 void TriangulateInto(SMesh *sm); 414 void MakeEdgesInto(SEdgeList *sel); 415 void MakeSectionEdgesInto(Vector n, double d, 416 SEdgeList *sel, SBezierList *sbl); 417 bool IsEmpty(void); 418 void RemapFaces(Group *g, int remap); 419 void Clear(void); 420 }; 421 422 #endif 423 424