/*-------------------------------------------------------------------------
 * drawElements Quality Program Tester Core
 * ----------------------------------------
 *
 * Copyright 2014 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 *//*!
 * \file
 * \brief Rasterization verifier utils.
 *//*--------------------------------------------------------------------*/

#include "tcuRasterizationVerifier.hpp"
#include "tcuVector.hpp"
#include "tcuSurface.hpp"
#include "tcuTestLog.hpp"
#include "tcuTextureUtil.hpp"
#include "tcuVectorUtil.hpp"
#include "tcuFloat.hpp"
#include "deMath.h"

#include "rrRasterizer.hpp"

#include <limits>

namespace tcu
{
namespace
{

bool lineLineIntersect (const tcu::Vector<deInt64, 2>& line0Beg, const tcu::Vector<deInt64, 2>& line0End, const tcu::Vector<deInt64, 2>& line1Beg, const tcu::Vector<deInt64, 2>& line1End)
{
	typedef tcu::Vector<deInt64, 2> I64Vec2;

	// Lines do not intersect if the other line's endpoints are on the same side
	// otherwise, the do intersect

	// Test line 0
	{
		const I64Vec2 line			= line0End - line0Beg;
		const I64Vec2 v0			= line1Beg - line0Beg;
		const I64Vec2 v1			= line1End - line0Beg;
		const deInt64 crossProduct0	= (line.x() * v0.y() - line.y() * v0.x());
		const deInt64 crossProduct1	= (line.x() * v1.y() - line.y() * v1.x());

		// check signs
		if ((crossProduct0 < 0 && crossProduct1 < 0) ||
			(crossProduct0 > 0 && crossProduct1 > 0))
			return false;
	}

	// Test line 1
	{
		const I64Vec2 line			= line1End - line1Beg;
		const I64Vec2 v0			= line0Beg - line1Beg;
		const I64Vec2 v1			= line0End - line1Beg;
		const deInt64 crossProduct0	= (line.x() * v0.y() - line.y() * v0.x());
		const deInt64 crossProduct1	= (line.x() * v1.y() - line.y() * v1.x());

		// check signs
		if ((crossProduct0 < 0 && crossProduct1 < 0) ||
			(crossProduct0 > 0 && crossProduct1 > 0))
			return false;
	}

	return true;
}

bool isTriangleClockwise (const tcu::Vec4& p0, const tcu::Vec4& p1, const tcu::Vec4& p2)
{
	const tcu::Vec2	u				(p1.x() / p1.w() - p0.x() / p0.w(), p1.y() / p1.w() - p0.y() / p0.w());
	const tcu::Vec2	v				(p2.x() / p2.w() - p0.x() / p0.w(), p2.y() / p2.w() - p0.y() / p0.w());
	const float		crossProduct	= (u.x() * v.y() - u.y() * v.x());

	return crossProduct > 0.0f;
}

bool compareColors (const tcu::RGBA& colorA, const tcu::RGBA& colorB, int redBits, int greenBits, int blueBits)
{
	const int thresholdRed		= 1 << (8 - redBits);
	const int thresholdGreen	= 1 << (8 - greenBits);
	const int thresholdBlue		= 1 << (8 - blueBits);

	return	deAbs32(colorA.getRed()   - colorB.getRed())   <= thresholdRed   &&
			deAbs32(colorA.getGreen() - colorB.getGreen()) <= thresholdGreen &&
			deAbs32(colorA.getBlue()  - colorB.getBlue())  <= thresholdBlue;
}

bool pixelNearLineSegment (const tcu::IVec2& pixel, const tcu::Vec2& p0, const tcu::Vec2& p1)
{
	const tcu::Vec2 pixelCenterPosition = tcu::Vec2((float)pixel.x() + 0.5f, (float)pixel.y() + 0.5f);

	// "Near" = Distance from the line to the pixel is less than 2 * pixel_max_radius. (pixel_max_radius = sqrt(2) / 2)
	const float maxPixelDistance		= 1.414f;
	const float maxPixelDistanceSquared	= 2.0f;

	// Near the line
	{
		const tcu::Vec2	line			= p1                  - p0;
		const tcu::Vec2	v				= pixelCenterPosition - p0;
		const float		crossProduct	= (line.x() * v.y() - line.y() * v.x());

		// distance to line: (line x v) / |line|
		//     |(line x v) / |line|| > maxPixelDistance
		// ==> (line x v)^2 / |line|^2 > maxPixelDistance^2
		// ==> (line x v)^2 > maxPixelDistance^2 * |line|^2

		if (crossProduct * crossProduct > maxPixelDistanceSquared * tcu::lengthSquared(line))
			return false;
	}

	// Between the endpoints
	{
		// distance from line endpoint 1 to pixel is less than line length + maxPixelDistance
		const float maxDistance = tcu::length(p1 - p0) + maxPixelDistance;

		if (tcu::length(pixelCenterPosition - p0) > maxDistance)
			return false;
		if (tcu::length(pixelCenterPosition - p1) > maxDistance)
			return false;
	}

	return true;
}

bool pixelOnlyOnASharedEdge (const tcu::IVec2& pixel, const TriangleSceneSpec::SceneTriangle& triangle, const tcu::IVec2& viewportSize)
{
	if (triangle.sharedEdge[0] || triangle.sharedEdge[1] || triangle.sharedEdge[2])
	{
		const tcu::Vec2 triangleNormalizedDeviceSpace[3] =
		{
			tcu::Vec2(triangle.positions[0].x() / triangle.positions[0].w(), triangle.positions[0].y() / triangle.positions[0].w()),
			tcu::Vec2(triangle.positions[1].x() / triangle.positions[1].w(), triangle.positions[1].y() / triangle.positions[1].w()),
			tcu::Vec2(triangle.positions[2].x() / triangle.positions[2].w(), triangle.positions[2].y() / triangle.positions[2].w()),
		};
		const tcu::Vec2 triangleScreenSpace[3] =
		{
			(triangleNormalizedDeviceSpace[0] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * tcu::Vec2((float)viewportSize.x(), (float)viewportSize.y()),
			(triangleNormalizedDeviceSpace[1] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * tcu::Vec2((float)viewportSize.x(), (float)viewportSize.y()),
			(triangleNormalizedDeviceSpace[2] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * tcu::Vec2((float)viewportSize.x(), (float)viewportSize.y()),
		};

		const bool pixelOnEdge0 = pixelNearLineSegment(pixel, triangleScreenSpace[0], triangleScreenSpace[1]);
		const bool pixelOnEdge1 = pixelNearLineSegment(pixel, triangleScreenSpace[1], triangleScreenSpace[2]);
		const bool pixelOnEdge2 = pixelNearLineSegment(pixel, triangleScreenSpace[2], triangleScreenSpace[0]);

		// If the pixel is on a multiple edges return false

		if (pixelOnEdge0 && !pixelOnEdge1 && !pixelOnEdge2)
			return triangle.sharedEdge[0];
		if (!pixelOnEdge0 && pixelOnEdge1 && !pixelOnEdge2)
			return triangle.sharedEdge[1];
		if (!pixelOnEdge0 && !pixelOnEdge1 && pixelOnEdge2)
			return triangle.sharedEdge[2];
	}

	return false;
}

float triangleArea (const tcu::Vec2& s0, const tcu::Vec2& s1, const tcu::Vec2& s2)
{
	const tcu::Vec2	u				(s1.x() - s0.x(), s1.y() - s0.y());
	const tcu::Vec2	v				(s2.x() - s0.x(), s2.y() - s0.y());
	const float		crossProduct	= (u.x() * v.y() - u.y() * v.x());

	return crossProduct / 2.0f;
}

tcu::IVec4 getTriangleAABB (const TriangleSceneSpec::SceneTriangle& triangle, const tcu::IVec2& viewportSize)
{
	const tcu::Vec2 normalizedDeviceSpace[3] =
	{
		tcu::Vec2(triangle.positions[0].x() / triangle.positions[0].w(), triangle.positions[0].y() / triangle.positions[0].w()),
		tcu::Vec2(triangle.positions[1].x() / triangle.positions[1].w(), triangle.positions[1].y() / triangle.positions[1].w()),
		tcu::Vec2(triangle.positions[2].x() / triangle.positions[2].w(), triangle.positions[2].y() / triangle.positions[2].w()),
	};
	const tcu::Vec2 screenSpace[3] =
	{
		(normalizedDeviceSpace[0] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * tcu::Vec2((float)viewportSize.x(), (float)viewportSize.y()),
		(normalizedDeviceSpace[1] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * tcu::Vec2((float)viewportSize.x(), (float)viewportSize.y()),
		(normalizedDeviceSpace[2] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * tcu::Vec2((float)viewportSize.x(), (float)viewportSize.y()),
	};

	tcu::IVec4 aabb;

	aabb.x() = (int)deFloatFloor(de::min(de::min(screenSpace[0].x(), screenSpace[1].x()), screenSpace[2].x()));
	aabb.y() = (int)deFloatFloor(de::min(de::min(screenSpace[0].y(), screenSpace[1].y()), screenSpace[2].y()));
	aabb.z() = (int)deFloatCeil (de::max(de::max(screenSpace[0].x(), screenSpace[1].x()), screenSpace[2].x()));
	aabb.w() = (int)deFloatCeil (de::max(de::max(screenSpace[0].y(), screenSpace[1].y()), screenSpace[2].y()));

	return aabb;
}

float getExponentEpsilonFromULP (int valueExponent, deUint32 ulp)
{
	DE_ASSERT(ulp < (1u<<10));

	// assume mediump precision, using ulp as ulps in a 10 bit mantissa
	return tcu::Float32::construct(+1, valueExponent, (1u<<23) + (ulp << (23 - 10))).asFloat() - tcu::Float32::construct(+1, valueExponent, (1u<<23)).asFloat();
}

float getValueEpsilonFromULP (float value, deUint32 ulp)
{
	DE_ASSERT(value != std::numeric_limits<float>::infinity() && value != -std::numeric_limits<float>::infinity());

	const int exponent = tcu::Float32(value).exponent();
	return getExponentEpsilonFromULP(exponent, ulp);
}

float getMaxValueWithinError (float value, deUint32 ulp)
{
	if (value == std::numeric_limits<float>::infinity() || value == -std::numeric_limits<float>::infinity())
		return value;

	return value + getValueEpsilonFromULP(value, ulp);
}

float getMinValueWithinError (float value, deUint32 ulp)
{
	if (value == std::numeric_limits<float>::infinity() || value == -std::numeric_limits<float>::infinity())
		return value;

	return value - getValueEpsilonFromULP(value, ulp);
}

float getMinFlushToZero (float value)
{
	// flush to zero if that decreases the value
	// assume mediump precision
	if (value > 0.0f && value < tcu::Float32::construct(+1, -14, 1u<<23).asFloat())
		return 0.0f;
	return value;
}

float getMaxFlushToZero (float value)
{
	// flush to zero if that increases the value
	// assume mediump precision
	if (value < 0.0f && value > tcu::Float32::construct(-1, -14, 1u<<23).asFloat())
		return 0.0f;
	return value;
}

tcu::IVec3 convertRGB8ToNativeFormat (const tcu::RGBA& color, const RasterizationArguments& args)
{
	tcu::IVec3 pixelNativeColor;

	for (int channelNdx = 0; channelNdx < 3; ++channelNdx)
	{
		const int channelBitCount	= (channelNdx == 0) ? (args.redBits) : (channelNdx == 1) ? (args.greenBits) : (args.blueBits);
		const int channelPixelValue	= (channelNdx == 0) ? (color.getRed()) : (channelNdx == 1) ? (color.getGreen()) : (color.getBlue());

		if (channelBitCount <= 8)
			pixelNativeColor[channelNdx] = channelPixelValue >> (8 - channelBitCount);
		else if (channelBitCount == 8)
			pixelNativeColor[channelNdx] = channelPixelValue;
		else
		{
			// just in case someone comes up with 8+ bits framebuffers pixel formats. But as
			// we can only read in rgba8, we have to guess the trailing bits. Guessing 0.
			pixelNativeColor[channelNdx] = channelPixelValue << (channelBitCount - 8);
		}
	}

	return pixelNativeColor;
}

/*--------------------------------------------------------------------*//*!
 * Returns the maximum value of x / y, where x c [minDividend, maxDividend]
 * and y c [minDivisor, maxDivisor]
 *//*--------------------------------------------------------------------*/
float maximalRangeDivision (float minDividend, float maxDividend, float minDivisor, float maxDivisor)
{
	DE_ASSERT(minDividend <= maxDividend);
	DE_ASSERT(minDivisor <= maxDivisor);

	// special cases
	if (minDividend == 0.0f && maxDividend == 0.0f)
		return 0.0f;
	if (minDivisor <= 0.0f && maxDivisor >= 0.0f)
		return std::numeric_limits<float>::infinity();

	return de::max(de::max(minDividend / minDivisor, minDividend / maxDivisor), de::max(maxDividend / minDivisor, maxDividend / maxDivisor));
}

/*--------------------------------------------------------------------*//*!
 * Returns the minimum value of x / y, where x c [minDividend, maxDividend]
 * and y c [minDivisor, maxDivisor]
 *//*--------------------------------------------------------------------*/
float minimalRangeDivision (float minDividend, float maxDividend, float minDivisor, float maxDivisor)
{
	DE_ASSERT(minDividend <= maxDividend);
	DE_ASSERT(minDivisor <= maxDivisor);

	// special cases
	if (minDividend == 0.0f && maxDividend == 0.0f)
		return 0.0f;
	if (minDivisor <= 0.0f && maxDivisor >= 0.0f)
		return -std::numeric_limits<float>::infinity();

	return de::min(de::min(minDividend / minDivisor, minDividend / maxDivisor), de::min(maxDividend / minDivisor, maxDividend / maxDivisor));
}

static bool isLineXMajor (const tcu::Vec2& lineScreenSpaceP0, const tcu::Vec2& lineScreenSpaceP1)
{
	return de::abs(lineScreenSpaceP1.x() - lineScreenSpaceP0.x()) >= de::abs(lineScreenSpaceP1.y() - lineScreenSpaceP0.y());
}

static bool isPackedSSLineXMajor (const tcu::Vec4& packedLine)
{
	const tcu::Vec2 lineScreenSpaceP0 = packedLine.swizzle(0, 1);
	const tcu::Vec2 lineScreenSpaceP1 = packedLine.swizzle(2, 3);

	return isLineXMajor(lineScreenSpaceP0, lineScreenSpaceP1);
}

struct InterpolationRange
{
	tcu::Vec3 max;
	tcu::Vec3 min;
};

struct LineInterpolationRange
{
	tcu::Vec2 max;
	tcu::Vec2 min;
};

InterpolationRange calcTriangleInterpolationWeights (const tcu::Vec4& p0, const tcu::Vec4& p1, const tcu::Vec4& p2, const tcu::Vec2& ndpixel)
{
	const int roundError		= 1;
	const int barycentricError	= 3;
	const int divError			= 8;

	const tcu::Vec2 nd0 = p0.swizzle(0, 1) / p0.w();
	const tcu::Vec2 nd1 = p1.swizzle(0, 1) / p1.w();
	const tcu::Vec2 nd2 = p2.swizzle(0, 1) / p2.w();

	const float ka = triangleArea(ndpixel, nd1, nd2);
	const float kb = triangleArea(ndpixel, nd2, nd0);
	const float kc = triangleArea(ndpixel, nd0, nd1);

	const float kaMax = getMaxFlushToZero(getMaxValueWithinError(ka, barycentricError));
	const float kbMax = getMaxFlushToZero(getMaxValueWithinError(kb, barycentricError));
	const float kcMax = getMaxFlushToZero(getMaxValueWithinError(kc, barycentricError));
	const float kaMin = getMinFlushToZero(getMinValueWithinError(ka, barycentricError));
	const float kbMin = getMinFlushToZero(getMinValueWithinError(kb, barycentricError));
	const float kcMin = getMinFlushToZero(getMinValueWithinError(kc, barycentricError));
	DE_ASSERT(kaMin <= kaMax);
	DE_ASSERT(kbMin <= kbMax);
	DE_ASSERT(kcMin <= kcMax);

	// calculate weights: vec3(ka / p0.w, kb / p1.w, kc / p2.w) / (ka / p0.w + kb / p1.w + kc / p2.w)
	const float maxPreDivisionValues[3] =
	{
		getMaxFlushToZero(getMaxValueWithinError(getMaxFlushToZero(kaMax / p0.w()), divError)),
		getMaxFlushToZero(getMaxValueWithinError(getMaxFlushToZero(kbMax / p1.w()), divError)),
		getMaxFlushToZero(getMaxValueWithinError(getMaxFlushToZero(kcMax / p2.w()), divError)),
	};
	const float minPreDivisionValues[3] =
	{
		getMinFlushToZero(getMinValueWithinError(getMinFlushToZero(kaMin / p0.w()), divError)),
		getMinFlushToZero(getMinValueWithinError(getMinFlushToZero(kbMin / p1.w()), divError)),
		getMinFlushToZero(getMinValueWithinError(getMinFlushToZero(kcMin / p2.w()), divError)),
	};
	DE_ASSERT(minPreDivisionValues[0] <= maxPreDivisionValues[0]);
	DE_ASSERT(minPreDivisionValues[1] <= maxPreDivisionValues[1]);
	DE_ASSERT(minPreDivisionValues[2] <= maxPreDivisionValues[2]);

	const float maxDivisor = getMaxFlushToZero(getMaxValueWithinError(maxPreDivisionValues[0] + maxPreDivisionValues[1] + maxPreDivisionValues[2], 2*roundError));
	const float minDivisor = getMinFlushToZero(getMinValueWithinError(minPreDivisionValues[0] + minPreDivisionValues[1] + minPreDivisionValues[2], 2*roundError));
	DE_ASSERT(minDivisor <= maxDivisor);

	InterpolationRange returnValue;

	returnValue.max.x() = getMaxFlushToZero(getMaxValueWithinError(getMaxFlushToZero(maximalRangeDivision(minPreDivisionValues[0], maxPreDivisionValues[0], minDivisor, maxDivisor)), divError));
	returnValue.max.y() = getMaxFlushToZero(getMaxValueWithinError(getMaxFlushToZero(maximalRangeDivision(minPreDivisionValues[1], maxPreDivisionValues[1], minDivisor, maxDivisor)), divError));
	returnValue.max.z() = getMaxFlushToZero(getMaxValueWithinError(getMaxFlushToZero(maximalRangeDivision(minPreDivisionValues[2], maxPreDivisionValues[2], minDivisor, maxDivisor)), divError));
	returnValue.min.x() = getMinFlushToZero(getMinValueWithinError(getMinFlushToZero(minimalRangeDivision(minPreDivisionValues[0], maxPreDivisionValues[0], minDivisor, maxDivisor)), divError));
	returnValue.min.y() = getMinFlushToZero(getMinValueWithinError(getMinFlushToZero(minimalRangeDivision(minPreDivisionValues[1], maxPreDivisionValues[1], minDivisor, maxDivisor)), divError));
	returnValue.min.z() = getMinFlushToZero(getMinValueWithinError(getMinFlushToZero(minimalRangeDivision(minPreDivisionValues[2], maxPreDivisionValues[2], minDivisor, maxDivisor)), divError));

	DE_ASSERT(returnValue.min.x() <= returnValue.max.x());
	DE_ASSERT(returnValue.min.y() <= returnValue.max.y());
	DE_ASSERT(returnValue.min.z() <= returnValue.max.z());

	return returnValue;
}

LineInterpolationRange calcLineInterpolationWeights (const tcu::Vec2& pa, float wa, const tcu::Vec2& pb, float wb, const tcu::Vec2& pr)
{
	const int roundError	= 1;
	const int divError		= 3;

	// calc weights:
	//			(1-t) / wa					t / wb
	//		-------------------	,	-------------------
	//		(1-t) / wa + t / wb		(1-t) / wa + t / wb

	// Allow 1 ULP
	const float		dividend	= tcu::dot(pr - pa, pb - pa);
	const float		dividendMax	= getMaxValueWithinError(dividend, 1);
	const float		dividendMin	= getMinValueWithinError(dividend, 1);
	DE_ASSERT(dividendMin <= dividendMax);

	// Assuming lengthSquared will not be implemented as sqrt(x)^2, allow 1 ULP
	const float		divisor		= tcu::lengthSquared(pb - pa);
	const float		divisorMax	= getMaxValueWithinError(divisor, 1);
	const float		divisorMin	= getMinValueWithinError(divisor, 1);
	DE_ASSERT(divisorMin <= divisorMax);

	// Allow 3 ULP precision for division
	const float		tMax		= getMaxValueWithinError(maximalRangeDivision(dividendMin, dividendMax, divisorMin, divisorMax), divError);
	const float		tMin		= getMinValueWithinError(minimalRangeDivision(dividendMin, dividendMax, divisorMin, divisorMax), divError);
	DE_ASSERT(tMin <= tMax);

	const float		perspectiveTMax			= getMaxValueWithinError(maximalRangeDivision(tMin, tMax, wb, wb), divError);
	const float		perspectiveTMin			= getMinValueWithinError(minimalRangeDivision(tMin, tMax, wb, wb), divError);
	DE_ASSERT(perspectiveTMin <= perspectiveTMax);

	const float		perspectiveInvTMax		= getMaxValueWithinError(maximalRangeDivision((1.0f - tMax), (1.0f - tMin), wa, wa), divError);
	const float		perspectiveInvTMin		= getMinValueWithinError(minimalRangeDivision((1.0f - tMax), (1.0f - tMin), wa, wa), divError);
	DE_ASSERT(perspectiveInvTMin <= perspectiveInvTMax);

	const float		perspectiveDivisorMax	= getMaxValueWithinError(perspectiveTMax + perspectiveInvTMax, roundError);
	const float		perspectiveDivisorMin	= getMinValueWithinError(perspectiveTMin + perspectiveInvTMin, roundError);
	DE_ASSERT(perspectiveDivisorMin <= perspectiveDivisorMax);

	LineInterpolationRange returnValue;
	returnValue.max.x() = getMaxValueWithinError(maximalRangeDivision(perspectiveInvTMin,	perspectiveInvTMax,	perspectiveDivisorMin, perspectiveDivisorMax), divError);
	returnValue.max.y() = getMaxValueWithinError(maximalRangeDivision(perspectiveTMin,		perspectiveTMax,	perspectiveDivisorMin, perspectiveDivisorMax), divError);
	returnValue.min.x() = getMinValueWithinError(minimalRangeDivision(perspectiveInvTMin,	perspectiveInvTMax,	perspectiveDivisorMin, perspectiveDivisorMax), divError);
	returnValue.min.y() = getMinValueWithinError(minimalRangeDivision(perspectiveTMin,		perspectiveTMax,	perspectiveDivisorMin, perspectiveDivisorMax), divError);

	DE_ASSERT(returnValue.min.x() <= returnValue.max.x());
	DE_ASSERT(returnValue.min.y() <= returnValue.max.y());

	return returnValue;
}

LineInterpolationRange calcLineInterpolationWeightsAxisProjected (const tcu::Vec2& pa, float wa, const tcu::Vec2& pb, float wb, const tcu::Vec2& pr)
{
	const int	roundError		= 1;
	const int	divError		= 3;
	const bool	isXMajor		= isLineXMajor(pa, pb);
	const int	majorAxisNdx	= (isXMajor) ? (0) : (1);

	// calc weights:
	//			(1-t) / wa					t / wb
	//		-------------------	,	-------------------
	//		(1-t) / wa + t / wb		(1-t) / wa + t / wb

	// Use axis projected (inaccurate) method, i.e. for X-major lines:
	//     (xd - xa) * (xb - xa)      xd - xa
	// t = ---------------------  ==  -------
	//       ( xb - xa ) ^ 2          xb - xa

	// Allow 1 ULP
	const float		dividend	= (pr[majorAxisNdx] - pa[majorAxisNdx]);
	const float		dividendMax	= getMaxValueWithinError(dividend, 1);
	const float		dividendMin	= getMinValueWithinError(dividend, 1);
	DE_ASSERT(dividendMin <= dividendMax);

	// Allow 1 ULP
	const float		divisor		= (pb[majorAxisNdx] - pa[majorAxisNdx]);
	const float		divisorMax	= getMaxValueWithinError(divisor, 1);
	const float		divisorMin	= getMinValueWithinError(divisor, 1);
	DE_ASSERT(divisorMin <= divisorMax);

	// Allow 3 ULP precision for division
	const float		tMax		= getMaxValueWithinError(maximalRangeDivision(dividendMin, dividendMax, divisorMin, divisorMax), divError);
	const float		tMin		= getMinValueWithinError(minimalRangeDivision(dividendMin, dividendMax, divisorMin, divisorMax), divError);
	DE_ASSERT(tMin <= tMax);

	const float		perspectiveTMax			= getMaxValueWithinError(maximalRangeDivision(tMin, tMax, wb, wb), divError);
	const float		perspectiveTMin			= getMinValueWithinError(minimalRangeDivision(tMin, tMax, wb, wb), divError);
	DE_ASSERT(perspectiveTMin <= perspectiveTMax);

	const float		perspectiveInvTMax		= getMaxValueWithinError(maximalRangeDivision((1.0f - tMax), (1.0f - tMin), wa, wa), divError);
	const float		perspectiveInvTMin		= getMinValueWithinError(minimalRangeDivision((1.0f - tMax), (1.0f - tMin), wa, wa), divError);
	DE_ASSERT(perspectiveInvTMin <= perspectiveInvTMax);

	const float		perspectiveDivisorMax	= getMaxValueWithinError(perspectiveTMax + perspectiveInvTMax, roundError);
	const float		perspectiveDivisorMin	= getMinValueWithinError(perspectiveTMin + perspectiveInvTMin, roundError);
	DE_ASSERT(perspectiveDivisorMin <= perspectiveDivisorMax);

	LineInterpolationRange returnValue;
	returnValue.max.x() = getMaxValueWithinError(maximalRangeDivision(perspectiveInvTMin,	perspectiveInvTMax,	perspectiveDivisorMin, perspectiveDivisorMax), divError);
	returnValue.max.y() = getMaxValueWithinError(maximalRangeDivision(perspectiveTMin,		perspectiveTMax,	perspectiveDivisorMin, perspectiveDivisorMax), divError);
	returnValue.min.x() = getMinValueWithinError(minimalRangeDivision(perspectiveInvTMin,	perspectiveInvTMax,	perspectiveDivisorMin, perspectiveDivisorMax), divError);
	returnValue.min.y() = getMinValueWithinError(minimalRangeDivision(perspectiveTMin,		perspectiveTMax,	perspectiveDivisorMin, perspectiveDivisorMax), divError);

	DE_ASSERT(returnValue.min.x() <= returnValue.max.x());
	DE_ASSERT(returnValue.min.y() <= returnValue.max.y());

	return returnValue;
}

template <typename WeightEquation>
LineInterpolationRange calcSingleSampleLineInterpolationRangeWithWeightEquation (const tcu::Vec2&	pa,
																				 float				wa,
																				 const tcu::Vec2&	pb,
																				 float				wb,
																				 const tcu::IVec2&	pixel,
																				 int				subpixelBits,
																				 WeightEquation		weightEquation)
{
	// allow interpolation weights anywhere in the central subpixels
	const float testSquareSize = (2.0f / (float)(1UL << subpixelBits));
	const float testSquarePos  = (0.5f - testSquareSize / 2);

	const tcu::Vec2 corners[4] =
	{
		tcu::Vec2((float)pixel.x() + testSquarePos + 0.0f,				(float)pixel.y() + testSquarePos + 0.0f),
		tcu::Vec2((float)pixel.x() + testSquarePos + 0.0f,				(float)pixel.y() + testSquarePos + testSquareSize),
		tcu::Vec2((float)pixel.x() + testSquarePos + testSquareSize,	(float)pixel.y() + testSquarePos + testSquareSize),
		tcu::Vec2((float)pixel.x() + testSquarePos + testSquareSize,	(float)pixel.y() + testSquarePos + 0.0f),
	};

	// calculate interpolation as a line
	const LineInterpolationRange weights[4] =
	{
		weightEquation(pa, wa, pb, wb, corners[0]),
		weightEquation(pa, wa, pb, wb, corners[1]),
		weightEquation(pa, wa, pb, wb, corners[2]),
		weightEquation(pa, wa, pb, wb, corners[3]),
	};

	const tcu::Vec2 minWeights = tcu::min(tcu::min(weights[0].min, weights[1].min), tcu::min(weights[2].min, weights[3].min));
	const tcu::Vec2 maxWeights = tcu::max(tcu::max(weights[0].max, weights[1].max), tcu::max(weights[2].max, weights[3].max));

	LineInterpolationRange result;
	result.min = minWeights;
	result.max = maxWeights;
	return result;
}

LineInterpolationRange calcSingleSampleLineInterpolationRange (const tcu::Vec2& pa, float wa, const tcu::Vec2& pb, float wb, const tcu::IVec2& pixel, int subpixelBits)
{
	return calcSingleSampleLineInterpolationRangeWithWeightEquation(pa, wa, pb, wb, pixel, subpixelBits, calcLineInterpolationWeights);
}

LineInterpolationRange calcSingleSampleLineInterpolationRangeAxisProjected (const tcu::Vec2& pa, float wa, const tcu::Vec2& pb, float wb, const tcu::IVec2& pixel, int subpixelBits)
{
	return calcSingleSampleLineInterpolationRangeWithWeightEquation(pa, wa, pb, wb, pixel, subpixelBits, calcLineInterpolationWeightsAxisProjected);
}

struct TriangleInterpolator
{
	const TriangleSceneSpec& scene;

	TriangleInterpolator (const TriangleSceneSpec& scene_)
		: scene(scene_)
	{
	}

	InterpolationRange interpolate (int primitiveNdx, const tcu::IVec2 pixel, const tcu::IVec2 viewportSize, bool multisample, int subpixelBits) const
	{
		// allow anywhere in the pixel area in multisample
		// allow only in the center subpixels (4 subpixels) in singlesample
		const float testSquareSize = (multisample) ? (1.0f) : (2.0f / (float)(1UL << subpixelBits));
		const float testSquarePos  = (multisample) ? (0.0f) : (0.5f - testSquareSize / 2);
		const tcu::Vec2 corners[4] =
		{
			tcu::Vec2(((float)pixel.x() + testSquarePos + 0.0f)           / (float)viewportSize.x() * 2.0f - 1.0f, ((float)pixel.y() + testSquarePos + 0.0f          ) / (float)viewportSize.y() * 2.0f - 1.0f),
			tcu::Vec2(((float)pixel.x() + testSquarePos + 0.0f)           / (float)viewportSize.x() * 2.0f - 1.0f, ((float)pixel.y() + testSquarePos + testSquareSize) / (float)viewportSize.y() * 2.0f - 1.0f),
			tcu::Vec2(((float)pixel.x() + testSquarePos + testSquareSize) / (float)viewportSize.x() * 2.0f - 1.0f, ((float)pixel.y() + testSquarePos + testSquareSize) / (float)viewportSize.y() * 2.0f - 1.0f),
			tcu::Vec2(((float)pixel.x() + testSquarePos + testSquareSize) / (float)viewportSize.x() * 2.0f - 1.0f, ((float)pixel.y() + testSquarePos + 0.0f          ) / (float)viewportSize.y() * 2.0f - 1.0f),
		};
		const InterpolationRange weights[4] =
		{
			calcTriangleInterpolationWeights(scene.triangles[primitiveNdx].positions[0], scene.triangles[primitiveNdx].positions[1], scene.triangles[primitiveNdx].positions[2], corners[0]),
			calcTriangleInterpolationWeights(scene.triangles[primitiveNdx].positions[0], scene.triangles[primitiveNdx].positions[1], scene.triangles[primitiveNdx].positions[2], corners[1]),
			calcTriangleInterpolationWeights(scene.triangles[primitiveNdx].positions[0], scene.triangles[primitiveNdx].positions[1], scene.triangles[primitiveNdx].positions[2], corners[2]),
			calcTriangleInterpolationWeights(scene.triangles[primitiveNdx].positions[0], scene.triangles[primitiveNdx].positions[1], scene.triangles[primitiveNdx].positions[2], corners[3]),
		};

		InterpolationRange result;
		result.min = tcu::min(tcu::min(weights[0].min, weights[1].min), tcu::min(weights[2].min, weights[3].min));
		result.max = tcu::max(tcu::max(weights[0].max, weights[1].max), tcu::max(weights[2].max, weights[3].max));
		return result;
	}
};

/*--------------------------------------------------------------------*//*!
 * Used only by verifyMultisampleLineGroupInterpolation to calculate
 * correct line interpolations for the triangulated lines.
 *//*--------------------------------------------------------------------*/
struct MultisampleLineInterpolator
{
	const LineSceneSpec& scene;

	MultisampleLineInterpolator (const LineSceneSpec& scene_)
		: scene(scene_)
	{
	}

	InterpolationRange interpolate (int primitiveNdx, const tcu::IVec2 pixel, const tcu::IVec2 viewportSize, bool multisample, int subpixelBits) const
	{
		DE_UNREF(multisample);
		DE_UNREF(subpixelBits);

		// in triangulation, one line emits two triangles
		const int		lineNdx		= primitiveNdx / 2;

		// allow interpolation weights anywhere in the pixel
		const tcu::Vec2 corners[4] =
		{
			tcu::Vec2((float)pixel.x() + 0.0f, (float)pixel.y() + 0.0f),
			tcu::Vec2((float)pixel.x() + 0.0f, (float)pixel.y() + 1.0f),
			tcu::Vec2((float)pixel.x() + 1.0f, (float)pixel.y() + 1.0f),
			tcu::Vec2((float)pixel.x() + 1.0f, (float)pixel.y() + 0.0f),
		};

		const float		wa = scene.lines[lineNdx].positions[0].w();
		const float		wb = scene.lines[lineNdx].positions[1].w();
		const tcu::Vec2	pa = tcu::Vec2((scene.lines[lineNdx].positions[0].x() / wa + 1.0f) * 0.5f * (float)viewportSize.x(),
									   (scene.lines[lineNdx].positions[0].y() / wa + 1.0f) * 0.5f * (float)viewportSize.y());
		const tcu::Vec2	pb = tcu::Vec2((scene.lines[lineNdx].positions[1].x() / wb + 1.0f) * 0.5f * (float)viewportSize.x(),
									   (scene.lines[lineNdx].positions[1].y() / wb + 1.0f) * 0.5f * (float)viewportSize.y());

		// calculate interpolation as a line
		const LineInterpolationRange weights[4] =
		{
			calcLineInterpolationWeights(pa, wa, pb, wb, corners[0]),
			calcLineInterpolationWeights(pa, wa, pb, wb, corners[1]),
			calcLineInterpolationWeights(pa, wa, pb, wb, corners[2]),
			calcLineInterpolationWeights(pa, wa, pb, wb, corners[3]),
		};

		const tcu::Vec2 minWeights = tcu::min(tcu::min(weights[0].min, weights[1].min), tcu::min(weights[2].min, weights[3].min));
		const tcu::Vec2 maxWeights = tcu::max(tcu::max(weights[0].max, weights[1].max), tcu::max(weights[2].max, weights[3].max));

		// convert to three-component form. For all triangles, the vertex 0 is always emitted by the line starting point, and vertex 2 by the ending point
		InterpolationRange result;
		result.min = tcu::Vec3(minWeights.x(), 0.0f, minWeights.y());
		result.max = tcu::Vec3(maxWeights.x(), 0.0f, maxWeights.y());
		return result;
	}
};

template <typename Interpolator>
bool verifyTriangleGroupInterpolationWithInterpolator (const tcu::Surface& surface, const TriangleSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log, const Interpolator& interpolator)
{
	const tcu::RGBA		invalidPixelColor	= tcu::RGBA(255, 0, 0, 255);
	const bool			multisampled		= (args.numSamples != 0);
	const tcu::IVec2	viewportSize		= tcu::IVec2(surface.getWidth(), surface.getHeight());
	const int			errorFloodThreshold	= 4;
	int					errorCount			= 0;
	int					invalidPixels		= 0;
	int					subPixelBits		= args.subpixelBits;
	tcu::Surface		errorMask			(surface.getWidth(), surface.getHeight());

	tcu::clear(errorMask.getAccess(), tcu::Vec4(0.0f, 0.0f, 0.0f, 1.0f));

	// log format

	log << tcu::TestLog::Message << "Verifying rasterization result. Native format is RGB" << args.redBits << args.greenBits << args.blueBits << tcu::TestLog::EndMessage;
	if (args.redBits > 8 || args.greenBits > 8 || args.blueBits > 8)
		log << tcu::TestLog::Message << "Warning! More than 8 bits in a color channel, this may produce false negatives." << tcu::TestLog::EndMessage;

	// subpixel bits in in a valid range?

	if (subPixelBits < 0)
	{
		log << tcu::TestLog::Message << "Invalid subpixel count (" << subPixelBits << "), assuming 0" << tcu::TestLog::EndMessage;
		subPixelBits = 0;
	}
	else if (subPixelBits > 16)
	{
		// At high subpixel bit counts we might overflow. Checking at lower bit count is ok, but is less strict
		log << tcu::TestLog::Message << "Subpixel count is greater than 16 (" << subPixelBits << "). Checking results using less strict 16 bit requirements. This may produce false positives." << tcu::TestLog::EndMessage;
		subPixelBits = 16;
	}

	// check pixels

	for (int y = 0; y < surface.getHeight(); ++y)
	for (int x = 0; x < surface.getWidth();  ++x)
	{
		const tcu::RGBA		color				= surface.getPixel(x, y);
		bool				stackBottomFound	= false;
		int					stackSize			= 0;
		tcu::Vec4			colorStackMin;
		tcu::Vec4			colorStackMax;

		// Iterate triangle coverage front to back, find the stack of pontentially contributing fragments
		for (int triNdx = (int)scene.triangles.size() - 1; triNdx >= 0; --triNdx)
		{
			const CoverageType coverage = calculateTriangleCoverage(scene.triangles[triNdx].positions[0],
																	scene.triangles[triNdx].positions[1],
																	scene.triangles[triNdx].positions[2],
																	tcu::IVec2(x, y),
																	viewportSize,
																	subPixelBits,
																	multisampled);

			if (coverage == COVERAGE_FULL || coverage == COVERAGE_PARTIAL)
			{
				// potentially contributes to the result fragment's value
				const InterpolationRange weights = interpolator.interpolate(triNdx, tcu::IVec2(x, y), viewportSize, multisampled, subPixelBits);

				const tcu::Vec4 fragmentColorMax =	de::clamp(weights.max.x(), 0.0f, 1.0f) * scene.triangles[triNdx].colors[0] +
													de::clamp(weights.max.y(), 0.0f, 1.0f) * scene.triangles[triNdx].colors[1] +
													de::clamp(weights.max.z(), 0.0f, 1.0f) * scene.triangles[triNdx].colors[2];
				const tcu::Vec4 fragmentColorMin =	de::clamp(weights.min.x(), 0.0f, 1.0f) * scene.triangles[triNdx].colors[0] +
													de::clamp(weights.min.y(), 0.0f, 1.0f) * scene.triangles[triNdx].colors[1] +
													de::clamp(weights.min.z(), 0.0f, 1.0f) * scene.triangles[triNdx].colors[2];

				if (stackSize++ == 0)
				{
					// first triangle, set the values properly
					colorStackMin = fragmentColorMin;
					colorStackMax = fragmentColorMax;
				}
				else
				{
					// contributing triangle
					colorStackMin = tcu::min(colorStackMin, fragmentColorMin);
					colorStackMax = tcu::max(colorStackMax, fragmentColorMax);
				}

				if (coverage == COVERAGE_FULL)
				{
					// loop terminates, this is the bottommost fragment
					stackBottomFound = true;
					break;
				}
			}
		}

		// Partial coverage == background may be visible
		if (stackSize != 0 && !stackBottomFound)
		{
			stackSize++;
			colorStackMin = tcu::Vec4(0.0f, 0.0f, 0.0f, 1.0f);
		}

		// Is the result image color in the valid range.
		if (stackSize == 0)
		{
			// No coverage, allow only background (black, value=0)
			const tcu::IVec3	pixelNativeColor	= convertRGB8ToNativeFormat(color, args);
			const int			threshold			= 1;

			if (pixelNativeColor.x() > threshold ||
				pixelNativeColor.y() > threshold ||
				pixelNativeColor.z() > threshold)
			{
				++errorCount;

				// don't fill the logs with too much data
				if (errorCount < errorFloodThreshold)
				{
					log << tcu::TestLog::Message
						<< "Found an invalid pixel at (" << x << "," << y << ")\n"
						<< "\tPixel color:\t\t" << color << "\n"
						<< "\tExpected background color.\n"
						<< tcu::TestLog::EndMessage;
				}

				++invalidPixels;
				errorMask.setPixel(x, y, invalidPixelColor);
			}
		}
		else
		{
			DE_ASSERT(stackSize);

			// Each additional step in the stack may cause conversion error of 1 bit due to undefined rounding direction
			const int			thresholdRed	= stackSize - 1;
			const int			thresholdGreen	= stackSize - 1;
			const int			thresholdBlue	= stackSize - 1;

			const tcu::Vec3		valueRangeMin	= tcu::Vec3(colorStackMin.xyz());
			const tcu::Vec3		valueRangeMax	= tcu::Vec3(colorStackMax.xyz());

			const tcu::IVec3	formatLimit		((1 << args.redBits) - 1, (1 << args.greenBits) - 1, (1 << args.blueBits) - 1);
			const tcu::Vec3		colorMinF		(de::clamp(valueRangeMin.x() * (float)formatLimit.x(), 0.0f, (float)formatLimit.x()),
												 de::clamp(valueRangeMin.y() * (float)formatLimit.y(), 0.0f, (float)formatLimit.y()),
												 de::clamp(valueRangeMin.z() * (float)formatLimit.z(), 0.0f, (float)formatLimit.z()));
			const tcu::Vec3		colorMaxF		(de::clamp(valueRangeMax.x() * (float)formatLimit.x(), 0.0f, (float)formatLimit.x()),
												 de::clamp(valueRangeMax.y() * (float)formatLimit.y(), 0.0f, (float)formatLimit.y()),
												 de::clamp(valueRangeMax.z() * (float)formatLimit.z(), 0.0f, (float)formatLimit.z()));
			const tcu::IVec3	colorMin		((int)deFloatFloor(colorMinF.x()),
												 (int)deFloatFloor(colorMinF.y()),
												 (int)deFloatFloor(colorMinF.z()));
			const tcu::IVec3	colorMax		((int)deFloatCeil (colorMaxF.x()),
												 (int)deFloatCeil (colorMaxF.y()),
												 (int)deFloatCeil (colorMaxF.z()));

			// Convert pixel color from rgba8 to the real pixel format. Usually rgba8 or 565
			const tcu::IVec3 pixelNativeColor = convertRGB8ToNativeFormat(color, args);

			// Validity check
			if (pixelNativeColor.x() < colorMin.x() - thresholdRed   ||
				pixelNativeColor.y() < colorMin.y() - thresholdGreen ||
				pixelNativeColor.z() < colorMin.z() - thresholdBlue  ||
				pixelNativeColor.x() > colorMax.x() + thresholdRed   ||
				pixelNativeColor.y() > colorMax.y() + thresholdGreen ||
				pixelNativeColor.z() > colorMax.z() + thresholdBlue)
			{
				++errorCount;

				// don't fill the logs with too much data
				if (errorCount <= errorFloodThreshold)
				{
					log << tcu::TestLog::Message
						<< "Found an invalid pixel at (" << x << "," << y << ")\n"
						<< "\tPixel color:\t\t" << color << "\n"
						<< "\tNative color:\t\t" << pixelNativeColor << "\n"
						<< "\tAllowed error:\t\t" << tcu::IVec3(thresholdRed, thresholdGreen, thresholdBlue) << "\n"
						<< "\tReference native color min: " << tcu::clamp(colorMin - tcu::IVec3(thresholdRed, thresholdGreen, thresholdBlue), tcu::IVec3(0,0,0), formatLimit) << "\n"
						<< "\tReference native color max: " << tcu::clamp(colorMax + tcu::IVec3(thresholdRed, thresholdGreen, thresholdBlue), tcu::IVec3(0,0,0), formatLimit) << "\n"
						<< "\tReference native float min: " << tcu::clamp(colorMinF - tcu::IVec3(thresholdRed, thresholdGreen, thresholdBlue).cast<float>(), tcu::Vec3(0.0f, 0.0f, 0.0f), formatLimit.cast<float>()) << "\n"
						<< "\tReference native float max: " << tcu::clamp(colorMaxF + tcu::IVec3(thresholdRed, thresholdGreen, thresholdBlue).cast<float>(), tcu::Vec3(0.0f, 0.0f, 0.0f), formatLimit.cast<float>()) << "\n"
						<< "\tFmin:\t" << tcu::clamp(valueRangeMin, tcu::Vec3(0.0f, 0.0f, 0.0f), tcu::Vec3(1.0f, 1.0f, 1.0f)) << "\n"
						<< "\tFmax:\t" << tcu::clamp(valueRangeMax, tcu::Vec3(0.0f, 0.0f, 0.0f), tcu::Vec3(1.0f, 1.0f, 1.0f)) << "\n"
						<< tcu::TestLog::EndMessage;
				}

				++invalidPixels;
				errorMask.setPixel(x, y, invalidPixelColor);
			}
		}
	}

	// don't just hide failures
	if (errorCount > errorFloodThreshold)
		log << tcu::TestLog::Message << "Omitted " << (errorCount-errorFloodThreshold) << " pixel error description(s)." << tcu::TestLog::EndMessage;

	// report result
	if (invalidPixels)
	{
		log << tcu::TestLog::Message << invalidPixels << " invalid pixel(s) found." << tcu::TestLog::EndMessage;
		log << tcu::TestLog::ImageSet("Verification result", "Result of rendering")
			<< tcu::TestLog::Image("Result", "Result",			surface)
			<< tcu::TestLog::Image("ErrorMask", "ErrorMask",	errorMask)
			<< tcu::TestLog::EndImageSet;

		return false;
	}
	else
	{
		log << tcu::TestLog::Message << "No invalid pixels found." << tcu::TestLog::EndMessage;
		log << tcu::TestLog::ImageSet("Verification result", "Result of rendering")
			<< tcu::TestLog::Image("Result", "Result", surface)
			<< tcu::TestLog::EndImageSet;

		return true;
	}
}


float calculateIntersectionParameter (const tcu::Vec2 line[2], float w, int componentNdx)
{
	DE_ASSERT(componentNdx < 2);
	if (line[1][componentNdx] == line[0][componentNdx])
		return -1.0f;

	return (w - line[0][componentNdx]) / (line[1][componentNdx] - line[0][componentNdx]);
}

// Clips the given line with a ((-w, -w), (-w, w), (w, w), (w, -w)) rectangle
void applyClippingBox (tcu::Vec2 line[2], float w)
{
	for (int side = 0; side < 4; ++side)
	{
		const int	sign		= ((side / 2) * -2) + 1;
		const int	component	= side % 2;
		const float	t			= calculateIntersectionParameter(line, w * (float)sign, component);

		if ((t > 0) && (t < 1))
		{
			const float newCoord	= t * line[1][1 - component] + (1 - t) * line[0][1 - component];

			if (line[1][component] > (w * (float)sign))
			{
				line[1 - side / 2][component] = w * (float)sign;
				line[1 - side / 2][1 - component] = newCoord;
			}
			else
			{
				line[side / 2][component] = w * (float)sign;
				line[side / 2][1 - component] = newCoord;
			}
		}
	}
}

enum ClipMode
{
	CLIPMODE_NO_CLIPPING = 0,
	CLIPMODE_USE_CLIPPING_BOX,

	CLIPMODE_LAST
};

bool verifyMultisampleLineGroupRasterization (const tcu::Surface& surface, const LineSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log, ClipMode clipMode)
{
	// Multisampled line == 2 triangles

	const tcu::Vec2		viewportSize	= tcu::Vec2((float)surface.getWidth(), (float)surface.getHeight());
	const float			halfLineWidth	= scene.lineWidth * 0.5f;
	TriangleSceneSpec	triangleScene;

	triangleScene.triangles.resize(2 * scene.lines.size());
	for (int lineNdx = 0; lineNdx < (int)scene.lines.size(); ++lineNdx)
	{
		// Transform to screen space, add pixel offsets, convert back to normalized device space, and test as triangles
		tcu::Vec2 lineNormalizedDeviceSpace[2] =
		{
			tcu::Vec2(scene.lines[lineNdx].positions[0].x() / scene.lines[lineNdx].positions[0].w(), scene.lines[lineNdx].positions[0].y() / scene.lines[lineNdx].positions[0].w()),
			tcu::Vec2(scene.lines[lineNdx].positions[1].x() / scene.lines[lineNdx].positions[1].w(), scene.lines[lineNdx].positions[1].y() / scene.lines[lineNdx].positions[1].w()),
		};

		if (clipMode == CLIPMODE_USE_CLIPPING_BOX)
		{
			applyClippingBox(lineNormalizedDeviceSpace, 1.0f);
		}

		const tcu::Vec2 lineScreenSpace[2] =
		{
			(lineNormalizedDeviceSpace[0] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * viewportSize,
			(lineNormalizedDeviceSpace[1] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * viewportSize,
		};

		const tcu::Vec2 lineDir			= tcu::normalize(lineScreenSpace[1] - lineScreenSpace[0]);
		const tcu::Vec2 lineNormalDir	= tcu::Vec2(lineDir.y(), -lineDir.x());

		const tcu::Vec2 lineQuadScreenSpace[4] =
		{
			lineScreenSpace[0] + lineNormalDir * halfLineWidth,
			lineScreenSpace[0] - lineNormalDir * halfLineWidth,
			lineScreenSpace[1] - lineNormalDir * halfLineWidth,
			lineScreenSpace[1] + lineNormalDir * halfLineWidth,
		};
		const tcu::Vec2 lineQuadNormalizedDeviceSpace[4] =
		{
			lineQuadScreenSpace[0] / viewportSize * 2.0f - tcu::Vec2(1.0f, 1.0f),
			lineQuadScreenSpace[1] / viewportSize * 2.0f - tcu::Vec2(1.0f, 1.0f),
			lineQuadScreenSpace[2] / viewportSize * 2.0f - tcu::Vec2(1.0f, 1.0f),
			lineQuadScreenSpace[3] / viewportSize * 2.0f - tcu::Vec2(1.0f, 1.0f),
		};

		triangleScene.triangles[lineNdx*2 + 0].positions[0] = tcu::Vec4(lineQuadNormalizedDeviceSpace[0].x(), lineQuadNormalizedDeviceSpace[0].y(), 0.0f, 1.0f);	triangleScene.triangles[lineNdx*2 + 0].sharedEdge[0] = false;
		triangleScene.triangles[lineNdx*2 + 0].positions[1] = tcu::Vec4(lineQuadNormalizedDeviceSpace[1].x(), lineQuadNormalizedDeviceSpace[1].y(), 0.0f, 1.0f);	triangleScene.triangles[lineNdx*2 + 0].sharedEdge[1] = false;
		triangleScene.triangles[lineNdx*2 + 0].positions[2] = tcu::Vec4(lineQuadNormalizedDeviceSpace[2].x(), lineQuadNormalizedDeviceSpace[2].y(), 0.0f, 1.0f);	triangleScene.triangles[lineNdx*2 + 0].sharedEdge[2] = true;

		triangleScene.triangles[lineNdx*2 + 1].positions[0] = tcu::Vec4(lineQuadNormalizedDeviceSpace[0].x(), lineQuadNormalizedDeviceSpace[0].y(), 0.0f, 1.0f);	triangleScene.triangles[lineNdx*2 + 1].sharedEdge[0] = true;
		triangleScene.triangles[lineNdx*2 + 1].positions[1] = tcu::Vec4(lineQuadNormalizedDeviceSpace[2].x(), lineQuadNormalizedDeviceSpace[2].y(), 0.0f, 1.0f);	triangleScene.triangles[lineNdx*2 + 1].sharedEdge[1] = false;
		triangleScene.triangles[lineNdx*2 + 1].positions[2] = tcu::Vec4(lineQuadNormalizedDeviceSpace[3].x(), lineQuadNormalizedDeviceSpace[3].y(), 0.0f, 1.0f);	triangleScene.triangles[lineNdx*2 + 1].sharedEdge[2] = false;
	}

	return verifyTriangleGroupRasterization(surface, triangleScene, args, log);
}

bool verifyMultisampleLineGroupInterpolation (const tcu::Surface& surface, const LineSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log)
{
	// Multisampled line == 2 triangles

	const tcu::Vec2		viewportSize	= tcu::Vec2((float)surface.getWidth(), (float)surface.getHeight());
	const float			halfLineWidth	= scene.lineWidth * 0.5f;
	TriangleSceneSpec	triangleScene;

	triangleScene.triangles.resize(2 * scene.lines.size());
	for (int lineNdx = 0; lineNdx < (int)scene.lines.size(); ++lineNdx)
	{
		// Transform to screen space, add pixel offsets, convert back to normalized device space, and test as triangles
		const tcu::Vec2 lineNormalizedDeviceSpace[2] =
		{
			tcu::Vec2(scene.lines[lineNdx].positions[0].x() / scene.lines[lineNdx].positions[0].w(), scene.lines[lineNdx].positions[0].y() / scene.lines[lineNdx].positions[0].w()),
			tcu::Vec2(scene.lines[lineNdx].positions[1].x() / scene.lines[lineNdx].positions[1].w(), scene.lines[lineNdx].positions[1].y() / scene.lines[lineNdx].positions[1].w()),
		};
		const tcu::Vec2 lineScreenSpace[2] =
		{
			(lineNormalizedDeviceSpace[0] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * viewportSize,
			(lineNormalizedDeviceSpace[1] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * viewportSize,
		};

		const tcu::Vec2 lineDir			= tcu::normalize(lineScreenSpace[1] - lineScreenSpace[0]);
		const tcu::Vec2 lineNormalDir	= tcu::Vec2(lineDir.y(), -lineDir.x());

		const tcu::Vec2 lineQuadScreenSpace[4] =
		{
			lineScreenSpace[0] + lineNormalDir * halfLineWidth,
			lineScreenSpace[0] - lineNormalDir * halfLineWidth,
			lineScreenSpace[1] - lineNormalDir * halfLineWidth,
			lineScreenSpace[1] + lineNormalDir * halfLineWidth,
		};
		const tcu::Vec2 lineQuadNormalizedDeviceSpace[4] =
		{
			lineQuadScreenSpace[0] / viewportSize * 2.0f - tcu::Vec2(1.0f, 1.0f),
			lineQuadScreenSpace[1] / viewportSize * 2.0f - tcu::Vec2(1.0f, 1.0f),
			lineQuadScreenSpace[2] / viewportSize * 2.0f - tcu::Vec2(1.0f, 1.0f),
			lineQuadScreenSpace[3] / viewportSize * 2.0f - tcu::Vec2(1.0f, 1.0f),
		};

		triangleScene.triangles[lineNdx*2 + 0].positions[0] = tcu::Vec4(lineQuadNormalizedDeviceSpace[0].x(), lineQuadNormalizedDeviceSpace[0].y(), 0.0f, 1.0f);
		triangleScene.triangles[lineNdx*2 + 0].positions[1] = tcu::Vec4(lineQuadNormalizedDeviceSpace[1].x(), lineQuadNormalizedDeviceSpace[1].y(), 0.0f, 1.0f);
		triangleScene.triangles[lineNdx*2 + 0].positions[2] = tcu::Vec4(lineQuadNormalizedDeviceSpace[2].x(), lineQuadNormalizedDeviceSpace[2].y(), 0.0f, 1.0f);

		triangleScene.triangles[lineNdx*2 + 0].sharedEdge[0] = false;
		triangleScene.triangles[lineNdx*2 + 0].sharedEdge[1] = false;
		triangleScene.triangles[lineNdx*2 + 0].sharedEdge[2] = true;

		triangleScene.triangles[lineNdx*2 + 0].colors[0] = scene.lines[lineNdx].colors[0];
		triangleScene.triangles[lineNdx*2 + 0].colors[1] = scene.lines[lineNdx].colors[0];
		triangleScene.triangles[lineNdx*2 + 0].colors[2] = scene.lines[lineNdx].colors[1];

		triangleScene.triangles[lineNdx*2 + 1].positions[0] = tcu::Vec4(lineQuadNormalizedDeviceSpace[0].x(), lineQuadNormalizedDeviceSpace[0].y(), 0.0f, 1.0f);
		triangleScene.triangles[lineNdx*2 + 1].positions[1] = tcu::Vec4(lineQuadNormalizedDeviceSpace[2].x(), lineQuadNormalizedDeviceSpace[2].y(), 0.0f, 1.0f);
		triangleScene.triangles[lineNdx*2 + 1].positions[2] = tcu::Vec4(lineQuadNormalizedDeviceSpace[3].x(), lineQuadNormalizedDeviceSpace[3].y(), 0.0f, 1.0f);

		triangleScene.triangles[lineNdx*2 + 1].sharedEdge[0] = true;
		triangleScene.triangles[lineNdx*2 + 1].sharedEdge[1] = false;
		triangleScene.triangles[lineNdx*2 + 1].sharedEdge[2] = false;

		triangleScene.triangles[lineNdx*2 + 1].colors[0] = scene.lines[lineNdx].colors[0];
		triangleScene.triangles[lineNdx*2 + 1].colors[1] = scene.lines[lineNdx].colors[1];
		triangleScene.triangles[lineNdx*2 + 1].colors[2] = scene.lines[lineNdx].colors[1];
	}

	return verifyTriangleGroupInterpolationWithInterpolator(surface, triangleScene, args, log, MultisampleLineInterpolator(scene));
}

bool verifyMultisamplePointGroupRasterization (const tcu::Surface& surface, const PointSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log)
{
	// Multisampled point == 2 triangles

	const tcu::Vec2		viewportSize	= tcu::Vec2((float)surface.getWidth(), (float)surface.getHeight());
	TriangleSceneSpec	triangleScene;

	triangleScene.triangles.resize(2 * scene.points.size());
	for (int pointNdx = 0; pointNdx < (int)scene.points.size(); ++pointNdx)
	{
		// Transform to screen space, add pixel offsets, convert back to normalized device space, and test as triangles
		const tcu::Vec2	pointNormalizedDeviceSpace			= tcu::Vec2(scene.points[pointNdx].position.x() / scene.points[pointNdx].position.w(), scene.points[pointNdx].position.y() / scene.points[pointNdx].position.w());
		const tcu::Vec2	pointScreenSpace					= (pointNormalizedDeviceSpace + tcu::Vec2(1.0f, 1.0f)) * 0.5f * viewportSize;
		const float		offset								= scene.points[pointNdx].pointSize * 0.5f;
		const tcu::Vec2	lineQuadNormalizedDeviceSpace[4]	=
		{
			(pointScreenSpace + tcu::Vec2(-offset, -offset))/ viewportSize * 2.0f - tcu::Vec2(1.0f, 1.0f),
			(pointScreenSpace + tcu::Vec2(-offset,  offset))/ viewportSize * 2.0f - tcu::Vec2(1.0f, 1.0f),
			(pointScreenSpace + tcu::Vec2( offset,  offset))/ viewportSize * 2.0f - tcu::Vec2(1.0f, 1.0f),
			(pointScreenSpace + tcu::Vec2( offset, -offset))/ viewportSize * 2.0f - tcu::Vec2(1.0f, 1.0f),
		};

		triangleScene.triangles[pointNdx*2 + 0].positions[0] = tcu::Vec4(lineQuadNormalizedDeviceSpace[0].x(), lineQuadNormalizedDeviceSpace[0].y(), 0.0f, 1.0f);	triangleScene.triangles[pointNdx*2 + 0].sharedEdge[0] = false;
		triangleScene.triangles[pointNdx*2 + 0].positions[1] = tcu::Vec4(lineQuadNormalizedDeviceSpace[1].x(), lineQuadNormalizedDeviceSpace[1].y(), 0.0f, 1.0f);	triangleScene.triangles[pointNdx*2 + 0].sharedEdge[1] = false;
		triangleScene.triangles[pointNdx*2 + 0].positions[2] = tcu::Vec4(lineQuadNormalizedDeviceSpace[2].x(), lineQuadNormalizedDeviceSpace[2].y(), 0.0f, 1.0f);	triangleScene.triangles[pointNdx*2 + 0].sharedEdge[2] = true;

		triangleScene.triangles[pointNdx*2 + 1].positions[0] = tcu::Vec4(lineQuadNormalizedDeviceSpace[0].x(), lineQuadNormalizedDeviceSpace[0].y(), 0.0f, 1.0f);	triangleScene.triangles[pointNdx*2 + 1].sharedEdge[0] = true;
		triangleScene.triangles[pointNdx*2 + 1].positions[1] = tcu::Vec4(lineQuadNormalizedDeviceSpace[2].x(), lineQuadNormalizedDeviceSpace[2].y(), 0.0f, 1.0f);	triangleScene.triangles[pointNdx*2 + 1].sharedEdge[1] = false;
		triangleScene.triangles[pointNdx*2 + 1].positions[2] = tcu::Vec4(lineQuadNormalizedDeviceSpace[3].x(), lineQuadNormalizedDeviceSpace[3].y(), 0.0f, 1.0f);	triangleScene.triangles[pointNdx*2 + 1].sharedEdge[2] = false;
	}

	return verifyTriangleGroupRasterization(surface, triangleScene, args, log);
}

void genScreenSpaceLines (std::vector<tcu::Vec4>& screenspaceLines, const std::vector<LineSceneSpec::SceneLine>& lines, const tcu::IVec2& viewportSize)
{
	DE_ASSERT(screenspaceLines.size() == lines.size());

	for (int lineNdx = 0; lineNdx < (int)lines.size(); ++lineNdx)
	{
		const tcu::Vec2 lineNormalizedDeviceSpace[2] =
		{
			tcu::Vec2(lines[lineNdx].positions[0].x() / lines[lineNdx].positions[0].w(), lines[lineNdx].positions[0].y() / lines[lineNdx].positions[0].w()),
			tcu::Vec2(lines[lineNdx].positions[1].x() / lines[lineNdx].positions[1].w(), lines[lineNdx].positions[1].y() / lines[lineNdx].positions[1].w()),
		};
		const tcu::Vec4 lineScreenSpace[2] =
		{
			tcu::Vec4((lineNormalizedDeviceSpace[0].x() + 1.0f) * 0.5f * (float)viewportSize.x(), (lineNormalizedDeviceSpace[0].y() + 1.0f) * 0.5f * (float)viewportSize.y(), 0.0f, 1.0f),
			tcu::Vec4((lineNormalizedDeviceSpace[1].x() + 1.0f) * 0.5f * (float)viewportSize.x(), (lineNormalizedDeviceSpace[1].y() + 1.0f) * 0.5f * (float)viewportSize.y(), 0.0f, 1.0f),
		};

		screenspaceLines[lineNdx] = tcu::Vec4(lineScreenSpace[0].x(), lineScreenSpace[0].y(), lineScreenSpace[1].x(), lineScreenSpace[1].y());
	}
}

bool verifySinglesampleLineGroupRasterization (const tcu::Surface& surface, const LineSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log)
{
	DE_ASSERT(deFloatFrac(scene.lineWidth) != 0.5f); // rounding direction is not defined, disallow undefined cases
	DE_ASSERT(scene.lines.size() < 255); // indices are stored as unsigned 8-bit ints

	bool					allOK				= true;
	bool					overdrawInReference	= false;
	int						referenceFragments	= 0;
	int						resultFragments		= 0;
	int						lineWidth			= deFloorFloatToInt32(scene.lineWidth + 0.5f);
	bool					imageShown			= false;
	std::vector<bool>		lineIsXMajor		(scene.lines.size());
	std::vector<tcu::Vec4>	screenspaceLines(scene.lines.size());

	// Reference renderer produces correct fragments using the diamond-rule. Make 2D int array, each cell contains the highest index (first index = 1) of the overlapping lines or 0 if no line intersects the pixel
	tcu::TextureLevel referenceLineMap(tcu::TextureFormat(tcu::TextureFormat::R, tcu::TextureFormat::UNSIGNED_INT8), surface.getWidth(), surface.getHeight());
	tcu::clear(referenceLineMap.getAccess(), tcu::IVec4(0, 0, 0, 0));

	genScreenSpaceLines(screenspaceLines, scene.lines, tcu::IVec2(surface.getWidth(), surface.getHeight()));

	for (int lineNdx = 0; lineNdx < (int)scene.lines.size(); ++lineNdx)
	{
		rr::SingleSampleLineRasterizer rasterizer(tcu::IVec4(0, 0, surface.getWidth(), surface.getHeight()));
		rasterizer.init(tcu::Vec4(screenspaceLines[lineNdx][0],
								  screenspaceLines[lineNdx][1],
								  0.0f,
								  1.0f),
						tcu::Vec4(screenspaceLines[lineNdx][2],
								  screenspaceLines[lineNdx][3],
								  0.0f,
								  1.0f),
						scene.lineWidth);

		// calculate majority of later use
		lineIsXMajor[lineNdx] = isPackedSSLineXMajor(screenspaceLines[lineNdx]);

		for (;;)
		{
			const int			maxPackets			= 32;
			int					numRasterized		= 0;
			rr::FragmentPacket	packets[maxPackets];

			rasterizer.rasterize(packets, DE_NULL, maxPackets, numRasterized);

			for (int packetNdx = 0; packetNdx < numRasterized; ++packetNdx)
			{
				for (int fragNdx = 0; fragNdx < 4; ++fragNdx)
				{
					if ((deUint32)packets[packetNdx].coverage & (1 << fragNdx))
					{
						const tcu::IVec2 fragPos = packets[packetNdx].position + tcu::IVec2(fragNdx%2, fragNdx/2);

						// Check for overdraw
						if (!overdrawInReference)
							overdrawInReference = referenceLineMap.getAccess().getPixelInt(fragPos.x(), fragPos.y()).x() != 0;

						// Output pixel
						referenceLineMap.getAccess().setPixel(tcu::IVec4(lineNdx + 1, 0, 0, 0), fragPos.x(), fragPos.y());
					}
				}
			}

			if (numRasterized != maxPackets)
				break;
		}
	}

	// Requirement 1: The coordinates of a fragment produced by the algorithm may not deviate by more than one unit
	{
		tcu::Surface	errorMask			(surface.getWidth(), surface.getHeight());
		bool			missingFragments	= false;

		tcu::clear(errorMask.getAccess(), tcu::IVec4(0, 255, 0, 255));

		log << tcu::TestLog::Message << "Searching for deviating fragments." << tcu::TestLog::EndMessage;

		for (int y = 0; y < referenceLineMap.getHeight(); ++y)
		for (int x = 0; x < referenceLineMap.getWidth(); ++x)
		{
			const bool reference	= referenceLineMap.getAccess().getPixelInt(x, y).x() != 0;
			const bool result		= compareColors(surface.getPixel(x, y), tcu::RGBA::white(), args.redBits, args.greenBits, args.blueBits);

			if (reference)
				++referenceFragments;
			if (result)
				++resultFragments;

			if (reference == result)
				continue;

			// Reference fragment here, matching result fragment must be nearby
			if (reference && !result)
			{
				bool foundFragment = false;

				if (x == 0 || y == 0 || x == referenceLineMap.getWidth() - 1 || y == referenceLineMap.getHeight() -1)
				{
					// image boundary, missing fragment could be over the image edge
					foundFragment = true;
				}

				// find nearby fragment
				for (int dy = -1; dy < 2 && !foundFragment; ++dy)
				for (int dx = -1; dx < 2 && !foundFragment; ++dx)
				{
					if (compareColors(surface.getPixel(x+dx, y+dy), tcu::RGBA::white(), args.redBits, args.greenBits, args.blueBits))
						foundFragment = true;
				}

				if (!foundFragment)
				{
					missingFragments = true;
					errorMask.setPixel(x, y, tcu::RGBA::red());
				}
			}
		}

		if (missingFragments)
		{
			log << tcu::TestLog::Message << "Invalid deviation(s) found." << tcu::TestLog::EndMessage;
			log << tcu::TestLog::ImageSet("Verification result", "Result of rendering")
				<< tcu::TestLog::Image("Result", "Result",			surface)
				<< tcu::TestLog::Image("ErrorMask", "ErrorMask",	errorMask)
				<< tcu::TestLog::EndImageSet;

			imageShown = true;
			allOK = false;
		}
		else
		{
			log << tcu::TestLog::Message << "No invalid deviations found." << tcu::TestLog::EndMessage;
		}
	}

	// Requirement 2: The total number of fragments produced by the algorithm may differ from
	//                that produced by the diamond-exit rule by no more than one.
	{
		// Check is not valid if the primitives intersect or otherwise share same fragments
		if (!overdrawInReference)
		{
			int allowedDeviation = (int)scene.lines.size() * lineWidth; // one pixel per primitive in the major direction

			log << tcu::TestLog::Message << "Verifying fragment counts:\n"
				<< "\tDiamond-exit rule: " << referenceFragments << " fragments.\n"
				<< "\tResult image: " << resultFragments << " fragments.\n"
				<< "\tAllowing deviation of " << allowedDeviation << " fragments.\n"
				<< tcu::TestLog::EndMessage;

			if (deAbs32(referenceFragments - resultFragments) > allowedDeviation)
			{
				tcu::Surface reference(surface.getWidth(), surface.getHeight());

				// show a helpful reference image
				tcu::clear(reference.getAccess(), tcu::IVec4(0, 0, 0, 255));
				for (int y = 0; y < surface.getHeight(); ++y)
				for (int x = 0; x < surface.getWidth(); ++x)
					if (referenceLineMap.getAccess().getPixelInt(x, y).x())
						reference.setPixel(x, y, tcu::RGBA::white());

				log << tcu::TestLog::Message << "Invalid fragment count in result image." << tcu::TestLog::EndMessage;
				log << tcu::TestLog::ImageSet("Verification result", "Result of rendering")
					<< tcu::TestLog::Image("Reference", "Reference",	reference)
					<< tcu::TestLog::Image("Result", "Result",			surface)
					<< tcu::TestLog::EndImageSet;

				allOK = false;
				imageShown = true;
			}
			else
			{
				log << tcu::TestLog::Message << "Fragment count is valid." << tcu::TestLog::EndMessage;
			}
		}
		else
		{
			log << tcu::TestLog::Message << "Overdraw in scene. Fragment count cannot be verified. Skipping fragment count checks." << tcu::TestLog::EndMessage;
		}
	}

	// Requirement 3: Line width must be constant
	{
		bool invalidWidthFound = false;

		log << tcu::TestLog::Message << "Verifying line widths of the x-major lines." << tcu::TestLog::EndMessage;
		for (int y = 1; y < referenceLineMap.getHeight() - 1; ++y)
		{
			bool	fullyVisibleLine		= false;
			bool	previousPixelUndefined	= false;
			int		currentLine				= 0;
			int		currentWidth			= 1;

			for (int x = 1; x < referenceLineMap.getWidth() - 1; ++x)
			{
				const bool	result	= compareColors(surface.getPixel(x, y), tcu::RGBA::white(), args.redBits, args.greenBits, args.blueBits);
				int			lineID	= 0;

				// Which line does this fragment belong to?

				if (result)
				{
					bool multipleNearbyLines = false;
					bool renderAtSurfaceEdge = false;

					renderAtSurfaceEdge = (x == 1) || (x == referenceLineMap.getWidth() - 2);

					for (int dy = -1; dy < 2; ++dy)
					for (int dx = -1; dx < 2; ++dx)
					{
						const int nearbyID = referenceLineMap.getAccess().getPixelInt(x+dx, y+dy).x();
						if (nearbyID)
						{
							if (lineID && lineID != nearbyID)
								multipleNearbyLines = true;
							lineID = nearbyID;
						}
					}

					if (multipleNearbyLines || renderAtSurfaceEdge)
					{
						// Another line is too close, don't try to calculate width here
						// Or the render result is outside of surface range
						previousPixelUndefined = true;
						continue;
					}
				}

				// Only line with id of lineID is nearby

				if (previousPixelUndefined)
				{
					// The line might have been overdrawn or not
					currentLine = lineID;
					currentWidth = 1;
					fullyVisibleLine = false;
					previousPixelUndefined = false;
				}
				else if (lineID == currentLine)
				{
					// Current line continues
					++currentWidth;
				}
				else if (lineID > currentLine)
				{
					// Another line was drawn over or the line ends
					currentLine = lineID;
					currentWidth = 1;
					fullyVisibleLine = true;
				}
				else
				{
					// The line ends
					if (fullyVisibleLine && !lineIsXMajor[currentLine-1])
					{
						// check width
						if (currentWidth != lineWidth)
						{
							log << tcu::TestLog::Message << "\tInvalid line width at (" << x - currentWidth << ", " << y << ") - (" << x - 1 << ", " << y << "). Detected width of " << currentWidth << ", expected " << lineWidth << tcu::TestLog::EndMessage;
							invalidWidthFound = true;
						}
					}

					currentLine = lineID;
					currentWidth = 1;
					fullyVisibleLine = false;
				}
			}
		}

		log << tcu::TestLog::Message << "Verifying line widths of the y-major lines." << tcu::TestLog::EndMessage;
		for (int x = 1; x < referenceLineMap.getWidth() - 1; ++x)
		{
			bool	fullyVisibleLine		= false;
			bool	previousPixelUndefined	= false;
			int		currentLine				= 0;
			int		currentWidth			= 1;

			for (int y = 1; y < referenceLineMap.getHeight() - 1; ++y)
			{
				const bool	result	= compareColors(surface.getPixel(x, y), tcu::RGBA::white(), args.redBits, args.greenBits, args.blueBits);
				int			lineID	= 0;

				// Which line does this fragment belong to?

				if (result)
				{
					bool multipleNearbyLines = false;
					bool renderAtSurfaceEdge = false;

					renderAtSurfaceEdge = (y == 1) || (y == referenceLineMap.getWidth() - 2);

					for (int dy = -1; dy < 2; ++dy)
					for (int dx = -1; dx < 2; ++dx)
					{
						const int nearbyID = referenceLineMap.getAccess().getPixelInt(x+dx, y+dy).x();
						if (nearbyID)
						{
							if (lineID && lineID != nearbyID)
								multipleNearbyLines = true;
							lineID = nearbyID;
						}
					}

					if (multipleNearbyLines || renderAtSurfaceEdge)
					{
						// Another line is too close, don't try to calculate width here
						// Or the render result is outside of surface range
						previousPixelUndefined = true;
						continue;
					}
				}

				// Only line with id of lineID is nearby

				if (previousPixelUndefined)
				{
					// The line might have been overdrawn or not
					currentLine = lineID;
					currentWidth = 1;
					fullyVisibleLine = false;
					previousPixelUndefined = false;
				}
				else if (lineID == currentLine)
				{
					// Current line continues
					++currentWidth;
				}
				else if (lineID > currentLine)
				{
					// Another line was drawn over or the line ends
					currentLine = lineID;
					currentWidth = 1;
					fullyVisibleLine = true;
				}
				else
				{
					// The line ends
					if (fullyVisibleLine && lineIsXMajor[currentLine-1])
					{
						// check width
						if (currentWidth != lineWidth)
						{
							log << tcu::TestLog::Message << "\tInvalid line width at (" << x << ", " << y - currentWidth << ") - (" << x  << ", " << y - 1 << "). Detected width of " << currentWidth << ", expected " << lineWidth << tcu::TestLog::EndMessage;
							invalidWidthFound = true;
						}
					}

					currentLine = lineID;
					currentWidth = 1;
					fullyVisibleLine = false;
				}
			}
		}

		if (invalidWidthFound)
		{
			log << tcu::TestLog::Message << "Invalid line width found, image is not valid." << tcu::TestLog::EndMessage;
			allOK = false;
		}
		else
		{
			log << tcu::TestLog::Message << "Line widths are valid." << tcu::TestLog::EndMessage;
		}
	}

	//\todo [2013-10-24 jarkko].
	//Requirement 4. If two line segments share a common endpoint, and both segments are either
	//x-major (both left-to-right or both right-to-left) or y-major (both bottom-totop
	//or both top-to-bottom), then rasterizing both segments may not produce
	//duplicate fragments, nor may any fragments be omitted so as to interrupt
	//continuity of the connected segments.

	if (!imageShown)
	{
		log << tcu::TestLog::ImageSet("Verification result", "Result of rendering")
			<< tcu::TestLog::Image("Result", "Result", surface)
			<< tcu::TestLog::EndImageSet;
	}

	return allOK;
}

struct SingleSampleNarrowLineCandidate
{
	int			lineNdx;
	tcu::IVec3	colorMin;
	tcu::IVec3	colorMax;
	tcu::Vec3	colorMinF;
	tcu::Vec3	colorMaxF;
	tcu::Vec3	valueRangeMin;
	tcu::Vec3	valueRangeMax;
};

void setMaskMapCoverageBitForLine (int bitNdx, const tcu::Vec2& screenSpaceP0, const tcu::Vec2& screenSpaceP1, float lineWidth, tcu::PixelBufferAccess maskMap)
{
	enum
	{
		MAX_PACKETS = 32,
	};

	rr::SingleSampleLineRasterizer	rasterizer				(tcu::IVec4(0, 0, maskMap.getWidth(), maskMap.getHeight()));
	int								numRasterized			= MAX_PACKETS;
	rr::FragmentPacket				packets[MAX_PACKETS];

	rasterizer.init(tcu::Vec4(screenSpaceP0.x(), screenSpaceP0.y(), 0.0f, 1.0f),
					tcu::Vec4(screenSpaceP1.x(), screenSpaceP1.y(), 0.0f, 1.0f),
					lineWidth);

	while (numRasterized == MAX_PACKETS)
	{
		rasterizer.rasterize(packets, DE_NULL, MAX_PACKETS, numRasterized);

		for (int packetNdx = 0; packetNdx < numRasterized; ++packetNdx)
		{
			for (int fragNdx = 0; fragNdx < 4; ++fragNdx)
			{
				if ((deUint32)packets[packetNdx].coverage & (1 << fragNdx))
				{
					const tcu::IVec2	fragPos			= packets[packetNdx].position + tcu::IVec2(fragNdx%2, fragNdx/2);

					DE_ASSERT(deInBounds32(fragPos.x(), 0, maskMap.getWidth()));
					DE_ASSERT(deInBounds32(fragPos.y(), 0, maskMap.getHeight()));

					const deUint32		previousMask	= maskMap.getPixelUint(fragPos.x(), fragPos.y()).x();
					const deUint32		newMask			= (previousMask) | ((deUint32)1u << bitNdx);

					maskMap.setPixel(tcu::UVec4(newMask, 0, 0, 0), fragPos.x(), fragPos.y());
				}
			}
		}
	}
}

void setMaskMapCoverageBitForLines (const std::vector<tcu::Vec4>& screenspaceLines, float lineWidth, tcu::PixelBufferAccess maskMap)
{
	for (int lineNdx = 0; lineNdx < (int)screenspaceLines.size(); ++lineNdx)
	{
		const tcu::Vec2 pa = screenspaceLines[lineNdx].swizzle(0, 1);
		const tcu::Vec2 pb = screenspaceLines[lineNdx].swizzle(2, 3);

		setMaskMapCoverageBitForLine(lineNdx, pa, pb, lineWidth, maskMap);
	}
}

// verify line interpolation assuming line pixels are interpolated independently depending only on screen space location
bool verifyLineGroupPixelIndependentInterpolation (const tcu::Surface&				surface,
												   const LineSceneSpec&				scene,
												   const RasterizationArguments&	args,
												   tcu::TestLog&					log,
												   LineInterpolationMethod			interpolationMethod)
{
	DE_ASSERT(scene.lines.size() < 8); // coverage indices are stored as bitmask in a unsigned 8-bit ints
	DE_ASSERT(interpolationMethod == LINEINTERPOLATION_STRICTLY_CORRECT || interpolationMethod == LINEINTERPOLATION_PROJECTED);

	const tcu::RGBA			invalidPixelColor	= tcu::RGBA(255, 0, 0, 255);
	const tcu::IVec2		viewportSize		= tcu::IVec2(surface.getWidth(), surface.getHeight());
	const int				errorFloodThreshold	= 4;
	int						errorCount			= 0;
	tcu::Surface			errorMask			(surface.getWidth(), surface.getHeight());
	int						invalidPixels		= 0;
	std::vector<tcu::Vec4>	screenspaceLines	(scene.lines.size()); //!< packed (x0, y0, x1, y1)

	// Reference renderer produces correct fragments using the diamond-exit-rule. Make 2D int array, store line coverage as a 8-bit bitfield
	// The map is used to find lines with potential coverage to a given pixel
	tcu::TextureLevel		referenceLineMap	(tcu::TextureFormat(tcu::TextureFormat::R, tcu::TextureFormat::UNSIGNED_INT8), surface.getWidth(), surface.getHeight());

	tcu::clear(referenceLineMap.getAccess(), tcu::IVec4(0, 0, 0, 0));
	tcu::clear(errorMask.getAccess(), tcu::Vec4(0.0f, 0.0f, 0.0f, 1.0f));

	// log format

	log << tcu::TestLog::Message << "Verifying rasterization result. Native format is RGB" << args.redBits << args.greenBits << args.blueBits << tcu::TestLog::EndMessage;
	if (args.redBits > 8 || args.greenBits > 8 || args.blueBits > 8)
		log << tcu::TestLog::Message << "Warning! More than 8 bits in a color channel, this may produce false negatives." << tcu::TestLog::EndMessage;

	// prepare lookup map

	genScreenSpaceLines(screenspaceLines, scene.lines, viewportSize);
	setMaskMapCoverageBitForLines(screenspaceLines, scene.lineWidth, referenceLineMap.getAccess());

	// Find all possible lines with coverage, check pixel color matches one of them

	for (int y = 1; y < surface.getHeight() - 1; ++y)
	for (int x = 1; x < surface.getWidth()  - 1; ++x)
	{
		const tcu::RGBA		color					= surface.getPixel(x, y);
		const tcu::IVec3	pixelNativeColor		= convertRGB8ToNativeFormat(color, args);	// Convert pixel color from rgba8 to the real pixel format. Usually rgba8 or 565
		int					lineCoverageSet			= 0;										// !< lines that may cover this fragment
		int					lineSurroundingCoverage = 0xFFFF;									// !< lines that will cover this fragment
		bool				matchFound				= false;
		const tcu::IVec3	formatLimit				((1 << args.redBits) - 1, (1 << args.greenBits) - 1, (1 << args.blueBits) - 1);

		std::vector<SingleSampleNarrowLineCandidate> candidates;

		// Find lines with possible coverage

		for (int dy = -1; dy < 2; ++dy)
		for (int dx = -1; dx < 2; ++dx)
		{
			const int coverage = referenceLineMap.getAccess().getPixelInt(x+dx, y+dy).x();

			lineCoverageSet			|= coverage;
			lineSurroundingCoverage	&= coverage;
		}

		// background color is possible?
		if (lineSurroundingCoverage == 0 && compareColors(color, tcu::RGBA::black(), args.redBits, args.greenBits, args.blueBits))
			continue;

		// Check those lines

		for (int lineNdx = 0; lineNdx < (int)scene.lines.size(); ++lineNdx)
		{
			if (((lineCoverageSet >> lineNdx) & 0x01) != 0)
			{
				const float						wa				= scene.lines[lineNdx].positions[0].w();
				const float						wb				= scene.lines[lineNdx].positions[1].w();
				const tcu::Vec2					pa				= screenspaceLines[lineNdx].swizzle(0, 1);
				const tcu::Vec2					pb				= screenspaceLines[lineNdx].swizzle(2, 3);

				const LineInterpolationRange	range			= (interpolationMethod == LINEINTERPOLATION_STRICTLY_CORRECT)
																	? (calcSingleSampleLineInterpolationRange(pa, wa, pb, wb, tcu::IVec2(x, y), args.subpixelBits))
																	: (calcSingleSampleLineInterpolationRangeAxisProjected(pa, wa, pb, wb, tcu::IVec2(x, y), args.subpixelBits));

				const tcu::Vec4					valueMin		= de::clamp(range.min.x(), 0.0f, 1.0f) * scene.lines[lineNdx].colors[0] + de::clamp(range.min.y(), 0.0f, 1.0f) * scene.lines[lineNdx].colors[1];
				const tcu::Vec4					valueMax		= de::clamp(range.max.x(), 0.0f, 1.0f) * scene.lines[lineNdx].colors[0] + de::clamp(range.max.y(), 0.0f, 1.0f) * scene.lines[lineNdx].colors[1];

				const tcu::Vec3					colorMinF		(de::clamp(valueMin.x() * (float)formatLimit.x(), 0.0f, (float)formatLimit.x()),
																 de::clamp(valueMin.y() * (float)formatLimit.y(), 0.0f, (float)formatLimit.y()),
																 de::clamp(valueMin.z() * (float)formatLimit.z(), 0.0f, (float)formatLimit.z()));
				const tcu::Vec3					colorMaxF		(de::clamp(valueMax.x() * (float)formatLimit.x(), 0.0f, (float)formatLimit.x()),
																 de::clamp(valueMax.y() * (float)formatLimit.y(), 0.0f, (float)formatLimit.y()),
																 de::clamp(valueMax.z() * (float)formatLimit.z(), 0.0f, (float)formatLimit.z()));
				const tcu::IVec3				colorMin		((int)deFloatFloor(colorMinF.x()),
																 (int)deFloatFloor(colorMinF.y()),
																 (int)deFloatFloor(colorMinF.z()));
				const tcu::IVec3				colorMax		((int)deFloatCeil (colorMaxF.x()),
																 (int)deFloatCeil (colorMaxF.y()),
																 (int)deFloatCeil (colorMaxF.z()));

				// Verify validity
				if (pixelNativeColor.x() < colorMin.x() ||
					pixelNativeColor.y() < colorMin.y() ||
					pixelNativeColor.z() < colorMin.z() ||
					pixelNativeColor.x() > colorMax.x() ||
					pixelNativeColor.y() > colorMax.y() ||
					pixelNativeColor.z() > colorMax.z())
				{
					if (errorCount < errorFloodThreshold)
					{
						// Store candidate information for logging
						SingleSampleNarrowLineCandidate candidate;

						candidate.lineNdx		= lineNdx;
						candidate.colorMin		= colorMin;
						candidate.colorMax		= colorMax;
						candidate.colorMinF		= colorMinF;
						candidate.colorMaxF		= colorMaxF;
						candidate.valueRangeMin	= valueMin.swizzle(0, 1, 2);
						candidate.valueRangeMax	= valueMax.swizzle(0, 1, 2);

						candidates.push_back(candidate);
					}
				}
				else
				{
					matchFound = true;
					break;
				}
			}
		}

		if (matchFound)
			continue;

		// invalid fragment
		++invalidPixels;
		errorMask.setPixel(x, y, invalidPixelColor);

		++errorCount;

		// don't fill the logs with too much data
		if (errorCount < errorFloodThreshold)
		{
			log << tcu::TestLog::Message
				<< "Found an invalid pixel at (" << x << "," << y << "), " << (int)candidates.size() << " candidate reference value(s) found:\n"
				<< "\tPixel color:\t\t" << color << "\n"
				<< "\tNative color:\t\t" << pixelNativeColor << "\n"
				<< tcu::TestLog::EndMessage;

			for (int candidateNdx = 0; candidateNdx < (int)candidates.size(); ++candidateNdx)
			{
				const SingleSampleNarrowLineCandidate& candidate = candidates[candidateNdx];

				log << tcu::TestLog::Message << "\tCandidate (line " << candidate.lineNdx << "):\n"
					<< "\t\tReference native color min: " << tcu::clamp(candidate.colorMin, tcu::IVec3(0,0,0), formatLimit) << "\n"
					<< "\t\tReference native color max: " << tcu::clamp(candidate.colorMax, tcu::IVec3(0,0,0), formatLimit) << "\n"
					<< "\t\tReference native float min: " << tcu::clamp(candidate.colorMinF, tcu::Vec3(0.0f, 0.0f, 0.0f), formatLimit.cast<float>()) << "\n"
					<< "\t\tReference native float max: " << tcu::clamp(candidate.colorMaxF, tcu::Vec3(0.0f, 0.0f, 0.0f), formatLimit.cast<float>()) << "\n"
					<< "\t\tFmin:\t" << tcu::clamp(candidate.valueRangeMin, tcu::Vec3(0.0f, 0.0f, 0.0f), tcu::Vec3(1.0f, 1.0f, 1.0f)) << "\n"
					<< "\t\tFmax:\t" << tcu::clamp(candidate.valueRangeMax, tcu::Vec3(0.0f, 0.0f, 0.0f), tcu::Vec3(1.0f, 1.0f, 1.0f)) << "\n"
					<< tcu::TestLog::EndMessage;
			}
		}
	}

	// don't just hide failures
	if (errorCount > errorFloodThreshold)
		log << tcu::TestLog::Message << "Omitted " << (errorCount-errorFloodThreshold) << " pixel error description(s)." << tcu::TestLog::EndMessage;

	// report result
	if (invalidPixels)
	{
		log << tcu::TestLog::Message << invalidPixels << " invalid pixel(s) found." << tcu::TestLog::EndMessage;
		log << tcu::TestLog::ImageSet("Verification result", "Result of rendering")
			<< tcu::TestLog::Image("Result", "Result",			surface)
			<< tcu::TestLog::Image("ErrorMask", "ErrorMask",	errorMask)
			<< tcu::TestLog::EndImageSet;

		return false;
	}
	else
	{
		log << tcu::TestLog::Message << "No invalid pixels found." << tcu::TestLog::EndMessage;
		log << tcu::TestLog::ImageSet("Verification result", "Result of rendering")
			<< tcu::TestLog::Image("Result", "Result", surface)
			<< tcu::TestLog::EndImageSet;

		return true;
	}
}

bool verifySinglesampleNarrowLineGroupInterpolation (const tcu::Surface& surface, const LineSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log)
{
	DE_ASSERT(scene.lineWidth == 1.0f);
	return verifyLineGroupPixelIndependentInterpolation(surface, scene, args, log, LINEINTERPOLATION_STRICTLY_CORRECT);
}

bool verifyLineGroupInterpolationWithProjectedWeights (const tcu::Surface& surface, const LineSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log)
{
	return verifyLineGroupPixelIndependentInterpolation(surface, scene, args, log, LINEINTERPOLATION_PROJECTED);
}

struct SingleSampleWideLineCandidate
{
	struct InterpolationPointCandidate
	{
		tcu::IVec2	interpolationPoint;
		tcu::IVec3	colorMin;
		tcu::IVec3	colorMax;
		tcu::Vec3	colorMinF;
		tcu::Vec3	colorMaxF;
		tcu::Vec3	valueRangeMin;
		tcu::Vec3	valueRangeMax;
	};

	int							lineNdx;
	int							numCandidates;
	InterpolationPointCandidate	interpolationCandidates[3];
};

// return point on line at a given position on a given axis
tcu::Vec2 getLineCoordAtAxisCoord (const tcu::Vec2& pa, const tcu::Vec2& pb, bool isXAxis, float axisCoord)
{
	const int	fixedCoordNdx		= (isXAxis) ? (0) : (1);
	const int	varyingCoordNdx		= (isXAxis) ? (1) : (0);

	const float	fixedDifference		= pb[fixedCoordNdx] - pa[fixedCoordNdx];
	const float	varyingDifference	= pb[varyingCoordNdx] - pa[varyingCoordNdx];

	DE_ASSERT(fixedDifference != 0.0f);

	const float	resultFixedCoord	= axisCoord;
	const float	resultVaryingCoord	= pa[varyingCoordNdx] + (axisCoord - pa[fixedCoordNdx]) * (varyingDifference / fixedDifference);

	return (isXAxis) ? (tcu::Vec2(resultFixedCoord, resultVaryingCoord))
					 : (tcu::Vec2(resultVaryingCoord, resultFixedCoord));
}

bool isBlack (const tcu::RGBA& c)
{
	return c.getRed() == 0 && c.getGreen() == 0 && c.getBlue() == 0;
}

bool verifySinglesampleWideLineGroupInterpolation (const tcu::Surface& surface, const LineSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log)
{
	DE_ASSERT(deFloatFrac(scene.lineWidth) != 0.5f); // rounding direction is not defined, disallow undefined cases
	DE_ASSERT(scene.lines.size() < 8); // coverage indices are stored as bitmask in a unsigned 8-bit ints

	enum
	{
		FLAG_ROOT_NOT_SET = (1u << 16)
	};

	const tcu::RGBA						invalidPixelColor	= tcu::RGBA(255, 0, 0, 255);
	const tcu::IVec2					viewportSize		= tcu::IVec2(surface.getWidth(), surface.getHeight());
	const int							errorFloodThreshold	= 4;
	int									errorCount			= 0;
	tcu::Surface						errorMask			(surface.getWidth(), surface.getHeight());
	int									invalidPixels		= 0;
	std::vector<tcu::Vec4>				effectiveLines		(scene.lines.size()); //!< packed (x0, y0, x1, y1)
	std::vector<bool>					lineIsXMajor		(scene.lines.size());

	// for each line, for every distinct major direction fragment, store root pixel location (along
	// minor direction);
	std::vector<std::vector<deUint32> >	rootPixelLocation	(scene.lines.size()); //!< packed [16b - flags] [16b - coordinate]

	// log format

	log << tcu::TestLog::Message << "Verifying rasterization result. Native format is RGB" << args.redBits << args.greenBits << args.blueBits << tcu::TestLog::EndMessage;
	if (args.redBits > 8 || args.greenBits > 8 || args.blueBits > 8)
		log << tcu::TestLog::Message << "Warning! More than 8 bits in a color channel, this may produce false negatives." << tcu::TestLog::EndMessage;

	// Reference renderer produces correct fragments using the diamond-exit-rule. Make 2D int array, store line coverage as a 8-bit bitfield
	// The map is used to find lines with potential coverage to a given pixel
	tcu::TextureLevel referenceLineMap(tcu::TextureFormat(tcu::TextureFormat::R, tcu::TextureFormat::UNSIGNED_INT8), surface.getWidth(), surface.getHeight());
	tcu::clear(referenceLineMap.getAccess(), tcu::IVec4(0, 0, 0, 0));

	tcu::clear(errorMask.getAccess(), tcu::Vec4(0.0f, 0.0f, 0.0f, 1.0f));

	// calculate mask and effective line coordinates
	{
		std::vector<tcu::Vec4> screenspaceLines(scene.lines.size());

		genScreenSpaceLines(screenspaceLines, scene.lines, viewportSize);
		setMaskMapCoverageBitForLines(screenspaceLines, scene.lineWidth, referenceLineMap.getAccess());

		for (int lineNdx = 0; lineNdx < (int)scene.lines.size(); ++lineNdx)
		{
			const tcu::Vec2	lineScreenSpaceP0	= screenspaceLines[lineNdx].swizzle(0, 1);
			const tcu::Vec2	lineScreenSpaceP1	= screenspaceLines[lineNdx].swizzle(2, 3);
			const bool		isXMajor			= isPackedSSLineXMajor(screenspaceLines[lineNdx]);

			lineIsXMajor[lineNdx] = isXMajor;

			// wide line interpolations are calculated for a line moved in minor direction
			{
				const float		offsetLength	= (scene.lineWidth - 1.0f) / 2.0f;
				const tcu::Vec2	offsetDirection	= (isXMajor) ? (tcu::Vec2(0.0f, -1.0f)) : (tcu::Vec2(-1.0f, 0.0f));
				const tcu::Vec2	offset			= offsetDirection * offsetLength;

				effectiveLines[lineNdx] = tcu::Vec4(lineScreenSpaceP0.x() + offset.x(),
													lineScreenSpaceP0.y() + offset.y(),
													lineScreenSpaceP1.x() + offset.x(),
													lineScreenSpaceP1.y() + offset.y());
			}
		}
	}

	for (int lineNdx = 0; lineNdx < (int)scene.lines.size(); ++lineNdx)
	{
		// Calculate root pixel lookup table for this line. Since the implementation's fragment
		// major coordinate range might not be a subset of the correct line range (they are allowed
		// to vary by one pixel), we must extend the domain to cover whole viewport along major
		// dimension.
		//
		// Expanding line strip to (effectively) infinite line might result in exit-diamnod set
		// that is not a superset of the exit-diamond set of the line strip. In practice, this
		// won't be an issue, since the allow-one-pixel-variation rule should tolerate this even
		// if the original and extended line would resolve differently a diamond the line just
		// touches (precision lost in expansion changes enter/exit status).

		{
			const bool						isXMajor			= lineIsXMajor[lineNdx];
			const int						majorSize			= (isXMajor) ? (surface.getWidth()) : (surface.getHeight());
			rr::LineExitDiamondGenerator	diamondGenerator;
			rr::LineExitDiamond				diamonds[32];
			int								numRasterized		= DE_LENGTH_OF_ARRAY(diamonds);

			// Expand to effectively infinite line (endpoints are just one pixel over viewport boundaries)
			const tcu::Vec2					expandedP0		= getLineCoordAtAxisCoord(effectiveLines[lineNdx].swizzle(0, 1), effectiveLines[lineNdx].swizzle(2, 3), isXMajor, -1.0f);
			const tcu::Vec2					expandedP1		= getLineCoordAtAxisCoord(effectiveLines[lineNdx].swizzle(0, 1), effectiveLines[lineNdx].swizzle(2, 3), isXMajor, (float)majorSize + 1.0f);

			diamondGenerator.init(tcu::Vec4(expandedP0.x(), expandedP0.y(), 0.0f, 1.0f),
								  tcu::Vec4(expandedP1.x(), expandedP1.y(), 0.0f, 1.0f));

			rootPixelLocation[lineNdx].resize(majorSize, FLAG_ROOT_NOT_SET);

			while (numRasterized == DE_LENGTH_OF_ARRAY(diamonds))
			{
				diamondGenerator.rasterize(diamonds, DE_LENGTH_OF_ARRAY(diamonds), numRasterized);

				for (int packetNdx = 0; packetNdx < numRasterized; ++packetNdx)
				{
					const tcu::IVec2	fragPos			= diamonds[packetNdx].position;
					const int			majorPos		= (isXMajor) ? (fragPos.x()) : (fragPos.y());
					const int			rootPos			= (isXMajor) ? (fragPos.y()) : (fragPos.x());
					const deUint32		packed			= (deUint32)((deUint16)((deInt16)rootPos));

					// infinite line will generate some diamonds outside the viewport
					if (deInBounds32(majorPos, 0, majorSize))
					{
						DE_ASSERT((rootPixelLocation[lineNdx][majorPos] & FLAG_ROOT_NOT_SET) != 0u);
						rootPixelLocation[lineNdx][majorPos] = packed;
					}
				}
			}

			// Filled whole lookup table
			for (int majorPos = 0; majorPos < majorSize; ++majorPos)
				DE_ASSERT((rootPixelLocation[lineNdx][majorPos] & FLAG_ROOT_NOT_SET) == 0u);
		}
	}

	// Find all possible lines with coverage, check pixel color matches one of them

	for (int y = 1; y < surface.getHeight() - 1; ++y)
	for (int x = 1; x < surface.getWidth()  - 1; ++x)
	{
		const tcu::RGBA		color					= surface.getPixel(x, y);
		const tcu::IVec3	pixelNativeColor		= convertRGB8ToNativeFormat(color, args);	// Convert pixel color from rgba8 to the real pixel format. Usually rgba8 or 565
		int					lineCoverageSet			= 0;										// !< lines that may cover this fragment
		int					lineSurroundingCoverage = 0xFFFF;									// !< lines that will cover this fragment
		bool				matchFound				= false;
		const tcu::IVec3	formatLimit				((1 << args.redBits) - 1, (1 << args.greenBits) - 1, (1 << args.blueBits) - 1);

		std::vector<SingleSampleWideLineCandidate> candidates;

		// Find lines with possible coverage

		for (int dy = -1; dy < 2; ++dy)
		for (int dx = -1; dx < 2; ++dx)
		{
			const int coverage = referenceLineMap.getAccess().getPixelInt(x+dx, y+dy).x();

			lineCoverageSet			|= coverage;
			lineSurroundingCoverage	&= coverage;
		}

		// background color is possible?
		if (lineSurroundingCoverage == 0 && compareColors(color, tcu::RGBA::black(), args.redBits, args.greenBits, args.blueBits))
			continue;

		// Check those lines

		for (int lineNdx = 0; lineNdx < (int)scene.lines.size(); ++lineNdx)
		{
			if (((lineCoverageSet >> lineNdx) & 0x01) != 0)
			{
				const float						wa				= scene.lines[lineNdx].positions[0].w();
				const float						wb				= scene.lines[lineNdx].positions[1].w();
				const tcu::Vec2					pa				= effectiveLines[lineNdx].swizzle(0, 1);
				const tcu::Vec2					pb				= effectiveLines[lineNdx].swizzle(2, 3);

				// \note Wide line fragments are generated by replicating the root fragment for each
				//       fragment column (row for y-major). Calculate interpolation at the root
				//       fragment.
				const bool						isXMajor		= lineIsXMajor[lineNdx];
				const int						majorPosition	= (isXMajor) ? (x) : (y);
				const deUint32					minorInfoPacked	= rootPixelLocation[lineNdx][majorPosition];
				const int						minorPosition	= (int)((deInt16)((deUint16)(minorInfoPacked & 0xFFFFu)));
				const tcu::IVec2				idealRootPos	= (isXMajor) ? (tcu::IVec2(majorPosition, minorPosition)) : (tcu::IVec2(minorPosition, majorPosition));
				const tcu::IVec2				minorDirection	= (isXMajor) ? (tcu::IVec2(0, 1)) : (tcu::IVec2(1, 0));

				SingleSampleWideLineCandidate	candidate;

				candidate.lineNdx		= lineNdx;
				candidate.numCandidates	= 0;
				DE_STATIC_ASSERT(DE_LENGTH_OF_ARRAY(candidate.interpolationCandidates) == 3);

				// Interpolation happens at the root fragment, which is then replicated in minor
				// direction. Search for implementation's root position near accurate root.
				for (int minorOffset = -1; minorOffset < 2; ++minorOffset)
				{
					const tcu::IVec2				rootPosition	= idealRootPos + minorOffset * minorDirection;

					// A fragment can be root fragment only if it exists
					// \note root fragment can "exist" outside viewport
					// \note no pixel format theshold since in this case allowing only black is more conservative
					if (deInBounds32(rootPosition.x(), 0, surface.getWidth()) &&
						deInBounds32(rootPosition.y(), 0, surface.getHeight()) &&
						isBlack(surface.getPixel(rootPosition.x(), rootPosition.y())))
					{
						continue;
					}

					const LineInterpolationRange	range			= calcSingleSampleLineInterpolationRange(pa, wa, pb, wb, rootPosition, args.subpixelBits);

					const tcu::Vec4					valueMin		= de::clamp(range.min.x(), 0.0f, 1.0f) * scene.lines[lineNdx].colors[0] + de::clamp(range.min.y(), 0.0f, 1.0f) * scene.lines[lineNdx].colors[1];
					const tcu::Vec4					valueMax		= de::clamp(range.max.x(), 0.0f, 1.0f) * scene.lines[lineNdx].colors[0] + de::clamp(range.max.y(), 0.0f, 1.0f) * scene.lines[lineNdx].colors[1];

					const tcu::Vec3					colorMinF		(de::clamp(valueMin.x() * (float)formatLimit.x(), 0.0f, (float)formatLimit.x()),
																	 de::clamp(valueMin.y() * (float)formatLimit.y(), 0.0f, (float)formatLimit.y()),
																	 de::clamp(valueMin.z() * (float)formatLimit.z(), 0.0f, (float)formatLimit.z()));
					const tcu::Vec3					colorMaxF		(de::clamp(valueMax.x() * (float)formatLimit.x(), 0.0f, (float)formatLimit.x()),
																	 de::clamp(valueMax.y() * (float)formatLimit.y(), 0.0f, (float)formatLimit.y()),
																	 de::clamp(valueMax.z() * (float)formatLimit.z(), 0.0f, (float)formatLimit.z()));
					const tcu::IVec3				colorMin		((int)deFloatFloor(colorMinF.x()),
																	 (int)deFloatFloor(colorMinF.y()),
																	 (int)deFloatFloor(colorMinF.z()));
					const tcu::IVec3				colorMax		((int)deFloatCeil (colorMaxF.x()),
																	 (int)deFloatCeil (colorMaxF.y()),
																	 (int)deFloatCeil (colorMaxF.z()));

					// Verify validity
					if (pixelNativeColor.x() < colorMin.x() ||
						pixelNativeColor.y() < colorMin.y() ||
						pixelNativeColor.z() < colorMin.z() ||
						pixelNativeColor.x() > colorMax.x() ||
						pixelNativeColor.y() > colorMax.y() ||
						pixelNativeColor.z() > colorMax.z())
					{
						if (errorCount < errorFloodThreshold)
						{
							// Store candidate information for logging
							SingleSampleWideLineCandidate::InterpolationPointCandidate& interpolationCandidate = candidate.interpolationCandidates[candidate.numCandidates++];
							DE_ASSERT(candidate.numCandidates <= DE_LENGTH_OF_ARRAY(candidate.interpolationCandidates));

							interpolationCandidate.interpolationPoint	= rootPosition;
							interpolationCandidate.colorMin				= colorMin;
							interpolationCandidate.colorMax				= colorMax;
							interpolationCandidate.colorMinF			= colorMinF;
							interpolationCandidate.colorMaxF			= colorMaxF;
							interpolationCandidate.valueRangeMin		= valueMin.swizzle(0, 1, 2);
							interpolationCandidate.valueRangeMax		= valueMax.swizzle(0, 1, 2);
						}
					}
					else
					{
						matchFound = true;
						break;
					}
				}

				if (!matchFound)
				{
					// store info for logging
					if (errorCount < errorFloodThreshold && candidate.numCandidates > 0)
						candidates.push_back(candidate);
				}
				else
				{
					// no need to check other lines
					break;
				}
			}
		}

		if (matchFound)
			continue;

		// invalid fragment
		++invalidPixels;
		errorMask.setPixel(x, y, invalidPixelColor);

		++errorCount;

		// don't fill the logs with too much data
		if (errorCount < errorFloodThreshold)
		{
			tcu::MessageBuilder msg(&log);

			msg	<< "Found an invalid pixel at (" << x << "," << y << "), " << (int)candidates.size() << " candidate reference value(s) found:\n"
				<< "\tPixel color:\t\t" << color << "\n"
				<< "\tNative color:\t\t" << pixelNativeColor << "\n";

			for (int lineCandidateNdx = 0; lineCandidateNdx < (int)candidates.size(); ++lineCandidateNdx)
			{
				const SingleSampleWideLineCandidate& candidate = candidates[lineCandidateNdx];

				msg << "\tCandidate line (line " << candidate.lineNdx << "):\n";

				for (int interpolationCandidateNdx = 0; interpolationCandidateNdx < candidate.numCandidates; ++interpolationCandidateNdx)
				{
					const SingleSampleWideLineCandidate::InterpolationPointCandidate& interpolationCandidate = candidate.interpolationCandidates[interpolationCandidateNdx];

					msg	<< "\t\tCandidate interpolation point (index " << interpolationCandidateNdx << "):\n"
						<< "\t\t\tRoot fragment position (non-replicated fragment): " << interpolationCandidate.interpolationPoint << ":\n"
						<< "\t\t\tReference native color min: " << tcu::clamp(interpolationCandidate.colorMin, tcu::IVec3(0,0,0), formatLimit) << "\n"
						<< "\t\t\tReference native color max: " << tcu::clamp(interpolationCandidate.colorMax, tcu::IVec3(0,0,0), formatLimit) << "\n"
						<< "\t\t\tReference native float min: " << tcu::clamp(interpolationCandidate.colorMinF, tcu::Vec3(0.0f, 0.0f, 0.0f), formatLimit.cast<float>()) << "\n"
						<< "\t\t\tReference native float max: " << tcu::clamp(interpolationCandidate.colorMaxF, tcu::Vec3(0.0f, 0.0f, 0.0f), formatLimit.cast<float>()) << "\n"
						<< "\t\t\tFmin:\t" << tcu::clamp(interpolationCandidate.valueRangeMin, tcu::Vec3(0.0f, 0.0f, 0.0f), tcu::Vec3(1.0f, 1.0f, 1.0f)) << "\n"
						<< "\t\t\tFmax:\t" << tcu::clamp(interpolationCandidate.valueRangeMax, tcu::Vec3(0.0f, 0.0f, 0.0f), tcu::Vec3(1.0f, 1.0f, 1.0f)) << "\n";
				}
			}

			msg << tcu::TestLog::EndMessage;
		}
	}

	// don't just hide failures
	if (errorCount > errorFloodThreshold)
		log << tcu::TestLog::Message << "Omitted " << (errorCount-errorFloodThreshold) << " pixel error description(s)." << tcu::TestLog::EndMessage;

	// report result
	if (invalidPixels)
	{
		log << tcu::TestLog::Message << invalidPixels << " invalid pixel(s) found." << tcu::TestLog::EndMessage;
		log << tcu::TestLog::ImageSet("Verification result", "Result of rendering")
			<< tcu::TestLog::Image("Result", "Result",			surface)
			<< tcu::TestLog::Image("ErrorMask", "ErrorMask",	errorMask)
			<< tcu::TestLog::EndImageSet;

		return false;
	}
	else
	{
		log << tcu::TestLog::Message << "No invalid pixels found." << tcu::TestLog::EndMessage;
		log << tcu::TestLog::ImageSet("Verification result", "Result of rendering")
			<< tcu::TestLog::Image("Result", "Result", surface)
			<< tcu::TestLog::EndImageSet;

		return true;
	}
}

} // anonymous

CoverageType calculateTriangleCoverage (const tcu::Vec4& p0, const tcu::Vec4& p1, const tcu::Vec4& p2, const tcu::IVec2& pixel, const tcu::IVec2& viewportSize, int subpixelBits, bool multisample)
{
	typedef tcu::Vector<deInt64, 2> I64Vec2;

	const deUint64		numSubPixels						= ((deUint64)1) << subpixelBits;
	const deUint64		pixelHitBoxSize						= (multisample) ? (numSubPixels) : (2+2);	//!< allow 4 central (2x2) for non-multisample pixels. Rounding may move edges 1 subpixel to any direction.
	const bool			order								= isTriangleClockwise(p0, p1, p2);			//!< clockwise / counter-clockwise
	const tcu::Vec4&	orderedP0							= p0;										//!< vertices of a clockwise triangle
	const tcu::Vec4&	orderedP1							= (order) ? (p1) : (p2);
	const tcu::Vec4&	orderedP2							= (order) ? (p2) : (p1);
	const tcu::Vec2		triangleNormalizedDeviceSpace[3]	=
	{
		tcu::Vec2(orderedP0.x() / orderedP0.w(), orderedP0.y() / orderedP0.w()),
		tcu::Vec2(orderedP1.x() / orderedP1.w(), orderedP1.y() / orderedP1.w()),
		tcu::Vec2(orderedP2.x() / orderedP2.w(), orderedP2.y() / orderedP2.w()),
	};
	const tcu::Vec2		triangleScreenSpace[3]				=
	{
		(triangleNormalizedDeviceSpace[0] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * tcu::Vec2((float)viewportSize.x(), (float)viewportSize.y()),
		(triangleNormalizedDeviceSpace[1] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * tcu::Vec2((float)viewportSize.x(), (float)viewportSize.y()),
		(triangleNormalizedDeviceSpace[2] + tcu::Vec2(1.0f, 1.0f)) * 0.5f * tcu::Vec2((float)viewportSize.x(), (float)viewportSize.y()),
	};

	// Broad bounding box - pixel check
	{
		const float minX = de::min(de::min(triangleScreenSpace[0].x(), triangleScreenSpace[1].x()), triangleScreenSpace[2].x());
		const float minY = de::min(de::min(triangleScreenSpace[0].y(), triangleScreenSpace[1].y()), triangleScreenSpace[2].y());
		const float maxX = de::max(de::max(triangleScreenSpace[0].x(), triangleScreenSpace[1].x()), triangleScreenSpace[2].x());
		const float maxY = de::max(de::max(triangleScreenSpace[0].y(), triangleScreenSpace[1].y()), triangleScreenSpace[2].y());

		if ((float)pixel.x() > maxX + 1 ||
			(float)pixel.y() > maxY + 1 ||
			(float)pixel.x() < minX - 1 ||
			(float)pixel.y() < minY - 1)
			return COVERAGE_NONE;
	}

	// Broad triangle - pixel area intersection
	{
		const I64Vec2 pixelCenterPosition = I64Vec2(pixel.x(), pixel.y()) * I64Vec2(numSubPixels, numSubPixels) + I64Vec2(numSubPixels / 2, numSubPixels / 2);
		const I64Vec2 triangleSubPixelSpaceRound[3] =
		{
			I64Vec2(deRoundFloatToInt32(triangleScreenSpace[0].x() * (float)numSubPixels), deRoundFloatToInt32(triangleScreenSpace[0].y() * (float)numSubPixels)),
			I64Vec2(deRoundFloatToInt32(triangleScreenSpace[1].x() * (float)numSubPixels), deRoundFloatToInt32(triangleScreenSpace[1].y() * (float)numSubPixels)),
			I64Vec2(deRoundFloatToInt32(triangleScreenSpace[2].x() * (float)numSubPixels), deRoundFloatToInt32(triangleScreenSpace[2].y() * (float)numSubPixels)),
		};

		// Check (using cross product) if pixel center is
		// a) too far from any edge
		// b) fully inside all edges
		bool insideAllEdges = true;
		for (int vtxNdx = 0; vtxNdx < 3; ++vtxNdx)
		{
			const int		otherVtxNdx				= (vtxNdx + 1) % 3;
			const deInt64	maxPixelDistanceSquared	= pixelHitBoxSize*pixelHitBoxSize; // Max distance from the pixel center from within the pixel is (sqrt(2) * boxWidth/2). Use 2x value for rounding tolerance
			const I64Vec2	edge					= triangleSubPixelSpaceRound[otherVtxNdx]	- triangleSubPixelSpaceRound[vtxNdx];
			const I64Vec2	v						= pixelCenterPosition						- triangleSubPixelSpaceRound[vtxNdx];
			const deInt64	crossProduct			= (edge.x() * v.y() - edge.y() * v.x());

			// distance from edge: (edge x v) / |edge|
			//     (edge x v) / |edge| > maxPixelDistance
			// ==> (edge x v)^2 / edge^2 > maxPixelDistance^2    | edge x v > 0
			// ==> (edge x v)^2 > maxPixelDistance^2 * edge^2
			if (crossProduct < 0 && crossProduct*crossProduct > maxPixelDistanceSquared * tcu::lengthSquared(edge))
				return COVERAGE_NONE;
			if (crossProduct < 0 || crossProduct*crossProduct < maxPixelDistanceSquared * tcu::lengthSquared(edge))
				insideAllEdges = false;
		}

		if (insideAllEdges)
			return COVERAGE_FULL;
	}

	// Accurate intersection for edge pixels
	{
		//  In multisampling, the sample points can be anywhere in the pixel, and in single sampling only in the center.
		const I64Vec2 pixelCorners[4] =
		{
			I64Vec2((pixel.x()+0) * numSubPixels, (pixel.y()+0) * numSubPixels),
			I64Vec2((pixel.x()+1) * numSubPixels, (pixel.y()+0) * numSubPixels),
			I64Vec2((pixel.x()+1) * numSubPixels, (pixel.y()+1) * numSubPixels),
			I64Vec2((pixel.x()+0) * numSubPixels, (pixel.y()+1) * numSubPixels),
		};
		const I64Vec2 pixelCenterCorners[4] =
		{
			I64Vec2(pixel.x() * numSubPixels + numSubPixels/2 + 0, pixel.y() * numSubPixels + numSubPixels/2 + 0),
			I64Vec2(pixel.x() * numSubPixels + numSubPixels/2 + 1, pixel.y() * numSubPixels + numSubPixels/2 + 0),
			I64Vec2(pixel.x() * numSubPixels + numSubPixels/2 + 1, pixel.y() * numSubPixels + numSubPixels/2 + 1),
			I64Vec2(pixel.x() * numSubPixels + numSubPixels/2 + 0, pixel.y() * numSubPixels + numSubPixels/2 + 1),
		};

		// both rounding directions
		const I64Vec2 triangleSubPixelSpaceFloor[3] =
		{
			I64Vec2(deFloorFloatToInt32(triangleScreenSpace[0].x() * (float)numSubPixels), deFloorFloatToInt32(triangleScreenSpace[0].y() * (float)numSubPixels)),
			I64Vec2(deFloorFloatToInt32(triangleScreenSpace[1].x() * (float)numSubPixels), deFloorFloatToInt32(triangleScreenSpace[1].y() * (float)numSubPixels)),
			I64Vec2(deFloorFloatToInt32(triangleScreenSpace[2].x() * (float)numSubPixels), deFloorFloatToInt32(triangleScreenSpace[2].y() * (float)numSubPixels)),
		};
		const I64Vec2 triangleSubPixelSpaceCeil[3] =
		{
			I64Vec2(deCeilFloatToInt32(triangleScreenSpace[0].x() * (float)numSubPixels), deCeilFloatToInt32(triangleScreenSpace[0].y() * (float)numSubPixels)),
			I64Vec2(deCeilFloatToInt32(triangleScreenSpace[1].x() * (float)numSubPixels), deCeilFloatToInt32(triangleScreenSpace[1].y() * (float)numSubPixels)),
			I64Vec2(deCeilFloatToInt32(triangleScreenSpace[2].x() * (float)numSubPixels), deCeilFloatToInt32(triangleScreenSpace[2].y() * (float)numSubPixels)),
		};
		const I64Vec2* const corners = (multisample) ? (pixelCorners) : (pixelCenterCorners);

		// Test if any edge (with any rounding) intersects the pixel (boundary). If it does => Partial. If not => fully inside or outside

		for (int edgeNdx = 0; edgeNdx < 3; ++edgeNdx)
		for (int startRounding = 0; startRounding < 4; ++startRounding)
		for (int endRounding = 0; endRounding < 4; ++endRounding)
		{
			const int		nextEdgeNdx	= (edgeNdx+1) % 3;
			const I64Vec2	startPos	((startRounding&0x01)	? (triangleSubPixelSpaceFloor[edgeNdx].x())		: (triangleSubPixelSpaceCeil[edgeNdx].x()),		(startRounding&0x02)	? (triangleSubPixelSpaceFloor[edgeNdx].y())		: (triangleSubPixelSpaceCeil[edgeNdx].y()));
			const I64Vec2	endPos		((endRounding&0x01)		? (triangleSubPixelSpaceFloor[nextEdgeNdx].x())	: (triangleSubPixelSpaceCeil[nextEdgeNdx].x()),	(endRounding&0x02)		? (triangleSubPixelSpaceFloor[nextEdgeNdx].y())	: (triangleSubPixelSpaceCeil[nextEdgeNdx].y()));

			for (int pixelEdgeNdx = 0; pixelEdgeNdx < 4; ++pixelEdgeNdx)
			{
				const int pixelEdgeEnd = (pixelEdgeNdx + 1) % 4;

				if (lineLineIntersect(startPos, endPos, corners[pixelEdgeNdx], corners[pixelEdgeEnd]))
					return COVERAGE_PARTIAL;
			}
		}

		// fully inside or outside
		for (int edgeNdx = 0; edgeNdx < 3; ++edgeNdx)
		{
			const int		nextEdgeNdx		= (edgeNdx+1) % 3;
			const I64Vec2&	startPos		= triangleSubPixelSpaceFloor[edgeNdx];
			const I64Vec2&	endPos			= triangleSubPixelSpaceFloor[nextEdgeNdx];
			const I64Vec2	edge			= endPos - startPos;
			const I64Vec2	v				= corners[0] - endPos;
			const deInt64	crossProduct	= (edge.x() * v.y() - edge.y() * v.x());

			// a corner of the pixel is outside => "fully inside" option is impossible
			if (crossProduct < 0)
				return COVERAGE_NONE;
		}

		return COVERAGE_FULL;
	}
}

bool verifyTriangleGroupRasterization (const tcu::Surface& surface, const TriangleSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log, VerificationMode mode)
{
	DE_ASSERT(mode < VERIFICATIONMODE_LAST);

	const tcu::RGBA		backGroundColor				= tcu::RGBA(0, 0, 0, 255);
	const tcu::RGBA		triangleColor				= tcu::RGBA(255, 255, 255, 255);
	const tcu::RGBA		missingPixelColor			= tcu::RGBA(255, 0, 255, 255);
	const tcu::RGBA		unexpectedPixelColor		= tcu::RGBA(255, 0, 0, 255);
	const tcu::RGBA		partialPixelColor			= tcu::RGBA(255, 255, 0, 255);
	const tcu::RGBA		primitivePixelColor			= tcu::RGBA(30, 30, 30, 255);
	const int			weakVerificationThreshold	= 10;
	const bool			multisampled				= (args.numSamples != 0);
	const tcu::IVec2	viewportSize				= tcu::IVec2(surface.getWidth(), surface.getHeight());
	int					missingPixels				= 0;
	int					unexpectedPixels			= 0;
	int					subPixelBits				= args.subpixelBits;
	tcu::TextureLevel	coverageMap					(tcu::TextureFormat(tcu::TextureFormat::R, tcu::TextureFormat::UNSIGNED_INT8), surface.getWidth(), surface.getHeight());
	tcu::Surface		errorMask					(surface.getWidth(), surface.getHeight());

	// subpixel bits in in a valid range?

	if (subPixelBits < 0)
	{
		log << tcu::TestLog::Message << "Invalid subpixel count (" << subPixelBits << "), assuming 0" << tcu::TestLog::EndMessage;
		subPixelBits = 0;
	}
	else if (subPixelBits > 16)
	{
		// At high subpixel bit counts we might overflow. Checking at lower bit count is ok, but is less strict
		log << tcu::TestLog::Message << "Subpixel count is greater than 16 (" << subPixelBits << "). Checking results using less strict 16 bit requirements. This may produce false positives." << tcu::TestLog::EndMessage;
		subPixelBits = 16;
	}

	// generate coverage map

	tcu::clear(coverageMap.getAccess(), tcu::IVec4(COVERAGE_NONE, 0, 0, 0));

	for (int triNdx = 0; triNdx < (int)scene.triangles.size(); ++triNdx)
	{
		const tcu::IVec4 aabb = getTriangleAABB(scene.triangles[triNdx], viewportSize);

		for (int y = de::max(0, aabb.y()); y <= de::min(aabb.w(), coverageMap.getHeight() - 1); ++y)
		for (int x = de::max(0, aabb.x()); x <= de::min(aabb.z(), coverageMap.getWidth() - 1); ++x)
		{
			if (coverageMap.getAccess().getPixelUint(x, y).x() == COVERAGE_FULL)
				continue;

			const CoverageType coverage = calculateTriangleCoverage(scene.triangles[triNdx].positions[0],
																	scene.triangles[triNdx].positions[1],
																	scene.triangles[triNdx].positions[2],
																	tcu::IVec2(x, y),
																	viewportSize,
																	subPixelBits,
																	multisampled);

			if (coverage == COVERAGE_FULL)
			{
				coverageMap.getAccess().setPixel(tcu::IVec4(COVERAGE_FULL, 0, 0, 0), x, y);
			}
			else if (coverage == COVERAGE_PARTIAL)
			{
				CoverageType resultCoverage = COVERAGE_PARTIAL;

				// Sharing an edge with another triangle?
				// There should always be such a triangle, but the pixel in the other triangle might be
				// on multiple edges, some of which are not shared. In these cases the coverage cannot be determined.
				// Assume full coverage if the pixel is only on a shared edge in shared triangle too.
				if (pixelOnlyOnASharedEdge(tcu::IVec2(x, y), scene.triangles[triNdx], viewportSize))
				{
					bool friendFound = false;
					for (int friendTriNdx = 0; friendTriNdx < (int)scene.triangles.size(); ++friendTriNdx)
					{
						if (friendTriNdx != triNdx && pixelOnlyOnASharedEdge(tcu::IVec2(x, y), scene.triangles[friendTriNdx], viewportSize))
						{
							friendFound = true;
							break;
						}
					}

					if (friendFound)
						resultCoverage = COVERAGE_FULL;
				}

				coverageMap.getAccess().setPixel(tcu::IVec4(resultCoverage, 0, 0, 0), x, y);
			}
		}
	}

	// check pixels

	tcu::clear(errorMask.getAccess(), tcu::Vec4(0.0f, 0.0f, 0.0f, 1.0f));

	for (int y = 0; y < surface.getHeight(); ++y)
	for (int x = 0; x < surface.getWidth(); ++x)
	{
		const tcu::RGBA		color				= surface.getPixel(x, y);
		const bool			imageNoCoverage		= compareColors(color, backGroundColor, args.redBits, args.greenBits, args.blueBits);
		const bool			imageFullCoverage	= compareColors(color, triangleColor, args.redBits, args.greenBits, args.blueBits);
		CoverageType		referenceCoverage	= (CoverageType)coverageMap.getAccess().getPixelUint(x, y).x();

		switch (referenceCoverage)
		{
			case COVERAGE_NONE:
				if (!imageNoCoverage)
				{
					// coverage where there should not be
					++unexpectedPixels;
					errorMask.setPixel(x, y, unexpectedPixelColor);
				}
				break;

			case COVERAGE_PARTIAL:
				// anything goes
				errorMask.setPixel(x, y, partialPixelColor);
				break;

			case COVERAGE_FULL:
				if (!imageFullCoverage)
				{
					// no coverage where there should be
					++missingPixels;
					errorMask.setPixel(x, y, missingPixelColor);
				}
				else
				{
					errorMask.setPixel(x, y, primitivePixelColor);
				}
				break;

			default:
				DE_ASSERT(false);
		};
	}

	// Output results
	log << tcu::TestLog::Message << "Verifying rasterization result." << tcu::TestLog::EndMessage;

	if (((mode == VERIFICATIONMODE_STRICT) && (missingPixels + unexpectedPixels > 0)) ||
		((mode == VERIFICATIONMODE_WEAK)   && (missingPixels + unexpectedPixels > weakVerificationThreshold)))
	{
		log << tcu::TestLog::Message << "Invalid pixels found:\n\t"
			<< missingPixels << " missing pixels. (Marked with purple)\n\t"
			<< unexpectedPixels << " incorrectly filled pixels. (Marked with red)\n\t"
			<< "Unknown (subpixel on edge) pixels are marked with yellow."
			<< tcu::TestLog::EndMessage;
		log << tcu::TestLog::ImageSet("Verification result", "Result of rendering")
			<< tcu::TestLog::Image("Result",	"Result",		surface)
			<< tcu::TestLog::Image("ErrorMask", "ErrorMask",	errorMask)
			<< tcu::TestLog::EndImageSet;

		return false;
	}
	else
	{
		log << tcu::TestLog::Message << "No invalid pixels found." << tcu::TestLog::EndMessage;
		log << tcu::TestLog::ImageSet("Verification result", "Result of rendering")
			<< tcu::TestLog::Image("Result", "Result", surface)
			<< tcu::TestLog::EndImageSet;

		return true;
	}
}

bool verifyLineGroupRasterization (const tcu::Surface& surface, const LineSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log)
{
	const bool multisampled = args.numSamples != 0;

	if (multisampled)
		return verifyMultisampleLineGroupRasterization(surface, scene, args, log, CLIPMODE_NO_CLIPPING);
	else
		return verifySinglesampleLineGroupRasterization(surface, scene, args, log);
}

bool verifyClippedTriangulatedLineGroupRasterization (const tcu::Surface& surface, const LineSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log)
{
	return verifyMultisampleLineGroupRasterization(surface, scene, args, log, CLIPMODE_USE_CLIPPING_BOX);
}

bool verifyPointGroupRasterization (const tcu::Surface& surface, const PointSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log)
{
	// Splitting to triangles is a valid solution in multisampled cases and even in non-multisample cases too.
	return verifyMultisamplePointGroupRasterization(surface, scene, args, log);
}

bool verifyTriangleGroupInterpolation (const tcu::Surface& surface, const TriangleSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log)
{
	return verifyTriangleGroupInterpolationWithInterpolator(surface, scene, args, log, TriangleInterpolator(scene));
}

LineInterpolationMethod verifyLineGroupInterpolation (const tcu::Surface& surface, const LineSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log)
{
	const bool multisampled = args.numSamples != 0;

	if (multisampled)
	{
		if (verifyMultisampleLineGroupInterpolation(surface, scene, args, log))
			return LINEINTERPOLATION_STRICTLY_CORRECT;
		return LINEINTERPOLATION_INCORRECT;
	}
	else
	{
		const bool isNarrow = (scene.lineWidth == 1.0f);

		// accurate interpolation
		if (isNarrow)
		{
			if (verifySinglesampleNarrowLineGroupInterpolation(surface, scene, args, log))
				return LINEINTERPOLATION_STRICTLY_CORRECT;
		}
		else
		{
			if (verifySinglesampleWideLineGroupInterpolation(surface, scene, args, log))
				return LINEINTERPOLATION_STRICTLY_CORRECT;
		}

		// check with projected (inaccurate) interpolation
		log << tcu::TestLog::Message << "Accurate verification failed, checking with projected weights (inaccurate equation)." << tcu::TestLog::EndMessage;
		if (verifyLineGroupInterpolationWithProjectedWeights(surface, scene, args, log))
			return LINEINTERPOLATION_PROJECTED;

		return LINEINTERPOLATION_INCORRECT;
	}
}

bool verifyTriangulatedLineGroupInterpolation (const tcu::Surface& surface, const LineSceneSpec& scene, const RasterizationArguments& args, tcu::TestLog& log)
{
	return verifyMultisampleLineGroupInterpolation(surface, scene, args, log);
}

} // tcu