Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » How to draw arc in opengl?

This thread is locked; no one can reply to it. rss feed Print
How to draw arc in opengl?
yew chee
Member #9,289
November 2007

these are some information to draw arc

1. point 1
2. point 2
3. radius
4. angle of arc below 180 degree

How to write the code?

Archon
Member #4,195
January 2004
avatar

Look up how to do bezier curves.

yew chee
Member #9,289
November 2007

then,how to draw bezier?......:D

Edgar Reynaldo
Member #8,592
May 2007
avatar

If you just want a circular arc from a defined point and radius you need to know these things :
The point of the center of the circle.
The starting angle of the arc.
The angular length of the arc.

1int q = 0;// for counters
2double d_center_x = 160.0;
3double d_center_y = 120.0;
4int center_x = 160;
5int center_y = 120;
6double radius = 60.0;
7 
8const double PI = 3.141592653589793
9const double deg_to_rad = 180.0/PI;
10const double rad_to_deg = PI/180.0;
11 
12double start_angle_rad = 45.0*deg_to_rad;
13double angular_length_rad = 90.0*deg_to_rad;
14 
15const double arc_distance_between_points = 0.95;
16const double arc_length = radius*angular_length_rad;
17const double d_num_segments = arc_length / arc_distance_between_points;
18 
19int num_segments = static_cast<int>(d_num_segments);
20if ((d_num_segments - static_cast<double>(static_cast<int>(d_num_segments)) >= 0.5) {
21 num_segments += 1;
22}
23const int num_points = num_segments + 1;
24 
25int arc_point_x[num_points];
26int arc_point_y[num_points];
27double d_arc_point_x = 0.0;
28double d_arc_point_y = 0.0;
29 
30double current_angle_rad = 0.0;
31for (q = 0 ; q < num_points ; q++) {
32 current_angle_rad = start_angle_rad + (static_cast<double>(q) / (static_cast<double>(num_points - 1)))*angular_length_rad);
33 d_arc_point_x = d_center_x + radius*cos(current_angle_rad);
34 d_arc_point_y = d_center_y + radius*sin(current_angle_rad);
35 arc_point_x[q] = static_cast<int>(d_arc_point_x);
36 arc_point_y[q] = static_cast<int>(d_arc_point_y);
37}
38 
39/// bmp and color are not declared yet , just use whatever you need
40if (arc_distance_between_points <= 1.0) {
41 for (q = 0 ; q < num_points ; q++) {
42 // use opengl's version of putpixel instead
43 putpixel(bmp , arc_point_x[q] , arc_point_y[q] , color);
44 }
45}
46if (arc_distance_between_points > 1.0) {
47 for (q = 0 ; q < num_segments ; q++) {
48 // use opengl's version of line instead
49 line(bmp , arc_point_x[q] , arc_point_y[q] , arc_point_x[q+1] , arc_point_y[q+1] , color);
50 }
51}

This is just an example and is untested. I would make it into a function that accepts a BITMAP* , a center x and y for the circle , its radius and the starting angle and angular length of the arc.

If you want to use this to draw an arc using two points on a circle and its radius then you can find the two points (center points) that are equidistant from each of the two points on the circle and then pick the appropriate one. Pass that as the center and its radius. You'll have to find the starting angle and angular length as well.

Nicol Bolas
Member #9,238
November 2007

Quote:

these are some information to draw arc

1. point 1
2. point 2
3. radius
4. angle of arc below 180 degree

I'm afraid that this is not enough information. For example, the radius field is self-explanatory, but what do point 1 and point 2 refer to? And how do these points relate to the angle?

The usual definition of an arc is with a circle (point + radius) and two angles, with the arc drawn between them in a specific direction.

Given this information, drawing the arc is simple in OpenGL. You build a loop, from the first angle to the second, with some reasonable stepsize. Then, compute points on the circle for each angular increment in the loop. After that, feed these points to OpenGL as a list of lines.

Thomas Fjellstrom
Member #476
June 2000
avatar

I had coded a simple "degraded" form (subset) of an arc, wrote it in agl and perl/glut. Basically the function took the start coord, the end coord, and the radius. the rest is worked out, and the actual ends always reached from one end to the other, always making a half oval/circle. If I could get to it, Id post it, but Im not at home, and once I get home, I have no idea if its on the most recent backup I made (back in april/may or something).

edit: here it is

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

yew chee
Member #9,289
November 2007

Thomas,your code just draw half circle....not arc!

[IMG]http://img.photobucket.com/albums/v715/tiamchee/e.jpg[/IMG]

Nicol Bolas
Member #9,238
November 2007

I'm afraid your link is a little broken. However, I did see the image.

