Browse Groups

• ## Re: [Frink] A Fun Application of Interval Arithmetic

(7)
• NextPrevious
• ... It looks like I m not alone. A web search shows that the tool GraphEQ apparently uses interval arithmetic to plot its graphs:
Message 1 of 7 , Jun 12, 2005
View Source
Marcus Downing wrote:

> That is pretty impressive. Technically, it's what a graph is - a locus
> of all positions - but no other graphing thing i know does it that
> straightforwardly.

It looks like I'm not alone. A web search shows that the tool
GraphEQ apparently uses interval arithmetic to plot its graphs:

http://www.peda.com/grafeq/spec/precise.html

> They all use tricks of tracing to lessen their

These tricks can often fail... GraphEQ has a "Rogue's Gallery" of
troublesome graphs: http://www.peda.com/grafeq/gallery/rogue.html

I tried a couple of these in Mathematica and it failed
miserably--completely missing asymptotes, etc. And I don't know how to
make Mathematica plot things like solid circles. But my simple graphing
sample has some trouble with a few of these too. It would obviously
benefit from successive refinement of points. It often plots "broader"
curves than it should.

At some point, I'll probably need to define and handle the unbounded
intervals [0, +infinity] and [-infinity, 0]. Sigh.

> I imagine it's fairly processor intensive if you do it per
> pixel, but that should be alleviated when you subdivide the screen
> level by level.

When you use larger intervals, they tend to "spread out" the results.
The results of doing calculations with bigger intervals may falsely
overlap, so the finer intervals you use, the better. Recursive
subdivision would certainly help this out. You can see the effects of
this by zooming in on a part of a graph with my graphing application:

http://futureboy.homeip.net/fsp/simplegraph.fsp

Whew... I thought I was failing completely at some of the graphs, but
you see the same effects of graph-blurring because of using bigger
pixels here:

http://www.peda.com/grafeq/spec/successive_refinement.html

> I now have visions of antialiasing the line based on sub-pixel
> subdivisions... not quite sure how it would work... :)

