diff options
Diffstat (limited to 'source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp')
| -rw-r--r-- | source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp | 422 |
1 files changed, 213 insertions, 209 deletions
diff --git a/source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp b/source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp index 28e4b0251de..214852001b6 100644 --- a/source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp +++ b/source/blender/freestyle/intern/view_map/CulledOccluderSource.cpp @@ -27,250 +27,254 @@ namespace Freestyle { -CulledOccluderSource::CulledOccluderSource(const GridHelpers::Transform& t, WingedEdge& we, ViewMap& viewMap, +CulledOccluderSource::CulledOccluderSource(const GridHelpers::Transform &t, + WingedEdge &we, + ViewMap &viewMap, bool extensiveFEdgeSearch) -: OccluderSource(t, we), rejected(0), gridSpaceOccluderProsceniumInitialized(false) + : OccluderSource(t, we), rejected(0), gridSpaceOccluderProsceniumInitialized(false) { - cullViewEdges(viewMap, extensiveFEdgeSearch); + 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 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(); - } + if (valid && !testCurrent()) { + next(); + } } -CulledOccluderSource::~CulledOccluderSource() {} +CulledOccluderSource::~CulledOccluderSource() +{ +} bool CulledOccluderSource::testCurrent() { - if (valid) { - // The test for gridSpaceOccluderProsceniumInitialized should not be necessary - return gridSpaceOccluderProsceniumInitialized && - GridHelpers::insideProscenium(gridSpaceOccluderProscenium, cachedPolygon); - } - return false; + 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; + 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]; - } + for (unsigned int i = 0; i < 4; ++i) { + proscenium[i] = gridSpaceOccluderProscenium[i]; + } } -static inline real distance2D(const Vec3r & point, const real origin[2]) +static inline real distance2D(const Vec3r &point, const real origin[2]) { - return ::hypot((point[0] - origin[0]), (point[1] - origin[1])); + 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()); + 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); + return GeomUtils::intersect2dSeg2dArea(min, max, A, B); } -static inline bool insideProscenium(real proscenium[4], const Vec3r& point) +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]); + return !(point[0] < proscenium[0] || point[0] > proscenium[1] || point[1] < proscenium[2] || + point[1] > proscenium[3]); } -void CulledOccluderSource::cullViewEdges(ViewMap& viewMap, bool extensiveFEdgeSearch) +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 + // 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; - } + 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; + } } } /* namespace Freestyle */ |