OpenGL line segment rasterization specification

Question

The most recent OpenGL specification (4.6 core), chapter 14.5.1 (Basic Line Segment Rasterization) (to be found at https://www.khronos.org/registry/OpenGL/specs/gl/glspec46.core.pdf) specifies how aliased lines (specified by 2 floating point endpoints) should be rasterized.

Ideally, the GL uses a “diamond-exit” rule to determine those fragments that are produced by rasterizing a line segment. For each fragment f with center at window coordinates x_f and y_f, define a diamond-shaped region that is the intersection of four half planes:

Essentially, a line segment starting at p_a and ending at p_b produces those fragments f for which the segment intersects R_f, except if p_b is contained in R_f.

However, consider this case:

When the line being drawn passes exactly through the corners of 2 adjacent diamonds as described by the formula above, neither fragment should be rasterized. The minimum value of the expression |x - x_f| + |y - y_f| is 1/2, and 1/2 is not less than 1/2, is therefore not part of R_f, and the line never intersects R_f. My software rasterization algorithm favors the right pixel in this case more or less arbitrarily due to an optimization.

Clearly that is not the intended behavior. In fact, further down, the specification says

Because the initial and final conditions of the diamond-exit rule may be difficult to implement, other line segment rasterization algorithms are allowed, subject to the following rules:

, followed by a bunch of rules that would essentially let implementors use Bresenham's algorithm almost as-is. Also, the topic 14.6.1 (Basic Polygon Rasterization) explicitly disambiguates a similar case for polygon rasterization:

Special treatment is given to a fragment whose center lies on a polygon edge. In such a case we require that if two polygons lie on either side of a common edge (with identical endpoints) on which a fragment center lies, then exactly one of the polygons results in the production of the fragment during rasterization.

Also, this corner case seems to be shrugged off according to my searches. Am I missing something in the specification? Which fragment is the correct one to rasterize in the ambiguous case presented above? What algorithm does (or how to define an algorithm) such that it handles this case correctly and consistently?

Answer 1

Also, this corner case seems to be shrugged off according to my searches. Am I missing something in the specification? Which fragment is the correct one to rasterize in the ambiguous case presented above?

The GL does not enforce a pixel-exact behavior (none of the common 3D rendering APIs does). It is actually left to to the implementation to implement appropriate rasterization rules, subject to the conditions given in the spec. There is no right or wrong decision, just the requirement of generating a fragment for just one of the primitives in this scenario, and different implementations can (and will) produce different outputs.

For the case of triangle rasterization, GPUs typically use some tie-breaking rule like the "top-left" rule: You can classify each edge of a triangle as either left or right (if they have a non-zero vertical extent) or as top or bottom (if both endpoints of the edge lie on the same y). Degenerated triangles (zero area) will never produce any fragments. rasterized.

If a pixel center (or any other sample point when using multisampling) lies exactly on one (or several) edges, that pixel/sample is considered "inside" of the primitive if and only if said pixel center is exclusively part of "left" or "top" edges.

Direct3D traditionally enforces the top-left rule in the specification, while OpenGL leaves such details completely open. A user of an OpenGL implementation can be sure that when rending two triangles sharing such a commmon edge, there will be no double fragments and no holes, and an implementor just has to use some algorithm which fulfills that.

Furthermore, the GL spec also requires implementations to fulfill some invariance rules, which generally enforce repeatability, so that an implementation cannot just randomly chose between different tie-breaking rules at different points in time. You should have a look at appendix A of the spec for details about the exact requirements and guarantees.

This implementor freedoms also applies to the corner-cases during line rasterization. I think that your conclusion

When the line being drawn passes exactly through the corners of 2 adjacent diamonds as described by the formula above, neither fragment should be rasterized.

is perfectly correct. In my opinion, the spec's description is very unfortunate at least. It would probably better to define the diamond as <= 1/2, and add the special rule that in cases where more than one diamond might be intersected at once, only one of the fragment shall be produced. Such a formulation would be consistent with the description for polygon rasterization, at least.