Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(1757)

Unified Diff: source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp

Issue 7416049: Freestyle r54826 branch review Base URL: https://svn.blender.org/svnroot/bf-blender/trunk/blender/
Patch Set: Created 11 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp
===================================================================
--- source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp (revision 0)
+++ source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp (working copy)
@@ -0,0 +1,287 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2010 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/freestyle/intern/view_map/CulledOccluderSource.cpp
+ * \ingroup freestyle
+ * \brief Class to define a cell grid surrounding the projected image of a scene
+ * \author Alexander Beels
+ * \date 2010-12-21
+ */
+
+#include "CulledOccluderSource.h"
+
+#include "FRS_freestyle.h"
+
+#include "../geometry/GridHelpers.h"
+
+#include "BKE_global.h"
+
+CulledOccluderSource::CulledOccluderSource(const GridHelpers::Transform& t, WingedEdge& we, ViewMap& viewMap,
+ bool extensiveFEdgeSearch)
+: OccluderSource(t, we), rejected(0), gridSpaceOccluderProsceniumInitialized(false)
+{
+ cullViewEdges(viewMap, extensiveFEdgeSearch);
+
+ // If we have not found any visible FEdges during our cull, then there is nothing to iterate over.
+ // Short-circuit everything.
+ valid = gridSpaceOccluderProsceniumInitialized;
+
+ if (valid && ! testCurrent()) {
+ next();
+ }
+}
+
+CulledOccluderSource::~CulledOccluderSource() {}
+
+bool CulledOccluderSource::testCurrent()
+{
+ if (valid) {
+ // The test for gridSpaceOccluderProsceniumInitialized should not be necessary
+ return gridSpaceOccluderProsceniumInitialized &&
+ GridHelpers::insideProscenium(gridSpaceOccluderProscenium, cachedPolygon);
+ }
+ return false;
+}
+
+bool CulledOccluderSource::next()
+{
+ while (OccluderSource::next()) {
+ if (testCurrent()) {
+ ++rejected;
+ return true;
+ }
+ }
+ if (G.debug & G_DEBUG_FREESTYLE) {
+ std::cout << "Finished generating occluders. Rejected " << rejected << " faces." << std::endl;
+ }
+ return false;
+}
+
+void CulledOccluderSource::getOccluderProscenium(real proscenium[4])
+{
+ for (unsigned int i = 0; i < 4; ++i) {
+ proscenium[i] = gridSpaceOccluderProscenium[i];
+ }
+}
+
+static inline real distance2D(const Vec3r & point, const real origin[2])
+{
+ return ::hypot((point[0] - origin[0]), (point[1] - origin[1]));
+}
+
+static inline bool crossesProscenium(real proscenium[4], FEdge *fe)
+{
+ Vec2r min(proscenium[0], proscenium[2]);
+ Vec2r max(proscenium[1], proscenium[3]);
+ Vec2r A(fe->vertexA()->getProjectedX(), fe->vertexA()->getProjectedY());
+ Vec2r B(fe->vertexB()->getProjectedX(), fe->vertexB()->getProjectedY());
+
+ return GeomUtils::intersect2dSeg2dArea (min, max, A, B);
+}
+
+static inline bool insideProscenium(real proscenium[4], const Vec3r& point)
+{
+ return !(point[0] < proscenium[0] || point[0] > proscenium[1] ||
+ point[1] < proscenium[2] || point[1] > proscenium[3]);
+}
+
+void CulledOccluderSource::cullViewEdges(ViewMap& viewMap, bool extensiveFEdgeSearch)
+{
+ // Cull view edges by marking them as non-displayable.
+ // This avoids the complications of trying to delete edges from the ViewMap.
+
+ // Non-displayable view edges will be skipped over during visibility calculation.
+
+ // View edges will be culled according to their position w.r.t. the viewport proscenium (viewport + 5% border,
+ // or some such).
+
+ // Get proscenium boundary for culling
+ real viewProscenium[4];
+ GridHelpers::getDefaultViewProscenium(viewProscenium);
+ real prosceniumOrigin[2];
+ prosceniumOrigin[0] = (viewProscenium[1] - viewProscenium[0]) / 2.0;
+ prosceniumOrigin[1] = (viewProscenium[3] - viewProscenium[2]) / 2.0;
+ if (G.debug & G_DEBUG_FREESTYLE) {
+ cout << "Proscenium culling:" << endl;
+ cout << "Proscenium: [" << viewProscenium[0] << ", " << viewProscenium[1] << ", " << viewProscenium[2]
+ << ", " << viewProscenium[3] << "]"<< endl;
+ cout << "Origin: [" << prosceniumOrigin[0] << ", " << prosceniumOrigin[1] << "]"<< endl;
+ }
+
+ // A separate occluder proscenium will also be maintained, starting out the same as the viewport proscenium, and
+ // expanding as necessary so that it encompasses the center point of at least one feature edge in each
+ // retained view edge.
+ // The occluder proscenium will be used later to cull occluding triangles before they are inserted into the Grid.
+ // The occluder proscenium starts out the same size as the view proscenium
+ GridHelpers::getDefaultViewProscenium(occluderProscenium);
+
+ // XXX Freestyle is inconsistent in its use of ViewMap::viewedges_container and vector<ViewEdge*>::iterator.
+ // Probably all occurences of vector<ViewEdge*>::iterator should be replaced ViewMap::viewedges_container
+ // throughout the code.
+ // For each view edge
+ ViewMap::viewedges_container::iterator ve, veend;
+
+ for (ve = viewMap.ViewEdges().begin(), veend = viewMap.ViewEdges().end(); ve != veend; ve++) {
+ // Overview:
+ // Search for a visible feature edge
+ // If none: mark view edge as non-displayable
+ // Otherwise:
+ // Find a feature edge with center point inside occluder proscenium.
+ // If none exists, find the feature edge with center point closest to viewport origin.
+ // Expand occluder proscenium to enclose center point.
+
+ // For each feature edge, while bestOccluderTarget not found and view edge not visibile
+ bool bestOccluderTargetFound = false;
+ FEdge *bestOccluderTarget = NULL;
+ real bestOccluderDistance = 0.0;
+ FEdge *festart = (*ve)->fedgeA();
+ FEdge *fe = festart;
+ // All ViewEdges start culled
+ (*ve)->setIsInImage(false);
+
+ // For simple visibility calculation: mark a feature edge that is known to have a center point inside
+ // the occluder proscenium. Cull all other feature edges.
+ do {
+ // All FEdges start culled
+ fe->setIsInImage(false);
+
+ // Look for the visible edge that can most easily be included in the occluder proscenium.
+ if (!bestOccluderTargetFound) {
+ // If center point is inside occluder proscenium,
+ if (insideProscenium(occluderProscenium, fe->center2d())) {
+ // Use this feature edge for visibility deterimination
+ fe->setIsInImage(true);
+ expandGridSpaceOccluderProscenium(fe);
+ // Mark bestOccluderTarget as found
+ bestOccluderTargetFound = true;
+ bestOccluderTarget = fe;
+ }
+ else {
+ real d = distance2D(fe->center2d(), prosceniumOrigin);
+ // If center point is closer to viewport origin than current target
+ if (bestOccluderTarget == NULL || d < bestOccluderDistance) {
+ // Then store as bestOccluderTarget
+ bestOccluderDistance = d;
+ bestOccluderTarget = fe;
+ }
+ }
+ }
+
+ // If feature edge crosses the view proscenium
+ if (!(*ve)->isInImage() && crossesProscenium(viewProscenium, fe)) {
+ // Then the view edge will be included in the image
+ (*ve)->setIsInImage(true);
+ }
+ fe = fe->nextEdge();
+ } while (fe != NULL && fe != festart && !(bestOccluderTargetFound && (*ve)->isInImage()));
+
+ // Either we have run out of FEdges, or we already have the one edge we need to determine visibility
+ // Cull all remaining edges.
+ while (fe != NULL && fe != festart) {
+ fe->setIsInImage(false);
+ fe = fe->nextEdge();
+ }
+
+ // If bestOccluderTarget was not found inside the occluder proscenium,
+ // we need to expand the occluder proscenium to include it.
+ if ((*ve)->isInImage() && bestOccluderTarget != NULL && ! bestOccluderTargetFound) {
+ // Expand occluder proscenium to enclose bestOccluderTarget
+ Vec3r point = bestOccluderTarget->center2d();
+ if (point[0] < occluderProscenium[0]) {
+ occluderProscenium[0] = point[0];
+ }
+ else if (point[0] > occluderProscenium[1]) {
+ occluderProscenium[1] = point[0];
+ }
+ if (point[1] < occluderProscenium[2]) {
+ occluderProscenium[2] = point[1];
+ }
+ else if (point[1] > occluderProscenium[3]) {
+ occluderProscenium[3] = point[1];
+ }
+ // Use bestOccluderTarget for visibility determination
+ bestOccluderTarget->setIsInImage(true);
+ }
+ }
+
+ // We are done calculating the occluder proscenium.
+ // Expand the occluder proscenium by an epsilon to avoid rounding errors.
+ const real epsilon = 1.0e-6;
+ occluderProscenium[0] -= epsilon;
+ occluderProscenium[1] += epsilon;
+ occluderProscenium[2] -= epsilon;
+ occluderProscenium[3] += epsilon;
+
+ // For "Normal" or "Fast" style visibility computation only:
+
+ // For more detailed visibility calculation, make a second pass through the view map, marking all feature edges
+ // with center points inside the final occluder proscenium. All of these feature edges can be considered during
+ // visibility calculation.
+
+ // So far we have only found one FEdge per ViewEdge. The "Normal" and "Fast" styles of visibility computation
+ // want to consider many FEdges for each ViewEdge.
+ // Here we re-scan the view map to find any usable FEdges that we skipped on the first pass, or that have become
+ // usable because the occluder proscenium has been expanded since the edge was visited on the first pass.
+ if (extensiveFEdgeSearch) {
+ // For each view edge,
+ for (ve = viewMap.ViewEdges().begin(), veend = viewMap.ViewEdges().end(); ve != veend; ve++) {
+ if (!(*ve)->isInImage()) {
+ continue;
+ }
+ // For each feature edge,
+ FEdge *festart = (*ve)->fedgeA();
+ FEdge *fe = festart;
+ do {
+ // If not (already) visible and center point inside occluder proscenium,
+ if (!fe->isInImage() && insideProscenium(occluderProscenium, fe->center2d())) {
+ // Use the feature edge for visibility determination
+ fe->setIsInImage(true);
+ expandGridSpaceOccluderProscenium(fe);
+ }
+ fe = fe->nextEdge();
+ } while (fe != NULL && fe != festart);
+ }
+ }
+
+ // Up until now, all calculations have been done in camera space.
+ // However, the occluder source's iteration and the grid that consumes the occluders both work in gridspace,
+ // so we need a version of the occluder proscenium in gridspace.
+ // Set the gridspace occlude proscenium
+}
+
+void CulledOccluderSource::expandGridSpaceOccluderProscenium(FEdge *fe)
+{
+ if (gridSpaceOccluderProsceniumInitialized) {
+ GridHelpers::expandProscenium(gridSpaceOccluderProscenium, transform(fe->center3d()));
+ }
+ else {
+ const Vec3r& point = transform(fe->center3d());
+ gridSpaceOccluderProscenium[0] = gridSpaceOccluderProscenium[1] = point[0];
+ gridSpaceOccluderProscenium[2] = gridSpaceOccluderProscenium[3] = point[1];
+ gridSpaceOccluderProsceniumInitialized = true;
+ }
+}

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b