HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GEO_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: GEO_Convex.h (GEO Library, C++)
7  *
8  * COMMENTS: Functions for convexing without modifying polygons
9  */
10 
11 #pragma once
12 
13 #ifndef __GEO_Convex__
14 #define __GEO_Convex__
15 
16 #include <GA/GA_Types.h>
17 #include <UT/UT_Array.h>
18 #include <UT/UT_Convex.h>
19 #include <UT/UT_OBBox.h>
20 #include <UT/UT_Vector3.h>
21 #include <SYS/SYS_Inline.h>
22 
23 template<typename T>
24 struct GEO_TriOrQuadT
25 {
27  GEO_TriOrQuadT(T v0, T v1, T v2, T v3=T(-1))
28  {
29  vertices[0] = v0;
30  vertices[1] = v1;
31  vertices[2] = v2;
32  vertices[3] = v3;
33  }
35  {
36  vertices[0] = T(-1);
37  vertices[1] = T(-1);
38  vertices[2] = T(-1);
39  vertices[3] = T(-1);
40  }
42  { vertices[3] = T(-1); }
43  SYS_FORCE_INLINE bool isTri() const
44  { return vertices[3] == T(-1); }
45 
46  T vertices[4];
47 };
49 
50 template<typename POLY>
52 public:
53  GEO_TriOrQuadWrapper(const POLY &poly, const GEO_TriOrQuad &convex)
54  : myPoly(poly)
55  , myConvex(convex)
56  {}
58  { return myConvex.isTri() ? 3 : 4; }
60  { return myPoly.getFastVertexOffset(myConvex.vertices[i]); }
62  { return myPoly.getPointOffset(myConvex.vertices[i]); }
64  { return myPoly.getPos3(myConvex.vertices[i]); }
65  float calcArea() const
66  {
67  UT_Vector3 p[4];
68  for (GA_Size i = 0; i < getFastVertexCount(); ++i)
69  p[i] = getPos3(i);
70  float area = cross(p[0]-p[1],p[2]-p[1]).length();
71  if (!myConvex.isTri())
72  area += cross(p[0]-p[3],p[2]-p[3]).length();
73  area *= 0.5f;
74  return area;
75  }
76 private:
77  const POLY &myPoly;
78  const GEO_TriOrQuad &myConvex;
79 };
80 
81 namespace {
82 template<typename POLY>
83 class geo_Convexer : private UT_Convex
84 {
85 public:
86  geo_Convexer(const POLY &poly, UT_Array<GEO_TriOrQuad> &output,
87  const UT_Vector3 &x, const UT_Vector3 &y,
88  bool triangulate)
89  : myInputPoly(poly)
90  , myOutputPolys(output)
91  , myX(x)
92  , myY(y)
93  {
94  GA_Size nvertices = poly.getFastVertexCount();
95 
96  // Turn everything into convex quads and triangles
97  // NOTE: We keep degenerate output polygons so that we reduce the
98  // risk of messing up the case where we must scatter an exact
99  // number of points on a degenerate input polygon.
100  // Only allow interruption for large polygons, since it's slow.
101  UT_Convex::convex(triangulate ? 3 : 4, nvertices > 256);
102  }
103 private:
104  virtual int getPointCount() const
105  { return myInputPoly.getFastVertexCount(); }
106  virtual void getPoint(int num, float &x, float &y) const
107  {
108  UT_Vector3 pos = myInputPoly.getPos3(num);
109  x = dot(pos, myX);
110  y = dot(pos, myY);
111  }
112  virtual void beginPolygon(int npoints, bool lastone)
113  {
114  UT_ASSERT_P(npoints == 3 || npoints == 4);
115  myOutputPolys.append();
116  myOutputPolys.last().makeTri();
117  myI = 0;
118  }
119  virtual void polyVertex(int num)
120  {
121  UT_ASSERT_P(myI < 4);
122  myOutputPolys.last().vertices[myI] = num;
123  ++myI;
124  }
125  virtual void endPolygon()
126  { UT_ASSERT_P(myI == 3 || myI == 4); }
127 
128  const POLY &myInputPoly;
129  int myI;
130  UT_Array<GEO_TriOrQuad> &myOutputPolys;
131  UT_Vector3 myX;
132  UT_Vector3 myY;
133 };
134 }
135 
136 /// Convexes polygon into tris and quads.
137 /// Writes to output if polygon needed convexing.
138 /// Returns true if output was written-to.
139 /// Mantra keeps non-convex quads and doesn't triangulate, hence the default.
140 template<typename POLY>
141 bool GEOconvexPoly(const POLY &poly, UT_Array<GEO_TriOrQuad> &output, bool keepnonconvexquads = true, bool triangulate = false)
142 {
143  output.setSize(0);
144  GA_Size nvertices = poly.getFastVertexCount();
145  if (nvertices <= 3)
146  return false;
147  if (nvertices == 4)
148  {
149  if (keepnonconvexquads)
150  return false;
151 
152  // Avoid using UT_Convex::convex for quads; it's slow.
153  UT_Vector3 p0 = poly.getPos3(0);
154  UT_Vector3 p1 = poly.getPos3(1);
155  UT_Vector3 p2 = poly.getPos3(2);
156  UT_Vector3 p3 = poly.getPos3(3);
157  bool split02 = UT_Convex::canSplitQuad02(p0, p1, p2, p3);
158  if (!split02)
159  {
160  // Split 1-3
161  // Be sure to use the same winding order!
162  output.setSize(2);
163  output(0) = GEO_TriOrQuad(0, 1, 3);
164  output(1) = GEO_TriOrQuad(1, 2, 3);
165  return true;
166  }
167  bool split13 = !triangulate && UT_Convex::canSplitQuad02(p1, p2, p3, p0);
168  if (!split13)
169  {
170  // Split 0-2
171  output.setSize(2);
172  output(0) = GEO_TriOrQuad(0, 1, 2);
173  output(1) = GEO_TriOrQuad(0, 2, 3);
174  return true;
175  }
176  return false;
177  }
178 
179  output.setSize(0);
180  // Minimum capacity needed is (n-1)/2, which is hit if divides into
181  // all quads except possibly one triangle if odd number of vertices.
182  GA_Size minquads = (nvertices-1)/2;
183  output.bumpCapacity(minquads);
184 
185  UT_Vector3 normal = poly.computeNormal();
186 
187  // In the unlikely event that our normal is garbage, go all out
188  // with computing an oriented bounding box to get a reasonable
189  // normal.
190  if (normal.isEqual(UT_Vector3(0,0,0)))
191  {
192  UT_Array<UT_Vector3> temppoints(nvertices, nvertices);
193  for (GA_Size i = 0; i < nvertices; ++i)
194  temppoints(i) = poly.getPos3(i);
195  UT_OBBoxF obbox(temppoints);
196  normal = obbox.getMinAxis();
197  }
198  UT_Vector3 x;
199  UT_Vector3 y;
200  normal.getFrameOfReference(y, x);
201  geo_Convexer<POLY>(poly, output, x, y, triangulate);
202  UT_ASSERT_P(output.size() >= minquads);
203  return true;
204 }
205 
206 /// Triangulates polygon.
207 /// Writes to output if polygon had more than 3 vertices.
208 /// Returns true if output was written-to.
209 template<typename POLY>
210 SYS_FORCE_INLINE bool
211 GEOtriangulatePoly(const POLY &poly, UT_Array<GEO_TriOrQuad> &output)
212 {
213  return GEOconvexPoly(poly, output, false, true);
214 }
215 
216 #endif
GEO_TriOrQuadT< GA_Size > GEO_TriOrQuad
Definition: GEO_Convex.h:48
SYS_FORCE_INLINE void makeTri()
Definition: GEO_Convex.h:41
SYS_FORCE_INLINE UT_Vector3 getPos3(GA_Size i) const
Definition: GEO_Convex.h:63
UT_Vector3T< T > getMinAxis() const
Return the minimum axis direction.
Definition: UT_OBBox.h:56
virtual void polyVertex(int num)=0
Arbitrarily Oriented Bounding (OBB)
Definition: UT_OBBox.h:25
GLint y
Definition: glcorearb.h:102
GLfloat GLfloat GLfloat v2
Definition: glcorearb.h:817
GLfloat GLfloat GLfloat GLfloat v3
Definition: glcorearb.h:818
virtual void beginPolygon(int npoints, bool lastone)=0
beginPolygon will be told when the last polygon is being added
void bumpCapacity(exint mincapacity)
Definition: UT_Array.h:410
png_uint_32 i
Definition: png.h:2877
void setSize(exint newsize)
Definition: UT_Array.h:462
exint GA_Size
Defines the bit width for index and offset types in GA.
Definition: GA_Types.h:211
GEO_TriOrQuadWrapper(const POLY &poly, const GEO_TriOrQuad &convex)
Definition: GEO_Convex.h:53
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:101
GA_Size GA_Offset
Definition: GA_Types.h:617
void getFrameOfReference(UT_Vector3T< T > &X, UT_Vector3T< T > &Y) const
Definition: UT_Vector3.h:493
float calcArea() const
Definition: GEO_Convex.h:65
virtual void getPoint(int num, float &x, float &y) const =0
SIM_DerScalar length() const
SYS_FORCE_INLINE GA_Size getFastVertexCount() const
Definition: GEO_Convex.h:57
fpreal64 dot(const CE_VectorT< T > &a, const CE_VectorT< T > &b)
Definition: CE_Vector.h:218
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
virtual void endPolygon()=0
GLfloat v0
Definition: glcorearb.h:815
SYS_FORCE_INLINE GA_Offset getFastVertexOffset(GA_Size i) const
Definition: GEO_Convex.h:59
SYS_FORCE_INLINE bool isEqual(const UT_FixedVector< S, SIZE, S_INSTANTIATED > &that, S tol=S(SYS_FTOLERANCE)) const
SYS_FORCE_INLINE bool isTri() const
Definition: GEO_Convex.h:43
SYS_FORCE_INLINE void makeInvalid()
Definition: GEO_Convex.h:34
GLint GLenum GLint x
Definition: glcorearb.h:408
GLfloat GLfloat v1
Definition: glcorearb.h:816
bool GEOconvexPoly(const POLY &poly, UT_Array< GEO_TriOrQuad > &output, bool keepnonconvexquads=true, bool triangulate=false)
Definition: GEO_Convex.h:141
GEO_TriOrQuadT(T v0, T v1, T v2, T v3=T(-1))
Definition: GEO_Convex.h:27
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
void convex(exint maxsides, bool allowinterrupt=true, bool avoiddegeneracy=false)
virtual int getPointCount() const =0
It's the sub-class responsibility to fill these out...
SIM_DerVector3 cross(const SIM_DerVector3 &lhs, const SIM_DerVector3 &rhs)
SYS_FORCE_INLINE bool GEOtriangulatePoly(const POLY &poly, UT_Array< GEO_TriOrQuad > &output)
Definition: GEO_Convex.h:211
GA_API const UT_StringHolder area
SYS_FORCE_INLINE GA_Offset getPointOffset(GA_Size i) const
Definition: GEO_Convex.h:61