Section Mnemonic Machine Code* Instruction
7.2.6.4 HALT 000000 halt7.2.6.3 MOV 01SSDD move
7.2.6.3 ADD 02SSDD add
7.2.6.3 SUB 03SSDD subtract
7.2.6.3 MUL 04SSDD multiply
7.2.6.3 DIV 05SSDD divide
7.2.6.4 JSR 060RDD jump to subroutine
7.2.6.4 RTS 07000R return from subroutine
7.2.6.3 CMP 08SSDD compare
7.2.6.5 RN 09nnDD read numeric
7.2.6.5 WN 10nnSS write numeric
7.2.6.5 RC 11nnDD read character
7.2.6.5 WC 12nnSS write character
7.2.6.2 CLR 1300DD clear
7.2.6.2 CLRH 1310DD clear high byte
7.2.6.2 CLRL 1320DD clear low byte
7.2.6.2 TST 1400DD test
7.2.6.2 SWAB 1500DD swap bytes
7.2.6.2 INC 1600DD increment
7.2.6.2 DEC 1700DD decrement
7.2.6.4 BR 180aaa unconditional branch
7.2.6.4 BEQ 181aaa branch if equal
7.2.6.4 BLT 182aaa branch if less than
7.2.6.4 BLE 183aaa branch if less than or equal
7.2.6.4 BGT 184aaa branch if greater than
7.2.6.4 BGE 185aaa branch if greater than or equal
7.2.6.4 BNE 186aaa branch if not equal to
7.2.6.4 TOFF 190000 trace off
7.2.6.4 TON 191000 trace on
7.2.6.4 NOP 192000 no operation
*Machine code in ascending order.
12.2.2. SML ASSEMBLER SUMMARY
Source statement format:
SOURCE DESTINATION
label: instruction operand, operand ; comment
Machine code format:
column 1-3 8-13 15 and on
memory address memory contents comments
Pseudo operators:
.BLKW nn reserve nn words of memory
.NUM a,b,...x reserve x words of memory initialize the first word with the value a, second word the value b, and so on.
.CHAR "string" reserve a block of words large enough to contain the entire string, with each word storing two characters in their ASCII representation.
.END signifies the end of the program.
12.3. ALLOWABLE CHARACTERS IN SML AND THEIR CORRESPONDING EBCDIC CODES
EBCDIC Character Codes
Character EBCDIC Character EBCDIC Character EBCDIC
Formfeed 012 } 208 E 197
Carriage \ 224 F 198
Return 013 a 129 G 199
Newline 021 b 130 H 200
Linefeed 037 c 131 I 201
Blank 064 d 132 J 209
. 075 e 133 K 210
< 076 f 134 L 211
( 077 g 135 M 212
+ 078 h 136 N 213
& 080 i 137 O 214
! 090 j 145 P 215
$ 091 k 146 Q 216
* 092 l 147 R 217
) 093 m 148 S 226
; 094 n 149 T 227
- 096 o 150 U 228
/ 097 p 151 V 229
| 106 q 152 W 230
' 107 r 153 X 231
% 108 s 162 Y 232
_ 109 t 163 Z 233
> 110 u 164 0 240
? 111 v 165 l 241
` 121 w 166 2 242
: 122 x 167 3 243
# 123 y 168 4 244
@ 124 z 169 5 245
' 125 A 193 6 246
= 126 B 194 7 247
" 127 C 195 8 248
~ 161 D 196 9 249
{ 192
12.4. COMMAND SUMMARIES
12.4.1. VI (Visual) Editor Command Summary
Inserting Text
a add after cursor
A add to end of line
i insert before cursor
I insert before first nonblank
o open line below cursor
O open line above cursor
Deleting Text
dd delete line
dw delete word
x delete character under cursor
X delete character to left of cursor
D delete rest of line
Undo
u undo last change
U restore current line
Changing and Replacing Text
. repeat last change
r replace character under cursor
R write over text starting at cursor
~ change case
cw change word
J join
[Return] (in insert mode) split
: 1,$s/X/Y/opt
Global substitute X with Y
options:
g - change every occurrence in line
c - confirm each change
p - print changed lines
Copying and Moving Text
Y yank into buffer
p put buffer after cursor
P put buffer before cursor
Searching Text
/X search forward for X
?X search backward for X
n repeat previous search in the specified direction
N repeat previous search in the opposite direction
:g/pattern/p print every line with pattern in it
Patterns Within Searching
(must use set magic option first)
. any character
* any number of the preceeding pattern
[abc] a, or b, or c
[^abc] any character but a, b, and c
[a-b] any character between a and b
Screen
^l clear and redraw
File Manipulation
:w name write to file name
:q! quit without saving changes
:wq write and quit
ZZ write and quit
:n edit next file
:n! edit next file, discarding changes to current
:r name read file name into buffer
Options
:set magic allow special search patterns
If a command is preceded with a number it will be repeated that number of times.
EX: 5dd will delete five lines
[ESC] cancels any command
u undo last command
12.4.2. Unix Command Summary
*Do not tamper with system software, or other user's files. Abuse will result in an immediate loss of privileges and possibly more severe consequences.
* Help can be obtained by the `man' command. For example:
% man ls
You can also get a list of possible manuals to read by using a keyword. For example:
% man -k directory
Below is a short list of commands to get you started.
PROGRAM DEVELOPMENT EXAMPLES
cc - 'C' compiler cc main.c
EDITORS
ex - text editor ex lab10.s
vi - visual (screen editor) vi lab10.s
FILE MAINTENANCE
ls - list contents of directory ls *.s
mv - move or rename files mv main.c super.c
cp - make a copy of a file cp version1 version
rm - remove files or directories rm old.c
cmp - compare two files cmp file1.c file2.c
chmod - change file protection modes chmod 644 solutions.txt
FILE OUTPUT
cat - display a file cat readme.txt
more - screen by screen display more readme.txt
lpr - print on mercury line printer print readme.txt
od - base 8, 10, and 16 file dump od -b test.o
lpr -Pc135 - print on c135 line printer lpr -Pc135 program.a
lpr -Pc115 - print on c115 line printer lpr -Pc115 program.a
DIRECTORIES
mkdir - make a directory mkdir assign1
pwd - print working directory name pwd
cd - change working directory cd assign1
rmdir - remove a directory rmdir assign1
SYSTEM INFO
who - who is on the system who
finger - user info lookup program finger smith
date - print and set the date date
DISK INFO
df - disk free space df
du - personal disk usage du
COMMUNICATING WITH OTHER USERS
mail - send and receive mail mail smith
write - write to another user write smith
COMMUNICATION SOFTWARE
cu - connect to a remote system cu -s 9600 -l /dev/cul0
ckermit - file transfer program ckermit
ftp/telnet - file transfers telnet meena
ASSORTED
passwd - change account password passwd
ascii - map of ASCII character set ascii
bc - calculator bc
calendar - reminder service N/A
KILLING PROCESSES
w - what are people doing w
ps - process status ps
kill - terminate a process kill -9 21356
logout - logging out logout
MAIL UTILITY
Mail is a utility to send messages to other users. To read incoming mail type 'mail'. To read old mail type 'mail -f'. Mail has the following commands,
q quit, preserving all messages
save [msglist] file append messages to file
xit exit, preserving all messages
h list of all messages
? help
reply [msglist] reply to message, including all recipients
Reply [msglist] reply to the authors of all messages
d [msglist] delete messages
[msglist] is optional and specifies messages by numbers, authors, subject or type. The default is the current message. For example d 1-2 would delete the first two messages.
12.4.3. XEDIT EDITOR COMMAND SUMMARY
Moving Around
[RETURN] move cursor to the command line
[TAB] moves between fields
PF1 [ESC] [1] help
PF3 [ESC] [3] quit (if no changes have been made)
PF7[ESC] [7] scrolls down
PF8[ESC] [8] scrolls up
Prefix Area Commands
#x single command, # is optional, means repeat command x by # times
xx block command, applys command to a range specified by two sets of xx (top of block and bottom of block)
c cc copy line(s), used in combination with f or p
m mm move line(s), used in combination with f or p
f apply command following this line
p apply command preceding this line
d dd delete line(s)
a add a blank line after this line
<# <<# shift text left by # line(s)
># >># shift text right by # line(s)
" "" duplicate line(s)
x xx exclude line(s) (leaves a shadow)
s show all lines in this shadow
s-# show # lines at the bottom of this shadow
s+# show # lines at the top of this shadow
/ make this line the current line
e extend this line past the 80 character limit
si structured input, automatically insert blank lines while you are typing
.xxxx leave bookmark for reference
Command Line Commands
help get help on XEDIT
top make the current line the top of the file
bottom make the current line the bottom of the file
up # move up # line(s)
down # move down # line(s)
left # shift the viewing screen left by # columns
right # shift the viewing screen right by # columns
quit quit without saving changes
qquit force a quit
save save (to a new file) and stay in the editor
ssave force a save
file file (to a new file) and leave the editor
ffile force a file
x[fn ft [fm]]
allows you to switch between editing multiple files or to edit an additional file
get fn ft [fm]
get file from the disk and insert it in the file after the current line
put[d] # fn ft [fm]
put (and optionally delete) # lines after and including the current line into file called fn ft [fm]
you can use * in place of # to mean all lines after and including this line
recover
recover lines that have just been deleted
sort # A col1 col2 [col3 col4 ...]
sort # lines after and including this line in ascending (A) or descending (D) order between the ranges col1 to col2 (primary key), and optionally col3 to col 4 (secondary key) and so on
Searching from the Command Line
/xxx/
search for xxx in the file
/xxx/ & /zzz/
search for lines containing xxx and zzz in the file
/xxx/ | /zzz/
search for lines containing xxx or zzz in the file
all /xxx/
display all lines containing xxx and make all other lines shadows
can use & and | to expand this criteria
all
remove all shadows and display all lines in the file
c/xxx/yyy/* *
change xxx to yyy
* * means all lines after and including this line and all occurrences on those lines
Set Command
set tabs
set tab stops
set autosave
set the frequency of saves with respect to changes (related to the change flag in the file identification line)
set case
allows uppercase/lowercase (mixed) or just uppercase
set number
allows you to see line numbers in the prefix area
set nulls
automatically truncates the end of every line
set prefix
allows you to display the prefix line on the left side of the screen, the right side of the screen, or not at all
set screen
allows you to split the screen into multiple screens, either horizontally or vertically
set cmdline
specifies the locating of the command line on the screen
set curline
specifies the location of the current line on the screen
set scale
specifies the location of the scale (ruler) on the screen, or not at all
12.5. DATA SHEETS
7400 QUAD 2-INPUT NAND GATE
All
four of the NAND gates operate independently. If both inputs are high the
output is low otherwise it is high.
Propagation Delay - 10 nanoseconds
typical
Current per package - 12 mA typical
7402 QUAD 2-INPUT NOR GATE
All
four NOR gates may be used independently. On any one gate if either input is
high the output is low otherwise the output is high.
Propagation delay -
10 nanoseconds typical
Current per package - 12 mA
7404 HEX INVERTER
All
inverters operate independently. A high input produces a low
output
Propagation delay - 10 nanoseconds typical
Current per package
- 12 mA
7410 TRIPLE 3-INPUT NAND GATE
All
gates operate independently. When any input is low on a gate the output will
be high.
Propagation delay - 9 nanoseconds typical
Current per
package - 6 mA
7420 QUAD 4-INPUT NAND GATE
All
gates operate independently. When any input is low on a gate the output will
be high.
Propagation delay - 10 nanoseconds typical
Current per
package - 4 mA
7432 QUAD 2-INPUT OR GATE
All
4 gates operate independently. If either input is high the output is
high.
Propagation Delay - 12 nanoseconds typical
Current per package
- 19 mA
7474 DUAL D EDGE-TRIGGERED FLIP-FLOP
The
two positive edge-triggered D flip-flops operate independently. The
information on the D input goes onto the Q output whenever the clock input goes
positive.
Information on the D input can be changed at any time but it
is only the value that is on the D input when the positive going edge of the
clock occurs that is passed to the Q output.
The Clear and Set inputs
should be tied high or left unconnected for normal operation. When CLR is
taken low Q is set low until CLR is again set high. When SET is taken low Q is
set high until SET is again set high. SET and CLR operations take priority so
the D input is ignored when SET or CLR is low.
Maximum clock
frequency - 25 MHz
Current per package - 20 mA
The operation of the
flip-flop is summarized below:
INPUT OUTPUTS
SET CLEAR CLOCK D Q xto(Q)
L H X X H L
H L X X L H
L L X X ? ?
H H [[arrowup]] H H L
H H
[[arrowup]] L L H
7476 DUAL JK EDGE-TRIGGERED FLIP-FLOP
The
two JK flip-flops operate independently. The Q and xto(Q) outputs change as
shown by the function table below.
The
Clear and Set inputs should be tied high or left unconnected for normal
operation. When CLR is taken low Q is set low until CLR is again set high.
When SET is taken low Q is set high until SET is again set high. SET and CLR
operations take priority so the J&K inputs are ignored when SET or CLR is
low.
Maximum frequency - 20 MHz
Current per package - 20 mA
7486 QUAD EXCLUSIVE-OR GATE
All
gates operate independently. If one input, but not both, is high then the
output will be high.
Propagation time - 18 nanoseconds
typical
Current per package - 30 mA typical
74LS138 DECODER/MULTIPLEXER
The
LS138 is designed for use in high-performance memory systems or data routing
applications. Three enable inputs, two low and one high, are provided to
minimize external enable circuitry requirements. When one of the enables is
valid one of the 8 outputs will be asserted low based on the binary input at
the ABC inputs. The table below summarizes the chips operation.
NOTE: G2=G2A+G2B
Propagation time - 22
nanoseconds
Current per package - 6.4 mA
74181 ARITHMETIC LOGIC UNIT
The
181 performs 16 binary arithmetic operations on two 4-bit words as shown in the
table below. These operations are selected by the four function select
line(S0-S3) and include addition, subtraction, decrement and straight
transfer.
SELECTION ACTIVE HIGH DATA
M=H M=L; ARITHMETIC OPERATIONS
logic xto(Cn)=H xto(Cn)=L
S3 S2 S1 S0 function (no carry) (with
carry)
L L L L F=xto(A) F=A F=A PLUS 1
L L L H F=xto(A+B) F=A+B F=(A+B) PLUS 1
L L H L F=xto(A)B F=A+xto(B) F=(A+XTO(B)) PLUS 1
L L H H F=0 F=MINUS 1(2's compl) F=ZERO
L H L L F=XTO(AB) F=A PLUS AXTO(B) F=A PLUS AXTO(B) PLUS 1
L H L H F=XTO(B) F=(A+B)PLUS AXTO(B) (A+B)PLUS AXTO(B) PLUS 1
L H H L F=A[[circleplus]]B F=A MINUS B MINUS 1 F=A MINUS B
L H H H F=AXTO(B) F=Axto(B) MINUS 1 F=Axto(B)
H L L L F=xto(A)+B F=A PLUS AB F= A PLUS AB PLUS 1
H L L H F=xto(A[[circleplus]]B) F= A PLUS B F=A PLUS B PLUS 1
H L H L F=B F=(A+XTO(B)) PLUS AB F=(A+XTO(B)) PLUS AB PLUS 1
H L H H F=AB F=AB MINUS 1 F=AB
H H L L F=1 F=A F=A PLUS A PLUS 1
H H L H F=A+XTO(B) F=(A+B) PLUS A F=(A+B) PLUS A PLUS 1
H H H L F=A+B F=(A+XTO(B)) PLUS A F=(A+XTO(B)) PLUS A PLUS 1
H H H H F=A F=A MINUS 1 F=A
INPUTS OUTPUTS
CLEAR S1 S0 CLK SL SR A B C D QA QB QC QD
L X X X X X X X X X L L L L
H X X L X X X X X X QA0 QB0 QC0 QD0
H H H [[arrowup]] X X a b c d a b c d
H L H [[arrowup]] X H X X X X H QAn QBn QCn
H L H [[arrowup]] X L X X X X L QAn QBn QCn
H H L [[arrowup]] H X X X X X QBn QCn QDn H
H H L [[arrowup]] L X X X X X QBn QCn QDn L
H L L X X X X X X X QA0 QB0 QC0 QD0
H = high level (steady state)
L = low level (steady state)
X = irrelevant (any input, including transitions)
[[arrowup]] = transition from low to high level
a,b,c,d = the level of steady state input at inputs A, B, C, or D respectively.
QA0, QB0, QC0, QD0 = the level of QA, QB, QC, or QD, respectively, before the indicated steady-state input conditions were established.
QAn, QBn, QCn, QDn = the level of QA, QB, QC, QD respectively before the most-recent [[arrowup]] transition of the clock.
ADC0804C 8-BIT ANALOG TO DIGITAL CONVERTER
WITH DIFFERENTIAL
INPUTS
The
804 is a CMOS 8 bit analog to digital converter that provides tri-state outputs
for easy interfacing to microprocessor circuits. The 804 can operate with an
external clock signal or with an external resistor and capacitor it can operate
using the on-chip clock generator.
When the xto(WR) input goes low the
804 is reset in preparation for the next conversion. As long as both xto(WR)
and xto(CS) remain low the 804 remains in the reset state. One to eight clock
cycles after xto(CS) or xto(WR) makes a low to high transition conversion will
start.
When the the conversion is completed xto(INTR) will be
asserted low. To enable the outputs (D0-D7) a low is applied at both xto(CS)
and xto(RD). To start another conversion take xto(WR) low as discussed
above.
12.6. USEFUL NOTES
12.6.1. Scan-converting circles
12.6.1.1. ALGORITHM 1: BRUTE FORCE PARAMETRIC METHOD
x = R sint
y = R cost
[[Delta]]t = TWO _PI / n;
for (t = 0; t < TWO _ PI; t +=[[Delta]]t)
plot(round (R *sin t), round (R *cos t));
Cost: 1 integer comparison
1 floating point addition
2 floating point multiplications
2 floating point trigonometric functions
2 rounding operations
12.6.1.2. ALGORITHM 2: INCREMENTAL VERSION OF 1
xi = R sin ti
yi = R cos ti
xi+1 = R sin ti+1 = R sin (ti + [[Delta]]t) = R sin ti cos [[Delta]]t + R cos ti sin [[Delta]]t
= xi cos [[Delta]]t + yi sin [[Delta]]t
yi+1 = R cos ti+1 = R cos (ti + [[Delta]]t) = R cos ti cos [[Delta]]t - R sin ti sin [[Delta]]t
= -xi sin [[Delta]]t + yi cos [[Delta]]t
x = 0; y = R;
DELTA _COS = cos (TWO_PI / n);
DELTA _SIN = sin (TWO_PI / n);
for (i = 0; i < n; i ++) {
plot (round (x), round (y));
x' = x * DELTA_COS + y * DELTA_SIN;
y = -x * DELTA_SIN + y * DELTA_COS;
x = x' ;
}
Cost: 1 integer comparison
4 floating point multiplications
2 floating point additions/subtractions
1 integer incrementation
2 rounding operations
12.6.1.3. ALGORITHM 3: ELIMINATING THE ROUNDING OPERATION
x2 + y2 = R2
We consider 1/8 of the entire circle:
At each step we select a grid point which minimizes the error function:
e = R2 - x2 - y2
for (x = 0, y = R; y > x; x ++) {
plot (x,y);
eR = R2 - (x+1)2 - y2 /*error assuming move to the right */
eD = R2 - (x+1)2 - (y-1)2 /*error assuming a diagonal move */
if ( | eR | > | eD |) /*move diagonally if this reduces
y --; error, otherwise move to the right */
}
Cost: high; we are going to reduce it anyway.
12.6.1.4. ALGORITHM 4: CALCULATING ERRORS INCREMENTALLY
e = R2 - x2 - y2
eR = R2 - (x + 1)2 - y2 = R2 - x2 - 2x - 1 - y2 = e - (2x + 1)
eD = R2 - (x + 1)2 - (y - 1)2 = R2 - x2 - 2x - 1 - y2 + 2y - 1 = e - (2x + 1) + (2y - 1)
e = 0;
for (x = 0, y = R; y > x; x ++) {
plot (x,y);
eR = e - (2x + 1);
eD = e - (2x + 1) + (2y - 1);
if (| eR | > | eD | ) {
e = eD;
y --;
}
else
e = eR;
}
12.6.1.5.
ALGORITHM 5: ELIMINATING CALCULATION OF ABSOLUTE VALUES
Recall that: eD = e - (2x + 1) + (2y - 1)
eR = e - (2x + 1)
Let us consider the value of | e | - | e | for possible combinations of eD and eR
eD eR | eD | - | eR | eD + eR
> 0 > 0 2y - 1 > 0 > 0
> 0 < 0 eD + eR = 2e - 4x + 2y - 3 = | eD | - | eR |
< 0 > 0 not possible
< 0 < 0 - (2y - 1) < 0 < 0
Conclusion: sign (| eD | - | eR |) = sign (eD + eR)
e = 0;
for (x = 0, y = R; y > x; x ++) {
plot (x,y);
eR = e - (2x+1);
eD = e - (2x+1) + (2y-1);
if (eR + eD < 0 ) {
e = eD ;
y --;
}
else
e = eR ;
}
12.6.1.6. ALGORITHM 6: EXPRESSING THE ALGORITHM IN TERMS OF THE SUM (ER + ED )
case eR + eD < 0 }
e' = eD = e - (2x+1) + (2y-1) } Recall:
x' = x+1 y' = y-1 } eR + eD = 2e - 4x + 2y - 3
(eR + eD )' = 2e' - 4x' + 2y' - 3 = 2[e - (2x+1) + (2y-1)]- 4(x+1) + 2(y-1)- 3
= 2e - 4x - 2 + 4y - 2 - 4x - 4 + 2y - 2 - 3 =
= (eR + eD ) - 4x + 4y - 10
case eR + eD >= 0
e' = eR = e - (2x+1)
x' = x +1 y' = y
(eR + eD )' = 2 e' - 4x' + 2y' - 3 = 2[e - (2x+1)] - 4(x+1) + 2y - 3 =
= 2e - 4x - 2 - 4x - 4 + 2y - 3 =
= (eR + eD ) - 4x - 6
/* treat (eR+eD) as a variable */
(eR+eD) = 2R-3; /*by putting e=0, x=0, y=R in the formula for eR + eD */
for (x=0, y=R; y > 0; x++) {
plot(x,y);
if (eR + eD < 0) {
(eR + eD) += -4x + 4y - 10;
y--; /*go diagonally */
}
else
(eR + eD) += -4x - 6; /* go right */
}
12.6.1.7.
ALGORITHM 7: ELIMINATING MULTIPLICATIONS: 4*X AND 4*Y
(Bresenham's) (they could be implemented as shifts, but still . . . )
E = 2R-3; /*E=eR + eD */
inc_diag = 4*R - 10; /*-4x+4y-10 for x=0, y=R */
inc_right= -G; /*-4x-6 for x=0 */
for (x=0, y = R; y > x; x++) {
plot (x,y);
if (E < 0) {
E += inc_diag;
inc_diag -= 8; /*difference between -4x+4y-10
and -4(x+1) + 4(y-1) - 10 */
y--;
}
else {
E += inc_right;
inc_diag -= 4; /*difference between -4x+4y-10
} and -4(x+1) + 4y-10 */
inc_right -= 4; /*difference between (-4x-6) and
} -4(x+1) - 6 *1
Cost (worst case): 2 integer comparisons
5 integer additions/subtractions/incrementation
12.6.2. Hidden-Surface Algorithms -- Point-Sampling Algorithms
12.6.2.1. DEPTH-SORTING (PAINTER'S ALGORITHM)
sort objects by z
for all objects
for all covered pixels (x,y)
paint
12.6.2.2. Z-BUFFER
for all objects
for all covered pixels (x,y)
compare z and maybe set pixel
Difference between dept-sorting and Z-buffer:
when depth - comparisons are made
12.6.2.3. RAY-TRACING (RAY-CASTING)
for all pixels
for all objects
compare z and set pixel
Difference between Z-buffer and Ray-tracing:
the nesting order of the loops
12.6.2.4.
SCAN-LINE
Sort objects by y; for all y
sort objects by x; for all x
compare 2 and set pixel
12.6.3. Features of Various Algorithms
12.6.3.1. DEPTH-SORTING
Problem with circular overlapping: 2 is in front of 1
3 is in front of 2
1 is in front of 3
Solution: polygon subdivision;
further processing using Weiler-Atherton algorithm
Advantage: transparent surfaces can be handled
12.6.3.2. Z-BUFFER
Problem with the edges:
What color should be
assigned to this edge?
Problem with precision (integer vs. floating-point z-buffer)
Problem with aliasing, no transparency -> A-buffer
Advantages: takes any input; fast;
good for hardware implementations
12.6.3.3. RAY-TRACING
* Problem with aliasing
* Time-consuming; another view requires ray-tracing "from scratch."
* No interaction between diffuse surfaces -> Radiosity
12.6.3.4. SCAN-LINE
* Scan-line version of z-buffer - less memory necessary, but we need the notion of the list of active polygons - more difficult to implement, esp. by hardware
* Does not offer the degree of realism comparable with ray-tracing nor radiosity
* Advantage: can provide anti-aliasing
Since we keep the list of active polygous (and their active edges), we can calculate the intersection points with the grid.
12.6.4. Hidden surface algorithms (continued)
Weiler and Atherton: Hidden surface removal using polygon area sorting - SIGGRAPH '77
12.6.4. Shading polygon meshes
APPROACHES
1) Shade each polygon separately
2) Use average normal vectors at the vertices, interpolate in the color space, first along the edges, then along the scan lines
3) Use average normal vectors at the vertices, interpolate in the space of normal vectors (Phong)
Dividing the RGB cube
How
to cut a box?
ALGORITHM: Varianced-based algorithm for color image quantization.
INPUT:
1) A full-color image h,
2) K: the number of representative colors desired.
OUTPUT:
A quantized image f containing K colors.
Procedure VB_quantizer(h,K);
integer colormap[K][3], i, j;
real frequency[32][32][32];
structure box{
integer r1, r2, g1, g2, b1, b2;
};
structure record {
real weighted_variance;
structure box boundaries;
} subbox[K];
begin
/* step 1: initalization */
calculate the frequency of each color of image h in the RGB space (5 bits for each color component); the array frequency[32][32][32] forms the initial box;
subbox[0].boundaries := boundaries of the initial box;
subbox[0].weighted_variance := 100;
/* step 2: iterative subdivision of the initial box */
for i := 1 to K-1 do begin
select the subbox j with the largest subbox[j].weighted_variance;
obtain distributions by projecting all the points in the subbox j onto each of the color axes;
for each projected distribution, calculate the optimal cut-point and compute the weighted sum of projected variances of the two intervals;
the partition plane is chosen to be perpendicular to the axis with the minimum weighted sum of projected variances and passes through the optimal cut-point;
compute the weighted variance for each of the two sub-boxes
subbox[i] := boundaries and weighted variance of the sub-box1;
subbox[j] := boundaries and weighted variance of the sub-box2;
end; /* for */
/* step 3: finding K representative colors */
compute the centroids of the individual K sub-boxes, which form the colormap[K][3];
/* step 4: displaying the quantized image f */
replace the color of each pixel in the original image h by the closest color in the colormap[K][3];
12.7. GRAPHICS UTILITIES
The following commands are useful utilities for handling graphical images and configuring the graphics environment on some computers. For more information on any command, you should refer to the man pages.
All Computers
compress/uncompress
Compresses/uncompress a single file. Essential for screen images which can take up many megabytes of disk space.
gzip
Compress and uncompress a single file. This is more efficient than compress, but is not available on all Unix platforms.
X Windows
xwd
Save the specified window. When the command is issued, the mouse cursor turns into a crosshair that can be used to specify the window to save.
xwud
View an image saved with the xwd command.
xpr
Print an image saved with the xwd command. All colours in the image are converted to grey before printing.
xstdcmap
Manipulate the X Windows standard colour map.
xsetroot
Manipulate the X Windows desktop. With this command you can change the background colour or desktop bitmap, the shape and colour of the mouse cursor, and a number of other X Windows display attributes.
xset
Modify the behaviour of a number of X Windows attributes, such as mouse handling parameters, fonts, screen saver, etc.
xlock
The X Windows screen saver.
xfd
View any X Windows font.
xv
View, modify, and convert a number of different image formats.
xfig & tgif
Draw and manipulate 2-D objects. Good for making overheads, slides, or images for inclusion into documents.
SGI Workstations
makemap
Restores original system colour maps.
palette
An interactive colour map editor. Across the top row of the window are the numbers from 0 to 16. As a rule never touch colour map 0. Always work with colour map 1. The three long boxes control the amount of red, green, and blue that are included in the current map entry. The box below the sliders is a 16 by 16 square of colour map boxes. Click on a box to modify that colour map entry. A ramp can be defined by clicking on the first map entry with the left button and the last entry with the middle button. This interpolates colours between the two entries.
savemap filename -r min max
Saves colour map one to filename. If the -r option is used, only the range of colour values from min to max is saved.
loadmap filename
Loads the colour map in filename into map one.
snapshot -b
Saves window(s) swept out by user. The -b option causes a bell to ring when the image has been saved. See man entry for more details. 4D series only.
ipaste filename
Displays a previously snapped file.
scrsave filename.rgb [x1 x2 y1 y2] -b
Saves the whole rgb screen unless the coordinates x1,x2,y1,y2 are specified. The -b option causes the image to be saved as a 1 bit per pixel black and white image as opposed to a 3 byte deep rgb image. 4D series only.
istat filename
Returns the file type. If SCREEN is returned the image can be displayed under MEX and if NORMAL is returned it can't.
12.8. UNIX PLOT ROUTINES
Plot is a UNIX filter which takes input in plot file format and produces output for one of a number of graphic devices. One method of creating a plot file is to use the plot library in C.
The plot routines are designed to use on a wide variety of devices and are therefore somewhat limited to the "common denominator". For example, there is no support for changing pens on the plotter. This does allow you to use the same output to drive both the plotter and the Tektronix screens.
PLOT FUNCTIONS
openpl(); Opens plot. Must precede all other functions.
erase(); Start a new plot frame.
label(s) Place text at current point.
char s[];
line(x1,y1,x2,y2); Draw line.
circle(x,y,r); Draws a circle of radius r with centre (x,y).
arc(x,y,x0,y0,x1,y1); Draws arc between (x0,y0) and (x1,y1) with centre (x,y).
move(x,y); Designates a new current point.
cont(x,y); Draw a line from the current point to (x,y).
point(x,y); Plot a point at (x,y).
linemod(s) Indicates the desired linemod. The styles can be 'dotted',
char s[]; 'solid', 'longdashed', 'shortdashed', and 'dotdashed'.
This is only valid for 4014,7475, and ver output types.
space(x0,y0,x1,y1); Defines the drawing space. This must be square.
closepl(); Closes a plot. This flushes any pending output.
EXAMPLE PROGRAM
/*
* Program to plot something
* Compile:
* cc -O -s -o thing plotter.c -lplot
*
* Run:
* thing | plot -Txxxx
* where 'xxxx' is a device type recognized by plot.
* hp7475 plotter = -Thp7475
* tektronix 4014 = -T4014
*
*/
main()
{
openpl(); /* open plotter */
space(0, 0, 200, 200 ); /* determine space to plot in */
box( 0, 0, 200, 200 ); /* draw a box */
something(); /* draw the object */
move( 85, 10 ); /* label it */
label( "Thing\n");
closepl(); /* close plotter */
}
something()
{
line( 120, 50, 90, 40 ); /* draw line */
cont( 20, 10 ); /* continue to next point */
cont( 90, 80 );
cont( 140, 70 );
cont( 160, 65 );
cont( 160, 55 );
circle( 100, 100, 50); /* circle */
cont( 140, 50 );
cont( 5, 52 );
cont( 10, 70 );
cont( 60, 60 );
}
12.9. HEWLETT PACKARD 7475A PLOTTER
This section summarizes the operation and programming of the plotter. For more detail consult the manuals beside the plotter. The plotter has the following characteristics:
* 4 sizes of paper - 8f(1,2) " by 11" and 11" by 17"(Metric and Imperial)
* 6 pen tray
* grip cover wheels
* 2Gs of acceleration
* maximum velocity of 38.1 m/s
* address resolution is 0.025 mm
* repeatability is 0.1 mm
* letters plot at about 2 char/second
* 19 fonts resident in plotter
12.9.1.
Controls & Indicators
ERROR
This light can be on, off, or blinking:
a) ON - VIEW button has been pressed or paper loading lever is up.
b) BLINKING - A plotter error has occurred. Press ENTER & VIEW together to reset plotter
ARROWS
These allow the user to move the pen location. This is useful for digitizing points.
ENTER
when pressed with VIEW resets all power up defaults. This will not correct a paper jam(turn the power on and off to do this). When the paper size light is blinking (B/A3 or A/A4) the plotter has received the HPGL instruction DP for digitizing a point. The user should move the pen to the desired point and press ENTER to digitize it. The point is then stored in the plotters buffer until a OD command is received to read the point.
12.9.2. Plotting on the 7475A
COORDINATE SYSTEM
The diagram below illustrates the coordinate system used by the plotter and the default location for the scaling points P1 and P2.
SCALING
As the preceding diagram shows the power up settings have P1/P2 frame size of 10000 by 7200 points. These axis can be scaled to user coordinates using the SC command(see summary of HPGL commands). For example SC0,12,0,1000 scales the axis into 12 user units on the x-axis and 1000 units on the y-axis.
HEWLETT PACKARD GRAPHICS LANGUAGE(HPGL)
HPGL commands are summarized in the table below. They have one of 4 kinds of parameters:
1) i - integer between -32768 to +32768
2) d - decimal between -128.0000 and +127.9999
3) sd - scaled decimal between -32768.0000 and +32767.9999
4) c - character
SUMMARY OF HPGL COMMANDS
Instruction Description
AA X[i/sd],Y[i/sd],arcangle[i] Arc absolute
(,chordangle[i])AR X[i/sd],Y[i/sd],arcangle[i] Arc relative
,(chordangle[i])CA n[i] Designate alternate set n
CI radius[i/sd](,chordangle[i]) Circle
CP spaces[d],lines[d] Character plot
CS n[i] Designate standard set n
DC Digitize clear
DF Set default values
DI run[d],rise[d] Absolute direction
DP Digitize point
DR run[d],rise[d] Relative direction
DT c[c] Define label terminator
EA X[i/sd],Y[i/sd] Edge rectangle absolute
ER X[i/sd],Y[i/sd] Edge rectangle relative
Instruction Description
EW radius[i/sd],startangle[i], Edge wedge
sweepangle[i],(,chord angle [i])SM c[c] Symbol mode
SP n[i] Select pen
SR width[d],height[d] Relative character size
SS Select standard character set
TL tp[d](,tn[d]) Tick length
UC (pen[i]),X[d],Y[d],pen[i](, ...) User defined character
VS v[d] Select velocity v
WG radius[i/sd],startangle[i], Shade wedge
sweepangle[i],(,chordangle[i])XT x-axis tick
YT y-axis tick
FT type[i](,spacing[sd](,angle[i]) Fill type
IM e[i](,s[i](,p[i])) Input e,s, and p masks
IN Initialize
IP P1x[i],P1y[i](,P2x[i],P2y[i]) Input P1 and P2
IW Xlo[i],Ylo[i],Xhi[i],Yhi[i] Input window
LB c ... c[c] Label ASCII string
LT t[d](,l[d]) Designate line type and length
OA Output actual position and status
OC Output commanded position and pen position
OD Output digitized point and pen
statusOE Output error
OF Output factors
OH Output hard-clip limits
OI Output identification
OO Output options
OP Output P1 and P2
OS Output status
OW Output window
PA X[i/sd],Y[i/sd](, ...) Plot absolute
PD (X[i/sd],Y[i/sd](, ...) Pen down
PR X[i/sd],Y[i/sd](, ...) Plot relative
PS paper size[i] Paper size
PT thickness[d] Pen thickness
PU (X[i/sd],Y[i/sd])(, ...) Pen up, then move
RA X[i/sd],Y[i/sd] Shade rectangle
RO n[i] Rotate coordinates
RR X[i/sd],Y[i/sd] Shade rectangle
SA Select alternate character set
SC Xmin[i],Xmax[i],Ymin[i],Ymax[i] Scale
SI width[d],height[d] Absolute character size
SL tanf[d] Absolute character slant
(from vertical)
EXAMPLE PROGRAM
/*/* Plot something
/*
*/
main()
{
plot_init(); /* set up plotter */
draw(); /* draw something */
plot_off(); /* turn plotter off */
}
/* draw a rectangle and a circle */
draw()
{
printf("IP;SC0,600,0,600;"); /* scale */
printf("PS4;"); /* page size 4 */
printf("SP3;");
printf("PU;PA0,0;PD;"); /* draw rectangle */
printf("EA600,600;");
printf("SP2;PU;PA300,300;PD;"); /* draw circle */
printf("CI150,5;PU;");
printf("SP0;"); /* put current pen away */
}
/*
/* Set up HP 7475 plotter to implement handshaking
/* using XON/XOFF protocol.
/*
/* plot_init should normally be called before any plotting is
/* attempted.
/* plot_off is called when all plotting is done.
/*
/* The plotter manages the handshaking by sending XOFF when
/* there is no more room in the buffer for data. When the plotter
/* has room the XON character is sent. For unix these characters are:
/* XON - ^S (19)
/* XOFF - ^Q (17)
/*
/* The XOFF threshold level is the number of bytes remaining in the
/* buffer before the XOFF character is sent (initially set at 80).
*/
#define PLOT_ON "\033.("
#define ABORT_DEV_CONTROL "\033.J"
#define ABORT_GRAPHIC_INST "\033.K"
#define HAND_SHAKE_MODE "\033.I30;;17:"
#define EXT_AND_HAND_SHAKE "\033.N;19:"
#define INIT_DEF "IN;DF;"
#define PLOT_OFF "\033.)"
plot_init()
{
printf(PLOT_ON); /* turn plotter on */
printf(ABORT_DEV_CONTROL); /* abort partial control instruction */
printf(ABORT_GRAPHIC_INST); /* abort partial graphic instruction*/
printf(HAND_SHAKE_MODE); /* XON/XOFF handshake mode */
printf(EXT_AND_HAND_SHAKE); /* set XOFF character */
printf(INIT_DEF); /* set default conditions */
}
plot_off()
{
printf(PLOT_OFF); /* turn plotter off */
}
12.9.3. Digitizing a Point
The instructions DP, OS, and OD are required to digitize a point. Issuing the DP command tells the plotter to digitize a point. The green paper size light flashes to indicate that the plotter is waiting for a point. Move the plotter to the desired point and press enter. The OS command is required by the program to determine when the human user has digitized a point. The integer returned by the plotter will have bit 2 set when a point has been digitized. When a point has been digitized the coordinates can obtained from the plotter by issuing the OD command. This returns three integers corresponding to x,y,pen_status. An example program to digitize a point is shown below:
main()
{
int x,y,up,i,n;
int status;
system("stty -echo"); /* we don't want to echo what the plotter sends us */
plot_init(); /* initialize plotter */
printf("DP;");
while (TRUE) {
sleep(1);
printf("OS;");
scanf("%d",&status);
if (status & 4) break; /* bit 2 of status byte is set when point avail */
}
printf("OD;");
scanf("%d,%d,%d",&x,&y,&up);
plot_off();
printf("%d %d\n",x,y); /* print out pair of coords digitized */
system("stty echo");
exit(0);
}