Archive for March, 2008

Curve and Vector

Sunday, March 30th, 2008

Curve (com.elbeno.curve) is my common lisp package for doing cool things with two-dimensional curves. In particular, modulating cubic Bézier curves and splines, but also approximating arbitrary elliptical and circular arc segments with cubic Bézier curves.

It depends on Vector (com.elbeno.vector), a cobbled together set of functionality for representing and manipulating points on the 2D Cartesian plane. It also depends on Zach Beane’s excellent Vecto, for ease of drawing. Both Curve and Vector are available under the GPLv3 license.

Download Curve
Download Vector

Currently both Curve and Vector are at v0.1.

Approximating elliptical arcs with Bézier curves

Saturday, March 29th, 2008

In doing my modulation work with curves and ellipses, I extended the vecto function for drawing an ellipse to enable an oriented ellipse. Lately it occurred to me that this didn’t go far enough in terms of functionality, and I began wondering about how to draw part of an elliptical arc.

Vecto’s ellipse drawing function works by drawing the ellipse in quarters, with four cubic Bézier curves. Each curve’s control points are calculated according to the radii and kappa, the constant that is 4(√2 – 1)/3, as explained by G. Adam Stanislav. This works fine if you are drawing quarters, halves, or complete ellipses (or circles of course), but what I wanted was a function like this:

(defun approximate-elliptical-arc (cx cy a b theta eta1 eta2)
…)

With (cx, cy) being the centre, a and b being the radii, theta being the orientation, and eta1 and eta2 being the start and end angles specifying the arc. The return value would be a Bézier curve, or a list of curves, depending on the required accuracy.

So I did some research and found an interesting paper by Luc Maisonobe on approximating such elliptical arcs with lines, quadratic and cubic Bézier curves. The maths is straightforward, if rather heavy on the constants, and it was less than an hour’s work to code up the function. I now have functionality to draw arbitrary elliptical (or circular) arc segments.

The interesting thing is that this method of approximating ellipses is not the same as G. Adam Stanislav’s method: to put it another way, when I compute a quarter-circle arc with a single Bézier curve, the control points are not quite coincident with the kappa-method control points. The error in the circle approximation is still undetectable to the eye, but careful comparison of two large circles shows that the kappa-method one is slightly larger: the curves are slightly more “pushed out”.

G. Adam writes: “It is my contention that we get the closest to a real circle if we draw the one curve with properties already discussed, and with the center point of the curve lying at the same point the center point of the circumference of a true quadrant of a circle would lie.” I would be interested to know if he has a proof behind this contention, and/or an expression for the error in such a curve. The derivation of kappa is based around this idea that the midpoint of the curve should be coincident with the midpoint of the arc.

G. Adam’s method seems accurate. But the Maisonobe method can be used to subdivide the arc, obtaining successively closer approximations to the true arc by using multiple Bézier curves, and includes a method for calculating an upper bound on the error. This, together with the fact that it easily handles start and end angle specification of the arc, leads me to favour it.

Functional Fills with Vecto

Tuesday, March 25th, 2008

I’ve been wanting to do exclusive-or functional fill in vecto for a while, so tonight I delved in. I added a pixel function to the graphics state and kept the default as the normal alpha-blending it was already doing. The pixel function signature is a bit clumsy, but it was easy to knock up a couple of functional fill demos. Programmer art alert!

XOR pixel function

This is a cyan background, and a circle drawn with an XOR function, white fill, and green stroke. From this you can see that the fill happened before the stroke, since the stroke is half-and-half.

OR pixel function

And this demonstrates an inclusive-OR fill: the standard additive colour chart.

The Hedgehog

Sunday, March 16th, 2008

The hedgehog is a noble beast; he keeps the garden clear
Of slugs and snails and other pests throughout the temperate year.
Just after dusk you’ll see him on his customary beat
Hunting Lumbricus terrestris or some other juicy treat.

Although he’s not the biggest or the fastest or most muscular,
He’s the most learned animal, nocturnal or crepuscular.
He wears his mantle lightly and he’s never ostentatious,
But of course he’s quite the expert on all matters erinaceous.

Gentility’s his touchstone; he’s unfailingly polite,
Except to over-curious dogs that send him into fright.
He’ll clean a plate of milk and bread without a single question,
Although dairy products will play merry hell with his digestion.

So if you find a hedgehog in your garden, wish him well,
And keep your eye out for him following a rainy spell.
Just let him tend his patch according to the natural order,
And he’ll gladly keep the pests away from your herbaceous border.

A bit of Pythagoras

Saturday, March 15th, 2008

Given Pythagorean triples that satisfy the Diophantine equation:

a² + b² = c²

where a, b and c share no common factors, one of a and b must be odd, the other must be even, and c is always odd.
First, note that squares of even numbers are always divisible by 4. [Lemma 1]

(2n)² = 4n²

