0

Edit: So I found a page related to rasterizing a trapezoid https://cse.taylor.edu/~btoll/s99/424/res/ucdavis/GraphicsNotes/Rasterizing-Polygons/Rasterizing-Polygons.html but am still trying to figure out if I can just do the edges

I am trying to generate points for the corners of an arbitrary N-gon. Where N is a non-zero positive integer. But I am trying to do so efficiently without the need of division and trig. I am thinking that there is probably some of sort of Bresenham's type algorithm for this but I cannot seem to find anything.

The only thing I can find on stackoverflow is this but the internal angle increments are found by using 2*π/N: How to draw a n sided regular polygon in cartesian coordinates?

Here was the algorithm from that page in C

float angle_increment = 2*PI / n_sides;
for(int i = 0; i < n_sides; ++i)
{
    float x = x_centre + radius * cos(i*angle_increment +start_angle);
    float y = y_centre + radius * sin(i*angle_increment +start_angle);
}

So is it possible to do so without any division?

yosmo78
  • 489
  • 4
  • 13
  • 1
    If you are worried about performance, I imagine `N` calls to `sin` and `cos` are going to be much more expensive than a single division. What makes you believe division is the bottleneck? – Igor Tandetnik Jul 18 '20 at 23:57
  • You're worried about division but not about `cos` and `sin`? – dbush Jul 18 '20 at 23:57
  • divisions no but trigonometry yes... are you serius? – Alberto Sinigaglia Jul 18 '20 at 23:58
  • 1
    BTW, if you really hate division, then consider that `a/b` is just `a * b^-1`, so you can do `a * pow(b, -1)`, but believe me when i say that division is by some orders of magnitude more efficient – Alberto Sinigaglia Jul 19 '20 at 00:00
  • Well is there a way to do it without both division and trig? – yosmo78 Jul 19 '20 at 00:10
  • If you are willing to live with a small level of inaccuracy, you can use the solution suggested at https://gamedev.stackexchange.com/questions/4779/is-there-a-faster-sine-function. – R Sahu Jul 19 '20 at 04:44

1 Answers1

1

There's no solution which avoids calling sin and cos, aside from precomputing them for all useful values of N. However, you only need to do the computation once, regardless of N. (Provided you know where the centre of the polygon is. You might need a second computation to figure out the coordinates of the centre.) Every vertex can be computed from the previous vertex using the same rotation matrix.

The lookup table of precomputed values is not an unreasonable solution, since at some sufficiently large value of N the polygon becomes indistinguishable from a circle. So you probably only need a lookup table of a few hundred values.

rici
  • 234,347
  • 28
  • 237
  • 341