Blender  V3.3
ViewMapBuilder.cpp
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
8 #include <algorithm>
9 #include <memory>
10 #include <sstream>
11 #include <stdexcept>
12 
13 #include "FRS_freestyle.h"
14 
15 #include "BoxGrid.h"
16 #include "CulledOccluderSource.h"
18 #include "OccluderSource.h"
19 #include "SphericalGrid.h"
20 #include "ViewMapBuilder.h"
21 
22 #include "../geometry/GeomUtils.h"
23 #include "../geometry/GridHelpers.h"
24 
25 #include "../winged_edge/WFillGrid.h"
26 
27 #include "BKE_global.h"
28 
29 namespace Freestyle {
30 
31 // XXX Grmll... G is used as template's typename parameter :/
32 static const Global &_global = G;
33 
34 #define LOGGING 0
35 
36 using namespace std;
37 
38 template<typename G, typename I>
39 static void findOccludee(FEdge *fe,
40  G & /*grid*/,
41  I &occluders,
42  real epsilon,
43  WFace **oaWFace,
44  Vec3r &u,
45  Vec3r &A,
46  Vec3r &origin,
47  Vec3r &edgeDir,
48  vector<WVertex *> &faceVertices)
49 {
50  WFace *face = nullptr;
51  if (fe->isSmooth()) {
52  FEdgeSmooth *fes = dynamic_cast<FEdgeSmooth *>(fe);
53  face = (WFace *)fes->face();
54  }
55  WFace *oface;
56  bool skipFace;
57 
59 
60  *oaWFace = nullptr;
61  if (((fe)->getNature() & Nature::SILHOUETTE) || ((fe)->getNature() & Nature::BORDER)) {
62  // we cast a ray from A in the same direction but looking behind
63  Vec3r v(-u[0], -u[1], -u[2]);
64  bool noIntersection = true;
65  real mint = FLT_MAX;
66 
67  for (occluders.initAfterTarget(); occluders.validAfterTarget(); occluders.nextOccludee()) {
68 #if LOGGING
70  cout << "\t\tEvaluating intersection for occludee " << occluders.getWFace() << " and ray "
71  << A << " * " << u << endl;
72  }
73 #endif
74  oface = occluders.getWFace();
75  Polygon3r *p = occluders.getCameraSpacePolygon();
76  real d = -((p->getVertices())[0] * p->getNormal());
77  real t, t_u, t_v;
78 
79  if (nullptr != face) {
80  skipFace = false;
81 
82  if (face == oface) {
83  continue;
84  }
85 
86  if (faceVertices.empty()) {
87  continue;
88  }
89 
90  for (vector<WVertex *>::iterator fv = faceVertices.begin(), fvend = faceVertices.end();
91  fv != fvend;
92  ++fv) {
93  if ((*fv)->isBoundary()) {
94  continue;
95  }
96  WVertex::incoming_edge_iterator iebegin = (*fv)->incoming_edges_begin();
97  WVertex::incoming_edge_iterator ieend = (*fv)->incoming_edges_end();
98  for (ie = iebegin; ie != ieend; ++ie) {
99  if ((*ie) == nullptr) {
100  continue;
101  }
102 
103  WFace *sface = (*ie)->GetbFace();
104  if (sface == oface) {
105  skipFace = true;
106  break;
107  }
108  }
109  if (skipFace) {
110  break;
111  }
112  }
113  if (skipFace) {
114  continue;
115  }
116  }
117  else {
118  // check whether the edge and the polygon plane are coincident:
119  //-------------------------------------------------------------
120  // first let us compute the plane equation.
121  if (GeomUtils::COINCIDENT ==
122  GeomUtils::intersectRayPlane(origin, edgeDir, p->getNormal(), d, t, epsilon)) {
123 #if LOGGING
125  cout << "\t\tRejecting occluder for target coincidence." << endl;
126  }
127 #endif
128  continue;
129  }
130  }
131 
132  if (p->rayIntersect(A, v, t, t_u, t_v)) {
133 #if LOGGING
135  cout << "\t\tRay " << A << " * " << v << " intersects at time " << t << endl;
136  cout << "\t\t(v * normal) == " << (v * p->getNormal()) << " for normal "
137  << p->getNormal() << endl;
138  }
139 #endif
140  if (fabs(v * p->getNormal()) > 0.0001) {
141  if ((t > 0.0) /* && (t<1.0) */) {
142  if (t < mint) {
143  *oaWFace = oface;
144  mint = t;
145  noIntersection = false;
146  fe->setOccludeeIntersection(Vec3r(A + t * v));
147 #if LOGGING
149  cout << "\t\tIs occludee" << endl;
150  }
151 #endif
152  }
153  }
154  }
155 
156  occluders.reportDepth(A, v, t);
157  }
158  }
159 
160  if (noIntersection) {
161  *oaWFace = nullptr;
162  }
163  }
164 }
165 
166 template<typename G, typename I>
167 static void findOccludee(FEdge *fe, G &grid, real epsilon, ViewEdge * /*ve*/, WFace **oaFace)
168 {
169  Vec3r A;
170  Vec3r edgeDir;
171  Vec3r origin;
172  A = Vec3r(((fe)->vertexA()->point3D() + (fe)->vertexB()->point3D()) / 2.0);
173  edgeDir = Vec3r((fe)->vertexB()->point3D() - (fe)->vertexA()->point3D());
174  edgeDir.normalize();
175  origin = Vec3r((fe)->vertexA()->point3D());
176  Vec3r u;
177  if (grid.orthographicProjection()) {
178  u = Vec3r(0.0, 0.0, grid.viewpoint().z() - A.z());
179  }
180  else {
181  u = Vec3r(grid.viewpoint() - A);
182  }
183  u.normalize();
184 
185  vector<WVertex *> faceVertices;
186 
187  WFace *face = nullptr;
188  if (fe->isSmooth()) {
189  FEdgeSmooth *fes = dynamic_cast<FEdgeSmooth *>(fe);
190  face = (WFace *)fes->face();
191  }
192 
193  if (face) {
194  face->RetrieveVertexList(faceVertices);
195  }
196 
197  I occluders(grid, A, epsilon);
198  findOccludee<G, I>(fe, grid, occluders, epsilon, oaFace, u, A, origin, edgeDir, faceVertices);
199 }
200 
201 // computeVisibility takes a pointer to foundOccluders, instead of using a reference,
202 // so that computeVeryFastVisibility can skip the AddOccluders step with minimal overhead.
203 template<typename G, typename I>
204 static int computeVisibility(ViewMap *viewMap,
205  FEdge *fe,
206  G &grid,
207  real epsilon,
208  ViewEdge * /*ve*/,
209  WFace **oaWFace,
210  set<ViewShape *> *foundOccluders)
211 {
212  int qi = 0;
213 
214  Vec3r center;
215  Vec3r edgeDir;
216  Vec3r origin;
217 
218  center = fe->center3d();
219  edgeDir = Vec3r(fe->vertexB()->point3D() - fe->vertexA()->point3D());
220  edgeDir.normalize();
221  origin = Vec3r(fe->vertexA()->point3D());
222 
223  Vec3r vp;
224  if (grid.orthographicProjection()) {
225  vp = Vec3r(center.x(), center.y(), grid.viewpoint().z());
226  }
227  else {
228  vp = Vec3r(grid.viewpoint());
229  }
230  Vec3r u(vp - center);
231  real raylength = u.norm();
232  u.normalize();
233 
234  WFace *face = nullptr;
235  if (fe->isSmooth()) {
236  FEdgeSmooth *fes = dynamic_cast<FEdgeSmooth *>(fe);
237  face = (WFace *)fes->face();
238  }
239  vector<WVertex *> faceVertices;
241 
242  WFace *oface;
243  bool skipFace;
244 
245  if (face) {
246  face->RetrieveVertexList(faceVertices);
247  }
248 
249  I occluders(grid, center, epsilon);
250 
251  for (occluders.initBeforeTarget(); occluders.validBeforeTarget(); occluders.nextOccluder()) {
252  // If we're dealing with an exact silhouette, check whether we must take care of this occluder
253  // of not. (Indeed, we don't consider the occluders that share at least one vertex with the
254  // face containing this edge).
255  //-----------
256  oface = occluders.getWFace();
257  Polygon3r *p = occluders.getCameraSpacePolygon();
258  real t, t_u, t_v;
259 #if LOGGING
261  cout << "\t\tEvaluating intersection for occluder " << (p->getVertices())[0]
262  << (p->getVertices())[1] << (p->getVertices())[2] << endl
263  << "\t\t\tand ray " << vp << " * " << u << " (center " << center << ")" << endl;
264  }
265 #endif
266 
267 #if LOGGING
268  Vec3r v(vp - center);
269  real rl = v.norm();
270  v.normalize();
271  vector<Vec3r> points;
272  // Iterate over vertices, storing projections in points
273  for (vector<WOEdge *>::const_iterator woe = oface->getEdgeList().begin(),
274  woend = oface->getEdgeList().end();
275  woe != woend;
276  woe++) {
277  points.push_back(Vec3r((*woe)->GetaVertex()->GetVertex()));
278  }
279  Polygon3r p1(points, oface->GetNormal());
280  Vec3r v1((p1.getVertices())[0]);
281  real d = -(v1 * p->getNormal());
283  cout << "\t\tp: " << (p->getVertices())[0] << (p->getVertices())[1] << (p->getVertices())[2]
284  << ", norm: " << p->getNormal() << endl;
285  cout << "\t\tp1: " << (p1.getVertices())[0] << (p1.getVertices())[1] << (p1.getVertices())[2]
286  << ", norm: " << p1.getNormal() << endl;
287  }
288 #else
289  real d = -((p->getVertices())[0] * p->getNormal());
290 #endif
291 
292  if (face) {
293 #if LOGGING
295  cout << "\t\tDetermining face adjacency...";
296  }
297 #endif
298  skipFace = false;
299 
300  if (face == oface) {
301 #if LOGGING
303  cout << " Rejecting occluder for face concurrency." << endl;
304  }
305 #endif
306  continue;
307  }
308 
309  for (vector<WVertex *>::iterator fv = faceVertices.begin(), fvend = faceVertices.end();
310  fv != fvend;
311  ++fv) {
312  if ((*fv)->isBoundary()) {
313  continue;
314  }
315 
316  WVertex::incoming_edge_iterator iebegin = (*fv)->incoming_edges_begin();
317  WVertex::incoming_edge_iterator ieend = (*fv)->incoming_edges_end();
318  for (ie = iebegin; ie != ieend; ++ie) {
319  if ((*ie) == nullptr) {
320  continue;
321  }
322 
323  WFace *sface = (*ie)->GetbFace();
324  // WFace *sfacea = (*ie)->GetaFace();
325  // if ((sface == oface) || (sfacea == oface))
326  if (sface == oface) {
327  skipFace = true;
328  break;
329  }
330  }
331  if (skipFace) {
332  break;
333  }
334  }
335  if (skipFace) {
336 #if LOGGING
338  cout << " Rejecting occluder for face adjacency." << endl;
339  }
340 #endif
341  continue;
342  }
343  }
344  else {
345  // check whether the edge and the polygon plane are coincident:
346  //-------------------------------------------------------------
347  // first let us compute the plane equation.
348  if (GeomUtils::COINCIDENT ==
349  GeomUtils::intersectRayPlane(origin, edgeDir, p->getNormal(), d, t, epsilon)) {
350 #if LOGGING
352  cout << "\t\tRejecting occluder for target coincidence." << endl;
353  }
354 #endif
355  continue;
356  }
357  }
358 
359 #if LOGGING
361  real x;
362  if (p1.rayIntersect(center, v, x, t_u, t_v)) {
363  cout << "\t\tRay should intersect at time " << (rl - x) << ". Center: " << center
364  << ", V: " << v << ", RL: " << rl << ", T:" << x << endl;
365  }
366  else {
367  cout << "\t\tRay should not intersect. Center: " << center << ", V: " << v
368  << ", RL: " << rl << endl;
369  }
370  }
371 #endif
372 
373  if (p->rayIntersect(center, u, t, t_u, t_v)) {
374 #if LOGGING
376  cout << "\t\tRay " << center << " * " << u << " intersects at time " << t
377  << " (raylength is " << raylength << ")" << endl;
378  cout << "\t\t(u * normal) == " << (u * p->getNormal()) << " for normal " << p->getNormal()
379  << endl;
380  }
381 #endif
382  if (fabs(u * p->getNormal()) > 0.0001) {
383  if ((t > 0.0) && (t < raylength)) {
384 #if LOGGING
386  cout << "\t\tIs occluder" << endl;
387  }
388 #endif
389  if (foundOccluders != nullptr) {
390  ViewShape *vshape = viewMap->viewShape(oface->GetVertex(0)->shape()->GetId());
391  foundOccluders->insert(vshape);
392  }
393  ++qi;
394 
395  if (!grid.enableQI()) {
396  break;
397  }
398  }
399 
400  occluders.reportDepth(center, u, t);
401  }
402  }
403  }
404 
405  // Find occludee
406  findOccludee<G, I>(
407  fe, grid, occluders, epsilon, oaWFace, u, center, origin, edgeDir, faceVertices);
408 
409  return qi;
410 }
411 
412 // computeCumulativeVisibility returns the lowest x such that the majority of FEdges have QI <= x
413 //
414 // This was probably the original intention of the "normal" algorithm on which
415 // computeDetailedVisibility is based. But because the "normal" algorithm chooses the most popular
416 // QI, without considering any other values, a ViewEdge with FEdges having QIs of 0, 21, 22, 23, 24
417 // and 25 will end up having a total QI of 0, even though most of the FEdges are heavily occluded.
418 // computeCumulativeVisibility will treat this case as a QI of 22 because 3 out of 6 occluders have
419 // QI <= 22.
420 
421 template<typename G, typename I>
422 static void computeCumulativeVisibility(ViewMap *ioViewMap,
423  G &grid,
424  real epsilon,
425  RenderMonitor *iRenderMonitor)
426 {
427  vector<ViewEdge *> &vedges = ioViewMap->ViewEdges();
428 
429  FEdge *fe, *festart;
430  int nSamples = 0;
431  vector<WFace *> wFaces;
432  WFace *wFace = nullptr;
433  unsigned count = 0;
434  unsigned count_step = (unsigned)ceil(0.01f * vedges.size());
435  unsigned tmpQI = 0;
436  unsigned qiClasses[256];
437  unsigned maxIndex, maxCard;
438  unsigned qiMajority;
439  for (vector<ViewEdge *>::iterator ve = vedges.begin(), veend = vedges.end(); ve != veend; ve++) {
440  if (iRenderMonitor) {
441  if (iRenderMonitor->testBreak()) {
442  break;
443  }
444  if (count % count_step == 0) {
445  stringstream ss;
446  ss << "Freestyle: Visibility computations " << (100 * count / vedges.size()) << "%";
447  iRenderMonitor->setInfo(ss.str());
448  iRenderMonitor->progress((float)count / vedges.size());
449  }
450  count++;
451  }
452 #if LOGGING
454  cout << "Processing ViewEdge " << (*ve)->getId() << endl;
455  }
456 #endif
457  // Find an edge to test
458  if (!(*ve)->isInImage()) {
459  // This view edge has been proscenium culled
460  (*ve)->setQI(255);
461  (*ve)->setaShape(nullptr);
462 #if LOGGING
464  cout << "\tCulled." << endl;
465  }
466 #endif
467  continue;
468  }
469 
470  // Test edge
471  festart = (*ve)->fedgeA();
472  fe = (*ve)->fedgeA();
473  qiMajority = 0;
474  do {
475  if (fe != nullptr && fe->isInImage()) {
476  qiMajority++;
477  }
478  fe = fe->nextEdge();
479  } while (fe && fe != festart);
480 
481  if (qiMajority == 0) {
482  // There are no occludable FEdges on this ViewEdge
483  // This should be impossible.
485  cout << "View Edge in viewport without occludable FEdges: " << (*ve)->getId() << endl;
486  }
487  // We can recover from this error:
488  // Treat this edge as fully visible with no occludee
489  (*ve)->setQI(0);
490  (*ve)->setaShape(nullptr);
491  continue;
492  }
493 
494  ++qiMajority;
495  qiMajority >>= 1;
496 
497 #if LOGGING
499  cout << "\tqiMajority: " << qiMajority << endl;
500  }
501 #endif
502 
503  tmpQI = 0;
504  maxIndex = 0;
505  maxCard = 0;
506  nSamples = 0;
507  memset(qiClasses, 0, 256 * sizeof(*qiClasses));
508  set<ViewShape *> foundOccluders;
509 
510  fe = (*ve)->fedgeA();
511  do {
512  if (!fe || !fe->isInImage()) {
513  fe = fe->nextEdge();
514  continue;
515  }
516  if (maxCard < qiMajority) {
517  // ARB: change &wFace to wFace and use reference in called function
518  tmpQI = computeVisibility<G, I>(
519  ioViewMap, fe, grid, epsilon, *ve, &wFace, &foundOccluders);
520 #if LOGGING
522  cout << "\tFEdge: visibility " << tmpQI << endl;
523  }
524 #endif
525 
526  // ARB: This is an error condition, not an alert condition.
527  // Some sort of recovery or abort is necessary.
528  if (tmpQI >= 256) {
529  cerr << "Warning: too many occluding levels" << endl;
530  // ARB: Wild guess: instead of aborting or corrupting memory, treat as tmpQI == 255
531  tmpQI = 255;
532  }
533 
534  if (++qiClasses[tmpQI] > maxCard) {
535  maxCard = qiClasses[tmpQI];
536  maxIndex = tmpQI;
537  }
538  }
539  else {
540  // ARB: FindOccludee is redundant if ComputeRayCastingVisibility has been called
541  // ARB: change &wFace to wFace and use reference in called function
542  findOccludee<G, I>(fe, grid, epsilon, *ve, &wFace);
543 #if LOGGING
545  cout << "\tFEdge: occludee only (" << (wFace != NULL ? "found" : "not found") << ")"
546  << endl;
547  }
548 #endif
549  }
550 
551  // Store test results
552  if (wFace) {
553  vector<Vec3r> vertices;
554  for (int i = 0, numEdges = wFace->numberOfEdges(); i < numEdges; ++i) {
555  vertices.emplace_back(wFace->GetVertex(i)->GetVertex());
556  }
557  Polygon3r poly(vertices, wFace->GetNormal());
558  poly.userdata = (void *)wFace;
559  fe->setaFace(poly);
560  wFaces.push_back(wFace);
561  fe->setOccludeeEmpty(false);
562 #if LOGGING
564  cout << "\tFound occludee" << endl;
565  }
566 #endif
567  }
568  else {
569  fe->setOccludeeEmpty(true);
570  }
571 
572  ++nSamples;
573  fe = fe->nextEdge();
574  } while ((maxCard < qiMajority) && (fe) && (fe != festart));
575 
576 #if LOGGING
578  cout << "\tFinished with " << nSamples << " samples, maxCard = " << maxCard << endl;
579  }
580 #endif
581 
582  // ViewEdge
583  // qi --
584  // Find the minimum value that is >= the majority of the QI
585  for (unsigned count = 0, i = 0; i < 256; ++i) {
586  count += qiClasses[i];
587  if (count >= qiMajority) {
588  (*ve)->setQI(i);
589  break;
590  }
591  }
592  // occluders --
593  // I would rather not have to go through the effort of creating this set and then copying out
594  // its contents. Is there a reason why ViewEdge::_Occluders cannot be converted to a set<>?
595  for (set<ViewShape *>::iterator o = foundOccluders.begin(), oend = foundOccluders.end();
596  o != oend;
597  ++o) {
598  (*ve)->AddOccluder((*o));
599  }
600 #if LOGGING
602  cout << "\tConclusion: QI = " << maxIndex << ", " << (*ve)->occluders_size() << " occluders."
603  << endl;
604  }
605 #else
606  (void)maxIndex;
607 #endif
608  // occludee --
609  if (!wFaces.empty()) {
610  if (wFaces.size() <= (float)nSamples / 2.0f) {
611  (*ve)->setaShape(nullptr);
612  }
613  else {
614  ViewShape *vshape = ioViewMap->viewShape(
615  (*wFaces.begin())->GetVertex(0)->shape()->GetId());
616  (*ve)->setaShape(vshape);
617  }
618  }
619 
620  wFaces.clear();
621  }
622  if (iRenderMonitor && !vedges.empty()) {
623  stringstream ss;
624  ss << "Freestyle: Visibility computations " << (100 * count / vedges.size()) << "%";
625  iRenderMonitor->setInfo(ss.str());
626  iRenderMonitor->progress((float)count / vedges.size());
627  }
628 }
629 
630 template<typename G, typename I>
631 static void computeDetailedVisibility(ViewMap *ioViewMap,
632  G &grid,
633  real epsilon,
634  RenderMonitor *iRenderMonitor)
635 {
636  vector<ViewEdge *> &vedges = ioViewMap->ViewEdges();
637 
638  FEdge *fe, *festart;
639  int nSamples = 0;
640  vector<WFace *> wFaces;
641  WFace *wFace = nullptr;
642  unsigned tmpQI = 0;
643  unsigned qiClasses[256];
644  unsigned maxIndex, maxCard;
645  unsigned qiMajority;
646  for (vector<ViewEdge *>::iterator ve = vedges.begin(), veend = vedges.end(); ve != veend; ve++) {
647  if (iRenderMonitor && iRenderMonitor->testBreak()) {
648  break;
649  }
650 #if LOGGING
652  cout << "Processing ViewEdge " << (*ve)->getId() << endl;
653  }
654 #endif
655  // Find an edge to test
656  if (!(*ve)->isInImage()) {
657  // This view edge has been proscenium culled
658  (*ve)->setQI(255);
659  (*ve)->setaShape(nullptr);
660 #if LOGGING
662  cout << "\tCulled." << endl;
663  }
664 #endif
665  continue;
666  }
667 
668  // Test edge
669  festart = (*ve)->fedgeA();
670  fe = (*ve)->fedgeA();
671  qiMajority = 0;
672  do {
673  if (fe != nullptr && fe->isInImage()) {
674  qiMajority++;
675  }
676  fe = fe->nextEdge();
677  } while (fe && fe != festart);
678 
679  if (qiMajority == 0) {
680  // There are no occludable FEdges on this ViewEdge
681  // This should be impossible.
683  cout << "View Edge in viewport without occludable FEdges: " << (*ve)->getId() << endl;
684  }
685  // We can recover from this error:
686  // Treat this edge as fully visible with no occludee
687  (*ve)->setQI(0);
688  (*ve)->setaShape(nullptr);
689  continue;
690  }
691 
692  ++qiMajority;
693  qiMajority >>= 1;
694 
695 #if LOGGING
697  cout << "\tqiMajority: " << qiMajority << endl;
698  }
699 #endif
700 
701  tmpQI = 0;
702  maxIndex = 0;
703  maxCard = 0;
704  nSamples = 0;
705  memset(qiClasses, 0, 256 * sizeof(*qiClasses));
706  set<ViewShape *> foundOccluders;
707 
708  fe = (*ve)->fedgeA();
709  do {
710  if (fe == nullptr || !fe->isInImage()) {
711  fe = fe->nextEdge();
712  continue;
713  }
714  if (maxCard < qiMajority) {
715  // ARB: change &wFace to wFace and use reference in called function
716  tmpQI = computeVisibility<G, I>(
717  ioViewMap, fe, grid, epsilon, *ve, &wFace, &foundOccluders);
718 #if LOGGING
720  cout << "\tFEdge: visibility " << tmpQI << endl;
721  }
722 #endif
723 
724  // ARB: This is an error condition, not an alert condition.
725  // Some sort of recovery or abort is necessary.
726  if (tmpQI >= 256) {
727  cerr << "Warning: too many occluding levels" << endl;
728  // ARB: Wild guess: instead of aborting or corrupting memory, treat as tmpQI == 255
729  tmpQI = 255;
730  }
731 
732  if (++qiClasses[tmpQI] > maxCard) {
733  maxCard = qiClasses[tmpQI];
734  maxIndex = tmpQI;
735  }
736  }
737  else {
738  // ARB: FindOccludee is redundant if ComputeRayCastingVisibility has been called
739  // ARB: change &wFace to wFace and use reference in called function
740  findOccludee<G, I>(fe, grid, epsilon, *ve, &wFace);
741 #if LOGGING
743  cout << "\tFEdge: occludee only (" << (wFace != NULL ? "found" : "not found") << ")"
744  << endl;
745  }
746 #endif
747  }
748 
749  // Store test results
750  if (wFace) {
751  vector<Vec3r> vertices;
752  for (int i = 0, numEdges = wFace->numberOfEdges(); i < numEdges; ++i) {
753  vertices.emplace_back(wFace->GetVertex(i)->GetVertex());
754  }
755  Polygon3r poly(vertices, wFace->GetNormal());
756  poly.userdata = (void *)wFace;
757  fe->setaFace(poly);
758  wFaces.push_back(wFace);
759  fe->setOccludeeEmpty(false);
760 #if LOGGING
762  cout << "\tFound occludee" << endl;
763  }
764 #endif
765  }
766  else {
767  fe->setOccludeeEmpty(true);
768  }
769 
770  ++nSamples;
771  fe = fe->nextEdge();
772  } while ((maxCard < qiMajority) && (fe) && (fe != festart));
773 
774 #if LOGGING
776  cout << "\tFinished with " << nSamples << " samples, maxCard = " << maxCard << endl;
777  }
778 #endif
779 
780  // ViewEdge
781  // qi --
782  (*ve)->setQI(maxIndex);
783  // occluders --
784  // I would rather not have to go through the effort of creating this this set and then copying
785  // out its contents. Is there a reason why ViewEdge::_Occluders cannot be converted to a set<>?
786  for (set<ViewShape *>::iterator o = foundOccluders.begin(), oend = foundOccluders.end();
787  o != oend;
788  ++o) {
789  (*ve)->AddOccluder((*o));
790  }
791 #if LOGGING
793  cout << "\tConclusion: QI = " << maxIndex << ", " << (*ve)->occluders_size() << " occluders."
794  << endl;
795  }
796 #endif
797  // occludee --
798  if (!wFaces.empty()) {
799  if (wFaces.size() <= (float)nSamples / 2.0f) {
800  (*ve)->setaShape(nullptr);
801  }
802  else {
803  ViewShape *vshape = ioViewMap->viewShape(
804  (*wFaces.begin())->GetVertex(0)->shape()->GetId());
805  (*ve)->setaShape(vshape);
806  }
807  }
808 
809  wFaces.clear();
810  }
811 }
812 
813 template<typename G, typename I>
814 static void computeFastVisibility(ViewMap *ioViewMap, G &grid, real epsilon)
815 {
816  vector<ViewEdge *> &vedges = ioViewMap->ViewEdges();
817 
818  FEdge *fe, *festart;
819  unsigned nSamples = 0;
820  vector<WFace *> wFaces;
821  WFace *wFace = nullptr;
822  unsigned tmpQI = 0;
823  unsigned qiClasses[256];
824  unsigned maxIndex, maxCard;
825  unsigned qiMajority;
826  bool even_test;
827  for (vector<ViewEdge *>::iterator ve = vedges.begin(), veend = vedges.end(); ve != veend; ve++) {
828  // Find an edge to test
829  if (!(*ve)->isInImage()) {
830  // This view edge has been proscenium culled
831  (*ve)->setQI(255);
832  (*ve)->setaShape(nullptr);
833  continue;
834  }
835 
836  // Test edge
837  festart = (*ve)->fedgeA();
838  fe = (*ve)->fedgeA();
839 
840  even_test = true;
841  qiMajority = 0;
842  do {
843  if (even_test && fe && fe->isInImage()) {
844  qiMajority++;
845  even_test = !even_test;
846  }
847  fe = fe->nextEdge();
848  } while (fe && fe != festart);
849 
850  if (qiMajority == 0) {
851  // There are no occludable FEdges on this ViewEdge
852  // This should be impossible.
854  cout << "View Edge in viewport without occludable FEdges: " << (*ve)->getId() << endl;
855  }
856  // We can recover from this error:
857  // Treat this edge as fully visible with no occludee
858  (*ve)->setQI(0);
859  (*ve)->setaShape(nullptr);
860  continue;
861  }
862 
863  ++qiMajority;
864  qiMajority >>= 1;
865 
866  even_test = true;
867  maxIndex = 0;
868  maxCard = 0;
869  nSamples = 0;
870  memset(qiClasses, 0, 256 * sizeof(*qiClasses));
871  set<ViewShape *> foundOccluders;
872 
873  fe = (*ve)->fedgeA();
874  do {
875  if (!fe || !fe->isInImage()) {
876  fe = fe->nextEdge();
877  continue;
878  }
879  if (even_test) {
880  if (maxCard < qiMajority) {
881  // ARB: change &wFace to wFace and use reference in called function
882  tmpQI = computeVisibility<G, I>(
883  ioViewMap, fe, grid, epsilon, *ve, &wFace, &foundOccluders);
884 
885  // ARB: This is an error condition, not an alert condition.
886  // Some sort of recovery or abort is necessary.
887  if (tmpQI >= 256) {
888  cerr << "Warning: too many occluding levels" << endl;
889  // ARB: Wild guess: instead of aborting or corrupting memory, treat as tmpQI == 255
890  tmpQI = 255;
891  }
892 
893  if (++qiClasses[tmpQI] > maxCard) {
894  maxCard = qiClasses[tmpQI];
895  maxIndex = tmpQI;
896  }
897  }
898  else {
899  // ARB: FindOccludee is redundant if ComputeRayCastingVisibility has been called
900  // ARB: change &wFace to wFace and use reference in called function
901  findOccludee<G, I>(fe, grid, epsilon, *ve, &wFace);
902  }
903 
904  if (wFace) {
905  vector<Vec3r> vertices;
906  for (int i = 0, numEdges = wFace->numberOfEdges(); i < numEdges; ++i) {
907  vertices.emplace_back(wFace->GetVertex(i)->GetVertex());
908  }
909  Polygon3r poly(vertices, wFace->GetNormal());
910  poly.userdata = (void *)wFace;
911  fe->setaFace(poly);
912  wFaces.push_back(wFace);
913  }
914  ++nSamples;
915  }
916 
917  even_test = !even_test;
918  fe = fe->nextEdge();
919  } while ((maxCard < qiMajority) && (fe) && (fe != festart));
920 
921  // qi --
922  (*ve)->setQI(maxIndex);
923 
924  // occluders --
925  for (set<ViewShape *>::iterator o = foundOccluders.begin(), oend = foundOccluders.end();
926  o != oend;
927  ++o) {
928  (*ve)->AddOccluder((*o));
929  }
930 
931  // occludee --
932  if (!wFaces.empty()) {
933  if (wFaces.size() < nSamples / 2) {
934  (*ve)->setaShape(nullptr);
935  }
936  else {
937  ViewShape *vshape = ioViewMap->viewShape(
938  (*wFaces.begin())->GetVertex(0)->shape()->GetId());
939  (*ve)->setaShape(vshape);
940  }
941  }
942 
943  wFaces.clear();
944  }
945 }
946 
947 template<typename G, typename I>
948 static void computeVeryFastVisibility(ViewMap *ioViewMap, G &grid, real epsilon)
949 {
950  vector<ViewEdge *> &vedges = ioViewMap->ViewEdges();
951 
952  FEdge *fe;
953  unsigned qi = 0;
954  WFace *wFace = nullptr;
955 
956  for (vector<ViewEdge *>::iterator ve = vedges.begin(), veend = vedges.end(); ve != veend; ve++) {
957  // Find an edge to test
958  if (!(*ve)->isInImage()) {
959  // This view edge has been proscenium culled
960  (*ve)->setQI(255);
961  (*ve)->setaShape(nullptr);
962  continue;
963  }
964  fe = (*ve)->fedgeA();
965  // Find a FEdge inside the occluder proscenium to test for visibility
966  FEdge *festart = fe;
967  while (fe && !fe->isInImage() && fe != festart) {
968  fe = fe->nextEdge();
969  }
970 
971  // Test edge
972  if (!fe || !fe->isInImage()) {
973  // There are no occludable FEdges on this ViewEdge
974  // This should be impossible.
976  cout << "View Edge in viewport without occludable FEdges: " << (*ve)->getId() << endl;
977  }
978  // We can recover from this error:
979  // Treat this edge as fully visible with no occludee
980  qi = 0;
981  wFace = nullptr;
982  }
983  else {
984  qi = computeVisibility<G, I>(ioViewMap, fe, grid, epsilon, *ve, &wFace, NULL);
985  }
986 
987  // Store test results
988  if (wFace) {
989  vector<Vec3r> vertices;
990  for (int i = 0, numEdges = wFace->numberOfEdges(); i < numEdges; ++i) {
991  vertices.emplace_back(wFace->GetVertex(i)->GetVertex());
992  }
993  Polygon3r poly(vertices, wFace->GetNormal());
994  poly.userdata = (void *)wFace;
995  fe->setaFace(poly); // This works because setaFace *copies* the polygon
996  ViewShape *vshape = ioViewMap->viewShape(wFace->GetVertex(0)->shape()->GetId());
997  (*ve)->setaShape(vshape);
998  }
999  else {
1000  (*ve)->setaShape(nullptr);
1001  }
1002  (*ve)->setQI(qi);
1003  }
1004 }
1005 
1006 void ViewMapBuilder::BuildGrid(WingedEdge &we, const BBox<Vec3r> &bbox, unsigned int sceneNumFaces)
1007 {
1008  _Grid->clear();
1009  Vec3r size;
1010  for (unsigned int i = 0; i < 3; i++) {
1011  size[i] = fabs(bbox.getMax()[i] - bbox.getMin()[i]);
1012  // let make the grid 1/10 bigger to avoid numerical errors while computing triangles/cells
1013  // intersections.
1014  size[i] += size[i] / 10.0;
1015  if (size[i] == 0) {
1017  cout << "Warning: the bbox size is 0 in dimension " << i << endl;
1018  }
1019  }
1020  }
1021  _Grid->configure(Vec3r(bbox.getMin() - size / 20.0), size, sceneNumFaces);
1022 
1023  // Fill in the grid:
1024  WFillGrid fillGridRenderer(_Grid, &we);
1025  fillGridRenderer.fillGrid();
1026 
1027  // DEBUG
1028  _Grid->displayDebug();
1029 }
1030 
1032  visibility_algo iAlgo,
1033  real epsilon,
1034  const BBox<Vec3r> &bbox,
1035  unsigned int sceneNumFaces)
1036 {
1037  _ViewMap = new ViewMap;
1038  _currentId = 1;
1039  _currentFId = 0;
1040  _currentSVertexId = 0;
1041 
1042  // Builds initial view edges
1043  computeInitialViewEdges(we);
1044 
1045  // Detects cusps
1046  computeCusps(_ViewMap);
1047 
1048  // Compute intersections
1049  ComputeIntersections(_ViewMap, sweep_line, epsilon);
1050 
1051  // Compute visibility
1052  ComputeEdgesVisibility(_ViewMap, we, bbox, sceneNumFaces, iAlgo, epsilon);
1053 
1054  return _ViewMap;
1055 }
1056 
1057 static inline real distance2D(const Vec3r &point, const real origin[2])
1058 {
1059  return ::hypot((point[0] - origin[0]), (point[1] - origin[1]));
1060 }
1061 
1062 static inline bool crossesProscenium(real proscenium[4], FEdge *fe)
1063 {
1064  Vec2r min(proscenium[0], proscenium[2]);
1065  Vec2r max(proscenium[1], proscenium[3]);
1066  Vec2r A(fe->vertexA()->getProjectedX(), fe->vertexA()->getProjectedY());
1067  Vec2r B(fe->vertexB()->getProjectedX(), fe->vertexB()->getProjectedY());
1068 
1070 }
1071 
1072 static inline bool insideProscenium(const real proscenium[4], const Vec3r &point)
1073 {
1074  return !(point[0] < proscenium[0] || point[0] > proscenium[1] || point[1] < proscenium[2] ||
1075  point[1] > proscenium[3]);
1076 }
1077 
1079  real viewProscenium[4],
1080  real occluderProscenium[4],
1081  bool extensiveFEdgeSearch)
1082 {
1083  // Cull view edges by marking them as non-displayable.
1084  // This avoids the complications of trying to delete edges from the ViewMap.
1085 
1086  // Non-displayable view edges will be skipped over during visibility calculation.
1087 
1088  // View edges will be culled according to their position w.r.t. the viewport proscenium (viewport
1089  // + 5% border, or some such).
1090 
1091  // Get proscenium boundary for culling
1092  GridHelpers::getDefaultViewProscenium(viewProscenium);
1093  real prosceniumOrigin[2];
1094  prosceniumOrigin[0] = (viewProscenium[1] - viewProscenium[0]) / 2.0;
1095  prosceniumOrigin[1] = (viewProscenium[3] - viewProscenium[2]) / 2.0;
1097  cout << "Proscenium culling:" << endl;
1098  cout << "Proscenium: [" << viewProscenium[0] << ", " << viewProscenium[1] << ", "
1099  << viewProscenium[2] << ", " << viewProscenium[3] << "]" << endl;
1100  cout << "Origin: [" << prosceniumOrigin[0] << ", " << prosceniumOrigin[1] << "]" << endl;
1101  }
1102 
1103  // A separate occluder proscenium will also be maintained, starting out the same as the viewport
1104  // proscenium, and expanding as necessary so that it encompasses the center point of at least one
1105  // feature edge in each retained view edge. The occluder proscenium will be used later to cull
1106  // occluding triangles before they are inserted into the Grid. The occluder proscenium starts out
1107  // the same size as the view proscenium
1108  GridHelpers::getDefaultViewProscenium(occluderProscenium);
1109 
1110  // N.B. Freestyle is inconsistent in its use of ViewMap::viewedges_container and
1111  // vector<ViewEdge*>::iterator. Probably all occurrences of vector<ViewEdge*>::iterator should be
1112  // replaced ViewMap::viewedges_container throughout the code. For each view edge
1113  ViewMap::viewedges_container::iterator ve, veend;
1114 
1115  for (ve = ioViewMap->ViewEdges().begin(), veend = ioViewMap->ViewEdges().end(); ve != veend;
1116  ve++) {
1117  // Overview:
1118  // Search for a visible feature edge
1119  // If none: mark view edge as non-displayable
1120  // Otherwise:
1121  // Find a feature edge with center point inside occluder proscenium.
1122  // If none exists, find the feature edge with center point closest to viewport origin.
1123  // Expand occluder proscenium to enclose center point.
1124 
1125  // For each feature edge, while bestOccluderTarget not found and view edge not visible
1126  bool bestOccluderTargetFound = false;
1127  FEdge *bestOccluderTarget = nullptr;
1128  real bestOccluderDistance = 0.0;
1129  FEdge *festart = (*ve)->fedgeA();
1130  FEdge *fe = festart;
1131  // All ViewEdges start culled
1132  (*ve)->setIsInImage(false);
1133 
1134  // For simple visibility calculation: mark a feature edge that is known to have a center point
1135  // inside the occluder proscenium. Cull all other feature edges.
1136  do {
1137  // All FEdges start culled
1138  fe->setIsInImage(false);
1139 
1140  // Look for the visible edge that can most easily be included in the occluder proscenium.
1141  if (!bestOccluderTargetFound) {
1142  // If center point is inside occluder proscenium,
1143  if (insideProscenium(occluderProscenium, fe->center2d())) {
1144  // Use this feature edge for visibility deterimination
1145  fe->setIsInImage(true);
1146  // Mark bestOccluderTarget as found
1147  bestOccluderTargetFound = true;
1148  bestOccluderTarget = fe;
1149  }
1150  else {
1151  real d = distance2D(fe->center2d(), prosceniumOrigin);
1152  // If center point is closer to viewport origin than current target
1153  if (bestOccluderTarget == nullptr || d < bestOccluderDistance) {
1154  // Then store as bestOccluderTarget
1155  bestOccluderDistance = d;
1156  bestOccluderTarget = fe;
1157  }
1158  }
1159  }
1160 
1161  // If feature edge crosses the view proscenium
1162  if (!(*ve)->isInImage() && crossesProscenium(viewProscenium, fe)) {
1163  // Then the view edge will be included in the image
1164  (*ve)->setIsInImage(true);
1165  }
1166  fe = fe->nextEdge();
1167  } while (fe && fe != festart && !(bestOccluderTargetFound && (*ve)->isInImage()));
1168 
1169  // Either we have run out of FEdges, or we already have the one edge we need to determine
1170  // visibility Cull all remaining edges.
1171  while (fe && fe != festart) {
1172  fe->setIsInImage(false);
1173  fe = fe->nextEdge();
1174  }
1175 
1176  // If bestOccluderTarget was not found inside the occluder proscenium, we need to expand the
1177  // occluder proscenium to include it.
1178  if ((*ve)->isInImage() && bestOccluderTarget != nullptr && !bestOccluderTargetFound) {
1179  // Expand occluder proscenium to enclose bestOccluderTarget
1180  Vec3r point = bestOccluderTarget->center2d();
1181  if (point[0] < occluderProscenium[0]) {
1182  occluderProscenium[0] = point[0];
1183  }
1184  else if (point[0] > occluderProscenium[1]) {
1185  occluderProscenium[1] = point[0];
1186  }
1187  if (point[1] < occluderProscenium[2]) {
1188  occluderProscenium[2] = point[1];
1189  }
1190  else if (point[1] > occluderProscenium[3]) {
1191  occluderProscenium[3] = point[1];
1192  }
1193  // Use bestOccluderTarget for visibility determination
1194  bestOccluderTarget->setIsInImage(true);
1195  }
1196  }
1197 
1198  // We are done calculating the occluder proscenium.
1199  // Expand the occluder proscenium by an epsilon to avoid rounding errors.
1200  const real epsilon = 1.0e-6;
1201  occluderProscenium[0] -= epsilon;
1202  occluderProscenium[1] += epsilon;
1203  occluderProscenium[2] -= epsilon;
1204  occluderProscenium[3] += epsilon;
1205 
1206  // For "Normal" or "Fast" style visibility computation only:
1207 
1208  // For more detailed visibility calculation, make a second pass through the view map, marking all
1209  // feature edges with center points inside the final occluder proscenium. All of these feature
1210  // edges can be considered during visibility calculation.
1211 
1212  // So far we have only found one FEdge per ViewEdge. The "Normal" and "Fast" styles of
1213  // visibility computation want to consider many FEdges for each ViewEdge. Here we re-scan the
1214  // view map to find any usable FEdges that we skipped on the first pass, or that have become
1215  // usable because the occluder proscenium has been expanded since the edge was visited on the
1216  // first pass.
1217  if (extensiveFEdgeSearch) {
1218  // For each view edge,
1219  for (ve = ioViewMap->ViewEdges().begin(), veend = ioViewMap->ViewEdges().end(); ve != veend;
1220  ve++) {
1221  if (!(*ve)->isInImage()) {
1222  continue;
1223  }
1224  // For each feature edge,
1225  FEdge *festart = (*ve)->fedgeA();
1226  FEdge *fe = festart;
1227  do {
1228  // If not (already) visible and center point inside occluder proscenium,
1229  if (!fe->isInImage() && insideProscenium(occluderProscenium, fe->center2d())) {
1230  // Use the feature edge for visibility determination
1231  fe->setIsInImage(true);
1232  }
1233  fe = fe->nextEdge();
1234  } while (fe && fe != festart);
1235  }
1236  }
1237 }
1238 
1240 {
1241  vector<WShape *> wshapes = we.getWShapes();
1242  SShape *psShape;
1243 
1244  for (vector<WShape *>::const_iterator it = wshapes.begin(); it != wshapes.end(); it++) {
1245  if (_pRenderMonitor && _pRenderMonitor->testBreak()) {
1246  break;
1247  }
1248 
1249  // create the embedding
1250  psShape = new SShape;
1251  psShape->setId((*it)->GetId());
1252  psShape->setName((*it)->getName());
1253  psShape->setLibraryPath((*it)->getLibraryPath());
1254  psShape->setFrsMaterials((*it)->frs_materials()); // FIXME
1255 
1256  // create the view shape
1257  ViewShape *vshape = new ViewShape(psShape);
1258  // add this view shape to the view map:
1259  _ViewMap->AddViewShape(vshape);
1260 
1261  // we want to number the view edges in a unique way for the while scene.
1262  _pViewEdgeBuilder->setCurrentViewId(_currentId);
1263  // we want to number the feature edges in a unique way for the while scene.
1264  _pViewEdgeBuilder->setCurrentFId(_currentFId);
1265  // we want to number the SVertex in a unique way for the while scene.
1266  _pViewEdgeBuilder->setCurrentSVertexId(_currentFId);
1267  _pViewEdgeBuilder->BuildViewEdges(dynamic_cast<WXShape *>(*it),
1268  vshape,
1269  _ViewMap->ViewEdges(),
1270  _ViewMap->ViewVertices(),
1271  _ViewMap->FEdges(),
1272  _ViewMap->SVertices());
1273 
1274  _currentId = _pViewEdgeBuilder->currentViewId() + 1;
1275  _currentFId = _pViewEdgeBuilder->currentFId() + 1;
1276  _currentSVertexId = _pViewEdgeBuilder->currentSVertexId() + 1;
1277 
1278  psShape->ComputeBBox();
1279  }
1280 }
1281 
1283 {
1284  vector<ViewVertex *> newVVertices;
1285  vector<ViewEdge *> newVEdges;
1286  ViewMap::viewedges_container &vedges = ioViewMap->ViewEdges();
1287  ViewMap::viewedges_container::iterator ve = vedges.begin(), veend = vedges.end();
1288  for (; ve != veend; ++ve) {
1289  if (_pRenderMonitor && _pRenderMonitor->testBreak()) {
1290  break;
1291  }
1292  if ((!((*ve)->getNature() & Nature::SILHOUETTE)) || (!((*ve)->fedgeA()->isSmooth()))) {
1293  continue;
1294  }
1295  FEdge *fe = (*ve)->fedgeA();
1296  FEdge *fefirst = fe;
1297  bool first = true;
1298  bool positive = true;
1299  do {
1300  FEdgeSmooth *fes = dynamic_cast<FEdgeSmooth *>(fe);
1301  Vec3r A((fes)->vertexA()->point3d());
1302  Vec3r B((fes)->vertexB()->point3d());
1303  Vec3r AB(B - A);
1304  AB.normalize();
1305  Vec3r m((A + B) / 2.0);
1306  Vec3r crossP(AB ^ (fes)->normal());
1307  crossP.normalize();
1308  Vec3r viewvector;
1309  if (_orthographicProjection) {
1310  viewvector = Vec3r(0.0, 0.0, m.z() - _viewpoint.z());
1311  }
1312  else {
1313  viewvector = Vec3r(m - _viewpoint);
1314  }
1315  viewvector.normalize();
1316  if (first) {
1317  if (((crossP) * (viewvector)) > 0) {
1318  positive = true;
1319  }
1320  else {
1321  positive = false;
1322  }
1323  first = false;
1324  }
1325  // If we're in a positive part, we need a stronger negative value to change
1326  NonTVertex *cusp = nullptr;
1327  if (positive) {
1328  if (((crossP) * (viewvector)) < -0.1) {
1329  // state changes
1330  positive = false;
1331  // creates and insert cusp
1332  cusp = dynamic_cast<NonTVertex *>(
1333  ioViewMap->InsertViewVertex(fes->vertexA(), newVEdges));
1334  if (cusp) {
1335  cusp->setNature(cusp->getNature() | Nature::CUSP);
1336  }
1337  }
1338  }
1339  else {
1340  // If we're in a negative part, we need a stronger negative value to change
1341  if (((crossP) * (viewvector)) > 0.1) {
1342  positive = true;
1343  cusp = dynamic_cast<NonTVertex *>(
1344  ioViewMap->InsertViewVertex(fes->vertexA(), newVEdges));
1345  if (cusp) {
1346  cusp->setNature(cusp->getNature() | Nature::CUSP);
1347  }
1348  }
1349  }
1350  fe = fe->nextEdge();
1351  } while (fe && fe != fefirst);
1352  }
1353  for (ve = newVEdges.begin(), veend = newVEdges.end(); ve != veend; ++ve) {
1354  (*ve)->viewShape()->AddEdge(*ve);
1355  vedges.push_back(*ve);
1356  }
1357 }
1358 
1360  WingedEdge &we,
1361  const BBox<Vec3r> &bbox,
1362  real epsilon,
1363  bool cull,
1364  GridDensityProviderFactory &factory)
1365 {
1367  AutoPtr<OccluderSource> source;
1368 
1369  if (_orthographicProjection) {
1370  transform = std::make_unique<BoxGrid::Transform>();
1371  }
1372  else {
1373  transform = std::make_unique<SphericalGrid::Transform>();
1374  }
1375 
1376  if (cull) {
1377  source = std::make_unique<CulledOccluderSource>(*transform, we, *ioViewMap, true);
1378  }
1379  else {
1380  source = std::make_unique<OccluderSource>(*transform, we);
1381  }
1382 
1384 
1385  if (_orthographicProjection) {
1386  BoxGrid grid(*source, *density, ioViewMap, _viewpoint, _EnableQI);
1387  computeCumulativeVisibility<BoxGrid, BoxGrid::Iterator>(
1388  ioViewMap, grid, epsilon, _pRenderMonitor);
1389  }
1390  else {
1391  SphericalGrid grid(*source, *density, ioViewMap, _viewpoint, _EnableQI);
1392  computeCumulativeVisibility<SphericalGrid, SphericalGrid::Iterator>(
1393  ioViewMap, grid, epsilon, _pRenderMonitor);
1394  }
1395 }
1396 
1398  WingedEdge &we,
1399  const BBox<Vec3r> &bbox,
1400  real epsilon,
1401  bool cull,
1402  GridDensityProviderFactory &factory)
1403 {
1405  AutoPtr<OccluderSource> source;
1406 
1407  if (_orthographicProjection) {
1408  transform = std::make_unique<BoxGrid::Transform>();
1409  }
1410  else {
1411  transform = std::make_unique<SphericalGrid::Transform>();
1412  }
1413 
1414  if (cull) {
1415  source = std::make_unique<CulledOccluderSource>(*transform, we, *ioViewMap, true);
1416  }
1417  else {
1418  source = std::make_unique<OccluderSource>(*transform, we);
1419  }
1420 
1422 
1423  if (_orthographicProjection) {
1424  BoxGrid grid(*source, *density, ioViewMap, _viewpoint, _EnableQI);
1425  computeDetailedVisibility<BoxGrid, BoxGrid::Iterator>(
1426  ioViewMap, grid, epsilon, _pRenderMonitor);
1427  }
1428  else {
1429  SphericalGrid grid(*source, *density, ioViewMap, _viewpoint, _EnableQI);
1430  computeDetailedVisibility<SphericalGrid, SphericalGrid::Iterator>(
1431  ioViewMap, grid, epsilon, _pRenderMonitor);
1432  }
1433 }
1434 
1436  WingedEdge &we,
1437  const BBox<Vec3r> &bbox,
1438  unsigned int sceneNumFaces,
1439  visibility_algo iAlgo,
1440  real epsilon)
1441 {
1442 #if 0
1443  iAlgo = ray_casting; // for testing algorithms equivalence
1444 #endif
1445  switch (iAlgo) {
1446  case ray_casting:
1448  cout << "Using ordinary ray casting" << endl;
1449  }
1450  BuildGrid(we, bbox, sceneNumFaces);
1451  ComputeRayCastingVisibility(ioViewMap, epsilon);
1452  break;
1453  case ray_casting_fast:
1455  cout << "Using fast ray casting" << endl;
1456  }
1457  BuildGrid(we, bbox, sceneNumFaces);
1458  ComputeFastRayCastingVisibility(ioViewMap, epsilon);
1459  break;
1460  case ray_casting_very_fast:
1462  cout << "Using very fast ray casting" << endl;
1463  }
1464  BuildGrid(we, bbox, sceneNumFaces);
1465  ComputeVeryFastRayCastingVisibility(ioViewMap, epsilon);
1466  break;
1467  case ray_casting_culled_adaptive_traditional:
1469  cout << "Using culled adaptive grid with heuristic density and traditional QI calculation"
1470  << endl;
1471  }
1472  try {
1473  HeuristicGridDensityProviderFactory factory(0.5f, sceneNumFaces);
1474  ComputeDetailedVisibility(ioViewMap, we, bbox, epsilon, true, factory);
1475  }
1476  catch (...) {
1477  // Last resort catch to make sure RAII semantics hold for OptimizedGrid. Can be replaced
1478  // with try...catch block around main() if the program as a whole is converted to RAII
1479 
1480  // This is the little-mentioned caveat of RAII: RAII does not work unless destructors are
1481  // always called, but destructors are only called if all exceptions are caught (or
1482  // std::terminate() is replaced).
1483 
1484  // We don't actually handle the exception here, so re-throw it now that our destructors
1485  // have had a chance to run.
1486  throw;
1487  }
1488  break;
1489  case ray_casting_adaptive_traditional:
1491  cout
1492  << "Using unculled adaptive grid with heuristic density and traditional QI calculation"
1493  << endl;
1494  }
1495  try {
1496  HeuristicGridDensityProviderFactory factory(0.5f, sceneNumFaces);
1497  ComputeDetailedVisibility(ioViewMap, we, bbox, epsilon, false, factory);
1498  }
1499  catch (...) {
1500  throw;
1501  }
1502  break;
1503  case ray_casting_culled_adaptive_cumulative:
1505  cout << "Using culled adaptive grid with heuristic density and cumulative QI calculation"
1506  << endl;
1507  }
1508  try {
1509  HeuristicGridDensityProviderFactory factory(0.5f, sceneNumFaces);
1510  ComputeCumulativeVisibility(ioViewMap, we, bbox, epsilon, true, factory);
1511  }
1512  catch (...) {
1513  throw;
1514  }
1515  break;
1516  case ray_casting_adaptive_cumulative:
1518  cout << "Using unculled adaptive grid with heuristic density and cumulative QI calculation"
1519  << endl;
1520  }
1521  try {
1522  HeuristicGridDensityProviderFactory factory(0.5f, sceneNumFaces);
1523  ComputeCumulativeVisibility(ioViewMap, we, bbox, epsilon, false, factory);
1524  }
1525  catch (...) {
1526  throw;
1527  }
1528  break;
1529  default:
1530  break;
1531  }
1532 }
1533 
1534 static const unsigned gProgressBarMaxSteps = 10;
1535 static const unsigned gProgressBarMinSize = 2000;
1536 
1538 {
1539  vector<ViewEdge *> &vedges = ioViewMap->ViewEdges();
1540  bool progressBarDisplay = false;
1541  unsigned progressBarStep = 0;
1542  unsigned vEdgesSize = vedges.size();
1543  unsigned fEdgesSize = ioViewMap->FEdges().size();
1544 
1545  if (_pProgressBar != nullptr && fEdgesSize > gProgressBarMinSize) {
1546  unsigned progressBarSteps = min(gProgressBarMaxSteps, vEdgesSize);
1547  progressBarStep = vEdgesSize / progressBarSteps;
1548  _pProgressBar->reset();
1549  _pProgressBar->setLabelText("Computing Ray casting Visibility");
1550  _pProgressBar->setTotalSteps(progressBarSteps);
1551  _pProgressBar->setProgress(0);
1552  progressBarDisplay = true;
1553  }
1554 
1555  unsigned counter = progressBarStep;
1556  FEdge *fe, *festart;
1557  int nSamples = 0;
1558  vector<Polygon3r *> aFaces;
1559  Polygon3r *aFace = nullptr;
1560  unsigned tmpQI = 0;
1561  unsigned qiClasses[256];
1562  unsigned maxIndex, maxCard;
1563  unsigned qiMajority;
1564  static unsigned timestamp = 1;
1565  for (vector<ViewEdge *>::iterator ve = vedges.begin(), veend = vedges.end(); ve != veend; ve++) {
1566  if (_pRenderMonitor && _pRenderMonitor->testBreak()) {
1567  break;
1568  }
1569 #if LOGGING
1571  cout << "Processing ViewEdge " << (*ve)->getId() << endl;
1572  }
1573 #endif
1574  festart = (*ve)->fedgeA();
1575  fe = (*ve)->fedgeA();
1576  qiMajority = 1;
1577  do {
1578  qiMajority++;
1579  fe = fe->nextEdge();
1580  } while (fe && fe != festart);
1581  qiMajority >>= 1;
1582 #if LOGGING
1584  cout << "\tqiMajority: " << qiMajority << endl;
1585  }
1586 #endif
1587 
1588  tmpQI = 0;
1589  maxIndex = 0;
1590  maxCard = 0;
1591  nSamples = 0;
1592  fe = (*ve)->fedgeA();
1593  memset(qiClasses, 0, 256 * sizeof(*qiClasses));
1594  set<ViewShape *> occluders;
1595  do {
1596  if (maxCard < qiMajority) {
1597  tmpQI = ComputeRayCastingVisibility(fe, _Grid, epsilon, occluders, &aFace, timestamp++);
1598 
1599 #if LOGGING
1601  cout << "\tFEdge: visibility " << tmpQI << endl;
1602  }
1603 #endif
1604  // ARB: This is an error condition, not an alert condition.
1605  // Some sort of recovery or abort is necessary.
1606  if (tmpQI >= 256) {
1607  cerr << "Warning: too many occluding levels" << endl;
1608  // ARB: Wild guess: instead of aborting or corrupting memory, treat as tmpQI == 255
1609  tmpQI = 255;
1610  }
1611 
1612  if (++qiClasses[tmpQI] > maxCard) {
1613  maxCard = qiClasses[tmpQI];
1614  maxIndex = tmpQI;
1615  }
1616  }
1617  else {
1618  // ARB: FindOccludee is redundant if ComputeRayCastingVisibility has been called
1619  FindOccludee(fe, _Grid, epsilon, &aFace, timestamp++);
1620 #if LOGGING
1622  cout << "\tFEdge: occludee only (" << (aFace != NULL ? "found" : "not found") << ")"
1623  << endl;
1624  }
1625 #endif
1626  }
1627 
1628  if (aFace) {
1629  fe->setaFace(*aFace);
1630  aFaces.push_back(aFace);
1631  fe->setOccludeeEmpty(false);
1632 #if LOGGING
1634  cout << "\tFound occludee" << endl;
1635  }
1636 #endif
1637  }
1638  else {
1639  // ARB: We are arbitrarily using the last observed value for occludee (almost always the
1640  // value observed
1641  // for the edge before festart). Is that meaningful?
1642  // ...in fact, _occludeeEmpty seems to be unused.
1643  fe->setOccludeeEmpty(true);
1644  }
1645 
1646  ++nSamples;
1647  fe = fe->nextEdge();
1648  } while ((maxCard < qiMajority) && (fe) && (fe != festart));
1649 #if LOGGING
1651  cout << "\tFinished with " << nSamples << " samples, maxCard = " << maxCard << endl;
1652  }
1653 #endif
1654 
1655  // ViewEdge
1656  // qi --
1657  (*ve)->setQI(maxIndex);
1658  // occluders --
1659  for (set<ViewShape *>::iterator o = occluders.begin(), oend = occluders.end(); o != oend;
1660  ++o) {
1661  (*ve)->AddOccluder((*o));
1662  }
1663 #if LOGGING
1665  cout << "\tConclusion: QI = " << maxIndex << ", " << (*ve)->occluders_size() << " occluders."
1666  << endl;
1667  }
1668 #endif
1669  // occludee --
1670  if (!aFaces.empty()) {
1671  if (aFaces.size() <= (float)nSamples / 2.0f) {
1672  (*ve)->setaShape(nullptr);
1673  }
1674  else {
1675  vector<Polygon3r *>::iterator p = aFaces.begin();
1676  WFace *wface = (WFace *)((*p)->userdata);
1677  ViewShape *vshape = ioViewMap->viewShape(wface->GetVertex(0)->shape()->GetId());
1678  ++p;
1679  (*ve)->setaShape(vshape);
1680  }
1681  }
1682 
1683  if (progressBarDisplay) {
1684  counter--;
1685  if (counter <= 0) {
1686  counter = progressBarStep;
1687  _pProgressBar->setProgress(_pProgressBar->getProgress() + 1);
1688  }
1689  }
1690  aFaces.clear();
1691  }
1692 }
1693 
1695 {
1696  vector<ViewEdge *> &vedges = ioViewMap->ViewEdges();
1697  bool progressBarDisplay = false;
1698  unsigned progressBarStep = 0;
1699  unsigned vEdgesSize = vedges.size();
1700  unsigned fEdgesSize = ioViewMap->FEdges().size();
1701 
1702  if (_pProgressBar != nullptr && fEdgesSize > gProgressBarMinSize) {
1703  unsigned progressBarSteps = min(gProgressBarMaxSteps, vEdgesSize);
1704  progressBarStep = vEdgesSize / progressBarSteps;
1705  _pProgressBar->reset();
1706  _pProgressBar->setLabelText("Computing Ray casting Visibility");
1707  _pProgressBar->setTotalSteps(progressBarSteps);
1708  _pProgressBar->setProgress(0);
1709  progressBarDisplay = true;
1710  }
1711 
1712  unsigned counter = progressBarStep;
1713  FEdge *fe, *festart;
1714  unsigned nSamples = 0;
1715  vector<Polygon3r *> aFaces;
1716  Polygon3r *aFace = nullptr;
1717  unsigned tmpQI = 0;
1718  unsigned qiClasses[256];
1719  unsigned maxIndex, maxCard;
1720  unsigned qiMajority;
1721  static unsigned timestamp = 1;
1722  bool even_test;
1723  for (vector<ViewEdge *>::iterator ve = vedges.begin(), veend = vedges.end(); ve != veend; ve++) {
1724  if (_pRenderMonitor && _pRenderMonitor->testBreak()) {
1725  break;
1726  }
1727 
1728  festart = (*ve)->fedgeA();
1729  fe = (*ve)->fedgeA();
1730  qiMajority = 1;
1731  do {
1732  qiMajority++;
1733  fe = fe->nextEdge();
1734  } while (fe && fe != festart);
1735  if (qiMajority >= 4) {
1736  qiMajority >>= 2;
1737  }
1738  else {
1739  qiMajority = 1;
1740  }
1741 
1742  set<ViewShape *> occluders;
1743 
1744  even_test = true;
1745  maxIndex = 0;
1746  maxCard = 0;
1747  nSamples = 0;
1748  memset(qiClasses, 0, 256 * sizeof(*qiClasses));
1749  fe = (*ve)->fedgeA();
1750  do {
1751  if (even_test) {
1752  if (maxCard < qiMajority) {
1753  tmpQI = ComputeRayCastingVisibility(fe, _Grid, epsilon, occluders, &aFace, timestamp++);
1754 
1755  // ARB: This is an error condition, not an alert condition.
1756  // Some sort of recovery or abort is necessary.
1757  if (tmpQI >= 256) {
1758  cerr << "Warning: too many occluding levels" << endl;
1759  // ARB: Wild guess: instead of aborting or corrupting memory, treat as tmpQI == 255
1760  tmpQI = 255;
1761  }
1762 
1763  if (++qiClasses[tmpQI] > maxCard) {
1764  maxCard = qiClasses[tmpQI];
1765  maxIndex = tmpQI;
1766  }
1767  }
1768  else {
1769  // ARB: FindOccludee is redundant if ComputeRayCastingVisibility has been called
1770  FindOccludee(fe, _Grid, epsilon, &aFace, timestamp++);
1771  }
1772 
1773  if (aFace) {
1774  fe->setaFace(*aFace);
1775  aFaces.push_back(aFace);
1776  }
1777  ++nSamples;
1778  even_test = false;
1779  }
1780  else {
1781  even_test = true;
1782  }
1783  fe = fe->nextEdge();
1784  } while ((maxCard < qiMajority) && (fe) && (fe != festart));
1785 
1786  (*ve)->setQI(maxIndex);
1787 
1788  if (!aFaces.empty()) {
1789  if (aFaces.size() < nSamples / 2) {
1790  (*ve)->setaShape(nullptr);
1791  }
1792  else {
1793  vector<Polygon3r *>::iterator p = aFaces.begin();
1794  WFace *wface = (WFace *)((*p)->userdata);
1795  ViewShape *vshape = ioViewMap->viewShape(wface->GetVertex(0)->shape()->GetId());
1796  ++p;
1797 #if 0
1798  for (; p != pend; ++p) {
1799  WFace *f = (WFace *)((*p)->userdata);
1800  ViewShape *vs = ioViewMap->viewShape(f->GetVertex(0)->shape()->GetId());
1801  if (vs != vshape) {
1802  sameShape = false;
1803  break;
1804  }
1805  }
1806  if (sameShape)
1807 #endif
1808  {
1809  (*ve)->setaShape(vshape);
1810  }
1811  }
1812  }
1813 
1814  //(*ve)->setaFace(aFace);
1815 
1816  if (progressBarDisplay) {
1817  counter--;
1818  if (counter <= 0) {
1819  counter = progressBarStep;
1820  _pProgressBar->setProgress(_pProgressBar->getProgress() + 1);
1821  }
1822  }
1823  aFaces.clear();
1824  }
1825 }
1826 
1828 {
1829  vector<ViewEdge *> &vedges = ioViewMap->ViewEdges();
1830  bool progressBarDisplay = false;
1831  unsigned progressBarStep = 0;
1832  unsigned vEdgesSize = vedges.size();
1833  unsigned fEdgesSize = ioViewMap->FEdges().size();
1834 
1835  if (_pProgressBar != nullptr && fEdgesSize > gProgressBarMinSize) {
1836  unsigned progressBarSteps = min(gProgressBarMaxSteps, vEdgesSize);
1837  progressBarStep = vEdgesSize / progressBarSteps;
1838  _pProgressBar->reset();
1839  _pProgressBar->setLabelText("Computing Ray casting Visibility");
1840  _pProgressBar->setTotalSteps(progressBarSteps);
1841  _pProgressBar->setProgress(0);
1842  progressBarDisplay = true;
1843  }
1844 
1845  unsigned counter = progressBarStep;
1846  FEdge *fe;
1847  unsigned qi = 0;
1848  Polygon3r *aFace = nullptr;
1849  static unsigned timestamp = 1;
1850  for (vector<ViewEdge *>::iterator ve = vedges.begin(), veend = vedges.end(); ve != veend; ve++) {
1851  if (_pRenderMonitor && _pRenderMonitor->testBreak()) {
1852  break;
1853  }
1854 
1855  set<ViewShape *> occluders;
1856 
1857  fe = (*ve)->fedgeA();
1858  qi = ComputeRayCastingVisibility(fe, _Grid, epsilon, occluders, &aFace, timestamp++);
1859  if (aFace) {
1860  fe->setaFace(*aFace);
1861  WFace *wface = (WFace *)(aFace->userdata);
1862  ViewShape *vshape = ioViewMap->viewShape(wface->GetVertex(0)->shape()->GetId());
1863  (*ve)->setaShape(vshape);
1864  }
1865  else {
1866  (*ve)->setaShape(nullptr);
1867  }
1868 
1869  (*ve)->setQI(qi);
1870 
1871  if (progressBarDisplay) {
1872  counter--;
1873  if (counter <= 0) {
1874  counter = progressBarStep;
1875  _pProgressBar->setProgress(_pProgressBar->getProgress() + 1);
1876  }
1877  }
1878  }
1879 }
1880 
1882  Grid *iGrid,
1883  real epsilon,
1884  Polygon3r **oaPolygon,
1885  unsigned timestamp,
1886  Vec3r &u,
1887  Vec3r &A,
1888  Vec3r &origin,
1889  Vec3r &edgeDir,
1890  vector<WVertex *> &faceVertices)
1891 {
1892  WFace *face = nullptr;
1893  if (fe->isSmooth()) {
1894  FEdgeSmooth *fes = dynamic_cast<FEdgeSmooth *>(fe);
1895  face = (WFace *)fes->face();
1896  }
1897  OccludersSet occluders;
1898  WFace *oface;
1899  bool skipFace;
1900 
1902  OccludersSet::iterator p, pend;
1903 
1904  *oaPolygon = nullptr;
1905  if (((fe)->getNature() & Nature::SILHOUETTE) || ((fe)->getNature() & Nature::BORDER)) {
1906  occluders.clear();
1907  // we cast a ray from A in the same direction but looking behind
1908  Vec3r v(-u[0], -u[1], -u[2]);
1909  iGrid->castInfiniteRay(A, v, occluders, timestamp);
1910 
1911  bool noIntersection = true;
1912  real mint = FLT_MAX;
1913  // we met some occluders, let us fill the aShape field with the first intersected occluder
1914  for (p = occluders.begin(), pend = occluders.end(); p != pend; p++) {
1915  // check whether the edge and the polygon plane are coincident:
1916  //-------------------------------------------------------------
1917  // first let us compute the plane equation.
1918  oface = (WFace *)(*p)->userdata;
1919  Vec3r v1(((*p)->getVertices())[0]);
1920  Vec3r normal((*p)->getNormal());
1921  real d = -(v1 * normal);
1922  real t, t_u, t_v;
1923 
1924  if (face) {
1925  skipFace = false;
1926 
1927  if (face == oface) {
1928  continue;
1929  }
1930 
1931  if (faceVertices.empty()) {
1932  continue;
1933  }
1934 
1935  for (vector<WVertex *>::iterator fv = faceVertices.begin(), fvend = faceVertices.end();
1936  fv != fvend;
1937  ++fv) {
1938  if ((*fv)->isBoundary()) {
1939  continue;
1940  }
1941  WVertex::incoming_edge_iterator iebegin = (*fv)->incoming_edges_begin();
1942  WVertex::incoming_edge_iterator ieend = (*fv)->incoming_edges_end();
1943  for (ie = iebegin; ie != ieend; ++ie) {
1944  if ((*ie) == nullptr) {
1945  continue;
1946  }
1947 
1948  WFace *sface = (*ie)->GetbFace();
1949  if (sface == oface) {
1950  skipFace = true;
1951  break;
1952  }
1953  }
1954  if (skipFace) {
1955  break;
1956  }
1957  }
1958  if (skipFace) {
1959  continue;
1960  }
1961  }
1962  else {
1963  if (GeomUtils::COINCIDENT ==
1964  GeomUtils::intersectRayPlane(origin, edgeDir, normal, d, t, epsilon)) {
1965  continue;
1966  }
1967  }
1968  if ((*p)->rayIntersect(A, v, t, t_u, t_v)) {
1969  if (fabs(v * normal) > 0.0001) {
1970  if (t > 0.0) { // && t < 1.0) {
1971  if (t < mint) {
1972  *oaPolygon = (*p);
1973  mint = t;
1974  noIntersection = false;
1975  fe->setOccludeeIntersection(Vec3r(A + t * v));
1976  }
1977  }
1978  }
1979  }
1980  }
1981 
1982  if (noIntersection) {
1983  *oaPolygon = nullptr;
1984  }
1985  }
1986 }
1987 
1989  FEdge *fe, Grid *iGrid, real epsilon, Polygon3r **oaPolygon, unsigned timestamp)
1990 {
1991  OccludersSet occluders;
1992 
1993  Vec3r A;
1994  Vec3r edgeDir;
1995  Vec3r origin;
1996  A = Vec3r(((fe)->vertexA()->point3D() + (fe)->vertexB()->point3D()) / 2.0);
1997  edgeDir = Vec3r((fe)->vertexB()->point3D() - (fe)->vertexA()->point3D());
1998  edgeDir.normalize();
1999  origin = Vec3r((fe)->vertexA()->point3D());
2000  Vec3r u;
2001  if (_orthographicProjection) {
2002  u = Vec3r(0.0, 0.0, _viewpoint.z() - A.z());
2003  }
2004  else {
2005  u = Vec3r(_viewpoint - A);
2006  }
2007  u.normalize();
2008  if (A < iGrid->getOrigin()) {
2009  cerr << "Warning: point is out of the grid for fedge " << fe->getId().getFirst() << "-"
2010  << fe->getId().getSecond() << endl;
2011  }
2012 
2013  vector<WVertex *> faceVertices;
2014 
2015  WFace *face = nullptr;
2016  if (fe->isSmooth()) {
2017  FEdgeSmooth *fes = dynamic_cast<FEdgeSmooth *>(fe);
2018  face = (WFace *)fes->face();
2019  }
2020  if (face) {
2021  face->RetrieveVertexList(faceVertices);
2022  }
2023 
2024  return FindOccludee(
2025  fe, iGrid, epsilon, oaPolygon, timestamp, u, A, origin, edgeDir, faceVertices);
2026 }
2027 
2029  Grid *iGrid,
2030  real epsilon,
2031  set<ViewShape *> &oOccluders,
2032  Polygon3r **oaPolygon,
2033  unsigned timestamp)
2034 {
2035  OccludersSet occluders;
2036  int qi = 0;
2037 
2038  Vec3r center;
2039  Vec3r edgeDir;
2040  Vec3r origin;
2041 
2042  center = fe->center3d();
2043  edgeDir = Vec3r(fe->vertexB()->point3D() - fe->vertexA()->point3D());
2044  edgeDir.normalize();
2045  origin = Vec3r(fe->vertexA()->point3D());
2046  // Is the edge outside the view frustum ?
2047  Vec3r gridOrigin(iGrid->getOrigin());
2048  Vec3r gridExtremity(iGrid->getOrigin() + iGrid->gridSize());
2049 
2050  if ((center.x() < gridOrigin.x()) || (center.y() < gridOrigin.y()) ||
2051  (center.z() < gridOrigin.z()) || (center.x() > gridExtremity.x()) ||
2052  (center.y() > gridExtremity.y()) || (center.z() > gridExtremity.z())) {
2053  cerr << "Warning: point is out of the grid for fedge " << fe->getId() << endl;
2054  // return 0;
2055  }
2056 
2057 #if 0
2058  Vec3r A(fe->vertexA()->point2d());
2059  Vec3r B(fe->vertexB()->point2d());
2060  int viewport[4];
2062  if ((A.x() < viewport[0]) || (A.x() > viewport[2]) || (A.y() < viewport[1]) ||
2063  (A.y() > viewport[3]) || (B.x() < viewport[0]) || (B.x() > viewport[2]) ||
2064  (B.y() < viewport[1]) || (B.y() > viewport[3])) {
2065  cerr << "Warning: point is out of the grid for fedge " << fe->getId() << endl;
2066  //return 0;
2067  }
2068 #endif
2069 
2070  Vec3r vp;
2071  if (_orthographicProjection) {
2072  vp = Vec3r(center.x(), center.y(), _viewpoint.z());
2073  }
2074  else {
2075  vp = Vec3r(_viewpoint);
2076  }
2077  Vec3r u(vp - center);
2078  real raylength = u.norm();
2079  u.normalize();
2080 #if 0
2082  cout << "grid origin " << iGrid->getOrigin().x() << "," << iGrid->getOrigin().y() << ","
2083  << iGrid->getOrigin().z() << endl;
2084  cout << "center " << center.x() << "," << center.y() << "," << center.z() << endl;
2085  }
2086 #endif
2087 
2088  iGrid->castRay(center, vp, occluders, timestamp);
2089 
2090  WFace *face = nullptr;
2091  if (fe->isSmooth()) {
2092  FEdgeSmooth *fes = dynamic_cast<FEdgeSmooth *>(fe);
2093  face = (WFace *)fes->face();
2094  }
2095  vector<WVertex *> faceVertices;
2097 
2098  WFace *oface;
2099  bool skipFace;
2100  OccludersSet::iterator p, pend;
2101  if (face) {
2102  face->RetrieveVertexList(faceVertices);
2103  }
2104 
2105  for (p = occluders.begin(), pend = occluders.end(); p != pend; p++) {
2106  // If we're dealing with an exact silhouette, check whether we must take care of this occluder
2107  // of not. (Indeed, we don't consider the occluders that share at least one vertex with the
2108  // face containing this edge).
2109  //-----------
2110  oface = (WFace *)(*p)->userdata;
2111 #if LOGGING
2113  cout << "\t\tEvaluating intersection for occluder " << ((*p)->getVertices())[0]
2114  << ((*p)->getVertices())[1] << ((*p)->getVertices())[2] << endl
2115  << "\t\t\tand ray " << vp << " * " << u << " (center " << center << ")" << endl;
2116  }
2117 #endif
2118  Vec3r v1(((*p)->getVertices())[0]);
2119  Vec3r normal((*p)->getNormal());
2120  real d = -(v1 * normal);
2121  real t, t_u, t_v;
2122 
2123 #if LOGGING
2125  cout << "\t\tp: " << ((*p)->getVertices())[0] << ((*p)->getVertices())[1]
2126  << ((*p)->getVertices())[2] << ", norm: " << (*p)->getNormal() << endl;
2127  }
2128 #endif
2129 
2130  if (face) {
2131 #if LOGGING
2133  cout << "\t\tDetermining face adjacency...";
2134  }
2135 #endif
2136  skipFace = false;
2137 
2138  if (face == oface) {
2139 #if LOGGING
2141  cout << " Rejecting occluder for face concurrency." << endl;
2142  }
2143 #endif
2144  continue;
2145  }
2146 
2147  for (vector<WVertex *>::iterator fv = faceVertices.begin(), fvend = faceVertices.end();
2148  fv != fvend;
2149  ++fv) {
2150  if ((*fv)->isBoundary()) {
2151  continue;
2152  }
2153 
2154  WVertex::incoming_edge_iterator iebegin = (*fv)->incoming_edges_begin();
2155  WVertex::incoming_edge_iterator ieend = (*fv)->incoming_edges_end();
2156  for (ie = iebegin; ie != ieend; ++ie) {
2157  if ((*ie) == nullptr) {
2158  continue;
2159  }
2160 
2161  WFace *sface = (*ie)->GetbFace();
2162  // WFace *sfacea = (*ie)->GetaFace();
2163  // if ((sface == oface) || (sfacea == oface)) {
2164  if (sface == oface) {
2165  skipFace = true;
2166  break;
2167  }
2168  }
2169  if (skipFace) {
2170  break;
2171  }
2172  }
2173  if (skipFace) {
2174 #if LOGGING
2176  cout << " Rejecting occluder for face adjacency." << endl;
2177  }
2178 #endif
2179  continue;
2180  }
2181  }
2182  else {
2183  // check whether the edge and the polygon plane are coincident:
2184  //-------------------------------------------------------------
2185  // first let us compute the plane equation.
2186 
2187  if (GeomUtils::COINCIDENT ==
2188  GeomUtils::intersectRayPlane(origin, edgeDir, normal, d, t, epsilon)) {
2189 #if LOGGING
2191  cout << "\t\tRejecting occluder for target coincidence." << endl;
2192  }
2193 #endif
2194  continue;
2195  }
2196  }
2197 
2198  if ((*p)->rayIntersect(center, u, t, t_u, t_v)) {
2199 #if LOGGING
2201  cout << "\t\tRay " << vp << " * " << u << " intersects at time " << t << " (raylength is "
2202  << raylength << ")" << endl;
2203  cout << "\t\t(u * normal) == " << (u * normal) << " for normal " << normal << endl;
2204  }
2205 #endif
2206  if (fabs(u * normal) > 0.0001) {
2207  if ((t > 0.0) && (t < raylength)) {
2208 #if LOGGING
2210  cout << "\t\tIs occluder" << endl;
2211  }
2212 #endif
2213  WFace *f = (WFace *)((*p)->userdata);
2214  ViewShape *vshape = _ViewMap->viewShape(f->GetVertex(0)->shape()->GetId());
2215  oOccluders.insert(vshape);
2216  ++qi;
2217  if (!_EnableQI) {
2218  break;
2219  }
2220  }
2221  }
2222  }
2223  }
2224 
2225  // Find occludee
2226  FindOccludee(fe, iGrid, epsilon, oaPolygon, timestamp, u, center, origin, edgeDir, faceVertices);
2227 
2228  return qi;
2229 }
2230 
2232  intersection_algo iAlgo,
2233  real epsilon)
2234 {
2235  switch (iAlgo) {
2236  case sweep_line:
2237  ComputeSweepLineIntersections(ioViewMap, epsilon);
2238  break;
2239  default:
2240  break;
2241  }
2242 #if 0
2244  ViewMap::viewvertices_container &vvertices = ioViewMap->ViewVertices();
2245  for (ViewMap::viewvertices_container::iterator vv = vvertices.begin(), vvend = vvertices.end();
2246  vv != vvend;
2247  ++vv) {
2248  if ((*vv)->getNature() == Nature::T_VERTEX) {
2249  TVertex *tvertex = (TVertex *)(*vv);
2250  cout << "TVertex " << tvertex->getId() << " has :" << endl;
2251  cout << "FrontEdgeA: " << tvertex->frontEdgeA().first << endl;
2252  cout << "FrontEdgeB: " << tvertex->frontEdgeB().first << endl;
2253  cout << "BackEdgeA: " << tvertex->backEdgeA().first << endl;
2254  cout << "BackEdgeB: " << tvertex->backEdgeB().first << endl << endl;
2255  }
2256  }
2257  }
2258 #endif
2259 }
2260 
2263 
2265  {
2266  epsilon = eps;
2267  }
2268 
2270  {
2271  Vec3r A = x->point2D();
2272  Vec3r B = y->point2D();
2273  for (unsigned int i = 0; i < 3; i++) {
2274  if (fabs(A[i] - B[i]) < epsilon) {
2275  continue;
2276  }
2277  if (A[i] < B[i]) {
2278  return true;
2279  }
2280  if (A[i] > B[i]) {
2281  return false;
2282  }
2283  }
2284  return false;
2285  }
2286 };
2287 
2290 
2293 
2295  {
2296  edge = iEdge;
2297  }
2298 
2300  {
2301  real tx = x->getParameter(edge);
2302  real ty = y->getParameter(edge);
2303  if (tx > ty) {
2304  return true;
2305  }
2306  return false;
2307  }
2308 };
2309 
2310 struct silhouette_binary_rule : public binary_rule<segment, segment> {
2311  bool operator()(segment &s1, segment &s2) override
2312  {
2313  FEdge *f1 = s1.edge();
2314  FEdge *f2 = s2.edge();
2315 
2316  if ((!(((f1)->getNature() & Nature::SILHOUETTE) || ((f1)->getNature() & Nature::BORDER))) &&
2317  (!(((f2)->getNature() & Nature::SILHOUETTE) || ((f2)->getNature() & Nature::BORDER)))) {
2318  return false;
2319  }
2320 
2321  return true;
2322  }
2323 };
2324 
2326 {
2327  vector<SVertex *> &svertices = ioViewMap->SVertices();
2328  bool progressBarDisplay = false;
2329  unsigned sVerticesSize = svertices.size();
2330  unsigned fEdgesSize = ioViewMap->FEdges().size();
2331 #if 0
2333  ViewMap::fedges_container &fedges = ioViewMap->FEdges();
2334  for (ViewMap::fedges_container::const_iterator f = fedges.begin(), end = fedges.end();
2335  f != end;
2336  ++f) {
2337  cout << (*f)->aMaterialIndex() << "-" << (*f)->bMaterialIndex() << endl;
2338  }
2339  }
2340 #endif
2341  unsigned progressBarStep = 0;
2342 
2343  if (_pProgressBar != nullptr && fEdgesSize > gProgressBarMinSize) {
2344  unsigned progressBarSteps = min(gProgressBarMaxSteps, sVerticesSize);
2345  progressBarStep = sVerticesSize / progressBarSteps;
2346  _pProgressBar->reset();
2347  _pProgressBar->setLabelText("Computing Sweep Line Intersections");
2348  _pProgressBar->setTotalSteps(progressBarSteps);
2349  _pProgressBar->setProgress(0);
2350  progressBarDisplay = true;
2351  }
2352 
2353  unsigned counter = progressBarStep;
2354 
2355  sort(svertices.begin(), svertices.end(), less_SVertex2D(epsilon));
2356 
2358 
2359  vector<FEdge *> &ioEdges = ioViewMap->FEdges();
2360 
2361  vector<segment *> segments;
2362 
2363  vector<FEdge *>::iterator fe, fend;
2364 
2365  for (fe = ioEdges.begin(), fend = ioEdges.end(); fe != fend; fe++) {
2366  segment *s = new segment((*fe), (*fe)->vertexA()->point2D(), (*fe)->vertexB()->point2D());
2367  (*fe)->userdata = s;
2368  segments.push_back(s);
2369  }
2370 
2371  vector<segment *> vsegments;
2372  for (vector<SVertex *>::iterator sv = svertices.begin(), svend = svertices.end(); sv != svend;
2373  sv++) {
2374  if (_pRenderMonitor && _pRenderMonitor->testBreak()) {
2375  break;
2376  }
2377 
2378  const vector<FEdge *> &vedges = (*sv)->fedges();
2379 
2380  for (vector<FEdge *>::const_iterator sve = vedges.begin(), sveend = vedges.end();
2381  sve != sveend;
2382  sve++) {
2383  vsegments.push_back((segment *)((*sve)->userdata));
2384  }
2385 
2386  Vec3r evt((*sv)->point2D());
2388  SL.process(evt, vsegments, sbr, epsilon);
2389 
2390  if (progressBarDisplay) {
2391  counter--;
2392  if (counter <= 0) {
2393  counter = progressBarStep;
2394  _pProgressBar->setProgress(_pProgressBar->getProgress() + 1);
2395  }
2396  }
2397  vsegments.clear();
2398  }
2399 
2400  if (_pRenderMonitor && _pRenderMonitor->testBreak()) {
2401  // delete segments
2402  if (!segments.empty()) {
2403  vector<segment *>::iterator s, send;
2404  for (s = segments.begin(), send = segments.end(); s != send; s++) {
2405  delete *s;
2406  }
2407  }
2408  return;
2409  }
2410 
2411  // reset userdata:
2412  for (fe = ioEdges.begin(), fend = ioEdges.end(); fe != fend; fe++) {
2413  (*fe)->userdata = nullptr;
2414  }
2415 
2416  // list containing the new edges resulting from splitting operations.
2417  vector<FEdge *> newEdges;
2418 
2419  // retrieve the intersected edges:
2420  vector<segment *> &iedges = SL.intersectedEdges();
2421  // retrieve the intersections:
2422  vector<intersection *> &intersections = SL.intersections();
2423 
2424  int id = 0;
2425  // create a view vertex for each intersection and linked this one with the intersection object
2426  vector<intersection *>::iterator i, iend;
2427  for (i = intersections.begin(), iend = intersections.end(); i != iend; i++) {
2428  FEdge *fA = (*i)->EdgeA->edge();
2429  FEdge *fB = (*i)->EdgeB->edge();
2430 
2431  Vec3r A1 = fA->vertexA()->point3D();
2432  Vec3r A2 = fA->vertexB()->point3D();
2433  Vec3r B1 = fB->vertexA()->point3D();
2434  Vec3r B2 = fB->vertexB()->point3D();
2435 
2436  Vec3r a1 = fA->vertexA()->point2D();
2437  Vec3r a2 = fA->vertexB()->point2D();
2438  Vec3r b1 = fB->vertexA()->point2D();
2439  Vec3r b2 = fB->vertexB()->point2D();
2440 
2441  real ta = (*i)->tA;
2442  real tb = (*i)->tB;
2443 
2444  if ((ta < -epsilon) || (ta > 1 + epsilon)) {
2445  cerr << "Warning: 2D intersection out of range for edge " << fA->vertexA()->getId() << " - "
2446  << fA->vertexB()->getId() << endl;
2447  }
2448 
2449  if ((tb < -epsilon) || (tb > 1 + epsilon)) {
2450  cerr << "Warning: 2D intersection out of range for edge " << fB->vertexA()->getId() << " - "
2451  << fB->vertexB()->getId() << endl;
2452  }
2453 
2456 
2457  if ((Ta < -epsilon) || (Ta > 1 + epsilon)) {
2458  cerr << "Warning: 3D intersection out of range for edge " << fA->vertexA()->getId() << " - "
2459  << fA->vertexB()->getId() << endl;
2460  }
2461 
2462  if ((Tb < -epsilon) || (Tb > 1 + epsilon)) {
2463  cerr << "Warning: 3D intersection out of range for edge " << fB->vertexA()->getId() << " - "
2464  << fB->vertexB()->getId() << endl;
2465  }
2466 
2467 #if 0
2469  if ((Ta < -epsilon) || (Ta > 1 + epsilon) || (Tb < -epsilon) || (Tb > 1 + epsilon)) {
2470  printf("ta %.12e\n", ta);
2471  printf("tb %.12e\n", tb);
2472  printf("a1 %e, %e -- a2 %e, %e\n", a1[0], a1[1], a2[0], a2[1]);
2473  printf("b1 %e, %e -- b2 %e, %e\n", b1[0], b1[1], b2[0], b2[1]);
2474  //printf("line([%e, %e], [%e, %e]);\n", a1[0], a2[0], a1[1], a2[1]);
2475  //printf("line([%e, %e], [%e, %e]);\n", b1[0], b2[0], b1[1], b2[1]);
2476  if ((Ta < -epsilon) || (Ta > 1 + epsilon)) {
2477  printf("Ta %.12e\n", Ta);
2478  }
2479  if ((Tb < -epsilon) || (Tb > 1 + epsilon)) {
2480  printf("Tb %.12e\n", Tb);
2481  }
2482  printf("A1 %e, %e, %e -- A2 %e, %e, %e\n", A1[0], A1[1], A1[2], A2[0], A2[1], A2[2]);
2483  printf("B1 %e, %e, %e -- B2 %e, %e, %e\n", B1[0], B1[1], B1[2], B2[0], B2[1], B2[2]);
2484  }
2485  }
2486 #endif
2487 
2488  TVertex *tvertex = ioViewMap->CreateTVertex(Vec3r(A1 + Ta * (A2 - A1)),
2489  Vec3r(a1 + ta * (a2 - a1)),
2490  fA,
2491  Vec3r(B1 + Tb * (B2 - B1)),
2492  Vec3r(b1 + tb * (b2 - b1)),
2493  fB,
2494  id);
2495 
2496  (*i)->userdata = tvertex;
2497  ++id;
2498  }
2499 
2500  progressBarStep = 0;
2501 
2502  if (progressBarDisplay) {
2503  unsigned iEdgesSize = iedges.size();
2504  unsigned progressBarSteps = min(gProgressBarMaxSteps, iEdgesSize);
2505  progressBarStep = iEdgesSize / progressBarSteps;
2506  _pProgressBar->reset();
2507  _pProgressBar->setLabelText("Splitting intersected edges");
2508  _pProgressBar->setTotalSteps(progressBarSteps);
2509  _pProgressBar->setProgress(0);
2510  }
2511 
2512  counter = progressBarStep;
2513 
2514  vector<TVertex *> edgeVVertices;
2515  vector<ViewEdge *> newVEdges;
2516  vector<segment *>::iterator s, send;
2517  for (s = iedges.begin(), send = iedges.end(); s != send; s++) {
2518  edgeVVertices.clear();
2519  newEdges.clear();
2520  newVEdges.clear();
2521 
2522  FEdge *fedge = (*s)->edge();
2523  ViewEdge *vEdge = fedge->viewedge();
2524  ViewShape *shape = vEdge->viewShape();
2525 
2526  vector<intersection *> &eIntersections = (*s)->intersections();
2527  // we first need to sort these intersections from farther to closer to A
2528  sort(eIntersections.begin(), eIntersections.end(), less_Intersection(*s));
2529  for (i = eIntersections.begin(), iend = eIntersections.end(); i != iend; i++) {
2530  edgeVVertices.push_back((TVertex *)(*i)->userdata);
2531  }
2532 
2533  shape->SplitEdge(fedge, edgeVVertices, ioViewMap->FEdges(), ioViewMap->ViewEdges());
2534 
2535  if (progressBarDisplay) {
2536  counter--;
2537  if (counter <= 0) {
2538  counter = progressBarStep;
2539  _pProgressBar->setProgress(_pProgressBar->getProgress() + 1);
2540  }
2541  }
2542  }
2543 
2544  // reset userdata:
2545  for (fe = ioEdges.begin(), fend = ioEdges.end(); fe != fend; fe++) {
2546  (*fe)->userdata = nullptr;
2547  }
2548 
2549  // delete segments
2550  if (!segments.empty()) {
2551  for (s = segments.begin(), send = segments.end(); s != send; s++) {
2552  delete *s;
2553  }
2554  }
2555 }
2556 
2557 } /* namespace Freestyle */
typedef float(TangentPoint)[2]
@ G_DEBUG_FREESTYLE
Definition: BKE_global.h:181
Class to define a cell grid surrounding the projected image of a scene.
Class to define a cell grid surrounding the projected image of a scene.
NSNotificationCenter * center
_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 y
_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
Class to define a cell grid surrounding the projected image of a scene.
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
Class to define a cell grid surrounding the projected image of a scene.
#define A2
Definition: RandGen.cpp:24
#define A1
Definition: RandGen.cpp:23
Class to define a cell grid surrounding the projected image of a scene.
#define LOGGING
Class to build silhouette edges from a Winged-Edge structure.
ATTR_WARN_UNUSED_RESULT const BMVert * v
#define A
SIMD_FORCE_INLINE btVector3 transform(const btVector3 &point) const
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
void sort(btMatrix3x3 &U, btVector3 &sigma, btMatrix3x3 &V, int t)
Helper function of 3X3 SVD for sorting singular values.
SIMD_FORCE_INLINE btVector3 & getOrigin()
Return the origin vector translation.
Definition: btTransform.h:113
const Point & getMax() const
Definition: BBox.h:72
const Point & getMin() const
Definition: BBox.h:67
void * face() const
Definition: Silhouette.h:1340
virtual Id getId() const
Definition: Silhouette.h:483
void setOccludeeEmpty(bool iempty)
Definition: Silhouette.h:798
Vec3r center2d()
Definition: Silhouette.h:668
int occluders_size() const
Definition: Silhouette.cpp:259
SVertex * vertexA()
Definition: Silhouette.h:597
ViewEdge * viewedge() const
Definition: Silhouette.h:658
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
bool isSmooth() const
Definition: Silhouette.h:706
void setaFace(Polygon3r &iFace)
Definition: Silhouette.h:788
FEdge * nextEdge()
Definition: Silhouette.h:623
void setOccludeeIntersection(const Vec3r &iPoint)
Definition: Silhouette.h:793
bool rayIntersect(const Vec3r &orig, const Vec3r &dir, real &t, real &u, real &v, real epsilon=M_EPSILON) const
Definition: Polygon.h:195
const vector< Point > & getVertices() const
Definition: Polygon.h:67
unsigned getId() const
Definition: Polygon.h:95
virtual AutoPtr< GridDensityProvider > newGridDensityProvider(OccluderSource &source, const real proscenium[4])=0
Vec3r gridSize() const
Definition: Grid.h:326
const Vec3r & getOrigin() const
Definition: Grid.h:321
void castInfiniteRay(const Vec3r &orig, const Vec3r &dir, OccludersSet &occluders, unsigned timestamp)
Definition: Grid.cpp:293
void castRay(const Vec3r &orig, const Vec3r &end, OccludersSet &occluders, unsigned timestamp)
Definition: Grid.cpp:283
id_type getFirst() const
Definition: Id.h:62
id_type getSecond() const
Definition: Id.h:68
void setInfo(string info)
Definition: RenderMonitor.h:29
void setId(Id id)
Definition: Silhouette.h:1907
void setFrsMaterials(const vector< FrsMaterial > &iMaterials)
Definition: Silhouette.h:1925
void setLibraryPath(const string &path)
Definition: Silhouette.h:1919
void setName(const string &name)
Definition: Silhouette.h:1913
const Vec3r & point2d() const
Definition: Silhouette.h:395
const Vec3r & point3D() const
Definition: Silhouette.h:223
virtual Id getId() const
Definition: Silhouette.h:117
const Vec3r & point2D() const
Definition: Silhouette.h:228
virtual real getProjectedY() const
Definition: Silhouette.h:96
virtual real getProjectedX() const
Definition: Silhouette.h:90
static real ImageToWorldParameter(FEdge *fe, real t)
static void retrieveViewport(int viewport[4])
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
vector< Segment< T, Point > * > & intersectedEdges()
Definition: SweepLine.h:313
directedViewEdge & frontEdgeB()
Definition: ViewMap.h:538
directedViewEdge & frontEdgeA()
Definition: ViewMap.h:533
directedViewEdge & backEdgeB()
Definition: ViewMap.h:548
directedViewEdge & backEdgeA()
Definition: ViewMap.h:543
virtual Id getId() const
Definition: ViewMap.h:441
value_type x() const
Definition: VecMat.h:518
value_type z() const
Definition: VecMat.h:538
value_type y() const
Definition: VecMat.h:528
value_type norm() const
Definition: VecMat.h:95
Vec< T, N > & normalize()
Definition: VecMat.h:105
ViewShape * viewShape()
Definition: ViewMap.h:1091
void ComputeFastRayCastingVisibility(ViewMap *ioViewMap, real epsilon=1.0e-6)
void ComputeCumulativeVisibility(ViewMap *ioViewMap, WingedEdge &we, const BBox< Vec3r > &bbox, real epsilon, bool cull, GridDensityProviderFactory &factory)
void ComputeEdgesVisibility(ViewMap *ioViewMap, WingedEdge &we, const BBox< Vec3r > &bbox, unsigned int sceneNumFaces, visibility_algo iAlgo=ray_casting, real epsilon=1.0e-6)
void FindOccludee(FEdge *fe, Grid *iGrid, real epsilon, Polygon3r **oaPolygon, unsigned timestamp)
void CullViewEdges(ViewMap *ioViewMap, real viewProscenium[4], real occluderProscenium[4], bool extensiveFEdgeSearch=true)
void computeInitialViewEdges(WingedEdge &)
void ComputeRayCastingVisibility(ViewMap *ioViewMap, real epsilon=1.0e-6)
void BuildGrid(WingedEdge &we, const BBox< Vec3r > &bbox, unsigned int sceneNumFaces)
void computeCusps(ViewMap *ioViewMap)
ViewMap * BuildViewMap(WingedEdge &we, visibility_algo iAlgo, real epsilon, const BBox< Vec3r > &bbox, unsigned int sceneNumFaces)
void ComputeIntersections(ViewMap *ioViewMap, intersection_algo iAlgo=sweep_line, real epsilon=1.0e-06)
void ComputeSweepLineIntersections(ViewMap *ioViewMap, real epsilon=1.0e-6)
void ComputeVeryFastRayCastingVisibility(ViewMap *ioViewMap, real epsilon=1.0e-6)
void ComputeDetailedVisibility(ViewMap *ioViewMap, WingedEdge &we, const BBox< Vec3r > &bbox, real epsilon, bool cull, GridDensityProviderFactory &factory)
vector< FEdge * > fedges_container
Definition: ViewMap.h:52
ViewShape * viewShape(unsigned id)
Definition: ViewMap.cpp:76
vector< ViewVertex * > viewvertices_container
Definition: ViewMap.h:49
vector< ViewEdge * > viewedges_container
Definition: ViewMap.h:48
TVertex * CreateTVertex(const Vec3r &iA3D, const Vec3r &iA2D, FEdge *iFEdgeA, const Vec3r &iB3D, const Vec3r &iB2D, FEdge *iFEdgeB, const Id &id)
Definition: ViewMap.cpp:129
svertices_container & SVertices()
Definition: ViewMap.h:121
viewvertices_container & ViewVertices()
Definition: ViewMap.h:109
fedges_container & FEdges()
Definition: ViewMap.h:115
ViewVertex * InsertViewVertex(SVertex *iVertex, vector< ViewEdge * > &newViewEdges)
Definition: ViewMap.cpp:172
viewedges_container & ViewEdges()
Definition: ViewMap.h:103
void SplitEdge(FEdge *fe, const vector< TVertex * > &iViewVertices, vector< FEdge * > &ioNewEdges, vector< ViewEdge * > &ioNewViewEdges)
Definition: ViewMap.h:1640
virtual Nature::VertexNature getNature() const
Definition: ViewMap.h:317
void setNature(Nature::VertexNature iNature)
Definition: ViewMap.h:324
void * userdata
Definition: WEdge.h:703
int numberOfEdges() const
Definition: WEdge.h:879
Vec3f & GetNormal()
Definition: WEdge.h:728
WVertex * GetVertex(unsigned int index)
Definition: WEdge.h:751
const vector< WOEdge * > & getEdgeList()
Definition: WEdge.h:718
void RetrieveVertexList(vector< WVertex * > &oVertices)
Definition: WEdge.h:778
unsigned GetId()
Definition: WEdge.h:1060
Vec3f & GetVertex()
Definition: WEdge.h:73
WShape * shape() const
Definition: WEdge.h:88
vector< WShape * > & getWShapes()
Definition: WEdge.h:1322
SyclQueue void void size_t num_bytes void
IconTextureDrawCall normal
int count
ccl_gpu_kernel_postfix ccl_global int * counter
ccl_device_inline float2 fabs(const float2 &a)
Definition: math_float2.h:222
ccl_device_inline float3 ceil(const float3 &a)
Definition: math_float3.h:363
#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
intersection_test intersectRayPlane(const Vec3r &orig, const Vec3r &dir, const Vec3r &norm, const real d, real &t, const real epsilon)
Definition: GeomUtils.cpp:498
VecMat::Vec3< real > Vec3r
Definition: Geom.h:28
void getDefaultViewProscenium(real viewProscenium[4])
Definition: GridHelpers.cpp:12
static const EdgeNature BORDER
Definition: Nature.h:38
static const VertexNature T_VERTEX
Definition: Nature.h:28
static const VertexNature CUSP
Definition: Nature.h:30
static const EdgeNature SILHOUETTE
Definition: Nature.h:36
inherits from class Rep
Definition: AppCanvas.cpp:18
static void computeDetailedVisibility(ViewMap *ioViewMap, G &grid, real epsilon, RenderMonitor *iRenderMonitor)
static void computeFastVisibility(ViewMap *ioViewMap, G &grid, real epsilon)
static real distance2D(const Vec3r &point, const real origin[2])
static double B1(double u)
Definition: FitCurve.cpp:304
static unsigned x[3]
Definition: RandGen.cpp:73
static const Global & _global
static const unsigned gProgressBarMinSize
static const unsigned gProgressBarMaxSteps
static bool insideProscenium(const real proscenium[4], const Vec3r &point)
static void computeCumulativeVisibility(ViewMap *ioViewMap, G &grid, real epsilon, RenderMonitor *iRenderMonitor)
Segment< FEdge *, Vec3r > segment
static int computeVisibility(ViewMap *viewMap, FEdge *fe, G &grid, real epsilon, ViewEdge *, WFace **oaWFace, set< ViewShape * > *foundOccluders)
vector< Polygon3r * > OccludersSet
Definition: Grid.h:33
static void findOccludee(FEdge *fe, G &, I &occluders, real epsilon, WFace **oaWFace, Vec3r &u, Vec3r &A, Vec3r &origin, Vec3r &edgeDir, vector< WVertex * > &faceVertices)
static double B2(double u)
Definition: FitCurve.cpp:310
static bool crossesProscenium(real proscenium[4], FEdge *fe)
static void computeVeryFastVisibility(ViewMap *ioViewMap, G &grid, real epsilon)
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
static const pxr::TfToken density("density", pxr::TfToken::Immortal)
#define I
const btScalar eps
Definition: poly34.cpp:11
#define min(a, b)
Definition: sort.c:35
bool operator()(intersection *x, intersection *y)
bool operator()(SVertex *x, SVertex *y)
bool operator()(segment &s1, segment &s2) override
int debug
Definition: BKE_global.h:123
float max