In any case, your definition of an arc is not in the format that is most reasonable for actual use. Also, it is not guaranteed to produce a result; if the radius is smaller than half the length of the line, then there can be no arc that fits the requirements. Even if the radius is large enough, it does not define a unique arc; it actually defines 2, depending on which side of the line you put the center of the circle. You can adopt a convention for it of course.

But in any case, the most effective form is with a circle and two angles. You can convert your format to this with some trigonometry and a convention as stated above. But I'll leave that as an exercise for the reader.

yew chee
Member #9,289
November 2007

that why i state one of the information is "angle of arc below 180"

so,only one center point can be determined......
if the radius too small,it should be error..!

Thomas Fjellstrom
Member #476
June 2000
avatar

Quote:

Thomas,your code just draw half circle....not arc!

I said that, but it actually draws half ellipses ;) you can pass in any radius.

Also, its a simple exercise to get it to draw normal arcs. I just short cut'ed it to do half ellipses.

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

Edgar Reynaldo
Member #8,592
May 2007
avatar

{I revised and corrected this post on 12-11-2007}

Since an arc is a segment of a circle then what we need first is a circle.

A circle can be defined in several ways :

  1. 1. A point and a radius.


  2. 2. Two unique points and a radius from them. (Defines two circles that pass through both points. Or rather two new points that are equidistant from both original points and are the centers of the two circles.)


  3. 3. Three unique points that are not on the same line defines one circle.

Since we want to draw arcs and not circles then we need 4 things :
(a) the center point of the circle
(b) the radius of the circle
(c) the starting angle
(d) the angular length of the arc (ending angle - starting angle).

I've already shown how to draw an arc using circle type # 1 in my previous code. I've refined it into a function which I will post below. In the meantime , I will explain how to draw an arc using circle types # 2 and # 3.

Drawing an arc using circle method # 2 :

Given 2 points A and B and a radius r :
http://www.allegro.cc/files/attachment/593940
Steps necessary to find (a) , (b) , (c) , (d) from above :
(pre-requisite -> The radius (r) must be greater than or equal to the distance from A to B divided by 2. Otherwise there is no possible point that can be the center of the circle with points A and B on it.)

################# Revision ################

I. Find the midpoint E of the line segment AB

<math>\mathrm{E_x = \frac{A_x + B_x}{2.0}}</math>

<math>\mathrm{E_y = \frac{A_y + B_y}{2.0}}</math>

II. Find the distances AE and then CE

II a. Find the distance from A to E using the distance formula.

<math>\mathrm{\overline{AE} = \sqrt{\left(E_x - A_x\right)^2 + \left(Ey - A_y\right)^2}}</math>

II b. Find the distance from C to E using the pythagorean theorem.
(Angle AEC is a right angle by definition since angle theta = angle beta + PI/2.0)

<math>\mathrm{\overline{CE} = \sqrt{r^2 - \left(\overline{AE}\right)^2}}</math>

III. Find the angle of A to B and then the angle of C to E
We can use the atan2 function to find the angles from point to point. It returns angles in radians in values from -PI to PI , so we'll normalize them to the values [0 to 2.0*PI). So if they come back from the function as a negative angle then add 2.0*PI to them (a positive whole turn).

III a. Find angle AB

<math>\mathrm{\angle\overrightarrow{AB} = atan2\left((B_y - A_y) , (B_x - A_x)\right)}</math>

III b. Find angle CE by adding PI/2.0 to angle AB (one positive quarter turn)

<math>\mathrm{\angle\overrightarrow{CE} = \angle\overrightarrow{AB} + \frac{\pi}{2.0}}</math>

IV. Now we can find the coordinates of the center of the circle
If you want the curve to be righthanded (when drawing the arc from A to B the angle of the direction of movement decreases (turns clockwise)) then use Cx,Cy as the center of the circle and if you want the curve to be lefthanded then use Dx,Dy as the center of the circle.

IV a. Right handed curve (clockwise) (decreasing angles)

<math>\mathrm{C_x = E_x - \overline{CE}*\cos\left(\angle\overrightarrow{CE}\right)}</math>
<math>\mathrm{C_y = E_y - \overline{CE}*\sin\left(\angle\overrightarrow{CE}\right)}</math>

IV b. Left handed curve (counterclockwise) (increasing angles)

<math>\mathrm{D_x = E_x + \overline{CE}*\cos\left(\angle\overrightarrow{CE}\right)}</math>
<math>\mathrm{D_y = E_y + \overline{CE}*\sin\left(\angle\overrightarrow{CE}\right)}</math>

V. Finding angles from C or D to A and B
Now we will find the angles from the center of the circle to each of the two original points so that we can find the starting angle and angular length of the arc.

V a. Right handed curve

<math>\mathrm{\angle\overrightarrow{CA} = atan2\left((A_y - C_y) , (A_x - C_x)\right)
}</math>
<math>\mathrm{\angle\overrightarrow{CB} = atan2\left((B_y - C_y) , (B_x - C_x)\right)
}</math>
Now normalize the values (if (angle < 0) {angle += 2.0*PI;})

