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)
lines))
(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))
(begin
(set-dot! (+ x line) (+ y col) (ref-bitmap bm col line))
(draw-line! line (+ col 1)))))
(define (draw! line)
(if (< line (height-bitmap bm))
(begin
(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.
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 'done )
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.
;;
'done
))
Test your function by combining a bitmap-painter with the segment-painters
defined in the original graphic
language scheme definition (x-painter).
(define (cube-painter1 region) ...)The combiners defined on cubes are:
(beside3D cube-painter1 cube-painter2):
return a cube-painter drawing two half-cubes side by side.
(below3D cube-painter1 cube-painter2):
return a cube-painter drawing two half-cubes one on top of the other.
(front3D cube-painter1 cube-painter2):
return a cube-painter drawing two half-cubes one in front of the
other.
;; ======================================================================
;; 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)
(add-3Dvect
(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))))
;; 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))))
(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)
(begin
(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))))
;; 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))
0)
(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))))