Notes on Goodbye My Friend

Writing and production history

This song was written in May, 2019 as a farewell to Tom Hedges who died in November of 2007. I worked with him for 30 years and we became business partners at Fractal Design, where we created Painter, ImageStudio, ColorStudio, and other great products. The song is all guitars, bass, and drums (aside from vocals). Tom was a Beatles fan, and he liked John Lennon. Lennon mainly respected rock songs that used the traditional rock instruments, so that's why I arranged the song this way. I also altered my voice like Lennon, who always wanted something different. The song chronicles many memories, and tries hard to show how much he influenced me.

It starts with a chorus, with the drum setting the tempo and an iconic guitar riff, subtly fuzzed. In the background are some descending chromatic vocals. Slow arpeggiations on a clean guitar trace out the harmony in a wistful way while the drum fills get your attention.

The first verse sets the scene. He was, at first, my mentor, but eventually I took over as lead coder. Apps took over in importance and salability. The B-section of the first verse chronicles our relationship - we fought over lots of things but always somehow remembered to be friends the next day.

The second verse talks about how we were the progenitors of our software Apps. But we didn’t write them all — others helped write them like John Derry (UI and brushes), Bob Lansdon (watercolors), Priscilla Shih (general coding), Shelby Moore (PC version, multi-point color fills), Glenn Reid (R&D Management), Christina Hall (general coding), Vahe Avedissian (general coding), Scott Cooper (general coding), Erik Johnson (general coding), and our Ray Dream friends, Damien Saint-Macary (web features), François Huet (web features), and Nicholas Barry (Web features). These were the people that actually touched the code (and there were a few more I can’t recall). These were “our loyal crew”. And they were awesome!

But our loyal crew also consisted of a few more people who were instrumental to the development of the complex software base. For instance, Michael Cinque, who headed QA and Steve Rathmann, an early hire that always adapted to the task.

In the B-section of the second verse, the tale of difficulties competing against the software giant Adobe gets told. We fought the Painter fight ten years. All through the time, Tom’s health got worse and worse. He was diagnosed with Non-Hodgkin’s lymphoma in 1989, went into remission, had it flare up in 1995, and went into remission again. However, his radiation therapy treatments ended up creating a spreading neuropathy that started with his hands, and eventually affected his lower arms, and then his whole arms (by 2005) and finally his lungs.

We believe what caused this was his brief tenure as KSJO’s chief engineer. He spent a lot of time in the Optimod room up near the peak of Mt. Hamilton, where their radio antennas and microwave transmitters resided. I went in there once (but only once). You could literally feel the radiation.

KSJO's Antenna Tower - Next to the Optimod shack

He also had a spectacular lack of good luck with the women in his life. And I’ll say no more about that (for now).

Reprise references

The reprise from this song contains a dozen references to arcana from Tom’s life and the time we shared. Here, I’ll pick it apart, line by line.

Remember the days in Boston town

Tom and I were Fractal Software, a partnership, in 1986-1989, with Letraset as our marketers. We often traveled to Boston for the MacWorld East show, to show our product. Letraset had demo artists and a medium-sized booth. Later on, Fractal Design, the company that Tom and I had a hand in founding (along with Steve Manousos, Lee Lorenzen, and Steve Thomas), had a much larger booth presence. Tom and I would arrive in August in Boston, set up shop in a nice hotel, hit the bar, and wait for the other people showing products to arrive. It became a growth period for both of us.

Remember the day we lost our friend

Bob Lansdon was our odd friend from academia. He was constantly in search of a PhD in math. There was no doubt he was smart. Bob introduced me to Fourier transforms, and taught me how to vary the phase of the frequency signal, an incredibly useful trick. He and I dreamt of laser interferometry for measuring paper surface texture. Bob wrote the first watercolor capability in Painter. One day in 1994, Bob came into Fractal Design the office on Spreckels Drive in Aptos, and into the suite where Tom, John Derry, and I had our desks, and we talked for a bit. He had completed his PhD, finally after all these years (his thesis advisor was Ralph Abraham). We were a busy group and he left. A few days later we learned of his suicide. When I announced it to the new at Fractal, that was one of the few times I actually cried in front of the company I ran.

Remember how Water Tank went down

In the early 1990s, Tom was married to Joanne Etheridge (née Stoner) and they became a couple. They had two kids, Colin and Broghan. By the late 1990s, the relationship between Tom and Joanne was strained for a reason I never knew. It might have been Tom’s personality, which was a wee bit crude for many people’s taste. I don’t know. But there was a point where Joanne hired her parents, both real estate agents, to get them a second home. They bought a house on Water Tank Road in La Selva. To me as an observer, I felt that their strained relations, compounded with the fact that Joanne was literally creating a bachelor pad for Tom, meant that they were headed for divorce. But somehow Tom never saw it.

Remember the goldfish bowl and then