And squares of odd numbers are of the form (4n + 1). [Lemma 2]

(2n + 1)² = 4n² + 4n + 1
= 4n(n+1) + 1

If a and b are both even, it is trivial to see that a, b and c share the factor 2.

c² = (2n)² + (2k)²
= 4n² + 4k²
= 4(n² + k²)

By Lemma 1, c is even. Therefore the solution reduces to the more primitive form:

n² + k² = (c/2)²

Consider a and b both odd:

c² = (2n + 1)² + (2k + 1)²
= 4n² + 4n + 1 + 4k² + 4k + 1
= 4n² + 4n + 4k² + 4k + 2
= 2(2(n² + n + k² + k) + 1)

This (by Lemmas 1 & 2) is not a perfect square, so this cannot be a solution. In fact, in this case c must be irrational:

Let p = n² + n + k² + k
c = √2√(2p + 1)

2p + 1 cannot have 2 as a factor. And since √2 is irrational, so is c. Therefore one of a and b must be odd and the other even.

c² = (2n + 1)² + (2k)²
= 4n² + 4n + 1 + 4k²
= 4n² + 4n + 4k² + 1
= 4(n² + n + k²) + 1

And c is odd (Lemma 2). QED.

Even more on ellipses and splines

Saturday, March 15th, 2008

Honestly, they’re incredibly interesting. Anyway, I’ll skip straight to the pièce de résistance:

Ellipse Modulation VI

This is a 4-curve cubic Bézier spline modulated onto an ellipse. The ellipse [a=4, b=3] is at an angle of π/4. C1 continuity of the complete curve is preserved. The flickr set tells the story of how I got here.

This is around 450 lines of my naive lisp, including class definitions and test code. So Gary, this is your g-code challenge!

The lisp code is object oriented (oh, and so much nicer than C++’s so-called object orientation). I rewrote the earlier code now that I knew what I was doing, and I added lines and polylines to the mix too (see the flickr set) so I can easily modulate whatever edge I want. You’ll notice if you look closely at the earlier attempts that they had a bit of a problem with c1 continuity, which is now fixed with the new code.

In closing, thanks, Zach!

On the Benefits of Showering

Wednesday, March 12th, 2008

From time to time when I’m perplexed
Or by a tricky problem vexed;
A cipher that just will not yield
But keeps its mystery concealed,

I find I have a last resort
Before cerebral fuel runs short:
I open up the bathroom door
And step onto the tiled floor.

The whirring fan, the gurgling drain,
The white noise washing on my brain.
The shower is my bosom friend –
It leads me to the enigma’s end.

No matter how fiendish the puzzle,
The pump’s deliberative buzz’ll
Help me find the right solution
By the end of my ablution.

Showers do not only soak us;
They bring things into mental focus.
Doubt not their catalytic power –
I wrote this poem in the shower.

Ellipses & Splines again

Monday, March 10th, 2008

After some code cleanup and generalisation, I can now modulate whole splines onto ellipses and onto splines themselves. Here is my simple 4-bezier spline modulated onto an ellipse:
spline_on_ellipse
And onto itself:
spline_on_spline
Repeatedly modulating a spline onto itself while varying the frequency parameter leads to some interesting and fractal patterns. Nice.

Wish-it-was two-factor authentication

Sunday, March 9th, 2008

In order to print out a tax form, I’ve just had to go through some silly security question rigmarole with my online bank. The wish-it-was two-factor authentication is getting quite out of hand these days. They are really desperate to give the appearance of security. In addition to displaying a chosen/random image and “security phrase” – ostensibly to prevent phishing and enable me to recognise that I’m in the right place – they asked me to pick five security questions and answers. The usual tripe like what was my high school mascot, what is the name of my hometown newspaper, etc.

I briefly toyed with the idea of putting in weird answers (high school mascot? half a dog) but in the end went with mashing the keys to produce 10-12 characters of alphanumeric nonsense for each answer. Since they’re going to ask me these questions in future, I copied them and sent them to myself in an encrypted email.

The strange thing is that they do this instead of enforcing a well-chosen password. So it’s actually (if properly answered) nowhere near as secure as a 10-12 character randomised password.

On Being, and Raising, a Gifted Child

Saturday, March 8th, 2008

[apologies to my LJ readers for the lack of cut]

Lately I’ve been reading books on gifted children: how to identify them; how to deal with them; what to expect as a parent. Is mini-Elbeno gifted? Without wanting to sound like a competitive parent, and properly considering that it’s still early days, I think he’s showing signs.

He’ll be two next month. His language development is quite impressive, I think. He speaks whole sentences and volunteers complete thoughts about what we’re doing. “Mummy and Henry are going to the tot lot” was a recent example. He is absorbing language (including foreign languages) as fast as we can expose him to it. Today we caught him singing a Spanish song that Mrs Elbeno doesn’t even know all the words to. He shows remarkable feats of memory and can concentrate on tasks very intensely. He can read. We’ve stopped counting how many words; he often reads his books on his own now and attempts to read words that he’s never seen before, e.g. when out and about on signs, trucks, etc. I have nearly no experience of nearly-two-year-olds to compare him to, but this seems out of the ordinary.

