diff options
Diffstat (limited to 'source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp')
| -rw-r--r-- | source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp | 277 |
1 files changed, 277 insertions, 0 deletions
diff --git a/source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp b/source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp new file mode 100644 index 00000000000..ea57da93347 --- /dev/null +++ b/source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp @@ -0,0 +1,277 @@ +// +// Filename : CulledOccluderSource.h +// Author(s) : Alexander Beels +// Purpose : Class to define a cell grid surrounding +// the projected image of a scene +// Date of creation : 2010-12-21 +// +/////////////////////////////////////////////////////////////////////////////// + + +// +// Copyright (C) : Please refer to the COPYRIGHT file distributed +// with this source distribution. +// +// 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +// +/////////////////////////////////////////////////////////////////////////////// + +#include "CulledOccluderSource.h" +#include "../geometry/GridHelpers.h" +#include "FRS_freestyle.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; + } + } + std::cout << "Finished generating occluders. Rejected " << rejected << " faces." << std::endl; + return false; +} + +void CulledOccluderSource::getOccluderProscenium(real proscenium[4]) { + for ( unsigned 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; + 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); + + // N.B. 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; + } +} + |