HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GU_PolyBevel3Offset.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 Library (C++)
7  *
8  * COMMENTS: Utility tool to compute inset positions for a one or more
9  * (open or closed) chains of point positions.
10  *
11  * NB: At this point (and likely for the foreseeable future), GU_LoopOffset
12  * will be based on an idea which I call the "weak straight skeleton" of the
13  * input chains. I don't know of any references to this concept in the
14  * literature and I worked it out on my own due to certain advantages it
15  * provides and the way it functions as a middle ground for efficient yet
16  * acceptable insetting.
17  *
18  * The standard straight skeleton (defined for straight-line embedded graph
19  * in 2D), is defined by creating a "wavefront" by sliding the edges of the
20  * graph at equal speed parallel to themselves and tracking the paths the
21  * vertices of the graph travel. As the edges are slid during this process,
22  * two type of "events" can take place:
23  *
24  * An "Edge Event" traditionally refers to the moment at which the length
25  * of an edge becomes zero, i.e. the straight skeleton branches that
26  * correspond to the trajectories of the two vertices at two ends of the
27  * edge in question collide. Such an event merges the two trajectories into
28  * one. Note that the topology of the wavefront stays unchanged under the
29  * effect of an edge event.
30  *
31  * A "Vertex Event" refers to the moment at which a vertex of the moving
32  * graph hits an edge to which it is not adjacent. The hit edge is then
33  * split and the connected component of the wavefront that contains the
34  * colliding parties is split into two (or more). Therefore, this type of
35  * event causes the topology of the wavefront to change, in particular
36  * spawning two ore more branches in the skeleton with trajectories
37  * diverging out of the collision point.
38  *
39  *
40  * The weak straight skeleton is defined using only the first type of event.
41  * In other words, we follow the trajectories of the vertices of the graph but
42  * systematically ignore collisions of the vertices with edges and only catch
43  * collisions between trajectories of "neighbouring" vertices along the
44  * wavefront. Unlike the wavefronts of the straight skeleton, those of the weak
45  * skeleton can self-intersect but in a limited manner. However, there are at
46  * a handful of significant consequences to this choice:
47  *
48  * 1. The topology of the wavefront never changes. This maybe indispensable
49  * if, say, we want to bridge the original chain and the inset one. In
50  * particular, there is no reason to define the weak skeleton on general
51  * graphs but rather on "chains" which would be open or closed sequences
52  * of (possibly repeated) vertices.
53  *
54  * 2. It is far far cheaper to compute the weak skeleton than do the
55  * standard one, since it is the detection of vertex events that
56  * is the real challenge in the computation of the straight skeleton and
57  * takes upwards of quadratic time per event or O(n^3) in general. In
58  * contrast the weak skeleton can be computed in O(n log n) time.
59  *
60  * 3. It is also a fair bit easier to turn the weak skeleton computation
61  * into a robust algorithm due to the strong restriction on the way the
62  * topology is modified along the way.
63  *
64  * 4. It is much easier to generalize the algorithm to non-planar curves.
65  * due to the fact that the collisions only need to be sought (or
66  * interpreted) between neighbouring vertices along the wavefront.
67  *
68  */
69 
70 #ifndef __GU_PolyBevel3Offset_h__
71 #define __GU_PolyBevel3Offset_h__
72 
73 #include "GU_API.h"
74 #include "GU_PolyReduce2.h"
75 #include "GU_Detail.h"
76 
77 #include <UT/UT_UniquePtr.h>
78 #include <GEO/GEO_HedgeInterface.h>
79 #include <GEO/GEO_PolyInterface.h>
80 
81 
82 namespace GU_PolyBevel3
83 {
84 
85 enum Side
86 {
87  L = 0,
88  R = 1
89 };
90 
92 {
93  EMPTY = 0, // No limiting of offsets
94  INDIVIDUAL, // One limit per loop
95  SIMULTANEOUS // Same limit for all loops
96 };
97 
99 {
100  SLIDE_END = 0, // Sliding point reaching end of the slide edge
101  PINCH, // Merge event representing a pinch (local max)
102  COLLISION // Reflex vertex hitting non-neighbour edge
103 };
104 
106 {
108  PINCH_MASK = 1U << PINCH,
110 };
111 
113 {
117 };
118 
119 // A LoopSet object is used to describe the loop that needs to be offset
120 // to LoopOffset. Multiple Loops can be added to a LoopSet. Each loop is
121 // created by calling addLoop() followed by calls to an interleaving sequence
122 // of calls to addPoint() and addEdge(). The final addEdge() call in a loop
123 // is optional and omitting it signals the loop is open.
124 //
125 // addLoop() takes as argument a group_id (defaulted to -1). If the group id
126 // is non-negative, then all loops with the same group_id are considered as a
127 // single family of loops, meaning that their mutual collisions are taken into
128 // account and a single stoppage time is associated with the whole group.
129 //
130 // addPoint() requires the position of the point being added. Optionally, one
131 // can pass the slide direction for that point which restricts the
132 // movements of the point to the half-line out of the starting position
133 // moving in the given direction (but not necessarily at the given speed).
134 // If the zero vector is passed for slide direction, then direction is
135 // determined by LoopOffset so as to minimize the distortion in offset
136 // amount while staying in the given offset planes (see addEdge() below).
137 // The third argument (VelocityType) provides a way of interpreting the
138 // magnitude of the passed direction as a limit to sliding. If set to
139 // DIRECTION_ONLY, no limit is set. If set to MAX_OFFSET, the range of
140 // movement of the point will be a segment of length equal to the length
141 // of the passed direction vector. If set to MAX_OFFSET_X2, it will be
142 // half of that (used for when two opposite points slide on the same
143 // line).
144 //
145 // addEdge() requires the normal of the plane on which the edge is meant to
146 // slide. If zero, the edge simply won't slide at all and its endpoints
147 // are frozen. Note that Obviously, it is not always possible to stick
148 // to a given plane and in extreme cases it may be that no positive
149 // offset of an edge meets no positive offsets of its successors. In such
150 // cases, the point at which the two edge meet is kept frozen.
151 
153 {
154 
155 public:
156  explicit LoopSet(int num_loops = -1,
157  int num_points = -1,
158  int num_edges = -1);
159 
160  LoopSet(LoopSet &&robbed) = default;
161 
163  void addLoop(int group_id = -1);
164 
166  void addPoint(UT_Vector3R pos,
167  UT_Vector3R v = UT_Vector3R(0, 0, 0),
170  void addEdge(UT_Vector3R normal);
171 
173  int numLoops() const
174  { return int(myLoopFirstPoint.size() - 1); }
175 
177  int numPoints() const { return int(myPoints.size()); }
178 
180  int numEdges() const { return int(myEdges.size()); }
181 
183  bool isClosed(int l) const
184  { return numLoopPoints(l) == numLoopEdges(l); }
185 
188  { return myPoints(p).position; }
189 
192  { return myPoints(p).velocity; }
193 
195  bool pointHasOffsetLimit(int p) const
196  { return myPoints(p).veltype != DIRECTION_ONLY; }
197 
200  { return myPoints(p).veltype; }
201 
203  UT_Vector3R edgeNormal(int e) const
204  { return myEdges(e).normal; }
205 
207  int pointLoop(int p) const
208  { return myPointLoop(p); }
209 
211  int edgeLoop(int e) const
212  { return myEdgeLoop(e); }
213 
215  int numLoopEdges(int l) const
216  { return myLoopFirstEdge(l + 1)
217  - myLoopFirstEdge(l); }
219  int numLoopPoints(int l) const
220  { return myLoopFirstPoint(l + 1)
221  - myLoopFirstPoint(l); }
223  int loopEdge(int l, int i) const;
224 
226  int loopPoint(int l, int i) const;
227 
229  int pointEdge(int p, Side s) const;
230 
232  int edgePoint(int e, Side s) const;
233 
235  int loopGroup(int l) const { return myLoopGroup(l); }
236 
238  int numLoopGroups() const { return myNumLoopGroups; }
239 
240 private:
241 
242  struct PointData
243  {
245  VelocityType t) :
246  position(p), velocity(v), veltype(t) { }
247 
248  UT_Vector3R position; // Initial position
249  UT_Vector3R velocity; // Constraint velocity
250  VelocityType veltype;
251  };
252 
253  struct EdgeData
254  {
255  SYS_FORCE_INLINE EdgeData(UT_Vector3R n) : normal(n) { }
256 
257  UT_Vector3R normal; // Initial position
258  };
259 
260  using PointDataArray = UT_Array<PointData>;
261  using EdgeDataArray = UT_Array<EdgeData>;
262 
263  PointDataArray myPoints;
264  EdgeDataArray myEdges;
265 
266  UT_IntArray myPointLoop;
267  UT_IntArray myEdgeLoop;
268  UT_IntArray myLoopFirstPoint;
269  UT_IntArray myLoopFirstEdge;
270  UT_IntArray myLoopGroup;
271  int myNumLoopGroups = 0;
272 };
273 
274 
275 class Skeleton;
276 
278 {
279 public:
281 
282  /// GU_LoopOffset works on one or more sequences of (point/primitive/vertex)
283  /// offsets on a detail. Each sequence of offsets, along with a *position*
284  /// attribute defines a *chain* of edges. The end-points of the edges, which
285  /// we call the *joints* of the chain, can be repeated along the chain (an
286  /// offset may appear multiple times in the same chain). Each edge of the
287  /// chain is supplied with a velocity vector along which it will be slid.
288  /// It is also possible to override the otherwise calculated joint
289  /// velocities.
290  ///
291  /// The number of chains is specified by 'num_chains'. The 'chain_lengths'
292  /// array should have at least num_chains elements and specifies the number
293  /// of joints in each chain. The 'joint_offsets' array must present the
294  /// joint offsets for all chains back to back and therefore should have
295  /// length (at least) equal to the sum of the elements in 'chain_lengths'.
296  ///
297  /// Each chain can be "closed" or "open", respectively meaning an edge is
298  /// or is not interpreted to exist between the last joint of the chain and
299  /// its first. Setting 'closed_flags' to NULL indicates that all the chains
300  /// are "closed". Otherwise the array to which it points must have least
301  /// num_chains elements.
302  ///
303  /// The 'edge_vel' array must always be supplied with exactly the same
304  /// length as joint_offsets to indicate the velocity vector for the edge
305  /// between the joint at a corresponding position and its successor.
306  /// The velocity vector paired with the last joint of an open chain is
307  /// ignored.
308  ///
309  /// The 'joint_vel' array, provides overrides for the joint velocities that
310  /// are automatically calculated based on edge velocities. Joints with
311  /// override velocity set to (0, 0, 0) still get a calculated velocity.
312  /// However, joints with preset velocities are ensured to always move in
313  /// the given direction even after merging with other trajectories. If two
314  /// joints with preset velocities collide, the insetting limit is reached.
315  ///
316  /// *Two sided* insetters can evaluate both positive and negative inset
317  /// amounts. If 'two-sided' is set to false, evaluation of inset position
318  /// for negative isnet amounts will only use the initial joint velocity
319  /// vectors.
320  ///
321  /// 'collinearity_tol' is the cosine of the largest angle between the
322  /// normals of the planes scanned by two edge velocity vectors below which
323  /// the planes are considered parallel.
324 
325  explicit LoopOffset(LoopSet &&loops,
326  bool two_sided = false,
327  fpreal max_speed = -1);
328 
329  ~LoopOffset();
330 
331  UT_Vector3R offsetPosition(int pt,
332  fpreal offset,
333  bool limit_slides,
334  bool handle_collisions,
335  LimitTriggerMask limit_type,
336  LimitGrouping limit_mode = INDIVIDUAL,
337  int *hits_limit = nullptr,
338  int *is_merged = nullptr);
339 
340  /// Returns the inset value beyond which insetting freezes, ie, the
341  /// outcome stays the same for larger values. If no limit exists, -1 is
342  /// returned.
343  /// If the insetter is two-sided, the returned limit is the the limit of
344  /// the positive side if 'positive' is set true or that of the negative
345  /// side otherwise. If single-sided, the parameter is ignored. Note that
346  /// the limit of the negative side is returned as a positive number if
347  /// such a limit exists (and as -1 otherwise) and the actual limit value
348  /// would be the negative of the returned amount.
349 
350  fpreal getLimit(LimitTriggerMask mask, bool positive = true);
351 
352 
353  static fpreal unitOffsetLength(UT_Vector3R v, UT_Vector3R t0,
354  UT_Vector3R t1);
355 
356  static UT_Vector3R normalBisector(UT_Vector3R t0, UT_Vector3R n0,
358 private:
359  using SkeletonUptr = UT_UniquePtr<Skeleton>;
360 
361  SkeletonUptr myPosSkeleton;
362  SkeletonUptr myNegSkeleton;
363  LoopSet myLoops;
364 };
365 
366 
368 Side
370 {
371  return Side(1 - int(s));
372 }
373 
374 void
375 LoopSet::addLoop(int group_id)
376 {
377  myLoopGroup.append(group_id >= 0 ? group_id : int(myLoopGroup.size()));
378  if (myLoopGroup.last() > myNumLoopGroups - 1)
379  myNumLoopGroups = myLoopGroup.last() + 1;
380 
381  myLoopFirstEdge.append(int(myEdges.size()));
382  myLoopFirstPoint.append(int(myPoints.size()));
383 }
384 
385 void
387 {
388  myPoints.append(PointData(pos, v, t));
389  myPointLoop.append(numLoops() - 1);
390  myLoopFirstPoint.last()++;
391 }
392 
393 void
395 {
396  myEdges.append(EdgeData(normal));
397  myEdgeLoop.append(numLoops() - 1);
398  myLoopFirstEdge.last()++;
399 }
400 
401 
402 } // namespace GU_PolyBevel3
403 
404 #endif
GLdouble s
Definition: glew.h:1390
T & last()
Definition: UT_Array.h:608
SYS_FORCE_INLINE void addEdge(UT_Vector3R normal)
SYS_FORCE_INLINE int numEdges() const
SYS_FORCE_INLINE VelocityType pointVelocityType(int p) const
SYS_FORCE_INLINE UT_Vector3R edgeNormal(int e) const
GLdouble l
Definition: glew.h:9122
const GLdouble * v
Definition: glew.h:1391
SYS_FORCE_INLINE void addLoop(int group_id=-1)
GLenum GLint GLuint mask
Definition: glew.h:1845
exint size() const
Definition: UT_Array.h:458
SYS_FORCE_INLINE int numPoints() const
std::unique_ptr< T, Deleter > UT_UniquePtr
A smart pointer for unique ownership of dynamically allocated objects.
Definition: UT_UniquePtr.h:33
SYS_FORCE_INLINE int pointLoop(int p) const
SYS_FORCE_INLINE int loopGroup(int l) const
SYS_FORCE_INLINE void addPoint(UT_Vector3R pos, UT_Vector3R v=UT_Vector3R(0, 0, 0), VelocityType t=DIRECTION_ONLY)
UT_UniquePtr< LoopSet > LoopSetUptr
SYS_FORCE_INLINE bool isClosed(int l) const
SYS_FORCE_INLINE bool pointHasOffsetLimit(int p) const
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
GLsizei n
Definition: glew.h:4040
SYS_FORCE_INLINE int numLoopEdges(int l) const
typedef int(WINAPI *PFNWGLRELEASEPBUFFERDCARBPROC)(HPBUFFERARB hPbuffer
#define GU_API
Definition: GU_API.h:14
SYS_FORCE_INLINE int numLoopGroups() const
exint append()
Definition: UT_Array.h:95
GLfloat GLfloat p
Definition: glew.h:16321
SYS_FORCE_INLINE UT_Vector3R pointPosition(int p) const
UT_Vector3T< fpreal > UT_Vector3R
fpreal64 fpreal
Definition: SYS_Types.h:277
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t1
Definition: glew.h:12681
unsigned int uint32
Definition: SYS_Types.h:40
SYS_FORCE_INLINE Side opposite(Side s)
SYS_FORCE_INLINE int numLoops() const
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t0
Definition: glew.h:12681
SYS_FORCE_INLINE int numLoopPoints(int l) const
SYS_FORCE_INLINE void normal(const UT_Vector3T< T > &va, const UT_Vector3T< T > &vb)
Definition: UT_Vector3.h:387
SYS_FORCE_INLINE UT_Vector3R pointVelocity(int p) const
GLdouble GLdouble t
Definition: glew.h:1398
GLintptr offset
Definition: glew.h:1682
SYS_FORCE_INLINE int edgeLoop(int e) const