A discussion of how to properly handle liquid inside glasses in a raytracer made me look up the scheme that I had implemented once before, which I’m now stashing a pointer to just for safekeeping.

Journal of Graphics Tools – Papers – Simple Nested Dielectrics in Ray Traced Images

The reason that this is difficult (or can be difficult) is that often a glass of liquid is modelled as two objects (the glass and the liquid) with different refractive indices, and with surfaces that are largely coincident. This avoids the coicident surface problem by using a technique reminiscent of a scheme that I used to implement constructive solid geometry efficiently in a raytracer.

Anyway, some good ideas, I thought worth mentioning.

Over twenty years ago, I first read Structure and Interpretation of Computer Programs, which I still consider to be the most amazing computer science textbook ever written. I’ve known for a while that one of the author’s, Gerald Sussman has written a book on classical mechanics called (appropriately enough) Structure and Interpretation of Classical Mechanics. What’s cool is that the entire text is online. I got reminded of this while watching this lecture by Sussman on the occasion of Dan Friedman’s 60th Birthday.

I must admit that most of the physics (and a great deal of the math) is over my head, but basically he’s talking about the systematic representation of knowledge (in this case, physics knowledge) as programs, and how math becomes more tractable and interesting when programming is made part of the process.

It’s very thought provoking.

[tags]Mathematics,Programming,Physics,Sussman[/tags]

Addendum: Sussman mentioned this article by Minsky which I found a link to, and will have to read later.

Addendum²: I got the link to the video from this article on Lambda the Ultimate. Lots of other linked videos look interesting to me, I’ll be watching some of them later.

I had the vaguest recollection of a SIGGRAPH sketch on creating an armature wired with potentiometers for creating an inexpensive motion capture setup. A bit of digging revealed that this done by Stefan Gustavson in 2002, and Tom was kind enough to run down this link to his page which somehow eluded by Google-fu.

I’ve worked on computer graphics for over twenty years now. Through some quirk of fate, I have spent nearly all of my time programming batch rendering algorithms that take minutes or even hours (days?) to render pictures. The last time I really did interactive work was before OpenGL even had the “Open” prefix, back when I was working in the Princeton Applied Math department back in 1990. So, I’m not exactly the most experienced OpenGL programmer. I haven’t written anything more complicated than simple 2D plotting in years.

So, I was working on my program that reads the accelerometers from the Wii Remote tonight, and tried to set it up to draw an airplane that I could tip and tilt using the Wii remote. Unfortunately, I couldn’t get the lighting to look right. I tried all sorts of different things, but finally decided to do a bit of research and found this page:

Avoiding 16 Common OpenGL Pitfalls

What bit me? Why, the very first thing: glEnable(GL_NORMALIZE);. It never dawned on me that OpenGL might fail to compensate for scaling before computing lighting. Oh well. Live and learn.

I’ll have some example code and video of this little hack this weekend. I want to clean it up a bit more, and I still need to shoot some video of it.

An interesting aside bit of personal trivia: the model that I am using is a model of the NASA’s X29 experimental aircraft. It’s the same polygonal model that I first rendered with my old raytracer over twenty years ago. I feel like I’ve come full circle.

[tags]Computer Graphics,Wii Hacking,Wii Remote[/tags]

Addendum: Here’s a brief blurb about the X29 from NASA.

Addendum²: Here’s a screen dump of the same shaded in OpenGL:

It’s actually not just hard in the sense that you normally think of as hard. You might think that if you worked hard, you could figure out what programs actually do. Ed Felton shows that this simply isn’t true. In his simple Python scripts, he asks a question: “is there any combination of inputs to make the program print the word ‘Drat’?” Here’s the program:

import sys, sha
h = sha.new(sha.new(sys.argv[1]).digest()[:9]).digest()

if h.startswith("abcdefghij"):
    print "Drat"

It usually surprises people who don’t have computer science degrees that there is no practical way to tell. Alan Turing formalized this idea: it’s basically impossible to provide an algorithm to determine any non-trivial property of programs (such as whether they halt). Any legislation which requires somebody to evaluate the complete behavior of any program is not just absurd and impractical, but simply not possible.

