1

I am search for efficient algorithm and/or code to rasterize curved polygons. In best case such algorithm would support anti-aliasing with sub pixel accuracy. My goal is to understand and implement such algorithm in c++.

Point-In-Spline-Polygon Algorithm Here is the code to detect if point is inside such curved polygon, and of course one could use brute-force to rasterize this, but it would be too slow.

Essentially I need fast c++ code to produce images presented in this article.

Brute force code would look something like this.

// draw a single pixel at x,y coordinates.
void draw_pixel(int x, int y, int coverage);

// slow code without anti-aliasing 
void brute_force(int x_res, int y_res, double *poly) {
    for(int y = 0; y < y_res; ++y) {
        const double fy = double(y);
        for(int x = 0; x < x_res; ++x) {
            const double fx = double(x);
            if (pointInSplinePoly(poly, fx, fy)) {
                draw_pixel(x,y, 0xFF);
            }
        }
    }
}

Here is slow code with 2x2 anti-aliasing.

DevO
  • 365
  • 1
  • 8
  • Maybe you are looking for something like De Casteljau's alogrithm? – 123 Apr 10 '20 at 17:43
  • Thanks but it is not what I am looking for. I need to rasterize curved-polygon and not find a points on such polygon. – DevO Apr 10 '20 at 17:52
  • On the other side may be this is too narrow, and what I need is something like compact and simplified software font rasterization code. I know there are libraries that can do this but this code need to be as standalone. – DevO Apr 10 '20 at 18:00
  • The first thing that has to go is the `draw_pixel` function. That's going to be slow no matter how you implement the algorithm. – user3386109 Apr 10 '20 at 19:32
  • 1
    @ user3386109: yes I know this. Efficient algorithm will probably be scan-line based and use something like draw_line(y, x_start, x_end, coverage_start, coverage_end). – DevO Apr 10 '20 at 19:35
  • Yes, so the next step is to decide whether precomputing and/or caching are options. For example, you could precompute `x_start`, `x_end`, `coverage_start`, and `coverage_end` for each character in the font. You might also consider caching the rasterized characters as they are generated. – user3386109 Apr 10 '20 at 19:39
  • The question is how to calculate all this values for every scan-line in efficient way. – DevO Apr 10 '20 at 19:46
  • @DevO assuming 2D for really effective rasterization you need to handle only convex polygons. So first you need to disect your polygon into convex ones. The [basic scanline filling](https://stackoverflow.com/a/19078088/2521214) is enough as you guessed already. So instead of linear interpolation you use cubic (or whatever degree of curve you got) on floats with precomputed parameter step that is smaller than pixel and update the buffers. Once whole perimeter is done fill the stuff with horizontal or vertical lines... the step can be adjusted on the run by haming distance from last position ... – Spektre Apr 11 '20 at 13:54
  • So do you have CUBICs or different curves? any sample polygon for testing ? 2D limitation ? Flat or Gourard shading? any other parameters (texture etc ... ) ? for limited concavity is also doable without disecting but it involves quite a few edge cases tests slowing down this a bit. – Spektre Apr 11 '20 at 13:55
  • Added slow code with 2x2 anti-aliasing! – DevO Apr 17 '20 at 17:09

0 Answers0