Assignment 3

Principles of Programming Languages (201-1289101)

Abstract Data Types -- Graphic Language

Due 15 April 1997


This is long to read because I've included most of the answers. Your part is quite short.


  1. Bitmap painters
  2. Cube language


Question 1: Bitmap Painters

The painters discussed in class only worked with list of segments. We will develop a restricted set of painters working on bitmaps as well. A bitmap is a two-dimensional array of pixels of different colors. It describes a picture point by point in a discrete manner.

A primitive bitmap has an original size, specified as a width and height. It can then be displayed directly on the screen, by displaying each pixel as a single dot of the appropriate color.

In order to implement painters for bitmaps, we need to be able to resize bitmaps to different sizes before displaying them in a given frame. There are different algorithms to solve this problem, so that the resized bitmap looks as much as possible as the original one. One particular algorithm is called digital differential analyzer and is described in a short article available at the department office (A 2-D DDA Algorithm for fast image scaling, Dr Dobb's Journal, April 1997, pp.46-49, Dean Clark). This code implements this algorithm in C. The algorithm is simple and efficient, working with integer arithmetic as much as possible (for efficiency) and avoiding the complex computations of full bilinear interpolation.

The following Scheme functions define a new ADT for bitmaps. They are based on a new Scheme datatype called vector, which works like one-dimensional arrays in Pascal. The primitive Scheme functions for manipulating vectors are documented in Vectors Manual.

;; ======================================================================
;; Supporting ADTs: Bitmap
;; ======================================================================
(define (make-bitmap width height color)
  ;; A bitmap is a vector of lines.  Each line is a vector of pixels
  ;; specified by their color.
  (let ((lines (make-vector height)))
    (define (make-line i)
      (if (< i height)
	  (let ((line (make-vector width)))
	    (vector-fill! line color)
	    (vector-set! lines i line)
	    (make-line (+ i 1)))))
    (make-line 0)

(define (width-bitmap bm)
  (vector-length (vector-ref bm 0)))

(define (height-bitmap bm)
  (vector-length bm))

(define (ref-bitmap bm x y)
  (vector-ref (vector-ref bm y) x))

(define (set-bitmap! bm x y c)
  (vector-set! (vector-ref bm y) x c))

(define (draw-bitmap! bm x y)
  (define (draw-line! line col)
    (if (< col (width-bitmap bm))
	  (set-dot! (+ x line) (+ y col) (ref-bitmap bm col line))
	  (draw-line! line (+ col 1)))))
  (define (draw! line)
    (if (< line (height-bitmap bm))
	  (draw-line! line 0)
	  (draw! (+ line 1)))))
  (draw! 0))
Note that the function draw-bitmap! only draws the original bitmap in its original size. To turn a bitmap into a painter, you need to define two additional functions: one to deal with the different ways of flipping a bitmap, and one to resize the bitmap.

Question 2.1: Flip-bitmap

Write the function flip-bitmap that receives as parameter a bitmap and three boolean flags determining how to flip the bitmap. The function returns a new bitmap of the appropriate size and filled with the appropriate colors copied from the original bitmap.
(define (flip-bitmap bm flipx flipy flipxy)
  ;; Return a new bitmap with the same size as bm 
  ;; but flipped according to the 3 flags as follows:
  ;; (flipx: invert the direction of x or not)
  ;; (flipy: invert the direction of y or not)
  ;; (flipxy: invert the role of x and y or not)
  ;;     y       x <--|       y    |--> x
  ;;     ^            |       ^    |
  ;;     |            v       |    v
  ;;     |___> x      y   x<--|    y
  ;;     NNN     YYN      YNN      NYN
  ;;     x       y <--|       x    |--> y
  ;;     ^            |       ^    |
  ;;     |            v       |    v
  ;;     |___>y       x   y<--|    x
  ;;     NNY     YYN      YNY      NYY

Question 2.2:

Write the function bitmap->painter that transforms a primitive bitmap into a painter that can display the original bitmap in any frame. To ease the problem, only consider the case of frames that are orthogonal to the x and y axis (no rotation -- only flips are allowed). Your code must rely on the DDA algorithm.
(define (bitmap->painter bm)
  (lambda (frame)
    (if (not (or (= 0 (xcor-vect (edge1-frame frame)))
		 (= 0 (ycor-vect (edge1-frame frame)))
		 (= 0 (xcor-vect (edge2-frame frame)))
		 (= 0 (ycor-vect (edge2-frame frame)))))
	(error "No support for rotation on bitmaps."))
    ;; Draw the bitmap bm in the appropriate size in frame.
    ;; 1. Should draw directly on the screen (no need to create an
    ;;    intermediary bitmap).
    ;; 2. Should support rotations and flips of 90 degree angles only
    ;;    That is: should work with the following 8 configurations:
    ;;    (This is checked in the if-test above)
    ;;    That is it should recognize which version of flip-bitmap to use
    ;;    by looking at the frame.
    ;; 3. Should work with non square frame (edge1 and edge2 can be of
    ;;    different length).  Note that the algorithm in C assumes a single
    ;;    zoom value is used for both x and y.  You must adjust it so that
    ;;    it works with different zoom values for x and y.

Test your function by combining a bitmap-painter with the segment-painters defined in the original graphic language scheme definition (x-painter).

Question 2: Cube Language

The purpose of this question is to define an extension of the graphic language working on three-dimensional cubes instead of frames. We will just work with very basic cubes of simple colors as primitives. A cube-painter is defined as a function that displays a simple cube in the region of the 3-D space it receives as an argument:
(define (cube-painter1 region) ...)
The combiners defined on cubes are: Modify the code studied in class to work with 3D objects with these operators. The following new support ADTs are provided:
;; ======================================================================
;; Supporting ADTs: Region
;; ======================================================================
(define (make-cube origin edgex edgey edgez)
  (list origin edgex edgey edgez))

(define (origin-cube cube) (car cube))
(define (edgex-cube cube) (cadr cube))
(define (edgey-cube cube) (caddr cube))
(define (edgez-cube cube) (cadddr cube))

(define pi (* 2.0 (asin 1)))

(define (region-coord-map region)
  (lambda (v)
     (origin-cube region)
     (add-3Dvect (scale-3Dvect (xcor-3Dvect v)
			       (edgex-cube region))
		 (add-3Dvect (scale-3Dvect (ycor-3Dvect v)
					   (edgey-cube region))
			     (scale-3Dvect (zcor-3Dvect v)
					   (edgez-cube region)))))))

;; ======================================================================
;; Supporting ADTs: 3D-Vectors
;; ======================================================================

(define (make-3Dvect x y z) (list x y z))
(define (xcor-3Dvect v) (car v))
(define (ycor-3Dvect v) (cadr v))
(define (zcor-3Dvect v) (caddr v))
(define (add-3Dvect v1 v2) (make-3Dvect (+ (xcor-3Dvect v1) (xcor-3Dvect v2))
					(+ (ycor-3Dvect v1) (ycor-3Dvect v2))
					(+ (zcor-3Dvect v1) (zcor-3Dvect v2))))
(define (scale-3Dvect s v) (make-3Dvect (* s (xcor-3Dvect v))
					(* s (ycor-3Dvect v))
					(* s (zcor-3Dvect v))))
(define (sub-3Dvect v1 v2) (make-3Dvect (- (xcor-3Dvect v1) (xcor-3Dvect v2))
					(- (ycor-3Dvect v1) (ycor-3Dvect v2))
					(- (zcor-3Dvect v1) (zcor-3Dvect v2))))

(define (length-3Dvect v)
  (sqrt (+ (square (xcor-3Dvect v)) 
	   (square (ycor-3Dvect v))
	   (square (zcor-3Dvect v)))))

(define (resize-3Dvect v new-length)
  (scale-3Dvect (/ new-length (length-3Dvect v)) v))

;; 2D determinant of matrix:
;; a c
;; b d
(define (determinant a b c d)
  (- (* a d) (* b c)))

;; This computes a vector that is orthogonal to both v1 and v2.
(define (product-3Dvect v1 v2)
  (let ((x1 (xcor-3Dvect v1))
	(y1 (ycor-3Dvect v1))
	(z1 (zcor-3Dvect v1))
	(x2 (xcor-3Dvect v2))
	(y2 (ycor-3Dvect v2))
	(z2 (zcor-3Dvect v2)))
    (make-3Dvect (determinant y1 z1 y2 z2)
		 (- (determinant x1 z1 x2 z2))
		 (determinant x1 y1 x2 y2))))

Similar to the segment-painters studied in class, develop a family of segment cubes. To draw the 3D segments, you can use the following procedures providing ways to draw in isometric perspective at a given angle:
;; Project a 3d vector on a 2d frame.
(define (project v3 angle)
  (make-vect (+ (xcor-3Dvect v3) (* 0.5 (zcor-3Dvect v3) (cos angle)))
	     (+ (ycor-3Dvect v3) (* 0.5 (zcor-3Dvect v3) (sin angle))))))

(define (draw3d! region angle v3start v3end)
  (let ((regmap (region-coord-map region)))
    (let ((start (project (regmap v3start) angle))
	  (end (project (regmap v3end) angle)))
      (draw-line! start end))))

For example, the following 3D-painter draws a cube in any region:
(define (color-cube c angle n)
  ;; This draws a cube of color c, projected at angle angle, and with
  ;; n equi-distant horizontal lines.
  (lambda (region)
    ;; Draw the 2 horizontal lines at level n
    (define (draw-y! y inc)
      (if (<= y 1.0)
	    (draw3d! region angle (make-3Dvect 0 y 0) (make-3Dvect 1 y 0))
	    (draw3d! region angle (make-3Dvect 1 y 0) (make-3Dvect 1 y 1))
	    (draw-y! (+ y inc) inc))))
    (set-color! c)
    (draw3d! region angle (make-3Dvect 0 0 0) (make-3Dvect 0 1 0))
    (draw3d! region angle (make-3Dvect 1 0 0) (make-3Dvect 1 1 0))
    (draw3d! region angle (make-3Dvect 1 0 1) (make-3Dvect 1 1 1))
    (draw3d! region angle (make-3Dvect 0 1 0) (make-3Dvect 0 1 1))
    (draw3d! region angle (make-3Dvect 0 1 1) (make-3Dvect 1 1 1))
    (draw-y! 0 (/ 1 n))))

You can try it using the following procedure to draw a 3D-painter in a given frame: (let* is documented in Binding constructs).
;; This computes a cube that should fit within frame when projected
;; at any angle.
(define (frame->region frame)
  (let* ((x (edge1-frame frame))
	 (y (edge2-frame frame))
	 (lx (length-vect x))
	 (ly (length-vect y))
	 (vx (make-3Dvect (xcor-vect x) (ycor-vect x) 0.0))
	 (vy (make-3Dvect (xcor-vect y) (ycor-vect y) 0.0))
	 (m  (min lx ly)))
    (make-cube (make-3dvect (xcor-vect (origin-frame frame))
			    (ycor-vect (origin-frame frame))
	       (scale-3dvect 0.5 vx)
	       (scale-3dvect 0.5 vy)
	       (resize-3dvect (product-3Dvect vx vy) (/ m 2)))))

;; Draw a cube in the current window
(define (draw-cube! cube)
  (cube (frame->region (center-frame))))

Write the following functions:
The end.