HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_Convex.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_Convex.h ( UT Library, C++)
7  *
8  * COMMENTS: This code does general polygon convexing. It's down here
9  * in UT since there are places other than the GEO lib which
10  * may need to use convexing code (i.e. the RE lib, or UI).
11  * This code convexes 2D polygons.
12  */
13 
14 #ifndef __UT_Convex__
15 #define __UT_Convex__
16 
17 #include "UT_API.h"
18 #include "UT_Vector3.h"
19 #include <SYS/SYS_Types.h>
20 #include <stdlib.h>
21 
22 class UT_ConvexPoint;
23 class UT_Interrupt;
24 
26 public:
28  {
29  myData = 0;
30  myConvexInfo = 0;
31  myConvexSize = 0;
32  myConvexEntries = 0;
33  myPointList = 0;
34  myPointSize = 0;
35  }
36  virtual ~UT_Convex()
37  {
38  if (myConvexInfo) free(myConvexInfo);
39  if (myPointList) free(myPointList);
40  }
41 
42  bool isConcave();
43  void convex(exint maxsides, bool allowinterrupt = true,
44  bool avoiddegeneracy = false);
45 
46  virtual void initialize();
47  /// It's the sub-class responsibility to fill these out...
48  virtual int getPointCount() const = 0;
49  virtual void getPoint(int num, float &x, float &y) const = 0;
50 
51  /// beginPolygon will be told when the last polygon is being added
52  virtual void beginPolygon(int npoints, bool lastone) = 0;
53  virtual void polyVertex(int num) = 0;
54  virtual void endPolygon() = 0;
55 
56  /// If the last polygon to be added won't be added after all, e.g. if it is
57  /// degenerate and avoiddegeneracy is true, the earlyTermination() method
58  /// will be called. This is so that the caller can clean up properly, since
59  /// beginPolygon will *not* have been called with lastone==true.
60  /// By default, this method does nothing.
61  virtual void earlyTermination();
62 
63  /// Returns true if splitting the specified quad along the line from
64  /// point 0 to point 2 is possible
65  static inline bool canSplitQuad02(const UT_Vector3 &p0,
66  const UT_Vector3 &p1,
67  const UT_Vector3 &p2,
68  const UT_Vector3 &p3)
69  {
70  const UT_Vector3 v0 = p1 - p0;
71  const UT_Vector3 v1 = p2 - p1;
72  const UT_Vector3 v2 = p3 - p2;
73  const UT_Vector3 v3 = p0 - p3;
74  // Okay if normals at 1 and 3 point in the same direction
75  return ((cross(v0, v1)).dot(cross(v2, v3)) > 0);
76  }
77 
78  /// Returns true if the specified quad is convex.
79  /// NOTE: This may return false negatives for highly non-planar quads,
80  /// since the definition of convex breaks down.
81  static inline bool isQuadConvex(const UT_Vector3 &p0,
82  const UT_Vector3 &p1,
83  const UT_Vector3 &p2,
84  const UT_Vector3 &p3)
85  {
86  const UT_Vector3 v0 = p1 - p0;
87  const UT_Vector3 v1 = p2 - p1;
88  const UT_Vector3 v2 = p3 - p2;
89  const UT_Vector3 v3 = p0 - p3;
90  // Convex if normals at 1 and 3 point in the same direction
91  // and normals at 0 and 2 point in the same direction
92  return (cross(v0, v1).dot(cross(v2, v3)) > 0)
93  && (cross(v1, v2).dot(cross(v3, v0)) > 0);
94  }
95 
96  virtual int64 getMemoryUsage(bool inclusive) const;
97 
98 private:
99  UT_ConvexPoint *polySetup(bool avoiddegeneracy);
100  int leftOrRight(int v1, int v2, int v3, bool &double_back);
101  int leftOrRight(int v1, int v2, int v3)
102  {
103  bool double_back;
104  return leftOrRight(v1, v2, v3, double_back);
105  }
106  uint leftMost(uint a, uint b, int ccwise);
107  bool testConcave(uint first, uint last);
108  bool arePointsSame(uint i, uint j);
109  bool isDegenerate(uint first, uint last);
110  bool addPolygon(
111  UT_Interrupt *boss, uint first,
112  uint last, bool lastone,
113  bool avoiddegeneracy);
114  void addTriangle(uint a, uint b, uint c,
115  bool lastone);
116  void doSplit(uint first, uint newfirst,
117  uint newlast, uint last);
118  bool cornerTest(int side, uint la, uint lb,
119  uint first, uint last);
120  bool insideOut(uint k, uint la,
121  uint lb, uint first, uint last);
122  uint chooseCoincidentIntruder(
123  uint l, uint k1, uint k2,
124  uint first, uint last, uint ccwise);
125  uint findClosestInRange(uint lb, uint la,
126  uint ls, uint first, uint last);
127  uint testIntersect(uint l, uint lb, uint la,
128  uint first, uint last, int &ccwise);
129 
130 protected:
131  /// NOTE: You *must* set myData to NULL before
132  /// calling isConcave() or convex() !
133  UT_ConvexPoint *myData;
134 
135 private:
136  UT_ConvexPoint *myConvexInfo;
137  uint myConvexSize;
138  uint myConvexEntries;
139  int *myPointList;
140  uint myPointSize;
141 
142  /// NOTE: The only purpose of this bool is because isConvex() must call
143  /// polySetup(true), so if there were degenerate points and
144  /// convex(__, __, false) is then called, it needs to know to call
145  /// polySetup(false) to get those omitted points.
146  bool myAvoidDegeneracyPrev;
147 };
148 
149 #endif
150 
GLint first
Definition: glcorearb.h:404
static bool isQuadConvex(const UT_Vector3 &p0, const UT_Vector3 &p1, const UT_Vector3 &p2, const UT_Vector3 &p3)
Definition: UT_Convex.h:81
SIM_DerScalar dot(const SIM_DerVector3 &rhs) const
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
#define UT_API
Definition: UT_API.h:13
GLint y
Definition: glcorearb.h:102
UT_Convex()
Definition: UT_Convex.h:27
GLfloat GLfloat GLfloat v2
Definition: glcorearb.h:817
GLfloat GLfloat GLfloat GLfloat v3
Definition: glcorearb.h:818
png_uint_32 i
Definition: png.h:2877
long long int64
Definition: SYS_Types.h:107
int64 exint
Definition: SYS_Types.h:116
fpreal64 dot(const CE_VectorT< T > &a, const CE_VectorT< T > &b)
Definition: CE_Vector.h:218
UT_ConvexPoint * myData
Definition: UT_Convex.h:133
OPENVDB_API void initialize()
Global registration of basic types.
Definition: logging.h:318
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
unsigned int uint
Definition: SYS_Types.h:40
virtual ~UT_Convex()
Definition: UT_Convex.h:36
GLfloat v0
Definition: glcorearb.h:815
GLint GLenum GLint x
Definition: glcorearb.h:408
GLfloat GLfloat v1
Definition: glcorearb.h:816
png_infop png_uint_32 int num
Definition: png.h:2158
static bool canSplitQuad02(const UT_Vector3 &p0, const UT_Vector3 &p1, const UT_Vector3 &p2, const UT_Vector3 &p3)
Definition: UT_Convex.h:65
SIM_DerVector3 cross(const SIM_DerVector3 &lhs, const SIM_DerVector3 &rhs)