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