V b. Left handed curve

<math>\mathrm{\angle\overrightarrow{DA} = atan2\left((A_y - D_y) , (A_x - D_x)\right)
}</math>
<math>\mathrm{\angle\overrightarrow{DB} = atan2\left((B_y - D_y) , (B_x - D_x)\right)
}</math>
Now normalize the values (if (angle < 0) {angle += 2.0*PI;})

VI. Now we find the starting angle and ending angle.

VI a. Right handed curves
If the arc is right handed (angle decreases as the arc is drawn from A to B) then we know the starting angle of the arc is angle C to A and the ending angle is angle C to B. However , for the angular length to be computed properly , angle C to B must be less than angle C to A.

<math>\mathrm{\angle StartingAngle = \angle\overrightarrow{CA}}</math>
if (angCtoB > angCtoA) {angCtoB -= 2.0*PI;}
<math>\mathrm{\angle EndingAngle = \angle\overrightarrow{CB}}</math>

VI b. Left handed curves
If the arc is left handed (angle increases as the arc is drawn from A to B) then we know the starting angle of the arc is angle D to A and the ending angle is angle D to B. However , for the angular length to be computed properly , angle D to B must be more than angle D to A.

<math>\mathrm{\angle StartingAngle = \angle\overrightarrow{DA}}</math>
if (angDtoB < angDtoA) {angDtoB += 2.0*PI;}
<math>\mathrm{\angle EndingAngle = \angle\overrightarrow{DB}}</math>

VII. Finding the angular length
The starting angle plus the angular length of the arc equals the ending angle.
So the angular length of the arc equals (the ending angle - the starting angle).

<math>\mathrm{\angle StartingAngle + \angle AngularLength = \angle EndingAngle}</math>

<math>\mathrm{\angle AngularLength = \angle EndingAngle - \angle StartingAngle}</math>

VIII. Solution for arc data complete!
Now we have the coordinates of the center of the circle , the starting angle of the arc and the angular length of the arc. Pass these to the arc drawing function and enjoy! :D

############### End Revision ###############

Here's my revised code for drawing an arc given (a) , (b) , (c) , and (d) from above and also the distance you would like between successive points on the arc.

1#include <allegro.h>
2#include <cmath>
3 
4void round_double (double dbl_to_round , int &rounded_num) {
5 rounded_num = static_cast<int>(dbl_to_round);
6 if ((dbl_to_round - static_cast<double>(rounded_num)) >= 0.5) {rounded_num++;}
7}
8 
9void draw_arc(BITMAP* dest_bmp , double d_circ_center_x , double d_circ_center_y , double d_radius ,
10 double d_start_angle_deg , double d_angular_length_deg , double d_arc_distance_between_points , int color) {
11 
12 int q = 0;// for counters
13 double d_q = 0.0;// for percentage of loop completed
14 double d_q_plus_one = 0.0;
15
16 const double d_start_angle_rad = d_start_angle_deg*deg_to_rad;
17 const double d_angular_length_rad = d_angular_length_deg*deg_to_rad;
18 double d_angular_length_rad_per_segment = 0.0;
19
20 
21 double arc_length = d_radius*d_angular_length_rad;
22 if (arc_length < 0.0) {arc_length *= -1.0;}
23 const double d_num_segments = arc_length / d_arc_distance_between_points;
24 
25 int num_segments = 0;
26 round_double(d_num_segments , num_segments);
27 
28 if (num_segments == 0) {num_segments += 1;} // need at least one segment (two points)
29 const int num_points = num_segments + 1;
30 const double d_num_points_minus_one = static_cast<double>(num_points - 1);
31 
32 int arc_point_x;//[num_points];
33 int arc_point_y;//[num_points];
34 int arc_point2_x;//[num_points];
35 int arc_point2_y;//[num_points];
36 double d_arc_point_x = 0.0;
37 double d_arc_point_y = 0.0;
38 double d_arc_point2_x = 0.0;
39 double d_arc_point2_y = 0.0;
40 
41 double current_angle_rad = 0.0;
42 double current_angle2_rad = 0.0;
43
44
45 /// bmp and color are not declared yet , just use whatever you need
46 if (d_arc_distance_between_points <= 1.0) {
47 for (q = 0 ; q < num_points ; q++) {
48 d_q = static_cast<double>(q);
49 current_angle_rad = d_start_angle_rad + (d_q / d_num_points_minus_one)*d_angular_length_rad;
50 d_arc_point_x = d_circ_center_x + d_radius*cos(current_angle_rad);
51 d_arc_point_y = d_circ_center_y + d_radius*sin(current_angle_rad);
52
53 round_double(d_arc_point_x , arc_point_x);
54 round_double(d_arc_point_y , arc_point_y);
55
56 /// use opengl's version of putpixel instead
57 putpixel(dest_bmp , arc_point_x , arc_point_y , color);
58 }
59 }
60 if (d_arc_distance_between_points > 1.0) {
61
62 d_angular_length_rad_per_segment = d_angular_length_rad / d_num_points_minus_one;
63 for (q = 0 ; q < num_segments ; q++) {
64 d_q = static_cast<double>(q);
65 d_q_plus_one = static_cast<double>(q + 1);
66 
67 current_angle_rad = d_start_angle_rad + d_q*d_angular_length_rad_per_segment;
68 current_angle2_rad = d_start_angle_rad + d_q_plus_one*d_angular_length_rad_per_segment;
69 
70 d_arc_point_x = d_circ_center_x + d_radius*cos(current_angle_rad);
71 d_arc_point_y = d_circ_center_y + d_radius*sin(current_angle_rad);
72 
73 round_double(d_arc_point_x , arc_point_x);
74 round_double(d_arc_point_y , arc_point_y);
75 
76 d_arc_point2_x = d_circ_center_x + d_radius*cos(current_angle2_rad);
77 d_arc_point2_y = d_circ_center_y + d_radius*sin(current_angle2_rad);
78 
79 round_double(d_arc_point2_x , arc_point2_x);
80 round_double(d_arc_point2_y , arc_point2_y);
81 
82 /// use opengl's version of line instead
83 line(dest_bmp , arc_point_x , arc_point_y , arc_point2_x , arc_point2_y , color);
84 }
85 }
86 
87 
88 return;
89}

