💾 Archived View for gemini.spam.works › mirrors › textfiles › magazines › CHACKING › c-hacking20.txt captured on 2022-06-12 at 10:36:07.
-=-=-=-=-=-=-
########
##################
###### ######
#####
##### #### #### ## ##### #### #### #### #### #### #####
##### ## ## #### ## ## ## ### ## #### ## ## ##
##### ######## ## ## ## ##### ## ## ## ## ##
##### ## ## ######## ## ## ## ### ## ## #### ## ##
##### #### #### #### #### ##### #### #### #### #### #### ######
##### ##
###### ###### Issue #20
################## April 18, 2001
########
...............................................................................
Ineptitude: If you can't learn to do something well, learn to enjoy
doing it poorly.
-- "Demotivator" poster
...............................................................................
BSOUT
Hoo-ah! Time for another late (but hopefully great) issue of C=Hacking!
This issue features several nifty articles on both software and hardware
projects. There seems to be a lot of activity in the hardware area right
now, so hopefully we'll see more hardware articles in future issues.
In the software area, however...
If I may pithily berate for a moment, I'd like to observe that talking about
programming on comp.sys.cbm is -- this may come as a surprise to some -- not
the same as actually programming. I'd like to once again encourage those who
have been talking about projects, or have half-completed projects sitting
around on an FD disk somewhere, to go for it and get the job done!
Just like... um... C=Hacking (hey, it gets done... eventually...).
The format for this issue has changed a little, with all the news and stuff
moved into the previously skimpy "Jiffies" section. Therefore, this is now
just the 'me' column.
So 'me' would like to thank all the authors in this issue for their time
and effort (and patience), and all of the true C= Hackers out there for their
spirit and work and cool projects.
'Me' is also very happy to announce that he is getting married on August 17.
And heck, you're ALL INVITED (I think an SX-64 would make an excellent
wedding present, don't you?).
And finally, me still thinks the 64 is the niftiest computer ever made.
Onwards!
-Steve
.......
....
..
. C=H #20
::::::::::::::::::::::::::::::::::: Contents ::::::::::::::::::::::::::::::::::
BSOUT
o Voluminous ruminations from your unfettered editor.
Jiffies
o News, things, and stuff.
Side Hacking
o "Super/Turbo CPU VDC Hack", by Henry Sopko <henry.sopko@hwcn.org>
Normally it is not possible to access the VDC chip when using
a SuperCPU64 or Turbo CPU on a 128. The 1-wire hack described
in this article fixes that situation!
o "16K Memory Expansion for the VIC-20", by Per Olofsson
<MagerValp@cling.gu.se>. This article describes a nifty way to
add more memory to the VIC-20, along with some basic circuit
design information for the hardware neophyte (i.e. people like me!).
o "Quick Quadratic Splines", by moi <sjudd@ffd2.com>
A spline is a powerful tool for drawing a curve through an arbitrary
set of points -- for motion/animation, for arbitrary curves (like
fonts), and numerous other tasks. This article describes _quadratic_
splines and some fast C64 implementations, and includes a program
for experimenting with splines.
Main Articles
o "VIC-20 Kernal ROM Disassembly Project", by Richard Cini
<rcini@email.msn.com>
The ever-dependable Richard Cini has written the fourth article
in the quest for a complete disassembly of the VIC-20 kernal. This
installment focuses on device I/O routines: SETNAM, SETLF, OPEN,
and beyond.
o "MODs and Digital Mixing", by Jolse Maginnis
<jmaginni@postoffice.utas.edu.au>.
Josmod is a program for JOS, by Jolse, that can play Amiga MOD files
(and their newer successors). This article describes the general
functioning of the program, the layout of a MOD file, and how to mix
multiple digital samples in real-time (and hence play MODs!).
o "The C64 Digi", by Robin Harbron <macbeth@psw.ca>, Levente
Harsfalvi <levente@terrasoft.hu>, and Stephen Judd <sjudd@ffd2.com>
This article is, we hope, a complete reference on digital sampling
and the C64, including: general theory, SID hardware description,
and methods of playback (changing $d418, pulse width modulation,
and various tricks). Numerous code examples are given, along with
a program that does true 8-bit playback at 16KHz -- it requires a
SuperCPU, but it is most impressive, and chances are awfully good
that you've never heard a digi like this out of SID before.
.................................. Credits ...................................
Editor, The Big Kahuna, The Car'a'carn..... Stephen L. Judd
C=Hacking logo by.......................... Mark Lawrence
Special thanks to the folks who have helped out with reviewing and such,
to the article authors for being patient, and to all the cbm hackers that
make this possible!
Legal disclaimer:
1) If you screw it up it's your own fault!
2) If you use someone's stuff without permission you're a dork!
About the authors:
Jolse Maginnis is a 20 year old programmer and web page designer,
currently taking a break from CS studies. He first came into contact
with the C64 at just five or six years of age, when his parents brought
home their "work" computer. He started out playing games, then moved on
to BASIC, and then on to ML. He always wanted to be a demo coder, and in
1994 met up with a coder at a user's group meeting, and has since worked
on a variety of projects from NTSC fixing to writing demo pages and intros
and even a music collection. JOS is taking up all his C64 time and he
is otherwise playing/watching sports, out with his girlfriend, or at a
movie or concert somewhere. He'd just like to say that "everyone MUST
buy a SuperCPU, it's the way of the future" and that if he can afford
one, anyone can!
Richard Cini is a 31 year old vice president of Congress Financial
Corporation, and first became involved with Commodore 8-bits in 1981, when
his parents bought him a VIC-20 as a birthday present. Mostly he used it
for general BASIC programming, with some ML later on, for projects such as
controlling the lawn sprinkler system, and for a text-to-speech synthesyzer.
All his CBM stuff is packed up right now, along with his other "classic"
computers, including a PDP11/34 and a KIM-1. In addition to collecting
old computers Richard enjoys gardening, golf, and recently has gotten
interested in robotics. As to the C= community, he feels that it
is unique in being fiercely loyal without being evangelical, unlike
some other communities, while being extremely creative in making the
best use out of the 64.
Robin Harbron is a 28 year old internet tech support at a local
independent phone company. He first got involved with C= 8-bits
in 1980, playing with school PETs, and in 1983 his parents convinced
him to spend the extra money on a C64 instead of getting a VIC-20.
Like most of us he played a lot of games, typed in games out of
magazines, and tried to write his own games. Now he writes demos,
dabbles with Internet stuff, writes C= magazine articles, and, yes,
plays games. He is currently working on a few demos and a few games,
as well as the "in-progress-but-sometimes-stalled-for-a-real-long-time-
until-inspiration-hits-again Internet stuff". He is also working on
raising a family, and enjoys music (particularly playing bass and guitar),
church, ice hockey and cricket, and classic video games.
Levente Harsfalvi is a 26 year old microcontroller programmer who works at
a small local company. His first C= encounter was a Plus/4 at school, at
the age of 12, and later (1988) his parents bought a C-16. After learning
BASIC and ASM coding he joined a Plus/4 demo group (GOTU, and later Coroners),
and has worked on game conversions, an FLI editor, music software (including
a SID emulator to play c64 music on TED) and numerous other software and
hardware projects. More recently he has begun taking some measurements on
the Plus/4 to figure out things such as how the sound generator works and is
working on a C-16 demo. Outside of the C= he enjoys cycling and running,
and ~50km walking tours.
For information on the mailing list, ftp and web sites, send some email
to chacking-info@jbrain.com.
While http://www.ffd2.com/fridge/chacking is the main C=Hacking homepage,
C=Hacking is available many other places including
http://www.funet.fi/pub/cbm/magazines/c=hacking/
http://metalab.unc.edu/pub/micro/commodore/magazines/c=hacking/
................................... Jiffies ..................................
$01 Not _too_ long ago, an effort was made to write down the pin assignments
for the video port of all the major C= computers. The result, as compiled
by William Levak <wlevak@cyberspace.org>, is:
8 7
Commodore 6 Video Connector
3 1
5 4
2
Plus4 C16/C128
CBM-II VIC20 VIC20CR C64 Pin C64A/SX64 C64B/C/E
--------- ------------ ------- ---------- --- ---------- ----------
(R) Luminance +5 V +5 V Monochrome 1 Monochrome Monochrome (Y)
Ground Ground Ground Ground 2 Ground Ground
(B) V. Sync. Audio Audio Audio 3 Audio Audio (W)
(W) Video 50 Ohm Video Video Video 4 Video Video
(Y) H. Sync. Video Video Audio In 5 Audio In Audio In
6 Chroma Chroma (R)
7
8 +5 V
$02 "Professor Dredd" <profdredd@yahoo.com> has uploaded the programs
from "Inside Commodore DOS" to his webpage at
http://www.geocities.com/profdredd
$03 Todd Elliot has written a version of Pasi Ojala's zip/unzip program
for GEOS/Wheels, available at:
http://www.cs.tut.fi/~albert/Dev/gunzip-geos/
$04 Jeri has been hard at work on her video/cpu-board:
http://www.geocities.com/cm_easy/
$05 Jolse has been hard at work on JOS (but you'll have to wait until next
issue for the article!):
Here's the latest Jos news:
Support for CMD HD, including native partitions. (Read only atm, and no
1581 partitions)
Enhanced shell with filename completion and recursive wildcards.
Improvements to the GUI - the architecture now allows for a different
window interface styles transparent to the application.
Numerous showstopper bugs killed.
Improvements to the httpd server to allow directory listings.
Swiftlink/T232/Duart drivers.
Started writing tutorials for programmers wanting to give Jos a go.
Plus heaps more things not worth mentioning..
cya!,
Jolse
$06 Philip 'Pepto' Timmermann has made some very accurate measurements
(and RGB calculations) of VIC-II colors:
http://www.pepto.de/projects/colorvic/
$07 And finally, I have written a 2D graphics library for use by assembly
language programs (plot points, draw lines and circles, that kind of
thing). It's super-easy to use and pretty fast, so go ahead and use it
if you need some hires drawing routines!
For more information, pop on over to
http://www.ffd2.com/fridge/grlib/
................................ Side Hacking ................................
Super/Turbo CPU VDC Hack
for
Commodore 128 with SuperCPU 64 or Turbo Master CPU Accelerators
by Henry Sopko
(henry.sopko@hwcn.org)
As many of you probably know, accessing the VDC (8563) chip is not
possible when using a SuperCPU 64 (version 1 tested only!) or the
TurboMaster CPU (latest revision), until now. With this 1 wire hack,
you can have access to the C128 (flat only tested) VDC 80 column
chip with your SCPU 64 or TurboMaster CPU!
DISCLAIMER
--------------------------------------------------------------------
I take no responsibility whatsoever to any damage that may occur to
your Computer or SCPU 64/TM CPU resulting from this hardware hack!
You do this hack totally at YOUR OWN RISK!
[C=Hacking disclaimer: if you screw it up, it's your fault!]
--------------------------------------------------------------------
This hack was only tested on a flat C128, using CMD's SCPU 64 (version 1).
Tested also was the Turbo Master CPU 4.09 MHz accelerator from Schnedler
Systems (latest revision).
Parts required: (1) long wire (12 inches or so, cutting it to length).
INSTRUCTIONS
Dissassemble your C128, taking the metal shield completely off. With the
motherboard exposed, find the 8563 VDC chip (U22). After locating this chip,
remove it (take note of the notch position, so you correctly re-insert the
chip). Bend out PIN 9 (R/W) of the 8563 just enough so it does not touch the
socket or any metal (in the flat 128, theres not much room, so be carefull).
Now re-insert the 8563 chip. Take a wire (you can either solder the wire to
pin 9 as I did, or use Microclips -- your choice). Now, connect the wire by
soldering or using Microclips to PIN 5 on the CARTRIDGE EXPANSION PORT. Thats
it!
I have done this hack quite a while ago without any signs of problems
whatsoever. The C128 functions the same with or without a SCPU 64 or TM CPU
connected after preforming this hack. I really did this hack for the Turbo
Master CPU so I could access the VDC. Turns out, that the SCPU 64 accelerator
(and maybe others?) work with this hack as well. The better choice of course
is to buy a CMD SuperCPU 128 to take full advantage of the Commodore 128 in
both modes!
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
16K Memory Expansion for the Vic-20
By Per Olofsson <MagerValp@cling.gu.se>.
Thanks to Ruud Baltissen, Pasi Ojala and Spiro Trikaliotis for help and
suggestions. The latest version of this project may be found at
http://www.cling.gu.se/~cl3polof/64.html.
I tried to keep the expansion as simple as possible, requiring no chips
besides the two memory chips, and a minimum of soldering. It uses two 6264
SRAM chips (62256 also works) piggy-backed to the Kernal and Basic 2364
ROMs. It's recommended that you do the expansion one chip at a time, as this
greatly simplifies troubleshooting. After the first chip checks out OK, do the
second one. I'll start out by explaining a few basic principles.
o Static Electricity
We'll be using CMOS RAM chips, and they are very sensitive to static
electricity. If you don't have an anti-static wrist strap, make sure you touch
a grounded surface before you touch the chips. Do not work sitting on shag
carpet in a mohair sweater while petting the cat :)
o Be Careful With ICs
ICs are sensitive to heat, and keeping the soldering iron for too long on a
pin can toast the chip. If you need to redo a solder joint on a pin, wait for
it to cool down first.
o Up, Down, and Pin Numbering
The top of a DIP IC (the kind used in Vic-20s) is marked with a small notch,
looking something like this:
___ ___
1 =| V |= 8
2 =| |= 7
3 =| |= 6
4 =| |= 5
`-------'
As you can see, the pin numbers start at 1, and the first pin is the top left,
going down to the bottom left, then from the bottom right to the top right.
Piggy-backing
-------------
Piggy-backing is a quick way of adding another IC on top of an existing
one. Normally you would create a PCB with chip sockets, connect it to the
expansion port and populate it with memory chips, but with piggy-backing you
simply add chips on top of internal ones. This works when the new chip's pins
has signals that are identical to, or closely matches, the layout of the one
it's being mounted on top of.
6264 RAM
___ ___
2364 ROM NC 1 =| V |= 28 Vcc
___ ___ A12 2 =| |= 27 /WE
A7 1 =| V |= 24 Vcc A7 3 =| |= 26 CS2
A6 2 =| |= 23 A8 A6 4 =| |= 25 A8
A5 3 =| |= 22 A9 A5 5 =| |= 24 A9
A4 4 =| |= 21 A12 A4 6 =| |= 23 A11
A3 5 =| |= 20 /CS A3 7 =| |= 22 /OE
A2 6 =| |= 19 A10 A2 8 =| |= 21 A10
A1 7 =| |= 18 A11 A1 9 =| |= 20 /CS1
A0 8 =| |= 17 D7 A0 10 =| |= 19 D7
D0 9 =| |= 16 D6 D0 11 =| |= 18 D6
D1 10 =| |= 15 D5 D1 12 =| |= 17 D5
D2 11 =| |= 14 D4 D2 13 =| |= 16 D4
Vss 12 =| |= 13 D3 Vss 14 =| |= 15 D3
`-------' `-------'
As you can see there are 8 that don't match. However, we don't have to rewire
all of them. NC means "No Connection" so we can just ignore that pin. Note
that if you're using 62256 chips you'll have to wire this one too, see
below. We want to connect CS2 to Vcc, and we'll also swap A11 and A12, leaving
5 pins to solder on each chip. Swapping address bus pins works on RAM chips,
as it only affects how bits are stored internally -- when you read them out
again, they're swapped back. This also works for the databus.
We'll mount one 6264 on top of the Kernal ROM, and one 6264 on top of the
Basic ROM. The ROMs are marked UE11 and UE12 and can be found in the bottom
right of the motherboard. The wiring is identical for the two chips, except
for the /OE and /CS1 pins. The pins that we want to rewire we carefully bend
up so that they don't connect to the ROM. You want to bend them almost all the
way up (about 150 degrees) so that you can reach them with the soldering
iron. The pins are very sensitive, so make sure you bend the right pins --
bending a pin back again could easily break it.
Sometimes the pins on the RAM are too wide apart to make a good connection
when you piggy-back it. In this case, bend all the pins on the RAM slightly
inwards. You can do this by putting it on the side on a flat, hard surface and
press gently.
o Soldering A11/A12 and Vcc
You could get A11, A12, and Vcc from several places on the motherboard, but as
they're available on the ROMs we'll just solder small wires from the ROM to
the RAM. Remember that we're swapping A11 and A12, so connect pin 18 on the
ROM to pin 2 on the RAM. Connect pins 26 and 28 on the RAM to eachother.
o Soldering /WE
Pin 27 on the RAMs should be connected to pin 34 on the 6502 CPU. The CPU is
the 40-pin chip in socket UE10 on the motherboard, right next to the ROM
chips. Pin 34 is the 7th pin if you count from the top right pin on the CPU.
o /OE and /CS1
In the Vic-20 memory is divided into 8 blocks of 8K each. Block 0 is further
divided into 8 1K blocks, of which 5 are populated with RAM. Block 4 is used
by the VIC and the VIA chips, block 6 is the Basic ROM, and block 7 is the
kernal ROM. This leaves four blocks (1, 2, 3 and 5) available for cartridges
and RAM expansions. For RAM to be visible to the basic interpreter, you must
start by adding ram in block 1, then 2 and then 3. RAM in block 5 is never
detected by the basic. 8K cartridges use block 5, and 16K cartridges use block
5 together with another one, usually 3. To be as compatible as possible with
existing cartridges and to expand basic memory I'll use block 1 and 2 for this
expansion, but you could use any two of the available blocks you want. I've
added instructions for making the blocks selectable by switches below.
The block signals are available on the 74LS138 decoder chip marked UC5 on the
left side of the motherboard. Block 1 is on pin 14, block 2 is on pin 13,
block 3 is on pin 12 and block 5 is on pin 10. If you look closely you'll see
that the signals for block 1 and 2 go out from the chip a few mm to a small
pad. It's much easier to connect your wires to these pads than the pins on the
decoder chip. Solder a wire from block 1 to pin 20 and 22 on the first RAM
chip, and a wire from block 2 to pin 20 and 22 on the second RAM chip.
You're done!
That's all. When you power up the Vic-20, you should be greeted with a 19967
BYTES FREE message. If you've only done one chip so far, you'll get 11775
BYTES FREE, provided you connected it to block 1. If you've connected memory
to other blocks but not block 1, you'll just get the normal 3583 BYTES FREE
message. To test your memory, try this program:
10 input "test which block";b
20 s = b*8192 : t = s+8191 : e = 0
30 print "testing databus"
40 for a = s to t : poke a, 85 : if peek(a) 85 then gosub 1000
50 poke a, 170 : if peek(a) 170 then gosub 1000
60 next : de = e
70 e=0 : print "testing high address bus"
80 for a = s to t : poke a, int(a/256) : next
90 for a = s to t : if peek(a) int(a/256) then gosub 1000
100 next : he = e
110 e=0 : print "testing low address bus"
120 for a = s to t : poke a, a and 255 : next
130 for a = s to t : if peek(a) a and 255 then gosub 1000
140 next : print
150 print de;"errors found in databus test"
160 print he;"errors found in high address bus test"
170 print e;"errors found in low address bus test"
999 end
1000 e = e+1 : print "error at";a : return
The program takes a couple of minutes to run.
Troubleshooting
---------------
The computer doesn't start at all, or all you get is a black screen
You've probably shorted or toasted something. Not good, this could
have damaged the computer. Recheck all your soldering and make sure
that you haven't accidentally connected something wrong.
The computer powers up with 3583 bytes free
Memory in block 1 is either not connected or not working. Check the
connections between block 1, /CS1 and /OE, between R/W and /WE, and
between Vcc, CS2 and Vcc.
The computer powers up with something other than 3583, 11775 or 19967 bytes
free
Memory is functioning partially, check A11 and A12. This could also
indicate that a RAM chip is faulty.
The computer powers up with the correct number of bytes free, but the memory
test program fails
Memory is functioning partially. If the databus test fails, check the
connections between block 1, /CS1 and /OE, between R/W and /WE,
between Vcc, CS2 and Vcc, and D0 through D7. If the address bus test
fails, check A0 through A12.
Using 62256 chips instead of 6264
---------------------------------
You can freely substitute 62256 chips for the 6264. Only two pins differ:
6264 RAM 62256 RAM
___ ___ ___ ___
NC 1 =| V |= 28 Vcc A14 1 =| V |= 28 Vcc
A12 2 =| |= 27 /WE A12 2 =| |= 27 /WE
A7 3 =| |= 26 CS2 A7 3 =| |= 26 A13
A6 4 =| |= 25 A8 A6 4 =| |= 25 A8
A5 5 =| |= 24 A9 A5 5 =| |= 24 A9
A4 6 =| |= 23 A11 A4 6 =| |= 23 A11
A3 7 =| |= 22 /OE A3 7 =| |= 22 /OE
A2 8 =| |= 21 A10 A2 8 =| |= 21 A10
A1 9 =| |= 20 /CS1 A1 9 =| |= 20 /CS1
A0 10 =| |= 19 D7 A0 10 =| |= 19 D7
D0 11 =| |= 18 D6 D0 11 =| |= 18 D6
D1 12 =| |= 17 D5 D1 12 =| |= 17 D5
D2 13 =| |= 16 D4 D2 13 =| |= 16 D4
Vss 14 =| |= 15 D3 Vss 14 =| |= 15 D3
`-------' `-------'
Pin 26 (A13) can be connected to Vcc just like on the 6264, but we need to
wire pin 1 (A14) to either Vcc, Vss or another address bus pin. It's probably
easiest to wire it to pin 2 (A12). We won't be using the greater capacity of
the 62256 using this method (doing so would require some kind of decoder
logic) but sometimes 62256 chips are cheaper than 6264, or maybe you just have
some lying around.
Adding Block Select and Write Protect Switches
----------------------------------------------
Adding block select switches allows you to chose which blocks should be
populated on the fly. This allows you to chose between a basic expansion and a
"cartridge emulator" that allows you to load cartridge images into ram and run
them. I added one switch for each chip, giving the first chip the option
between block 1 and 3, and the second between 2 and 5.
block 1 -----o
\
o----- to /CS1 and /WE on chip 1
block 3 -----o
block 2 -----o
\
o----- to /CS1 and /WE on chip 2
block 5 -----o
As a kind of copy protection, some cartridge images try to modify themselves
to detect if they're running from RAM. If we add write protect switches we'll
be able to run those as well. Switch to write enabled while loading, then
switch to write protected and reset.
R/W -----o
\
o----- to /WE on chip 1
+5 V -----o
R/W -----o
\
o----- to /WE on chip 2
+5 V -----o
+5 V is the same as Vcc.
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Quick Quadratic Splines
----------------------- S. Judd <sjudd@ffd2.com>
Splines are neat.
Splines are a way of drawing curves -- specifically, drawing a curve through
any set of _points_ that you choose; for example, a curve that starts at (0,0),
goes over to (100,50), then loops back to (50,0), and continues on through
any number of points can be drawn just by specifying the points.
This is a very useful thing! One place splines are used is in drawing fonts.
With a relatively small list of points, it becomes possible to draw letters
in arbitrary shapes (and scale those shapes easily). Another application
is animation -- it is possible to specify a long motion path using just
a few points along the path. Furthermore, an animated object might have
different parts that move differently -- arms, legs, head, etc. By just
specifying a few frames of the animation, splines can be used to generate
the in-between frames.
Chances are good that by now you are thinking about some of your own
applications for splines, so let's see how they work.
Most articles/books/etc. that talk about splines talk about "cubic splines".
This article is going to talk about "quadratic splines", which never seem
to be mentioned. Which is a pity, since quadratic splines are perfectly
adequate for many (if not most) spline applications and are far more
computationally efficient.
Graphically, a two-dimensional quadratic spline looks something like:
* P1
/ \
/ \
/ \
/ . . \
/ . . \
/. .\
/. .
/. * P2
.
.
P0 *
(Another brilliant display of ASCII art). The curve starts at P0, moves
towards P1, and then turns around and heads towards P2, where it ends. If
we draw lines from P0 to P1 and from P1 to P2, these lines are tangent to
the curve at the endpoints P0 and P2; that is, these lines say what
"direction" the curve is going at the endpoints. Using the above diagram,
it should be very easy to visualize how changing P1 changes the shape of
the curve.
So here, for your computing pleasure, is a quadratic spline:
P(t) = P0*(1-t)^2 + 2*P1*t*(1-t) + P2*t^2
where P0, P1, P2 are constant values, and t ranges from zero to one. If
you don't like equations, then how about a computer program to compute
the above:
10 P0=10:P1=100:P2=37
20 FOR T=0 TO 1 STEP 1/16
30 PRINT T,P0*(1-T)*(1-T) + 2*P1*T*(1-T) + P2*T*T
40 NEXT
This is actually very easy to understand. When t=0, P(t) = P0. As t starts
to increase, (1-t) starts to decrease and P(t) starts moving towards P1. As
t gets even larger P(t) starts moving towards P2, until finally, at t=1,
P(t) = P2.
You may be wondering why there is that 2*P1 in the equation, instead of
just P1, but that will become apparent shortly.
At this point there is an important thing to notice about the above
equations: adding _any_ constant to P0 P1 and P2 is just like adding the
constant to the entire spline P. Let P0=P0+C, P1=P1+C, P2=P2+C; the
spline is then
P'(t) = (P0+C)*(1-t)^2 + 2*(P1+C)*t*(1-t) + (P2+C)*t^2
= [ P0*(1-t)^2 + 2*P2*t*(1-t) + P2*t^2 ] + C*[(1-t)^2 + 2*t*(1-t) + t^2]
= P(t) + C
This is one reason that factor of 2 multiplying P1 is important -- it makes
the expression multiplying C add up to 1. This property means that splines
can be _translated_ easily. Note that one value you can translate everything
by is P0 -- subtract P0 from each point and the spline becomes
P(t) - P0 = 2*(P1-P0)*t*(1-t) + (P2-P1)*t^2
and hence
P(t) = 2*(P1-P0)*t*(1-t) + (P2-P1)*t^2 + P0
which gets rid of the P0*(1-t)^2 term. Depending on how the spline algorithm
works, this can save some computation time.
Now, the points P0, P1 etc. are called "control points". If you're on the ball
(or if you've tried the BASIC program above) you've noticed that while the
spline starts at P0 and ends at P2, it never actually reaches P1 -- it just
heads towards it but then heads away towards P2. If a different P1 is
chosen, the spline still starts at P0 and ends at P2 but takes a different
path between the endpoints. P1 controls the shape of the curve.
So now let's say we want a curve that passes through three points, s0, s1,
and s2, using a quadratic spline. P0 and P2 are easy to choose:
P0 = s0
P2 = s2
P1 can actually be chosen at this point to be any number of points. All we
do is choose a value for t -- call it t1 -- when the spline should hit s1:
P(t1) = s1 => P1 = (s1 - P0*(1-t1)^2 - P2*t1^2) / (2*(t1*(1-t1))
(just substitute t=t1 into the equation for P(t) and solve for P1). So if
t1=1/2, say, then
P1 = (s1 - P0/4 - P2/4) / (2 * 1/4)
= 2*s1 - (P0 + P2)/2
and the spline will hit s1 halfway through the iteration at t=1/2.
In a typical application, of course, the curve will need to go through tens,
hundreds, even thousands of points. Naturally, the way to do this is by
joining a bunch of splines together.
If we just choose a spline for every three points, using the above equation
for P1, there will typically be sharp corners where the splines join
together. Sometimes this is a good thing -- for example, when drawing
something like a valentine we might want sharp corners. But usually
what is needed is a nice smooth curve through all the points.
With quadratic splines this is a piece of cake. Each spline has three
control points: the two endpoints, and the middle control point P1. The
endpoints are simply chosen to be the points we want to pass through,
and P1 can then be chosen to make all the connections smooth.
That is, given a list of points s0, s1, s2, ... to put a curve through,
choose s0 and s1 to be the endpoints of the first spline, s1 and s2 to
be the endpoints of the second spline, and so on, and choose the middle
control points to make everything smooth.
"Smooth" here means a continuous first derivative -- if you don't know what
a derivative is then don't worry about it, it just means that the "slope" of
each spline is the same where they join together. Given a spline
S1(t) = P0*(1-t)^2 + 2*P1*t*(1-t) + P2*t^2
the derivative at t=1 is given by
S1' = 2*(P2 - P1)
P2-P1 is simply the line segment running from P1 to P2, which verifies what
was said earlier: at P2 the curve is tangent to a line drawn from P1 to P2.
* P1
/ \
/ \
/ \
/ . . \
/ . . \
/. .\
/. .
/. * P2
.
.
P0 *
P2-P1 is the direction the curve is headed in. So to join another spline
smoothly to the first one, simply extend this line segment and make sure
the second middle control point lies somewhere on that line:
* P1
/ \
/ \
/ \
/ . . \
/ . . \
/. .\
/. .
/. * P2
. . * P5
. \. ./
P0 * \ ../
\ /
* P4
Since the first spline is tangent to P2-P1, and the second spline is tangent
to P4-P2, the two splines have the same slope at P2, and join smoothly.
Note that P4 can be _anywhere_ along the P2-P1 line, and choosing different
values for P4 will change the curve.
To make this more precise, let the two splines be given by
S1(t) = P0*(1-t)^2 + 2*P1*t*(1-t) + P2*t^2
S2(t) = P3*(1-t)^2 + 2*P4*t*(1-t) + P5*t^2
To join them smoothly, the slope of the first spline must be proportional
to the slope of the second spline at the joint:
P4-P3 = c*(P2-P1)
where c is some constant (the _direction_ of the two slopes need to be the
same, but not the magnitude). So, to make the second spline fit smoothly
to the first we simply choose the middle control point P4 as
P4 = P3 + c*(P2-P1)
or, in plain English, starting from P3 (the joining point) move some
distance c in the direction P2-P1. To see why the factor c is important
just scroll up a page or two to the diagram, and imagine how the curve
changes as P4 slides back and forth along the line.
We now have the tools to construct a smooth curve that passes through any
points s0, s1, s2, s3, ... Let the first spline pass through s0, s1,
and s2, using the t=1/2 formula given earlier:
P0 = s0
P1 = 2*s1 - (s0 + s2)/2
P2 = s2
P1 could be chosen in other ways, of course, but the above usually works
pretty well. Then choose each succeeding spline to match up smoothly with
the previous spline:
P3 = s2 ;start at spline 1 endpoint
P4 = P3 + c1*(P2-P1) ;smooth joint
P5 = s3 ;next point
P6 = s3
P7 = P6 + c2*(P5-P4)
P8 = s4
and so on. (When drawing smooth curves, it is of course really only
necessary to store the middle control points P4 P7 etc. for each spline).
The choice of the constants c1 c2 etc. really depends on how you want the
curve to look.
As you can see above, each extra point requires another spline. One spline
per point may sound like a lot, but there are a lot of pixels in-between each
pair of points, and more importantly these are quadratic splines and hence
can be made to go very, very fast.
Computing the spline
--------------------
Note that the control points are one-time calculations; those three constant
values completely determine the spline. One way of drawing the spline is
to use some lookup tables for t^2, 2*t*(t-1), and (1-t)^2 and do a little
fast multiply magic. This is fast and straightforward, so I won't talk
about it much except to mention that signed multiplies may be required,
and each curve is limited to 256 points (t can go from 0 to 255 in the
lookup tables). Note also that it would be nice to have an "incremental"
plot routine, i.e. one that just updates pointers when necessary, instead
of recomputing all the bitmap pointers at every iteration.
Which of course brings us to a second way of drawing the spline: to ask
"how does the spline change when I increment t?"
Let's say that t is incremented by dt at each step (t -> t+dt). At each
step, then, the spline changes by
S(t+dt) = P0*(1-t-dt)^2 + P1*2*(t+dt)*(1-t-dt) + P2*(t+dt)^2
= S(t) + k1*dt^2 + k1*2*t*dt + k2
where k1 = P0 - 2*P1 + P2 and k2 = 2*dt*(P1 - P0). That is, to advance one
step, we add
k1*dt^2 + 2*k1*t*dt + k2
to the current value. Take a look at how the above value changes as t
changes:
t k1*dt^2 + 2*k1*t*dt + k2
-- ------------------------
0 k1*dt^2 + k2 = k1*dt^2 + k2
dt k1*dt^2 + 2*k1*dt^2 + k2 = 3*k1*dt^2 + k2
2*dt k1*dt^2 + 4*k1*dt^2 + k2 = 5*k1*dt^2 + k2
3*dt k1*dt^2 + 6*k1*dt^2 + k2 = 7*k1*dt^2 + k2
and so on. This means that all we have to do to advance the spline is
something like
c0 = k1*dt^2
C = c0 + k2
S = P0
:loop
S = S + C
plot S
C = C + 2*c0
loop
Which is really, really fast. Instead of specifying the spline with the
three values P0, P1, and P2 we can specify it by the three values P0, k1,
and k2.
It is possible to understand this iterative method somewhat. The update
constant k1 can be written as
k1 = (P0-P1) + (P2-P1)
whereas k2 goes like
k2 ~= (P1-P0).
P1-P0 is the "direction" line segment towards P1, so the curve starts moving
towards P1. But k1 starts to balance that out with the P0-P1 term (the line
segment pointing in the opposite direction), while moving towards P2 with the
P2-P1 term, which is the direction line segment from P1 to P2. Now, isn't
that all nice and clear now?
The Program
-----------
At the end of this article I've included a sort of "spline laboratory" --
it's a little BASIC program that lets you experiment with different aspects
of splines and see what they look like. It uses BLARG for the graphics, so
I've included that as well.
When you run it, it plots three points on the screen to draw a curve through.
You can move these points around, as well as add new points, draw the splines,
draw the control point "a-frames", and so on. It has a ton of commands,
basically because I just added them as I got curious about different things:
+/- Move to next/previous point
cursor keys Move current point
return Draw spline
space Clear screen