Rasterize 'Bresenham' line segments as parallelograms
The previous 'connected diamonds' polygon that was used to rasterize
Bresenham lines suffered from duplicate rasterization of endpoints,
which violates the diamond exit-rule and is disallowed by the Vulkan
(and OpenGL) spec.
This change rasterizes Bresenham lines as a parallelogram, as described
by Vulkan's non-strictLines algorithm.
This satisfied Vulkan's requirements laid out in section 26.10.2
Bresenham Line Segment Rasterization:
"Implementations may use other line segment rasterization algorithms,
subject to the following rules:
- The coordinates of a fragment produced by the algorithm must not
deviate by more than one unit in either x or y framebuffer
coordinates from a corresponding fragment produced by the diamond-
exit rule.
- The total number of fragments produced by the algorithm must not
differ from that produced by the diamond-exit rule by no more than
one.
- For an x-major line, two fragments that lie in the same framebuffer-
coordinate column must not be produced (for a y-major line, two
fragments that lie in the same framebuffer-coordinate row must not be
produced).
- If two line segments share a common endpoint, and both segments are
either x-major (both left-to-right or both right-to-left) or y-mayor
(both bottom-to-top or both top-to-bottom), then rasterizing both
segments must not produce duplicate fragments. Fragments also must
not be omitted so as to interrupt continuity of the connected
segments."
OpenGL ES line rasterization has not been modified as part of this
change, to not require rebasing of golden images, but the parallelogram
algorithm was made available for easy comparison.
Bug: b/80135519
Change-Id: I09e8b90a393d3a08387d79669d9dbe5f83a0811d
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/38049
Presubmit-Ready: Nicolas Capens <nicolascapens@google.com>
Kokoro-Presubmit: kokoro <noreply+kokoro@google.com>
Tested-by: Nicolas Capens <nicolascapens@google.com>
Reviewed-by: Chris Forbes <chrisforbes@google.com>
Reviewed-by: Alexis Hétu <sugoi@google.com>
diff --git a/src/Device/Renderer.cpp b/src/Device/Renderer.cpp
index c37150d..ea68bc3 100644
--- a/src/Device/Renderer.cpp
+++ b/src/Device/Renderer.cpp
@@ -814,16 +814,17 @@
return false;
}
- // TODO(b/142965928): Bresenham lines should render the same with or without
- // multisampling, which will require a special case in the
- // code when multisampling is on. For now, we just use
- // rectangular lines when multisampling is enabled.
-
- // We use rectangular lines for non Bresenham lines and
- // for Bresenham lines when multiSampling is enabled
+ // We use rectangular lines for non-Bresenham lines (cf. 'strictLines'),
+ // and for Bresenham lines when multiSampling is enabled.
+ // FIXME(b/142965928): Bresenham lines should render the same with or without
+ // multisampling, which will require a special case in the
+ // code when multisampling is on. For now, we just use
+ // rectangular lines when multisampling is enabled.
if((draw.setupState.multiSample > 1) ||
- (draw.lineRasterizationMode != VK_LINE_RASTERIZATION_MODE_BRESENHAM_EXT)) // Rectangle centered on the line segment
+ (draw.lineRasterizationMode != VK_LINE_RASTERIZATION_MODE_BRESENHAM_EXT))
{
+ // Rectangle centered on the line segment
+
float4 P[4];
int C[4];
@@ -876,8 +877,13 @@
return draw.setupRoutine(&primitive, &triangle, &polygon, &data);
}
}
- else // Diamond test convention
+ else if(false) // TODO(b/80135519): Deprecate
{
+ // Connecting diamonds polygon
+ // This shape satisfies the diamond test convention, except for the exit rule part.
+ // Line segments with overlapping endpoints have duplicate fragments.
+ // The ideal algorithm requires half-open line rasterization (b/80135519).
+
float4 P[8];
int C[8];
@@ -982,6 +988,97 @@
return draw.setupRoutine(&primitive, &triangle, &polygon, &data);
}
}
+ else
+ {
+ // Parallelogram approximating Bresenham line
+ // This algorithm does not satisfy the ideal diamond-exit rule, but does avoid the
+ // duplicate fragment rasterization problem and satisfies all of Vulkan's minimum
+ // requirements for Bresenham line segment rasterization.
+
+ float4 P[8];
+ P[0] = P0;
+ P[1] = P0;
+ P[2] = P0;
+ P[3] = P0;
+ P[4] = P1;
+ P[5] = P1;
+ P[6] = P1;
+ P[7] = P1;
+
+ float dx0 = lineWidth * 0.5f * P0.w / W;
+ float dy0 = lineWidth * 0.5f * P0.w / H;
+
+ float dx1 = lineWidth * 0.5f * P1.w / W;
+ float dy1 = lineWidth * 0.5f * P1.w / H;
+
+ P[0].x += -dx0;
+ P[1].y += +dy0;
+ P[2].x += +dx0;
+ P[3].y += -dy0;
+ P[4].x += -dx1;
+ P[5].y += +dy1;
+ P[6].x += +dx1;
+ P[7].y += -dy1;
+
+ float4 L[4];
+
+ if(dx > -dy)
+ {
+ if(dx > dy) // Right
+ {
+ L[0] = P[1];
+ L[1] = P[5];
+ L[2] = P[7];
+ L[3] = P[3];
+ }
+ else // Down
+ {
+ L[0] = P[0];
+ L[1] = P[4];
+ L[2] = P[6];
+ L[3] = P[2];
+ }
+ }
+ else
+ {
+ if(dx > dy) // Up
+ {
+ L[0] = P[0];
+ L[1] = P[2];
+ L[2] = P[6];
+ L[3] = P[4];
+ }
+ else // Left
+ {
+ L[0] = P[1];
+ L[1] = P[3];
+ L[2] = P[7];
+ L[3] = P[5];
+ }
+ }
+
+ int C0 = Clipper::ComputeClipFlags(L[0]);
+ int C1 = Clipper::ComputeClipFlags(L[1]);
+ int C2 = Clipper::ComputeClipFlags(L[2]);
+ int C3 = Clipper::ComputeClipFlags(L[3]);
+
+ if((C0 & C1 & C2 & C3) == Clipper::CLIP_FINITE)
+ {
+ Polygon polygon(L, 4);
+
+ int clipFlagsOr = C0 | C1 | C2 | C3;
+
+ if(clipFlagsOr != Clipper::CLIP_FINITE)
+ {
+ if(!Clipper::Clip(polygon, clipFlagsOr, draw))
+ {
+ return false;
+ }
+ }
+
+ return draw.setupRoutine(&primitive, &triangle, &polygon, &data);
+ }
+ }
return false;
}
diff --git a/src/Renderer/Renderer.cpp b/src/Renderer/Renderer.cpp
index c3c2260..de1ab7b 100644
--- a/src/Renderer/Renderer.cpp
+++ b/src/Renderer/Renderer.cpp
@@ -1790,8 +1790,10 @@
return false;
}
- if(state.multiSample > 1) // Rectangle
+ if(state.multiSample > 1)
{
+ // Rectangle centered on the line segment
+
float4 P[4];
int C[4];
@@ -1844,8 +1846,13 @@
return setupRoutine(&primitive, &triangle, &polygon, &data);
}
}
- else // Diamond test convention
+ else if(true)
{
+ // Connecting diamonds polygon
+ // This shape satisfies the diamond test convention, except for the exit rule part.
+ // Line segments with overlapping endpoints have duplicate fragments.
+ // The ideal algorithm requires half-open line rasterization (b/80135519).
+
float4 P[8];
int C[8];
@@ -1950,6 +1957,97 @@
return setupRoutine(&primitive, &triangle, &polygon, &data);
}
}
+ else
+ {
+ // Parallelogram approximating Bresenham line
+ // This algorithm does not satisfy the ideal diamond-exit rule, but does avoid the
+ // duplicate fragment rasterization problem and satisfies all of Vulkan's minimum
+ // requirements for Bresenham line segment rasterization.
+
+ float4 P[8];
+ P[0] = P0;
+ P[1] = P0;
+ P[2] = P0;
+ P[3] = P0;
+ P[4] = P1;
+ P[5] = P1;
+ P[6] = P1;
+ P[7] = P1;
+
+ float dx0 = lineWidth * 0.5f * P0.w / W;
+ float dy0 = lineWidth * 0.5f * P0.w / H;
+
+ float dx1 = lineWidth * 0.5f * P1.w / W;
+ float dy1 = lineWidth * 0.5f * P1.w / H;
+
+ P[0].x += -dx0;
+ P[1].y += +dy0;
+ P[2].x += +dx0;
+ P[3].y += -dy0;
+ P[4].x += -dx1;
+ P[5].y += +dy1;
+ P[6].x += +dx1;
+ P[7].y += -dy1;
+
+ float4 L[4];
+
+ if(dx > -dy)
+ {
+ if(dx > dy) // Right
+ {
+ L[0] = P[1];
+ L[1] = P[5];
+ L[2] = P[7];
+ L[3] = P[3];
+ }
+ else // Down
+ {
+ L[0] = P[0];
+ L[1] = P[4];
+ L[2] = P[6];
+ L[3] = P[2];
+ }
+ }
+ else
+ {
+ if(dx > dy) // Up
+ {
+ L[0] = P[0];
+ L[1] = P[2];
+ L[2] = P[6];
+ L[3] = P[4];
+ }
+ else // Left
+ {
+ L[0] = P[1];
+ L[1] = P[3];
+ L[2] = P[7];
+ L[3] = P[5];
+ }
+ }
+
+ int C0 = clipper->computeClipFlags(L[0]);
+ int C1 = clipper->computeClipFlags(L[1]);
+ int C2 = clipper->computeClipFlags(L[2]);
+ int C3 = clipper->computeClipFlags(L[3]);
+
+ if((C0 & C1 & C2 & C3) == Clipper::CLIP_FINITE)
+ {
+ Polygon polygon(L, 4);
+
+ int clipFlagsOr = C0 | C1 | C2 | C3;
+
+ if(clipFlagsOr != Clipper::CLIP_FINITE)
+ {
+ if(!clipper->clip(polygon, clipFlagsOr, draw))
+ {
+ return false;
+ }
+ }
+
+ return setupRoutine(&primitive, &triangle, &polygon, &data);
+ }
+ }
return false;
}
