Merge "Merge "Further relax line verification in primitive bbox tests" into nougat...
[platform/upstream/VK-GL-CTS.git] / framework / referencerenderer / rrRasterizer.cpp
1 /*-------------------------------------------------------------------------
2  * drawElements Quality Program Reference Renderer
3  * -----------------------------------------------
4  *
5  * Copyright 2014 The Android Open Source Project
6  *
7  * Licensed under the Apache License, Version 2.0 (the "License");
8  * you may not use this file except in compliance with the License.
9  * You may obtain a copy of the License at
10  *
11  *      http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing, software
14  * distributed under the License is distributed on an "AS IS" BASIS,
15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16  * See the License for the specific language governing permissions and
17  * limitations under the License.
18  *
19  *//*!
20  * \file
21  * \brief Reference rasterizer
22  *//*--------------------------------------------------------------------*/
23
24 #include "rrRasterizer.hpp"
25 #include "deMath.h"
26 #include "tcuVectorUtil.hpp"
27
28 namespace rr
29 {
30
31 inline deInt64 toSubpixelCoord (float v)
32 {
33         return (deInt64)(v * (1<<RASTERIZER_SUBPIXEL_BITS) + (v < 0.f ? -0.5f : 0.5f));
34 }
35
36 inline deInt64 toSubpixelCoord (deInt32 v)
37 {
38         return v << RASTERIZER_SUBPIXEL_BITS;
39 }
40
41 inline deInt32 ceilSubpixelToPixelCoord (deInt64 coord, bool fillEdge)
42 {
43         if (coord >= 0)
44                 return (deInt32)((coord + ((1ll<<RASTERIZER_SUBPIXEL_BITS) - (fillEdge ? 0 : 1))) >> RASTERIZER_SUBPIXEL_BITS);
45         else
46                 return (deInt32)((coord + (fillEdge ? 1 : 0)) >> RASTERIZER_SUBPIXEL_BITS);
47 }
48
49 inline deInt32 floorSubpixelToPixelCoord (deInt64 coord, bool fillEdge)
50 {
51         if (coord >= 0)
52                 return (deInt32)((coord - (fillEdge ? 1 : 0)) >> RASTERIZER_SUBPIXEL_BITS);
53         else
54                 return (deInt32)((coord - ((1ll<<RASTERIZER_SUBPIXEL_BITS) - (fillEdge ? 0 : 1))) >> RASTERIZER_SUBPIXEL_BITS);
55 }
56
57 static inline void initEdgeCCW (EdgeFunction& edge, const HorizontalFill horizontalFill, const VerticalFill verticalFill, const deInt64 x0, const deInt64 y0, const deInt64 x1, const deInt64 y1)
58 {
59         // \note See EdgeFunction documentation for details.
60
61         const deInt64   xd                      = x1-x0;
62         const deInt64   yd                      = y1-y0;
63         bool                    inclusive       = false;        //!< Inclusive in CCW orientation.
64
65         if (yd == 0)
66                 inclusive = verticalFill == FILL_BOTTOM ? xd >= 0 : xd <= 0;
67         else
68                 inclusive = horizontalFill == FILL_LEFT ? yd <= 0 : yd >= 0;
69
70         edge.a                  = (y0 - y1);
71         edge.b                  = (x1 - x0);
72         edge.c                  = x0*y1 - y0*x1;
73         edge.inclusive  = inclusive; //!< \todo [pyry] Swap for CW triangles
74 }
75
76 static inline void reverseEdge (EdgeFunction& edge)
77 {
78         edge.a                  = -edge.a;
79         edge.b                  = -edge.b;
80         edge.c                  = -edge.c;
81         edge.inclusive  = !edge.inclusive;
82 }
83
84 static inline deInt64 evaluateEdge (const EdgeFunction& edge, const deInt64 x, const deInt64 y)
85 {
86         return edge.a*x + edge.b*y + edge.c;
87 }
88
89 static inline bool isInsideCCW (const EdgeFunction& edge, const deInt64 edgeVal)
90 {
91         return edge.inclusive ? (edgeVal >= 0) : (edgeVal > 0);
92 }
93
94 namespace LineRasterUtil
95 {
96
97 struct SubpixelLineSegment
98 {
99         const tcu::Vector<deInt64,2>    m_v0;
100         const tcu::Vector<deInt64,2>    m_v1;
101
102         SubpixelLineSegment (const tcu::Vector<deInt64,2>& v0, const tcu::Vector<deInt64,2>& v1)
103                 : m_v0(v0)
104                 , m_v1(v1)
105         {
106         }
107
108         tcu::Vector<deInt64,2> direction (void) const
109         {
110                 return m_v1 - m_v0;
111         }
112 };
113
114 enum LINE_SIDE
115 {
116         LINE_SIDE_INTERSECT = 0,
117         LINE_SIDE_LEFT,
118         LINE_SIDE_RIGHT
119 };
120
121 static tcu::Vector<deInt64,2> toSubpixelVector (const tcu::Vec2& v)
122 {
123         return tcu::Vector<deInt64,2>(toSubpixelCoord(v.x()), toSubpixelCoord(v.y()));
124 }
125
126 static tcu::Vector<deInt64,2> toSubpixelVector (const tcu::IVec2& v)
127 {
128         return tcu::Vector<deInt64,2>(toSubpixelCoord(v.x()), toSubpixelCoord(v.y()));
129 }
130
131 #if defined(DE_DEBUG)
132 static bool isTheCenterOfTheFragment (const tcu::Vector<deInt64,2>& a)
133 {
134         const deUint64 pixelSize = 1ll << (RASTERIZER_SUBPIXEL_BITS);
135         const deUint64 halfPixel = 1ll << (RASTERIZER_SUBPIXEL_BITS-1);
136         return  ((a.x() & (pixelSize-1)) == halfPixel &&
137                                 (a.y() & (pixelSize-1)) == halfPixel);
138 }
139
140 static bool inViewport (const tcu::IVec2& p, const tcu::IVec4& viewport)
141 {
142         return  p.x() >= viewport.x() &&
143                         p.y() >= viewport.y() &&
144                         p.x() <  viewport.x() + viewport.z() &&
145                         p.y() <  viewport.y() + viewport.w();
146 }
147 #endif // DE_DEBUG
148
149 // returns true if vertex is on the left side of the line
150 static bool vertexOnLeftSideOfLine (const tcu::Vector<deInt64,2>& p, const SubpixelLineSegment& l)
151 {
152         const tcu::Vector<deInt64,2> u = l.direction();
153         const tcu::Vector<deInt64,2> v = ( p - l.m_v0);
154         const deInt64 crossProduct = (u.x() * v.y() - u.y() * v.x());
155         return crossProduct < 0;
156 }
157
158 // returns true if vertex is on the right side of the line
159 static bool vertexOnRightSideOfLine (const tcu::Vector<deInt64,2>& p, const SubpixelLineSegment& l)
160 {
161         const tcu::Vector<deInt64,2> u = l.direction();
162         const tcu::Vector<deInt64,2> v = ( p - l.m_v0);
163         const deInt64 crossProduct = (u.x() * v.y() - u.y() * v.x());
164         return crossProduct > 0;
165 }
166
167 // returns true if vertex is on the line
168 static bool vertexOnLine (const tcu::Vector<deInt64,2>& p, const SubpixelLineSegment& l)
169 {
170         const tcu::Vector<deInt64,2> u = l.direction();
171         const tcu::Vector<deInt64,2> v = ( p - l.m_v0);
172         const deInt64 crossProduct = (u.x() * v.y() - u.y() * v.x());
173         return crossProduct == 0; // cross product == 0
174 }
175
176 // returns true if vertex is on the line segment
177 static bool vertexOnLineSegment (const tcu::Vector<deInt64,2>& p, const SubpixelLineSegment& l)
178 {
179         if (!vertexOnLine(p, l))
180                 return false;
181
182         const tcu::Vector<deInt64,2> v  = l.direction();
183         const tcu::Vector<deInt64,2> u1 = ( p - l.m_v0);
184         const tcu::Vector<deInt64,2> u2 = ( p - l.m_v1);
185
186         if (v.x() == 0 && v.y() == 0)
187                 return false;
188
189         return  tcu::dot( v, u1) >= 0 &&
190                         tcu::dot(-v, u2) >= 0; // dot (A->B, A->V) >= 0 and dot (B->A, B->V) >= 0
191 }
192
193 static LINE_SIDE getVertexSide (const tcu::Vector<deInt64,2>& v, const SubpixelLineSegment& l)
194 {
195         if (vertexOnLeftSideOfLine(v, l))
196                 return LINE_SIDE_LEFT;
197         else if (vertexOnRightSideOfLine(v, l))
198                 return LINE_SIDE_RIGHT;
199         else if (vertexOnLine(v, l))
200                 return LINE_SIDE_INTERSECT;
201         else
202         {
203                 DE_ASSERT(false);
204                 return LINE_SIDE_INTERSECT;
205         }
206 }
207
208 // returns true if angle between line and given cornerExitNormal is in range (-45, 45)
209 bool lineInCornerAngleRange (const SubpixelLineSegment& line, const tcu::Vector<deInt64,2>& cornerExitNormal)
210 {
211         // v0 -> v1 has angle difference to cornerExitNormal in range (-45, 45)
212         const tcu::Vector<deInt64,2> v = line.direction();
213         const deInt64 dotProduct = dot(v, cornerExitNormal);
214
215         // dotProduct > |v1-v0|*|cornerExitNormal|/sqrt(2)
216         if (dotProduct < 0)
217                 return false;
218         return 2 * dotProduct * dotProduct > tcu::lengthSquared(v)*tcu::lengthSquared(cornerExitNormal);
219 }
220
221 // returns true if angle between line and given cornerExitNormal is in range (-135, 135)
222 bool lineInCornerOutsideAngleRange (const SubpixelLineSegment& line, const tcu::Vector<deInt64,2>& cornerExitNormal)
223 {
224         // v0 -> v1 has angle difference to cornerExitNormal in range (-135, 135)
225         const tcu::Vector<deInt64,2> v = line.direction();
226         const deInt64 dotProduct = dot(v, cornerExitNormal);
227
228         // dotProduct > -|v1-v0|*|cornerExitNormal|/sqrt(2)
229         if (dotProduct >= 0)
230                 return true;
231         return 2 * (-dotProduct) * (-dotProduct) < tcu::lengthSquared(v)*tcu::lengthSquared(cornerExitNormal);
232 }
233
234 bool doesLineSegmentExitDiamond (const SubpixelLineSegment& line, const tcu::Vector<deInt64,2>& diamondCenter)
235 {
236         DE_ASSERT(isTheCenterOfTheFragment(diamondCenter));
237
238         // Diamond Center is at diamondCenter in subpixel coords
239
240         const deInt64 halfPixel = 1ll << (RASTERIZER_SUBPIXEL_BITS-1);
241
242         // Reject distant diamonds early
243         {
244                 const tcu::Vector<deInt64,2>    u                               = line.direction();
245                 const tcu::Vector<deInt64,2>    v                               = (diamondCenter - line.m_v0);
246                 const deInt64                                   crossProduct    = (u.x() * v.y() - u.y() * v.x());
247
248                 // crossProduct = |p| |l| sin(theta)
249                 // distanceFromLine = |p| sin(theta)
250                 // => distanceFromLine = crossProduct / |l|
251                 //
252                 // |distanceFromLine| > C
253                 // => distanceFromLine^2 > C^2
254                 // => crossProduct^2 / |l|^2 > C^2
255                 // => crossProduct^2 > |l|^2 * C^2
256
257                 const deInt64   floorSqrtMaxInt64                       = 3037000499LL; //!< floor(sqrt(MAX_INT64))
258
259                 const deInt64   broadRejectDistance                     = 2 * halfPixel;
260                 const deInt64   broadRejectDistanceSquared      = broadRejectDistance * broadRejectDistance;
261                 const bool              crossProductOverflows           = (crossProduct > floorSqrtMaxInt64 || crossProduct < -floorSqrtMaxInt64);
262                 const deInt64   crossProductSquared                     = (crossProductOverflows) ? (0) : (crossProduct * crossProduct); // avoid overflow
263                 const deInt64   lineLengthSquared                       = tcu::lengthSquared(u);
264                 const bool              limitValueCouldOverflow         = ((64 - deClz64(lineLengthSquared)) + (64 - deClz64(broadRejectDistanceSquared))) > 63;
265                 const deInt64   limitValue                                      = (limitValueCouldOverflow) ? (0) : (lineLengthSquared * broadRejectDistanceSquared); // avoid overflow
266
267                 // only cross overflows
268                 if (crossProductOverflows && !limitValueCouldOverflow)
269                         return false;
270
271                 // both representable
272                 if (!crossProductOverflows && !limitValueCouldOverflow)
273                 {
274                         if (crossProductSquared > limitValue)
275                                 return false;
276                 }
277         }
278
279         const struct DiamondBound
280         {
281                 tcu::Vector<deInt64,2>  p0;
282                 tcu::Vector<deInt64,2>  p1;
283                 bool                                    edgeInclusive; // would a point on the bound be inside of the region
284         } bounds[] =
285         {
286                 { diamondCenter + tcu::Vector<deInt64,2>(0,                             -halfPixel),    diamondCenter + tcu::Vector<deInt64,2>(-halfPixel,      0),                              false  },
287                 { diamondCenter + tcu::Vector<deInt64,2>(-halfPixel,    0),                             diamondCenter + tcu::Vector<deInt64,2>(0,                       halfPixel),              false  },
288                 { diamondCenter + tcu::Vector<deInt64,2>(0,                             halfPixel),             diamondCenter + tcu::Vector<deInt64,2>(halfPixel,       0),                              true   },
289                 { diamondCenter + tcu::Vector<deInt64,2>(halfPixel,             0),                             diamondCenter + tcu::Vector<deInt64,2>(0,                       -halfPixel),     true   },
290         };
291
292         const struct DiamondCorners
293         {
294                 enum CORNER_EDGE_CASE_BEHAVIOR
295                 {
296                         CORNER_EDGE_CASE_NONE,                                                  // if the line intersects just a corner, no entering or exiting
297                         CORNER_EDGE_CASE_HIT,                                                   // if the line intersects just a corner, entering and exit
298                         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)
299                         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)
300                 };
301                 enum CORNER_START_CASE_BEHAVIOR
302                 {
303                         CORNER_START_CASE_NONE,                                                 // the line starting point is outside, no exiting
304                         CORNER_START_CASE_OUTSIDE,                                              // exit, if line does not intersect the region (preturbing moves the start point inside)
305                         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.
306                         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.
307                 };
308                 enum CORNER_END_CASE_BEHAVIOR
309                 {
310                         CORNER_END_CASE_NONE,                                                   // end is inside, no exiting (preturbing moves the line end inside)
311                         CORNER_END_CASE_DIRECTION,                                              // exit, if line intersected the region (preturbing moves the line end outside)
312                         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)
313                         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)
314                 };
315
316                 tcu::Vector<deInt64,2>          dp;
317                 bool                                            pointInclusive;                 // would a point in this corner intersect with the region
318                 CORNER_EDGE_CASE_BEHAVIOR       lineBehavior;                   // would a line segment going through this corner intersect with the region
319                 CORNER_START_CASE_BEHAVIOR      startBehavior;                  // how the corner behaves if the start point at the corner
320                 CORNER_END_CASE_BEHAVIOR        endBehavior;                    // how the corner behaves if the end point at the corner
321         } corners[] =
322         {
323                 { 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},
324                 { tcu::Vector<deInt64,2>(-halfPixel,    0),                             false,  DiamondCorners::CORNER_EDGE_CASE_NONE,                                  DiamondCorners::CORNER_START_CASE_NONE,                         DiamondCorners::CORNER_END_CASE_DIRECTION                                       },
325                 { 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     },
326                 { tcu::Vector<deInt64,2>(halfPixel,             0),                             true,   DiamondCorners::CORNER_EDGE_CASE_HIT,                                   DiamondCorners::CORNER_START_CASE_OUTSIDE,                      DiamondCorners::CORNER_END_CASE_NONE                                            },
327         };
328
329         // Corner cases at the corners
330         for (int ndx = 0; ndx < DE_LENGTH_OF_ARRAY(corners); ++ndx)
331         {
332                 const tcu::Vector<deInt64,2> p  = diamondCenter + corners[ndx].dp;
333                 const bool intersectsAtCorner   = LineRasterUtil::vertexOnLineSegment(p, line);
334
335                 if (!intersectsAtCorner)
336                         continue;
337
338                 // line segment body intersects with the corner
339                 if (p != line.m_v0 && p != line.m_v1)
340                 {
341                         if (corners[ndx].lineBehavior == DiamondCorners::CORNER_EDGE_CASE_HIT)
342                                 return true;
343
344                         // endpoint in (+X, -Y) (X or Y may be 0) direction <==> x*y <= 0
345                         if (corners[ndx].lineBehavior == DiamondCorners::CORNER_EDGE_CASE_HIT_FIRST_QUARTER &&
346                                 (line.direction().x() * line.direction().y()) <= 0)
347                                 return true;
348
349                         // endpoint in (+X, +Y) (Y > 0) direction <==> x*y > 0
350                         if (corners[ndx].lineBehavior == DiamondCorners::CORNER_EDGE_CASE_HIT_SECOND_QUARTER &&
351                                 (line.direction().x() * line.direction().y()) > 0)
352                                 return true;
353                 }
354
355                 // line exits the area at the corner
356                 if (lineInCornerAngleRange(line, corners[ndx].dp))
357                 {
358                         const bool startIsInside = corners[ndx].pointInclusive || p != line.m_v0;
359                         const bool endIsOutside = !corners[ndx].pointInclusive || p != line.m_v1;
360
361                         // starting point is inside the region and end endpoint is outside
362                         if (startIsInside && endIsOutside)
363                                 return true;
364                 }
365
366                 // line end is at the corner
367                 if (p == line.m_v1)
368                 {
369                         if (corners[ndx].endBehavior == DiamondCorners::CORNER_END_CASE_DIRECTION ||
370                                 corners[ndx].endBehavior == DiamondCorners::CORNER_END_CASE_DIRECTION_AND_FIRST_QUARTER ||
371                                 corners[ndx].endBehavior == DiamondCorners::CORNER_END_CASE_DIRECTION_AND_SECOND_QUARTER)
372                         {
373                                 // did the line intersect the region
374                                 if (lineInCornerAngleRange(line, corners[ndx].dp))
375                                         return true;
376                         }
377
378                         // due to the perturbed endpoint, lines at this the angle will cause and enter-exit pair
379                         if (corners[ndx].endBehavior == DiamondCorners::CORNER_END_CASE_DIRECTION_AND_FIRST_QUARTER &&
380                                 line.direction().x() < 0 &&
381                                 line.direction().y() > 0)
382                                 return true;
383                         if (corners[ndx].endBehavior == DiamondCorners::CORNER_END_CASE_DIRECTION_AND_SECOND_QUARTER &&
384                                 line.direction().x() > 0 &&
385                                 line.direction().y() > 0)
386                                 return true;
387                 }
388
389                 // line start is at the corner
390                 if (p == line.m_v0)
391                 {
392                         if (corners[ndx].startBehavior == DiamondCorners::CORNER_START_CASE_OUTSIDE)
393                         {
394                                 // if the line is not going inside, it will exit
395                                 if (lineInCornerOutsideAngleRange(line, corners[ndx].dp))
396                                         return true;
397                         }
398
399                         // exit, if line the angle between line vector and X-axis is in range (0, 45] in positive Y side.
400                         if (corners[ndx].startBehavior == DiamondCorners::CORNER_START_CASE_POSITIVE_Y_45 &&
401                                 line.direction().x() > 0 &&
402                                 line.direction().y() > 0 &&
403                                 line.direction().y() <= line.direction().x())
404                                 return true;
405
406                         // exit, if line the angle between line vector and X-axis is in range [0, 45] in negative Y side.
407                         if (corners[ndx].startBehavior == DiamondCorners::CORNER_START_CASE_NEGATIVE_Y_45 &&
408                                  line.direction().x() > 0 &&
409                                  line.direction().y() <= 0 &&
410                                 -line.direction().y() <= line.direction().x())
411                                 return true;
412                 }
413         }
414
415         // Does the line intersect boundary at the left == exits the diamond
416         for (int ndx = 0; ndx < DE_LENGTH_OF_ARRAY(bounds); ++ndx)
417         {
418                 const bool startVertexInside =  LineRasterUtil::vertexOnLeftSideOfLine                                          (line.m_v0, LineRasterUtil::SubpixelLineSegment(bounds[ndx].p0, bounds[ndx].p1)) ||
419                                                                                 (bounds[ndx].edgeInclusive && LineRasterUtil::vertexOnLine      (line.m_v0, LineRasterUtil::SubpixelLineSegment(bounds[ndx].p0, bounds[ndx].p1)));
420                 const bool endVertexInside =    LineRasterUtil::vertexOnLeftSideOfLine                                          (line.m_v1, LineRasterUtil::SubpixelLineSegment(bounds[ndx].p0, bounds[ndx].p1)) ||
421                                                                                 (bounds[ndx].edgeInclusive && LineRasterUtil::vertexOnLine      (line.m_v1, LineRasterUtil::SubpixelLineSegment(bounds[ndx].p0, bounds[ndx].p1)));
422
423                 // start must be on inside this half space (left or at the inclusive boundary)
424                 if (!startVertexInside)
425                         continue;
426
427                 // end must be outside of this half-space (right or at non-inclusive boundary)
428                 if (endVertexInside)
429                         continue;
430
431                 // Does the line via v0 and v1 intersect the line segment p0-p1
432                 // <==> p0 and p1 are the different sides (LEFT, RIGHT) of the v0-v1 line.
433                 // Corners are not allowed, they are checked already
434                 LineRasterUtil::LINE_SIDE sideP0 = LineRasterUtil::getVertexSide(bounds[ndx].p0, line);
435                 LineRasterUtil::LINE_SIDE sideP1 = LineRasterUtil::getVertexSide(bounds[ndx].p1, line);
436
437                 if (sideP0 != LineRasterUtil::LINE_SIDE_INTERSECT &&
438                         sideP1 != LineRasterUtil::LINE_SIDE_INTERSECT &&
439                         sideP0 != sideP1)
440                         return true;
441         }
442
443         return false;
444 }
445
446 } // LineRasterUtil
447
448 TriangleRasterizer::TriangleRasterizer (const tcu::IVec4& viewport, const int numSamples, const RasterizationState& state)
449         : m_viewport                            (viewport)
450         , m_numSamples                          (numSamples)
451         , m_winding                                     (state.winding)
452         , m_horizontalFill                      (state.horizontalFill)
453         , m_verticalFill                        (state.verticalFill)
454         , m_face                                        (FACETYPE_LAST)
455         , m_viewportOrientation         (state.viewportOrientation)
456 {
457 }
458
459 /*--------------------------------------------------------------------*//*!
460  * \brief Initialize triangle rasterization
461  * \param v0 Screen-space coordinates (x, y, z) and 1/w for vertex 0.
462  * \param v1 Screen-space coordinates (x, y, z) and 1/w for vertex 1.
463  * \param v2 Screen-space coordinates (x, y, z) and 1/w for vertex 2.
464  *//*--------------------------------------------------------------------*/
465 void TriangleRasterizer::init (const tcu::Vec4& v0, const tcu::Vec4& v1, const tcu::Vec4& v2)
466 {
467         m_v0 = v0;
468         m_v1 = v1;
469         m_v2 = v2;
470
471         // Positions in fixed-point coordinates.
472         const deInt64   x0              = toSubpixelCoord(v0.x());
473         const deInt64   y0              = toSubpixelCoord(v0.y());
474         const deInt64   x1              = toSubpixelCoord(v1.x());
475         const deInt64   y1              = toSubpixelCoord(v1.y());
476         const deInt64   x2              = toSubpixelCoord(v2.x());
477         const deInt64   y2              = toSubpixelCoord(v2.y());
478
479         // Initialize edge functions.
480         if (m_winding == WINDING_CCW)
481         {
482                 initEdgeCCW(m_edge01, m_horizontalFill, m_verticalFill, x0, y0, x1, y1);
483                 initEdgeCCW(m_edge12, m_horizontalFill, m_verticalFill, x1, y1, x2, y2);
484                 initEdgeCCW(m_edge20, m_horizontalFill, m_verticalFill, x2, y2, x0, y0);
485         }
486         else
487         {
488                 // Reverse edges
489                 initEdgeCCW(m_edge01, m_horizontalFill, m_verticalFill, x1, y1, x0, y0);
490                 initEdgeCCW(m_edge12, m_horizontalFill, m_verticalFill, x2, y2, x1, y1);
491                 initEdgeCCW(m_edge20, m_horizontalFill, m_verticalFill, x0, y0, x2, y2);
492         }
493
494         // Determine face.
495         const deInt64   s                               = evaluateEdge(m_edge01, x2, y2);
496         const bool              positiveArea    = (m_winding == WINDING_CCW) ? (s > 0) : (s < 0);
497
498         if (m_viewportOrientation == VIEWPORTORIENTATION_UPPER_LEFT)
499                 m_face = positiveArea ? FACETYPE_BACK : FACETYPE_FRONT;
500         else
501                 m_face = positiveArea ? FACETYPE_FRONT : FACETYPE_BACK;
502
503         if (!positiveArea)
504         {
505                 // Reverse edges so that we can use CCW area tests & interpolation
506                 reverseEdge(m_edge01);
507                 reverseEdge(m_edge12);
508                 reverseEdge(m_edge20);
509         }
510
511         // Bounding box
512         const deInt64   xMin    = de::min(de::min(x0, x1), x2);
513         const deInt64   xMax    = de::max(de::max(x0, x1), x2);
514         const deInt64   yMin    = de::min(de::min(y0, y1), y2);
515         const deInt64   yMax    = de::max(de::max(y0, y1), y2);
516
517         m_bboxMin.x() = floorSubpixelToPixelCoord       (xMin, m_horizontalFill == FILL_LEFT);
518         m_bboxMin.y() = floorSubpixelToPixelCoord       (yMin, m_verticalFill   == FILL_BOTTOM);
519         m_bboxMax.x() = ceilSubpixelToPixelCoord        (xMax, m_horizontalFill == FILL_RIGHT);
520         m_bboxMax.y() = ceilSubpixelToPixelCoord        (yMax, m_verticalFill   == FILL_TOP);
521
522         // Clamp to viewport
523         const int               wX0             = m_viewport.x();
524         const int               wY0             = m_viewport.y();
525         const int               wX1             = wX0 + m_viewport.z() - 1;
526         const int               wY1             = wY0 + m_viewport.w() -1;
527
528         m_bboxMin.x() = de::clamp(m_bboxMin.x(), wX0, wX1);
529         m_bboxMin.y() = de::clamp(m_bboxMin.y(), wY0, wY1);
530         m_bboxMax.x() = de::clamp(m_bboxMax.x(), wX0, wX1);
531         m_bboxMax.y() = de::clamp(m_bboxMax.y(), wY0, wY1);
532
533         m_curPos = m_bboxMin;
534 }
535
536 void TriangleRasterizer::rasterizeSingleSample (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
537 {
538         DE_ASSERT(maxFragmentPackets > 0);
539
540         const deUint64  halfPixel       = 1ll << (RASTERIZER_SUBPIXEL_BITS-1);
541         int                             packetNdx       = 0;
542
543         // For depth interpolation; given barycentrics A, B, C = (1 - A - B)
544         // we can reformulate the usual z = z0*A + z1*B + z2*C into more
545         // stable equation z = A*(z0 - z2) + B*(z1 - z2) + z2.
546         const float             za                      = m_v0.z()-m_v2.z();
547         const float             zb                      = m_v1.z()-m_v2.z();
548         const float             zc                      = m_v2.z();
549
550         while (m_curPos.y() <= m_bboxMax.y() && packetNdx < maxFragmentPackets)
551         {
552                 const int               x0              = m_curPos.x();
553                 const int               y0              = m_curPos.y();
554
555                 // Subpixel coords
556                 const deInt64   sx0             = toSubpixelCoord(x0)   + halfPixel;
557                 const deInt64   sx1             = toSubpixelCoord(x0+1) + halfPixel;
558                 const deInt64   sy0             = toSubpixelCoord(y0)   + halfPixel;
559                 const deInt64   sy1             = toSubpixelCoord(y0+1) + halfPixel;
560
561                 const deInt64   sx[4]   = { sx0, sx1, sx0, sx1 };
562                 const deInt64   sy[4]   = { sy0, sy0, sy1, sy1 };
563
564                 // Viewport test
565                 const bool              outX1   = x0+1 == m_viewport.x()+m_viewport.z();
566                 const bool              outY1   = y0+1 == m_viewport.y()+m_viewport.w();
567
568                 DE_ASSERT(x0 < m_viewport.x()+m_viewport.z());
569                 DE_ASSERT(y0 < m_viewport.y()+m_viewport.w());
570
571                 // Edge values
572                 tcu::Vector<deInt64, 4> e01;
573                 tcu::Vector<deInt64, 4> e12;
574                 tcu::Vector<deInt64, 4> e20;
575
576                 // Coverage
577                 deUint64                coverage        = 0;
578
579                 // Evaluate edge values
580                 for (int i = 0; i < 4; i++)
581                 {
582                         e01[i] = evaluateEdge(m_edge01, sx[i], sy[i]);
583                         e12[i] = evaluateEdge(m_edge12, sx[i], sy[i]);
584                         e20[i] = evaluateEdge(m_edge20, sx[i], sy[i]);
585                 }
586
587                 // Compute coverage mask
588                 coverage = setCoverageValue(coverage, 1, 0, 0, 0,                                               isInsideCCW(m_edge01, e01[0]) && isInsideCCW(m_edge12, e12[0]) && isInsideCCW(m_edge20, e20[0]));
589                 coverage = setCoverageValue(coverage, 1, 1, 0, 0, !outX1 &&                             isInsideCCW(m_edge01, e01[1]) && isInsideCCW(m_edge12, e12[1]) && isInsideCCW(m_edge20, e20[1]));
590                 coverage = setCoverageValue(coverage, 1, 0, 1, 0, !outY1 &&                             isInsideCCW(m_edge01, e01[2]) && isInsideCCW(m_edge12, e12[2]) && isInsideCCW(m_edge20, e20[2]));
591                 coverage = setCoverageValue(coverage, 1, 1, 1, 0, !outX1 && !outY1 &&   isInsideCCW(m_edge01, e01[3]) && isInsideCCW(m_edge12, e12[3]) && isInsideCCW(m_edge20, e20[3]));
592
593                 // Advance to next location
594                 m_curPos.x() += 2;
595                 if (m_curPos.x() > m_bboxMax.x())
596                 {
597                         m_curPos.y() += 2;
598                         m_curPos.x()  = m_bboxMin.x();
599                 }
600
601                 if (coverage == 0)
602                         continue; // Discard.
603
604                 // Floating-point edge values for barycentrics etc.
605                 const tcu::Vec4         e01f    = e01.asFloat();
606                 const tcu::Vec4         e12f    = e12.asFloat();
607                 const tcu::Vec4         e20f    = e20.asFloat();
608
609                 // Compute depth values.
610                 if (depthValues)
611                 {
612                         const tcu::Vec4         edgeSum = e01f + e12f + e20f;
613                         const tcu::Vec4         z0              = e12f / edgeSum;
614                         const tcu::Vec4         z1              = e20f / edgeSum;
615
616                         depthValues[packetNdx*4+0] = z0[0]*za + z1[0]*zb + zc;
617                         depthValues[packetNdx*4+1] = z0[1]*za + z1[1]*zb + zc;
618                         depthValues[packetNdx*4+2] = z0[2]*za + z1[2]*zb + zc;
619                         depthValues[packetNdx*4+3] = z0[3]*za + z1[3]*zb + zc;
620                 }
621
622                 // Compute barycentrics and write out fragment packet
623                 {
624                         FragmentPacket& packet = fragmentPackets[packetNdx];
625
626                         const tcu::Vec4         b0              = e12f * m_v0.w();
627                         const tcu::Vec4         b1              = e20f * m_v1.w();
628                         const tcu::Vec4         b2              = e01f * m_v2.w();
629                         const tcu::Vec4         bSum    = b0 + b1 + b2;
630
631                         packet.position                 = tcu::IVec2(x0, y0);
632                         packet.coverage                 = coverage;
633                         packet.barycentric[0]   = b0 / bSum;
634                         packet.barycentric[1]   = b1 / bSum;
635                         packet.barycentric[2]   = 1.0f - packet.barycentric[0] - packet.barycentric[1];
636
637                         packetNdx += 1;
638                 }
639         }
640
641         DE_ASSERT(packetNdx <= maxFragmentPackets);
642         numPacketsRasterized = packetNdx;
643 }
644
645 // Sample positions - ordered as (x, y) list.
646
647 // \note Macros are used to eliminate function calls even in debug builds.
648 #define SAMPLE_POS_TO_SUBPIXEL_COORD(POS)       \
649         (deInt64)((POS) * (1<<RASTERIZER_SUBPIXEL_BITS) + 0.5f)
650
651 #define SAMPLE_POS(X, Y)        \
652         SAMPLE_POS_TO_SUBPIXEL_COORD(X), SAMPLE_POS_TO_SUBPIXEL_COORD(Y)
653
654 static const deInt64 s_samplePos2[] =
655 {
656         SAMPLE_POS(0.3f, 0.3f),
657         SAMPLE_POS(0.7f, 0.7f)
658 };
659
660 static const deInt64 s_samplePos4[] =
661 {
662         SAMPLE_POS(0.25f, 0.25f),
663         SAMPLE_POS(0.75f, 0.25f),
664         SAMPLE_POS(0.25f, 0.75f),
665         SAMPLE_POS(0.75f, 0.75f)
666 };
667 DE_STATIC_ASSERT(DE_LENGTH_OF_ARRAY(s_samplePos4) == 4*2);
668
669 static const deInt64 s_samplePos8[] =
670 {
671         SAMPLE_POS( 7.f/16.f,  9.f/16.f),
672         SAMPLE_POS( 9.f/16.f, 13.f/16.f),
673         SAMPLE_POS(11.f/16.f,  3.f/16.f),
674         SAMPLE_POS(13.f/16.f, 11.f/16.f),
675         SAMPLE_POS( 1.f/16.f,  7.f/16.f),
676         SAMPLE_POS( 5.f/16.f,  1.f/16.f),
677         SAMPLE_POS(15.f/16.f,  5.f/16.f),
678         SAMPLE_POS( 3.f/16.f, 15.f/16.f)
679 };
680 DE_STATIC_ASSERT(DE_LENGTH_OF_ARRAY(s_samplePos8) == 8*2);
681
682 static const deInt64 s_samplePos16[] =
683 {
684         SAMPLE_POS(1.f/8.f, 1.f/8.f),
685         SAMPLE_POS(3.f/8.f, 1.f/8.f),
686         SAMPLE_POS(5.f/8.f, 1.f/8.f),
687         SAMPLE_POS(7.f/8.f, 1.f/8.f),
688         SAMPLE_POS(1.f/8.f, 3.f/8.f),
689         SAMPLE_POS(3.f/8.f, 3.f/8.f),
690         SAMPLE_POS(5.f/8.f, 3.f/8.f),
691         SAMPLE_POS(7.f/8.f, 3.f/8.f),
692         SAMPLE_POS(1.f/8.f, 5.f/8.f),
693         SAMPLE_POS(3.f/8.f, 5.f/8.f),
694         SAMPLE_POS(5.f/8.f, 5.f/8.f),
695         SAMPLE_POS(7.f/8.f, 5.f/8.f),
696         SAMPLE_POS(1.f/8.f, 7.f/8.f),
697         SAMPLE_POS(3.f/8.f, 7.f/8.f),
698         SAMPLE_POS(5.f/8.f, 7.f/8.f),
699         SAMPLE_POS(7.f/8.f, 7.f/8.f)
700 };
701 DE_STATIC_ASSERT(DE_LENGTH_OF_ARRAY(s_samplePos16) == 16*2);
702
703 #undef SAMPLE_POS
704 #undef SAMPLE_POS_TO_SUBPIXEL_COORD
705
706 template<int NumSamples>
707 void TriangleRasterizer::rasterizeMultiSample (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
708 {
709         DE_ASSERT(maxFragmentPackets > 0);
710
711         const deInt64*  samplePos       = DE_NULL;
712         const deUint64  halfPixel       = 1ll << (RASTERIZER_SUBPIXEL_BITS-1);
713         int                             packetNdx       = 0;
714
715         // For depth interpolation, see rasterizeSingleSample
716         const float             za                      = m_v0.z()-m_v2.z();
717         const float             zb                      = m_v1.z()-m_v2.z();
718         const float             zc                      = m_v2.z();
719
720         switch (NumSamples)
721         {
722                 case 2:         samplePos = s_samplePos2;       break;
723                 case 4:         samplePos = s_samplePos4;       break;
724                 case 8:         samplePos = s_samplePos8;       break;
725                 case 16:        samplePos = s_samplePos16;      break;
726                 default:
727                         DE_ASSERT(false);
728         }
729
730         while (m_curPos.y() <= m_bboxMax.y() && packetNdx < maxFragmentPackets)
731         {
732                 const int               x0              = m_curPos.x();
733                 const int               y0              = m_curPos.y();
734
735                 // Base subpixel coords
736                 const deInt64   sx0             = toSubpixelCoord(x0);
737                 const deInt64   sx1             = toSubpixelCoord(x0+1);
738                 const deInt64   sy0             = toSubpixelCoord(y0);
739                 const deInt64   sy1             = toSubpixelCoord(y0+1);
740
741                 const deInt64   sx[4]   = { sx0, sx1, sx0, sx1 };
742                 const deInt64   sy[4]   = { sy0, sy0, sy1, sy1 };
743
744                 // Viewport test
745                 const bool              outX1   = x0+1 == m_viewport.x()+m_viewport.z();
746                 const bool              outY1   = y0+1 == m_viewport.y()+m_viewport.w();
747
748                 DE_ASSERT(x0 < m_viewport.x()+m_viewport.z());
749                 DE_ASSERT(y0 < m_viewport.y()+m_viewport.w());
750
751                 // Edge values
752                 tcu::Vector<deInt64, 4> e01[NumSamples];
753                 tcu::Vector<deInt64, 4> e12[NumSamples];
754                 tcu::Vector<deInt64, 4> e20[NumSamples];
755
756                 // Coverage
757                 deUint64                coverage        = 0;
758
759                 // Evaluate edge values at sample positions
760                 for (int sampleNdx = 0; sampleNdx < NumSamples; sampleNdx++)
761                 {
762                         const deInt64 ox = samplePos[sampleNdx*2 + 0];
763                         const deInt64 oy = samplePos[sampleNdx*2 + 1];
764
765                         for (int fragNdx = 0; fragNdx < 4; fragNdx++)
766                         {
767                                 e01[sampleNdx][fragNdx] = evaluateEdge(m_edge01, sx[fragNdx] + ox, sy[fragNdx] + oy);
768                                 e12[sampleNdx][fragNdx] = evaluateEdge(m_edge12, sx[fragNdx] + ox, sy[fragNdx] + oy);
769                                 e20[sampleNdx][fragNdx] = evaluateEdge(m_edge20, sx[fragNdx] + ox, sy[fragNdx] + oy);
770                         }
771                 }
772
773                 // Compute coverage mask
774                 for (int sampleNdx = 0; sampleNdx < NumSamples; sampleNdx++)
775                 {
776                         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]));
777                         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]));
778                         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]));
779                         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]));
780                 }
781
782                 // Advance to next location
783                 m_curPos.x() += 2;
784                 if (m_curPos.x() > m_bboxMax.x())
785                 {
786                         m_curPos.y() += 2;
787                         m_curPos.x()  = m_bboxMin.x();
788                 }
789
790                 if (coverage == 0)
791                         continue; // Discard.
792
793                 // Compute depth values.
794                 if (depthValues)
795                 {
796                         for (int sampleNdx = 0; sampleNdx < NumSamples; sampleNdx++)
797                         {
798                                 // Floating-point edge values at sample coordinates.
799                                 const tcu::Vec4&        e01f    = e01[sampleNdx].asFloat();
800                                 const tcu::Vec4&        e12f    = e12[sampleNdx].asFloat();
801                                 const tcu::Vec4&        e20f    = e20[sampleNdx].asFloat();
802
803                                 const tcu::Vec4         edgeSum = e01f + e12f + e20f;
804                                 const tcu::Vec4         z0              = e12f / edgeSum;
805                                 const tcu::Vec4         z1              = e20f / edgeSum;
806
807                                 depthValues[(packetNdx*4+0)*NumSamples + sampleNdx] = z0[0]*za + z1[0]*zb + zc;
808                                 depthValues[(packetNdx*4+1)*NumSamples + sampleNdx] = z0[1]*za + z1[1]*zb + zc;
809                                 depthValues[(packetNdx*4+2)*NumSamples + sampleNdx] = z0[2]*za + z1[2]*zb + zc;
810                                 depthValues[(packetNdx*4+3)*NumSamples + sampleNdx] = z0[3]*za + z1[3]*zb + zc;
811                         }
812                 }
813
814                 // Compute barycentrics and write out fragment packet
815                 {
816                         FragmentPacket& packet = fragmentPackets[packetNdx];
817
818                         // Floating-point edge values at pixel center.
819                         tcu::Vec4                       e01f;
820                         tcu::Vec4                       e12f;
821                         tcu::Vec4                       e20f;
822
823                         for (int i = 0; i < 4; i++)
824                         {
825                                 e01f[i] = float(evaluateEdge(m_edge01, sx[i] + halfPixel, sy[i] + halfPixel));
826                                 e12f[i] = float(evaluateEdge(m_edge12, sx[i] + halfPixel, sy[i] + halfPixel));
827                                 e20f[i] = float(evaluateEdge(m_edge20, sx[i] + halfPixel, sy[i] + halfPixel));
828                         }
829
830                         // Barycentrics & scale.
831                         const tcu::Vec4         b0              = e12f * m_v0.w();
832                         const tcu::Vec4         b1              = e20f * m_v1.w();
833                         const tcu::Vec4         b2              = e01f * m_v2.w();
834                         const tcu::Vec4         bSum    = b0 + b1 + b2;
835
836                         packet.position                 = tcu::IVec2(x0, y0);
837                         packet.coverage                 = coverage;
838                         packet.barycentric[0]   = b0 / bSum;
839                         packet.barycentric[1]   = b1 / bSum;
840                         packet.barycentric[2]   = 1.0f - packet.barycentric[0] - packet.barycentric[1];
841
842                         packetNdx += 1;
843                 }
844         }
845
846         DE_ASSERT(packetNdx <= maxFragmentPackets);
847         numPacketsRasterized = packetNdx;
848 }
849
850 void TriangleRasterizer::rasterize (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
851 {
852         DE_ASSERT(maxFragmentPackets > 0);
853
854         switch (m_numSamples)
855         {
856                 case 1:         rasterizeSingleSample           (fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);       break;
857                 case 2:         rasterizeMultiSample<2>         (fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);       break;
858                 case 4:         rasterizeMultiSample<4>         (fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);       break;
859                 case 8:         rasterizeMultiSample<8>         (fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);       break;
860                 case 16:        rasterizeMultiSample<16>        (fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);       break;
861                 default:
862                         DE_ASSERT(DE_FALSE);
863         }
864 }
865
866 SingleSampleLineRasterizer::SingleSampleLineRasterizer (const tcu::IVec4& viewport)
867         : m_viewport            (viewport)
868         , m_curRowFragment      (0)
869         , m_lineWidth           (0.0f)
870 {
871 }
872
873 SingleSampleLineRasterizer::~SingleSampleLineRasterizer (void)
874 {
875 }
876
877 void SingleSampleLineRasterizer::init (const tcu::Vec4& v0, const tcu::Vec4& v1, float lineWidth)
878 {
879         const bool                                              isXMajor                = de::abs((v1 - v0).x()) >= de::abs((v1 - v0).y());
880
881         // Bounding box \note: with wide lines, the line is actually moved as in the spec
882         const deInt32                                   lineWidthPixels = (lineWidth > 1.0f) ? (deInt32)floor(lineWidth + 0.5f) : 1;
883
884         const tcu::Vector<deInt64,2>    widthOffset             = (isXMajor ? tcu::Vector<deInt64,2>(0, -1) : tcu::Vector<deInt64,2>(-1, 0)) * (toSubpixelCoord(lineWidthPixels - 1) / 2);
885
886         const deInt64                                   x0                              = toSubpixelCoord(v0.x()) + widthOffset.x();
887         const deInt64                                   y0                              = toSubpixelCoord(v0.y()) + widthOffset.y();
888         const deInt64                                   x1                              = toSubpixelCoord(v1.x()) + widthOffset.x();
889         const deInt64                                   y1                              = toSubpixelCoord(v1.y()) + widthOffset.y();
890
891         // line endpoints might be perturbed, add some margin
892         const deInt64                                   xMin                    = de::min(x0, x1) - toSubpixelCoord(1);
893         const deInt64                                   xMax                    = de::max(x0, x1) + toSubpixelCoord(1);
894         const deInt64                                   yMin                    = de::min(y0, y1) - toSubpixelCoord(1);
895         const deInt64                                   yMax                    = de::max(y0, y1) + toSubpixelCoord(1);
896
897         // Remove invisible area
898
899         if (isXMajor)
900         {
901                 // clamp to viewport in major direction
902                 m_bboxMin.x() = de::clamp(floorSubpixelToPixelCoord(xMin, true), m_viewport.x(), m_viewport.x() + m_viewport.z() - 1);
903                 m_bboxMax.x() = de::clamp(ceilSubpixelToPixelCoord (xMax, true), m_viewport.x(), m_viewport.x() + m_viewport.z() - 1);
904
905                 // clamp to padded viewport in minor direction (wide lines might bleed over viewport in minor direction)
906                 m_bboxMin.y() = de::clamp(floorSubpixelToPixelCoord(yMin, true), m_viewport.y() - lineWidthPixels, m_viewport.y() + m_viewport.w() - 1);
907                 m_bboxMax.y() = de::clamp(ceilSubpixelToPixelCoord (yMax, true), m_viewport.y() - lineWidthPixels, m_viewport.y() + m_viewport.w() - 1);
908         }
909         else
910         {
911                 // clamp to viewport in major direction
912                 m_bboxMin.y() = de::clamp(floorSubpixelToPixelCoord(yMin, true), m_viewport.y(), m_viewport.y() + m_viewport.w() - 1);
913                 m_bboxMax.y() = de::clamp(ceilSubpixelToPixelCoord (yMax, true), m_viewport.y(), m_viewport.y() + m_viewport.w() - 1);
914
915                 // clamp to padded viewport in minor direction (wide lines might bleed over viewport in minor direction)
916                 m_bboxMin.x() = de::clamp(floorSubpixelToPixelCoord(xMin, true), m_viewport.x() - lineWidthPixels, m_viewport.x() + m_viewport.z() - 1);
917                 m_bboxMax.x() = de::clamp(ceilSubpixelToPixelCoord (xMax, true), m_viewport.x() - lineWidthPixels, m_viewport.x() + m_viewport.z() - 1);
918         }
919
920         m_lineWidth = lineWidth;
921
922         m_v0 = v0;
923         m_v1 = v1;
924
925         m_curPos = m_bboxMin;
926         m_curRowFragment = 0;
927 }
928
929 void SingleSampleLineRasterizer::rasterize (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
930 {
931         DE_ASSERT(maxFragmentPackets > 0);
932
933         const deInt64                                                           halfPixel                       = 1ll << (RASTERIZER_SUBPIXEL_BITS-1);
934         const deInt32                                                           lineWidth                       = (m_lineWidth > 1.0f) ? deFloorFloatToInt32(m_lineWidth + 0.5f) : 1;
935         const bool                                                                      isXMajor                        = de::abs((m_v1 - m_v0).x()) >= de::abs((m_v1 - m_v0).y());
936         const tcu::IVec2                                                        minorDirection          = (isXMajor) ? (tcu::IVec2(0, 1)) : (tcu::IVec2(1, 0));
937         const int                                                                       minViewportLimit        = (isXMajor) ? (m_viewport.y()) : (m_viewport.x());
938         const int                                                                       maxViewportLimit        = (isXMajor) ? (m_viewport.y() + m_viewport.w()) : (m_viewport.x() + m_viewport.z());
939         const tcu::Vector<deInt64,2>                            widthOffset                     = -minorDirection.cast<deInt64>() * (toSubpixelCoord(lineWidth - 1) / 2);
940         const tcu::Vector<deInt64,2>                            pa                                      = LineRasterUtil::toSubpixelVector(m_v0.xy()) + widthOffset;
941         const tcu::Vector<deInt64,2>                            pb                                      = LineRasterUtil::toSubpixelVector(m_v1.xy()) + widthOffset;
942         const LineRasterUtil::SubpixelLineSegment       line                            = LineRasterUtil::SubpixelLineSegment(pa, pb);
943
944         int                                                                                     packetNdx                       = 0;
945
946         while (m_curPos.y() <= m_bboxMax.y() && packetNdx < maxFragmentPackets)
947         {
948                 const tcu::Vector<deInt64,2> diamondPosition = LineRasterUtil::toSubpixelVector(m_curPos) + tcu::Vector<deInt64,2>(halfPixel,halfPixel);
949
950                 // Should current fragment be drawn? == does the segment exit this diamond?
951                 if (LineRasterUtil::doesLineSegmentExitDiamond(line, diamondPosition))
952                 {
953                         const tcu::Vector<deInt64,2>    pr                                      = diamondPosition;
954                         const float                                             t                                       = tcu::dot((pr - pa).asFloat(), (pb - pa).asFloat()) / tcu::lengthSquared(pb.asFloat() - pa.asFloat());
955
956                         // Rasterize on only fragments that are would end up in the viewport (i.e. visible)
957                         const int                                               fragmentLocation        = (isXMajor) ? (m_curPos.y()) : (m_curPos.x());
958                         const int                                               rowFragBegin            = de::max(0, minViewportLimit - fragmentLocation);
959                         const int                                               rowFragEnd                      = de::min(maxViewportLimit - fragmentLocation, lineWidth);
960
961                         // Wide lines require multiple fragments.
962                         for (; rowFragBegin + m_curRowFragment < rowFragEnd; m_curRowFragment++)
963                         {
964                                 const int                       replicationId   = rowFragBegin + m_curRowFragment;
965                                 const tcu::IVec2        fragmentPos             = m_curPos + minorDirection * replicationId;
966
967                                 // We only rasterize visible area
968                                 DE_ASSERT(LineRasterUtil::inViewport(fragmentPos, m_viewport));
969
970                                 // Compute depth values.
971                                 if (depthValues)
972                                 {
973                                         const float za = m_v0.z();
974                                         const float zb = m_v1.z();
975
976                                         depthValues[packetNdx*4+0] = (1 - t) * za + t * zb;
977                                         depthValues[packetNdx*4+1] = 0;
978                                         depthValues[packetNdx*4+2] = 0;
979                                         depthValues[packetNdx*4+3] = 0;
980                                 }
981
982                                 {
983                                         // output this fragment
984                                         // \note In order to make consistent output with multisampled line rasterization, output "barycentric" coordinates
985                                         FragmentPacket& packet = fragmentPackets[packetNdx];
986
987                                         const tcu::Vec4         b0              = tcu::Vec4(1 - t);
988                                         const tcu::Vec4         b1              = tcu::Vec4(t);
989                                         const tcu::Vec4         ooSum   = 1.0f / (b0 + b1);
990
991                                         packet.position                 = fragmentPos;
992                                         packet.coverage                 = getCoverageBit(1, 0, 0, 0);
993                                         packet.barycentric[0]   = b0 * ooSum;
994                                         packet.barycentric[1]   = b1 * ooSum;
995                                         packet.barycentric[2]   = tcu::Vec4(0.0f);
996
997                                         packetNdx += 1;
998                                 }
999
1000                                 if (packetNdx == maxFragmentPackets)
1001                                 {
1002                                         m_curRowFragment++; // don't redraw this fragment again next time
1003                                         numPacketsRasterized = packetNdx;
1004                                         return;
1005                                 }
1006                         }
1007
1008                         m_curRowFragment = 0;
1009                 }
1010
1011                 ++m_curPos.x();
1012                 if (m_curPos.x() > m_bboxMax.x())
1013                 {
1014                         ++m_curPos.y();
1015                         m_curPos.x() = m_bboxMin.x();
1016                 }
1017         }
1018
1019         DE_ASSERT(packetNdx <= maxFragmentPackets);
1020         numPacketsRasterized = packetNdx;
1021 }
1022
1023 MultiSampleLineRasterizer::MultiSampleLineRasterizer (const int numSamples, const tcu::IVec4& viewport)
1024         : m_numSamples                  (numSamples)
1025         , m_triangleRasterizer0 (viewport, m_numSamples, RasterizationState())
1026         , m_triangleRasterizer1 (viewport, m_numSamples, RasterizationState())
1027 {
1028 }
1029
1030 MultiSampleLineRasterizer::~MultiSampleLineRasterizer ()
1031 {
1032 }
1033
1034 void MultiSampleLineRasterizer::init (const tcu::Vec4& v0, const tcu::Vec4& v1, float lineWidth)
1035 {
1036         // allow creation of single sampled rasterizer objects but do not allow using them
1037         DE_ASSERT(m_numSamples > 1);
1038
1039         const tcu::Vec2 lineVec         = tcu::Vec2(tcu::Vec4(v1).xy()) - tcu::Vec2(tcu::Vec4(v0).xy());
1040         const tcu::Vec2 normal2         = tcu::normalize(tcu::Vec2(-lineVec[1], lineVec[0]));
1041         const tcu::Vec4 normal4         = tcu::Vec4(normal2.x(), normal2.y(), 0, 0);
1042         const float offset                      = lineWidth / 2.0f;
1043
1044         const tcu::Vec4 p0 = v0 + normal4 * offset;
1045         const tcu::Vec4 p1 = v0 - normal4 * offset;
1046         const tcu::Vec4 p2 = v1 - normal4 * offset;
1047         const tcu::Vec4 p3 = v1 + normal4 * offset;
1048
1049         // Edge 0 -> 1 is always along the line and edge 1 -> 2 is in 90 degree angle to the line
1050         m_triangleRasterizer0.init(p0, p3, p2);
1051         m_triangleRasterizer1.init(p2, p1, p0);
1052 }
1053
1054 void MultiSampleLineRasterizer::rasterize (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
1055 {
1056         DE_ASSERT(maxFragmentPackets > 0);
1057
1058         m_triangleRasterizer0.rasterize(fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);
1059
1060         // Remove 3rd barycentric value and rebalance. Lines do not have non-zero barycentric at index 2
1061         for (int packNdx = 0; packNdx < numPacketsRasterized; ++packNdx)
1062         for (int fragNdx = 0; fragNdx < 4; fragNdx++)
1063         {
1064                 float removedValue = fragmentPackets[packNdx].barycentric[2][fragNdx];
1065                 fragmentPackets[packNdx].barycentric[2][fragNdx] = 0.0f;
1066                 fragmentPackets[packNdx].barycentric[1][fragNdx] += removedValue;
1067         }
1068
1069         // rasterizer 0 filled the whole buffer?
1070         if (numPacketsRasterized == maxFragmentPackets)
1071                 return;
1072
1073         {
1074                 FragmentPacket* const nextFragmentPackets       = fragmentPackets + numPacketsRasterized;
1075                 float* nextDepthValues                                          = (depthValues) ? (depthValues+4*numPacketsRasterized*m_numSamples) : (DE_NULL);
1076                 int numPacketsRasterized2                                       = 0;
1077
1078                 m_triangleRasterizer1.rasterize(nextFragmentPackets, nextDepthValues, maxFragmentPackets - numPacketsRasterized, numPacketsRasterized2);
1079
1080                 numPacketsRasterized += numPacketsRasterized2;
1081
1082                 // Fix swapped barycentrics in the second triangle
1083                 for (int packNdx = 0; packNdx < numPacketsRasterized2; ++packNdx)
1084                 for (int fragNdx = 0; fragNdx < 4; fragNdx++)
1085                 {
1086                         float removedValue = nextFragmentPackets[packNdx].barycentric[2][fragNdx];
1087                         nextFragmentPackets[packNdx].barycentric[2][fragNdx] = 0.0f;
1088                         nextFragmentPackets[packNdx].barycentric[1][fragNdx] += removedValue;
1089
1090                         // edge has reversed direction
1091                         std::swap(nextFragmentPackets[packNdx].barycentric[0][fragNdx], nextFragmentPackets[packNdx].barycentric[1][fragNdx]);
1092                 }
1093         }
1094 }
1095
1096 LineExitDiamondGenerator::LineExitDiamondGenerator (void)
1097 {
1098 }
1099
1100 LineExitDiamondGenerator::~LineExitDiamondGenerator (void)
1101 {
1102 }
1103
1104 void LineExitDiamondGenerator::init (const tcu::Vec4& v0, const tcu::Vec4& v1)
1105 {
1106         const deInt64                                   x0                              = toSubpixelCoord(v0.x());
1107         const deInt64                                   y0                              = toSubpixelCoord(v0.y());
1108         const deInt64                                   x1                              = toSubpixelCoord(v1.x());
1109         const deInt64                                   y1                              = toSubpixelCoord(v1.y());
1110
1111         // line endpoints might be perturbed, add some margin
1112         const deInt64                                   xMin                    = de::min(x0, x1) - toSubpixelCoord(1);
1113         const deInt64                                   xMax                    = de::max(x0, x1) + toSubpixelCoord(1);
1114         const deInt64                                   yMin                    = de::min(y0, y1) - toSubpixelCoord(1);
1115         const deInt64                                   yMax                    = de::max(y0, y1) + toSubpixelCoord(1);
1116
1117         m_bboxMin.x() = floorSubpixelToPixelCoord(xMin, true);
1118         m_bboxMin.y() = floorSubpixelToPixelCoord(yMin, true);
1119         m_bboxMax.x() = ceilSubpixelToPixelCoord (xMax, true);
1120         m_bboxMax.y() = ceilSubpixelToPixelCoord (yMax, true);
1121
1122         m_v0 = v0;
1123         m_v1 = v1;
1124
1125         m_curPos = m_bboxMin;
1126 }
1127
1128 void LineExitDiamondGenerator::rasterize (LineExitDiamond* const lineDiamonds, const int maxDiamonds, int& numWritten)
1129 {
1130         DE_ASSERT(maxDiamonds > 0);
1131
1132         const deInt64                                                           halfPixel                       = 1ll << (RASTERIZER_SUBPIXEL_BITS-1);
1133         const tcu::Vector<deInt64,2>                            pa                                      = LineRasterUtil::toSubpixelVector(m_v0.xy());
1134         const tcu::Vector<deInt64,2>                            pb                                      = LineRasterUtil::toSubpixelVector(m_v1.xy());
1135         const LineRasterUtil::SubpixelLineSegment       line                            = LineRasterUtil::SubpixelLineSegment(pa, pb);
1136
1137         int                                                                                     diamondNdx                      = 0;
1138
1139         while (m_curPos.y() <= m_bboxMax.y() && diamondNdx < maxDiamonds)
1140         {
1141                 const tcu::Vector<deInt64,2> diamondPosition = LineRasterUtil::toSubpixelVector(m_curPos) + tcu::Vector<deInt64,2>(halfPixel,halfPixel);
1142
1143                 if (LineRasterUtil::doesLineSegmentExitDiamond(line, diamondPosition))
1144                 {
1145                         LineExitDiamond& packet = lineDiamonds[diamondNdx];
1146                         packet.position = m_curPos;
1147                         ++diamondNdx;
1148                 }
1149
1150                 ++m_curPos.x();
1151                 if (m_curPos.x() > m_bboxMax.x())
1152                 {
1153                         ++m_curPos.y();
1154                         m_curPos.x() = m_bboxMin.x();
1155                 }
1156         }
1157
1158         DE_ASSERT(diamondNdx <= maxDiamonds);
1159         numWritten = diamondNdx;
1160 }
1161
1162 } // rr