Fix for [#35482] 2.67 freestyle line visibility computation bug.

The reported line visibility issue was caused by a wrong calculation of a 2D
bounding box (so-called "proscenium face" in Freestyle) in the case of a
spherical grid data structure used for a perspective camera.  The problem was
resulting from the proscenium computation based on two corners (min and max)
of the 3D bounding box of imported mesh data.  Aware of the spherical coordinate
transformation involving non-linear (arctangent) functions, now the proscenium
is computed by taking in account all the eight corners of the 3D bounding box.

Also added minor code changes to facilitate future debugging.

7 files changed, 39 insertions, 23 deletions

diff --git a/source/blender/freestyle/intern/view_map/ArbitraryGridDensityProvider.cpp b/source/blender/freestyle/intern/view_map/ArbitraryGridDensityProvider.cpp
index ed9932c3eef..8bc7c0952a8 100644
--- a/source/blender/freestyle/intern/view_map/ArbitraryGridDensityProvider.cpp
+++ b/source/blender/freestyle/intern/view_map/ArbitraryGridDensityProvider.cpp
@@ -79,10 +79,10 @@ void ArbitraryGridDensityProvider::initialize(const real proscenium[4])
 	// Make sure the grid exceeds the proscenium by a small amount
 	float safetyZone = 0.1f;
 	if (_cellsX * _cellSize < prosceniumWidth * (1.0 + safetyZone)) {
-		_cellsX = prosceniumWidth * (1.0 + safetyZone) / _cellSize;
+		_cellsX = ceil(prosceniumWidth * (1.0 + safetyZone) / _cellSize);
 	}
 	if (_cellsY * _cellSize < prosceniumHeight * (1.0 + safetyZone)) {
-		_cellsY = prosceniumHeight * (1.0 + safetyZone) / _cellSize;
+		_cellsY = ceil(prosceniumHeight * (1.0 + safetyZone) / _cellSize);
 	}
 	if (G.debug & G_DEBUG_FREESTYLE) {
 		cout << _cellsX << "x" << _cellsY << " cells of size " << _cellSize << " square." << endl;
diff --git a/source/blender/freestyle/intern/view_map/AverageAreaGridDensityProvider.cpp b/source/blender/freestyle/intern/view_map/AverageAreaGridDensityProvider.cpp
index 61ad78a8567..952b9752a3e 100644
--- a/source/blender/freestyle/intern/view_map/AverageAreaGridDensityProvider.cpp
+++ b/source/blender/freestyle/intern/view_map/AverageAreaGridDensityProvider.cpp
@@ -100,10 +100,10 @@ void AverageAreaGridDensityProvider::initialize(const real proscenium[4], real s
 	// Make sure the grid exceeds the proscenium by a small amount
 	float safetyZone = 0.1f;
 	if (_cellsX * _cellSize < prosceniumWidth * (1.0 + safetyZone)) {
-		_cellsX = prosceniumWidth * (1.0 + safetyZone) / _cellSize;
+		_cellsX = ceil(prosceniumWidth * (1.0 + safetyZone) / _cellSize);
 	}
 	if (_cellsY * _cellSize < prosceniumHeight * (1.0 + safetyZone)) {
-		_cellsY = prosceniumHeight * (1.0 + safetyZone) / _cellSize;
+		_cellsY = ceil(prosceniumHeight * (1.0 + safetyZone) / _cellSize);
 	}
 	if (G.debug & G_DEBUG_FREESTYLE) {
 		cout << _cellsX << "x" << _cellsY << " cells of size " << _cellSize << " square." << endl;
diff --git a/source/blender/freestyle/intern/view_map/BoxGrid.cpp b/source/blender/freestyle/intern/view_map/BoxGrid.cpp
index 2e702813fb8..f770bf6843f 100644
--- a/source/blender/freestyle/intern/view_map/BoxGrid.cpp
+++ b/source/blender/freestyle/intern/view_map/BoxGrid.cpp
@@ -129,6 +129,10 @@ void BoxGrid::assignCells (OccluderSource& source, GridDensityProvider& density,
 	_cellsY = density.cellsY();
 	_cellOrigin[0] = density.cellOrigin(0);
 	_cellOrigin[1] = density.cellOrigin(1);
+	if (G.debug & G_DEBUG_FREESTYLE) {
+		cout << "Using " << _cellsX << "x" << _cellsY << " cells of size " << _cellSize << " square." << endl;
+		cout << "Cell origin: " << _cellOrigin[0] << ", " << _cellOrigin[1] << endl;
+	}
 
 	// Now allocate the cell table and fill it with default (empty) cells
 	_cells.resize(_cellsX * _cellsY);
diff --git a/source/blender/freestyle/intern/view_map/GridDensityProvider.h b/source/blender/freestyle/intern/view_map/GridDensityProvider.h
index d096fb3aacd..fe14efbe20f 100644
--- a/source/blender/freestyle/intern/view_map/GridDensityProvider.h
+++ b/source/blender/freestyle/intern/view_map/GridDensityProvider.h
@@ -100,24 +100,29 @@ public:
 	static void calculateQuickProscenium(const GridHelpers::Transform& transform, const BBox<Vec3r>& bbox,
 	                                     real proscenium[4])
 	{
-		real z;
-		// We want to use the z-coordinate closest to the camera to determine the proscenium face
-		if (::fabs(bbox.getMin()[2]) < ::fabs(bbox.getMax()[2])) {
-			z = bbox.getMin()[2];
-		}
-		else {
-			z = bbox.getMax()[2];
-		}
-		// Now calculate the proscenium according to the min and max values of the x and y coordinates
-		Vec3r minPoint = transform(Vec3r(bbox.getMin()[0], bbox.getMin()[1], z));
-		Vec3r maxPoint = transform(Vec3r(bbox.getMax()[0], bbox.getMax()[1], z));
-		proscenium[0] = std::min(minPoint[0], maxPoint[0]);
-		proscenium[1] = std::max(minPoint[0], maxPoint[0]);
-		proscenium[2] = std::min(minPoint[1], maxPoint[1]);
-		proscenium[3] = std::max(minPoint[1], maxPoint[1]);
+		// Transform the coordinates of the 8 corners of the 3D bounding box
+		real xm = bbox.getMin()[0], xM = bbox.getMax()[0];
+		real ym = bbox.getMin()[1], yM = bbox.getMax()[1];
+		real zm = bbox.getMin()[2], zM = bbox.getMax()[2];
+		Vec3r p1 = transform(Vec3r(xm, ym, zm));
+		Vec3r p2 = transform(Vec3r(xm, ym, zM));
+		Vec3r p3 = transform(Vec3r(xm, yM, zm));
+		Vec3r p4 = transform(Vec3r(xm, yM, zM));
+		Vec3r p5 = transform(Vec3r(xM, ym, zm));
+		Vec3r p6 = transform(Vec3r(xM, ym, zM));
+		Vec3r p7 = transform(Vec3r(xM, yM, zm));
+		Vec3r p8 = transform(Vec3r(xM, yM, zM));
+		// Determine the proscenium face according to the min and max values of the transformed x and y coordinates
+		proscenium[0] = std::min(std::min(std::min(p1.x(), p2.x()), std::min(p3.x(), p4.x())),
+		                         std::min(std::min(p5.x(), p6.x()), std::min(p7.x(), p8.x())));
+		proscenium[1] = std::max(std::max(std::max(p1.x(), p2.x()), std::max(p3.x(), p4.x())),
+		                         std::max(std::max(p5.x(), p6.x()), std::max(p7.x(), p8.x())));
+		proscenium[2] = std::min(std::min(std::min(p1.y(), p2.y()), std::min(p3.y(), p4.y())),
+		                         std::min(std::min(p5.y(), p6.y()), std::min(p7.y(), p8.y())));
+		proscenium[3] = std::max(std::max(std::max(p1.y(), p2.y()), std::max(p3.y(), p4.y())),
+		                         std::max(std::max(p5.y(), p6.y()), std::max(p7.y(), p8.y())));
 		if (G.debug & G_DEBUG_FREESTYLE) {
-			cout << "Bounding box: " << minPoint << " to " << maxPoint << endl;
-			cout << "Proscenium  : " << proscenium[0] << ", " << proscenium[1] << ", " << proscenium[2] << ", " <<
+			cout << "Proscenium: " << proscenium[0] << ", " << proscenium[1] << ", " << proscenium[2] << ", " <<
 			        proscenium[3] << endl;
 		}
 	}
diff --git a/source/blender/freestyle/intern/view_map/Pow23GridDensityProvider.cpp b/source/blender/freestyle/intern/view_map/Pow23GridDensityProvider.cpp
index 40a3c9f298d..e3bb9b87ecc 100644
--- a/source/blender/freestyle/intern/view_map/Pow23GridDensityProvider.cpp
+++ b/source/blender/freestyle/intern/view_map/Pow23GridDensityProvider.cpp
@@ -78,10 +78,10 @@ void Pow23GridDensityProvider::initialize(const real proscenium[4])
 	// Make sure the grid exceeds the proscenium by a small amount
 	float safetyZone = 0.1;
 	if (_cellsX * _cellSize < prosceniumWidth * (1.0 + safetyZone)) {
-		_cellsX = prosceniumWidth * (1.0 + safetyZone) / _cellSize;
+		_cellsX = ceil(prosceniumWidth * (1.0 + safetyZone) / _cellSize);
 	}
 	if (_cellsY * _cellSize < prosceniumHeight * (1.0 + safetyZone)) {
-		_cellsY = prosceniumHeight * (1.0 + safetyZone) / _cellSize;
+		_cellsY = ceil(prosceniumHeight * (1.0 + safetyZone) / _cellSize);
 	}
 	if (G.debug & G_DEBUG_FREESTYLE) {
 		cout << _cellsX << "x" << _cellsY << " cells of size " << _cellSize << " square." << endl;
diff --git a/source/blender/freestyle/intern/view_map/SphericalGrid.cpp b/source/blender/freestyle/intern/view_map/SphericalGrid.cpp
index 1621bd85000..60ad7daea0a 100644
--- a/source/blender/freestyle/intern/view_map/SphericalGrid.cpp
+++ b/source/blender/freestyle/intern/view_map/SphericalGrid.cpp
@@ -127,6 +127,10 @@ void SphericalGrid::assignCells(OccluderSource& source, GridDensityProvider& den
 	_cellsY = density.cellsY();
 	_cellOrigin[0] = density.cellOrigin(0);
 	_cellOrigin[1] = density.cellOrigin(1);
+	if (G.debug & G_DEBUG_FREESTYLE) {
+		cout << "Using " << _cellsX << "x" << _cellsY << " cells of size " << _cellSize << " square." << endl;
+		cout << "Cell origin: " << _cellOrigin[0] << ", " << _cellOrigin[1] << endl;
+	}
 
 	// Now allocate the cell table and fill it with default (empty) cells
 	_cells.resize(_cellsX * _cellsY);
diff --git a/source/blender/freestyle/intern/view_map/ViewMapBuilder.cpp b/source/blender/freestyle/intern/view_map/ViewMapBuilder.cpp
index 20b0f6576bb..81b0f5f8934 100644
--- a/source/blender/freestyle/intern/view_map/ViewMapBuilder.cpp
+++ b/source/blender/freestyle/intern/view_map/ViewMapBuilder.cpp
@@ -1364,6 +1364,9 @@ void ViewMapBuilder::ComputeDetailedVisibility(ViewMap *ioViewMap, WingedEdge& w
 void ViewMapBuilder::ComputeEdgesVisibility(ViewMap *ioViewMap, WingedEdge& we, const BBox<Vec3r>& bbox,
                                             unsigned int sceneNumFaces, visibility_algo iAlgo, real epsilon)
 {
+#if 0
+	iAlgo = ray_casting; // for testing algorithms equivalence
+#endif
 	switch (iAlgo) {
 		case ray_casting:
 			if (_global.debug & G_DEBUG_FREESTYLE) {