I've also attached the source code to an example program using this function. ArcTest.zip
The example program has been revised and will be included in the next post.
It has three modes for drawing arcs.
In mode 1 you can draw an arc from (a),(b),(c), and (d) above.
In mode 2 you can draw an arc between two points , move the points and alter the radius.
In mode 3 you can draw an arc from one point through another point to a third point. Each point can be moved with the mouse. This one is the most fun but I like mode 2 also.

I'll show how to draw an arc from point A through point B to point C in my next post.

{Edited formulas for correctness 12-11-2007}

Albin Engström
Member #8,110
December 2006
avatar

Edgar Reynaldo rocks, just coming out of nowhere and posting awesomely detailed answers.. unfortunately, I'm not good enough to understand half of it but i really like the time he spends on sharing his knowledge, i think you should make handy tutorials instead of letting things like this fade away as mere replies. :).

Also, maybe the draw_arc function could make a good contribution too the allegro library? as far as i can tell allegro does not have such a function and i think it might be a cool thing to have included.

Edgar Reynaldo
Member #8,592
May 2007
avatar

{I revised and corrected this post on 12-14-2007}

My previous post in this thread has been updated and corrected. I've tested the process for finding the correct information to draw an arc from 2 unique points , a radius , and the direction of the angle drawing the curve. It works now!

This post has been revised and corrected since the last method was based on incorrect formulas.
All mistakes have been fixed and this method works properly now.

- Albin -
Thanks for the appreciation. No problem. :)
As far as making tutorials , I don't mind. I can convert things to wiki pages when I get the time. When I write long replies like this , I always keep it saved as a local text file so I don't lose my work. ;)
If you have any questions just ask , I'd be glad to explain.
What kind of tutorial would you be interested in? Something on Trigonometry? Geometry?

BTW , Allegro already has an arc function that accepts integer circle coordinates and angles in allegro's fixed data type.

Other note : The function for drawing an arc that I posted takes degrees and not radians , but could be easily altered to accept radian angles.

On to cooler things , drawing an arc from point A through point B to point C.

http://www.allegro.cc/files/attachment/593951

#################### Revision #########################

Okay , step by step here is how to get the relevant data to draw an arc from point A through point B to point C.

I. First make sure that all three points are unique (are not equivalent).

II. Find the angles from A to B , from B to C , and from A to C by using the atan2 function :

<math>\mathrm{\angle\overrightarrow{AB} = atan2\left((B_y - A_y) , (B_x - A_x)\right)}</math>

<math>\mathrm{\angle\overrightarrow{BC} = atan2\left((C_y - B_y) , (C_x - B_x)\right)}</math>

<math>\mathrm{\angle\overrightarrow{AC} = atan2\left((C_y - A_y) , (C_x - A_x)\right)}</math>

Since the atan2 function returns values in the range from -PI to PI , normalize them to [0,2.0*PI).
So if they are less than 0 , then add 2.0*PI.

III. Determine the direction that the curve of the arc is being drawn and make sure all 3 points are not on a line.
The next thing we need to do is find angle X which is the change in angle between angle AB and angle AC which determines the direction of the curve of the arc as it is drawn from A through B to C.

