alexp
/
l3lib
1
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
You cannot select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
main
Branches Tags
${ item.name }
Create tag ${ searchTerm }
Create branch ${ searchTerm }
from 'main'
${ noResults }
l3lib/devel/trash/circle_draw.shtml

338 lines
20 KiB
Plaintext
Raw Permalink Blame History

<!DOCTYPE shtml PUBLIC "-//W3C//DTD shtml 4.01 Transitional//EN" "http://www.w3.org/TR/shtml4/loose.dtd">
<html><head>
<title>An Efficient Way to Draw Approximate Circles in OpenGL - SiegeLord's Abode</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<link rel="stylesheet" type="text/css" href="circle_draw-Dateien/style.css">
<link rel="SHORTCUT ICON" href="http://slabode.exofire.net/images/sl.ico">
</head><body>
<div class="button_how_pre"></div><div class="button_up_how_pre"></div><div class="button_back_how_pre"></div><div class="button_home_how_pre"></div>
<p class="title_image"><img src="circle_draw-Dateien/title_computer.jpg"></p>
<hr color="#6699ff">
<div class="link_bar">
<a class="link_bar" href="http://slabode.exofire.net/index.shtml">Home</a>
<a class="link_bar" href="http://slabode.exofire.net/progress_reports.shtml">Progress</a>
<a class="link_bar" href="http://slabode.exofire.net/computer_programming.shtml">Computers</a>
<a class="link_bar" href="http://slabode.exofire.net/various_art.shtml">Various Art</a>
<a class="link_bar" href="http://slabode.exofire.net/building.shtml">Building</a>
<a class="link_bar" href="http://slabode.exofire.net/about.shtml">About</a>
</div>
<hr color="#6699ff">
<h1>An Efficient Way to Draw Approximate Circles in OpenGL</h1>
<br>
<h2>Introduction</h2>
<p>OpenGL is well known to not posses any
method to rasterize non-straight curves. As such, whenever one is
required to draw a curve, one has to either rasterize it himself
(through GL_POINTS) which is slow, or approximate it using a number
of line segments by drawing a many sided regular polygon. The latter method shall be explored here for
drawing circles.
</p>
<p>It is a well known fact that a regular
polygon with a large number of sides looks approximately like a
circle when rasterized on the screen. As such, when given a challenge
to draw a circle in OpenGL, people generally come up with something
like this:
</p>
<hr color="#6699ff">
<p class="code">
</p><pre><span class="type">void</span> DrawCircle<span class="operator">(</span><span class="type">float</span> cx<span class="operator">,</span><span class="type"> float</span> cy<span class="operator">,</span><span class="type"> float</span> r<span class="operator">,</span><span class="type"> int</span> num_segments<span class="operator">)
{</span>
glBegin<span class="operator">(</span>GL_LINE_LOOP<span class="operator">);</span><span class="flow">
for</span><span class="operator">(</span><span class="type">int</span> ii<span class="operator"> =</span><span class="int"> 0</span><span class="operator">;</span> ii<span class="operator"> &lt;</span> num_segments<span class="operator">;</span> ii<span class="operator">++)
{</span><span class="type">
float</span> theta<span class="operator"> =</span><span class="float"> 2.0f</span><span class="operator"> *</span><span class="float"> 3.1415926f</span><span class="operator"> *</span><span class="type"> float</span><span class="operator">(</span>ii<span class="operator">) /</span><span class="type"> float</span><span class="operator">(</span>num_segments<span class="operator">);</span><span class="comment">//get the current angle
</span><span class="type"> float</span> x<span class="operator"> =</span> r<span class="operator"> *</span> cosf<span class="operator">(</span>theta<span class="operator">);</span><span class="comment">//calculate the x component
</span><span class="type"> float</span> y<span class="operator"> =</span> r<span class="operator"> *</span> sinf<span class="operator">(</span>theta<span class="operator">);</span><span class="comment">//calculate the y component
</span> glVertex2f<span class="operator">(</span>x<span class="operator"> +</span> cx<span class="operator">,</span> y<span class="operator"> +</span> cy<span class="operator">);</span><span class="comment">//output vertex
</span><span class="operator"> }</span>
glEnd<span class="operator">();
}</span>
</pre>
<p></p>
<hr color="#6699ff">
<p>There are some simple optimizations
that one can do, but nonetheless the general algorithm is as stated.
This is very bad algorithm however, since for every point we have to
perform expensive calls to the trigonometric functions. I propose a
method that requires only the basic arithmetic operations for every
point to obtain the same result.
</p>
<h2>The Algorithm</h2>
<p>The inspiration came to me from
physics. As we know, when an object moves in a circle it does so
entirely because of a constant centripetal acceleration acting on it.
When this is the case the object moves at a constant radial speed.
Note that that means that we have two constant length terms (radial
speed and centripetal acceleration) which only change direction, but
not length. Since direction is easy to compute, it is just a vector,
we are in business.
</p>
<p class="title_image"><img src="circle_draw-Dateien/circle_diag.png"></p>
<p>Here is the general motion of the point
whose position we use to calculate the position of the vertices of
our circle. During each calculation, we move the point tangentially
to the circle for a fixed distance (segments AK and BL) and then back
towards the centre of the circle for a fixed distance (segments KB
and LC). At this point we store the location of our point (perhaps
through a call to glVertex) and then repeat the process. Our problem,
thus, is to calculate the magnitude of the tangential motion, the
direction of the tangential motion, the magnitude of the radial
motion and the direction of the radial motion.
</p>
<p>We are helped in this task by the
following vectors that we know. At the beginning of our calculation
we know the vector AO. We can easily turn this vector 90 degrees so
it becomes tangent to the circle by flipping the coordinates, while
negating one of them. Now, we have a vector that is tangent to the
circle, but still the length of the radius. To make be the length of
AK, we multiply it by a factor, which is simply the tangent of the
theta. This factor is the same for every calculation, so it can be
precalculated before entering the loop.
</p>
<p>Now, we add the tangential vector to
the vector AO and get the vector KO. We need to get the vector BO
from that. Again, we can simply multiply it by a factor which turns
out to be the cosine of theta. Again, this factor is constant and can
be precalculated. At this point we are back where we started, so we
can just repeat this process again, and continue to do so until we
fill the entire circle. Thus, here is the code for this
implementation:
</p>
<hr color="#6699ff">
<p class="code">
</p><pre><span class="type">void</span> DrawCircle<span class="operator">(</span><span class="type">float</span> cx<span class="operator">,</span><span class="type"> float</span> cy<span class="operator">,</span><span class="type"> float</span> r<span class="operator">,</span><span class="type"> int</span> num_segments<span class="operator">)
{</span><span class="type">
float</span> theta<span class="operator"> =</span><span class="int"> 2</span><span class="operator"> *</span><span class="float"> 3.1415926</span><span class="operator"> /</span><span class="type"> float</span><span class="operator">(</span>num_segments<span class="operator">);</span><span class="type">
float</span> tangetial_factor<span class="operator"> =</span> tanf<span class="operator">(</span>theta<span class="operator">);</span><span class="comment">//calculate the tangential factor
</span><span class="type"> float</span> radial_factor<span class="operator"> =</span> cosf<span class="operator">(</span>theta<span class="operator">);</span><span class="comment">//calculate the radial factor
</span><span class="type">
float</span> x<span class="operator"> =</span> r<span class="operator">;</span><span class="comment">//we start at angle = 0
</span><span class="type"> float</span> y<span class="operator"> =</span><span class="int"> 0</span><span class="operator">;</span>
glBegin<span class="operator">(</span>GL_LINE_LOOP<span class="operator">);</span><span class="flow">
for</span><span class="operator">(</span><span class="type">int</span> ii<span class="operator"> =</span><span class="int"> 0</span><span class="operator">;</span> ii<span class="operator"> &lt;</span> num_segments<span class="operator">;</span> ii<span class="operator">++)
{</span>
glVertex2f<span class="operator">(</span>x<span class="operator"> +</span> cx<span class="operator">,</span> y<span class="operator"> +</span> cy<span class="operator">);</span><span class="comment">//output vertex
//calculate the tangential vector
//remember, the radial vector is (x, y)
//to get the tangential vector we flip those coordinates and negate one of them
</span><span class="type"> float</span> tx<span class="operator"> = -</span>y<span class="operator">;</span><span class="type">
float</span> ty<span class="operator"> =</span> x<span class="operator">;</span><span class="comment">
//add the tangential vector
</span> x<span class="operator"> +=</span> tx<span class="operator"> *</span> tangetial_factor<span class="operator">;</span>
y<span class="operator"> +=</span> ty<span class="operator"> *</span> tangetial_factor<span class="operator">;</span><span class="comment">
//correct using the radial factor
</span> x<span class="operator"> *=</span> radial_factor<span class="operator">;</span>
y<span class="operator"> *=</span> radial_factor<span class="operator">;
}</span>
glEnd<span class="operator">();
}</span></pre>
<p></p>
<hr color="#6699ff">
The algorithm can be modified to draw arcs instead of circles. We first calculate the starting point from the starting angle.
Then we calculate the theta parameter based not on the full circle as before, but rather the angular span of the arc.
<br>
Here is one way to do it:
<hr color="#6699ff">
<p class="code">
</p><pre><span class="type">void</span> DrawArc<span class="operator">(</span><span class="type">float</span> cx<span class="operator">,</span><span class="type"> float</span> cy<span class="operator">,</span><span class="type"> float</span> r<span class="operator">,</span><span class="type"> float</span> start_angle<span class="operator">,</span><span class="type"> float</span> arc_angle<span class="operator">,</span><span class="type"> int</span> num_segments<span class="operator">)
{</span><span class="type">
float</span> theta<span class="operator"> =</span> arc_angle<span class="operator"> /</span><span class="type"> float</span><span class="operator">(</span>num_segments<span class="operator"> -</span><span class="int"> 1</span><span class="operator">);</span><span class="comment">//theta is now calculated from the arc angle instead, the - 1 bit comes from the fact that the arc is open
</span><span class="type"> float</span> tangetial_factor<span class="operator"> =</span> tanf<span class="operator">(</span>theta<span class="operator">);</span><span class="type">
float</span> radial_factor<span class="operator"> =</span> cosf<span class="operator">(</span>theta<span class="operator">);</span><span class="type">
float</span> x<span class="operator"> =</span> r<span class="operator"> *</span> cosf<span class="operator">(</span>start_angle<span class="operator">);</span><span class="comment">//we now start at the start angle
</span><span class="type"> float</span> y<span class="operator"> =</span> r<span class="operator"> *</span> sinf<span class="operator">(</span>start_angle<span class="operator">);</span>
glBegin<span class="operator">(</span>GL_LINE_STRIP<span class="operator">);</span><span class="comment">//since the arc is not a closed curve, this is a strip now
</span><span class="flow"> for</span><span class="operator">(</span><span class="type">int</span> ii<span class="operator"> =</span><span class="int"> 0</span><span class="operator">;</span> ii<span class="operator"> &lt;</span> num_segments<span class="operator">;</span> ii<span class="operator">++)
{</span>
glVertex2f<span class="operator">(</span>x<span class="operator"> +</span> cx<span class="operator">,</span> y<span class="operator"> +</span> cy<span class="operator">);</span><span class="type">
float</span> tx<span class="operator"> = -</span>y<span class="operator">;</span><span class="type">
float</span> ty<span class="operator"> =</span> x<span class="operator">;</span>
x<span class="operator"> +=</span> tx<span class="operator"> *</span> tangetial_factor<span class="operator">;</span>
y<span class="operator"> +=</span> ty<span class="operator"> *</span> tangetial_factor<span class="operator">;</span>
x<span class="operator"> *=</span> radial_factor<span class="operator">;</span>
y<span class="operator"> *=</span> radial_factor<span class="operator">;
}</span>
glEnd<span class="operator">();
}</span></pre>
<p></p>
<hr color="#6699ff">
<h2>Other Considerations</h2>
<p></p>
<p>Both this and the other algorithms can
be greately sped up by using a vertex array, that is then passed as
an argument to the glDrawArrays, I leave it up to the reader to
implement this trivial optimisation.
</p>
<p>You will note that to draw the circle
you need to pass the number of segments to draw. Is it possible to
create a function to give a good estimate of that number so that you
get a reasonably smooth circle? Yes there is. One way to do this is
to limit to the magnitude of the KB segment in the diagram above. The
length of that segment is easily derived to be:
</p>
<hr color="#6699ff">
<p class="code">
</p><pre><span class="operator">(</span><span class="int">1</span><span class="operator"> -</span> cos<span class="operator">(</span>theta<span class="operator">)) *</span> r</pre>
<p></p>
<hr color="#6699ff">
<p>We set that to some small value and
solve for theta. I find that setting it to 0.25 (i.e. a quarter of a
pixel) generally produces acceptable results. You can vary that
number as appropriate. The actual formula that you get involves inverse trigonometric functions,
but I found that the following approximation matches their prediction quite well:
</p>
<hr color="#6699ff">
<p class="code">
</p><pre><span class="type">int</span> GetNumCircleSegments<span class="operator">(</span><span class="type">float</span> r<span class="operator">)
{</span><span class="flow">
return</span><span class="int"> 10</span><span class="operator"> *</span> sqrtf<span class="operator">(</span>r<span class="operator">);</span><span class="comment">//change the 10 to a smaller/bigger number as needed
</span><span class="operator">}</span></pre>
<p></p>
<hr color="#6699ff">
<p>Lastly, this code can be adapted to
draw ellipses as well. Simply
scale the x and y variables by appropriate factors, either using a
matrix, or perhaps by modifying the algorithm itself. This extension is
trivial.
</p>
<h2>Conclusion</h2>
<p></p>
<p>This algorithm is significantly faster
than any other circle approximation algorithm I have personally
encountered on the web. I believe that if one chooses to draw a
circle using OpenGL and using a polygonal approximation then my
method is optimal. In theory, with a large number of segments the
true circle, i.e. compatible with the diamond-exit specification, can
be drawn, although at that point it may be preferable to rasterize
the circle using GL_POINTS manually.
</p>
<h2>Recasting the Algorithm as a Repeated Rotation</h2>
<p>
Someone suggested to me that this algorithm can be recast as a simple repeated rotation.
That is indeed correct. All you have to do is multiply the whole algorithm by a few trig functions,
and obtain something that just looks like the repeated application of the rotation matrix. I leave it
as the excersize to the reader to see how you can transform the above algorithm into this one:
</p>
<p class="code">
</p><pre><span class="type">void</span> DrawCircle<span class="operator">(</span><span class="type">float</span> cx<span class="operator">,</span><span class="type"> float</span> cy<span class="operator">,</span><span class="type"> float</span> r<span class="operator">,</span><span class="type"> int</span> num_segments<span class="operator">)
{</span><span class="type">
float</span> theta<span class="operator"> =</span><span class="int"> 2</span><span class="operator"> *</span><span class="float"> 3.1415926</span><span class="operator"> /</span><span class="type"> float</span><span class="operator">(</span>num_segments<span class="operator">);</span><span class="type">
float</span> c<span class="operator"> =</span> cosf<span class="operator">(</span>theta<span class="operator">);</span><span class="comment">//precalculate the sine and cosine
</span><span class="type"> float</span> s<span class="operator"> =</span> sinf<span class="operator">(</span>theta<span class="operator">);</span><span class="type">
float</span> t<span class="operator">;</span><span class="type">
float</span> x<span class="operator"> =</span> r<span class="operator">;</span><span class="comment">//we start at angle = 0
</span><span class="type"> float</span> y<span class="operator"> =</span><span class="int"> 0</span><span class="operator">;</span>
glBegin<span class="operator">(</span>GL_LINE_LOOP<span class="operator">);</span><span class="flow">
for</span><span class="operator">(</span><span class="type">int</span> ii<span class="operator"> =</span><span class="int"> 0</span><span class="operator">;</span> ii<span class="operator"> &lt;</span> num_segments<span class="operator">;</span> ii<span class="operator">++)
{</span>
glVertex2f<span class="operator">(</span>x<span class="operator"> +</span> cx<span class="operator">,</span> y<span class="operator"> +</span> cy<span class="operator">);</span><span class="comment">//output vertex
//apply the rotation matrix
</span> t<span class="operator"> =</span> x<span class="operator">;</span>
x<span class="operator"> =</span> c<span class="operator"> *</span> x<span class="operator"> -</span> s<span class="operator"> *</span> y<span class="operator">;</span>
y<span class="operator"> =</span> s<span class="operator"> *</span> t<span class="operator"> +</span> c<span class="operator"> *</span> y<span class="operator">;
}</span>
glEnd<span class="operator">();
}</span></pre>
<p></p>
<p>
The advantages of this version of the algorithm is that it is easier to understand
(repeated rotation instead of the physics inspired mumbo jumbo) and at a glance it seems to be
a little more numerically stable. I use this version in my current projects, but in principle its your
choice which one you like more.
</p>
<p>This code is released as public domain,
but I will appreciate an email if you do use it somewhere. Feel free
to email me for clarifications of the algorithm and to report bugs
and whatnot.</p>
<br>
<hr color="#6699ff">
<div class="bottom_bar">
<a class="back_button" href="http://slabode.exofire.net/computer_programming.shtml"></a>
<a class="home_button" href="http://slabode.exofire.net/index.shtml"></a>
<a class="up_button" href="#"></a>
</div>
<hr color="#6699ff">
<p class="copy_note">Original content Copyright SiegeLord's Abode 2006-2009. All rights reserved.
&nbsp;
<a href="http://my.statcounter.com/project/standard/stats.php?project_id=4033591&amp;guest=1">♫</a>
<!-- Start of StatCounter Code -->
<script type="text/javascript">
var sc_project=4033591;
var sc_invisible=1;
var sc_partition=31;
var sc_click_stat=1;
var sc_security="c1dd1a20";
var sc_text=1;
</script>
<script type="text/javascript" src="circle_draw-Dateien/counter.js"></script><noscript><div
class="statcounter"><a title="web analytics"
href="http://www.statcounter.com/" target="_blank"><img
class="statcounter"
src="http://c.statcounter.com/4033591/0/c1dd1a20/1/" alt="web
analytics" ></a></div></noscript>
<!-- End of StatCounter Code -->
</p>
</body></html>
Reference in New Issue View Git Blame Copy Permalink