I addressed the same question in a similar way in a previous post.

Addendum: The statement above is actually subtly incorrect (I should have referred back to my old theory of computation textbooks). I was trying for a description of Rice’s theorem. The idea here is that there is no algorithm (equivalently, you can’t build a Turing machine) to decide with generality whether another Turing machine (for example) accepts a particular string. Or halts. Or halts on an empty tape. Or, in fact any non trivial property.

From Wikipedia:

Using Rogers’ characterization of acceptable programming systems, this result may essentially be generalized to most computer programming languages: there exists no automatic method that decides with generality non-trivial questions on the black-box behavior of computer programs. This is one explanation of the difficulty of debugging.

Years ago, I read Gleick’s Chaos, and my recent diversion into calculating various numbers to high degrees of precision made me think about Feigenbaum’s Constant. While I didn’t write a program to compute this constant, I did recall how it is defined, on the basis of this logistic map:

Feigenbaum’s constant is the limiting ratio between successive bifurcation intervals of the logistic map (as well as all other one dimensional maps with a single hump). You can read more here.

I’m no expert on this stuff, it was just a momentary coffee break diversion.

[tags]Chaos,Mathematics[/tags]

In between sessions of zelda (currently in the Lake Temple, total elapsed time just over fourteen hours), I’ve been considering just how cool the Wii Remote controllers are. For $40 (admittedly, quite a bit for a controller) you get a controller with the following nifty features:

• It communicates wirelessly via Bluetooth, which opens up a whole bunch of possibilities for using them on other machines.
• They include a fair supply of buttons, and a “rumble pack” force feedback device.
• You can play sound back through the remote.
• It’s got four LEDs that you have individual control over.
• It has a three axis, 3.6g accelerometer, so you can read acceleration and orientation from the remote.
• It has an imaging infrared sensor that can be used to determine your orientation compared to the Wii sensor bar.

In short, it’s just a damned cool little device all to itself. I was surfing and discovered wiili.org, a site which is all about wii hacking, and they include links to drivers and libraries for reading the Wii controller on different devices. A download of libcwiimote later, and a bit of programming, and I was reading acceleration data from the remote. Behold the following graph plotted with gnuplot:

Near the beginning, I am holding the remote fairly steady. The red, green and blue lines measure the acceleration in x, y, and z, respectively. Notice that the blue line is offset. This is because of the acceleration due to gravity. Later in the test, I whirled the remote around in circles, which you can see by the rather chaotic motion.

Neat!

I’m currently working on a little interactive display using OpenGL. More later.

[tags]Nintendo,Wii Remote,Hacking[/tags]

Addendum: A little smoothing of the data makes it look much better. Here’s a different run, with some smoothing…

Addendum²: I figured out how to normalize the data appropriately. Here’s another graph:

Dear me. Macrovision has its panties all in a bunch over Steve Jobs’ recent “Open Letter” which has received a lot of attention in the blogosphere.

Macrovision’s Response to Steve Jobs’ Open Letter

It contains a lot of howlers, but I thought I’d bring your attention to a few of them.

Macrovision admonishes Steve by saying that DRM “is broader than just music”. Indeed? Do you think that Jobs, the single largest stockholder in Disney, doesn’t realize that?

Macrovision claims that DRM increases consumer value. Oh really? If I buy a song on iTunes, I can transfer it to only a limited number of devices. If I pirate it, I can copy it to any device I own. How is my consumer value enhanced? Macrovision says “consumers who want to consume content on only a single device can pay less than those who want to use it across all of their entertainment areas – vacation homes, cars, different devices and remotely”. What they are arguing is that they want you to pay for the same content multiple times. Since providing those bits to you is very cheap for them, I can understand why they might like this business model, but it’s simply astounding to say that it adds customer value.

