Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Rasterising 2D Transformations of Circles/Ellipses
32 views
Skip to first unread message
JS
Apr 19, 2012, 7:09:42 AM4/19/12
to
Hi,
I am currently looking at a number of 2D graphics algorithms in order to
create my own rudimentary 2D drawing system as a learning exercise. One
of my goals is to be able to transform any primitive by any arbitrary
affine transform and have it render correctly. For most primitives this
will be rather an easy task, however I am having some difficulty with
regard to the best way to transform circles, ellipses, and their
respective arcs.
For filled circles/ellipses I presume standard scan-line techniques
would be used, however reverse transforming the current scan-line prior
to solving intersection with the circle like as is done in ray tracing.
This technique however introduces complexity with the requirement that a
scan line now be represented as a line, instead of simply just a y value.
For stroked circles/ellipses, I believe most algorithms rely on the
adjacency between pixels etc to render them correctly. Applying any
transforms will effectively destroy all their screen space assumptions.
I don't even want to consider arcs yet.
Can anyone point me toward some standard way of transforming
spheres/ellipses such that scan-line and circle/ellipse stroking
algorithms will work correctly?
Regards,
Joel.
I am currently looking at a number of 2D graphics algorithms in order to
create my own rudimentary 2D drawing system as a learning exercise. One
of my goals is to be able to transform any primitive by any arbitrary
affine transform and have it render correctly. For most primitives this
will be rather an easy task, however I am having some difficulty with
regard to the best way to transform circles, ellipses, and their
respective arcs.
For filled circles/ellipses I presume standard scan-line techniques
would be used, however reverse transforming the current scan-line prior
to solving intersection with the circle like as is done in ray tracing.
This technique however introduces complexity with the requirement that a
scan line now be represented as a line, instead of simply just a y value.
For stroked circles/ellipses, I believe most algorithms rely on the
adjacency between pixels etc to render them correctly. Applying any
transforms will effectively destroy all their screen space assumptions.
I don't even want to consider arcs yet.
Can anyone point me toward some standard way of transforming
spheres/ellipses such that scan-line and circle/ellipse stroking
algorithms will work correctly?
Regards,
Joel.
ma...@smartfills.com
Apr 23, 2012, 9:05:47 PM4/23/12
to
четверг, 19 апреля 2012 г., 23:09:42 UTC+12 пользователь JS написал:
I do not see, what d'you mean. You may want to transform a raster image- in this case thee is no need in algorithms, specific for arcs, ellipses etc. or you have set of vector objects- in this case you need transform them as a functions and then redraw new set of objects.
JS
Apr 26, 2012, 11:53:27 PM4/26/12
to
> I do not see, what d'you mean. You may want to transform a raster image- in this case thee is no need in algorithms, specific for arcs, ellipses etc. or you have set of vector objects- in this case you need transform them as a functions and then redraw new set of objects.
general ellipses using only a standard circle drawing algorithm and
affine transformations, or whether it is necessary to assume that a
general ellipse is being drawn 100% of the time with a circle becoming
simply a form of general ellipse where the length of both axes are equal.
Does that make sense?
Joel.
ma...@smartfills.com
Apr 27, 2012, 6:19:22 AM4/27/12
to
пятница, 27 апреля 2012 г., 15:53:27 UTC+12 пользователь JS написал:
Which algorithm of drawing circles is "standard"? One possible way is to call function of WinAPI. This one is named "Ellipse". Unfortunately, it doesn't support all of affine transformation, only subset of it. But you may write your own method, based on Bezier curves. To draw an ellipse within a screen with large resolution like 1920 x 1280 one needs only 12 control points. To apply affine transform to a circle ( to ellipse, or to elliptic arc, no matter) all what you need is to transform coordinates of control points of a Bezier curve. After it the whole Bezier curve will be transformed automatically. Therefore, you need to write procedure that computes Bezier curve, approximating circle (ellipse, arc) and draws it.
JS
Apr 27, 2012, 6:40:39 PM4/27/12
to
independent drawing system as a learning exercise. I will be
implementing the circle/ellipse drawing functionality myself, from
algorithms presented in journal papers, not using any other API.
I am not interested in an approximation based on Bezier curves.
Nobody
Apr 27, 2012, 8:32:35 PM4/27/12
to
On Sat, 28 Apr 2012 08:40:39 +1000, JS wrote:
> I am not interested in an approximation based on Bezier curves.
Note that rational Bezier curves (i.e. <x/w,y/w> where x, y and w are
> I am not interested in an approximation based on Bezier curves.
quadratic or higher functions) can describe an ellipse exactly.
ma...@smartfills.com
Apr 28, 2012, 5:25:37 AM4/28/12
to
суббота, 28 апреля 2012 г., 12:32:35 UTC+12 пользователь Nobody написал:
Not true. They cannot describe even a circle exactly. Bezier curve is a couple of polynoms. There are no such polynoms, whose squares been added give a constant (X=a0+a1*t+a2*t^2+a3*t^3, Y=b0+b1*t+b2*t^2+b3*t^3). X^2+Y^2 cannot be equal to constant, except trivial event. But Bezier curves can describe an elliptic arc very precisely using small number of control points.
Dr J R Stockton
Apr 28, 2012, 2:18:13 PM4/28/12
to
In comp.graphics.algorithms message <4f9b2062$0$11092$c3e...@news.astra
web.com>, Sat, 28 Apr 2012 08:40:39, JS <ju...@sixtytonangel.com> posted:
>I'm sorry, I've not made myself clear. I am implementing my own
>platform independent drawing system as a learning exercise. I will be
>implementing the circle/ellipse drawing functionality myself, from
>algorithms presented in journal papers, not using any other API.
Win XP sp3, Firefox 12, P4/3GHz : I can draw a spiral of 200,000 lineTo
segments on an HTML canvas element with JavaScript in about two seconds.
<http://www.merlyn.demon.co.uk/js-grphx.htm>, with J increased from 1139
in one of the first lines that need scrolling to be seen in the white
area in the "Sample Code" section, then press "ReadText". Note "Wipe".
For practical purposes, the simple brute force approach may well serve
until something better is found.
--
(c) John Stockton, nr London UK ?@merlyn.demon.co.uk IE8 FF8 Op11 Sf5 Cr15
news:comp.lang.javascript FAQ <http://www.jibbering.com/faq/index.html>.
<http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
web.com>, Sat, 28 Apr 2012 08:40:39, JS <ju...@sixtytonangel.com> posted:
>I'm sorry, I've not made myself clear. I am implementing my own
>platform independent drawing system as a learning exercise. I will be
>implementing the circle/ellipse drawing functionality myself, from
>algorithms presented in journal papers, not using any other API.
segments on an HTML canvas element with JavaScript in about two seconds.
<http://www.merlyn.demon.co.uk/js-grphx.htm>, with J increased from 1139
in one of the first lines that need scrolling to be seen in the white
area in the "Sample Code" section, then press "ReadText". Note "Wipe".
For practical purposes, the simple brute force approach may well serve
until something better is found.
--
(c) John Stockton, nr London UK ?@merlyn.demon.co.uk IE8 FF8 Op11 Sf5 Cr15
news:comp.lang.javascript FAQ <http://www.jibbering.com/faq/index.html>.
<http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
Hans-Bernhard Bröker
Apr 29, 2012, 10:07:20 AM4/29/12
to
On 28.04.2012 11:25, ma...@smartfills.com wrote:
> суббота, 28 апреля 2012 г., 12:32:35 UTC+12 пользователь Nobody написал:
>> On Sat, 28 Apr 2012 08:40:39 +1000, JS wrote:
>>
>>> I am not interested in an approximation based on Bezier curves.
>>
>> Note that rational Bezier curves (i.e.<x/w,y/w> where x, y and w are
>> quadratic or higher functions) can describe an ellipse exactly.
>
> Not true.
You're wrong, apparently because you read what you wanted to read,
> суббота, 28 апреля 2012 г., 12:32:35 UTC+12 пользователь Nobody написал:
>> On Sat, 28 Apr 2012 08:40:39 +1000, JS wrote:
>>
>>> I am not interested in an approximation based on Bezier curves.
>>
>> Note that rational Bezier curves (i.e.<x/w,y/w> where x, y and w are
>> quadratic or higher functions) can describe an ellipse exactly.
>
> Not true.
instead of what "JS" actually wrote.
> They cannot describe even a circle exactly. Bezier curve is a couple
> of polynoms.
curves, you've missed JS's point.
Nobody
Apr 29, 2012, 4:13:53 PM4/29/12
to
On Sat, 28 Apr 2012 02:25:37 -0700, mats wrote:
>> > I am not interested in an approximation based on Bezier curves.
>>
>> Note that rational Bezier curves (i.e. <x/w,y/w> where x, y and w are
>> quadratic or higher functions) can describe an ellipse exactly.
>
> Not true. They cannot describe even a circle exactly. Bezier curve is a
> couple of polynoms. There are no such polynoms, whose squares been added
> give a constant (X=a0+a1*t+a2*t^2+a3*t^3, Y=b0+b1*t+b2*t^2+b3*t^3).
> X^2+Y^2 cannot be equal to constant, except trivial event. But Bezier
> curves can describe an elliptic arc very precisely using small number of
> control points.
Read what I actually wrote. A RATIONAL (homogeneous) Bezier curve (where
>> > I am not interested in an approximation based on Bezier curves.
>>
>> Note that rational Bezier curves (i.e. <x/w,y/w> where x, y and w are
>> quadratic or higher functions) can describe an ellipse exactly.
>
> Not true. They cannot describe even a circle exactly. Bezier curve is a
> couple of polynoms. There are no such polynoms, whose squares been added
> give a constant (X=a0+a1*t+a2*t^2+a3*t^3, Y=b0+b1*t+b2*t^2+b3*t^3).
> X^2+Y^2 cannot be equal to constant, except trivial event. But Bezier
> curves can describe an elliptic arc very precisely using small number of
> control points.
each component is the ratio of two polynomials, all components sharing the
same denominator) can describe an ellipse exactly.
E.g. a quadratic curve with homogenous control points:
0:1:1 k:k:k 1:0:1
[where k = 1/sqrt(2)] forms one quadrant of the unit circle.
The curve has the parametric equation:
[x] [1-2k] [2k ] + [0]
[y] = [1-2k].t^2 + [2k-2].t + [1]
[w] [2-2k] [2k-2] + [1]
It's a simple matter to verify that (x/w)^2 + (y/w)^2 = 1.
JS
Apr 29, 2012, 11:04:28 PM4/29/12
to
Thanks guys. I believe I may have found what I was after. There are a
few nice bits of information at the following URL that should have me
pointed in the right direction.
http://www.maa.org/joma/Volume8/Kalman/QuadForm.html
Granted I haven't read the page overly thoroughly yet, on the surface it
looks like it gives me what I need, primarily pointers on:
- a simple 2x2 matrix formulation for origin-centred general ellipses
- how to recognise a circle
- how to recognise an axis-aligned ellipse
- how to recognise a general ellipse
- how to apply a transformation to the 2x2 matrix form
From here it will be a simple matter of relating all this stuff to the
various circle/ellipse drawing algorithms out there and see where I end up.
Thanks.
Joel.
few nice bits of information at the following URL that should have me
pointed in the right direction.
http://www.maa.org/joma/Volume8/Kalman/QuadForm.html
Granted I haven't read the page overly thoroughly yet, on the surface it
looks like it gives me what I need, primarily pointers on:
- a simple 2x2 matrix formulation for origin-centred general ellipses
- how to recognise a circle
- how to recognise an axis-aligned ellipse
- how to recognise a general ellipse
- how to apply a transformation to the 2x2 matrix form
From here it will be a simple matter of relating all this stuff to the
various circle/ellipse drawing algorithms out there and see where I end up.
Thanks.
Joel.
Kaba
Apr 30, 2012, 4:32:52 AM4/30/12
to
with EWA filtering. First, define an ellipsoid as an affine transform of
a unit sphere (I'll use the general terminology, since everything
generalizes to nD).
1) Find the quadratic form matrix of the ellipsoid. The derivation is in
http://kaba.hilvi.org/pastel/pastel/geometry/ellipsoid.hpp.htm
in the upper function.
1) Find a minimal axis-aligned box for the ellipsoid. You can find this
from:
http://kaba.hilvi.org/pastel/pastel/geometry/bounding_alignedbox_sphere.
hpp.htm
The derivation is in
http://kaba.hilvi.org/pastel/pastel/geometry/ellipsoid.hpp.htm
in the lower function.
2) The ellipsoid is given by the 1-sublevel set of the quadratic form. A
quadratic form is a homogeneous 2nd degree polynomial. Therefore you can
compute its value incrementally from pixel to pixel using finite
differences (additions only, it's fast). Now the task is simply to
compute the ellipsoids quadratic form function (incrementally) over the
bounding aligned box pixel by pixel, and draw only those pixels whose
value is less than or equal to 1.
You can see this in action in the bottom of
http://kaba.hilvi.org/pastel/pastel/gfx/ewaimage_texture.hpp.htm
--
http://kaba.hilvi.org
0 new messages