HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_OBBox2D.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_OBBox.h ( UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_OBBox2D_h__
12 #define __UT_OBBox2D_h__
13 
14 #include "UT_API.h"
15 #include "UT_Matrix2.h"
16 #include "UT_Vector2.h"
17 
18 template<typename T>
19 class UT_Array;
20 
21 template <typename T>
23 {
24 public:
25 
26  /// points is an array of 2d vectors and tol is the tolerance parameter tol
27  /// allows the returned answer to be (1 + tol) larger than the smallest
28  /// possible. The returned answer will then be the oriented bounding box
29  /// "last" encountered which is up to (1 + tol) larger than the best found
30  /// box. This can be useful for avoiding rapid changes to the result when
31  /// input positions are only slightly perturbed.
32  /// The bd_advantage can be useful when the points list the edges of a
33  /// polygon in order. If bd_advantage is nonzero, then the area of an
34  /// oriented bounding box that is tangent to a boundary edge of the
35  /// input polygon (consecutive points in the array) is regarded as
36  /// multiplied by (1.0 - bd_advantage). This prioritizes solutions that
37  /// though suboptimal are close enough to the optimal and align with an
38  /// input edge when that is preferred.
39  ///
40  /// NB. tol and bd_advantage my fight each other. Make sure you
41  /// pick a larger values for more important one.
42 
43  UT_OBBox2DT(const UT_Array<UT_Vector2T<T> > &points,
44  T tol = 0.05,
45  T bd_advantage = 0.0);
46 
47  /// Return the basis that defines the orientation of the OBB
48  UT_Matrix2T<T> getBasis() const {return myBasis;}
49  /// Return the half radii(side length) of the OBB
50  UT_Vector2T<T> getRadii() const {return myRadii;}
51  /// Return the center of the OBB
52  UT_Vector2T<T> getCenter() const {return myCenter;}
53 
54  /// Return the non-oriented bounding box.
56  {
57  int imin = SYSargmin(myRadii.x(), myRadii.y());
58  return UT_Vector2T<T>(myBasis(imin, 0), myBasis(imin, 1));
59  }
60 
61  /// Return the non-oriented bounding box.
63  {
64  int imax = SYSargmax(myRadii.x(), myRadii.y());
65  return UT_Vector2T<T>(myBasis(imax, 0), myBasis(imax, 1));
66  }
67 
68  void getSupportPoints(int &x0, int &x1,
69  int &y0, int &y1) const;
70 
71  bool operator==(const UT_OBBox2DT<T> &obb) const;
72  bool operator!=(const UT_OBBox2DT<T> &obb) const
73  {
74  return !(*this == obb);
75  }
76 
77  bool isEqual(const UT_OBBox2DT<T> &obb,
78  T tolerance = T(SYS_FTOLERANCE)) const;
79 
80 protected:
81  void calcOBB(const UT_Array<UT_Vector2T<T> > &points,
82  T tol, T bd_advantage);
83 
87 
88  int myXPivot0, myXPivot1, myYPivot0, myYPivot1;
89 
90 private:
91 
92  class Caliper
93  {
94  public:
95  Caliper(int num_vertices,
96  int p0, UT_Vector2T<T> l0,
97  int p1, UT_Vector2T<T> l1);
98 
99  // The caliper tracks two vertices (pivots) of the polygon tangent to
100  // its two supporting lines (even though it is possible for one or both
101  // of the lines to overlap edges the polygon).
102  inline int getPivot0() const { return myPivot0; }
103  inline int getPivot1() const { return myPivot1; }
104 
105 
106  // For each of the the min and max supporting vertex indices, the caliper
107  // holds the direction of the outgoing edge out of that vertex. These
108  // *limit* directions are used to limit the rotation of the caliper forward.
109  UT_Vector2T<T> getLimit0() const { return myLimit0; }
110  UT_Vector2T<T> getLimit1() const { return myLimit1; }
111 
112  // The caliper knows the number of points around the polygon (num_idxs
113  // passed to the constructor) and can can advance each of the supporting
114  // vertex indices it holds.
115 
116  inline void advancePivot0(UT_Vector2T<T> new_limit);
117  inline void advancePivot1(UT_Vector2T<T> new_limit);
118 
119  // rotationRoom() returns a real value which for *any* set of two parallel
120  // lines supporting our convex polygon and passing through our pivots
121  // indicate that a clockwise rotation will sooner hit
122  // the min limit direction if the returned value is positive,
123  // the max limit direction if the returned value is negative, or
124  // both limit directions if the returned value is zero.
125  //
126  // NB. This measure uses an exact geometry predicate which means it can be
127  // use very reliably to make a robust algorithmic decision.
128 
129  inline T rotationRoom() const;
130 
131  UT_Vector2T<T> getAxis() const { return myAxis; }
132  void setAxis(UT_Vector2T<T> a) { myAxis = a; }
133 
134  private:
135  int myNumVertices, myPivot0, myPivot1;
136  UT_Vector2T<T> myLimit0, myLimit1, myAxis;
137  };
138 
139  // OrthoCalipers encapsulates the idea of two calipers around the same
140  // convex polygon whose lines are mutually orthogonal to each other.
141  //
142 
143  class OrthoCalipers
144  {
145  public:
146  OrthoCalipers(int num_idxs,
147  int xp0, UT_Vector2T<T> xl0,
148  int xp1, UT_Vector2T<T> xl1,
149  int yp0, UT_Vector2T<T> yl0,
150  int yp1, UT_Vector2T<T> yl1);
151 
152  // rotate calipers while maintaining them orthogonal by the smallest
153  // possible amount around the current pivots until one of the supporting
154  // lines becomes tangent to an edge of the polygon (this would also be the
155  // largest possible amount before one of the calipers intersects the
156  // interior of the polygon. Returns the number of pivots that advance.
157  int rotate(UT_Vector2T<T> xl0, UT_Vector2T<T> xl1,
158  UT_Vector2T<T> yl0, UT_Vector2T<T> yl1);
159 
160  void getAxes(UT_Vector2T<T> &x, UT_Vector2T<T> &y) const;
161  void getPivots(int &xp0, int &xp1, int &yp0, int &yp1) const;
162 
163  bool isTangentAtX0() { return myXTangent0; }
164  bool isTangentAtX1() { return myXTangent1; }
165  bool isTangentAtY0() { return myYTangent0; }
166  bool isTangentAtY1() { return myYTangent1; }
167 
168  private:
169  Caliper myXCaliper, myYCaliper;
170  bool myXTangent0, myXTangent1, myYTangent0, myYTangent1;
171  };
172 };
173 
174 
175 /// Auxiliary function to compute the convex hull of a set of points in 2D.
176 /// Unlike the implementation in UT_QuickHull, this is a robust implementation
177 /// of Fortune's algorithm using exact predicates. Robustness implies that the
178 /// resulting convex hull passes the counter-clockwise test with infinite
179 /// precision for any edge of the convex hull and a third point in the input set.
180 ///
181 /// The output of the algorithm is the indices of the points that appear on
182 /// the boundary of the convex hull in the order they do.
183 ///
184 /// If set to false, the optional parameter 'exclude_on_edge_pts' makes the
185 /// algorithm return points that lie along the interior of convex hull
186 /// edges in the output sequence. Otherwise, only strict convex hull vertices
187 /// are returned, i.e. those that cannot be written as nontrivial convex
188 /// combinations of other points.
189 ///
190 /// The return value is the index of a convex hull point p1 which together
191 /// with the first point p0 in the generated convex hull, have the property
192 /// that the entire convex hull projects to the line p0p1 between p0 and p1.
193 
194 template <typename T>
195 UT_API int UTconvexHull2D(const UT_Array< UT_Vector2T<T> > &pts,
196  UT_IntArray &hull,
197  bool exclude_on_edge_pts = true);
198 
199 
203 
204 #endif
UT_OBBox2DT< fpreal > UT_OBBox2DR
Definition: UT_OBBox2D.h:200
UT_Vector2T< T > getMinAxis() const
Return the non-oriented bounding box.
Definition: UT_OBBox2D.h:55
UT_API int UTconvexHull2D(const UT_Array< UT_Vector2T< T > > &pts, UT_IntArray &hull, bool exclude_on_edge_pts=true)
UT_Vector2T< T > getRadii() const
Return the half radii(side length) of the OBB.
Definition: UT_OBBox2D.h:50
UT_Matrix2T< T > getBasis() const
Return the basis that defines the orientation of the OBB.
Definition: UT_OBBox2D.h:48
int myYPivot1
Definition: UT_OBBox2D.h:88
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
#define UT_API
Definition: UT_API.h:12
GLint y
Definition: glcorearb.h:102
bool operator!=(const UT_OBBox2DT< T > &obb) const
Definition: UT_OBBox2D.h:72
2D Vector class.
Definition: UT_Vector2.h:137
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
UT_OBBox2DT< fpreal32 > UT_OBBox2DF
Definition: UT_OBBox2D.h:201
UT_OBBox2DT< fpreal64 > UT_OBBox2DD
Definition: UT_OBBox2D.h:202
UT_Vector2T< T > myCenter
Definition: UT_OBBox2D.h:85
UT_Vector2T< T > getMaxAxis() const
Return the non-oriented bounding box.
Definition: UT_OBBox2D.h:62
GT_Basis myBasis
Definition: GT_CurveEval.h:262
UT_Vector2T< T > myRadii
Definition: UT_OBBox2D.h:86
GLint GLenum GLint x
Definition: glcorearb.h:408
#define SYS_FTOLERANCE
Definition: SYS_Types.h:196
UT_Matrix2T< T > myBasis
Definition: UT_OBBox2D.h:84
UT_Vector2T< T > getCenter() const
Return the center of the OBB.
Definition: UT_OBBox2D.h:52