HDK
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 public:
23  UT_QuickHullT();
24  virtual ~UT_QuickHullT();
25
26  /// Clear out points
27  void reset() { myPoints.entries(0); }
28
29  /// Add a point to the hull
30  void append(const UT_Vector3T<T> &P);
31
32  /// Compute the 2D convex hull area relative to the given plane normal.
33  T area2D(const UT_Vector3T<T> &N) const;
34
35  /// Return set of points that formed a convex hull based on the given plane
36  /// defined by the normal
37  void getQuickHull(UT_ValArray<UT_Vector2T<T> > &points,
38  const UT_Vector3T<T> &N) const;
39  /// Return set of points that formed a convex hull based on the given plane
40  /// defined by the two vectors. (X and Y are assumed to be orthogonal)
41  void getQuickHull(UT_ValArray<UT_Vector2T<T> > &points,
42  const UT_Vector3T<T> &X,
43  const UT_Vector3T<T> &Y) const;
44  /// Return the area and rotation of mininul bounding rectangle of the
45  /// projection of the points on to the given plane.
46  T getMinRectangle(const UT_Vector3T<T> &X,
47  const UT_Vector3T<T> &Y, T &rot) const;
48
49 protected:
50  static inline void swap2(UT_Vector2T<T> *list, uint a, uint b);
51  static inline void makeLineEqn(UT_Vector3T<T> &eqn,
52  const UT_Vector2T<T> *list,
53  uint a, uint b);
54  static uint quickHullSelect(UT_Vector2T<T> *list, uint a,
55  uint b, uint &cidx);
56  static T quickHull(UT_Vector2T<T> *list, uint a, uint b, uint c);
57  static void getQuickHullInternal(UT_ValArray<UT_Vector2T<T> > &points,
58  UT_Vector2T<T> *list, uint a,
59  uint b, uint c);
60  static T getMinRectInternal(const UT_ValArray<UT_Vector2T<T> > &points,
61  T &rot);
62
64 };
65
69 typedef UT_QuickHullT<float> UT_QuickHull; // deprecated
70
71 template <typename T>
72 inline void
74 {
75  UT_Vector2T<T> tmp = list[a];
76  list[a] = list[b];
77  list[b] = tmp;
78 }
79
80 template <typename T>
81 inline void
83  uint a, uint b)
84 {
85  eqn.x() = list[a].y() - list[b].y();
86  eqn.y() = list[b].x() - list[a].x();
87  eqn.z() = -(eqn.x()*list[a].x() + eqn.y()*list[a].y());
88 }
89
90 #endif
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
UT_Array< UT_Vector3T< T > > myPoints
Definition: UT_QuickHull.h:63
const GLfloat * c
Definition: glew.h:16631
GA_API const UT_StringHolder rot
#define UT_API
Definition: UT_API.h:14
static void swap2(UT_Vector2T< T > *list, uint a, uint b)
Definition: UT_QuickHull.h:73
static void makeLineEqn(UT_Vector3T< T > &eqn, const UT_Vector2T< T > *list, uint a, uint b)
Definition: UT_QuickHull.h:82
3D Vector class.
2D Vector class.
Definition: UT_Vector2.h:149
UT_QuickHullT< fpreal32 > UT_QuickHullF
Definition: UT_QuickHull.h:67
UT_QuickHullT< fpreal64 > UT_QuickHullD
Definition: UT_QuickHull.h:68
SYS_FORCE_INLINE T & y()
Definition: UT_Vector3.h:508
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
SYS_FORCE_INLINE T & z()
Definition: UT_Vector3.h:510
void reset()
Clear out points.
Definition: UT_QuickHull.h:27
UT_QuickHullT< fpreal > UT_QuickHullR
Definition: UT_QuickHull.h:66
GLuint GLdouble GLdouble GLint GLint const GLdouble * points
Definition: glew.h:3460
GLfloat eqn[4]
Definition: glew.h:15593
GA_API const UT_StringHolder N
UT_QuickHullT< float > UT_QuickHull
Definition: UT_QuickHull.h:69
SYS_FORCE_INLINE T & x()
Definition: UT_Vector3.h:506
unsigned int uint
Definition: SYS_Types.h:45