HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GU_ConvexHull3D.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: GU_ConvexHull3D.h ( GU Library, C++)
7  *
8  */
9 
10 #ifndef __GU_ConvexHull3D_h__
11 #define __GU_ConvexHull3D_h__
12 
13 #include "GU_API.h"
14 
15 #include <GEO/GEO_PolyCounts.h>
16 
17 #include <UT/UT_Array.h>
18 #include <UT/UT_BoundingBox.h>
19 #include <UT/UT_Format.h>
20 #include <UT/UT_Plane.h>
21 #include <UT/UT_StringStream.h>
22 #include <UT/UT_ValArray.h>
23 
24 class GA_PointGroup;
25 class GU_Detail;
26 
27 /// Utility for computing (and optionally expanding or shrinking) convex hulls.
28 /// This uses Bullet's convex hull algorithm (btConvexHullComputer).
30 {
31 public:
32  /// Computes the convex hull of the given point cloud.
33  /// @param shrink_amount If greater than zero, each face will be moved
34  /// towards the center along its normal by this amount. The value will be
35  /// clamped to not exceed the minimum distance of any face to the center of
36  /// the convex hull.
37  void computeAndShrink(fpreal shrink_amount, const UT_Vector3D *points,
38  int npoints, bool remove_inline);
39  void computeAndShrink(fpreal shrink_amount, const UT_Vector3DArray &points,
40  bool remove_inline)
41  { computeAndShrink(shrink_amount, points.data(), points.entries(), remove_inline); }
42 
43  /// Calls computeAndShrink() with the point positions from the given
44  /// detail.
45  void computeAndShrink(
46  fpreal shrink_amount, const GU_Detail &src_gdp,
47  const GA_PointGroup *src_grp, bool remove_inline);
48 
49  /// Expands the convex hull outwards by the given amount.
50  void expand(fpreal expand_amount);
51 
52  /// Transforms the convex hull points.
53  void transform(const UT_Matrix4D &xform);
54 
55  /// Appends the convex hull's geometry to the given detail, optionally
56  /// copying attributes from the corresponding points in the source detail.
57  void getGeometry(GU_Detail &gdp, const GU_Detail *src_gdp = nullptr,
58  const GA_PointGroup *src_grp = nullptr) const;
59 
60  /// Returns a list of the points in the convex hull.
61  const UT_Array<UT_Vector3D> &getPoints() const { return myPoints; }
62 
63  /// Returns the source point index for each point in the convex hull.
64  const UT_Array<int> &getPointSources() const { return myPointSources; }
65 
66  /// Returns a list of the polygons in the convex hull.
67  const GEO_PolyCounts &getPolygonSizes() const { return myPolygonSizes; }
68 
69  /// Returns a list of the vertices. Use getPolygonSizes() to iterate over
70  /// the polygons.
71  const UT_Array<int> &getVertices() const { return myVertices; }
72 
73 private:
74  SYS_FORCE_INLINE const UT_Vector3D &vertexPoint(exint vtx) const
75  {
76  return myPoints(myVertices(vtx));
77  }
78 
79  UT_Array<UT_Vector3D> myPoints;
80  UT_Array<int> myPointSources;
81  GEO_PolyCounts myPolygonSizes;
82  UT_Array<int> myVertices;
83 };
84 
85 /// Utility for working with a convex hull defined as a set of half
86 /// planes.
87 template <typename T>
89 {
90 public:
91  /// Directly build from a set of directed half planes
93  : myPlanes(planes)
94  {
95  }
96 
97  /// Build from a cloud of points.
99  {
100  // Trivially full world if no points.
101  if (!pts.entries())
102  return;
103 
104  GU_ConvexHull3D convexer;
105 
106  // Note removing inline can result in folded half planes.
107  convexer.computeAndShrink(0.0, pts, /*removeinline*/false);
108 
109  // Compute a center so we can validate our planes.
110  UT_Vector3D hullcenter;
111  hullcenter = 0;
112  for (auto && pt : pts)
113  {
114  hullcenter += pt;
115  }
116  hullcenter /= pts.entries();
117 
118  UT_Vector3DArray polyposes;
119  UT_Array<UT_PlaneT<T>> planes;
120  for (auto && poly : convexer.getPolygonSizes())
121  {
122  // Ignore degenerate polys, which likely shouldn't
123  // be output anyways.
124  if (poly.nvertices() < 3)
125  continue;
126 
127  // Compute this plane.
128  polyposes.clear();
129  for (exint vtx = 0; vtx < poly.nvertices(); vtx++)
130  {
131  exint pt = convexer.getVertices()(vtx+poly.start());
132  polyposes.append(convexer.getPoints()(pt));
133  }
134 
135  UT_Vector3D p2 = polyposes.last();
136  UT_Vector3D nml(0,0,0);
137  UT_Vector3D center(0,0,0);
138  for (exint vtx = 0; vtx < poly.nvertices(); vtx++)
139  {
140  UT_Vector3D p1 = p2;
141  p2 = polyposes(vtx);
142  center += p2;
143  // Newell's method.
144  nml.normal(p1, p2);
145  }
146 
147  center /= polyposes.entries();
148  nml.normalize();
149 
150  UT_PlaneT<T> plane(center, nml);
151  // Verify our hull center is on the correct side.
152  UT_ASSERT(plane.distance(hullcenter) <= 0);
153  if (plane.distance(hullcenter) > 0)
154  {
155  // Skip this plane, something went horribly wrong,
156  // might be a mis-wound polygon. It likely is somethin
157  // degenerate so ignoring likely is the right thing.
158  continue;
159  }
160 
161  myPlanes.append(plane);
162  }
163  }
164 
165  void addPlane(const UT_PlaneT<T> &plane)
166  {
167  myPlanes.append(plane);
168  }
169 
171  {
172  for (auto && plane : myPlanes)
173  {
174  plane.shiftOffset(offset);
175  }
176  }
177 
178  /// Return signed distance for the convex hull.
179  template <typename S>
180  T
182  {
183  T dist = -FLT_MAX;
184  // If any plane excludes it, it is excluded.
185  for (auto && plane : myPlanes)
186  {
187  dist = SYSmax(dist, plane.distance(pos));
188  }
189  return dist;
190  }
191 
192  /// Return signed distance for the convex hull.
193  /// Early exits when maxdist is reached.
194  template <typename S>
195  T
196  distance(UT_Vector3T<S> pos, T maxdist) const
197  {
198  T dist = -FLT_MAX;
199  // If any plane excludes it, it is excluded.
200  for (auto && plane : myPlanes)
201  {
202  dist = SYSmax(dist, plane.distance(pos));
203  if (dist > maxdist)
204  return dist;
205  }
206  return dist;
207  }
208 
209  /// Return signed distance for the convex hull.
210  /// Restricts tests to a set of active planes.
211  /// Early exits when maxdist is reached.
212  template <typename IDX, typename S>
213  T
214  distance(const UT_Array<IDX> &activeplanes, UT_Vector3T<S> pos, T maxdist) const
215  {
216  T dist = -FLT_MAX;
217  // If any plane excludes it, it is excluded.
218  for (auto && idx : activeplanes)
219  {
220  dist = SYSmax(dist, myPlanes(idx).distance(pos));
221  if (dist > maxdist)
222  return dist;
223  }
224  return dist;
225  }
226 
227 
228  /// Constructs a list of planes that are active for the given
229  /// sphere. These will be any planes that intersect the sphere.
230  /// The idea being that if one has already culled by this sphere,
231  /// only these planes have to be tested to if we are in or out.
232  /// If no active planes are found, the return result will be true
233  /// if entirely inside the planes, or false if entirely out.
234  template <typename IDX, typename S>
235  bool
236  findActivePlanes(UT_Array<IDX> &activeplanes, UT_Vector3T<S> pos, T rad) const
237  {
238  IDX idx = 0;
239  bool allinside = true;
240 
241  activeplanes.clear();
242  for (auto && plane : myPlanes)
243  {
244  T dist = plane.distance(pos);
245  if (dist >= -rad && dist < rad)
246  {
247  activeplanes.append(idx);
248  }
249  else if (dist >= rad)
250  {
251  // A plane fully excludes us, so thus all planes will.
252  // We can clear any previous planes and return outside.
253  activeplanes.clear();
254  return false;
255  }
256  if (dist > 0)
257  allinside = false;
258  idx++;
259  }
260  return allinside;
261  }
262 
263 
264  template <typename S>
265  bool
266  contains(const UT_BoundingBoxT<S> &bbox) const
267  {
268  UT_Vector3T<T> bmin(bbox.minvec());
269  UT_Vector3T<T> bmax(bbox.maxvec());
270 
271  UT_Vector3T<T> center = (bmax + bmin) / 2;
272  T bboxrad = (bmax - bmin).length() / 2;
273 
274  T centerdist = distance(center, bboxrad);
275 
276  // Check if bounding sphere is fully inside the hull.
277  if (centerdist <= -bboxrad)
278  {
279  return true;
280  }
281  // Check if it is fully outside of the hull.
282  if (centerdist >= bboxrad)
283  {
284  return false;
285  }
286 
287  // Also check the 8 corners to see if all
288  // are contained. Specifically, if any corner is excluded
289  // we know we fail, otherwise we pass.
290  for (int i = 0; i < 8; i++)
291  {
292  UT_Vector3T<T> pt( i & 1 ? bmin.x() : bmax.x(),
293  i & 2 ? bmin.y() : bmax.y(),
294  i & 4 ? bmin.z() : bmax.z() );
295  if (excludes(pt))
296  return false;
297  }
298  return true;
299  }
300 
301  template <typename S>
302  bool
303  excludes(UT_Vector3T<S> pos, T radius = 0) const
304  {
305  // If any plane excludes it, it is excluded.
306  T dist = distance(pos, radius);
307  if (dist >= radius)
308  return true;
309  // Nothing excludes, so must partially overlap.
310  return false;
311  }
312 
313  template <typename S>
314  bool
315  excludes(const UT_BoundingBoxT<S> &bbox) const
316  {
317  UT_Vector3T<T> bmin(bbox.minvec());
318  UT_Vector3T<T> bmax(bbox.maxvec());
319  UT_Vector3T<T> center = (bmax + bmin) / 2;
320 
321  // Check the bounding sphere is outside the box.
322  if (excludes(center, (bmax - bmin).length()/2))
323  {
324  return true;
325  }
326 
327  return false;
328  }
329 
330  size_t format(char *buffer, size_t bufsize) const
331  {
332  UT_OStringStream tmp;
333  bool first = true;
334  for (auto &&item : myPlanes)
335  {
336  if (!first)
337  tmp << ", ";
338  first = false;
339  UTformat(tmp, "{}", item);
340  }
341 
342  UT::Format::Writer writer(buffer, bufsize);
344  return f.format(writer, "[{}]", {tmp.str()});
345  }
346 
347 protected:
349 };
350 
351 template <typename T>
352 size_t format(char *buffer, size_t bufsize, const GU_ConvexHullHalfPlanesT<T> &h)
353 {
354  return h.format(buffer, bufsize);
355 }
356 
360 
361 #endif
#define SYSmax(a, b)
Definition: SYS_Math.h:1513
T & last()
Definition: UT_Array.h:759
GA_API const UT_StringHolder dist
bool findActivePlanes(UT_Array< IDX > &activeplanes, UT_Vector3T< S > pos, T rad) const
const UT_Array< int > & getVertices() const
GLenum GLuint GLsizei bufsize
Definition: glcorearb.h:1818
size_t format(W &writer, const char *format, std::initializer_list< ArgValue > args)
const UT_Array< UT_Vector3D > & getPoints() const
Returns a list of the points in the convex hull.
Axis-aligned bounding box (AABB).
Definition: GEO_Detail.h:43
GLint first
Definition: glcorearb.h:405
bool excludes(const UT_BoundingBoxT< S > &bbox) const
size_t format(char *buffer, size_t bufsize) const
void computeAndShrink(fpreal shrink_amount, const UT_Vector3DArray &points, bool remove_inline)
bool contains(const UT_BoundingBoxT< S > &bbox) const
int64 exint
Definition: SYS_Types.h:125
UT_Vector3T< T > maxvec() const
An output stream object that owns its own string buffer storage.
size_t format(char *buffer, size_t bufsize, const GU_ConvexHullHalfPlanesT< T > &h)
constexpr SYS_FORCE_INLINE T length() const noexcept
Definition: UT_Vector3.h:351
const UT_WorkBuffer & str()
Returns a read-only reference to the underlying UT_WorkBuffer.
T distance(const UT_Array< IDX > &activeplanes, UT_Vector3T< S > pos, T maxdist) const
GLuint GLenum GLenum transform
Definition: glew.h:15055
Definition: core.h:760
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
static int entries()
Returns the vector size.
Definition: UT_Vector3.h:761
UT_Array< UT_PlaneT< T > > myPlanes
T distance(UT_Vector3T< S > pos) const
Return signed distance for the convex hull.
T distance(UT_Vector3T< S > pos, T maxdist) const
#define GU_API
Definition: GU_API.h:14
exint append()
Definition: UT_Array.h:137
GLuint GLdouble GLdouble GLint GLint const GLdouble * points
Definition: glew.h:3460
exint entries() const
Alias of size(). size() is preferred.
Definition: UT_Array.h:611
GLuint GLsizei GLsizei * length
Definition: glcorearb.h:795
GLfloat GLfloat GLfloat GLfloat h
Definition: glcorearb.h:2002
const UT_Array< int > & getPointSources() const
Returns the source point index for each point in the convex hull.
fpreal64 fpreal
Definition: SYS_Types.h:277
UT_Vector3T< T > minvec() const
T * data()
Definition: UT_Array.h:785
Type-safe formatting, modeled on the Python str.format function.
size_t UTformat(FILE *file, const char *format, const Args &...args)
GLfloat f
Definition: glcorearb.h:1926
void addPlane(const UT_PlaneT< T > &plane)
void computeAndShrink(fpreal shrink_amount, const UT_Vector3D *points, int npoints, bool remove_inline)
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:153
SYS_FORCE_INLINE UT_StorageMathFloat_t< T > normalize() noexcept
Definition: UT_Vector3.h:366
GLintptr offset
Definition: glcorearb.h:665
GU_ConvexHullHalfPlanesT(const UT_Vector3DArray &pts)
Build from a cloud of points.
void clear()
Resets list to an empty list.
Definition: UT_Array.h:679
SYS_FORCE_INLINE void normal(const UT_Vector3T< T > &va, const UT_Vector3T< T > &vb)
Definition: UT_Vector3.h:528
GU_ConvexHullHalfPlanesT(const UT_Array< UT_PlaneT< T >> &planes)
Directly build from a set of directed half planes.
T distance(const UT_Vector3T< T > &p) const
Definition: UT_PlaneImpl.h:314
const GEO_PolyCounts & getPolygonSizes() const
Returns a list of the polygons in the convex hull.
bool excludes(UT_Vector3T< S > pos, T radius=0) const