<math>\mathrm{\angle\overrightarrow{AB} + \angle X = \angle\overrightarrow{BC}}</math>

<math>\mathrm{\angle X = \angle\overrightarrow{BC} - \angle\overrightarrow{AB}}</math>

In this case let's normalize the angle to [-PI , PI] so :

double ang_X = ang_BtoC - ang_AtoB;
if (ang_X > PI) {
  ang_X -= two_pi;
} else {
  if (ang_X < -1.0*PI) {ang_X += two_pi;}
}

Angle X tells us whether the arc from A through B to C is a right handed arc (drawn clockwise) (as the arc is drawn the angle decreases) or if it is a left handed arc (drawn counterclockwise) (as the arc is drawn the angle increases). If angle X is from 0 degrees to 180 degrees (0 to PI) then it is left handed. If angle X is from 180 to 360 degrees (PI to 2*PI) (also -180 to 0 or -PI to 0) then it is right handed. Note that angle X can not be 0 degrees or 180 degrees otherwise all three points are on the same line and could never be points on a circle.

So now we check whether angle X is equal to 0.0 or whether |angle X| is equal to PI. If either is true then all three points are on the same line and cannot be used to make a circle.

Now that we know angle X and that the three points are not on a line then from its value we know which direction the curve is being drawn. If angle X is greater than zero then the curve of arc is left handed (counterclockwise) (increasing angles). If angle X is less than zero then the curve of the arc is right handed (clockwise) (decreasing angles).

if (ang_X < 0.0) {righthanded = true;}
if (ang_X > 0.0) {lefthanded = true;}

IV. Find the midpoints of AB , BC , and AC.
The midpoint of two points is the sum of their positions divided by two.
Point D is the midpoint of AB , point E is the midpoint of AC , and point F is the midpoint of BC.

V. Find the angles from the center of the circle (point G) to points D , E , and F.
It is easy to find these angles since they are just one positive quarter turn added to angles AB , AC , and BC.

<math>\mathrm{\angle\overrightarrow{GD} = \angle\overrightarrow{AB} + \frac{PI}{2.0}}</math>

<math>\mathrm{\angle\overrightarrow{GE} = \angle\overrightarrow{AC} + \frac{PI}{2.0}}</math>

<math>\mathrm{\angle\overrightarrow{GF} = \angle\overrightarrow{BC} + \frac{PI}{2.0}}</math>

If any of these angles are greater than or equal to 2.0*PI than subtract 2.0*PI from them to get a normalized angle from [0,2.0*PI).

VI. Find general first degree equations for the lines through G and D , G and E , and G and F.
The position where these lines intersect is the center of the circle so first find the general first degree equations for these lines using a point on the line and the angle of the line (D and angle GD , E and angle GE , F and angle GF). So , given a point and an angle , this is how to find the general first degree equation of the line it creates :
The form of a general first degree equation is :

<math>\mathrm{A*x + B*y + C = 0}</math>

Now take two points <math>\mathrm{(x_1 , y_1) and (x_2 , y_2)}</math> and assume they are on the same line.
Putting them each in the equation separately and subtracting C from both sides of each equation we have :

<math>\mathrm{A*x_1 + B*y_1 = -C}</math>
<math>\mathrm{A*x_2 + B*y_2 = -C}</math>

Since the left hand side of each equation is equal to negative C then we can set them equal to each other and solve for A or B. This gives us :

<math>\mathrm{A*x_1 + B*y_1 = A*x_2 + B*y_2}</math> and then :

<math>\mathrm{A*(x_1 - x_2) = B*(y_2 - y_1)}</math> so :

<math>\mathrm{A = B*\left(\frac{y_2 - y_1}{x_1 - X_2}\right)}</math>

<math>\mathrm{B = A*\left(\frac{x_1 - x_2}{y_2 - y_1}\right)}</math>

Since we only have one point and an angle to find the equation of the line from , we need to refine these a little. Using trigonometry we can replace (y2 - y1) with r*sin(θ) and replace (x1 - x2) with -r*cos(θ) where θ is the angle of the line.

This diagram should make it clear.

