- View SourceMarcus Downing wrote:

> That is pretty impressive. Technically, it's what a graph is - a locus

It looks like I'm not alone. A web search shows that the tool

> of all positions - but no other graphing thing i know does it that

> straightforwardly.

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

> workload.

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

When you use larger intervals, they tend to "spread out" the results.

> pixel, but that should be alleviated when you subdivide the screen

> level by level.

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

Hmmm... as shown in the GraphEQ link above, a nice feature of this

> subdivisions... not quite sure how it would work... :)

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 - View Source
> At some point, I'll probably need to define and handle the unbounded

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

> intervals [0, +infinity] and [-infinity, 0]. Sigh.

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

> A pixel is only lit if the curve really does go through that point.

Rather than targetting pixels, is there any way you could target

> 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.

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... - View SourceAlan Eliasen wrote:
>>A pixel is only lit if the curve really does go through that point.

Marcus Downing wrote:

>>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

I'd certainly like to implement Frink's graphic libraries as

> something like postscript? define it in terms of beziers passing

> through point after point...

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 - View SourceI'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. - View SourceMyself said:

> ,..

I've done some finger-math, and i reckon that for a decent 0.01 pixel

> 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.

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.