2

I made an algorithm that generates circles (it is also generalized to ellipses). Right away, circles of size 1 to 16 render like this:

enter image description here

Here is how 256×256 and 256×128 ellipses render:

enter image description here

The way this works is that I have 8 quadratic Bezier curve points on the angles 0, 45, 90, 135, 180, 225, 270, 315, like this:

enter image description here

(in case of ellipses, trigonometric calculations are used to determine the positions of points that produce a 45° angle)

(I know that this isn't an exact circle, for example its area by radius ² is 6√2-16⁄3≈3.15194804091, but it's good enough for rendering)

However, in case of a filled circle, I round the position of the diagonal points to one of those highlighted lines; the red line and yellow background indicate an example:

enter image description here

In case of a single pixel circle outline, I round the position of the diagonal points to one of those highlighted lines; the red line and yellow background indicate an example:

enter image description here

So, I'm using the principles of font hinting diagonally. And when the dimensions of the ellipse are not integers, the width and height gets rounded and the horizontal/vertical points and the center are calculated based on the rounded dimensions, but the position of the diagonal points (relative to the center) is based on the original dimensions, not the rounded ones; they're rounded not to the pixel grid's horizontal or vertical lines, but to the diagonal lines.

Here is an example of how a quarter of a 10×10 circle is rendered:

enter image description here

Here is an example of how a quarter of a 10×10 circle outline is rendered; which pixels the blue dots are in determines what pixels the output will include:

enter image description here

It's possible to make similar constructions for a thickness like this enter image description here (I don't know the name of this thickness) or this enter image description here (a thickness of 2 pixels) or anything.

Is this algorithm a good design or a bad design? What do you think? Does it have any advantages or disadvantages over competing algorithms (the circle algorithms in various image editors)?

Edit: Here is a comparison of the rendering of a 256×256 circle: on the left is the result of the built-in tool in RealWorld Cursor Editor, on the right is the result of the method described in this question:

enter image description here

Specifically focus on the parts where the circle edge is at a 45° angle. Note how this method handles this angle.

Also, I made a webpage where you can enter any parameters of size to generate an ellipse with this algorithm yourself: https://circlerenderer.netlify.com/

Improve this question
7
  • 1
    For which purposes? Where is this algorithm going to be used? Why is there no anti-alias? – Luciano Jul 3 '19 at 9:50
  • This algorithm could be used to render circles/ellipses in image editors, in place of the existing algorithms used by various image editors in their ellipse tool. Also, if you want anti-aliasing you could oversample: generate a circle 4 or 6 times as large, then downscale (with gamma correction; with or without subpixel rendering); this is the same principle as used in anti-aliased text rendering. – Piotr Grochowski Jul 3 '19 at 10:00
  • THis site is not for programming related things so asking for algorithmic usefulness is out of scope. Its ok, but seems like a awfully complex way of doing this. Although the molecularity may be a win when you implement other bezier tool sets steps. Altough this isn itself is pretty useless. – joojaa Jul 3 '19 at 11:42
  • This isn't asking for "algorithmic usefulness" at all. This question is meant for users to evaluate the OUTPUT as a graphic design, not the code itself. – Piotr Grochowski Jul 3 '19 at 15:15
  • 2
    But then your question is too broad. As looking good is a subjective thing. But also it is somewhat dependent on hardware you look the pictures at. In anycase there is very little use for pixelated circle renders. And its not entirely trivial to just supersample either. – joojaa Jul 3 '19 at 17:40
0

I'm not an algorithm specialist, but right off the bat I'd say circles 10-11-12-13 (hollow version) still look too square-ish and not so round compared to the filled version (I mean the 45° section). The rest looks fine given the pixel size, but also not so different from existing image editors.

Improve this answer
6
  • That's just how the maths turn out. The result makes sense to me. I don't think it really is wrong. Also I don't know what do you mean by "not so different from existing image editors"; every image editor uses a different algorithm. For instance, here is how MS Paint renders circle outlines from 1×1 to 16×16: i.imgur.com/E5DNerC.png – Piotr Grochowski Jul 3 '19 at 15:14
  • hm ok, I haven't used MS Paint for a while... Also you asked "what do you think?"; I answered what I think. I prefer a different result on the 45° section. – Luciano Jul 3 '19 at 15:21
  • "I prefer a different result on the 45° section." What in particular do you mean by a different result on the 45° section? There are many ways in which a result can be different from another. – Piotr Grochowski Jul 3 '19 at 15:22
  • the pixels form a straight line (for ex on 12-13 - compare with 14-15, it looks more like a circle to me.).The others could be just an octagon, it's not easy do differentiate just by looking at it. – Luciano Jul 3 '19 at 15:28
  • I think that's to be expected at such small sizes. At small sizes such details start to become subjective. I also added a comparison of a 256×256 circle rendered with another image editor (left) and my method (right) as a demonstration how this algorithm handles 45° angles compared to another method. – Piotr Grochowski Jul 3 '19 at 15:30

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.