Hmmm... as shown in the GraphEQ link above, a nice feature of this
graphing method is that the graphs can be made "precise." A pixel is
only lit if the curve really does go through that point. However, when
you're printing at the full resolution of a laser printer, that's
probably too fine of a line. And modern graphical environments (say,
Java's graphics libraries) don't really even want you to address pixels
directly. You draw filled rectangles of a certain size or lines of a
given width.

I think you could do simple anti-aliasing by seeing how much of the
intervals on each side of the equation overlap. If they overlap only
10%, (of, say, the larger interval) then plot the point as 10% gray.
Sound reasonable?

I guess that means I need to write intersection and width functions now.

--
Alan Eliasen | "It is not enough to do your best;
eliasen@... | you must know what to do and THEN
http://futureboy.homeip.net/ | do your best." -- W. Edwards Deming
• ... I always seem to be the one making more work for you... ... Rather than targetting pixels, is there any way you could target something like postscript?
Message 1 of 7 , Jun 13, 2005
View Source
> At some point, I'll probably need to define and handle the unbounded
> intervals [0, +infinity] and [-infinity, 0]. Sigh.

> I guess that means I need to write intersection and width functions now.

I always seem to be the one making more work for you...

> A pixel is only lit if the curve really does go through that point.
> However, when you're printing at the full resolution of a laser printer,
> that's probably too fine of a line. And modern graphical environments
> (say, Java's graphics libraries) don't really even want you to address pixels
> directly. You draw filled rectangles of a certain size or lines of a
> given width.

Rather than targetting pixels, is there any way you could target
something like postscript? define it in terms of beziers passing
through point after point... i suppose you'd still need to have a base
resolution at which you calculated, even if that resolution was higher
or lower than the screen resolution.

What i'm thinking of is OS X's way of doing graphics, which is where
each window produces on demand an EPS description of its contents, and
then these can be interpreted by the OS at any resolution it wants.
It's not really used heavily yet, but there are hints that in time
they're going to start making the scale of the whole UI variable.

But now my brain has started to wonder about shortcuts in the
"mathematical description of curve -> pixels -> mathematical
description of curve" pipeline...
• ... I d certainly like to implement Frink s graphic libraries as rendering lines, rectangles, and curves instead of pixels. That way it s directly scalable,
Message 1 of 7 , Jun 15, 2005
View Source
Alan Eliasen wrote:
>>A pixel is only lit if the curve really does go through that point.
>>However, when you're printing at the full resolution of a laser printer,
>>that's probably too fine of a line. And modern graphical environments
>>(say, Java's graphics libraries) don't really even want you to address pixels
>>directly. You draw filled rectangles of a certain size or lines of a
>>given width.

Marcus Downing wrote:
> Rather than targetting pixels, is there any way you could target
> something like postscript? define it in terms of beziers passing
> through point after point...

I'd certainly like to implement Frink's graphic libraries as
rendering lines, rectangles, and curves instead of pixels. That way
it's directly scalable, and you don't have to re-calculate the graphics
again for different device resolutions or resizing windows. A
side-benefit is that that's the way Java's graphics libraries for
drawing to the screen or a printer work, too. My graphics library may
be a thin layer on top of Java's primitives, but I've also considered
making it quite a bit more complex with transformations and scaling,
etc. Java 1.2 and later essentially have everything I want--but I try
to target Java 1.1. Sigh.

I was thinking of how to apply the interval graphing algorithm to
bezier curves, but its nature that I wrote about yesterday makes it
difficult to know which point is "next to" the others. See again the
graph at:

http://www.peda.com/grafeq/spec/precise.html

and try to figure out how you'd draw the curves through the
calculated pixels without making them artificially wiggly...

By the way, I just noticed that my simple grapher web page had a bug
(I forgot to put <BR> tags at the end of each line) so if your browser
window was wide enough, it would put rows of the plot side-by-side. If
you looked at it, and it didn't make sense, try it again:

http://futureboy.us/fsp/simplegraph.fsp

By the way, I've been getting lots of good help from the luminaries
in the interval arithmetic field, like Bill Walster (who developed the
interval libraries for Sun's Fortran and C++ products.) There's an
interesting mailing list if you're interested in such things:

http://interval.louisiana.edu/reliable_computing.txt

--
Alan Eliasen | "It is not enough to do your best;
eliasen@... | you must know what to do and THEN
http://futureboy.homeip.net/ | do your best." -- W. Edwards Deming
• I ve no idea if this would work, but i m going to try thinking on paper about how to make a curved graph from a set of interval-calculated pixels. Each pixel,
Message 1 of 7 , Jun 15, 2005
View Source
I've no idea if this would work, but i'm going to try thinking on
paper about how to make a curved graph from a set of
interval-calculated pixels.

Each pixel, say (217, 19), actually represents an interval ([217,
218], [19, 20]). In the current scheme, if there is any point within
that interval for which the conditions hold true, then the pixel is
lit. However, the pixel is actually a representation of an infinite
number of points, some or all of which may happen to match the
criteria. In fact, there are several options for how this locus may
manifest itself within a pixel:
- one or more individual points
- one or more infinitessimally-thin lines
- one or more continuous areas
- the whole pixel

If we consider the most common mathematical case of a single line, you
have within each lit pixel a subset (both infinite and infinitessimal)
of points which match the criteria. FIND ONE. Start by recursively
dividing the pixel horizontally, and working outwards from the centre,
until you have determined an x-value which is on the locus
(approximately, to maybe 0.01 pixels precision). With a similar
technique on that thin slice, find a y-value for it which is true (to
a similar level).

You then have a series of points, one for each pixel, but each to much
higher than pixel accuracy. These can be joined together to form a
smooth curve (in the form of a series of 1-pixel long lines). This can
be rendered on screen to produce a beautifully anti-aliased curve, or
sent to a higher-resolution device like a printer, where the curve
will be slightly jerky if you look closer than 1/72 inch, but still a
lot smoother than the set of pixels.

Would that work? I don't see why not. Can it be expanded to cover the
non-line cases without blatant errors (like connecting unconnecting
points)? I think so. Would it be prohibitively expensive? Probably.
• ... I ve done some finger-math, and i reckon that for a decent 0.01 pixel accuracy - suitable for a printer, overkill for antialiasing - it ll be about 20
Message 1 of 7 , Jun 21, 2005
View Source
Myself said:

> ,..
> Would that work? I don't see why not. Can it be expanded to cover the
> non-line cases without blatant errors (like connecting unconnecting
> points)? I think so. Would it be prohibitively expensive? Probably.

I've done some finger-math, and i reckon that for a decent 0.01 pixel
accuracy - suitable for a printer, overkill for antialiasing - it'll
be about 20 times as expensive for each lit pixel. Assuming 1% of
pixels in a given graph are lit, that means this could be a
surprisingly reasonable way to produce smooth-looking curves from
interval arithmetic.
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.