{"name":"593952","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/6\/a6e00543828d1cf74db7ab9e8fd637ac.png","w":480,"h":360,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/6\/a6e00543828d1cf74db7ab9e8fd637ac"}593952

Okay , so if we substitute r*sin(θ) and -r*cos(θ) into our equation then the r's factor out and give us :

Formula # 1
<math>\mathrm{A = B*\left(\frac{\sin(\theta)}{-1*cos(\theta)}\right)}</math>

Formula # 2
<math>\mathrm{B = A*\left(\frac{-1*\cos(\theta)}{sin(\theta)}\right)}</math>

If the line is either horizontal or vertical then one of these formulas will be undefined due to division by zero , but the other will still be valid. If the line is diagonal then either formula will work but I prefer # 1 because it is easier to translate it to a slope-intercept line equation. Okay , so now we have the ratio between A and B , but how do we go on from here?

Using N as a constant multiplier of the formula for a first degree general equation we have :
<math>\mathrm{N*(A*x + B*y + C) = N*(0)}</math>

This means that we can scale the equation according to our needs. If we set N = 1/B as long as B != 0 then we have effectively changed B to the value of 1. Similarly this can be used to scale A as well as long as A != 0. This gives us three cases to handle then when we want to find the general first degree equation of a line from a point and an angle :

Horizontal line (cos(θ) == 0)
Formula # 1 becomes invalid so we have to use # 2. Set A equal to 1 , find B , and then solve for C.

Vertical line (sin(θ) == 0)
Formula # 2 becomes invalid so we have to use # 1. Set B equal to 1 , find A , and then solve for C.

Diagonal line (non-zero values for sin(θ) and cos(θ))
Either formula is valid , but formula # 1 is preferable because if you set B to 1 then you can easily find the slope-intercept equation of the line from the general first degree equation by subtracting A*x and C from both sides of the equation.

Okay , so we use this method to find the general first degree equations of the lines through GD , GE , and GF.

VII. Now find the intersection of two of the three equations and we have found the center of the circle.

Say we have two first degree general equations like this :

<math>\mathrm{A*x + B*y + C = 0}</math>
<math>\mathrm{D*x + E*y + F = 0}</math>

Subtract the constants from each side of the appropriate equation.

<math>\mathrm{A*x + B*y = -C}</math>
<math>\mathrm{D*x + E*y = -F}</math>

Now to find x or y then we need to multiply one of the equations by a constant so we can subtract away either x or y.

To find x , multiply the second equation times (B/E) and then subtract the result from the first equation and solve for x.
Sparing you the steps , the result is this :

<math>\mathrm{x = \frac{C*E - B*F}{B*D - A*E}}</math>

To find y , multiply the second equation by (A/D) and then subtract the result from the first equation and solve for y.
Which results in :

<math>\mathrm{y = \frac{A*F - C*D}{B*D - A*E}}</math>

If B*D is equal to A*E then the lines are parallel and have no strict intersection. They may be the same line or just parallel to each other.

So now we have equations to find the x and y point of the circle's center.

VIII. Find the radius of the circle.
Now that we have the position of the center of the circle , just use the distance formula to calculate it's distance from one of the three original points.

IX. Find the starting angle , ending angle , and then the angular length of the arc.

The starting angle of the arc is the angle from G to A.
<math>\mathrm{StartingAngle = \angle\overrightarrow{GA} = atan2((A_y - G_y) , (A_x - G_x))}</math>

The ending angle of the arc is the angle from G to C.
<math>\mathrm{EndingAngle = \angle\overrightarrow{GC} = atan2((C_y - G_y) , (C_x - G_x))}</math>

If we are making a right handed (clockwise , angle decreasing) curving arc then we need to make sure that the ending angle is less than the starting angle so that we get the correct portion of the curve. If the curve is left handed (counterclockwise , angle increasing) then we need to make sure the ending angle is greater than the starting angle.

if (left_handed_arc) {
  if (EndingAngle <= StartingAngle) {EndingAngle += 2.0*PI;}
}
if (right_handed_arc) {
  if (EndingAngle >= StartingAngle) {EndingAngle -= 2.0*PI;}
}

So now from the diagram , angle Y is the angular length of the arc to be drawn and since angle GA plus angle Y equals angle GC then :
<math>\mathrm{\angle \overrightarrow{GA} + \angle Y = \angle \overrightarrow{GC}}</math>

So :
<math>\mathrm{AngularLength = \angle Y = \angle \overrightarrow{GC} - \angle \overrightarrow{GA}}</math>

X. Draw the arc and enjoy!

So finally we have our circle's center , the radius , the starting angle , and the angular length of the arc so we can pass all of our values to our arc drawing function! :D

I have expanded the example program to use three moveable points and display an arc drawn through them.

Here's the up to date , working ArcTest source code , just link against Allegro.
Here's the list of keys you can use in the program ArcTest key list
Here's a dynamically compiled Windows binary ArcTest binary

Key reference

1 
2Keys that can be used in any mode
3Numpad 1,3 decrease,increase the distance between points drawn on the arc
4key R randomize the color of the arc
5key A clear the screen
6key I toggle clearing on and off
7key 1 select mode 1 for drawing an arc using a point , a radius , a starting angle and angle length
8key 2 select mode 2 for drawing an arc from 2 points
9key 3 select mode 3 for drawing an arc from point A through point B to point C
10key ESC quit
11 
12Keys that can be used while in mode # 1
13Numpad 4,6 decrease,increase the starting angle of the arc
14Numpad 7,9 decrease,increase the angular length of the arc
15Numpad -,+ decrease,increase the radius of the circle
16Arrow keys move the center of the circle
17 
18Keys that can be used while in mode # 2
19Key H reverse the handed-ness of the arc's curve (use the other circle's center point)
20 
21Left mouse click and drag the 2 different points that the arc is drawn between
22Note : If it says that the arc is invalid , increase the radius with the Numpad + key
23 
24Keys that can be used while in mode # 3
25Left mouse click and drag the 3 different points that the arc is drawn between
26Note : If it says that the arc is invalid it is because all 3 points are on the same line or two are overlapping and have the same value

