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 
120 {
121 
122 public:
123  explicit LoopSet(int num_loops = -1,
124  int num_points = -1,
125  int num_edges = -1);
126 
127  LoopSet(LoopSet &&robbed) = default;
128 
130  void addLoop(int group_id = -1);
131 
133  void addPoint(UT_Vector3R pos,
134  UT_Vector3R v = UT_Vector3R(0, 0, 0),
137  void addEdge(UT_Vector3R normal);
138 
140  int numLoops() const
141  { return int(myLoopFirstPoint.size() - 1); }
142 
144  int numPoints() const { return int(myPoints.size()); }
145 
147  int numEdges() const { return int(myEdges.size()); }
148 
150  bool isClosed(int l) const
151  { return numLoopPoints(l) == numLoopEdges(l); }
152 
155  { return myPoints(p).position; }
156 
159  { return myPoints(p).velocity; }
160 
162  bool pointHasOffsetLimit(int p) const
163  { return myPoints(p).veltype != DIRECTION_ONLY; }
164 
167  { return myPoints(p).veltype; }
168 
170  UT_Vector3R edgeNormal(int e) const
171  { return myEdges(e).normal; }
172 
174  int pointLoop(int p) const
175  { return myPointLoop(p); }
176 
178  int edgeLoop(int e) const
179  { return myEdgeLoop(e); }
180 
182  int numLoopEdges(int l) const
183  { return myLoopFirstEdge(l + 1)
184  - myLoopFirstEdge(l); }
186  int numLoopPoints(int l) const
187  { return myLoopFirstPoint(l + 1)
188  - myLoopFirstPoint(l); }
190  int loopEdge(int l, int i) const;
191 
193  int loopPoint(int l, int i) const;
194 
196  int pointEdge(int p, Side s) const;
197 
199  int edgePoint(int e, Side s) const;
200 
202  int loopGroup(int l) const { return myLoopGroup(l); }
203 
205  int numLoopGroups() const { return myNumLoopGroups; }
206 
207 private:
208 
209  struct PointData
210  {
212  VelocityType t) :
213  position(p), velocity(v), veltype(t) { }
214 
215  UT_Vector3R position; // Initial position
216  UT_Vector3R velocity; // Constraint velocity
217  VelocityType veltype;
218  };
219 
220  struct EdgeData
221  {
222  SYS_FORCE_INLINE EdgeData(UT_Vector3R n) : normal(n) { }
223 
224  UT_Vector3R normal; // Initial position
225  };
226 
227  using PointDataArray = UT_Array<PointData>;
228  using EdgeDataArray = UT_Array<EdgeData>;
229 
230  PointDataArray myPoints;
231  EdgeDataArray myEdges;
232 
233  UT_IntArray myPointLoop;
234  UT_IntArray myEdgeLoop;
235  UT_IntArray myLoopFirstPoint;
236  UT_IntArray myLoopFirstEdge;
237  UT_IntArray myLoopGroup;
238  int myNumLoopGroups = 0;
239 };
240 
241 
242 class Skeleton;
243 
245 {
246 public:
248 
249  /// GU_LoopOffset works on one or more sequences of (point/primitive/vertex)
250  /// offsets on a detail. Each sequence of offsets, along with a *position*
251  /// attribute defines a *chain* of edges. The end-points of the edges, which
252  /// we call the *joints* of the chain, can be repeated along the chain (an
253  /// offset may appear multiple times in the same chain). Each edge of the
254  /// chain is supplied with a velocity vector along which it will be slid.
255  /// It is also possible to override the otherwise calculated joint
256  /// velocities.
257  ///
258  /// The number of chains is specified by 'num_chains'. The 'chain_lengths'
259  /// array should have at least num_chains elements and specifies the number
260  /// of joints in each chain. The 'joint_offsets' array must present the
261  /// joint offsets for all chains back to back and therefore should have
262  /// length (at least) equal to the sum of the elements in 'chain_lengths'.
263  ///
264  /// Each chain can be "closed" or "open", respectively meaning an edge is
265  /// or is not interpreted to exist between the last joint of the chain and
266  /// its first. Setting 'closed_flags' to NULL indicates that all the chains
267  /// are "closed". Otherwise the array to which it points must have least
268  /// num_chains elements.
269  ///
270  /// The 'edge_vel' array must always be supplied with exactly the same
271  /// length as joint_offsets to indicate the velocity vector for the edge
272  /// between the joint at a corresponding position and its successor.
273  /// The velocity vector paired with the last joint of an open chain is
274  /// ignored.
275  ///
276  /// The 'joint_vel' array, provides overrides for the joint velocities that
277  /// are automatically calculated based on edge velocities. Joints with
278  /// override velocity set to (0, 0, 0) still get a calculated velocity.
279  /// However, joints with preset velocities are ensured to always move in
280  /// the given direction even after merging with other trajectories. If two
281  /// joints with preset velocities collide, the insetting limit is reached.
282  ///
283  /// *Two sided* insetters can evaluate both positive and negative inset
284  /// amounts. If 'two-sided' is set to false, evaluation of inset position
285  /// for negative isnet amounts will only use the initial joint velocity
286  /// vectors.
287  ///
288  /// 'collinearity_tol' is the cosine of the largest angle between the
289  /// normals of the planes scanned by two edge velocity vectors below which
290  /// the planes are considered parallel.
291 
292  explicit LoopOffset(LoopSet &&loops,
293  bool two_sided = false,
294  fpreal max_speed = -1);
295 
296  ~LoopOffset();
297 
298  UT_Vector3R offsetPosition(int pt,
299  fpreal offset,
300  bool limit_slides,
301  bool handle_collisions,
302  LimitTriggerMask limit_type,
303  LimitGrouping limit_mode = INDIVIDUAL,
304  int *hits_limit = nullptr,
305  int *is_merged = nullptr);
306 
307  /// Returns the inset value beyond which insetting freezes, ie, the
308  /// outcome stays the same for larger values. If no limit exists, -1 is
309  /// returned.
310  /// If the insetter is two-sided, the returned limit is the the limit of
311  /// the positive side if 'positive' is set true or that of the negative
312  /// side otherwise. If single-sided, the parameter is ignored. Note that
313  /// the limit of the negative side is returned as a positive number if
314  /// such a limit exists (and as -1 otherwise) and the actual limit value
315  /// would be the negative of the returned amount.
316 
317  fpreal getLimit(LimitTriggerMask mask, bool positive = true);
318 
319 
320  static fpreal unitOffsetLength(UT_Vector3R v, UT_Vector3R t0,
321  UT_Vector3R t1);
322 
323  static UT_Vector3R normalBisector(UT_Vector3R t0, UT_Vector3R n0,
325 private:
327 
328  SkeletonUptr myPosSkeleton;
329  SkeletonUptr myNegSkeleton;
330  LoopSet myLoops;
331 };
332 
333 
335 Side
337 {
338  return Side(1 - int(s));
339 }
340 
341 void
342 LoopSet::addLoop(int group_id)
343 {
344  myLoopGroup.append(group_id >= 0 ? group_id : int(myLoopGroup.size()));
345  if (myLoopGroup.last() > myNumLoopGroups - 1)
346  myNumLoopGroups = myLoopGroup.last() + 1;
347 
348  myLoopFirstEdge.append(int(myEdges.size()));
349  myLoopFirstPoint.append(int(myPoints.size()));
350 }
351 
352 void
354 {
355  myPoints.append(PointData(pos, v, t));
356  myPointLoop.append(numLoops() - 1);
357  myLoopFirstPoint.last()++;
358 }
359 
360 void
362 {
363  myEdges.append(EdgeData(normal));
364  myEdgeLoop.append(numLoops() - 1);
365  myLoopFirstEdge.last()++;
366 }
367 
368 
369 } // namespace GU_PolyBevel3
370 
371 #endif
GLdouble s
Definition: glew.h:1390
T & last()
Definition: UT_Array.h:599
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:451
SYS_FORCE_INLINE int numPoints() const
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)
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
GLfloat GLfloat p
Definition: glew.h:16321
double fpreal
Definition: SYS_Types.h:276
SYS_FORCE_INLINE UT_Vector3R pointPosition(int p) const
UT_Vector3T< fpreal > UT_Vector3R
A smart pointer for unique ownership of dynamically allocated objects.
Definition: UT_UniquePtr.h:47
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t1
Definition: glew.h:12681
exint append(void)
Definition: UT_Array.h:95
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:383
SYS_FORCE_INLINE UT_Vector3R pointVelocity(int p) const
GLdouble GLdouble t
Definition: glew.h:1398
unsigned int uint32
Definition: SYS_Types.h:40
GLintptr offset
Definition: glew.h:1682
SYS_FORCE_INLINE int edgeLoop(int e) const