Re: RFC: wideline algorithm

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 05/29/04

  • Next message: q_at_q.com: "Re: The Year 2038 Problem" 
    Date: Sat, 29 May 2004 14:49:57 -0400 (EDT)

    [removed c.s.w from crosspost for this branch of thread]

    On Sat, 29 May 2004, Ben Pfaff wrote:
    >
    > "Arthur J. O'Dwyer" <ajo@nospam.andrew.cmu.edu> writes:
    > > I have here a naive algorithm for drawing "wide lines,"
    > > a.k.a. "fat lines," "thick lines," and probably some other
    > > adjectives that I haven't thought to Google yet. It seems
    > > to work, but it is not perfect: it is rather clunky, it
    > > is not XOR-safe (it writes over some pixels more than
    > > once per line), and it does not generalize to non-integer
    > > line thicknesses.
    >
    > Have you considered using an algorithm for drawing convex
    > polygons? A thick line is just a rectangle whose edges are not
    > necessarily parallel to the x and y axes, so polygon algorithms
    > are entirely appropriate.

      [I think this is what Ian was suggesting, too, but I'm not
    entirely sure. Ian, did you mean something else, and if so,
    what?]

      Yes, I considered writing a full-fledged convex-polygon drawing
    routine (and I eventually will have to write one anyway). But
    I couldn't figure out how to efficiently apply the one to the other
    problem. Sure, a thickline is just a rectangle, but how do I go
    from the thickline parameters

        rectangle ABCD with AB = CD = 'thickness',
                            midpoint of AB = '(x1, y1)',
                            midpoint of CD = '(x2, y2)',

    to the polygon parameters

        rectangle ABCD with A=(a,b), B=(c,d), C=(e,f), D=(g,h)

    without using trigonometric functions?

      Here's the application, since I suppose in this branch it's
    quite relevant: A "roguelike" game's dungeon generator. The
    dungeon is composed of tiles which are [simplistically] either
    "WALL" or "FLOOR". I want to draw an "alleyway" going from
    point A to point B, with a specified "width."

      Antialiasing is irrelevant, because you can't have a tile
    that's "fifty percent WALL".

      I'd like to avoid floating-point math entirely, since that's
    a traditional goal of roguelike programming (helps portability).
    That's why I said "without trigonometric functions" above: I
    know how to get from one to the other using sin() and cos(),
    I just don't want to. :) And if Bresenham's algorithm can do
    straight lines without FP, I don't see why thicklines should
    be intrinsically impossible!

    HTH,
    -Arthur

  • Next message: q_at_q.com: "Re: The Year 2038 Problem"