The program is fun , give it a try!

################# End Revision ############################

{I revised and corrected this post on 12-14-2007}

juvinious
Member #5,145
October 2004
avatar

Nice stuff.
Testing out your code it seems that it does a complete circle instead of an arc from one point to another, like the allegro arc function.

__________________________________________
Paintown

Edgar Reynaldo
Member #8,592
May 2007
avatar

- juvinious -
No , my arc drawing function just draws an arc of the angular length that you pass to it.

I have completely revised both of my previous posts in this thread since I screwed up the method used to find an arc from 2 points and a radius or from three points. If anyone was using them before , please reread them.

Both new methods now work properly and I made a fun example program that uses them. The links to source code , key reference , and windows binary are at the end of my previous post.

- Edit -
Forgot that in mode 2 , the H key reverses which circle is used for the arc (left handed curve or right handed). Key reference and post updated.
- End Edit -

Here are a couple of pics from the program.

Mode 2
{"name":"593956","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/3\/f3aca1a108e2c1acc922f15a0176f657.jpg","w":640,"h":480,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/3\/f3aca1a108e2c1acc922f15a0176f657"}593956

Mode 3
{"name":"593957","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/5\/a53440de8b147ee4fb97dd35ecead201.jpg","w":640,"h":480,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/5\/a53440de8b147ee4fb97dd35ecead201"}593957

Mode 3 with screen clearing off (key I)
{"name":"593958","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/8\/8848c3c03a3f5fed00471805d9f4adb3.jpg","w":640,"h":480,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/8\/8848c3c03a3f5fed00471805d9f4adb3"}593958

Jonatan Hedborg
Member #4,886
July 2004
avatar

My god :o Very nice post!

-------
Sweden: Free from the shackles of Democracy since 2008-06-18!

Rash
Member #2,374
May 2002
avatar

Mathematics aside, no one has mentioned gluPartialDisk yet.

SiegeLord
Member #7,827
October 2006
avatar

I have recently wrote an arc and a circle drawing functions for my game framework. They are unremarkable in terms of their functionality, but I wanted to draw attention to the way I calculate points on the circle. My way is significantly faster than calculating each point using repeated calls of cos and sin. My inspiration came from physics, where the circular motion is described by a constant centripetal acceleration. The algorithm first moves the current point on the tangent line to the circle for some precomputed distance. Then it moves it towards the centre for some precomputed distance. Here they are:

1void DrawCircle(float _x, float _y, float _r, float depth, int32_t color, int segments)
2{
3 float r,g,b,a;
4 
5 r = float(getr32(color)) / 255.0f;
6 g = float(getg32(color)) / 255.0f;
7 b = float(getb32(color)) / 255.0f;
8 a = float(geta32(color)) / 255.0f;
9 
10 glColor4f(r, g, b, a);
11
12 float theta = 2 * AL_PI / float(segments);
13 float tangetial_factor = tanf(theta);
14 float radial_factor = 1 - cosf(theta);
15
16 float x = _x + _r;
17 float y = _y;
18
19 glBegin(GL_LINE_LOOP);
20 for(int ii = 0; ii < segments; ii++)
21 {
22 glVertex3f(x, y, depth);
23
24 float tx = -(y - _y);
25 float ty = x - _x;
26
27 x += tx * tangetial_factor;
28 y += ty * tangetial_factor;
29
30 float rx = _x - x;
31 float ry = _y - y;
32
33 x += rx * radial_factor;
34 y += ry * radial_factor;
35 }
36 glEnd();
37
38 glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
39}
40 
41//segments - number of segments per full revolution!
42//d_angle - determines the direction and the ammount of the arc to draw
43void DrawArc(float _x, float _y, float _r, float depth, float start_angle, float d_angle, int32_t color, int segments)
44{
45 float r,g,b,a;
46 
47 r = float(getr32(color)) / 255.0f;
48 g = float(getg32(color)) / 255.0f;
49 b = float(getb32(color)) / 255.0f;
50 a = float(geta32(color)) / 255.0f;
51 
52 glColor4f(r, g, b, a);
53
54 int real_segments = int(fabsf(d_angle) / (2 * AL_PI) * (float)segments) + 1;
55
56 float theta = d_angle / float(real_segments);
57 float tangetial_factor = tanf(theta);
58 float radial_factor = 1 - cosf(theta);
59
60 float x = _x + _r * cosf(start_angle);
61 float y = _y + _r * sinf(start_angle);
62
63 glBegin(GL_LINE_STRIP);
64 for(int ii = 0; ii < real_segments + 1; ii++)
65 {
66 glVertex3f(x, y, depth);
67
68 float tx = -(y - _y);
69 float ty = x - _x;
70
71 x += tx * tangetial_factor;
72 y += ty * tangetial_factor;
73
74 float rx = _x - x;
75 float ry = _y - y;
76
77 x += rx * radial_factor;
78 y += ry * radial_factor;
79 }
80 glEnd();
81
82 glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
83}

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Edgar Reynaldo
Member #8,592
May 2007
avatar

- SiegeLord -
Your approach looks intriguing , although I have a few questions.

Are your sinf , cosf , and tanf functions just wrappers for the sin,cos,and tan C functions that cast the float to a double , apply the function and then cast it back to a float and return the value?

I don't quite understand the geometry behind how you adjust the position to plot each time through the loop. The radial_factor , 1 - cosf(theta) , what does that represent geometrically?

Don't you get compiler redeclaration errors in the for loops when you declare float tx,ty , rx,ry in each iteration?

As a note , when you assign "float tx = -(y - _y);" , you could just rewrite that as "tx = _y - y;" and save a negation. Not that it matters codewise , but tangetial_factor is misspelled , a missing "n".

Anyways , it's a cool idea , thanks for sharing. :)

Milan Mimica
Member #3,877
September 2003
avatar

I can respond to some of the questions.

Quote:

Are your sinf , cosf , and tanf functions just wrappers...

sinf, cosf and tanf are standard C99 functions, nothing special, they just take and return a float.

Quote:

Don't you get compiler redeclaration errors in the for loops when you declare float tx,ty , rx,ry in each iteration?

No. You do? The variable goes out of scope on each loop iteration.

Edgar Reynaldo
Member #8,592
May 2007
avatar

Quote:

Quote:

Don't you get compiler redeclaration errors in the for loops when you declare float tx,ty , rx,ry in each iteration?

No. You do? The variable goes out of scope on each loop iteration.

Tried a simple test and it works just fine. Silly me.
Why not just declare them once outside the for loop though?

Can anyone explain what the radial_factor (1 - cosf(theta)) represents geometrically?

SiegeLord
Member #7,827
October 2006
avatar

Thanks for the typo corrections... this code shall be part of my ChristMassHack entry, and I'd rather it not to be too incomprehensible... :D

Quote:

Why not just declare them once outside the for loop though?

I believe that that is just a style preference.

Anyway, here is a geometric explanation of my algorithm.

http://www.allegro.cc/files/attachment/593978

In this diagram we start on point A. We know the location of point O (it is one of our function parameters) and we know the length OA. We also know theta, since it simply equals the angular size of the circle or arc we wish to draw divided by the number of segments.

So, as per our algorithm we first move tangentially to point K and then move radially to point B - which is the second point on our circle and would be connected to A by some sort of a line, OpenGL or otherwise. Now, since we know OA and we know theta we can calculate the magnitude of KA quite easily.
It is:

<math>\frac{KA}{OA} = tan(\theta)</math>

or:

<math>KA = OA tan(\theta)</math>

So our tangential factor is known. And amusing property of this factor is that it is negative when theta is negative, which allows for negative angular lengths for arcs. Now, what is the direction of KA? It is simply the normal vector to OA. We just exchange the components of the radius and negativize one of them. This is where my awkward "float tx = -(y - _y);" comes from. I just wanted to emphasize the fact that that is a normal(tangent) vector.

Thus, to find KA all we do is find the normal of OA and multiply it by the tangential factor.

Now, how to find KB, our radial vector that we move on to get to B? It is important to realize that we know what KO is, since we know where K is from the previous compuation (just add the KA vector to the point A). We also know OA and thus OB. Now, we form two equations:

1) <math>\frac{OA}{KO} = cos(\theta)</math>

which reduces to:

1) <math>OA = KO cos(\theta)</math>

And equation 2:

2) <math>OB + KB = KO</math>

Since OA = OB, we can plug equation 1 into 2 to get:

<math>KO cos(\theta) + KB = KO</math>

Simplifying that we get:

<math>KB = KO (1 - cos(\theta))</math>

So, our radial factor is 1 - cos(theta).

Thus, to get KB we would simply find the vector KO from K and O and then multiply it by our factor.

If we add that vector to K we will get the point B. Repeat that however number of times and you will get a number of equally spaced points on the circle. As you can see we only needed to precalculate the two factors. Everything else is determined iteratively in the main loop itself.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Go to: