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_NonCopyable.h"
19 #include "UT_Vector3.h"
20 #include <SYS/SYS_Types.h>
21 #include <stdlib.h>
22 
23 class UT_ConvexPoint;
24 class UT_Interrupt;
25 
27 public:
29  {
30  myData = 0;
31  myConvexInfo = 0;
32  myConvexSize = 0;
33  myConvexEntries = 0;
34  myPointList = 0;
35  myPointSize = 0;
36  }
37  virtual ~UT_Convex()
38  {
39  if (myConvexInfo) free(myConvexInfo);
40  if (myPointList) free(myPointList);
41  }
42 
44 
45  bool isConcave();
46  void convex(exint maxsides, bool allowinterrupt = true,
47  bool avoiddegeneracy = false);
48 
49  virtual void initialize();
50  /// It's the sub-class responsibility to fill these out...
51  virtual int getPointCount() const = 0;
52  virtual void getPoint(int num, float &x, float &y) const = 0;
53 
54  /// beginPolygon will be told when the last polygon is being added
55  virtual void beginPolygon(int npoints, bool lastone) = 0;
56  virtual void polyVertex(int num) = 0;
57  virtual void endPolygon() = 0;
58 
59  /// If the last polygon to be added won't be added after all, e.g. if it is
60  /// degenerate and avoiddegeneracy is true, the earlyTermination() method
61  /// will be called. This is so that the caller can clean up properly, since
62  /// beginPolygon will *not* have been called with lastone==true.
63  /// By default, this method does nothing.
64  virtual void earlyTermination();
65 
66  /// Returns true if splitting the specified quad along the line from
67  /// point 0 to point 2 is possible
68  static inline bool canSplitQuad02(const UT_Vector3 &p0,
69  const UT_Vector3 &p1,
70  const UT_Vector3 &p2,
71  const UT_Vector3 &p3)
72  {
73  const UT_Vector3 v0 = p1 - p0;
74  const UT_Vector3 v1 = p2 - p1;
75  const UT_Vector3 v2 = p3 - p2;
76  const UT_Vector3 v3 = p0 - p3;
77  // Okay if normals at 1 and 3 point in the same direction
78  return ((cross(v0, v1)).dot(cross(v2, v3)) > 0);
79  }
80 
81  /// Returns true if the specified quad is convex.
82  /// NOTE: This may return false negatives for highly non-planar quads,
83  /// since the definition of convex breaks down.
84  static inline bool isQuadConvex(const UT_Vector3 &p0,
85  const UT_Vector3 &p1,
86  const UT_Vector3 &p2,
87  const UT_Vector3 &p3)
88  {
89  const UT_Vector3 v0 = p1 - p0;
90  const UT_Vector3 v1 = p2 - p1;
91  const UT_Vector3 v2 = p3 - p2;
92  const UT_Vector3 v3 = p0 - p3;
93  // Convex if normals at 1 and 3 point in the same direction
94  // and normals at 0 and 2 point in the same direction
95  return (cross(v0, v1).dot(cross(v2, v3)) > 0)
96  && (cross(v1, v2).dot(cross(v3, v0)) > 0);
97  }
98 
99  virtual int64 getMemoryUsage(bool inclusive) const;
100 
101 private:
102  UT_ConvexPoint *polySetup(bool avoiddegeneracy);
103  int leftOrRight(int v1, int v2, int v3, bool &double_back);
104  int leftOrRight(int v1, int v2, int v3)
105  {
106  bool double_back;
107  return leftOrRight(v1, v2, v3, double_back);
108  }
109  uint leftMost(uint a, uint b, int ccwise);
110  bool testConcave(uint first, uint last);
111  bool arePointsSame(uint i, uint j);
112  bool isDegenerate(uint first, uint last);
113  bool addPolygon(
114  UT_Interrupt *boss, uint first,
115  uint last, bool lastone,
116  bool avoiddegeneracy);
117  void addTriangle(uint a, uint b, uint c,
118  bool lastone);
119  void doSplit(uint first, uint newfirst,
120  uint newlast, uint last);
121  bool cornerTest(int side, uint la, uint lb,
122  uint first, uint last);
123  bool insideOut(uint k, uint la,
124  uint lb, uint first, uint last) const;
125  uint chooseCoincidentIntruder(
126  uint l, uint k1, uint k2,
127  uint first, uint last, uint ccwise);
128  uint findClosestInRange(uint lb, uint la,
129  uint ls, uint first, uint last);
130  uint testIntersect(uint l, uint lb, uint la,
131  uint first, uint last, int &ccwise);
132 
133 protected:
134  /// NOTE: You *must* set myData to NULL before
135  /// calling isConcave() or convex() !
136  UT_ConvexPoint *myData;
137 
138 private:
139  UT_ConvexPoint *myConvexInfo;
140  uint myConvexSize;
141  uint myConvexEntries;
142  int *myPointList;
143  uint myPointSize;
144 
145  /// NOTE: The only purpose of this bool is because isConvex() must call
146  /// polySetup(true), so if there were degenerate points and
147  /// convex(__, __, false) is then called, it needs to know to call
148  /// polySetup(false) to get those omitted points.
149  bool myAvoidDegeneracyPrev;
150 };
151 
152 #endif
153 
GLint first
Definition: glcorearb.h:405
static bool isQuadConvex(const UT_Vector3 &p0, const UT_Vector3 &p1, const UT_Vector3 &p2, const UT_Vector3 &p3)
Definition: UT_Convex.h:84
int64 exint
Definition: SYS_Types.h:125
SIM_DerScalar dot(const SIM_DerVector3 &rhs) const
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
#define UT_API
Definition: UT_API.h:14
GLint y
Definition: glcorearb.h:103
UT_Convex()
Definition: UT_Convex.h:28
GLfloat GLfloat GLfloat v2
Definition: glcorearb.h:818
GLfloat GLfloat GLfloat GLfloat v3
Definition: glcorearb.h:819
fpreal64 dot(const CE_VectorT< T > &a, const CE_VectorT< T > &b)
Definition: CE_Vector.h:140
#define UT_NON_COPYABLE(CLASS)
Define deleted copy constructor and assignment operator inside a class.
long long int64
Definition: SYS_Types.h:116
UT_ConvexPoint * myData
Definition: UT_Convex.h:136
OPENVDB_API void initialize()
Global registration of native Grid, Transform, Metadata and Point attribute types. Also initializes blosc (if enabled).
Definition: logging.h:294
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
GLint GLenum GLint x
Definition: glcorearb.h:409
virtual ~UT_Convex()
Definition: UT_Convex.h:37
GLfloat v0
Definition: glcorearb.h:816
GLint j
Definition: glad.h:2733
__hostdev__ uint64_t last(uint32_t i) const
Definition: NanoVDB.h:5976
GLfloat GLfloat v1
Definition: glcorearb.h:817
static bool canSplitQuad02(const UT_Vector3 &p0, const UT_Vector3 &p1, const UT_Vector3 &p2, const UT_Vector3 &p3)
Definition: UT_Convex.h:68
unsigned int uint
Definition: SYS_Types.h:45
SIM_DerVector3 cross(const SIM_DerVector3 &lhs, const SIM_DerVector3 &rhs)