WhenI first met Tom Hedges at Calma Company in 1974, he was an RA at Stanford with his first wife, Rabbit (I never learned her name). So he came in late because those were his remaining working hours. I had been hired at Calma (at 4 bucks an hour, by Art Collmeyer) as an applications programmer for a new APL-based language (called GPL) that Carl Smith was creating. I needed a real workstation to do the work I was doing (which usually involved not doing what I was supposed to do). I was working on a demo of a rotating dodecahedron with hidden lines suppressed that ran on a Tektronix storage scope. One night Tom and Bruce Holloway, high as a kite, entered the demo area at Calma, which was surrounded by glass, and hence its name “the goldfish bowl”. They hopped on to the wheeled chairs and scooted themselves across the demo space, very close to me, and said “boo!”. I barely looked up from my code, which irked them a tiny bit. But they just kept abusing the 5-wheeled chairs, skating to and fro. It was a funny time for me, to be sure.

Remember the wall-sized plots we made

Tom introduced me to Bob Lansdon as a one time co-resident of Ruddock house in their days at Caltech. I myself was a Page house resident, but a few years later on. Bob was a shy nerd who rarely spoke. But he knew his math. At Calma one night, with access to a brand new Versatec raster printer, with four-foot-wide rolls of paper, they decided to make a plot. Tom suggested that the plot be of a nice mathematical function. Bob suggested a Fourier transform of a set of points on the unit circle (I think it was 9-point). A gigantic plot was produced and it hung on the walls for a time. I've recreated the plot here.

The end of your set you played that song

Tom worked for KZSU, the Stanford radio station as a DJ for a while in the 1970s. He divorced his first wife Rabbit (she was unfaithful to him I heard) and married Carolyn Foster. At the end of his DJ set at KZSU, Tom always played a song “Sweet Caroline” by Neil Diamond as a tribute to her.

Remember how partner’s draw was great

Tom and I were partners in Fractal Software from 1985 to 1990. When we got Letraset as a marketer was when we met Marla Milne, a product manager from Soho in New York. She spotted my demo of Gray Paint at a party thrown by Marc Canter. Once we built our first image editing App, ImageStudio, the royalty checks started coming in once a quarter. When they arrived, we deposited the check and then each drew out half of the check in “partner’s draw”. We bought houses on those checks and bought our first BMWs.

Remember how Cheshire cowed your dog

Tom and Caroline had a large German Shepherd mix, Pokey. It was a huge dog. One day they came to visit me and Ruth Zimmer (née Rasmussen), my second wife at our house in Evergreen. Ruth’s old black cat was named Cheshire and it was, let’s say, a bit strong-willed. Once Pokey came through the door, Cheshire pounced! Cheshire, with one tenth the body mass of Pokey, soon had Pokey literally cowering in the corner by the door. Poor dog!

Remember the Gershwin rhapsody

Tom’s dad, who had passed by the time we became partners in Fractal Software, was an avid pianist. He often played the Gershwin Rhapsody in Blue. When Tom and I met Ed Bogas (Steve Capps introduced us, I think) and his crew of musicians and programmers in the mid-1980s (including Neil Cormia and Ty Roberts), we both got interested in the possibilities of music and computers. We were tasked to sample a piano, so we did exactly that and produced an 88-key set of sound samples. I had created a program that could play MIDI format, triggering sound samples, and mimicking the sustain pedal and Tom laboriously keyed in the Gershwin Rhapsody so we could play it back. He also keyed in Wasted on the Way by Crosby, Stills, and Nash. With the Rhapsody, I think Tom was literally constructing a tribute to his Dad.

Remember when Painter saved the day

Tom and I had both profited from ImageStudio and ColorStudio, both Letraset-branded products, because we received royalties from their international sales. One day in 1990, we got a call from Letraset’s General Manager Jack Forbes who told us they were getting out of the software business in North America. I had been working on Painter for 11 months at my home (in secret). I chose that day to introduce it to Tom. He and I both thought it had definite possibilities, so we contacted some friends and started Fractal Design.

Remember the exit strategy

Tom, John, and I worked on Painter for nearly ten years. The board of directors had hired me back as CEO (of MetaCreations) and ordered me to sell off the software. Which I proceeded to do. It was an unpleasant time for me. But as it happened, we sold Painter and associated products to Corel and set up a consulting gig with them for the three of us. That was our exit strategy. It wasn’t planned.

Remember neuropathy’s dismay

All through our time when Fractal Design was in Scotts Valley, Tom Hedges began experiencing neuropathy in his hands. This was a result of his radiation therapy in 1898 for Non-Hodgkin’s lymphoma, an aggressive cancer. Unfortunately his radiation therapy had to be concentrated on his lymph nodes in his neck. At first he had problems typing. Now, Tom was always a two-finger typist to begin with. Eventually it cost him his productivity. Later on, it cost him the use of his arms.

Remember the picture Marla made

In 1985, we built ImageStudio, to be distributed by Letraset. Marla Milne was our product manager. Tom had a picture of his family. Tom also had a chipped tooth. Marla, as a joke, scanned that image and applied Tom’s chipped tooth to all his other family members. When I saw it, I had a laugh for about an hour. What a crazy, disrespectful idea. After I had my laugh, I said “Bummer, man” to Tom and resumed my coding. It was a thing we did. The funny thing was that Tom had that chipped tooth fixed within a week.

