1# OpenGL Line Segment Rasterization
2
3OpenGL and Vulkan both render line segments as a series of pixels between two points. They differ in
4which pixels cover the line.
5
6For single sample rendering Vulkan uses an algorithm based on quad coverage. A small shape is
7extruded around the line segment. Samples covered by the shape then represent the line segment. See
8[the Vulkan spec][VulkanLineRaster] for more details.
9
10OpenGL's algorithm is based on [Bresenham's line algorithm][Bresenham]. Bresenham's algorithm
11selects pixels on the line between the two segment points. Note Bresenham's does not support
12multisampling. When compared visually you can see the Vulkan line segment rasterization algorithm
13always selects a superset of the line segment pixels rasterized in OpenGL. See this example:
14
15![Vulkan vs OpenGL Line Rasterization][VulkanVsGLLineRaster]
16
17The OpenGL spec defines a "diamond-exit" rule to select fragments on a line. Please refer to the 2.0
18spec section 3.4.1 "Basic Line Segment Rasterization" spec for more details. To implement this rule
19we inject a small computation to test if a pixel falls within the diamond in the start of the pixel
20shader. If the pixel fails the diamond test we discard the fragment. Note that we only perform this
21test when drawing lines. See the section on [Shader Compilation](ShaderModuleCompilation.md) for
22more info. See the below diagram for an illustration of the diamond rule:
23
24![OpenGL Diamond Rule Example][DiamondRule]
25
26The diamond rule can be implemented in the fragment shader by computing the
27intersection between the line segment and the grid that crosses the pixel
28center. If the distance between an intersection and the pixel center is less
29than half a pixel then the line enters and exits the diamond. `f` is the pixel
30center in the diagram. The green circle indicates a diamond exit and the red
31circles indicate intersections that do not exit the diamond. We detect
32non-Bresenham fragments when both intersections are outside the diamond.
33
34The full code derivation is omitted for brevity. It produces the following
35fragment shader patch implementation:
36
37```
38vec2 p = (((((ANGLEPosition.xy) * 0.5) + 0.5) * viewport.zw) + viewport.xy);
39vec2 d = dFdx(p) + dFdy(p);
40vec2 f = gl_FragCoord.xy;
41vec2 p_ = p.yx;
42vec2 d_ = d.yx;
43vec2 f_ = f.yx;
44
45vec2 i = abs(p - f + (d/d_) * (f_ - p_));
46
47if (i.x > 0.500001 && i.y  > 0.500001)
48        discard;
49```
50
51Note that we must also pass the viewport size as an internal uniform. We use a small epsilon value
52to correct for cases when the line segment is perfectly parallel or perpendicular to the window. For
53code please see [TranslatorVulkan.cpp][TranslatorVulkan.cpp] under
54`AddLineSegmentRasterizationEmulation`.
55
56## Limitations
57
58Although this emulation passes all current GLES CTS tests it is not guaranteed
59to produce conformant lines. In particular lines that very nearly intersect
60the junction of four pixels render with holes. For example:
61
62![Holes in the emulated Bresenham line][Holes]
63
64Therefore for a complete implementation we require the Bresenham line
65rasterization feature from
66[VK_EXT_line_rasterization][VK_EXT_line_rasterization].
67
68[Bresenham]: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
69[DiamondRule]: img/LineRasterPixelExample.png
70[Holes]: img/LineRasterHoles.jpg
71[TranslatorVulkan.cpp]: https://chromium.googlesource.com/angle/angle/+/refs/heads/master/src/compiler/translator/TranslatorVulkan.cpp
72[VK_EXT_line_rasterization]: https://www.khronos.org/registry/vulkan/specs/1.1-extensions/man/html/VK_EXT_line_rasterization.html
73[VulkanLineRaster]: https://www.khronos.org/registry/vulkan/specs/1.1/html/chap24.html#primsrast-lines-basic
74[VulkanVsGLLineRaster]: img/LineRasterComparison.gif
75