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, int bits)
  32 {
  33         return (deInt64)(v * (float)(1 << bits) + (v < 0.f ? -0.5f : 0.5f));
  34 }
  35
  36 inline deInt64 toSubpixelCoord (deInt32 v, int bits)
  37 {
  38         return v << bits;
  39 }
  40
  41 inline deInt32 ceilSubpixelToPixelCoord (deInt64 coord, int bits, bool fillEdge)
  42 {
  43         if (coord >= 0)
  44                 return (deInt32)((coord + ((1ll << bits) - (fillEdge ? 0 : 1))) >> bits);
  45         else
  46                 return (deInt32)((coord + (fillEdge ? 1 : 0)) >> bits);
  47 }
  48
  49 inline deInt32 floorSubpixelToPixelCoord (deInt64 coord, int bits, bool fillEdge)
  50 {
  51         if (coord >= 0)
  52                 return (deInt32)((coord - (fillEdge ? 1 : 0)) >> bits);
  53         else
  54                 return (deInt32)((coord - ((1ll << bits) - (fillEdge ? 0 : 1))) >> 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, int bits)
 122 {
 123         return tcu::Vector<deInt64,2>(toSubpixelCoord(v.x(), bits), toSubpixelCoord(v.y(), bits));
 124 }
 125
 126 static tcu::Vector<deInt64,2> toSubpixelVector (const tcu::IVec2& v, int bits)
 127 {
 128         return tcu::Vector<deInt64,2>(toSubpixelCoord(v.x(), bits), toSubpixelCoord(v.y(), bits));
 129 }
 130
 131 #if defined(DE_DEBUG)
 132 static bool isTheCenterOfTheFragment (const tcu::Vector<deInt64,2>& a, int bits)
 133 {
 134         const deUint64 pixelSize = 1ll << bits;
 135         const deUint64 halfPixel = 1ll << (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, int bits)
 235 {
 236         DE_ASSERT(isTheCenterOfTheFragment(diamondCenter, bits));
 237
 238         // Diamond Center is at diamondCenter in subpixel coords
 239
 240         const deInt64 halfPixel = 1ll << (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, const int subpixelBits)
 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_subpixelBits                        (subpixelBits)
 455         , m_face                                        (FACETYPE_LAST)
 456         , m_viewportOrientation         (state.viewportOrientation)
 457 {
 458 }
 459
 460 /*--------------------------------------------------------------------*//*!
 461  * \brief Initialize triangle rasterization
 462  * \param v0 Screen-space coordinates (x, y, z) and 1/w for vertex 0.
 463  * \param v1 Screen-space coordinates (x, y, z) and 1/w for vertex 1.
 464  * \param v2 Screen-space coordinates (x, y, z) and 1/w for vertex 2.
 465  *//*--------------------------------------------------------------------*/
 466 void TriangleRasterizer::init (const tcu::Vec4& v0, const tcu::Vec4& v1, const tcu::Vec4& v2)
 467 {
 468         m_v0 = v0;
 469         m_v1 = v1;
 470         m_v2 = v2;
 471
 472         // Positions in fixed-point coordinates.
 473         const deInt64   x0              = toSubpixelCoord(v0.x(), m_subpixelBits);
 474         const deInt64   y0              = toSubpixelCoord(v0.y(), m_subpixelBits);
 475         const deInt64   x1              = toSubpixelCoord(v1.x(), m_subpixelBits);
 476         const deInt64   y1              = toSubpixelCoord(v1.y(), m_subpixelBits);
 477         const deInt64   x2              = toSubpixelCoord(v2.x(), m_subpixelBits);
 478         const deInt64   y2              = toSubpixelCoord(v2.y(), m_subpixelBits);
 479
 480         // Initialize edge functions.
 481         if (m_winding == WINDING_CCW)
 482         {
 483                 initEdgeCCW(m_edge01, m_horizontalFill, m_verticalFill, x0, y0, x1, y1);
 484                 initEdgeCCW(m_edge12, m_horizontalFill, m_verticalFill, x1, y1, x2, y2);
 485                 initEdgeCCW(m_edge20, m_horizontalFill, m_verticalFill, x2, y2, x0, y0);
 486         }
 487         else
 488         {
 489                 // Reverse edges
 490                 initEdgeCCW(m_edge01, m_horizontalFill, m_verticalFill, x1, y1, x0, y0);
 491                 initEdgeCCW(m_edge12, m_horizontalFill, m_verticalFill, x2, y2, x1, y1);
 492                 initEdgeCCW(m_edge20, m_horizontalFill, m_verticalFill, x0, y0, x2, y2);
 493         }
 494
 495         // Determine face.
 496         const deInt64   s                               = evaluateEdge(m_edge01, x2, y2);
 497         const bool              positiveArea    = (m_winding == WINDING_CCW) ? (s > 0) : (s < 0);
 498
 499         if (m_viewportOrientation == VIEWPORTORIENTATION_UPPER_LEFT)
 500                 m_face = positiveArea ? FACETYPE_BACK : FACETYPE_FRONT;
 501         else
 502                 m_face = positiveArea ? FACETYPE_FRONT : FACETYPE_BACK;
 503
 504         if (!positiveArea)
 505         {
 506                 // Reverse edges so that we can use CCW area tests & interpolation
 507                 reverseEdge(m_edge01);
 508                 reverseEdge(m_edge12);
 509                 reverseEdge(m_edge20);
 510         }
 511
 512         // Bounding box
 513         const deInt64   xMin    = de::min(de::min(x0, x1), x2);
 514         const deInt64   xMax    = de::max(de::max(x0, x1), x2);
 515         const deInt64   yMin    = de::min(de::min(y0, y1), y2);
 516         const deInt64   yMax    = de::max(de::max(y0, y1), y2);
 517
 518         m_bboxMin.x() = floorSubpixelToPixelCoord       (xMin, m_subpixelBits, m_horizontalFill == FILL_LEFT);
 519         m_bboxMin.y() = floorSubpixelToPixelCoord       (yMin, m_subpixelBits, m_verticalFill   == FILL_BOTTOM);
 520         m_bboxMax.x() = ceilSubpixelToPixelCoord        (xMax, m_subpixelBits, m_horizontalFill == FILL_RIGHT);
 521         m_bboxMax.y() = ceilSubpixelToPixelCoord        (yMax, m_subpixelBits, m_verticalFill   == FILL_TOP);
 522
 523         // Clamp to viewport
 524         const int               wX0             = m_viewport.x();
 525         const int               wY0             = m_viewport.y();
 526         const int               wX1             = wX0 + m_viewport.z() - 1;
 527         const int               wY1             = wY0 + m_viewport.w() -1;
 528
 529         m_bboxMin.x() = de::clamp(m_bboxMin.x(), wX0, wX1);
 530         m_bboxMin.y() = de::clamp(m_bboxMin.y(), wY0, wY1);
 531         m_bboxMax.x() = de::clamp(m_bboxMax.x(), wX0, wX1);
 532         m_bboxMax.y() = de::clamp(m_bboxMax.y(), wY0, wY1);
 533
 534         m_curPos = m_bboxMin;
 535 }
 536
 537 void TriangleRasterizer::rasterizeSingleSample (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
 538 {
 539         DE_ASSERT(maxFragmentPackets > 0);
 540
 541         const deUint64  halfPixel       = 1ll << (m_subpixelBits - 1);
 542         int                             packetNdx       = 0;
 543
 544         // For depth interpolation; given barycentrics A, B, C = (1 - A - B)
 545         // we can reformulate the usual z = z0*A + z1*B + z2*C into more
 546         // stable equation z = A*(z0 - z2) + B*(z1 - z2) + z2.
 547         const float             za                      = m_v0.z()-m_v2.z();
 548         const float             zb                      = m_v1.z()-m_v2.z();
 549         const float             zc                      = m_v2.z();
 550
 551         while (m_curPos.y() <= m_bboxMax.y() && packetNdx < maxFragmentPackets)
 552         {
 553                 const int               x0              = m_curPos.x();
 554                 const int               y0              = m_curPos.y();
 555
 556                 // Subpixel coords
 557                 const deInt64   sx0             = toSubpixelCoord(x0,   m_subpixelBits) + halfPixel;
 558                 const deInt64   sx1             = toSubpixelCoord(x0+1, m_subpixelBits) + halfPixel;
 559                 const deInt64   sy0             = toSubpixelCoord(y0,   m_subpixelBits) + halfPixel;
 560                 const deInt64   sy1             = toSubpixelCoord(y0+1, m_subpixelBits) + halfPixel;
 561
 562                 const deInt64   sx[4]   = { sx0, sx1, sx0, sx1 };
 563                 const deInt64   sy[4]   = { sy0, sy0, sy1, sy1 };
 564
 565                 // Viewport test
 566                 const bool              outX1   = x0+1 == m_viewport.x()+m_viewport.z();
 567                 const bool              outY1   = y0+1 == m_viewport.y()+m_viewport.w();
 568
 569                 DE_ASSERT(x0 < m_viewport.x()+m_viewport.z());
 570                 DE_ASSERT(y0 < m_viewport.y()+m_viewport.w());
 571
 572                 // Edge values
 573                 tcu::Vector<deInt64, 4> e01;
 574                 tcu::Vector<deInt64, 4> e12;
 575                 tcu::Vector<deInt64, 4> e20;
 576
 577                 // Coverage
 578                 deUint64                coverage        = 0;
 579
 580                 // Evaluate edge values
 581                 for (int i = 0; i < 4; i++)
 582                 {
 583                         e01[i] = evaluateEdge(m_edge01, sx[i], sy[i]);
 584                         e12[i] = evaluateEdge(m_edge12, sx[i], sy[i]);
 585                         e20[i] = evaluateEdge(m_edge20, sx[i], sy[i]);
 586                 }
 587
 588                 // Compute coverage mask
 589                 coverage = setCoverageValue(coverage, 1, 0, 0, 0,                                               isInsideCCW(m_edge01, e01[0]) && isInsideCCW(m_edge12, e12[0]) && isInsideCCW(m_edge20, e20[0]));
 590                 coverage = setCoverageValue(coverage, 1, 1, 0, 0, !outX1 &&                             isInsideCCW(m_edge01, e01[1]) && isInsideCCW(m_edge12, e12[1]) && isInsideCCW(m_edge20, e20[1]));
 591                 coverage = setCoverageValue(coverage, 1, 0, 1, 0, !outY1 &&                             isInsideCCW(m_edge01, e01[2]) && isInsideCCW(m_edge12, e12[2]) && isInsideCCW(m_edge20, e20[2]));
 592                 coverage = setCoverageValue(coverage, 1, 1, 1, 0, !outX1 && !outY1 &&   isInsideCCW(m_edge01, e01[3]) && isInsideCCW(m_edge12, e12[3]) && isInsideCCW(m_edge20, e20[3]));
 593
 594                 // Advance to next location
 595                 m_curPos.x() += 2;
 596                 if (m_curPos.x() > m_bboxMax.x())
 597                 {
 598                         m_curPos.y() += 2;
 599                         m_curPos.x()  = m_bboxMin.x();
 600                 }
 601
 602                 if (coverage == 0)
 603                         continue; // Discard.
 604
 605                 // Floating-point edge values for barycentrics etc.
 606                 const tcu::Vec4         e01f    = e01.asFloat();
 607                 const tcu::Vec4         e12f    = e12.asFloat();
 608                 const tcu::Vec4         e20f    = e20.asFloat();
 609
 610                 // Compute depth values.
 611                 if (depthValues)
 612                 {
 613                         const tcu::Vec4         edgeSum = e01f + e12f + e20f;
 614                         const tcu::Vec4         z0              = e12f / edgeSum;
 615                         const tcu::Vec4         z1              = e20f / edgeSum;
 616
 617                         depthValues[packetNdx*4+0] = z0[0]*za + z1[0]*zb + zc;
 618                         depthValues[packetNdx*4+1] = z0[1]*za + z1[1]*zb + zc;
 619                         depthValues[packetNdx*4+2] = z0[2]*za + z1[2]*zb + zc;
 620                         depthValues[packetNdx*4+3] = z0[3]*za + z1[3]*zb + zc;
 621                 }
 622
 623                 // Compute barycentrics and write out fragment packet
 624                 {
 625                         FragmentPacket& packet = fragmentPackets[packetNdx];
 626
 627                         const tcu::Vec4         b0              = e12f * m_v0.w();
 628                         const tcu::Vec4         b1              = e20f * m_v1.w();
 629                         const tcu::Vec4         b2              = e01f * m_v2.w();
 630                         const tcu::Vec4         bSum    = b0 + b1 + b2;
 631
 632                         packet.position                 = tcu::IVec2(x0, y0);
 633                         packet.coverage                 = coverage;
 634                         packet.barycentric[0]   = b0 / bSum;
 635                         packet.barycentric[1]   = b1 / bSum;
 636                         packet.barycentric[2]   = 1.0f - packet.barycentric[0] - packet.barycentric[1];
 637
 638                         packetNdx += 1;
 639                 }
 640         }
 641
 642         DE_ASSERT(packetNdx <= maxFragmentPackets);
 643         numPacketsRasterized = packetNdx;
 644 }
 645
 646 // Sample positions - ordered as (x, y) list.
 647 static const float s_samplePts2[] =
 648 {
 649         0.3f, 0.3f,
 650         0.7f, 0.7f
 651 };
 652
 653 static const float s_samplePts4[] =
 654 {
 655         0.25f, 0.25f,
 656         0.75f, 0.25f,
 657         0.25f, 0.75f,
 658         0.75f, 0.75f
 659 };
 660
 661 static const float s_samplePts8[] =
 662 {
 663         7.f  / 16.f,  9.f / 16.f,
 664         9.f  / 16.f, 13.f / 16.f,
 665         11.f / 16.f,  3.f / 16.f,
 666         13.f / 16.f, 11.f / 16.f,
 667         1.f  / 16.f,  7.f / 16.f,
 668         5.f  / 16.f,  1.f / 16.f,
 669         15.f / 16.f,  5.f / 16.f,
 670         3.f  / 16.f, 15.f / 16.f
 671 };
 672
 673 static const float s_samplePts16[] =
 674 {
 675         1.f / 8.f, 1.f / 8.f,
 676         3.f / 8.f, 1.f / 8.f,
 677         5.f / 8.f, 1.f / 8.f,
 678         7.f / 8.f, 1.f / 8.f,
 679         1.f / 8.f, 3.f / 8.f,
 680         3.f / 8.f, 3.f / 8.f,
 681         5.f / 8.f, 3.f / 8.f,
 682         7.f / 8.f, 3.f / 8.f,
 683         1.f / 8.f, 5.f / 8.f,
 684         3.f / 8.f, 5.f / 8.f,
 685         5.f / 8.f, 5.f / 8.f,
 686         7.f / 8.f, 5.f / 8.f,
 687         1.f / 8.f, 7.f / 8.f,
 688         3.f / 8.f, 7.f / 8.f,
 689         5.f / 8.f, 7.f / 8.f,
 690         7.f / 8.f, 7.f / 8.f
 691 };
 692
 693 template<int NumSamples>
 694 void TriangleRasterizer::rasterizeMultiSample (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
 695 {
 696         DE_ASSERT(maxFragmentPackets > 0);
 697
 698         // Big enough to hold maximum multisample count
 699         deInt64                 samplePos[DE_LENGTH_OF_ARRAY(s_samplePts16)];
 700         const float *   samplePts       = DE_NULL;
 701         const deUint64  halfPixel       = 1ll << (m_subpixelBits - 1);
 702         int                             packetNdx       = 0;
 703
 704         // For depth interpolation, see rasterizeSingleSample
 705         const float             za                      = m_v0.z()-m_v2.z();
 706         const float             zb                      = m_v1.z()-m_v2.z();
 707         const float             zc                      = m_v2.z();
 708
 709         switch (NumSamples)
 710         {
 711                 case 2:         samplePts = s_samplePts2;       break;
 712                 case 4:         samplePts = s_samplePts4;       break;
 713                 case 8:         samplePts = s_samplePts8;       break;
 714                 case 16:        samplePts = s_samplePts16;      break;
 715                 default:
 716                         DE_ASSERT(false);
 717         }
 718
 719         for (int c = 0; c < NumSamples * 2; ++c)
 720                 samplePos[c] = toSubpixelCoord(samplePts[c], m_subpixelBits);
 721
 722         while (m_curPos.y() <= m_bboxMax.y() && packetNdx < maxFragmentPackets)
 723         {
 724                 const int               x0              = m_curPos.x();
 725                 const int               y0              = m_curPos.y();
 726
 727                 // Base subpixel coords
 728                 const deInt64   sx0             = toSubpixelCoord(x0,   m_subpixelBits);
 729                 const deInt64   sx1             = toSubpixelCoord(x0+1, m_subpixelBits);
 730                 const deInt64   sy0             = toSubpixelCoord(y0,   m_subpixelBits);
 731                 const deInt64   sy1             = toSubpixelCoord(y0+1, m_subpixelBits);
 732
 733                 const deInt64   sx[4]   = { sx0, sx1, sx0, sx1 };
 734                 const deInt64   sy[4]   = { sy0, sy0, sy1, sy1 };
 735
 736                 // Viewport test
 737                 const bool              outX1   = x0+1 == m_viewport.x()+m_viewport.z();
 738                 const bool              outY1   = y0+1 == m_viewport.y()+m_viewport.w();
 739
 740                 DE_ASSERT(x0 < m_viewport.x()+m_viewport.z());
 741                 DE_ASSERT(y0 < m_viewport.y()+m_viewport.w());
 742
 743                 // Edge values
 744                 tcu::Vector<deInt64, 4> e01[NumSamples];
 745                 tcu::Vector<deInt64, 4> e12[NumSamples];
 746                 tcu::Vector<deInt64, 4> e20[NumSamples];
 747
 748                 // Coverage
 749                 deUint64                coverage        = 0;
 750
 751                 // Evaluate edge values at sample positions
 752                 for (int sampleNdx = 0; sampleNdx < NumSamples; sampleNdx++)
 753                 {
 754                         const deInt64 ox = samplePos[sampleNdx*2 + 0];
 755                         const deInt64 oy = samplePos[sampleNdx*2 + 1];
 756
 757                         for (int fragNdx = 0; fragNdx < 4; fragNdx++)
 758                         {
 759                                 e01[sampleNdx][fragNdx] = evaluateEdge(m_edge01, sx[fragNdx] + ox, sy[fragNdx] + oy);
 760                                 e12[sampleNdx][fragNdx] = evaluateEdge(m_edge12, sx[fragNdx] + ox, sy[fragNdx] + oy);
 761                                 e20[sampleNdx][fragNdx] = evaluateEdge(m_edge20, sx[fragNdx] + ox, sy[fragNdx] + oy);
 762                         }
 763                 }
 764
 765                 // Compute coverage mask
 766                 for (int sampleNdx = 0; sampleNdx < NumSamples; sampleNdx++)
 767                 {
 768                         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]));
 769                         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]));
 770                         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]));
 771                         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]));
 772                 }
 773
 774                 // Advance to next location
 775                 m_curPos.x() += 2;
 776                 if (m_curPos.x() > m_bboxMax.x())
 777                 {
 778                         m_curPos.y() += 2;
 779                         m_curPos.x()  = m_bboxMin.x();
 780                 }
 781
 782                 if (coverage == 0)
 783                         continue; // Discard.
 784
 785                 // Compute depth values.
 786                 if (depthValues)
 787                 {
 788                         for (int sampleNdx = 0; sampleNdx < NumSamples; sampleNdx++)
 789                         {
 790                                 // Floating-point edge values at sample coordinates.
 791                                 const tcu::Vec4&        e01f    = e01[sampleNdx].asFloat();
 792                                 const tcu::Vec4&        e12f    = e12[sampleNdx].asFloat();
 793                                 const tcu::Vec4&        e20f    = e20[sampleNdx].asFloat();
 794
 795                                 const tcu::Vec4         edgeSum = e01f + e12f + e20f;
 796                                 const tcu::Vec4         z0              = e12f / edgeSum;
 797                                 const tcu::Vec4         z1              = e20f / edgeSum;
 798
 799                                 depthValues[(packetNdx*4+0)*NumSamples + sampleNdx] = z0[0]*za + z1[0]*zb + zc;
 800                                 depthValues[(packetNdx*4+1)*NumSamples + sampleNdx] = z0[1]*za + z1[1]*zb + zc;
 801                                 depthValues[(packetNdx*4+2)*NumSamples + sampleNdx] = z0[2]*za + z1[2]*zb + zc;
 802                                 depthValues[(packetNdx*4+3)*NumSamples + sampleNdx] = z0[3]*za + z1[3]*zb + zc;
 803                         }
 804                 }
 805
 806                 // Compute barycentrics and write out fragment packet
 807                 {
 808                         FragmentPacket& packet = fragmentPackets[packetNdx];
 809
 810                         // Floating-point edge values at pixel center.
 811                         tcu::Vec4                       e01f;
 812                         tcu::Vec4                       e12f;
 813                         tcu::Vec4                       e20f;
 814
 815                         for (int i = 0; i < 4; i++)
 816                         {
 817                                 e01f[i] = float(evaluateEdge(m_edge01, sx[i] + halfPixel, sy[i] + halfPixel));
 818                                 e12f[i] = float(evaluateEdge(m_edge12, sx[i] + halfPixel, sy[i] + halfPixel));
 819                                 e20f[i] = float(evaluateEdge(m_edge20, sx[i] + halfPixel, sy[i] + halfPixel));
 820                         }
 821
 822                         // Barycentrics & scale.
 823                         const tcu::Vec4         b0              = e12f * m_v0.w();
 824                         const tcu::Vec4         b1              = e20f * m_v1.w();
 825                         const tcu::Vec4         b2              = e01f * m_v2.w();
 826                         const tcu::Vec4         bSum    = b0 + b1 + b2;
 827
 828                         packet.position                 = tcu::IVec2(x0, y0);
 829                         packet.coverage                 = coverage;
 830                         packet.barycentric[0]   = b0 / bSum;
 831                         packet.barycentric[1]   = b1 / bSum;
 832                         packet.barycentric[2]   = 1.0f - packet.barycentric[0] - packet.barycentric[1];
 833
 834                         packetNdx += 1;
 835                 }
 836         }
 837
 838         DE_ASSERT(packetNdx <= maxFragmentPackets);
 839         numPacketsRasterized = packetNdx;
 840 }
 841
 842 void TriangleRasterizer::rasterize (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
 843 {
 844         DE_ASSERT(maxFragmentPackets > 0);
 845
 846         switch (m_numSamples)
 847         {
 848                 case 1:         rasterizeSingleSample           (fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);       break;
 849                 case 2:         rasterizeMultiSample<2>         (fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);       break;
 850                 case 4:         rasterizeMultiSample<4>         (fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);       break;
 851                 case 8:         rasterizeMultiSample<8>         (fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);       break;
 852                 case 16:        rasterizeMultiSample<16>        (fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);       break;
 853                 default:
 854                         DE_ASSERT(DE_FALSE);
 855         }
 856 }
 857
 858 SingleSampleLineRasterizer::SingleSampleLineRasterizer (const tcu::IVec4& viewport, const int subpixelBits)
 859         : m_viewport            (viewport)
 860         , m_subpixelBits        (subpixelBits)
 861         , m_curRowFragment      (0)
 862         , m_lineWidth           (0.0f)
 863         , m_stippleCounter  (0)
 864 {
 865 }
 866
 867 SingleSampleLineRasterizer::~SingleSampleLineRasterizer (void)
 868 {
 869 }
 870
 871 void SingleSampleLineRasterizer::init (const tcu::Vec4& v0, const tcu::Vec4& v1, float lineWidth, deUint32 stippleFactor, deUint16 stipplePattern)
 872 {
 873         const bool                                              isXMajor                = de::abs((v1 - v0).x()) >= de::abs((v1 - v0).y());
 874
 875         // Bounding box \note: with wide lines, the line is actually moved as in the spec
 876         const deInt32                                   lineWidthPixels = (lineWidth > 1.0f) ? (deInt32)floor(lineWidth + 0.5f) : 1;
 877
 878         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);
 879
 880         const deInt64                                   x0                              = toSubpixelCoord(v0.x(), m_subpixelBits) + widthOffset.x();
 881         const deInt64                                   y0                              = toSubpixelCoord(v0.y(), m_subpixelBits) + widthOffset.y();
 882         const deInt64                                   x1                              = toSubpixelCoord(v1.x(), m_subpixelBits) + widthOffset.x();
 883         const deInt64                                   y1                              = toSubpixelCoord(v1.y(), m_subpixelBits) + widthOffset.y();
 884
 885         // line endpoints might be perturbed, add some margin
 886         const deInt64                                   xMin                    = de::min(x0, x1) - toSubpixelCoord(1, m_subpixelBits);
 887         const deInt64                                   xMax                    = de::max(x0, x1) + toSubpixelCoord(1, m_subpixelBits);
 888         const deInt64                                   yMin                    = de::min(y0, y1) - toSubpixelCoord(1, m_subpixelBits);
 889         const deInt64                                   yMax                    = de::max(y0, y1) + toSubpixelCoord(1, m_subpixelBits);
 890
 891         // Remove invisible area
 892
 893         if (isXMajor)
 894         {
 895                 // clamp to viewport in major direction
 896                 m_bboxMin.x() = de::clamp(floorSubpixelToPixelCoord(xMin, m_subpixelBits, true), m_viewport.x(), m_viewport.x() + m_viewport.z() - 1);
 897                 m_bboxMax.x() = de::clamp(ceilSubpixelToPixelCoord (xMax, m_subpixelBits, true), m_viewport.x(), m_viewport.x() + m_viewport.z() - 1);
 898
 899                 // clamp to padded viewport in minor direction (wide lines might bleed over viewport in minor direction)
 900                 m_bboxMin.y() = de::clamp(floorSubpixelToPixelCoord(yMin, m_subpixelBits, true), m_viewport.y() - lineWidthPixels, m_viewport.y() + m_viewport.w() - 1);
 901                 m_bboxMax.y() = de::clamp(ceilSubpixelToPixelCoord (yMax, m_subpixelBits, true), m_viewport.y() - lineWidthPixels, m_viewport.y() + m_viewport.w() - 1);
 902         }
 903         else
 904         {
 905                 // clamp to viewport in major direction
 906                 m_bboxMin.y() = de::clamp(floorSubpixelToPixelCoord(yMin, m_subpixelBits, true), m_viewport.y(), m_viewport.y() + m_viewport.w() - 1);
 907                 m_bboxMax.y() = de::clamp(ceilSubpixelToPixelCoord (yMax, m_subpixelBits, true), m_viewport.y(), m_viewport.y() + m_viewport.w() - 1);
 908
 909                 // clamp to padded viewport in minor direction (wide lines might bleed over viewport in minor direction)
 910                 m_bboxMin.x() = de::clamp(floorSubpixelToPixelCoord(xMin, m_subpixelBits, true), m_viewport.x() - lineWidthPixels, m_viewport.x() + m_viewport.z() - 1);
 911                 m_bboxMax.x() = de::clamp(ceilSubpixelToPixelCoord (xMax, m_subpixelBits, true), m_viewport.x() - lineWidthPixels, m_viewport.x() + m_viewport.z() - 1);
 912         }
 913
 914         m_lineWidth = lineWidth;
 915
 916         m_v0 = v0;
 917         m_v1 = v1;
 918
 919         // Choose direction of traversal and whether to start at bbox min or max. Direction matters
 920     // for the stipple counter.
 921         int                                                                                     xDelta                          = (m_v1 - m_v0).x() > 0 ? 1 : -1;
 922         int                                                                                     yDelta                          = (m_v1 - m_v0).y() > 0 ? 1 : -1;
 923
 924         m_curPos.x() = xDelta > 0 ? m_bboxMin.x() : m_bboxMax.x();
 925         m_curPos.y() = yDelta > 0 ? m_bboxMin.y() : m_bboxMax.y();
 926
 927         m_curRowFragment = 0;
 928         m_stippleFactor = stippleFactor;
 929         m_stipplePattern = stipplePattern;
 930 }
 931
 932 void SingleSampleLineRasterizer::rasterize (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
 933 {
 934         DE_ASSERT(maxFragmentPackets > 0);
 935
 936         const deInt64                                                           halfPixel                       = 1ll << (m_subpixelBits - 1);
 937         const deInt32                                                           lineWidth                       = (m_lineWidth > 1.0f) ? deFloorFloatToInt32(m_lineWidth + 0.5f) : 1;
 938         const bool                                                                      isXMajor                        = de::abs((m_v1 - m_v0).x()) >= de::abs((m_v1 - m_v0).y());
 939         const tcu::IVec2                                                        minorDirection          = (isXMajor) ? (tcu::IVec2(0, 1)) : (tcu::IVec2(1, 0));
 940         const int                                                                       minViewportLimit        = (isXMajor) ? (m_viewport.y()) : (m_viewport.x());
 941         const int                                                                       maxViewportLimit        = (isXMajor) ? (m_viewport.y() + m_viewport.w()) : (m_viewport.x() + m_viewport.z());
 942         const tcu::Vector<deInt64,2>                            widthOffset                     = -minorDirection.cast<deInt64>() * (toSubpixelCoord(lineWidth - 1, m_subpixelBits) / 2);
 943         const tcu::Vector<deInt64,2>                            pa                                      = LineRasterUtil::toSubpixelVector(m_v0.xy(), m_subpixelBits) + widthOffset;
 944         const tcu::Vector<deInt64,2>                            pb                                      = LineRasterUtil::toSubpixelVector(m_v1.xy(), m_subpixelBits) + widthOffset;
 945         const LineRasterUtil::SubpixelLineSegment       line                            = LineRasterUtil::SubpixelLineSegment(pa, pb);
 946
 947         int                                                                                     packetNdx                       = 0;
 948         int                                                                                     xDelta                          = (m_v1 - m_v0).x() > 0 ? 1 : -1;
 949         int                                                                                     yDelta                          = (m_v1 - m_v0).y() > 0 ? 1 : -1;
 950
 951         while (m_curPos.y() <= m_bboxMax.y() && m_curPos.y() >= m_bboxMin.y() && packetNdx < maxFragmentPackets)
 952         {
 953                 const tcu::Vector<deInt64,2> diamondPosition = LineRasterUtil::toSubpixelVector(m_curPos, m_subpixelBits) + tcu::Vector<deInt64,2>(halfPixel,halfPixel);
 954
 955                 // Should current fragment be drawn? == does the segment exit this diamond?
 956                 if (LineRasterUtil::doesLineSegmentExitDiamond(line, diamondPosition, m_subpixelBits))
 957                 {
 958                         const tcu::Vector<deInt64,2>    pr                                      = diamondPosition;
 959                         const float                                             t                                       = tcu::dot((pr - pa).asFloat(), (pb - pa).asFloat()) / tcu::lengthSquared(pb.asFloat() - pa.asFloat());
 960
 961                         // Rasterize on only fragments that are would end up in the viewport (i.e. visible)
 962                         const int                                               fragmentLocation        = (isXMajor) ? (m_curPos.y()) : (m_curPos.x());
 963                         const int                                               rowFragBegin            = de::max(0, minViewportLimit - fragmentLocation);
 964                         const int                                               rowFragEnd                      = de::min(maxViewportLimit - fragmentLocation, lineWidth);
 965
 966                         int stippleBit = (m_stippleCounter / m_stippleFactor) % 16;
 967                         bool stipplePass = (m_stipplePattern & (1 << stippleBit)) != 0;
 968                         m_stippleCounter++;
 969
 970                         if (stipplePass)
 971                         {
 972                                 // Wide lines require multiple fragments.
 973                                 for (; rowFragBegin + m_curRowFragment < rowFragEnd; m_curRowFragment++)
 974                                 {
 975                                         const int                       replicationId   = rowFragBegin + m_curRowFragment;
 976                                         const tcu::IVec2        fragmentPos             = m_curPos + minorDirection * replicationId;
 977
 978                                         // We only rasterize visible area
 979                                         DE_ASSERT(LineRasterUtil::inViewport(fragmentPos, m_viewport));
 980
 981                                         // Compute depth values.
 982                                         if (depthValues)
 983                                         {
 984                                                 const float za = m_v0.z();
 985                                                 const float zb = m_v1.z();
 986
 987                                                 depthValues[packetNdx*4+0] = (1 - t) * za + t * zb;
 988                                                 depthValues[packetNdx*4+1] = 0;
 989                                                 depthValues[packetNdx*4+2] = 0;
 990                                                 depthValues[packetNdx*4+3] = 0;
 991                                         }
 992
 993                                         {
 994                                                 // output this fragment
 995                                                 // \note In order to make consistent output with multisampled line rasterization, output "barycentric" coordinates
 996                                                 FragmentPacket& packet = fragmentPackets[packetNdx];
 997
 998                                                 const tcu::Vec4         b0              = tcu::Vec4(1 - t);
 999                                                 const tcu::Vec4         b1              = tcu::Vec4(t);
1000                                                 const tcu::Vec4         ooSum   = 1.0f / (b0 + b1);
1001
1002                                                 packet.position                 = fragmentPos;
1003                                                 packet.coverage                 = getCoverageBit(1, 0, 0, 0);
1004                                                 packet.barycentric[0]   = b0 * ooSum;
1005                                                 packet.barycentric[1]   = b1 * ooSum;
1006                                                 packet.barycentric[2]   = tcu::Vec4(0.0f);
1007
1008                                                 packetNdx += 1;
1009                                         }
1010
1011                                         if (packetNdx == maxFragmentPackets)
1012                                         {
1013                                                 m_curRowFragment++; // don't redraw this fragment again next time
1014                                                 m_stippleCounter--; // reuse same stipple counter next time
1015                                                 numPacketsRasterized = packetNdx;
1016                                                 return;
1017                                         }
1018                                 }
1019
1020                                 m_curRowFragment = 0;
1021                         }
1022                 }
1023
1024                 m_curPos.x() += xDelta;
1025                 if (m_curPos.x() > m_bboxMax.x() || m_curPos.x() < m_bboxMin.x())
1026                 {
1027                         m_curPos.y() += yDelta;
1028                         m_curPos.x() = xDelta > 0 ? m_bboxMin.x() : m_bboxMax.x();
1029                 }
1030         }
1031
1032         DE_ASSERT(packetNdx <= maxFragmentPackets);
1033         numPacketsRasterized = packetNdx;
1034 }
1035
1036 MultiSampleLineRasterizer::MultiSampleLineRasterizer (const int numSamples, const tcu::IVec4& viewport, const int subpixelBits)
1037         : m_numSamples                  (numSamples)
1038         , m_triangleRasterizer0 (viewport, m_numSamples, RasterizationState(), subpixelBits)
1039         , m_triangleRasterizer1 (viewport, m_numSamples, RasterizationState(), subpixelBits)
1040 {
1041 }
1042
1043 MultiSampleLineRasterizer::~MultiSampleLineRasterizer ()
1044 {
1045 }
1046
1047 void MultiSampleLineRasterizer::init (const tcu::Vec4& v0, const tcu::Vec4& v1, float lineWidth)
1048 {
1049         // allow creation of single sampled rasterizer objects but do not allow using them
1050         DE_ASSERT(m_numSamples > 1);
1051
1052         const tcu::Vec2 lineVec         = tcu::Vec2(tcu::Vec4(v1).xy()) - tcu::Vec2(tcu::Vec4(v0).xy());
1053         const tcu::Vec2 normal2         = tcu::normalize(tcu::Vec2(-lineVec[1], lineVec[0]));
1054         const tcu::Vec4 normal4         = tcu::Vec4(normal2.x(), normal2.y(), 0, 0);
1055         const float offset                      = lineWidth / 2.0f;
1056
1057         const tcu::Vec4 p0 = v0 + normal4 * offset;
1058         const tcu::Vec4 p1 = v0 - normal4 * offset;
1059         const tcu::Vec4 p2 = v1 - normal4 * offset;
1060         const tcu::Vec4 p3 = v1 + normal4 * offset;
1061
1062         // Edge 0 -> 1 is always along the line and edge 1 -> 2 is in 90 degree angle to the line
1063         m_triangleRasterizer0.init(p0, p3, p2);
1064         m_triangleRasterizer1.init(p2, p1, p0);
1065 }
1066
1067 void MultiSampleLineRasterizer::rasterize (FragmentPacket* const fragmentPackets, float* const depthValues, const int maxFragmentPackets, int& numPacketsRasterized)
1068 {
1069         DE_ASSERT(maxFragmentPackets > 0);
1070
1071         m_triangleRasterizer0.rasterize(fragmentPackets, depthValues, maxFragmentPackets, numPacketsRasterized);
1072
1073         // Remove 3rd barycentric value and rebalance. Lines do not have non-zero barycentric at index 2
1074         for (int packNdx = 0; packNdx < numPacketsRasterized; ++packNdx)
1075         for (int fragNdx = 0; fragNdx < 4; fragNdx++)
1076         {
1077                 float removedValue = fragmentPackets[packNdx].barycentric[2][fragNdx];
1078                 fragmentPackets[packNdx].barycentric[2][fragNdx] = 0.0f;
1079                 fragmentPackets[packNdx].barycentric[1][fragNdx] += removedValue;
1080         }
1081
1082         // rasterizer 0 filled the whole buffer?
1083         if (numPacketsRasterized == maxFragmentPackets)
1084                 return;
1085
1086         {
1087                 FragmentPacket* const nextFragmentPackets       = fragmentPackets + numPacketsRasterized;
1088                 float* nextDepthValues                                          = (depthValues) ? (depthValues+4*numPacketsRasterized*m_numSamples) : (DE_NULL);
1089                 int numPacketsRasterized2                                       = 0;
1090
1091                 m_triangleRasterizer1.rasterize(nextFragmentPackets, nextDepthValues, maxFragmentPackets - numPacketsRasterized, numPacketsRasterized2);
1092
1093                 numPacketsRasterized += numPacketsRasterized2;
1094
1095                 // Fix swapped barycentrics in the second triangle
1096                 for (int packNdx = 0; packNdx < numPacketsRasterized2; ++packNdx)
1097                 for (int fragNdx = 0; fragNdx < 4; fragNdx++)
1098                 {
1099                         float removedValue = nextFragmentPackets[packNdx].barycentric[2][fragNdx];
1100                         nextFragmentPackets[packNdx].barycentric[2][fragNdx] = 0.0f;
1101                         nextFragmentPackets[packNdx].barycentric[1][fragNdx] += removedValue;
1102
1103                         // edge has reversed direction
1104                         std::swap(nextFragmentPackets[packNdx].barycentric[0][fragNdx], nextFragmentPackets[packNdx].barycentric[1][fragNdx]);
1105                 }
1106         }
1107 }
1108
1109 LineExitDiamondGenerator::LineExitDiamondGenerator (const int subpixelBits)
1110         : m_subpixelBits(subpixelBits)
1111 {
1112 }
1113
1114 LineExitDiamondGenerator::~LineExitDiamondGenerator (void)
1115 {
1116 }
1117
1118 void LineExitDiamondGenerator::init (const tcu::Vec4& v0, const tcu::Vec4& v1)
1119 {
1120         const deInt64                                   x0                              = toSubpixelCoord(v0.x(), m_subpixelBits);
1121         const deInt64                                   y0                              = toSubpixelCoord(v0.y(), m_subpixelBits);
1122         const deInt64                                   x1                              = toSubpixelCoord(v1.x(), m_subpixelBits);
1123         const deInt64                                   y1                              = toSubpixelCoord(v1.y(), m_subpixelBits);
1124
1125         // line endpoints might be perturbed, add some margin
1126         const deInt64                                   xMin                    = de::min(x0, x1) - toSubpixelCoord(1, m_subpixelBits);
1127         const deInt64                                   xMax                    = de::max(x0, x1) + toSubpixelCoord(1, m_subpixelBits);
1128         const deInt64                                   yMin                    = de::min(y0, y1) - toSubpixelCoord(1, m_subpixelBits);
1129         const deInt64                                   yMax                    = de::max(y0, y1) + toSubpixelCoord(1, m_subpixelBits);
1130
1131         m_bboxMin.x() = floorSubpixelToPixelCoord(xMin, m_subpixelBits, true);
1132         m_bboxMin.y() = floorSubpixelToPixelCoord(yMin, m_subpixelBits, true);
1133         m_bboxMax.x() = ceilSubpixelToPixelCoord (xMax, m_subpixelBits, true);
1134         m_bboxMax.y() = ceilSubpixelToPixelCoord (yMax, m_subpixelBits, true);
1135
1136         m_v0 = v0;
1137         m_v1 = v1;
1138
1139         m_curPos = m_bboxMin;
1140 }
1141
1142 void LineExitDiamondGenerator::rasterize (LineExitDiamond* const lineDiamonds, const int maxDiamonds, int& numWritten)
1143 {
1144         DE_ASSERT(maxDiamonds > 0);
1145
1146         const deInt64                                                           halfPixel                       = 1ll << (m_subpixelBits - 1);
1147         const tcu::Vector<deInt64,2>                            pa                                      = LineRasterUtil::toSubpixelVector(m_v0.xy(), m_subpixelBits);
1148         const tcu::Vector<deInt64,2>                            pb                                      = LineRasterUtil::toSubpixelVector(m_v1.xy(), m_subpixelBits);
1149         const LineRasterUtil::SubpixelLineSegment       line                            = LineRasterUtil::SubpixelLineSegment(pa, pb);
1150
1151         int                                                                                     diamondNdx                      = 0;
1152
1153         while (m_curPos.y() <= m_bboxMax.y() && diamondNdx < maxDiamonds)
1154         {
1155                 const tcu::Vector<deInt64,2> diamondPosition = LineRasterUtil::toSubpixelVector(m_curPos, m_subpixelBits) + tcu::Vector<deInt64,2>(halfPixel,halfPixel);
1156
1157                 if (LineRasterUtil::doesLineSegmentExitDiamond(line, diamondPosition, m_subpixelBits))
1158                 {
1159                         LineExitDiamond& packet = lineDiamonds[diamondNdx];
1160                         packet.position = m_curPos;
1161                         ++diamondNdx;
1162                 }
1163
1164                 ++m_curPos.x();
1165                 if (m_curPos.x() > m_bboxMax.x())
1166                 {
1167                         ++m_curPos.y();
1168                         m_curPos.x() = m_bboxMin.x();
1169                 }
1170         }
1171
1172         DE_ASSERT(diamondNdx <= maxDiamonds);
1173         numWritten = diamondNdx;
1174 }
1175
1176 } // rr