There is also a certain amount of irony in the claim that DRM needs to be interoperable and open. Macrovision is of course has made millions by licensing their exclusive technology. I’m sure they’d be happy to help Steve out by licensing their technology to him, whether it is actually effective or not.

Yesterday Tom mentioned this article linked from Lambda The Ultimate the other day, and I finally got around to reading it today.

Regular Expression Matching Can Be Simple And Fast | Lambda the Ultimate

The short summary: the regular expression matching in common scripting languages like Perl and Python are many orders of magnitude slower than they need to be for fairly large classes of potential regular expressions. I guess I find this a little startling: the topic is pretty well understood, and has been so for roughly forty years. Ken Thompson wrote a paper in 1968 on the topic, a straightforward implementation of the ideas contained within runs a heck of a lot faster.

Interestingly enough, I learned how this stuff worked way back in my third year of college as an undergraduate. I took a compiler course, where we learned all about Thompson’s algorithm and how to convert regular expressions into non-deterministic finite automata, and then how to compile them into deterministic automata. This algorithm formed the basis of the lexer generator in an undergraduate compiler course, and was not difficult to write (or even understand). I’m left wondering: what are they teaching kids in Computer Science these days? Oy.

Here are some good examples of how to properly write a regular expression library.

Addendum: During the same time period, I had a personal epiphany. At the time we were using a Vax 11/750, and a fast version of fgrep, called match, written by Peter Bain came across the old mod.sources newsgroup. It used the dedicated MATCHC instruction of the VAX to search for matching strings. The funny thing was, soon after a whole bunch of even faster implementations came down the pike. It taught me that being smart was often a better thing than having better hardware.

Yep, Carmen stood in line for three hours at our local Toys R Us this morning, and now I have a Wii. Couple of quick notes:

• It does not like DD-WRT firmware on my wireless router. I could not get it to work with it at all. I reflashed my Linksys WRT54GS back to its stock firmware, and it worked like a charm. Since DD-WRT was also somewhat unreliable with my Macbook, I’m not that heartbroken, but it was annoying.
• Downloaded Opera. It plays youtube videos! Neat! It’s browser is actually pretty cool.
• Wii Sports is fun. My son Adam is beating me at pretty much everything.
• It’s not HD, but it does rescale for 16:9, which is cool, and it looks great. I may have to try to dig up some progressive video cables for it though.
• Rayman’s Raving Rabbids: ludicrous, but suprisingly fun.
• I’ll be buying Zelda later tonight.

[tags]Nintendo Wii[/tags]

I went ahead and coded up a version of the spigot algorithm for computing e. It makes a nice three line .signature program.

Here are the first 1000 digits (reformatted for legibility):

2.718 28182 84590 45235 36028 74713 52662 49775 72470 93699
95957 49669 67627 72407 66303 53547 59457 13821 78525 16642
74274 66391 93200 30599 21817 41359 66290 43572 90033 42952
60595 63073 81323 28627 94349 07632 33829 88075 31952 51019
01157 38341 87930 70215 40891 49934 88416 75092 44761 46066
80822 64800 16847 74118 53742 34544 24371 07539 07774 49920
69551 70276 18386 06261 33138 45830 00752 04493 38265 60297
60673 71132 00709 32870 91274 43747 04723 06969 77209 31014
16928 36819 02551 51086 57463 77211 12523 89784 42505 69536
96770 78544 99699 67946 86445 49059 87931 63688 92300 98793
12773 61782 15424 99922 95763 51482 20826 98951 93668 03318
25288 69398 49646 51058 20939 23982 94887 93320 36250 94431
17301 23819 70684 16140 39701 98376 79320 68328 23764 64804
29531 18023 28782 50981 94558 15301 75671 73613 32069 81125
09961 81881 59304 16903 51598 88851 93458 07273 86673 85894
22879 22849 98920 86805 82574 92796 10484 19844 43634 63244
96848 75602 33624 82704 19786 23209 00216 09902 35304 36994
18491 46314 09343 17381 43640 54625 31520 96183 69088 87070
16768 39642 43781 40592 71456 35490 61303 10720 85103 83750
51011 57477 04171 89861 06873 96965 52126 71546 88957 03503

