HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups 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  /// Return the axis (or one of the axes) with the appropriate sign along
69  /// which the bounding oriented box is tangent to the convex hull of the
70  /// point set.
72  {
73  if (myYPivot0Tangent)
74  return UT_Vector2T<T>(myBasis(0, 0), myBasis(0, 1));
75  if (myYPivot1Tangent)
76  return UT_Vector2T<T>(-myBasis(0, 0), -myBasis(0, 1));
77  if (myXPivot1Tangent)
78  return UT_Vector2T<T>(myBasis(1, 0), myBasis(1, 1));
79  return UT_Vector2T<T>(-myBasis(1, 0), -myBasis(1, 1));
80  }
81 
82  // Fill the indices of the points of tangency. Returns the mask
83  // indicating at which ones the bounding box is tangent to an edge of
84  // the convex hull. (0th bit for x0, 1st bit for x1, etc).
85  int getSupportPoints(int &x0, int &x1,
86  int &y0, int &y1) const;
87 
88  bool operator==(const UT_OBBox2DT<T> &obb) const;
89  bool operator!=(const UT_OBBox2DT<T> &obb) const
90  {
91  return !(*this == obb);
92  }
93 
94  bool isEqual(const UT_OBBox2DT<T> &obb,
95  T tolerance = T(SYS_FTOLERANCE)) const;
96 
97 protected:
98  void calcOBB(const UT_Array<UT_Vector2T<T> > &points,
99  T tol, T bd_advantage);
100 
104 
105  int myXPivot0, myXPivot1, myYPivot0, myYPivot1;
106  bool myXPivot0Tangent, myXPivot1Tangent;
107  bool myYPivot0Tangent, myYPivot1Tangent;
108 
109 private:
110 
111  class Caliper
112  {
113  public:
114  Caliper(int num_vertices,
115  int p0, UT_Vector2T<T> l0,
116  int p1, UT_Vector2T<T> l1);
117 
118  // The caliper tracks two vertices (pivots) of the polygon tangent to
119  // its two supporting lines (even though it is possible for one or both
120  // of the lines to overlap edges the polygon).
121  inline int getPivot0() const { return myPivot0; }
122  inline int getPivot1() const { return myPivot1; }
123 
124 
125  // For each of the the min and max supporting vertex indices, the caliper
126  // holds the direction of the outgoing edge out of that vertex. These
127  // *limit* directions are used to limit the rotation of the caliper forward.
128  UT_Vector2T<T> getLimit0() const { return myLimit0; }
129  UT_Vector2T<T> getLimit1() const { return myLimit1; }
130 
131  // The caliper knows the number of points around the polygon (num_idxs
132  // passed to the constructor) and can can advance each of the supporting
133  // vertex indices it holds.
134 
135  inline void advancePivot0(UT_Vector2T<T> new_limit);
136  inline void advancePivot1(UT_Vector2T<T> new_limit);
137 
138  // rotationRoom() returns a real value which for *any* set of two parallel
139  // lines supporting our convex polygon and passing through our pivots
140  // indicate that a clockwise rotation will sooner hit
141  // the min limit direction if the returned value is positive,
142  // the max limit direction if the returned value is negative, or
143  // both limit directions if the returned value is zero.
144  //
145  // NB. This measure uses an exact geometry predicate which means it can be
146  // use very reliably to make a robust algorithmic decision.
147 
148  inline T rotationRoom() const;
149 
150  UT_Vector2T<T> getAxis() const { return myAxis; }
151  void setAxis(UT_Vector2T<T> a) { myAxis = a; }
152 
153  private:
154  int myNumVertices, myPivot0, myPivot1;
155  UT_Vector2T<T> myLimit0, myLimit1, myAxis;
156  };
157 
158  // OrthoCalipers encapsulates the idea of two calipers around the same
159  // convex polygon whose lines are mutually orthogonal to each other.
160  //
161 
162  class OrthoCalipers
163  {
164  public:
165  OrthoCalipers(int num_idxs,
166  int xp0, UT_Vector2T<T> xl0,
167  int xp1, UT_Vector2T<T> xl1,
168  int yp0, UT_Vector2T<T> yl0,
169  int yp1, UT_Vector2T<T> yl1);
170 
171  // rotate calipers while maintaining them orthogonal by the smallest
172  // possible amount around the current pivots until one of the supporting
173  // lines becomes tangent to an edge of the polygon (this would also be the
174  // largest possible amount before one of the calipers intersects the
175  // interior of the polygon. Returns the number of pivots that advance.
176  int rotate(UT_Vector2T<T> xl0, UT_Vector2T<T> xl1,
177  UT_Vector2T<T> yl0, UT_Vector2T<T> yl1);
178 
179  void getAxes(UT_Vector2T<T> &x, UT_Vector2T<T> &y) const;
180  void getPivots(int &xp0, int &xp1, int &yp0, int &yp1) const;
181 
182  bool isTangentAtX0() { return myXTangent0; }
183  bool isTangentAtX1() { return myXTangent1; }
184  bool isTangentAtY0() { return myYTangent0; }
185  bool isTangentAtY1() { return myYTangent1; }
186 
187  private:
188  Caliper myXCaliper, myYCaliper;
189  bool myXTangent0, myXTangent1, myYTangent0, myYTangent1;
190  };
191 };
192 
193 
194 /// Auxiliary function to compute the convex hull of a set of points in 2D.
195 /// Unlike the implementation in UT_QuickHull, this is a robust implementation
196 /// of Fortune's algorithm using exact predicates. Robustness implies that the
197 /// resulting convex hull passes the counter-clockwise test with infinite
198 /// precision for any edge of the convex hull and a third point in the input set.
199 ///
200 /// The output of the algorithm is the indices of the points that appear on
201 /// the boundary of the convex hull in the order they do.
202 ///
203 /// If set to false, the optional parameter 'exclude_on_edge_pts' makes the
204 /// algorithm return points that lie along the interior of convex hull
205 /// edges in the output sequence. Otherwise, only strict convex hull vertices
206 /// are returned, i.e. those that cannot be written as nontrivial convex
207 /// combinations of other points.
208 ///
209 /// The return value is the index of a convex hull point p1 which together
210 /// with the first point p0 in the generated convex hull, have the property
211 /// that the entire convex hull projects to the line p0p1 between p0 and p1.
212 
213 template <typename T>
214 UT_API int UTconvexHull2D(const UT_Array< UT_Vector2T<T> > &pts,
215  UT_IntArray &hull,
216  bool exclude_on_edge_pts = true);
217 
218 
222 
223 #endif
UT_OBBox2DT< fpreal > UT_OBBox2DR
Definition: UT_OBBox2D.h:219
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
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
#define UT_API
Definition: UT_API.h:13
GLint y
Definition: glcorearb.h:102
bool operator!=(const UT_OBBox2DT< T > &obb) const
Definition: UT_OBBox2D.h:89
2D Vector class.
Definition: UT_Vector2.h:138
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
UT_OBBox2DT< fpreal32 > UT_OBBox2DF
Definition: UT_OBBox2D.h:220
UT_OBBox2DT< fpreal64 > UT_OBBox2DD
Definition: UT_OBBox2D.h:221
UT_Vector2T< T > myCenter
Definition: UT_OBBox2D.h:102
UT_Vector2T< T > getMaxAxis() const
Return the non-oriented bounding box.
Definition: UT_OBBox2D.h:62
bool myXPivot1Tangent
Definition: UT_OBBox2D.h:106
GT_Basis myBasis
Definition: GT_CurveEval.h:262
UT_Vector2T< T > myRadii
Definition: UT_OBBox2D.h:103
GLint GLenum GLint x
Definition: glcorearb.h:408
#define SYS_FTOLERANCE
Definition: SYS_Types.h:203
UT_Vector2T< T > getTangentAxis() const
Definition: UT_OBBox2D.h:71
UT_Matrix2T< T > myBasis
Definition: UT_OBBox2D.h:101
bool myYPivot1Tangent
Definition: UT_OBBox2D.h:107
UT_Vector2T< T > getCenter() const
Return the center of the OBB.
Definition: UT_OBBox2D.h:52