2
$\begingroup$

I'm trying to draw a line between two specified points, by updating values in an array which is heightxWidth with each element a set of four bytes (r,g,b,a). In my naive implementation I get the top line which reaches a point with jagged steps in the top line shown below. My question is, how do I accomplish the standard canvas line effect without jumps seen here as the lower line shown below?

enter image description here

$\endgroup$
  • $\begingroup$ I don't know what "the standard canvas" is, but it sounds like the term you want to search for is "antialiasing", e.g. en.wikipedia.org/wiki/Xiaolin_Wu's_line_algorithm $\endgroup$ – Simon F Jun 19 at 15:44
  • 1
    $\begingroup$ yes this is exactly what I was looking for! $\endgroup$ – Li Brary Jun 19 at 21:21
  • 1
    $\begingroup$ @SimonF if you want to formulate your comment as an answer I will accept? $\endgroup$ – Li Brary Jun 20 at 20:38
1
$\begingroup$

The problem you are seeing, i.e. "jaggies" or "staircasing", is an example of the more general problem known as "aliasing" and, in the graphics field, the term you want to search for is "Antialiasing".

Aliasing occurs when you undersample a signal. If a signal contains frequencies at or above the Nyquist Frequency, which is 1/2 the sampling frequency, those higher frequencies will come back "in disguise" i.e. "under an alias".

The example I often give to new starters to explain the problem is:

Imagine you've started at a new job and work solidly, 9 to 5, except for a 1hr break from 12 to 1.
The boss, however, regularly walks around the building at 12:30 and never sees you at your desk. He therefore concludes you are lazy and so don't get a pay rise

That is an example of aliasing. The boss needs to sample at a (much) higher rate. (Randomised/stratified sampling would also help :-) )

In your line drawing example, I expect you are taking one sample per pixel, but if you do a Fourier analysis of a line, you will see it contains an infinite spread of frequencies. It's these higher frequencies (plus the reconstruction of the sampled results - which I've ignored) that can lead to the jaggy results.

The ideal solution is to low pass filter your incoming signal before sampling it, but that's 'nontrivial' with geometric data.

There are, however, multiple practical approaches to mitigating the problem, including supersampling (SSAA) and multispampling (MSAA), but in your case, perhaps something like Wu's method for antialiased line drawing will suffice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.