and here is the little .signature program:

#define N (1000)         /* compute N-1 digits of e, by brainwagon@gmail.com */
main(i,j,q){int A[N];printf("2.");for(j=0;j<N;j++)A[j]=1;for(i=0;i<N-2;i++){q=0
;for(j=N-1;j>=0;){A[j]=10*A[j]+q;q=A[j]/(j+2);A[j]%=(j+2);j--;}putchar(q+48);}}

You can click here to get the code without the hassle of cutting and pasting.

Addendum: A bit more tinkering lead to this program, an even shorter program (it legitimately fits in two lines of code).

Addendum²: I got one for pi working. It’s almost four full lines, and I can’t help but think it could be significantly shortened. Maybe when I have some idle moments. The previously linked versions of this program (as well as its output) contained a bug, and the digits that I had below were not correct. They have been corrected

3.141 59265 35897 93238 46264 33832 79502 88419 71693 99375
10582 09749 44592 30781 64062 86208 99862 80348 25342 11706
79821 48086 51328 23066 47093 84460 95505 82231 72535 94081
28481 11745 02841 02701 93852 11055 59644 62294 89549 30381
96442 88109 75665 93344 61284 75648 23378 67831 65271 20190
91456 48566 92346 03486 10454 32664 82133 93607 26024 91412
73724 58700 66063 15588 17488 15209 20962 82925 40917 15364
36789 25903 60011 33053 05488 20466 52138 41469 51941 51160
94330 57270 36575 95919 53092 18611 73819 32611 79310 51185
48074 46237 99627 49567 35188 57527 24891 22793 81830 11949
12983 36733 62440 65664 30860 21394 94639 52247 37190 70217
98609 43702 77053 92171 76293 17675 23846 74818 46766 94051
32000 56812 71452 63560 82778 57713 42757 78960 91736 37178
72146 84409 01224 95343 01465 49585 37105 07922 79689 25892
35420 19956 11212 90219 60864 03441 81598 13629 77477 13099
60518 70721 13499 99998 37297 80499 51059 73173 28160 96318
59502 44594 55346 90830 26425 22308 25334 46850 35261 93118
81710 10003 13783 87528 86587 53320 83814 20617 17766 91473
03598 25349 04287 55468 73115 95628 63882 35378 75937 51957
78185 77805 32171 22680 66130 01927 87661 11959 09216 42019

Addendum³: I managed to trim enough from it to allow me to put an actual email return address. It’s got a bug. I’ll try again tomorrow.

Addendum⁴: Sigh. Tom pointed out the problem to me. Once that was out of the way, I figured out a number of optimizations to strip it down to fit into three lines,
which I think is an entirely credible result. Here’s the (for now) final version. It’s got an entire fourth line for you to stick good stuff onto.

[tags]Mathematics,Programming[/tags]

Your results:
You are Dr. Doom

Dr. Doom 65% Apocalypse 64% The Joker 55% Mr. Freeze 54% Lex Luthor 50% Magneto 50% Riddler 44% Green Goblin 44% Juggernaut 44% Kingpin 42% Poison Ivy 41% Venom 36% Catwoman 34% Dark Phoenix 33% Mystique 28% Two-Face 20%

Blessed with smarts and power but burdened by vanity.

Click here to take the “Which Super Villain am I?” quiz…

Wired: Monkeybites Internet Software Blog from Wired.com

There are still major issues. I haven’t had any stability problems, but there are bad memory leaks. Gran Paradiso, as Firefox 3 is code named, launches using about 33mb of RAM; after ten minutes of browsing that number jumped to 100mb and after a couple of hours it was close to 400mb — and that’s with no extensions installed.

However, the main reason for the memory leaks, according to the release notes, is the new and improved garbage collection system which promises a much improved memory footprint once the bugs are ironed out.

Most things do work better once the bugs are ironed out.

This just so totally rocks…

[tags]Robot,Amusement,Google Video[/tags]