Remember the sadness near the end

On Tom’s 57th birthday. He had a small gathering in his local pub, CB Hannigan’s. Tom’s arms hung limp at his sides because of his neuropathy. He and I spoke for fifteen minutes or so. His situation was not good since his lungs’ function was finally being impaired by his neuropathy. I listened to his situation and gave my final “Bummer, man” to him. He smiled (the only time that day I saw a smile from Tom) and we drank our beers. Mine was from a mug. His was from a tall glass with a long straw. It was a sad moment.

Remember the time you were betrayed

Really it was the “times” he was betrayed. But this line is referring to his months-long relationship with a woman known as “Yolanda”. She wasn’t straight with him. He took her to Tahiti on one vacation I remember, and lavished her with jewels and such. But as It turned out, she had never left her relationship with her previous boyfriend and actually brought him with them on the pretext of scuba training (for her). Later, when he wised up, he had a detective discover that she was still seeing him, with pictures and all. And that was it.

Remember I’ll always be your friend

Goodbye old friend.

Lyrics

Goodbye My Friend

Goodbye my friend

I said goodbye my friend

Though your time is gone

I look back upon

All those years we spent together

Working on and on

You were outta sight

And you taught me right

When you handed me the reins

I drove on through the night

Day by day

We learned to get along

Along the way

We remained strong

We both wrote the song

Others sang along

You know, even when the earth moved

We kept on keepin’ on

We worked to create

And our stuff was great

Yes our loyal crew was awesome

When they stepped up to the plate

Year by year

We fought the hardest fights

Have no fear

Soon comes the night

Goodbye my friend

Goodbye my friend

Goodbye my friend

I said goodbye my friend

Too much time in the radio station

Took its toll out on you

And even so it never made you blue

Too much trust in the ladies that found you

Left a few scars on you

Too bad that none of them could be true

Goodbye my friend

Goodbye my friend

Goodbye my friend

I said goodbye my friend

(Reprise)

Remember the days in Boston town

Remember the day we lost our friend

Remember how Water Tank went down

Remember the goldfish bowl and then

Remember the wall-sized plots we made

The end of your set you played that song

Remember how partner’s draw was great

Remember how Cheshire cowed your dog

Remember the Gershwin rhapsody

Remember when Painter saved the day

Remember the exit strategy

Remember neuropathy’s dismay

Remember the picture Marla made

Remember the sadness near the end

Remember the time you were betrayed

Remember I’ll always be your friend

How Does It Work, Part 2

Earlier this year I wrote a post about analytic geometry. In that blog post I introduced you to the coordinate plane, points, vectors, segments, and all sorts of useful operations in 2D. The dot and codot operators, and their relation to being able to say things like "to left of" and "to right of" were discussed. Also, the relationship between polygon area and its orientation. In this post, we'll go a bit further into the 2D analytic geometry domain, discuss why it is important, and show a few results. And I will actually explain how to use dot and codot.

In 1975, Tom Schaefer introduced me to these concepts while clicking his ball-point pen nervously.

Yet his guidance was like gold to me. I had just received the keys to the kingdom of analytic geometry.

I was familiar with the dot and cross products from my schooling in 3D analytic geometry I received from an ex-Lockheed employee named Mr. Pearson who taught at De Anza near where I lived. But I was still naive about 2D analytic geometry. At Calma, programming CAD software for chip-makers, I learned that the dot and the codot were very useful in 2D as well.

The 2D dot product (explained in my earlier post) can determine whether two vectors point in the same direction.

When they do, the dot product is positive. By the way, if you divide the dot product by the product of the lengths of the two vectors, you get the cosine of the angle between the vectors. The resulting quantity is exactly one when the vectors point in the exact same direction. And it is exactly zero when the two vectors are perpendicular.

This is quite the same as dotting two normalized vectors (vectors that have been divided by their lengths so that their new length is exactly one).

If the dot product is negative, however, then the vectors point in opposite directions. In clearer terms, v2 is more than ninety degrees away (in absolute value) from v1's direction when the dot product is negative.

So we can use the sign of the dot product to determine in which half-plane the endpoint of v2 resides. We will make use of this fact later in this post.

The dot product is easy to evaluate: given two vectors you multiply the x's together to make one product, multiply the y's together to make a second product, and add the two products together to make the dot product.

The 2D cross product (codot) shows whether two vectors define a counterclockwise or a clockwise angle.

When the codot is positive, the vectors make a counterclockwise (mathematically positive) angle. And similarly to the dot product, if you divide the codot product by the product of the lengths of the two vectors, you get the sine of the angle between the vectors. The resulting quantity is exactly zero when the vectors point in the exact same direction.

This fact can be used to determine whether the endpoint of v2 is to the left or to the right of vector v1.

