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 
129  void addLoop(int group_id = -1);
130 
131  void addPoint(UT_Vector3R pos,
132  UT_Vector3R v = UT_Vector3R(0, 0, 0),
134 
135  void addEdge(UT_Vector3R normal, fpreal weight);
136 
138  int numLoops() const { return int(myLoopFirstPoint.size() - 1); }
139 
141  int numPoints() const { return int(myPoints.size()); }
142 
144  int numEdges() const { return int(myEdges.size()); }
145 
147  bool isClosed(int l) const
148  { return numLoopPoints(l) == numLoopEdges(l); }
149 
152  { return myPoints(p).position; }
153 
156  { return myPoints(p).velocity; }
157 
159  bool pointHasOffsetLimit(int p) const
160  { return myPoints(p).veltype != DIRECTION_ONLY; }
161 
164  { return myPoints(p).veltype; }
165 
167  UT_Vector3R edgeNormal(int e) const
168  { return myEdges(e).normal; }
169 
171  fpreal edgeWeight(int e) const
172  { return myEdges(e).weight; }
173 
175  int pointLoop(int p) const
176  { return myPointLoop(p); }
177 
179  int edgeLoop(int e) const
180  { return myEdgeLoop(e); }
181 
183  int numLoopEdges(int l) const
184  { return myLoopFirstEdge(l + 1)
185  - myLoopFirstEdge(l); }
187  int numLoopPoints(int l) const
188  { return myLoopFirstPoint(l + 1)
189  - myLoopFirstPoint(l); }
191  int loopEdge(int l, int i) const;
192 
194  int loopPoint(int l, int i) const;
195 
197  int pointEdge(int p, Side s) const;
198 
200  int edgePoint(int e, Side s) const;
201 
203  int loopGroup(int l) const { return myLoopGroup(l); }
204 
206  int numLoopGroups() const { return myNumLoopGroups; }
207 
208 private:
209 
210  struct PointData
211  {
213  VelocityType t) :
214  position(p), velocity(v), veltype(t) { }
215 
216  UT_Vector3R position; // Initial position
217  UT_Vector3R velocity; // Constraint velocity
218  VelocityType veltype;
219  };
220 
221  struct EdgeData
222  {
223  SYS_FORCE_INLINE EdgeData(UT_Vector3R n, fpreal w) :
224  normal(n), weight(w) { }
225 
226  UT_Vector3R normal; // Initial position
227  fpreal weight; // Maximum offset
228  };
229 
230  using PointDataArray = UT_Array<PointData>;
231  using EdgeDataArray = UT_Array<EdgeData>;
232 
233  PointDataArray myPoints;
234  EdgeDataArray myEdges;
235 
236  UT_IntArray myPointLoop;
237  UT_IntArray myEdgeLoop;
238  UT_IntArray myLoopFirstPoint;
239  UT_IntArray myLoopFirstEdge;
240  UT_IntArray myLoopGroup;
241  int myNumLoopGroups = 0;
242 };
243 
244 
245 class Skeleton;
246 
248 {
249 public:
251 
252  /// GU_LoopOffset works on one or more sequences of (point/primitive/vertex)
253  /// offsets on a detail. Each sequence of offsets, along with a *position*
254  /// attribute defines a *chain* of edges. The end-points of the edges, which
255  /// we call the *joints* of the chain, can be repeated along the chain (an
256  /// offset may appear multiple times in the same chain). Each edge of the
257  /// chain is supplied with a velocity vector along which it will be slid.
258  /// It is also possible to override the otherwise calculated joint
259  /// velocities.
260  ///
261  /// The number of chains is specified by 'num_chains'. The 'chain_lengths'
262  /// array should have at least num_chains elements and specifies the number
263  /// of joints in each chain. The 'joint_offsets' array must present the
264  /// joint offsets for all chains back to back and therefore should have
265  /// length (at least) equal to the sum of the elements in 'chain_lengths'.
266  ///
267  /// Each chain can be "closed" or "open", respectively meaning an edge is
268  /// or is not interpreted to exist between the last joint of the chain and
269  /// its first. Setting 'closed_flags' to NULL indicates that all the chains
270  /// are "closed". Otherwise the array to which it points must have least
271  /// num_chains elements.
272  ///
273  /// The 'edge_vel' array must always be supplied with exactly the same
274  /// length as joint_offsets to indicate the velocity vector for the edge
275  /// between the joint at a corresponding position and its successor.
276  /// The velocity vector paired with the last joint of an open chain is
277  /// ignored.
278  ///
279  /// The 'joint_vel' array, provides overrides for the joint velocities that
280  /// are automatically calculated based on edge velocities. Joints with
281  /// override velocity set to (0, 0, 0) still get a calculated velocity.
282  /// However, joints with preset velocities are ensured to always move in
283  /// the given direction even after merging with other trajectories. If two
284  /// joints with preset velocities collide, the insetting limit is reached.
285  ///
286  /// *Two sided* insetters can evaluate both positive and negative inset
287  /// amounts. If 'two-sided' is set to false, evaluation of inset position
288  /// for negative isnet amounts will only use the initial joint velocity
289  /// vectors.
290  ///
291  /// 'collinearity_tol' is the cosine of the largest angle between the
292  /// normals of the planes scanned by two edge velocity vectors below which
293  /// the planes are considered parallel.
294 
295  explicit LoopOffset(LoopSet &&loops,
296  bool two_sided = false,
297  fpreal max_speed = -1);
298 
299  ~LoopOffset();
300 
301  UT_Vector3R offsetPosition(int pt,
302  fpreal offset,
303  bool limit_slides,
304  bool handle_collisions,
305  LimitTriggerMask limit_type,
306  LimitGrouping limit_mode = INDIVIDUAL,
307  int *hits_limit = nullptr,
308  int *is_merged = nullptr);
309 
310  /// Returns the inset value beyond which insetting freezes, ie, the
311  /// outcome stays the same for larger values. If no limit exists, -1 is
312  /// returned.
313  /// If the insetter is two-sided, the returned limit is the the limit of
314  /// the positive side if 'positive' is set true or that of the negative
315  /// side otherwise. If single-sided, the parameter is ignored. Note that
316  /// the limit of the negative side is returned as a positive number if
317  /// such a limit exists (and as -1 otherwise) and the actual limit value
318  /// would be the negative of the returned amount.
319 
320  fpreal getLimit(LimitTriggerMask mask, bool positive = true);
321 
322 
323  static fpreal unitOffsetLength(UT_Vector3R v, UT_Vector3R t0,
324  UT_Vector3R t1);
325 
326  static UT_Vector3R normalBisector(UT_Vector3R t0, UT_Vector3R n0,
328 private:
330 
331  SkeletonUptr myPosSkeleton;
332  SkeletonUptr myNegSkeleton;
333  LoopSet myLoops;
334 };
335 
336 
338 Side
340 {
341  return Side(1 - int(s));
342 }
343 
344 } // namespace GU_PolyBevel3
345 
346 #endif
GLdouble s
Definition: glew.h:1390
SYS_FORCE_INLINE int numEdges() const
GLuint GLuint GLfloat weight
Definition: glew.h:13609
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
GLenum GLint GLuint mask
Definition: glew.h:1845
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 bool isClosed(int l) const
SYS_FORCE_INLINE bool pointHasOffsetLimit(int p) const
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
GLubyte GLubyte GLubyte GLubyte w
Definition: glew.h:1890
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 fpreal edgeWeight(int e) const
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
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