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