If the codot is negative, then v2 lies to the right of vector v1, making a clockwise angle. This means we can use the codot to determine which half-plane that the endpoint of v2 lies. Another useful thing!

Evaluating the codot is a bit more complicated, but still easy to describe. The first product is the x from the first vector multiplied by the y from the second vector. The second product is the y from the first vector multiplied by the x from the second vector. Then the codot is computed by subtracting the second product from the first product.

With these newfound capabilities, I was suddenly empowered!

For instance, I was able now to compute the distance of a point from a segment easily, using the scalar cross product (also known as the codot operator). Why would I need this?
For one, when I needed to implement pick. To pick something is to click or tap and be able to determine the nearest thing. This is useful when you need to select something to delete it, to edit it, or to move it. And in those days I was working with segments and polygons.

Point-Segment Distance

To compute the distance between a point and a segment, we must consider all the cases. With a segment from point p1 to point p2, there are three cases. Either the point p is closest to point p1, it is closest to point p2, or it in in the middle and it is closest to the segment. We can see these three cases in this diagram.

Isolines of equal distance from the segment basically look like a sausage, since they are rounded at the ends.

But how do we determine which case a new point will be?

We start by evaluating three vectors, v1, v2, and v3. We start with v1, the vector from the start of the segment (point p1) to the end of the segment (point p2).

Vectors v2 and v3 are the vectors from point p1 to our point p and point p2 to our point p respectively. These will be used to determine locations and distances, the relationship of point p with the segment.

We can immediately see which case we are by using a dot product.

Dot v1 with v2 to determine which side of point p1 the new point p lies.

Similarly, dot v1 with v3 to decide which side of point p2 the new point p must lie.

If it is within neither area A nor B, then it is in area C by the exclusion principle (which Sherlock Holmes was so fond of).

But what if the point is in area B? Then we must perform some slightly more complex computation.

Here we see vectors v1 and v2, which can also be used to determine the point segment distance. By using the codot (scalar cross product) we can determine the sine of angle theta (shown in red).

As you can see, the dot and codot products are now becoming useful!

But this little diagram can give you a clue how to accomplish the computation. And also how to compute the signed distance.

Note that the sign of the distance is positive if the point p is to the left of the line from point p1 to point p2. And it is negative if p is to the right.

Thus, the point-segment distance in the most usual sense is the absolute value of D.

Note also that D is simply the length of v2 when p is in area A (closest to p1). If p is in the area C (closest to p2), then D is simply the length of v3 instead.

Geometry is Complicated

Yes, geometry is quite complicated! Any kind of interesting operation usually becomes a miasma of cases and complexity. Just imagine how complex it is to determine if a point is inside or outside a polygon?

Well, you won't have to imagine because it is our next problem. First, a word on polygon representation.

Where, Oh Where Has Polly Gone?

So let's return to the polygon. A polygon is a ring of points connected by segments. Internally to a computer we represent it as a list of points, which is usually our first mistake. Well, at least it's the first thing that can go wrong, that lends it complexity, etc.

You see, a list has a start and an end, but a ring does not. This means we need to do one of two things: (Method 1) make the list longer by one element and thus represent the start and the end points redundantly, or (Method 2) make a simplifying implicit assumption that the last point of the list is actually followed by the first in the list (though it is not recorded redundantly).

The first method has the dubious advantage of having all the segments represented as a contiguous pair of points, but the disadvantage that the count of items in the list is one larger than the count of points in the polygon. This means you will always have to be adding or subtracting one whenever you deal with the polygon's points, and this is the root of so many errors!

The second method has the advantage that the number of points is correct, but the disadvantage that one of the segments is not contiguous (the last one). This means that, whenever you have to enumerate the segments (in particular, the last one) you will have to do something special to see both points.

I prefer the second method. Because using the first method has come back to bite me more times than I can count! In fact, whenever I try to count the times, I always seem to be off by one! Ouch.

AC/DC Polygons?

The orientation of a polygon, which connotes whether it is clockwise or counterclockwise, can be determined by taking the sign of its area computed using the trapezoidal rule.

Some operations do not require the orientation to be known, like the test for whether a point is inside or outside the polygon. But if we need to make a local test for a point being inside or outside a particular edge of a polygon, orientation must be known. For instance, on a counterclockwise polygon, a right edge of the polygon goes in the upwards direction and the left edge goes in the downwards direction.

Some conditions confuse orientation, like self-intersecting polygons.

When you examine an ordinary (non-self-intersecting) polygon, that is oriented counterclockwise, you will find the right edges go from south to north and the left edges go from north to south. On a self-intesecting polygon this might not be the case.

Rules exist for deciding whether a point is inside or outside any polygon, including self-intersecting polygons. This includes the even-odd rule and the non-zero winding number rule. We will show how to implement these in the next section.

Holes are another quality that complicates polygons. Clearly you can't just treat a hole exactly like any other outside boundary polygon. But there are rules that can simplify our approach to holes.

When a polygon has holes, the convention is to orient the holes in the opposite way from the outer border of the polygon. So, a counterclockwise polygon has clockwise holes by convention.

