framework/referencerenderer/rrRasterizer.cpp

/*-------------------------------------------------------------------------
 * drawElements Quality Program Reference Renderer
 * -----------------------------------------------
 *
 * 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 Reference rasterizer
 *//*--------------------------------------------------------------------*/

#include "rrRasterizer.hpp"
#include "deMath.h"
#include "tcuVectorUtil.hpp"

namespace rr
{

inline deInt64 toSubpixelCoord (float v, int bits)
{
	return (deInt64)(v * (float)(1 << bits) + (v < 0.f ? -0.5f : 0.5f));
}

inline deInt64 toSubpixelCoord (deInt32 v, int bits)
{
	return v << bits;
}

inline deInt32 ceilSubpixelToPixelCoord (deInt64 coord, int bits, bool fillEdge)
{
	if (coord >= 0)
		return (deInt32)((coord + ((1ll << bits) - (fillEdge ? 0 : 1))) >> bits);
	else
		return (deInt32)((coord + (fillEdge ? 1 : 0)) >> bits);
}

inline deInt32 floorSubpixelToPixelCoord (deInt64 coord, int bits, bool fillEdge)
{
	if (coord >= 0)
		return (deInt32)((coord - (fillEdge ? 1 : 0)) >> bits);
	else
		return (deInt32)((coord - ((1ll << bits) - (fillEdge ? 0 : 1))) >> bits);
}

static inline void initEdgeCCW (EdgeFunction& edge, const HorizontalFill horizontalFill, const VerticalFill verticalFill, const deInt64 x0, const deInt64 y0, const deInt64 x1, const deInt64 y1)
{
	// \note See EdgeFunction documentation for details.

	const deInt64	xd			= x1-x0;
	const deInt64	yd			= y1-y0;
	bool			inclusive	= false;	//!< Inclusive in CCW orientation.

	if (yd == 0)
		inclusive = verticalFill == FILL_BOTTOM ? xd >= 0 : xd <= 0;
	else
		inclusive = horizontalFill == FILL_LEFT ? yd <= 0 : yd >= 0;

	edge.a			= (y0 - y1);
	edge.b			= (x1 - x0);
	edge.c			= x0*y1 - y0*x1;
	edge.inclusive	= inclusive; //!< \todo [pyry] Swap for CW triangles
}

static inline void reverseEdge (EdgeFunction& edge)
{
	edge.a			= -edge.a;
	edge.b			= -edge.b;
	edge.c			= -edge.c;
	edge.inclusive	= !edge.inclusive;
}

static inline deInt64 evaluateEdge (const EdgeFunction& edge, const deInt64 x, const deInt64 y)
{
	return edge.a*x + edge.b*y + edge.c;
}

static inline bool isInsideCCW (const EdgeFunction& edge, const deInt64 edgeVal)
{
	return edge.inclusive ? (edgeVal >= 0) : (edgeVal > 0);
}

namespace LineRasterUtil
{

struct SubpixelLineSegment
{
	const tcu::Vector<deInt64,2>	m_v0;
	const tcu::Vector<deInt64,2>	m_v1;

	SubpixelLineSegment (const tcu::Vector<deInt64,2>& v0, const tcu::Vector<deInt64,2>& v1)
		: m_v0(v0)
		, m_v1(v1)
	{
	}

