HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_QuickHull.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_QuickHull.h ( UT Library, C++)
7  *
8  * COMMENTS: This class is used to compute the convex hull area from a
9  * list of points.
10  */
11 
12 #ifndef __UT_QuickHull__
13 #define __UT_QuickHull__
14 
15 #include "UT_API.h"
16 #include "UT_Array.h"
17 #include "UT_Vector2.h"
18 #include "UT_Vector3.h"
19 
20 template <typename T>
22 {
23 public:
24 
25  /// Clear out points
26  void reset() { myPoints.entries(0); }
27 
28  /// Add a point to the hull
29  void append(const UT_Vector3T<T> &P);
30 
31  /// Compute the 2D convex hull area relative to the given plane normal.
32  T area2D(const UT_Vector3T<T> &N) const;
33 
34  /// Return set of points that formed a convex hull based on the given plane
35  /// defined by the normal
36  void getQuickHull(UT_ValArray<UT_Vector2T<T> > &points,
37  const UT_Vector3T<T> &N) const;
38  /// Return set of points that formed a convex hull based on the given plane
39  /// defined by the two vectors. (X and Y are assumed to be orthogonal)
40  void getQuickHull(UT_ValArray<UT_Vector2T<T> > &points,
41  const UT_Vector3T<T> &X,
42  const UT_Vector3T<T> &Y) const;
43  /// Return the area and rotation of mininul bounding rectangle of the
44  /// projection of the points on to the given plane.
45  T getMinRectangle(const UT_Vector3T<T> &X,
46  const UT_Vector3T<T> &Y, T &rot) const;
47 
48 protected:
49  static inline void swap2(UT_Vector2T<T> *list, uint a, uint b);
50  static inline void makeLineEqn(UT_Vector3T<T> &eqn,
51  const UT_Vector2T<T> *list,
52  uint a, uint b);
53  static uint quickHullSelect(UT_Vector2T<T> *list, uint a,
54  uint b, uint &cidx);
55  static T quickHull(UT_Vector2T<T> *list, uint a, uint b, uint c);
56  static void getQuickHullInternal(UT_ValArray<UT_Vector2T<T> > &points,
57  UT_Vector2T<T> *list, uint a,
58  uint b, uint c);
59  static T getMinRectInternal(const UT_ValArray<UT_Vector2T<T> > &points,
60  T &rot);
61 
63 };
64 
68 typedef UT_QuickHullT<float> UT_QuickHull; // deprecated
69 
70 template <typename T>
71 inline void
73 {
74  UT_Vector2T<T> tmp = list[a];
75  list[a] = list[b];
76  list[b] = tmp;
77 }
78 
79 template <typename T>
80 inline void
82  uint a, uint b)
83 {
84  eqn.x() = list[a].y() - list[b].y();
85  eqn.y() = list[b].x() - list[a].x();
86  eqn.z() = -(eqn.x()*list[a].x() + eqn.y()*list[a].y());
87 }
88 
89 #endif
GLdouble GLdouble GLint GLint const GLdouble * points
Definition: glad.h:2676
UT_Array< UT_Vector3T< T > > myPoints
Definition: UT_QuickHull.h:62
GA_API const UT_StringHolder rot
constexpr SYS_FORCE_INLINE T & z() noexcept
Definition: UT_Vector3.h:667
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
#define UT_API
Definition: UT_API.h:14
static void swap2(UT_Vector2T< T > *list, uint a, uint b)
Definition: UT_QuickHull.h:72
static void makeLineEqn(UT_Vector3T< T > &eqn, const UT_Vector2T< T > *list, uint a, uint b)
Definition: UT_QuickHull.h:81
3D Vector class.
2D Vector class.
Definition: UT_Vector2.h:159
UT_QuickHullT< fpreal32 > UT_QuickHullF
Definition: UT_QuickHull.h:66
constexpr SYS_FORCE_INLINE T & x() noexcept
Definition: UT_Vector2.h:423
UT_QuickHullT< fpreal64 > UT_QuickHullD
Definition: UT_QuickHull.h:67
void reset()
Clear out points.
Definition: UT_QuickHull.h:26
UT_QuickHullT< fpreal > UT_QuickHullR
Definition: UT_QuickHull.h:65
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
GA_API const UT_StringHolder N
UT_QuickHullT< float > UT_QuickHull
Definition: UT_QuickHull.h:68
constexpr SYS_FORCE_INLINE T & y() noexcept
Definition: UT_Vector3.h:665
unsigned int uint
Definition: SYS_Types.h:45
constexpr SYS_FORCE_INLINE T & y() noexcept
Definition: UT_Vector2.h:425
constexpr SYS_FORCE_INLINE T & x() noexcept
Definition: UT_Vector3.h:663