And then there is the issue of islands. You can have a counterclockwise island inside the hole. And so forth and so on. So holes can have holes, but they are really outlines.

I told you that geometry was complicated!

Vexing Convexity and Caving Into Concavity

Knowledge of orientation makes possible some of the more complex operations on a polygon, like fracturing into convex pieces.

But before we can do something as complicated as fracturing, we have to have an intuitive notion of what is locally concave and what is locally convex. Fortunately the codot comes to the rescue.

In this diagram you see the right edges of two counterclockwise polygons. The one on the left is locally convex at point p2. The one on the right is locally concave at point p2.

I form vector v1 by subtracting p2 from p1 and vector v2 by subtracting p3 from p2. We can just use the "to left of" and "to right of" measures to decide whether the polygon is convex or concave at point p2.

You see, v1 codot v2 will be positive if the polygon is convex at point p2 and negative if the polygon is concave at point p2. This is another reason that the dot and codot operators are so useful.

Inside and Outside

Now we can look at the problem of deciding whether point p is inside or outside of a polygon.

To solve this we really have to ask ourselves whether polygon orientation is important to this crucial test. It's not as easy as all that to answer this question.

To solve this problem we need only draw a ray east from point p. If we count the number of intersections of this ray with segments of the polygon, we can determine if point p is inside or outside. If the polygon isn't self-intersecting, then it is pretty easy to see that the number of intersections of this ray with the polygon segments will be an odd number only when point p is inside the polygon.

But how many cases are there to consider?

What happens when the ray is collinear with a horizontal segment?

If the ray is a clean intersection with the edge, it's easy to see it will count. But when the ray intersects at a vertex, then it is more complicated to decide if the intersection counts. But there is a simple trick that can help us decide how to count these unusual intersections.

Here a ray is shown intersecting a vertex in different ways. Some intersections count, like the leftmost one, which goes from the inside of the polygon to the outside. Other intersections do not count, which merely graze the polygon in some way.

The clever trick is to consider the top vertex and the bottom vertex of the edge. If the intersection occurs at the top vertex, then it counts. If it occurs at the bottom vertex, then it doesn't count. In the leftmost case, only one of the two segments would then intersect the ray, which is correct. In the middle case, both segments would intersect the ray, and since we are looking at the parity of the intersections, that would mean that they cancel each other out. In the right case, no intersection would count since both intersections are at the bottom vertex of the two segments.

When the polygon is self-intersecting, however, this method produces an answer that enforces the even-odd rule, since we are looking at the parity of the number of intersections.

And this is where polygon orientation comes in.

To implement the non-zero winding number rule, we must consider how the ray crosses a segment. If the segment crosses the ray in an upwards direction, then we add one to the winding number. If the segment crosses the ray in a downwards direction, then we subtract one from the winding number.

At the end, if the winding number is zero, then the point is outside the polygon. Otherwise if it is positive or negative (non-zero) then the point is considered to be inside the polygon. This is a good reason to orient a polygon's holes in the opposite direction as their outside boundaries.

The winding number rule works correctly with the top-counts bottom-doesn't rule, also, and so we have a solution!

Lastly, an inside-ouside tester might also want to return a value of "on edge" in some cases.

Sharp, Distance

A distance function can be used to shade a polygon and this has an application to the tiling patterns I have been working with recently. It also has a bearing on a problem in printing.

Printers often want to spread or choke a given shaded area. This is because ink isn't perfect and tends to spread a bit when it is printed on paper. So a shaded area is often choked first, which enables the natural spread that occurs in printing to produce the right-sized result.

This technique is also used in e-beam lithography, which is the first place I encountered the problem of insetting a polygon.

You can consider the inset of a polygon to be the set of points that occur at a fixed distance inside the boundaries of the polygon. So the outside boundary gets choked and holes get spread.

Things like insetting and outsetting are fairly well understood, but did you know that the way we construct gables for the roof of a house is actually completely related to the distance function and thus can help us compute any inset?

Here is a simple house's gabling as viewed from above. On a roof of a house, lines of equal elevation represent specific insets of the perimeter of the house.

So if I produce the gabling for an arbitrary polygon, I can use that information to produce any inset I want. And also any beveling I want.

You can compute the gabling of an arbitrary polygon. The boundaries between facets are actually the bisectors between successive edges of the polygon. But when the bisectors meet, then we need to bisect the edges that are farther apart.

Computing the gabling for an arbitrary polygon is complex indeed! It borders on graph theory.

But it is useful in both beveling and also for computing the grout of a tiled pattern! More on this in my next installment of the Patterns series.

How Does It Work, Part 1

Analytic geometry is one of the most useful kinds of mathematics I have ever learned. Painter was built on it. But the average person has little idea what makes it tick, much less what makes it relevant. This post will simplify two-dimensional analytic geometry and present it so anybody can understand it. I'll build you up from understanding points on the plane to segments and vectors. And then to angles, directions, orientation, area, really you name it (if it has to do with analytic geometry) and I can help you understand it.

