Fix for a static variable in BlenderStrokeRenderer::RenderStrokeRep() left after
[blender.git] / source / blender / freestyle / intern / view_map / CulledOccluderSource.cpp
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2010 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/freestyle/intern/view_map/CulledOccluderSource.cpp
29  *  \ingroup freestyle
30  *  \brief Class to define a cell grid surrounding the projected image of a scene
31  *  \author Alexander Beels
32  *  \date 2010-12-21
33  */
34
35 #include "CulledOccluderSource.h"
36
37 #include "FRS_freestyle.h"
38
39 #include "../geometry/GridHelpers.h"
40
41 #include "BKE_global.h"
42
43 CulledOccluderSource::CulledOccluderSource(const GridHelpers::Transform& t, WingedEdge& we, ViewMap& viewMap,
44                                            bool extensiveFEdgeSearch)
45 : OccluderSource(t, we), rejected(0), gridSpaceOccluderProsceniumInitialized(false)
46 {
47         cullViewEdges(viewMap, extensiveFEdgeSearch);
48
49         // If we have not found any visible FEdges during our cull, then there is nothing to iterate over.
50         // Short-circuit everything.
51         valid = gridSpaceOccluderProsceniumInitialized;
52
53         if (valid && ! testCurrent()) {
54                 next();
55         }
56 }
57
58 CulledOccluderSource::~CulledOccluderSource() {}
59
60 bool CulledOccluderSource::testCurrent()
61 {
62         if (valid) {
63                 // The test for gridSpaceOccluderProsceniumInitialized should not be necessary
64                 return gridSpaceOccluderProsceniumInitialized &&
65                        GridHelpers::insideProscenium(gridSpaceOccluderProscenium, cachedPolygon);
66         }
67         return false;
68 }
69
70 bool CulledOccluderSource::next()
71 {
72         while (OccluderSource::next()) {
73                 if (testCurrent()) {
74                         ++rejected;
75                         return true;
76                 }
77         }
78         if (G.debug & G_DEBUG_FREESTYLE) {
79                 std::cout << "Finished generating occluders.  Rejected " << rejected << " faces." << std::endl;
80         }
81         return false;
82 }
83
84 void CulledOccluderSource::getOccluderProscenium(real proscenium[4])
85 {
86         for (unsigned int i = 0; i < 4; ++i) {
87                 proscenium[i] = gridSpaceOccluderProscenium[i];
88         }
89 }
90
91 static inline real distance2D(const Vec3r & point, const real origin[2])
92 {
93         return ::hypot((point[0] - origin[0]), (point[1] - origin[1]));
94 }
95
96 static inline bool crossesProscenium(real proscenium[4], FEdge *fe)
97 {
98         Vec2r min(proscenium[0], proscenium[2]);
99         Vec2r max(proscenium[1], proscenium[3]);
100         Vec2r A(fe->vertexA()->getProjectedX(), fe->vertexA()->getProjectedY());
101         Vec2r B(fe->vertexB()->getProjectedX(), fe->vertexB()->getProjectedY());
102
103         return GeomUtils::intersect2dSeg2dArea (min, max, A, B);
104 }
105
106 static inline bool insideProscenium(real proscenium[4], const Vec3r& point)
107 {
108         return !(point[0] < proscenium[0] || point[0] > proscenium[1] ||
109                  point[1] < proscenium[2] || point[1] > proscenium[3]);
110 }
111
112 void CulledOccluderSource::cullViewEdges(ViewMap& viewMap, bool extensiveFEdgeSearch)
113 {
114         // Cull view edges by marking them as non-displayable.
115         // This avoids the complications of trying to delete edges from the ViewMap.
116
117         // Non-displayable view edges will be skipped over during visibility calculation.
118
119         // View edges will be culled according to their position w.r.t. the viewport proscenium (viewport + 5% border,
120         // or some such).
121
122         // Get proscenium boundary for culling
123         real viewProscenium[4];
124         GridHelpers::getDefaultViewProscenium(viewProscenium);
125         real prosceniumOrigin[2];
126         prosceniumOrigin[0] = (viewProscenium[1] - viewProscenium[0]) / 2.0;
127         prosceniumOrigin[1] = (viewProscenium[3] - viewProscenium[2]) / 2.0;
128         if (G.debug & G_DEBUG_FREESTYLE) {
129                 cout << "Proscenium culling:" << endl;
130                 cout << "Proscenium: [" << viewProscenium[0] << ", " << viewProscenium[1] << ", " << viewProscenium[2]
131                      << ", " << viewProscenium[3] << "]"<< endl;
132                 cout << "Origin: [" << prosceniumOrigin[0] << ", " << prosceniumOrigin[1] << "]"<< endl;
133         }
134
135         // A separate occluder proscenium will also be maintained, starting out the same as the viewport proscenium, and
136         // expanding as necessary so that it encompasses the center point of at least one feature edge in each
137         // retained view edge.
138         // The occluder proscenium will be used later to cull occluding triangles before they are inserted into the Grid.
139         // The occluder proscenium starts out the same size as the view proscenium
140         GridHelpers::getDefaultViewProscenium(occluderProscenium);
141
142         // XXX Freestyle is inconsistent in its use of ViewMap::viewedges_container and vector<ViewEdge*>::iterator.
143         // Probably all occurences of vector<ViewEdge*>::iterator should be replaced ViewMap::viewedges_container
144         // throughout the code.
145         // For each view edge
146         ViewMap::viewedges_container::iterator ve, veend;
147
148         for (ve = viewMap.ViewEdges().begin(), veend = viewMap.ViewEdges().end(); ve != veend; ve++) {
149                 // Overview:
150                 //    Search for a visible feature edge
151                 //    If none: mark view edge as non-displayable
152                 //    Otherwise:
153                 //        Find a feature edge with center point inside occluder proscenium.
154                 //        If none exists, find the feature edge with center point closest to viewport origin.
155                 //            Expand occluder proscenium to enclose center point.
156
157                 // For each feature edge, while bestOccluderTarget not found and view edge not visibile
158                 bool bestOccluderTargetFound = false;
159                 FEdge *bestOccluderTarget = NULL;
160                 real bestOccluderDistance = 0.0;
161                 FEdge *festart = (*ve)->fedgeA();
162                 FEdge *fe = festart;
163                 // All ViewEdges start culled
164                 (*ve)->setIsInImage(false);
165
166                 // For simple visibility calculation: mark a feature edge that is known to have a center point inside
167                 // the occluder proscenium. Cull all other feature edges.
168                 do {
169                         // All FEdges start culled
170                         fe->setIsInImage(false);
171
172                         // Look for the visible edge that can most easily be included in the occluder proscenium.
173                         if (!bestOccluderTargetFound) {
174                                 // If center point is inside occluder proscenium,
175                                 if (insideProscenium(occluderProscenium, fe->center2d())) {
176                                         // Use this feature edge for visibility deterimination
177                                         fe->setIsInImage(true);
178                                         expandGridSpaceOccluderProscenium(fe);
179                                         // Mark bestOccluderTarget as found
180                                         bestOccluderTargetFound = true;
181                                         bestOccluderTarget = fe;
182                                 }
183                                 else {
184                                         real d = distance2D(fe->center2d(), prosceniumOrigin);
185                                         // If center point is closer to viewport origin than current target
186                                         if (bestOccluderTarget == NULL || d < bestOccluderDistance) {
187                                                 // Then store as bestOccluderTarget
188                                                 bestOccluderDistance = d;
189                                                 bestOccluderTarget = fe;
190                                         }
191                                 }
192                         }
193
194                         // If feature edge crosses the view proscenium
195                         if (!(*ve)->isInImage() && crossesProscenium(viewProscenium, fe)) {
196                                 // Then the view edge will be included in the image
197                                 (*ve)->setIsInImage(true);
198                         }
199                         fe = fe->nextEdge();
200                 } while (fe != NULL && fe != festart && !(bestOccluderTargetFound && (*ve)->isInImage()));
201
202                 // Either we have run out of FEdges, or we already have the one edge we need to determine visibility
203                 // Cull all remaining edges.
204                 while (fe != NULL && fe != festart) {
205                         fe->setIsInImage(false);
206                         fe = fe->nextEdge();
207                 }
208
209                 // If bestOccluderTarget was not found inside the occluder proscenium, 
210                 // we need to expand the occluder proscenium to include it.
211                 if ((*ve)->isInImage() && bestOccluderTarget != NULL && ! bestOccluderTargetFound) {
212                         // Expand occluder proscenium to enclose bestOccluderTarget
213                         Vec3r point = bestOccluderTarget->center2d();
214                         if (point[0] < occluderProscenium[0]) {
215                                 occluderProscenium[0] = point[0];
216                         }
217                         else if (point[0] > occluderProscenium[1]) {
218                                 occluderProscenium[1] = point[0];
219                         }
220                         if (point[1] < occluderProscenium[2]) {
221                                 occluderProscenium[2] = point[1];
222                         }
223                         else if (point[1] > occluderProscenium[3]) {
224                                 occluderProscenium[3] = point[1];
225                         }
226                         // Use bestOccluderTarget for visibility determination
227                         bestOccluderTarget->setIsInImage(true);
228                 }
229         }
230
231         // We are done calculating the occluder proscenium.
232         // Expand the occluder proscenium by an epsilon to avoid rounding errors.
233         const real epsilon = 1.0e-6;
234         occluderProscenium[0] -= epsilon;
235         occluderProscenium[1] += epsilon;
236         occluderProscenium[2] -= epsilon;
237         occluderProscenium[3] += epsilon;
238
239         // For "Normal" or "Fast" style visibility computation only:
240
241         // For more detailed visibility calculation, make a second pass through the view map, marking all feature edges
242         // with center points inside the final occluder proscenium. All of these feature edges can be considered during
243         // visibility calculation.
244
245         // So far we have only found one FEdge per ViewEdge. The "Normal" and "Fast" styles of visibility computation
246         // want to consider many FEdges for each ViewEdge.
247         // Here we re-scan the view map to find any usable FEdges that we skipped on the first pass, or that have become
248         // usable because the occluder proscenium has been expanded since the edge was visited on the first pass.
249         if (extensiveFEdgeSearch) {
250                 // For each view edge,
251                 for (ve = viewMap.ViewEdges().begin(), veend = viewMap.ViewEdges().end(); ve != veend; ve++) {
252                         if (!(*ve)->isInImage()) {
253                                 continue;
254                         }
255                         // For each feature edge,
256                         FEdge *festart = (*ve)->fedgeA();
257                         FEdge *fe = festart;
258                         do {
259                                 // If not (already) visible and center point inside occluder proscenium, 
260                                 if (!fe->isInImage() && insideProscenium(occluderProscenium, fe->center2d())) {
261                                         // Use the feature edge for visibility determination
262                                         fe->setIsInImage(true);
263                                         expandGridSpaceOccluderProscenium(fe);
264                                 }
265                                 fe = fe->nextEdge();
266                         } while (fe != NULL && fe != festart);
267                 }
268         }
269
270         // Up until now, all calculations have been done in camera space.
271         // However, the occluder source's iteration and the grid that consumes the occluders both work in gridspace,
272         // so we need a version of the occluder proscenium in gridspace.
273         // Set the gridspace occlude proscenium
274 }
275
276 void CulledOccluderSource::expandGridSpaceOccluderProscenium(FEdge *fe)
277 {
278         if (gridSpaceOccluderProsceniumInitialized) {
279                 GridHelpers::expandProscenium(gridSpaceOccluderProscenium, transform(fe->center3d()));
280         }
281         else {
282                 const Vec3r& point = transform(fe->center3d());
283                 gridSpaceOccluderProscenium[0] = gridSpaceOccluderProscenium[1] = point[0];
284                 gridSpaceOccluderProscenium[2] = gridSpaceOccluderProscenium[3] = point[1];
285                 gridSpaceOccluderProsceniumInitialized = true;
286         }
287 }