Giftedness is partially hereditary, and he’s well set for it. Mrs Elbeno was put into “gifted & talented” programs at school. She has an IQ, based on very informal testing, in the gifted range. Not that IQ need have much bearing on giftedness. Reading the books on gifted children, it is also clear to me that I was a gifted child.

I can’t remember a time when I couldn’t read. What I can remember is taking a reading test at 5 years old. I remember being bored by the test, and while the teacher was pointing in turn to the simple words at the top, I had already “buffered” that line of words in my head and was looking at the words down at the bottom of the page. I distinctly remember two words that I saw there: metamorphosis and idiosyncrasy. I knew what metamorphosis meant because I’d read about butterflies and frogs. I didn’t know what idiosyncrasy meant, but I’d heard it in speech and when I saw it written, I realised what it was. The reading test results showed that I could read at an eighth grade level.

I was also gifted in mathematics. At preschool (starting age 3) I was doing addition and subtraction of 2-digit numbers. “Sums” consisted of this. e.g. 53 + 24 or 38 – 15. I remember one day our class spent a couple of hours in the next classroom for a lesson. I don’t remember the lesson content – I wasn’t paying attention. What I found much more interesting was the chart of times tables on the wall, which went up to 12. So I memorised it. I learned my times tables from that chart in about 10-20 minutes. I remember optimising the process and not bothering to memorise the 10s and 11s because they were so easy.

I’ve always excelled at tasks that involve taking in information, whether visually or auditorily. At primary school, I never scored less than 100% on a spelling test. Once when I was 9, I was called up to the teacher’s desk about my maths homework. We’d been studying addition and subtraction of fractions. I hadn’t shown any working for the exercises, just putting down the answers. So I guess the teacher wondered whether I was really doing the exercises or just copying the answers (which were in the back of the book). The problem she asked me about was 3/4 + 2/3, and my written answer was 1 5/12. My explanation was something like this:

“Well, I start by seeing that three and four (pointing to denominators) both divide into twelve, so I have to convert to twelfths. I look at three quarters and twelve divided by four is three, so I multiply by three. Three times three is nine, so three quarters is nine twelfths. I remember that. Then I look at two thirds. Twelve divided by three is four, so I multiply two by four to get eight. Eight twelfths. Nine twelfths plus eight twelfths is seventeen twelfths, which is one-and-five-twelfths.”

The teacher looked at me and said rather weakly, “… Well, er, can you put down your working from now on, at least so I can follow it?”

Giftedness isn’t all easy, though. My intellectual development far outstripped my emotional development. At 6 I could play chess, but when I lost, I threw tantrums like nobody’s business. Also, a strange thing happened at school when I was 10. I had for years been a model student and I was top of the class without putting in any effort. I was scheduled to take an entrance exam for a public school (US: private school); my teachers, and I dare say my parents, thought that although at primary school I had been a big fish in a small pond, I would be a small fish in a big pond at the new school, which would properly stretch my abilities. Well, I got bored and I got… I’ll have to say experimental. I went through a period of about a month when I just stopped doing schoolwork. My teacher was livid, saying I’d better buck up if I expected to pass the entrance exam to the new school. So I returned to doing schoolwork, and took the entrance exam in due course. It was no trouble.

My new school was much better, and did stretch my abilities in some areas. But I was still top of the class without really trying. One of the only classes that properly, regularly, challenged me was French. I remember feeling slighted a bit at some other subjects: after studying Latin for a year, myself and two other pupils were taken aside one day with a view to putting together a (very) small class for studying Greek. The teacher asked me “So, why are you so good at Latin?” I answered truthfully that I didn’t really know why since I’d only been studying it for a year. At this I was dismissed out of hand for studying Greek: it turned out that the other two pupils had had previous lessons at other schools.

One of my friends once remarked airily within earshot, “Oh I prefer [other student] to Ben. Ben swots so much to be top of the class, whereas [other student] is more intelligent.” A friend who knew me better nearly fell about laughing, and confided to me, “He’s got it exactly backwards: you’re one of the laziest people I know!”

I don’t really set much store by IQ tests, but every IQ test I’ve ever taken (including a properly administered test I took as a teenager) has put mine over three standard deviations higher than the norm. It seems reasonable from this, and from the evidence stated, to prepare for mini-Elbeno being gifted. The question is, how gifted, and in what ways? There is as much difference between a 170ish IQ and a 130ish IQ as there is between a 130ish IQ and average. Whatever lies in store for us with the young Elbeno, I’m planning to enjoy the ride.

Readers that are/were/have/teach gifted kids: what’s your experience?