The Plane, the Plane!

Pixels and points are two ways of looking at the plane. But both of them involve a two-dimensional address system, and the two dimensions are usually called X and Y, but sometimes also columns and rows.

We see here a right-handed coordinate system. On the compass, the X-axis points east and the Y-axis points north. In the center is the origin, the point where X and Y are both zero. We like to write a coordinate as an ordered pair, in this case (0, 0). The axes also split the plane into four quadrants (shown in color and with their conventional Roman numerals).

If you are working in columns and rows instead of X and Y, then you are actually using a left-handed coordinate system, because larger rows are below the smaller ones, and so the direction of increasing rows points south. Pixels in an image are usually laid out in rows and columns.

A coordinate system is the basis for all analytic geometry. A point is an infinitely small location in the plane. A pixel is really a small rectangle covering a (usually square) area in the plane. The center of the pixel is a point.

Vegments and Sectors

Wait, I meant segments and vectors (I'm just trying to confuse you with doubletalk, hee hee)! Join two points with a small straight line and you get a segment. If you join two points in the same way, but the join actually has a direction, then you have a vector. Segments and vectors may be measured and quantified in different ways. And each has their own use.

Here I show a segment from point P1 (X1, Y1) to P2 (X2, Y2). A segment is rooted (meaning it has a real position on the plane) because both endpoints have locations.

Segments may be chained end-to-end to create polygons. Most commonly, a polygon is closed, in which case it has an inside and an outside. You can compute a closed polygon's area also. More (much more!) on this later.

Here is a vector from point P3 (X3, Y3) to point P4 (X4, Y4). But a vector, which we have conveniently defined to be the straight path between these two endpoints is really not rooted and consists of only an X and a Y delta. A vector is pretty much the same no matter where you put it.

A vector's measure starts by computing the X and Y deltas that make it up. Once you perform the subtraction, any notion of being rooted in the plane goes away. Why? This is intuitively true because you subtract away the start point of the vector, removing its home base.

Length and Stuff (No, It Isn't Spelled Lenght! Grrr!)

Simple subtraction creates the vector, as you can see. This is why a vector is oriented. A vector from P3 to P4 is quite different from the vector from P4 to P3. In fact, it is the negative of it. Or inverse.

Its length may be easily calculated using Pythagoras' rule by making the segment the hypotenuse of a right triangle (you probably wondered when that rule was going to be useful to you in everyday life, right? Well, just wait until you get to trigonometry!).


So here is the easy way to compute the length of a segment. You move the "right angle" of the imaginary right triangle (kind of shown shaded in a very light peach color) directly to the origin. This translation is effectively performing a subtraction, in this case, of the lesser of the two X's, which happens to be X4, from the two points, and also a subtraction of the lesser of the two Y's, Y3, from the two points. Anyway, the base and height of the right triangle are now known, so we may compute its hypotenuse length using Pythagoras' rule.

Note that, when you square them, the deltas that make up a vector can be either positive or negative. This is because their signs get lost when you square them: they always end up non-negative (also coincidentally why the square root of a negative number is not a real number). So we can define the length of the vector to be the square root of the sum of the squares of the vector's deltas.

If you imagine a segment to be a vector, then you can compute its length in exactly the same way. Length doesn't depend upon the position of the segment. That's why it works to think of the segment as a vector in this case.

OMG Do I Have To Know This Stuff?!?

If you already know about all the kinds of numbers, then you can skip this section. However, just bear in mind that I had to know about all these things before I could develop Painter! And now it's your turn! Waahahahahaa!

There are various kinds of numbers that it is useful to know. The integers are the whole numbers, zero, and their negatives. On a computer, there may be a smallest integer and a largest integer. That is what we like to call an implementation detail in the business. If you need more accuracy, you might want to use a real number. Real numbers can represent the integers, and all the numbers in between as well, like 9.57212947621.... On computers, these are represented by things called floats and doubles. These have various numbers of bits of accuracy.

When you divide one integer by another integer, you get a rational number (but please don't divide by zero!). There is really quite a spectrum of numbers that can be represented by rational numbers, called a Markov spectrum (but I digress). On a computer, real numbers can't really represent all rational numbers with 100% accuracy. For instance, you can represent 123/128 exactly, but 1/3 is hopeless to represent accurately. This turns out to be true because computers use power-of-two (binary) representations, and 128 just happens to be two to the seventh power.

Some numbers can't be represented exactly as a rational number or by floats and doubles on the computer. One example of these is an algebraic number: a number that is the root of some polynomial with integer coefficients, like the square root of two. If a segment has its endpoints at points whose X and Y are integers, then the segment's length is an algebraic number.

Another example is a transcendental number. Such a number can't be represented as an algebraic number or a rational number. Well, pi and e, the base of natural logarithms, are two examples of transcendental numbers.

OK, computers really only approximate these, but it's good enough for government work.

Back to the Vector

A vector then has a length and also an angle. Mathematicians have for ages thought of angles as being rooted in a vector that points east. This is the zero angle, and it corresponds with the X axis. Angles increase counter-clockwise, starting at zero and increasing until they become 360 degrees back at the X axis again. Although mathematicians actually think in radians. A radian is about 57.3 degrees. This means that 360 degrees is actually two pi radians.

Pi, by the way, is the magic ratio of the circumference of a circle to its diameter. It has a value of about 3.14159.... Yes, I memorized pi to 100 places and I used to recite it. Jeez, was I a geek!

But radians are a pure mathematical way of looking at things. Using radians instead of degrees saves you a multiply each time you do a trig function. Uh-oh. Trig functions!

Well, anyway, when you have a vector, and you divide its X and Y components by its length, you get a unit vector that points in the same direction. This unit vector consists of the cosine and the sine of the direction angle, by the way.

I remember when I was introduced to this fact. It was, to me, an "aha" moment. Now I understood why trigonometry was important! Actually, a few things fell into place that day in 1974. I ended up using it later on a test given to me by Joe Sukonick, a clever programmer at Calma Company. That bearded MIT graduate fellow ended up with a patent on the XOR for cursors in raster systems, by the way. But it was another guy at Calma, Tom Schaefer, that taught me some really useful things about analytic geometry. Without this information, it would have been seriously difficult to create Painter, or build the mosaic brush. Or really anything I do today.

What's Dot?

At Calma, segments definitely got connected end-to-end to create polygons. Calma built very good CAD (computer-aided design) systems for the very first VLSI (very large scale integration) components. In other words, microchips like the Motorola 68000 were designed on our systems. Yep, the original Macintosh's CPU.

I remember thinking about the notion of concave and convex and clockwise and counterclockwise. How could I determine these attributes for a polygon? It seemed like concavity was a local thing, and could be determined by looking at three consecutive points. But clockwise and counterclockwise were much more complicated, and were clearly a global thing. Or were they?

So there I was at the tender age of 19 at Calma, thinking abstractly about analytic geometry. It turns out I was smart enough and up to the challenge!

Tom Schaefer clicked his pen a few times and then drew a few figures on a piece of Calma stationery. Tom Schaefer was responsible for the all-angle fracturing software that enabled e-beam devices to render arbitrary geometries onto silicon, so I believed he could help me.

First there were three points, P1, P2, and P3. You could subtract the points' X's and Y's to make two vectors, V1 and V2.

But note that, the two vectors, if rooted at the same origin, created an angle between them, called theta. The angle is measured in counterclockwise degrees (or radians!).

That's when he introduced two operators, dot and codot. Dot is really the dot product and codot is sometimes called the scalar cross product. I found the operators' definition to be unusually simple and low-cost computationally. You just multiplied the X and Y components of the two vectors together in different ways. Wow!

Then he proceeded to show me that these operators could actually be used to compute the sine and the cosine of the angle theta. It was all beginning to come together. But I was a little hazy on my trig, so he made it absolutely clear to me. It's all about which side P2 is with respect to the line that passes through P0 and P1.

In fact, the sign of the codot could be used to determine this useful bit of information. And here's how to do just that.

OMG I thought this was incredibly clever. With this one operation, I could decide if a polygon is concave or convex, and even whether to not a polygon was clockwise or counterclockwise (as long is it's not self-intersecting).

But, of course, my brain was thinking several steps ahead.

It also occurred to me that, if V1 and V2 were unit vectors, that the dot and codot operators would simply produce the cosine and the sine of theta directly. In fact, I could see now that the rule about a vector's angle was simply a special case of this.

The dot product, it turned out, was useful in determining whether the two vectors were pointing in the same basic direction (if the dot is positive) or the opposite direction (if the dot is negative). And, by the way, if the dot product is zero, then the two vectors are at right angles to each other (perpendicular).

Area, Orientation, and Lobster Bisque

Polygons are a connected and closed chain of points in the plane. Between any two neighboring points is a segment. So, how do we compute the area of a polygon? Well, we make use of a clever technique called the trapezoidal rule. If a polygon is clockwise, then we just have to make trapezoids from each segment by dropping lines to the Y axis as we see in this diagram. Note that, on the bottom of the polygon, when the segments are going in the other direction, then the trapezoid areas become negative, because the X terms are going from right-to-left instead of from left-to-right as they are here. And that makes polygon area work by first computing the integral under the top of the polygon and subtracting the integral below the bottom of the polygon.

This has an interesting side effect. The clockwise polygons have a positive area and the counterclockwise polygons have a negative area.

So, really, to get the area, we have to take the absolute value of the computed area. And the sign is the orientation of the polygon. This turns out to be a very convenient way to compute polygon area! Once you see it, you will wonder how it can be so simple.

This turned out to be a question on Joe Sukonick's aptitude test at Calma. I took that test, and I got it right. But another guy, Bruce Holloway, got the job. Because, I was going to college at Caltech. The very next spring, when in Chemistry lab at Caltech, I got a call from Art Collmeyer. He saw the test and decided I might be interested in a summer job at Calma. It's good he called. I met Tom Hedges at Calma.

Oh, and by the way, the lobster bisque at Hula's Grille in Santa Cruz is excellent!

Respecting the User's Input

I had the privilege of working at a Computer-Aided Design (CAD) company, Calma, in the late 70s, and thus I experienced first-hand the early years of computer graphics. And it was at Calma that I learned a principle that has served me well ever since: respect the user's input.

The users of the Calma workstations used a CalComp Talos table digitizer. You would tape your sheet of VLSI artwork down on the digitizer and then you could digitize the traces (conduits of electrons on the surface of the chip you were designing) using a puck. Digitizing was a tedious process and eventually this process was eliminated by allowing the designer to build their design directly on the CAD system in the first place. Which is obvious, of course. But computers were really primitive back then and so this was a necessary stepping stone.

It was considered massively incorrect to require the operator (what the user was called back then) to digitize a point more than once. The problem occurred so often, that the users called it double digitizing. This was clear to me, since when I wrote something, I was also its first user when testing it. And double digitizing was incredibly bad because it required extra work. And it didn't respect the user's input.

As time went on, I became the author of the graphic editor (GED) on the Calma GDS-II system. You may not recognize this system, bit it was used to design the Motorola 68000, so you probably know its effects. GED fulfilled the promise of digitizing the geometry within the system, although it wasn't unique, and we all considered this requirement to be obvious. When I wrote it, I paid particular attention to caching the user's input so I wouldn't require anything at all to be entered twice. Even a closure point. Because by then, tablets were being used (but with wire-connected styluses) and often it was hard to hit the same point twice. So, I invented a snapping distance specifically so you only had to get close to the starting point and still specify closure.

Constraint-based systems were still in their infancy in 1978.

Programming

As I did more programming, I became aware of another corollary to the principle of respecting the user's input. It was called the Perlin principle of modular programming: we hide the similarities and highlight the differences. Sometimes the similarities are simply encapsulated in classes or modules. Usually the differences become parameters to the modules, or the differences are wrapped up in the way you call the modules or use the classes. Here the user is the programmer and their input is respected in some ways because they won't have to write something twice. There is another way to respect the programmer's input: transparency. When an API (application programming interface) is complicated, then it becomes less transparent and the possibility of bugs can increase. On the other hand, when an interface is clean and well-defined, the programmer doesn't have to learn too many things, or understand the assumptions made by the writer of the API. All these things make fewer problems and also fewer chances for bugs, because the user's model of the code is very close to the way the code actually works. In this way, the programmers intent is better respected.

MIDI

Later on, in the late 1980s the user input became more complex. In 1988, I built a program for recording and playing back MIDI data from keyboards and drum machines. I called it MIDI '88 and it's a project that really has never seen the light of day, except for in my studio. Well, I did show it to Todd Rundgren once. And, of course, John Derry.

To get the MIDI data, I had to interface to a driver and write an input spooler. This spooler, implemented as a ring buffer (seen to right), kept all the data around without dropping samples and events. In this way, I was respecting my input to the keyboard and allowing me to record it. I recorded the events with a millisecond-accurate timestamp. And this was the beginning of my quest to accurately preserve the user's input and faithfully reproduce the user's gestures, allowing the style of the user to come through.

Tablets

When I first got a Wacom tablet in 1990, I sought to do the exact same thing: create an input spooler for the tablet data, and timestamp the data accurately. But with the Wacom, there was pressure data also that needed to be captured. And then there was tilt and bearing information.

The input spooler captured all these things.

But I soon learned that the data I got from the tablet wasn't perfect. It didn't really accurately capture the user's input at all. One source of the error was temporal aliasing. So I learned that input data often had to be massaged.

Some tablets had very few samples per second and others had quite a few. But, if you assumed the data from these tablets are regularly spaced, you could get kinks and ugly straight lines in your brush strokes. So I invented a limited FIFO that smoothed out these time-and-space irregularities. And I had to pay special attention to the tight turns in the path of the stylus. Changing the extrema of a brush stroke was highly undesirable since it made common actions like cross-hatching very hard. And sketching simply looked wrong if too much processing was done on the user's input. Usually, but not always, the extrema of the stylus' path was a place where velocity was at a minimum.

But, conversely, when the stylus was moving fast, less control was exerted on the actual position of the brush. So I could afford to use parametric cubic interpolation to create more points in the brush stroke in fast-moving sections of the brush stroke. This was a good thing, because there were fewer points per inch in fast-moving sections due to the fixed sampling interval: when your hand moves the stylus faster, the sample points are spaced farther apart.

All this made for smoother scribbling in Painter.

When John Derry came to Fractal Design in 1992, his enthusiasm for mark-making actually meshed quite well with my desire to accurately capture the input. It made Painter a very good tool indeed for an artist for these reasons.

We perfected the motto with respect to mark-making: to accurately capture the nuances of human expression and faithfully reproduce them, allowing the artist's style to come through.

It is this statement that I stumble through towards the end the video in my early post Creativity and Painter, Part 1. Ah, the early days.