Blender  V3.3
CulledOccluderSource.cpp
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
8 #include "CulledOccluderSource.h"
9 
10 #include "../geometry/GridHelpers.h"
11 
12 #include "BKE_global.h"
13 
14 namespace Freestyle {
15 
16 CulledOccluderSource::CulledOccluderSource(const GridHelpers::Transform &t,
17  WingedEdge &we,
18  ViewMap &viewMap,
19  bool extensiveFEdgeSearch)
20  : OccluderSource(t, we), rejected(0), gridSpaceOccluderProsceniumInitialized(false)
21 {
22  cullViewEdges(viewMap, extensiveFEdgeSearch);
23 
24  // If we have not found any visible FEdges during our cull, then there is nothing to iterate
25  // over. Short-circuit everything.
26  valid = gridSpaceOccluderProsceniumInitialized;
27 
28  if (valid && !testCurrent()) {
29  next();
30  }
31 }
32 
33 bool CulledOccluderSource::testCurrent()
34 {
35  if (valid) {
36  // The test for gridSpaceOccluderProsceniumInitialized should not be necessary
37  return gridSpaceOccluderProsceniumInitialized &&
38  GridHelpers::insideProscenium(gridSpaceOccluderProscenium, cachedPolygon);
39  }
40  return false;
41 }
42 
44 {
45  while (OccluderSource::next()) {
46  if (testCurrent()) {
47  ++rejected;
48  return true;
49  }
50  }
51  if (G.debug & G_DEBUG_FREESTYLE) {
52  std::cout << "Finished generating occluders. Rejected " << rejected << " faces." << std::endl;
53  }
54  return false;
55 }
56 
58 {
59  for (unsigned int i = 0; i < 4; ++i) {
60  proscenium[i] = gridSpaceOccluderProscenium[i];
61  }
62 }
63 
64 static inline real distance2D(const Vec3r &point, const real origin[2])
65 {
66  return ::hypot((point[0] - origin[0]), (point[1] - origin[1]));
67 }
68 
69 static inline bool crossesProscenium(real proscenium[4], FEdge *fe)
70 {
71  Vec2r min(proscenium[0], proscenium[2]);
72  Vec2r max(proscenium[1], proscenium[3]);
73  Vec2r A(fe->vertexA()->getProjectedX(), fe->vertexA()->getProjectedY());
74  Vec2r B(fe->vertexB()->getProjectedX(), fe->vertexB()->getProjectedY());
75 
77 }
78 
79 static inline bool insideProscenium(const real proscenium[4], const Vec3r &point)
80 {
81  return !(point[0] < proscenium[0] || point[0] > proscenium[1] || point[1] < proscenium[2] ||
82  point[1] > proscenium[3]);
83 }
84 
85 void CulledOccluderSource::cullViewEdges(ViewMap &viewMap, bool extensiveFEdgeSearch)
86 {
87  // Cull view edges by marking them as non-displayable.
88  // This avoids the complications of trying to delete edges from the ViewMap.
89 
90  // Non-displayable view edges will be skipped over during visibility calculation.
91 
92  // View edges will be culled according to their position w.r.t. the viewport proscenium (viewport
93  // + 5% border, or some such).
94 
95  // Get proscenium boundary for culling
96  real viewProscenium[4];
98  real prosceniumOrigin[2];
99  prosceniumOrigin[0] = (viewProscenium[1] - viewProscenium[0]) / 2.0;
100  prosceniumOrigin[1] = (viewProscenium[3] - viewProscenium[2]) / 2.0;
101  if (G.debug & G_DEBUG_FREESTYLE) {
102  cout << "Proscenium culling:" << endl;
103  cout << "Proscenium: [" << viewProscenium[0] << ", " << viewProscenium[1] << ", "
104  << viewProscenium[2] << ", " << viewProscenium[3] << "]" << endl;
105  cout << "Origin: [" << prosceniumOrigin[0] << ", " << prosceniumOrigin[1] << "]" << endl;
106  }
107 
108  // A separate occluder proscenium will also be maintained, starting out the same as the viewport
109  // proscenium, and expanding as necessary so that it encompasses the center point of at least one
110  // feature edge in each retained view edge. The occluder proscenium will be used later to cull
111  // occluding triangles before they are inserted into the Grid. The occluder proscenium starts out
112  // the same size as the view proscenium
113  GridHelpers::getDefaultViewProscenium(occluderProscenium);
114 
115  // XXX Freestyle is inconsistent in its use of ViewMap::viewedges_container and
116  // vector<ViewEdge*>::iterator. Probably all occurrences of vector<ViewEdge*>::iterator should be
117  // replaced ViewMap::viewedges_container throughout the code. For each view edge
118  ViewMap::viewedges_container::iterator ve, veend;
119 
120  for (ve = viewMap.ViewEdges().begin(), veend = viewMap.ViewEdges().end(); ve != veend; ve++) {
121  // Overview:
122  // Search for a visible feature edge
123  // If none: mark view edge as non-displayable
124  // Otherwise:
125  // Find a feature edge with center point inside occluder proscenium.
126  // If none exists, find the feature edge with center point closest to viewport origin.
127  // Expand occluder proscenium to enclose center point.
128 
129  // For each feature edge, while bestOccluderTarget not found and view edge not visible
130  bool bestOccluderTargetFound = false;
131  FEdge *bestOccluderTarget = nullptr;
132  real bestOccluderDistance = 0.0;
133  FEdge *festart = (*ve)->fedgeA();
134  FEdge *fe = festart;
135  // All ViewEdges start culled
136  (*ve)->setIsInImage(false);
137 
138  // For simple visibility calculation: mark a feature edge that is known to have a center point
139  // inside the occluder proscenium. Cull all other feature edges.
140  do {
141  // All FEdges start culled
142  fe->setIsInImage(false);
143 
144  // Look for the visible edge that can most easily be included in the occluder proscenium.
145  if (!bestOccluderTargetFound) {
146  // If center point is inside occluder proscenium,
147  if (insideProscenium(occluderProscenium, fe->center2d())) {
148  // Use this feature edge for visibility deterimination
149  fe->setIsInImage(true);
150  expandGridSpaceOccluderProscenium(fe);
151  // Mark bestOccluderTarget as found
152  bestOccluderTargetFound = true;
153  bestOccluderTarget = fe;
154  }
155  else {
156  real d = distance2D(fe->center2d(), prosceniumOrigin);
157  // If center point is closer to viewport origin than current target
158  if (bestOccluderTarget == nullptr || d < bestOccluderDistance) {
159  // Then store as bestOccluderTarget
160  bestOccluderDistance = d;
161  bestOccluderTarget = fe;
162  }
163  }
164  }
165 
166  // If feature edge crosses the view proscenium
167  if (!(*ve)->isInImage() && crossesProscenium(viewProscenium, fe)) {
168  // Then the view edge will be included in the image
169  (*ve)->setIsInImage(true);
170  }
171  fe = fe->nextEdge();
172  } while (fe != nullptr && fe != festart && !(bestOccluderTargetFound && (*ve)->isInImage()));
173 
174  // Either we have run out of FEdges, or we already have the one edge we need to determine
175  // visibility Cull all remaining edges.
176  while (!ELEM(fe, NULL, festart)) {
177  fe->setIsInImage(false);
178  fe = fe->nextEdge();
179  }
180 
181  // If bestOccluderTarget was not found inside the occluder proscenium,
182  // we need to expand the occluder proscenium to include it.
183  if ((*ve)->isInImage() && bestOccluderTarget != nullptr && !bestOccluderTargetFound) {
184  // Expand occluder proscenium to enclose bestOccluderTarget
185  Vec3r point = bestOccluderTarget->center2d();
186  if (point[0] < occluderProscenium[0]) {
187  occluderProscenium[0] = point[0];
188  }
189  else if (point[0] > occluderProscenium[1]) {
190  occluderProscenium[1] = point[0];
191  }
192  if (point[1] < occluderProscenium[2]) {
193  occluderProscenium[2] = point[1];
194  }
195  else if (point[1] > occluderProscenium[3]) {
196  occluderProscenium[3] = point[1];
197  }
198  // Use bestOccluderTarget for visibility determination
199  bestOccluderTarget->setIsInImage(true);
200  }
201  }
202 
203  // We are done calculating the occluder proscenium.
204  // Expand the occluder proscenium by an epsilon to avoid rounding errors.
205  const real epsilon = 1.0e-6;
206  occluderProscenium[0] -= epsilon;
207  occluderProscenium[1] += epsilon;
208  occluderProscenium[2] -= epsilon;
209  occluderProscenium[3] += epsilon;
210 
211  // For "Normal" or "Fast" style visibility computation only:
212 
213  // For more detailed visibility calculation, make a second pass through the view map, marking all
214  // feature edges with center points inside the final occluder proscenium. All of these feature
215  // edges can be considered during visibility calculation.
216 
217  // So far we have only found one FEdge per ViewEdge. The "Normal" and "Fast" styles of visibility
218  // computation want to consider many FEdges for each ViewEdge. Here we re-scan the view map to
219  // find any usable FEdges that we skipped on the first pass, or that have become usable because
220  // the occluder proscenium has been expanded since the edge was visited on the first pass.
221  if (extensiveFEdgeSearch) {
222  // For each view edge,
223  for (ve = viewMap.ViewEdges().begin(), veend = viewMap.ViewEdges().end(); ve != veend; ve++) {
224  if (!(*ve)->isInImage()) {
225  continue;
226  }
227  // For each feature edge,
228  FEdge *festart = (*ve)->fedgeA();
229  FEdge *fe = festart;
230  do {
231  // If not (already) visible and center point inside occluder proscenium,
232  if (!fe->isInImage() && insideProscenium(occluderProscenium, fe->center2d())) {
233  // Use the feature edge for visibility determination
234  fe->setIsInImage(true);
235  expandGridSpaceOccluderProscenium(fe);
236  }
237  fe = fe->nextEdge();
238  } while (!ELEM(fe, NULL, festart));
239  }
240  }
241 
242  // Up until now, all calculations have been done in camera space.
243  // However, the occluder source's iteration and the grid that consumes the occluders both work in
244  // gridspace, so we need a version of the occluder proscenium in gridspace. Set the gridspace
245  // occlude proscenium
246 }
247 
248 void CulledOccluderSource::expandGridSpaceOccluderProscenium(FEdge *fe)
249 {
250  if (gridSpaceOccluderProsceniumInitialized) {
251  GridHelpers::expandProscenium(gridSpaceOccluderProscenium, transform(fe->center3d()));
252  }
253  else {
254  const Vec3r &point = transform(fe->center3d());
255  gridSpaceOccluderProscenium[0] = gridSpaceOccluderProscenium[1] = point[0];
256  gridSpaceOccluderProscenium[2] = gridSpaceOccluderProscenium[3] = point[1];
257  gridSpaceOccluderProsceniumInitialized = true;
258  }
259 }
260 
261 } /* namespace Freestyle */
@ G_DEBUG_FREESTYLE
Definition: BKE_global.h:181
#define ELEM(...)
Class to define a cell grid surrounding the projected image of a scene.
_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
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 point
#define A
void getOccluderProscenium(real proscenium[4])
void cullViewEdges(ViewMap &viewMap, bool extensiveFEdgeSearch)
Vec3r center2d()
Definition: Silhouette.h:668
SVertex * vertexA()
Definition: Silhouette.h:597
bool isInImage() const
Definition: Silhouette.h:711
SVertex * vertexB()
Definition: Silhouette.h:603
Vec3r center3d()
Definition: Silhouette.h:663
void setIsInImage(bool iFlag)
Definition: Silhouette.h:811
FEdge * nextEdge()
Definition: Silhouette.h:623
const GridHelpers::Transform & transform
virtual real getProjectedY() const
Definition: Silhouette.h:96
virtual real getProjectedX() const
Definition: Silhouette.h:90
viewedges_container & ViewEdges()
Definition: ViewMap.h:103
#define B
#define G(x, y, z)
bool intersect2dSeg2dArea(const Vec2r &min, const Vec2r &max, const Vec2r &A, const Vec2r &B)
Definition: GeomUtils.cpp:15
VecMat::Vec3< real > Vec3r
Definition: Geom.h:28
void getDefaultViewProscenium(real viewProscenium[4])
Definition: GridHelpers.cpp:12
void expandProscenium(real proscenium[4], const Polygon3r &polygon)
Definition: GridHelpers.h:152
bool insideProscenium(const real proscenium[4], const Polygon3r &polygon)
Definition: GridHelpers.h:112
inherits from class Rep
Definition: AppCanvas.cpp:18
static real distance2D(const Vec3r &point, const real origin[2])
static bool insideProscenium(const real proscenium[4], const Vec3r &point)
static bool crossesProscenium(real proscenium[4], FEdge *fe)
double real
Definition: Precision.h:12
INLINE Rall1d< T, V, S > hypot(const Rall1d< T, V, S > &y, const Rall1d< T, V, S > &x)
Definition: rall1d.h:383
static double epsilon
#define min(a, b)
Definition: sort.c:35
float max