	tcu::Vector<deInt64,2> direction (void) const
	{
		return m_v1 - m_v0;
	}
};

enum LINE_SIDE
{
	LINE_SIDE_INTERSECT = 0,
	LINE_SIDE_LEFT,
	LINE_SIDE_RIGHT
};

static tcu::Vector<deInt64,2> toSubpixelVector (const tcu::Vec2& v, int bits)
{
	return tcu::Vector<deInt64,2>(toSubpixelCoord(v.x(), bits), toSubpixelCoord(v.y(), bits));
}

static tcu::Vector<deInt64,2> toSubpixelVector (const tcu::IVec2& v, int bits)
{
	return tcu::Vector<deInt64,2>(toSubpixelCoord(v.x(), bits), toSubpixelCoord(v.y(), bits));
}

#if defined(DE_DEBUG)
static bool isTheCenterOfTheFragment (const tcu::Vector<deInt64,2>& a, int bits)
{
	const deUint64 pixelSize = 1ll << bits;
	const deUint64 halfPixel = 1ll << (bits - 1);
	return	((a.x() & (pixelSize-1)) == halfPixel &&
				(a.y() & (pixelSize-1)) == halfPixel);
}

static bool inViewport (const tcu::IVec2& p, const tcu::IVec4& viewport)
{
	return	p.x() >= viewport.x() &&
			p.y() >= viewport.y() &&
			p.x() <  viewport.x() + viewport.z() &&
			p.y() <  viewport.y() + viewport.w();
}
#endif // DE_DEBUG

// returns true if vertex is on the left side of the line
static bool vertexOnLeftSideOfLine (const tcu::Vector<deInt64,2>& p, const SubpixelLineSegment& l)
{
	const tcu::Vector<deInt64,2> u = l.direction();
	const tcu::Vector<deInt64,2> v = ( p - l.m_v0);
	const deInt64 crossProduct = (u.x() * v.y() - u.y() * v.x());
	return crossProduct < 0;
}

// returns true if vertex is on the right side of the line
static bool vertexOnRightSideOfLine (const tcu::Vector<deInt64,2>& p, const SubpixelLineSegment& l)
{
	const tcu::Vector<deInt64,2> u = l.direction();
	const tcu::Vector<deInt64,2> v = ( p - l.m_v0);
	const deInt64 crossProduct = (u.x() * v.y() - u.y() * v.x());
	return crossProduct > 0;
}

// returns true if vertex is on the line
static bool vertexOnLine (const tcu::Vector<deInt64,2>& p, const SubpixelLineSegment& l)
{
	const tcu::Vector<deInt64,2> u = l.direction();
	const tcu::Vector<deInt64,2> v = ( p - l.m_v0);
	const deInt64 crossProduct = (u.x() * v.y() - u.y() * v.x());
	return crossProduct == 0; // cross product == 0
}

// returns true if vertex is on the line segment
static bool vertexOnLineSegment (const tcu::Vector<deInt64,2>& p, const SubpixelLineSegment& l)
{
	if (!vertexOnLine(p, l))
		return false;

	const tcu::Vector<deInt64,2> v	= l.direction();
	const tcu::Vector<deInt64,2> u1	= ( p - l.m_v0);
	const tcu::Vector<deInt64,2> u2	= ( p - l.m_v1);

	if (v.x() == 0 && v.y() == 0)
		return false;

	return	tcu::dot( v, u1) >= 0 &&
			tcu::dot(-v, u2) >= 0; // dot (A->B, A->V) >= 0 and dot (B->A, B->V) >= 0
}

static LINE_SIDE getVertexSide (const tcu::Vector<deInt64,2>& v, const SubpixelLineSegment& l)
{
	if (vertexOnLeftSideOfLine(v, l))
		return LINE_SIDE_LEFT;
	else if (vertexOnRightSideOfLine(v, l))
		return LINE_SIDE_RIGHT;
	else if (vertexOnLine(v, l))
		return LINE_SIDE_INTERSECT;
	else
	{
		DE_ASSERT(false);
		return LINE_SIDE_INTERSECT;
	}
}

// returns true if angle between line and given cornerExitNormal is in range (-45, 45)
bool lineInCornerAngleRange (const SubpixelLineSegment& line, const tcu::Vector<deInt64,2>& cornerExitNormal)
{
	// v0 -> v1 has angle difference to cornerExitNormal in range (-45, 45)
	const tcu::Vector<deInt64,2> v = line.direction();
	const deInt64 dotProduct = dot(v, cornerExitNormal);

	// dotProduct > |v1-v0|*|cornerExitNormal|/sqrt(2)
	if (dotProduct < 0)
		return false;
	return 2 * dotProduct * dotProduct > tcu::lengthSquared(v)*tcu::lengthSquared(cornerExitNormal);
}

// returns true if angle between line and given cornerExitNormal is in range (-135, 135)
bool lineInCornerOutsideAngleRange (const SubpixelLineSegment& line, const tcu::Vector<deInt64,2>& cornerExitNormal)
{
	// v0 -> v1 has angle difference to cornerExitNormal in range (-135, 135)
	const tcu::Vector<deInt64,2> v = line.direction();
	const deInt64 dotProduct = dot(v, cornerExitNormal);

	// dotProduct > -|v1-v0|*|cornerExitNormal|/sqrt(2)
	if (dotProduct >= 0)
		return true;
	return 2 * (-dotProduct) * (-dotProduct) < tcu::lengthSquared(v)*tcu::lengthSquared(cornerExitNormal);
}

bool doesLineSegmentExitDiamond (const SubpixelLineSegment& line, const tcu::Vector<deInt64,2>& diamondCenter, int bits)
{
	DE_ASSERT(isTheCenterOfTheFragment(diamondCenter, bits));

	// Diamond Center is at diamondCenter in subpixel coords

	const deInt64 halfPixel = 1ll << (bits - 1);

	// Reject distant diamonds early
	{
		const tcu::Vector<deInt64,2>	u				= line.direction();
		const tcu::Vector<deInt64,2>	v				= (diamondCenter - line.m_v0);
		const deInt64					crossProduct	= (u.x() * v.y() - u.y() * v.x());

		// crossProduct = |p| |l| sin(theta)
		// distanceFromLine = |p| sin(theta)
		// => distanceFromLine = crossProduct / |l|
		//
		// |distanceFromLine| > C
		// => distanceFromLine^2 > C^2
		// => crossProduct^2 / |l|^2 > C^2
		// => crossProduct^2 > |l|^2 * C^2

		const deInt64	floorSqrtMaxInt64			= 3037000499LL; //!< floor(sqrt(MAX_INT64))

		const deInt64	broadRejectDistance			= 2 * halfPixel;
		const deInt64	broadRejectDistanceSquared	= broadRejectDistance * broadRejectDistance;
		const bool		crossProductOverflows		= (crossProduct > floorSqrtMaxInt64 || crossProduct < -floorSqrtMaxInt64);
		const deInt64	crossProductSquared			= (crossProductOverflows) ? (0) : (crossProduct * crossProduct); // avoid overflow
		const deInt64	lineLengthSquared			= tcu::lengthSquared(u);
		const bool		limitValueCouldOverflow		= ((64 - deClz64(lineLengthSquared)) + (64 - deClz64(broadRejectDistanceSquared))) > 63;
		const deInt64	limitValue					= (limitValueCouldOverflow) ? (0) : (lineLengthSquared * broadRejectDistanceSquared); // avoid overflow

		// only cross overflows
		if (crossProductOverflows && !limitValueCouldOverflow)
			return false;

		// both representable
		if (!crossProductOverflows && !limitValueCouldOverflow)
		{
			if (crossProductSquared > limitValue)
				return false;
		}
	}

	const struct DiamondBound
	{
		tcu::Vector<deInt64,2>	p0;
		tcu::Vector<deInt64,2>	p1;
		bool					edgeInclusive; // would a point on the bound be inside of the region
	} bounds[] =
	{
		{ diamondCenter + tcu::Vector<deInt64,2>(0,				-halfPixel),	diamondCenter + tcu::Vector<deInt64,2>(-halfPixel,	0),				 false	},
		{ diamondCenter + tcu::Vector<deInt64,2>(-halfPixel,	0),				diamondCenter + tcu::Vector<deInt64,2>(0,			halfPixel),		 false	},
		{ diamondCenter + tcu::Vector<deInt64,2>(0,				halfPixel),		diamondCenter + tcu::Vector<deInt64,2>(halfPixel,	0),				 true	},
		{ diamondCenter + tcu::Vector<deInt64,2>(halfPixel,		0),				diamondCenter + tcu::Vector<deInt64,2>(0,			-halfPixel),	 true	},
	};

	const struct DiamondCorners
	{
		enum CORNER_EDGE_CASE_BEHAVIOR
		{
			CORNER_EDGE_CASE_NONE,							// if the line intersects just a corner, no entering or exiting
			CORNER_EDGE_CASE_HIT,							// if the line intersects just a corner, entering and exit
			CORNER_EDGE_CASE_HIT_FIRST_QUARTER,				// if the line intersects just a corner and the line has either endpoint in (+X,-Y) direction (preturbing moves the line inside)
			CORNER_EDGE_CASE_HIT_SECOND_QUARTER				// if the line intersects just a corner and the line has either endpoint in (+X,+Y) direction (preturbing moves the line inside)
		};
		enum CORNER_START_CASE_BEHAVIOR
		{
			CORNER_START_CASE_NONE,							// the line starting point is outside, no exiting
			CORNER_START_CASE_OUTSIDE,						// exit, if line does not intersect the region (preturbing moves the start point inside)
			CORNER_START_CASE_POSITIVE_Y_45,				// exit, if line the angle of line vector and X-axis is in range (0, 45] in positive Y side.
			CORNER_START_CASE_NEGATIVE_Y_45					// exit, if line the angle of line vector and X-axis is in range [0, 45] in negative Y side.
		};
		enum CORNER_END_CASE_BEHAVIOR
		{
			CORNER_END_CASE_NONE,							// end is inside, no exiting (preturbing moves the line end inside)
			CORNER_END_CASE_DIRECTION,						// exit, if line intersected the region (preturbing moves the line end outside)
			CORNER_END_CASE_DIRECTION_AND_FIRST_QUARTER,	// exit, if line intersected the region, or line originates from (+X,-Y) direction (preturbing moves the line end outside)
			CORNER_END_CASE_DIRECTION_AND_SECOND_QUARTER	// exit, if line intersected the region, or line originates from (+X,+Y) direction (preturbing moves the line end outside)
		};

		tcu::Vector<deInt64,2>		dp;
		bool						pointInclusive;			// would a point in this corner intersect with the region
		CORNER_EDGE_CASE_BEHAVIOR	lineBehavior;			// would a line segment going through this corner intersect with the region
		CORNER_START_CASE_BEHAVIOR	startBehavior;			// how the corner behaves if the start point at the corner
		CORNER_END_CASE_BEHAVIOR	endBehavior;			// how the corner behaves if the end point at the corner
	} corners[] =
	{
		{ tcu::Vector<deInt64,2>(0,				-halfPixel),	false,	DiamondCorners::CORNER_EDGE_CASE_HIT_SECOND_QUARTER,	DiamondCorners::CORNER_START_CASE_POSITIVE_Y_45,	DiamondCorners::CORNER_END_CASE_DIRECTION_AND_SECOND_QUARTER},
		{ tcu::Vector<deInt64,2>(-halfPixel,	0),				false,	DiamondCorners::CORNER_EDGE_CASE_NONE,					DiamondCorners::CORNER_START_CASE_NONE,				DiamondCorners::CORNER_END_CASE_DIRECTION					},
		{ tcu::Vector<deInt64,2>(0,				halfPixel),		false,	DiamondCorners::CORNER_EDGE_CASE_HIT_FIRST_QUARTER,		DiamondCorners::CORNER_START_CASE_NEGATIVE_Y_45,	DiamondCorners::CORNER_END_CASE_DIRECTION_AND_FIRST_QUARTER	},
		{ tcu::Vector<deInt64,2>(halfPixel,		0),				true,	DiamondCorners::CORNER_EDGE_CASE_HIT,					DiamondCorners::CORNER_START_CASE_OUTSIDE,			DiamondCorners::CORNER_END_CASE_NONE						},
	};

	// Corner cases at the corners
	for (int ndx = 0; ndx < DE_LENGTH_OF_ARRAY(corners); ++ndx)
	{
		const tcu::Vector<deInt64,2> p	= diamondCenter + corners[ndx].dp;
		const bool intersectsAtCorner	= LineRasterUtil::vertexOnLineSegment(p, line);

		if (!intersectsAtCorner)
			continue;

		// line segment body intersects with the corner
		if (p != line.m_v0 && p != line.m_v1)
		{
			if (corners[ndx].lineBehavior == DiamondCorners::CORNER_EDGE_CASE_HIT)
				return true;

			// endpoint in (+X, -Y) (X or Y may be 0) direction <==> x*y <= 0
			if (corners[ndx].lineBehavior == DiamondCorners::CORNER_EDGE_CASE_HIT_FIRST_QUARTER &&
				(line.direction().x() * line.direction().y()) <= 0)
				return true;

			// endpoint in (+X, +Y) (Y > 0) direction <==> x*y > 0
			if (corners[ndx].lineBehavior == DiamondCorners::CORNER_EDGE_CASE_HIT_SECOND_QUARTER &&
				(line.direction().x() * line.direction().y()) > 0)
				return true;
		}

		// line exits the area at the corner
		if (lineInCornerAngleRange(line, corners[ndx].dp))
		{
			const bool startIsInside = corners[ndx].pointInclusive || p != line.m_v0;
			const bool endIsOutside = !corners[ndx].pointInclusive || p != line.m_v1;

			// starting point is inside the region and end endpoint is outside
			if (startIsInside && endIsOutside)
				return true;
		}

		// line end is at the corner
		if (p == line.m_v1)
		{
			if (corners[ndx].endBehavior == DiamondCorners::CORNER_END_CASE_DIRECTION ||
				corners[ndx].endBehavior == DiamondCorners::CORNER_END_CASE_DIRECTION_AND_FIRST_QUARTER ||
				corners[ndx].endBehavior == DiamondCorners::CORNER_END_CASE_DIRECTION_AND_SECOND_QUARTER)
			{
				// did the line intersect the region
				if (lineInCornerAngleRange(line, corners[ndx].dp))
					return true;
			}

			// due to the perturbed endpoint, lines at this the angle will cause and enter-exit pair
			if (corners[ndx].endBehavior == DiamondCorners::CORNER_END_CASE_DIRECTION_AND_FIRST_QUARTER &&
				line.direction().x() < 0 &&
				line.direction().y() > 0)
				return true;
			if (corners[ndx].endBehavior == DiamondCorners::CORNER_END_CASE_DIRECTION_AND_SECOND_QUARTER &&
				line.direction().x() > 0 &&
				line.direction().y() > 0)
				return true;
		}

		// line start is at the corner
		if (p == line.m_v0)
		{
			if (corners[ndx].startBehavior == DiamondCorners::CORNER_START_CASE_OUTSIDE)
			{
				// if the line is not going inside, it will exit
				if (lineInCornerOutsideAngleRange(line, corners[ndx].dp))
					return true;
			}

			// exit, if line the angle between line vector and X-axis is in range (0, 45] in positive Y side.
			if (corners[ndx].startBehavior == DiamondCorners::CORNER_START_CASE_POSITIVE_Y_45 &&
				line.direction().x() > 0 &&
				line.direction().y() > 0 &&
				line.direction().y() <= line.direction().x())
				return true;

			// exit, if line the angle between line vector and X-axis is in range [0, 45] in negative Y side.
			if (corners[ndx].startBehavior == DiamondCorners::CORNER_START_CASE_NEGATIVE_Y_45 &&
				 line.direction().x() > 0 &&
				 line.direction().y() <= 0 &&
				-line.direction().y() <= line.direction().x())
				return true;
		}
	}

	// Does the line intersect boundary at the left == exits the diamond
	for (int ndx = 0; ndx < DE_LENGTH_OF_ARRAY(bounds); ++ndx)
	{
		const bool startVertexInside =	LineRasterUtil::vertexOnLeftSideOfLine						(line.m_v0, LineRasterUtil::SubpixelLineSegment(bounds[ndx].p0, bounds[ndx].p1)) ||
										(bounds[ndx].edgeInclusive && LineRasterUtil::vertexOnLine	(line.m_v0, LineRasterUtil::SubpixelLineSegment(bounds[ndx].p0, bounds[ndx].p1)));
		const bool endVertexInside =	LineRasterUtil::vertexOnLeftSideOfLine						(line.m_v1, LineRasterUtil::SubpixelLineSegment(bounds[ndx].p0, bounds[ndx].p1)) ||
										(bounds[ndx].edgeInclusive && LineRasterUtil::vertexOnLine	(line.m_v1, LineRasterUtil::SubpixelLineSegment(bounds[ndx].p0, bounds[ndx].p1)));

		// start must be on inside this half space (left or at the inclusive boundary)
		if (!startVertexInside)
			continue;

		// end must be outside of this half-space (right or at non-inclusive boundary)
		if (endVertexInside)
			continue;

		// Does the line via v0 and v1 intersect the line segment p0-p1
		// <==> p0 and p1 are the different sides (LEFT, RIGHT) of the v0-v1 line.
		// Corners are not allowed, they are checked already
		LineRasterUtil::LINE_SIDE sideP0 = LineRasterUtil::getVertexSide(bounds[ndx].p0, line);
		LineRasterUtil::LINE_SIDE sideP1 = LineRasterUtil::getVertexSide(bounds[ndx].p1, line);

		if (sideP0 != LineRasterUtil::LINE_SIDE_INTERSECT &&
			sideP1 != LineRasterUtil::LINE_SIDE_INTERSECT &&
			sideP0 != sideP1)
			return true;
	}

	return false;
}

} // LineRasterUtil

TriangleRasterizer::TriangleRasterizer (const tcu::IVec4& viewport, const int numSamples, const RasterizationState& state, const int subpixelBits)
	: m_viewport				(viewport)
	, m_numSamples				(numSamples)
	, m_winding					(state.winding)
	, m_horizontalFill			(state.horizontalFill)
	, m_verticalFill			(state.verticalFill)
	, m_subpixelBits			(subpixelBits)
	, m_face					(FACETYPE_LAST)
	, m_viewportOrientation		(state.viewportOrientation)
{
}

/*--------------------------------------------------------------------*//*!
 * \brief Initialize triangle rasterization
 * \param v0 Screen-space coordinates (x, y, z) and 1/w for vertex 0.
 * \param v1 Screen-space coordinates (x, y, z) and 1/w for vertex 1.
 * \param v2 Screen-space coordinates (x, y, z) and 1/w for vertex 2.
 *//*--------------------------------------------------------------------*/
void TriangleRasterizer::init (const tcu::Vec4& v0, const tcu::Vec4& v1, const tcu::Vec4& v2)
{
	m_v0 = v0;
	m_v1 = v1;
	m_v2 = v2;

	// Positions in fixed-point coordinates.
	const deInt64	x0		= toSubpixelCoord(v0.x(), m_subpixelBits);
	const deInt64	y0		= toSubpixelCoord(v0.y(), m_subpixelBits);
	const deInt64	x1		= toSubpixelCoord(v1.x(), m_subpixelBits);
	const deInt64	y1		= toSubpixelCoord(v1.y(), m_subpixelBits);
	const deInt64	x2		= toSubpixelCoord(v2.x(), m_subpixelBits);
	const deInt64	y2		= toSubpixelCoord(v2.y(), m_subpixelBits);

	// Initialize edge functions.
	if (m_winding == WINDING_CCW)
	{
		initEdgeCCW(m_edge01, m_horizontalFill, m_verticalFill, x0, y0, x1, y1);
		initEdgeCCW(m_edge12, m_horizontalFill, m_verticalFill, x1, y1, x2, y2);
		initEdgeCCW(m_edge20, m_horizontalFill, m_verticalFill, x2, y2, x0, y0);
	}
	else
	{
		// Reverse edges
		initEdgeCCW(m_edge01, m_horizontalFill, m_verticalFill, x1, y1, x0, y0);
		initEdgeCCW(m_edge12, m_horizontalFill, m_verticalFill, x2, y2, x1, y1);
		initEdgeCCW(m_edge20, m_horizontalFill, m_verticalFill, x0, y0, x2, y2);
	}

	// Determine face.
	const deInt64	s				= evaluateEdge(m_edge01, x2, y2);
	const bool		positiveArea	= (m_winding == WINDING_CCW) ? (s > 0) : (s < 0);

	if (m_viewportOrientation == VIEWPORTORIENTATION_UPPER_LEFT)
		m_face = positiveArea ? FACETYPE_BACK : FACETYPE_FRONT;
	else
		m_face = positiveArea ? FACETYPE_FRONT : FACETYPE_BACK;

	if (!positiveArea)
	{
		// Reverse edges so that we can use CCW area tests & interpolation
		reverseEdge(m_edge01);
		reverseEdge(m_edge12);
		reverseEdge(m_edge20);
	}

	// Bounding box
	const deInt64	xMin	= de::min(de::min(x0, x1), x2);
	const deInt64	xMax	= de::max(de::max(x0, x1), x2);
	const deInt64	yMin	= de::min(de::min(y0, y1), y2);
	const deInt64	yMax	= de::max(de::max(y0, y1), y2);

	m_bboxMin.x() = floorSubpixelToPixelCoord	(xMin, m_subpixelBits, m_horizontalFill	== FILL_LEFT);
	m_bboxMin.y() = floorSubpixelToPixelCoord	(yMin, m_subpixelBits, m_verticalFill	== FILL_BOTTOM);
	m_bboxMax.x() = ceilSubpixelToPixelCoord	(xMax, m_subpixelBits, m_horizontalFill	== FILL_RIGHT);
	m_bboxMax.y() = ceilSubpixelToPixelCoord	(yMax, m_subpixelBits, m_verticalFill	== FILL_TOP);

	// Clamp to viewport
	const int		wX0		= m_viewport.x();
	const int		wY0		= m_viewport.y();
	const int		wX1		= wX0 + m_viewport.z() - 1;
	const int		wY1		= wY0 + m_viewport.w() -1;

	m_bboxMin.x() = de::clamp(m_bboxMin.x(), wX0, wX1);
	m_bboxMin.y() = de::clamp(m_bboxMin.y(), wY0, wY1);
	m_bboxMax.x() = de::clamp(m_bboxMax.x(), wX0, wX1);
	m_bboxMax.y() = de::clamp(m_bboxMax.y(), wY0, wY1);

	m_curPos = m_bboxMin;
}

void TriangleRasterizer::rasterizeSingleSample (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
{
	DE_ASSERT(maxFragmentPackets > 0);

	const deUint64	halfPixel	= 1ll << (m_subpixelBits - 1);
	int				packetNdx	= 0;

	// For depth interpolation; given barycentrics A, B, C = (1 - A - B)
	// we can reformulate the usual z = z0*A + z1*B + z2*C into more
	// stable equation z = A*(z0 - z2) + B*(z1 - z2) + z2.
	const float		za			= m_v0.z()-m_v2.z();
	const float		zb			= m_v1.z()-m_v2.z();
	const float		zc			= m_v2.z();

	while (m_curPos.y() <= m_bboxMax.y() && packetNdx < maxFragmentPackets)
	{
		const int		x0		= m_curPos.x();
		const int		y0		= m_curPos.y();

		// Subpixel coords
		const deInt64	sx0		= toSubpixelCoord(x0,   m_subpixelBits)	+ halfPixel;
		const deInt64	sx1		= toSubpixelCoord(x0+1, m_subpixelBits)	+ halfPixel;
		const deInt64	sy0		= toSubpixelCoord(y0,   m_subpixelBits)	+ halfPixel;
		const deInt64	sy1		= toSubpixelCoord(y0+1, m_subpixelBits)	+ halfPixel;

		const deInt64	sx[4]	= { sx0, sx1, sx0, sx1 };
		const deInt64	sy[4]	= { sy0, sy0, sy1, sy1 };

		// Viewport test
		const bool		outX1	= x0+1 == m_viewport.x()+m_viewport.z();
		const bool		outY1	= y0+1 == m_viewport.y()+m_viewport.w();

		DE_ASSERT(x0 < m_viewport.x()+m_viewport.z());
		DE_ASSERT(y0 < m_viewport.y()+m_viewport.w());

		// Edge values
		tcu::Vector<deInt64, 4>	e01;
		tcu::Vector<deInt64, 4>	e12;
		tcu::Vector<deInt64, 4>	e20;

		// Coverage
		deUint64		coverage	= 0;

		// Evaluate edge values
		for (int i = 0; i < 4; i++)
		{
			e01[i] = evaluateEdge(m_edge01, sx[i], sy[i]);
			e12[i] = evaluateEdge(m_edge12, sx[i], sy[i]);
			e20[i] = evaluateEdge(m_edge20, sx[i], sy[i]);
		}

		// Compute coverage mask
		coverage = setCoverageValue(coverage, 1, 0, 0, 0,						isInsideCCW(m_edge01, e01[0]) && isInsideCCW(m_edge12, e12[0]) && isInsideCCW(m_edge20, e20[0]));
		coverage = setCoverageValue(coverage, 1, 1, 0, 0, !outX1 &&				isInsideCCW(m_edge01, e01[1]) && isInsideCCW(m_edge12, e12[1]) && isInsideCCW(m_edge20, e20[1]));
		coverage = setCoverageValue(coverage, 1, 0, 1, 0, !outY1 &&				isInsideCCW(m_edge01, e01[2]) && isInsideCCW(m_edge12, e12[2]) && isInsideCCW(m_edge20, e20[2]));
		coverage = setCoverageValue(coverage, 1, 1, 1, 0, !outX1 && !outY1 &&	isInsideCCW(m_edge01, e01[3]) && isInsideCCW(m_edge12, e12[3]) && isInsideCCW(m_edge20, e20[3]));

		// Advance to next location
		m_curPos.x() += 2;
		if (m_curPos.x() > m_bboxMax.x())
		{
			m_curPos.y() += 2;
			m_curPos.x()  = m_bboxMin.x();
		}

		if (coverage == 0)
			continue; // Discard.

		// Floating-point edge values for barycentrics etc.
		const tcu::Vec4		e01f	= e01.asFloat();
		const tcu::Vec4		e12f	= e12.asFloat();
		const tcu::Vec4		e20f	= e20.asFloat();

		// Compute depth values.
		if (depthValues)
		{
			const tcu::Vec4		edgeSum	= e01f + e12f + e20f;
			const tcu::Vec4		z0		= e12f / edgeSum;
			const tcu::Vec4		z1		= e20f / edgeSum;

			depthValues[packetNdx*4+0] = z0[0]*za + z1[0]*zb + zc;
			depthValues[packetNdx*4+1] = z0[1]*za + z1[1]*zb + zc;
			depthValues[packetNdx*4+2] = z0[2]*za + z1[2]*zb + zc;
			depthValues[packetNdx*4+3] = z0[3]*za + z1[3]*zb + zc;
		}

		// Compute barycentrics and write out fragment packet
		{
			FragmentPacket& packet = fragmentPackets[packetNdx];

			const tcu::Vec4		b0		= e12f * m_v0.w();
			const tcu::Vec4		b1		= e20f * m_v1.w();
			const tcu::Vec4		b2		= e01f * m_v2.w();
			const tcu::Vec4		bSum	= b0 + b1 + b2;

			packet.position			= tcu::IVec2(x0, y0);
			packet.coverage			= coverage;
			packet.barycentric[0]	= b0 / bSum;
			packet.barycentric[1]	= b1 / bSum;
			packet.barycentric[2]	= 1.0f - packet.barycentric[0] - packet.barycentric[1];

			packetNdx += 1;
		}
	}

	DE_ASSERT(packetNdx <= maxFragmentPackets);
	numPacketsRasterized = packetNdx;
}

// Sample positions - ordered as (x, y) list.
static const float s_samplePts2[] =
{
	0.3f, 0.3f,
	0.7f, 0.7f
};

static const float s_samplePts4[] =
{
	0.25f, 0.25f,
	0.75f, 0.25f,
	0.25f, 0.75f,
	0.75f, 0.75f
};

static const float s_samplePts8[] =
{
	7.f  / 16.f,  9.f / 16.f,
	9.f  / 16.f, 13.f / 16.f,
	11.f / 16.f,  3.f / 16.f,
	13.f / 16.f, 11.f / 16.f,
	1.f  / 16.f,  7.f / 16.f,
	5.f  / 16.f,  1.f / 16.f,
	15.f / 16.f,  5.f / 16.f,
	3.f  / 16.f, 15.f / 16.f
};

static const float s_samplePts16[] =
{
	1.f / 8.f, 1.f / 8.f,
	3.f / 8.f, 1.f / 8.f,
	5.f / 8.f, 1.f / 8.f,
	7.f / 8.f, 1.f / 8.f,
	1.f / 8.f, 3.f / 8.f,
	3.f / 8.f, 3.f / 8.f,
	5.f / 8.f, 3.f / 8.f,
	7.f / 8.f, 3.f / 8.f,
	1.f / 8.f, 5.f / 8.f,
	3.f / 8.f, 5.f / 8.f,
	5.f / 8.f, 5.f / 8.f,
	7.f / 8.f, 5.f / 8.f,
	1.f / 8.f, 7.f / 8.f,
	3.f / 8.f, 7.f / 8.f,
	5.f / 8.f, 7.f / 8.f,
	7.f / 8.f, 7.f / 8.f
};

template<int NumSamples>
void TriangleRasterizer::rasterizeMultiSample (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
{
	DE_ASSERT(maxFragmentPackets > 0);

	// Big enough to hold maximum multisample count
	deInt64			samplePos[DE_LENGTH_OF_ARRAY(s_samplePts16)];
	const float *	samplePts	= DE_NULL;
	const deUint64	halfPixel	= 1ll << (m_subpixelBits - 1);
	int				packetNdx	= 0;

	// For depth interpolation, see rasterizeSingleSample
	const float		za			= m_v0.z()-m_v2.z();
	const float		zb			= m_v1.z()-m_v2.z();
	const float		zc			= m_v2.z();

	switch (NumSamples)
	{
		case 2:		samplePts = s_samplePts2;	break;
		case 4:		samplePts = s_samplePts4;	break;
		case 8:		samplePts = s_samplePts8;	break;
		case 16:	samplePts = s_samplePts16;	break;
		default:
			DE_ASSERT(false);
	}

	for (int c = 0; c < NumSamples * 2; ++c)
		samplePos[c] = toSubpixelCoord(samplePts[c], m_subpixelBits);

	while (m_curPos.y() <= m_bboxMax.y() && packetNdx < maxFragmentPackets)
	{
		const int		x0		= m_curPos.x();
		const int		y0		= m_curPos.y();

		// Base subpixel coords
		const deInt64	sx0		= toSubpixelCoord(x0,   m_subpixelBits);
		const deInt64	sx1		= toSubpixelCoord(x0+1, m_subpixelBits);
		const deInt64	sy0		= toSubpixelCoord(y0,   m_subpixelBits);
		const deInt64	sy1		= toSubpixelCoord(y0+1, m_subpixelBits);

		const deInt64	sx[4]	= { sx0, sx1, sx0, sx1 };
		const deInt64	sy[4]	= { sy0, sy0, sy1, sy1 };

		// Viewport test
		const bool		outX1	= x0+1 == m_viewport.x()+m_viewport.z();
		const bool		outY1	= y0+1 == m_viewport.y()+m_viewport.w();

		DE_ASSERT(x0 < m_viewport.x()+m_viewport.z());
		DE_ASSERT(y0 < m_viewport.y()+m_viewport.w());

		// Edge values
		tcu::Vector<deInt64, 4>	e01[NumSamples];
		tcu::Vector<deInt64, 4>	e12[NumSamples];
		tcu::Vector<deInt64, 4>	e20[NumSamples];

		// Coverage
		deUint64		coverage	= 0;

		// Evaluate edge values at sample positions
		for (int sampleNdx = 0; sampleNdx < NumSamples; sampleNdx++)
		{
			const deInt64 ox = samplePos[sampleNdx*2 + 0];
			const deInt64 oy = samplePos[sampleNdx*2 + 1];

			for (int fragNdx = 0; fragNdx < 4; fragNdx++)
			{
				e01[sampleNdx][fragNdx] = evaluateEdge(m_edge01, sx[fragNdx] + ox, sy[fragNdx] + oy);
				e12[sampleNdx][fragNdx] = evaluateEdge(m_edge12, sx[fragNdx] + ox, sy[fragNdx] + oy);
				e20[sampleNdx][fragNdx] = evaluateEdge(m_edge20, sx[fragNdx] + ox, sy[fragNdx] + oy);
			}
		}

		// Compute coverage mask
		for (int sampleNdx = 0; sampleNdx < NumSamples; sampleNdx++)
		{
			coverage = setCoverageValue(coverage, NumSamples, 0, 0, sampleNdx,						isInsideCCW(m_edge01, e01[sampleNdx][0]) && isInsideCCW(m_edge12, e12[sampleNdx][0]) && isInsideCCW(m_edge20, e20[sampleNdx][0]));
			coverage = setCoverageValue(coverage, NumSamples, 1, 0, sampleNdx, !outX1 &&			isInsideCCW(m_edge01, e01[sampleNdx][1]) && isInsideCCW(m_edge12, e12[sampleNdx][1]) && isInsideCCW(m_edge20, e20[sampleNdx][1]));
			coverage = setCoverageValue(coverage, NumSamples, 0, 1, sampleNdx, !outY1 &&			isInsideCCW(m_edge01, e01[sampleNdx][2]) && isInsideCCW(m_edge12, e12[sampleNdx][2]) && isInsideCCW(m_edge20, e20[sampleNdx][2]));
			coverage = setCoverageValue(coverage, NumSamples, 1, 1, sampleNdx, !outX1 && !outY1 &&	isInsideCCW(m_edge01, e01[sampleNdx][3]) && isInsideCCW(m_edge12, e12[sampleNdx][3]) && isInsideCCW(m_edge20, e20[sampleNdx][3]));
		}

		// Advance to next location
		m_curPos.x() += 2;
		if (m_curPos.x() > m_bboxMax.x())
		{
			m_curPos.y() += 2;
			m_curPos.x()  = m_bboxMin.x();
		}

		if (coverage == 0)
			continue; // Discard.

		// Compute depth values.
		if (depthValues)
		{
			for (int sampleNdx = 0; sampleNdx < NumSamples; sampleNdx++)
			{
				// Floating-point edge values at sample coordinates.
				const tcu::Vec4&	e01f	= e01[sampleNdx].asFloat();
				const tcu::Vec4&	e12f	= e12[sampleNdx].asFloat();
				const tcu::Vec4&	e20f	= e20[sampleNdx].asFloat();

				const tcu::Vec4		edgeSum	= e01f + e12f + e20f;
				const tcu::Vec4		z0		= e12f / edgeSum;
				const tcu::Vec4		z1		= e20f / edgeSum;

				depthValues[(packetNdx*4+0)*NumSamples + sampleNdx] = z0[0]*za + z1[0]*zb + zc;
				depthValues[(packetNdx*4+1)*NumSamples + sampleNdx] = z0[1]*za + z1[1]*zb + zc;
				depthValues[(packetNdx*4+2)*NumSamples + sampleNdx] = z0[2]*za + z1[2]*zb + zc;
				depthValues[(packetNdx*4+3)*NumSamples + sampleNdx] = z0[3]*za + z1[3]*zb + zc;
			}
		}

		// Compute barycentrics and write out fragment packet
		{
			FragmentPacket& packet = fragmentPackets[packetNdx];

			// Floating-point edge values at pixel center.
			tcu::Vec4			e01f;
			tcu::Vec4			e12f;
			tcu::Vec4			e20f;

			for (int i = 0; i < 4; i++)
			{
				e01f[i] = float(evaluateEdge(m_edge01, sx[i] + halfPixel, sy[i] + halfPixel));
				e12f[i] = float(evaluateEdge(m_edge12, sx[i] + halfPixel, sy[i] + halfPixel));
				e20f[i] = float(evaluateEdge(m_edge20, sx[i] + halfPixel, sy[i] + halfPixel));
			}

			// Barycentrics & scale.
			const tcu::Vec4		b0		= e12f * m_v0.w();
			const tcu::Vec4		b1		= e20f * m_v1.w();
			const tcu::Vec4		b2		= e01f * m_v2.w();
			const tcu::Vec4		bSum	= b0 + b1 + b2;

			packet.position			= tcu::IVec2(x0, y0);
			packet.coverage			= coverage;
			packet.barycentric[0]	= b0 / bSum;
			packet.barycentric[1]	= b1 / bSum;
			packet.barycentric[2]	= 1.0f - packet.barycentric[0] - packet.barycentric[1];

			packetNdx += 1;
		}
	}

	DE_ASSERT(packetNdx <= maxFragmentPackets);
	numPacketsRasterized = packetNdx;
}

void TriangleRasterizer::rasterize (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
{
	DE_ASSERT(maxFragmentPackets > 0);

	switch (m_numSamples)
	{
		case 1:		rasterizeSingleSample		(fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);	break;
		case 2:		rasterizeMultiSample<2>		(fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);	break;
		case 4:		rasterizeMultiSample<4>		(fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);	break;
		case 8:		rasterizeMultiSample<8>		(fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);	break;
		case 16:	rasterizeMultiSample<16>	(fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);	break;
		default:
			DE_ASSERT(DE_FALSE);
	}
}

SingleSampleLineRasterizer::SingleSampleLineRasterizer (const tcu::IVec4& viewport, const int subpixelBits)
	: m_viewport		(viewport)
	, m_subpixelBits	(subpixelBits)
	, m_curRowFragment	(0)
	, m_lineWidth		(0.0f)
	, m_stippleCounter  (0)
{
}

SingleSampleLineRasterizer::~SingleSampleLineRasterizer (void)
{
}

void SingleSampleLineRasterizer::init (const tcu::Vec4& v0, const tcu::Vec4& v1, float lineWidth, deUint32 stippleFactor, deUint16 stipplePattern)
{
	const bool						isXMajor		= de::abs((v1 - v0).x()) >= de::abs((v1 - v0).y());

	// Bounding box \note: with wide lines, the line is actually moved as in the spec
	const deInt32					lineWidthPixels	= (lineWidth > 1.0f) ? (deInt32)floor(lineWidth + 0.5f) : 1;

	const tcu::Vector<deInt64,2>	widthOffset		= (isXMajor ? tcu::Vector<deInt64,2>(0, -1) : tcu::Vector<deInt64,2>(-1, 0)) * (toSubpixelCoord(lineWidthPixels - 1, m_subpixelBits) / 2);

	const deInt64					x0				= toSubpixelCoord(v0.x(), m_subpixelBits) + widthOffset.x();
	const deInt64					y0				= toSubpixelCoord(v0.y(), m_subpixelBits) + widthOffset.y();
	const deInt64					x1				= toSubpixelCoord(v1.x(), m_subpixelBits) + widthOffset.x();
	const deInt64					y1				= toSubpixelCoord(v1.y(), m_subpixelBits) + widthOffset.y();

	// line endpoints might be perturbed, add some margin
	const deInt64					xMin			= de::min(x0, x1) - toSubpixelCoord(1, m_subpixelBits);
	const deInt64					xMax			= de::max(x0, x1) + toSubpixelCoord(1, m_subpixelBits);
	const deInt64					yMin			= de::min(y0, y1) - toSubpixelCoord(1, m_subpixelBits);
	const deInt64					yMax			= de::max(y0, y1) + toSubpixelCoord(1, m_subpixelBits);

	// Remove invisible area

	if (isXMajor)
	{
		// clamp to viewport in major direction
		m_bboxMin.x() = de::clamp(floorSubpixelToPixelCoord(xMin, m_subpixelBits, true), m_viewport.x(), m_viewport.x() + m_viewport.z() - 1);
		m_bboxMax.x() = de::clamp(ceilSubpixelToPixelCoord (xMax, m_subpixelBits, true), m_viewport.x(), m_viewport.x() + m_viewport.z() - 1);

		// clamp to padded viewport in minor direction (wide lines might bleed over viewport in minor direction)
		m_bboxMin.y() = de::clamp(floorSubpixelToPixelCoord(yMin, m_subpixelBits, true), m_viewport.y() - lineWidthPixels, m_viewport.y() + m_viewport.w() - 1);
		m_bboxMax.y() = de::clamp(ceilSubpixelToPixelCoord (yMax, m_subpixelBits, true), m_viewport.y() - lineWidthPixels, m_viewport.y() + m_viewport.w() - 1);
	}
	else
	{
		// clamp to viewport in major direction
		m_bboxMin.y() = de::clamp(floorSubpixelToPixelCoord(yMin, m_subpixelBits, true), m_viewport.y(), m_viewport.y() + m_viewport.w() - 1);
		m_bboxMax.y() = de::clamp(ceilSubpixelToPixelCoord (yMax, m_subpixelBits, true), m_viewport.y(), m_viewport.y() + m_viewport.w() - 1);

		// clamp to padded viewport in minor direction (wide lines might bleed over viewport in minor direction)
		m_bboxMin.x() = de::clamp(floorSubpixelToPixelCoord(xMin, m_subpixelBits, true), m_viewport.x() - lineWidthPixels, m_viewport.x() + m_viewport.z() - 1);
		m_bboxMax.x() = de::clamp(ceilSubpixelToPixelCoord (xMax, m_subpixelBits, true), m_viewport.x() - lineWidthPixels, m_viewport.x() + m_viewport.z() - 1);
	}

	m_lineWidth = lineWidth;

	m_v0 = v0;
	m_v1 = v1;

	// Choose direction of traversal and whether to start at bbox min or max. Direction matters
    // for the stipple counter.
	int											xDelta				= (m_v1 - m_v0).x() > 0 ? 1 : -1;
	int											yDelta				= (m_v1 - m_v0).y() > 0 ? 1 : -1;

	m_curPos.x() = xDelta > 0 ? m_bboxMin.x() : m_bboxMax.x();
	m_curPos.y() = yDelta > 0 ? m_bboxMin.y() : m_bboxMax.y();

	m_curRowFragment = 0;
	m_stippleFactor = stippleFactor;
	m_stipplePattern = stipplePattern;
}

void SingleSampleLineRasterizer::rasterize (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
{
	DE_ASSERT(maxFragmentPackets > 0);

	const deInt64								halfPixel			= 1ll << (m_subpixelBits - 1);
	const deInt32								lineWidth			= (m_lineWidth > 1.0f) ? deFloorFloatToInt32(m_lineWidth + 0.5f) : 1;
	const bool									isXMajor			= de::abs((m_v1 - m_v0).x()) >= de::abs((m_v1 - m_v0).y());
	const tcu::IVec2							minorDirection		= (isXMajor) ? (tcu::IVec2(0, 1)) : (tcu::IVec2(1, 0));
	const int									minViewportLimit	= (isXMajor) ? (m_viewport.y()) : (m_viewport.x());
	const int									maxViewportLimit	= (isXMajor) ? (m_viewport.y() + m_viewport.w()) : (m_viewport.x() + m_viewport.z());
	const tcu::Vector<deInt64,2>				widthOffset			= -minorDirection.cast<deInt64>() * (toSubpixelCoord(lineWidth - 1, m_subpixelBits) / 2);
	const tcu::Vector<deInt64,2>				pa					= LineRasterUtil::toSubpixelVector(m_v0.xy(), m_subpixelBits) + widthOffset;
	const tcu::Vector<deInt64,2>				pb					= LineRasterUtil::toSubpixelVector(m_v1.xy(), m_subpixelBits) + widthOffset;
	const LineRasterUtil::SubpixelLineSegment	line				= LineRasterUtil::SubpixelLineSegment(pa, pb);

	int											packetNdx			= 0;
	int											xDelta				= (m_v1 - m_v0).x() > 0 ? 1 : -1;
	int											yDelta				= (m_v1 - m_v0).y() > 0 ? 1 : -1;

	while (m_curPos.y() <= m_bboxMax.y() && m_curPos.y() >= m_bboxMin.y() && packetNdx < maxFragmentPackets)
	{
		const tcu::Vector<deInt64,2> diamondPosition = LineRasterUtil::toSubpixelVector(m_curPos, m_subpixelBits) + tcu::Vector<deInt64,2>(halfPixel,halfPixel);

		// Should current fragment be drawn? == does the segment exit this diamond?
		if (LineRasterUtil::doesLineSegmentExitDiamond(line, diamondPosition, m_subpixelBits))
		{
			const tcu::Vector<deInt64,2>	pr					= diamondPosition;
			const float						t					= tcu::dot((pr - pa).asFloat(), (pb - pa).asFloat()) / tcu::lengthSquared(pb.asFloat() - pa.asFloat());

			// Rasterize on only fragments that are would end up in the viewport (i.e. visible)
			const int						fragmentLocation	= (isXMajor) ? (m_curPos.y()) : (m_curPos.x());
			const int						rowFragBegin		= de::max(0, minViewportLimit - fragmentLocation);
			const int						rowFragEnd			= de::min(maxViewportLimit - fragmentLocation, lineWidth);

			int stippleBit = (m_stippleCounter / m_stippleFactor) % 16;
			bool stipplePass = (m_stipplePattern & (1 << stippleBit)) != 0;
			m_stippleCounter++;

			if (stipplePass)
			{
				// Wide lines require multiple fragments.
				for (; rowFragBegin + m_curRowFragment < rowFragEnd; m_curRowFragment++)
				{
					const int			replicationId	= rowFragBegin + m_curRowFragment;
					const tcu::IVec2	fragmentPos		= m_curPos + minorDirection * replicationId;

					// We only rasterize visible area
					DE_ASSERT(LineRasterUtil::inViewport(fragmentPos, m_viewport));

					// Compute depth values.
					if (depthValues)
					{
						const float za = m_v0.z();
						const float zb = m_v1.z();

						depthValues[packetNdx*4+0] = (1 - t) * za + t * zb;
						depthValues[packetNdx*4+1] = 0;
						depthValues[packetNdx*4+2] = 0;
						depthValues[packetNdx*4+3] = 0;
					}

					{
						// output this fragment
						// \note In order to make consistent output with multisampled line rasterization, output "barycentric" coordinates
						FragmentPacket& packet = fragmentPackets[packetNdx];

						const tcu::Vec4		b0		= tcu::Vec4(1 - t);
						const tcu::Vec4		b1		= tcu::Vec4(t);
						const tcu::Vec4		ooSum	= 1.0f / (b0 + b1);

						packet.position			= fragmentPos;
						packet.coverage			= getCoverageBit(1, 0, 0, 0);
						packet.barycentric[0]	= b0 * ooSum;
						packet.barycentric[1]	= b1 * ooSum;
						packet.barycentric[2]	= tcu::Vec4(0.0f);

						packetNdx += 1;
					}

					if (packetNdx == maxFragmentPackets)
					{
						m_curRowFragment++; // don't redraw this fragment again next time
						m_stippleCounter--; // reuse same stipple counter next time
						numPacketsRasterized = packetNdx;
						return;
					}
				}

				m_curRowFragment = 0;
			}
		}

		m_curPos.x() += xDelta;
		if (m_curPos.x() > m_bboxMax.x() || m_curPos.x() < m_bboxMin.x())
		{
			m_curPos.y() += yDelta;
			m_curPos.x() = xDelta > 0 ? m_bboxMin.x() : m_bboxMax.x();
		}
	}

	DE_ASSERT(packetNdx <= maxFragmentPackets);
	numPacketsRasterized = packetNdx;
}

MultiSampleLineRasterizer::MultiSampleLineRasterizer (const int numSamples, const tcu::IVec4& viewport, const int subpixelBits)
	: m_numSamples			(numSamples)
	, m_triangleRasterizer0 (viewport, m_numSamples, RasterizationState(), subpixelBits)
	, m_triangleRasterizer1 (viewport, m_numSamples, RasterizationState(), subpixelBits)
{
}

MultiSampleLineRasterizer::~MultiSampleLineRasterizer ()
{
}

void MultiSampleLineRasterizer::init (const tcu::Vec4& v0, const tcu::Vec4& v1, float lineWidth)
{
	// allow creation of single sampled rasterizer objects but do not allow using them
	DE_ASSERT(m_numSamples > 1);

	const tcu::Vec2 lineVec		= tcu::Vec2(tcu::Vec4(v1).xy()) - tcu::Vec2(tcu::Vec4(v0).xy());
	const tcu::Vec2 normal2		= tcu::normalize(tcu::Vec2(-lineVec[1], lineVec[0]));
	const tcu::Vec4 normal4		= tcu::Vec4(normal2.x(), normal2.y(), 0, 0);
	const float offset			= lineWidth / 2.0f;

	const tcu::Vec4 p0 = v0 + normal4 * offset;
	const tcu::Vec4 p1 = v0 - normal4 * offset;
	const tcu::Vec4 p2 = v1 - normal4 * offset;
	const tcu::Vec4 p3 = v1 + normal4 * offset;

	// Edge 0 -> 1 is always along the line and edge 1 -> 2 is in 90 degree angle to the line
	m_triangleRasterizer0.init(p0, p3, p2);
	m_triangleRasterizer1.init(p2, p1, p0);
}

void MultiSampleLineRasterizer::rasterize (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
{
	DE_ASSERT(maxFragmentPackets > 0);

	m_triangleRasterizer0.rasterize(fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);

	// Remove 3rd barycentric value and rebalance. Lines do not have non-zero barycentric at index 2
	for (int packNdx = 0; packNdx < numPacketsRasterized; ++packNdx)
	for (int fragNdx = 0; fragNdx < 4; fragNdx++)
	{
		float removedValue = fragmentPackets[packNdx].barycentric[2][fragNdx];
		fragmentPackets[packNdx].barycentric[2][fragNdx] = 0.0f;
		fragmentPackets[packNdx].barycentric[1][fragNdx] += removedValue;
	}

	// rasterizer 0 filled the whole buffer?
	if (numPacketsRasterized == maxFragmentPackets)
		return;

	{
		FragmentPacket* const nextFragmentPackets	= fragmentPackets + numPacketsRasterized;
		float* nextDepthValues						= (depthValues) ? (depthValues+4*numPacketsRasterized*m_numSamples) : (DE_NULL);
		int numPacketsRasterized2					= 0;

		m_triangleRasterizer1.rasterize(nextFragmentPackets, nextDepthValues, maxFragmentPackets - numPacketsRasterized, numPacketsRasterized2);

		numPacketsRasterized += numPacketsRasterized2;

		// Fix swapped barycentrics in the second triangle
		for (int packNdx = 0; packNdx < numPacketsRasterized2; ++packNdx)
		for (int fragNdx = 0; fragNdx < 4; fragNdx++)
		{
			float removedValue = nextFragmentPackets[packNdx].barycentric[2][fragNdx];
			nextFragmentPackets[packNdx].barycentric[2][fragNdx] = 0.0f;
			nextFragmentPackets[packNdx].barycentric[1][fragNdx] += removedValue;

			// edge has reversed direction
			std::swap(nextFragmentPackets[packNdx].barycentric[0][fragNdx], nextFragmentPackets[packNdx].barycentric[1][fragNdx]);
		}
	}
}

LineExitDiamondGenerator::LineExitDiamondGenerator (const int subpixelBits)
	: m_subpixelBits(subpixelBits)
{
}

LineExitDiamondGenerator::~LineExitDiamondGenerator (void)
{
}

void LineExitDiamondGenerator::init (const tcu::Vec4& v0, const tcu::Vec4& v1)
{
	const deInt64					x0				= toSubpixelCoord(v0.x(), m_subpixelBits);
	const deInt64					y0				= toSubpixelCoord(v0.y(), m_subpixelBits);
	const deInt64					x1				= toSubpixelCoord(v1.x(), m_subpixelBits);
	const deInt64					y1				= toSubpixelCoord(v1.y(), m_subpixelBits);

	// line endpoints might be perturbed, add some margin
	const deInt64					xMin			= de::min(x0, x1) - toSubpixelCoord(1, m_subpixelBits);
	const deInt64					xMax			= de::max(x0, x1) + toSubpixelCoord(1, m_subpixelBits);
	const deInt64					yMin			= de::min(y0, y1) - toSubpixelCoord(1, m_subpixelBits);
	const deInt64					yMax			= de::max(y0, y1) + toSubpixelCoord(1, m_subpixelBits);

	m_bboxMin.x() = floorSubpixelToPixelCoord(xMin, m_subpixelBits, true);
	m_bboxMin.y() = floorSubpixelToPixelCoord(yMin, m_subpixelBits, true);
	m_bboxMax.x() = ceilSubpixelToPixelCoord (xMax, m_subpixelBits, true);
	m_bboxMax.y() = ceilSubpixelToPixelCoord (yMax, m_subpixelBits, true);

	m_v0 = v0;
	m_v1 = v1;

	m_curPos = m_bboxMin;
}

void LineExitDiamondGenerator::rasterize (LineExitDiamond* const lineDiamonds, const int maxDiamonds, int& numWritten)
{
	DE_ASSERT(maxDiamonds > 0);

	const deInt64								halfPixel			= 1ll << (m_subpixelBits - 1);
	const tcu::Vector<deInt64,2>				pa					= LineRasterUtil::toSubpixelVector(m_v0.xy(), m_subpixelBits);
	const tcu::Vector<deInt64,2>				pb					= LineRasterUtil::toSubpixelVector(m_v1.xy(), m_subpixelBits);
	const LineRasterUtil::SubpixelLineSegment	line				= LineRasterUtil::SubpixelLineSegment(pa, pb);

	int											diamondNdx			= 0;

	while (m_curPos.y() <= m_bboxMax.y() && diamondNdx < maxDiamonds)
	{
		const tcu::Vector<deInt64,2> diamondPosition = LineRasterUtil::toSubpixelVector(m_curPos, m_subpixelBits) + tcu::Vector<deInt64,2>(halfPixel,halfPixel);

		if (LineRasterUtil::doesLineSegmentExitDiamond(line, diamondPosition, m_subpixelBits))
		{
			LineExitDiamond& packet = lineDiamonds[diamondNdx];
			packet.position = m_curPos;
			++diamondNdx;
		}

		++m_curPos.x();
		if (m_curPos.x() > m_bboxMax.x())
		{
			++m_curPos.y();
			m_curPos.x() = m_bboxMin.x();
		}
	}

	DE_ASSERT(diamondNdx <= maxDiamonds);
	numWritten = diamondNdx;
}

} // rr