Loading ...
Sorry, an error occurred while loading the content.

Re: [Frink] A Fun Application of Interval Arithmetic

Expand Messages
  • Alan Eliasen
    ... 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
    • 0 Attachment
      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
      > workload.

      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
    • Marcus Downing
      ... 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 2 of 7 , Jun 13, 2005
      View Source
      • 0 Attachment
        > 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...
      • Alan Eliasen
        ... 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 3 of 7 , Jun 15, 2005
        View Source
        • 0 Attachment
          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
        • Marcus Downing
          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 4 of 7 , Jun 15, 2005
          View Source
          • 0 Attachment
            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.
          • Marcus Downing
            ... 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 5 of 7 , Jun 21, 2005
            View Source
            • 0 Attachment
              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.