Blender  V3.3
SweepLine.h
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
10 #include <list>
11 #include <vector>
12 
13 #ifdef WITH_CXX_GUARDEDALLOC
14 # include "MEM_guardedalloc.h"
15 #endif
16 
17 namespace Freestyle {
18 
20 template<class Edge> class Intersection {
21  public:
22  template<class EdgeClass> Intersection(EdgeClass *eA, real ta, EdgeClass *eB, real tb)
23  {
24  EdgeA = eA;
25  EdgeB = eB;
26  tA = ta;
27  tB = tb;
28  userdata = 0;
29  }
30 
31  Intersection(const Intersection &iBrother)
32  {
33  EdgeA = iBrother.EdgeA;
34  EdgeB = iBrother.EdgeB;
35  tA = iBrother.tA;
36  tB = iBrother.tB;
37  userdata = 0;
38  }
39 
42  {
43  if (iEdge == EdgeA) {
44  return tA;
45  }
46  if (iEdge == EdgeB) {
47  return tB;
48  }
49  return 0;
50  }
51 
52  public:
53  void *userdata; // FIXME
54 
55  Edge *EdgeA; // first segment
56  Edge *EdgeB; // second segment
57  real tA; // parameter defining the intersection point with respect to the segment EdgeA.
58  real tB; // parameter defining the intersection point with respect to the segment EdgeB.
59 
60 #ifdef WITH_CXX_GUARDEDALLOC
61  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:Intersection")
62 #endif
63 };
64 
65 #ifdef _MSC_VER
66 # pragma warning(push)
67 # pragma warning(disable : 4521) // disable warning C4521: multiple copy constructors specified
68 #endif
69 
70 template<class T, class Point> class Segment {
71  public:
73  {
74  }
75 
76  Segment(T &s, const Point &iA, const Point &iB)
77  {
78  _edge = s;
79  if (iA < iB) {
80  A = iA;
81  B = iB;
82  _order = true;
83  }
84  else {
85  A = iB;
86  B = iA;
87  _order = false;
88  }
89  }
90 
92  {
93  _edge = iBrother.edge();
94  A = iBrother.A;
95  B = iBrother.B;
96  _Intersections = iBrother._Intersections;
97  _order = iBrother._order;
98  }
99 
100  Segment(const Segment<T, Point> &iBrother)
101  {
102  _edge = iBrother._edge;
103  A = iBrother.A;
104  B = iBrother.B;
105  _Intersections = iBrother._Intersections;
106  _order = iBrother._order;
107  }
108 
110  {
111  _Intersections.clear();
112  }
113 
114  inline Point operator[](const unsigned short int &i) const
115  {
116  return (i % 2 == 0) ? A : B;
117  }
118 
119  inline bool operator==(const Segment<T, Point> &iBrother)
120  {
121  if (_edge == iBrother._edge) {
122  return true;
123  }
124  return false;
125  }
126 
127  /* Adds an intersection for this segment */
129  {
130  _Intersections.push_back(i);
131  }
132 
134  inline bool CommonVertex(const Segment<T, Point> &S, Point &CP)
135  {
136  if ((A == S[0]) || (A == S[1])) {
137  CP = A;
138  return true;
139  }
140  if ((B == S[0]) || (B == S[1])) {
141  CP = B;
142  return true;
143  }
144  return false;
145  }
146 
147  inline vector<Intersection<Segment<T, Point>> *> &intersections()
148  {
149  return _Intersections;
150  }
151 
152  inline bool order()
153  {
154  return _order;
155  }
156 
157  inline T &edge()
158  {
159  return _edge;
160  }
161 
162  private:
163  T _edge;
164  Point A;
165  Point B;
166  std::vector<Intersection<Segment<T, Point>> *>
167  _Intersections; // list of intersections parameters
168  bool _order; // true if A and B are in the same order than _edge.A and _edge.B. false otherwise.
169 
170 #ifdef WITH_CXX_GUARDEDALLOC
171  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:Segment")
172 #endif
173 };
174 
175 #ifdef _MSC_VER
176 # pragma warning(pop)
177 #endif
178 
182 template<class T1, class T2> struct binary_rule {
184  {
185  }
186  template<class T3, class T4> binary_rule(const binary_rule<T3, T4> & /*brother*/)
187  {
188  }
189  virtual ~binary_rule()
190  {
191  }
192 
193  virtual bool operator()(T1 &, T2 &)
194  {
195  return true;
196  }
197 };
198 
199 template<class T, class Point> class SweepLine {
200  public:
202  {
203  }
205  {
206  for (typename vector<Intersection<Segment<T, Point>> *>::iterator i = _Intersections.begin(),
207  iend = _Intersections.end();
208  i != iend;
209  i++) {
210  delete (*i);
211  }
212  }
213 
214  inline void process(Point &p,
215  vector<Segment<T, Point> *> &segments,
216 #if 0
219 #else
221 #endif
223  {
224  // first we remove the segments that need to be removed and then we add the segments to add
225  vector<Segment<T, Point> *> toadd;
226  typename vector<Segment<T, Point> *>::iterator s, send;
227  for (s = segments.begin(), send = segments.end(); s != send; s++) {
228  if (p == (*(*s))[0]) {
229  toadd.push_back((*s));
230  }
231  else {
232  remove((*s));
233  }
234  }
235  for (s = toadd.begin(), send = toadd.end(); s != send; s++) {
236  add((*s), binrule, epsilon);
237  }
238  }
239 
240  inline void add(Segment<T, Point> *S,
241 #if 0
244 #else
246 #endif
247  real epsilon)
248  {
249  real t, u;
250  Point CP;
251  Vec2r v0, v1, v2, v3;
252  if (true == S->order()) {
253  v0[0] = ((*S)[0])[0];
254  v0[1] = ((*S)[0])[1];
255  v1[0] = ((*S)[1])[0];
256  v1[1] = ((*S)[1])[1];
257  }
258  else {
259  v1[0] = ((*S)[0])[0];
260  v1[1] = ((*S)[0])[1];
261  v0[0] = ((*S)[1])[0];
262  v0[1] = ((*S)[1])[1];
263  }
264  for (typename std::list<Segment<T, Point> *>::iterator s = _set.begin(), send = _set.end();
265  s != send;
266  s++) {
267  Segment<T, Point> *currentS = (*s);
268  if (true != binrule(*S, *currentS)) {
269  continue;
270  }
271 
272  if (true == currentS->order()) {
273  v2[0] = ((*currentS)[0])[0];
274  v2[1] = ((*currentS)[0])[1];
275  v3[0] = ((*currentS)[1])[0];
276  v3[1] = ((*currentS)[1])[1];
277  }
278  else {
279  v3[0] = ((*currentS)[0])[0];
280  v3[1] = ((*currentS)[0])[1];
281  v2[0] = ((*currentS)[1])[0];
282  v2[1] = ((*currentS)[1])[1];
283  }
284  if (S->CommonVertex(*currentS, CP)) {
285  continue; // the two edges have a common vertex->no need to check
286  }
287 
290  // create the intersection
292  S, t, currentS, u);
293  // add it to the intersections list
294  _Intersections.push_back(inter);
295  // add this intersection to the first edge intersections list
296  S->AddIntersection(inter);
297  // add this intersection to the second edge intersections list
298  currentS->AddIntersection(inter);
299  }
300  }
301  // add the added segment to the list of active segments
302  _set.push_back(S);
303  }
304 
305  inline void remove(Segment<T, Point> *s)
306  {
307  if (s->intersections().size() > 0) {
308  _IntersectedEdges.push_back(s);
309  }
310  _set.remove(s);
311  }
312 
313  vector<Segment<T, Point> *> &intersectedEdges()
314  {
315  return _IntersectedEdges;
316  }
317 
318  vector<Intersection<Segment<T, Point>> *> &intersections()
319  {
320  return _Intersections;
321  }
322 
323  private:
324  std::list<Segment<T, Point> *>
325  _set; // set of active edges for a given position of the sweep line
326  std::vector<Segment<T, Point> *> _IntersectedEdges; // the list of intersected edges
327  std::vector<Intersection<Segment<T, Point>> *> _Intersections; // the list of all intersections.
328 
329 #ifdef WITH_CXX_GUARDEDALLOC
330  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:SweepLine")
331 #endif
332 };
333 
334 } /* namespace Freestyle */
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble t
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
in reality light always falls off quadratically Particle Retrieve the data of the particle that spawned the object for example to give variation to multiple instances of an object Point Retrieve information about points in a point cloud Retrieve the edges of an object as it appears to Cycles topology will always appear triangulated Convert a blackbody temperature to an RGB value Normal Generate a perturbed normal from an RGB normal map image Typically used for faking highly detailed surfaces Generate an OSL shader from a file or text data block Image Sample an image file as a texture Sky Generate a procedural sky texture Noise Generate fractal Perlin noise Wave Generate procedural bands or rings with noise Voronoi Generate Worley noise based on the distance to random points Typically used to generate textures such as or biological cells Brick Generate a procedural texture producing bricks Texture Retrieve multiple types of texture coordinates nTypically used as inputs for texture nodes Vector Convert a vector
ATTR_WARN_UNUSED_RESULT const BMVert * v2
Intersection(EdgeClass *eA, real ta, EdgeClass *eB, real tb)
Definition: SweepLine.h:22
real getParameter(Edge *iEdge)
Definition: SweepLine.h:41
Intersection(const Intersection &iBrother)
Definition: SweepLine.h:31
vector< Intersection< Segment< T, Point > > * > & intersections()
Definition: SweepLine.h:147
Segment(const Segment< T, Point > &iBrother)
Definition: SweepLine.h:100
Segment(T &s, const Point &iA, const Point &iB)
Definition: SweepLine.h:76
bool operator==(const Segment< T, Point > &iBrother)
Definition: SweepLine.h:119
bool CommonVertex(const Segment< T, Point > &S, Point &CP)
Definition: SweepLine.h:134
void AddIntersection(Intersection< Segment< T, Point >> *i)
Definition: SweepLine.h:128
Point operator[](const unsigned short int &i) const
Definition: SweepLine.h:114
Segment(Segment< T, Point > &iBrother)
Definition: SweepLine.h:91
vector< Intersection< Segment< T, Point > > * > & intersections()
Definition: SweepLine.h:318
void process(Point &p, vector< Segment< T, Point > * > &segments, binary_rule< Segment< T, Point >, Segment< T, Point >> &binrule, real epsilon=M_EPSILON)
Definition: SweepLine.h:214
void add(Segment< T, Point > *S, binary_rule< Segment< T, Point >, Segment< T, Point >> &binrule, real epsilon)
Definition: SweepLine.h:240
vector< Segment< T, Point > * > & intersectedEdges()
Definition: SweepLine.h:313
void remove(Segment< T, Point > *s)
Definition: SweepLine.h:305
#define T
#define T2
Definition: md5.cpp:18
#define T1
Definition: md5.cpp:17
intersection_test intersect2dSeg2dSegParametric(const Vec2r &p1, const Vec2r &p2, const Vec2r &p3, const Vec2r &p4, real &t, real &u, real epsilon)
Definition: GeomUtils.cpp:128
inherits from class Rep
Definition: AppCanvas.cpp:18
static const real M_EPSILON
Definition: Precision.h:15
double real
Definition: Precision.h:12
static double epsilon
binary_rule(const binary_rule< T3, T4 > &)
Definition: SweepLine.h:186
virtual ~binary_rule()
Definition: SweepLine.h:189
virtual bool operator()(T1 &, T2 &)
Definition: SweepLine.h:193