epsilon-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[epsilon-devel] Re: Learning to write I/O actions: paint_line


From: Luca Saiu
Subject: [epsilon-devel] Re: Learning to write I/O actions: paint_line
Date: Tue, 25 Nov 2003 16:14:21 +0100
User-agent: Mozilla/5.0 (X11; U; Linux i586; en-US; rv:1.3a) Gecko/20021212

Matteo Golfarini wrote:
Sorry for writing late but, like i told you i can't use the internet on saturday and sunday
  Don't mind.

now i think i can continue
> to implement other primitives of graphics, and if you
want we can start on how we can develop algorithms to solve graph problems
We need other graphic primitives and you are welcome to write them, even if I would prefer them to be written in C (c_libraries/sdl.c), since they would be faster (especially now, since we don't have a real optimizer yet). Alas, the documentation about C libraries is not finished yet; I will send a message to this list as soon as it is ready. For the time an epsilon implementation can do, and can also serve as a prototype; the algorithms to be used in C are essentially the same ones to be used in epsilon.
  I think we need:
* generic polygon, represented by a list of vertices (difficult in the filled version; the non-filled version is quite easy)
  * rectangle (filled and non-filled)
  * triangle (filled and non-filled)
  * circle (filled and non-filled)
  * ellipse (filled and non-filled)
* arc and pie (the most difficult and the least used; probably they aren't worth the trouble) The functions would be named draw_X and fill_X, for every primitive X. draw_polygon and fill_polygon can be used to implement some of the other primitives, if convenient.

However we could finish the implementation of paint_line before; if you are willing, of course. The module you sent the last time was correct, but I have cleaned it up just a bit; please spend a little time reading the comments marked with --positron. The only problem not yet solved (because I intentionally didn't expose the problem to you the first time; it's not your fault) is how to draw a line which has pendence > 45deg or < -45deg; see how the purple line in the attached file appears. The problem is that we are drawing a pixel for every natural value of x; this is correct and efficient when the pendence is little (<= 45deg or >= -45), but not when it's high. For high-pendency segments we should draw one pixel for every natural value of *y*; this also automatically solves the problem of vertical lines, as you will see in a moment. We can represent high-pendency lines as equations x = m y + q. The system of equations is
/ x1 = m y1 + q
\ x2 = m y2 + q
  which has the solution
/ m = (x2 - x1) / (y2 - y1)
\ q = (y2 x1 - y1 x2) / (y2 - y1)
Note that this is perfectly equal to the low-pendency case, exchanging x by y and vice-versa. And note that a vertical line (x1 = x2) can be drawn without problems; an horizontal line (y1 = y2) can't. You can try extending paint_line so that it automatically distinguishes between low-pendency and high-pendency. Note that this can require some remodularization; start from the cleaned file I have attached if you are willing to do this exercise.

If you aren't willing then don't mind, you can start implementing the other primitives using draw_line (it's in the new snapshot).

see you next time ...

the life in spain is going better :)
I'm happy about that. Life in Italy is going like always. Luckily we have epsilon :-).
  Best regards,

--
Luca Saiu, maintainer of GNU epsilon
http://www.gnu.org/software/epsilon
import random;
import simple_graphics;


define loop = fix \ f . \ x . f x ;

/* --positron:
   I added the following two trivial functions: */
define min = \ a . \ b . if a < b then a else b;
define max = \ a . \ b . if a > b then a else b;

/* --positron:
   Types were a bit confused in find_m and find_q; in find_m you (rightly)
   expected some integer parameters, in find_q you expected the same ones
   in the same order, but as floats.  I have changed find_q: */
define find_q = \ x1 . \ y1 . \ x2 . \ y2 .
  (integer_to_float (x2 * y1 - x1 * y2)) /f (integer_to_float (x2 - x1));

/* --positron:
   I have changed the names of the parameters; (x1, y1), (x2, y2) seems more
   understandable than (x, y), (x1, y1). Nothing important. */
define find_m =  \ x1 . \ y1 . \ x2 . \ y2 .
  ((integer_to_float y2) -f (integer_to_float y1)) /f
  ((integer_to_float x2) -f (integer_to_float x1))
;

/* --positron:
   I have removed paint_line_ugly and friends. Note that it was difficult
   to find good names for them; this is often a hint suggesting that the
   code could be made cleaner; note that the complexity of paint_line_ugly2_
   completely disappears if you use the trivial min and max functions.
   It often pays to add some utility functions which seem so simple to be
   unuseful. */

/* --positron:
   This only recurs on x, so it's quite fast. Note the common pattern
   "if CONDITION then skip else begin ... end"; it's the most common
   way to write recursive functions returning actions. */
define paint_line_rec = \ m . \ q . \ max_x . \ c . 
                        fix \ f . \ x . // we recur only on x!
  if x > max_x then
    skip
  else begin
    let y be
      float_to_integer (m *f (integer_to_float x) +f q)
    in
      show_pixel x y c;
    f (x + 1);
  end;

/* --positron:
   I have clarified this and arranged for recurring on a single variable,
   for speed's sake; with the let it's much more redable. */
define paint_line = \ x1 . \ y1 . \ x2 . \ y2 . \ c .
  let m be
    find_m x1 y1 x2 y2
  & q be
    find_q x1 y1 x2 y2
  & min_x be
    min x1 x2
  & max_x be
    max x1 x2
  in
    // min_x is the recursion variable, hence it's the last one:
    paint_line_rec m q max_x c min_x;

/* --positron:
  A trivial driver, just to test: */
define main = begin
  initialize_graphics 640 480;
  paint_line 0 0 50 479 (255, 255, 255);
  paint_line 100 100 639 470 (255, 0, 255);
  loop ();
end;

reply via email to

[Prev in Thread] Current Thread [Next in Thread]