Computer graphics proofs
I'm slowly assembling some proofs for computer graphics problems. My goal is to be non-intimidating and non-handwaving.
Inverse of rotation/translation matrix
My camera class is composed of rotations and translations. Occasionally I need to be back out of eye space and get back to object space, so I need the inverse of my modelview matrix. Finding an arbitrary inverse is non-trivial, but finding the inverse of a matrix that simply rotates and translates is simpler.
- Inverting a matrix product
- Inverting a translation
- Inverting a rotation
- Inverting a rotation + translation
Declarations in nested blocks
Until a couple of years ago, my mental model of how blocks worked in programming languages was that as one entered a block, space was allocated on the stack for its local variables. For example, the following would push 4 bytes onto the stack on entrance and pop them off on exit:
{
int tmp = rand();
}
When I wrapped such code up in a loop, I'd have a lot of pushing and popping:
for (int i = 0; i < 10; ++i) {
int tmp = rand();
}
I wanted to avoid all this stack twiddling, so I widened the scope:
int tmp;
for (int i = 0; i < 10; ++i) {
tmp = rand();
}
Then I learned that this was all a myth: the stack space needed by a block is easily evaluated during compilation and can be included in the surrounding subroutines' stack space. Michael Scott in his Programming Language Pragmatics states in section 3.3, "No run-time work is needed to allocate or deallocate space for variables declared in nested blocks; their space can be included in the total space for local variables allocated in the subroutine prologue and deallocated in the epilogue." I did not need to trade good narrow scoping for performance!
However, I wanted to see the compiler specifications that said this was actually how it's done. Unfortunately, my searching has yielded quite a lot sentiment but only one formal statement:
- C#: "The local variable declaration space of a block includes any nested blocks. Thus, within a nested block it is not possible to declare a local variable with the same name as a local variable in an enclosing block."
If you know of further sources, please share them.
Searching for visually selected text in Vim
I use visual mode a lot in Vim, and I've often found myself wanting to search for other occurrences of the selected text. This can be accomplished with:
- Select the text.
- Yank it (y).
- Start search (/).
- Paste yank register (<CR>").
But that's way too many keystrokes and if the search pattern contains forward slashes, I have to go through and escape them. I've mapped <Space>/ to achieve the same thing and automatically escape with:
vmap <Space>/ y:let @/=escape(@", '\/')<CR>:set hlsearch<CR>
This yanks the text into register ", escapes the contents and assigns it to the current search pattern, and then turns on search highlighting.
TextWatcher false positives
I have a few apps in which I register a TextWatcher on various EditText widgets like so:
@Override
public void afterTextChanged(Editable s) {
isDirty = true;
}
Then when the back button is pressed, I check the isDirty flag to see if I should prompt the user to save the changes:
@Override
public void onBackPressed() {
if (isDirty) {
AlertDialog.Builder dialog = new AlertDialog.Builder(this);
dialog.setTitle("Save?");
dialog.setMessage("You have unsaved changes. Save them?");
dialog.setPositiveButton("Save", new DialogInterface.OnClickListener() {
@Override
public void onClick(DialogInterface dialog,
int which) {
save();
finish();
}
});
dialog.setNegativeButton("Discard", new DialogInterface.OnClickListener() {
@Override
public void onClick(DialogInterface dialog,
int which) {
finish();
}
});
dialog.show();
} else {
finish();
}
}
This works great, except I am occasionally prompted to save despite having made no changes. In such situations, I have, however, rotated my device or popped out the keyboard. In such situations, this is what happens to my Activity:
- onCreate is called, in which I register my TextWatcher
- onRestoreInstanceState is called, and the text of the EditText is restored, triggering the afterTextChanged callback
The fix is to simply not register my TextWatcher until after onRestoreInstanceState. The documentation suggests that onPostCreate is a good place to do that:
@Override
public void onPostCreate(Bundle savedInstanceState) {
super.onPostCreate(savedInstanceState);
titleBox.addTextChangedListener(this);
}
A project for a programming languages course?
I'm to teach a course on programming languages at my mid-sized public university this spring. Historically, this course has served two purposes:
- Teach the students memory management, C, and C++.
- Run the students through a gauntlet of languages and paradigms (imperative, functional, logic, and object-oriented).
The first is a curriculum constraint; until recently, we have had no lower-division course with a systems bent. The second is all right by me -- I love languages and I love a lot of them.
The only thing is that in my own undergraduate course, we talked a lot about designing languages. I've had a few chances to use flex/bison (lex/yacc) and ANTLR for some tiny languages, and I want my students to get in on the grammar writing and translating too. As such, I've been thinking hard about a fun and tractable semester-long project that would get them to design a language and implement a translator. Following is a sketch of my idea.
(There are a few other things you should know: we have no compilers course and our elective and low-enrollment theory course is offered only every two or three years. There's some room to discuss language theory and recognition in this course.)
The project
Students over the course of the semester will craft two languages related to interactive fiction (IF). The first, a world description language, allows authors to express the interactive fiction worlds, describing each "room," its contents (let's call them "tangibles"), and how it connects to other rooms. The second allows a player to traverse an IF world, likely supporting commands like "east," "look," "inventory," etc.
The entire class will form the Interactive Fiction Language Review Board (IFLaRB). This board will draft specifications for the two languages in a collective process overseen by one chairperson (elected by his peers and receiving 3% extra credit). The chairperson may call a meeting up to two times during the semester (in lieu of 50-minute lecture). Through discussion and voting, the board will standardize the two languages and the chairperson will publish the grammars on the class discussion board by the 6th week of class. Alterations to the language (called "edits"), are allowed up until the 8th week. Thereafter, no alterations to the language will be allowed.
Prior to IFLaRB's first meeting (hopefully) each team will have played Adventure, read the Zork paper, and drafted a prototype language to facilitate discussion.
Meanwhile, members of the board will have organized themselves in teams of two or three. Each team is a small software development company whose two tasks are 1) to write an interactive utility that accepts a file in the world description language and offers the player a REPL interpreter for traversing it and 2) to write a work of interactive fiction in the world description language. Translation must be done using ANTLR and the target language is C++ (using ANTLR's C target, since ANTLR doesn't have a working C++ target). The IF work must be published on the course blog prior to the 12th week of the semester.
Each team will be graded on their completeness in supporting the grammars (including their ability to support other teams' works), their clever and clear use of C++, and their development and release of so-called "challenge worlds" which attempt to break other teams' translators.
Will it work?
I don't know.
Concession
These languages the students design aren't necessarily going to be Turing complete. The world description language the students develop may simply be declarative. Probably subprogram structures will not come into play. Maybe conditional statements could be used to support extensions to the language? Not a bad idea, but I'm interested in minimizing complexity until I know how this goes.
Naming patterns
This past semester I taught an introductory Java programming course. When it came time to discuss iteration, we started with while loops and then moved on to for loops. (I prefer this order, because the update step doesn't appear before the loop body.) I asked the class about their relative merits and which should be used when. One gentleman whose last name is Kubicek shared that for loops should be used for simple count-controlled repetition, and while loops for everything else. I agreed with him and jocularly labeled his statement the Kubicek Principle.
Several lectures later, we were writing some code and needed a loop. I asked which we should use, and a student stated, "By the Kubicek Principle, we should ..." It was nice.
As I prepare for another semester of this same course, I think I might expand our use of these named principles and patterns. For some reason, just calling something a "declaration" doesn't have a lot of traction with many students. But suppose we called
type name;
something catchy, like Pattern D? Or perhaps the real value is in giving students ownership of such names? Developing their own vocabulary may empower them in a field where others are often making decisions that they must abide by.
I'll give it a shot.
Illusionation
Optical illusions are fascinating. Daniel Kersten shares this one, in which perceived shape influences our perception of shading:
Shape influences our perception of shading.
Apparently shape is more compelling than color when it comes to interpreting our environment?
He also explores the interplay between shadow and depth.
I was working on a little two-player Chinese Checkers game and found that a fast-rotating light source makes the marbles dance wildly in my visual cortex, though the marbles themselves aren't moving at all:
We're fun.
Symbolic math in MATLAB
MATLAB's symbolic toolbox is really quite nice. I've been simplifying some of my matrix code lately, and I've used MATLAB to verify that my simplifications were correct. For instance, here I compute and simplify the inverse of an orthographic transformation matrix.
An orthographic transformation is a scale followed by translation. It's inverse is the inverse translation followed by the inverse scale. To simplify matrix creation, I've defined two functions:
function S = scale(x, y, z)
S = [x 0 0 0;
0 y 0 0;
0 0 z 0;
0 0 0 1];
function T = translate(x, y, z)
T = [1 0 0 x;
0 1 0 y;
0 0 1 z;
0 0 0 1];
Now I can assemble the inverse scale and inverse translation:
>> % Create some symbolic variables that define the viewing volume >> syms l r b t n f >> % Invert the translation component of the orthographic transformation. >> T = translate((r + l) / (r - l), (t + b) / (t - b), (f + n) / (f - n)) T = [ 1, 0, 0, -(l + r)/(l - r)] [ 0, 1, 0, -(b + t)/(b - t)] [ 0, 0, 1, (f + n)/(f - n)] [ 0, 0, 0, 1] >> % Invert the scale component of the orthographic transformation. >> S = scale((r - l) / 2, (t - b) / 2, (f - n) / 2) S = [ r/2 - l/2, 0, 0, 0] [ 0, t/2 - b/2, 0, 0] [ 0, 0, f/2 - n/2, 0] [ 0, 0, 0, 1]
I don't like the asymmetry across the rows of T. The symbolic toolbox organizes symbols alphabetically, popping l before r and b before t. I'm not sure if there's a way to control this apart from picking different names.
Now, what's the product?
>> S * T ans = [ r/2 - l/2, 0, 0, ((l + r)*(l/2 - r/2))/(l - r)] [ 0, t/2 - b/2, 0, ((b + t)*(b/2 - t/2))/(b - t)] [ 0, 0, f/2 - n/2, ((f + n)*(f/2 - n/2))/(f - n)] [ 0, 0, 0, 1]
Blech. Let's simplify:
>> simplify(S * T) ans = [ r/2 - l/2, 0, 0, l/2 + r/2] [ 0, t/2 - b/2, 0, b/2 + t/2] [ 0, 0, f/2 - n/2, f/2 + n/2] [ 0, 0, 0, 1]
That's pretty good. The common denominators don't seem to coalesce. It'd be nice to have control over that.
Android templates
Dialog with items
AlertDialog.Builder dialog = new AlertDialog.Builder(this);
dialog.setTitle(title);
dialog.setItems(items, new DialogInterface.OnClickListener() {
@Override
public void onClick(DialogInterface dialog,
int which) {
}
});
dialog.show();
Handling spawned Activity
@Override
protected void onActivityResult(int requestCode,
int resultCode,
Intent data) {
}
ggplot to EPS to LaTeX
For a paper I'm writing, I use R's ggplot library to produce EPS figures. I then include these in my LaTeX source. Unfortunately, the labels and caption are maligned:
Bad text in EPS figure
The problem is fixed by using the ps2pdf utility. I'm not entirely sure what the problem is, but the prepress option produces a big PDF, embedding fonts and so on:
ps2pdf14 -dPDFSETTINGS=/prepress bad.eps good.pdf pdftops -eps good.pdf good.eps ps2eps good.eps mv good.eps.eps good.eps
And the result is beautiful:
Good text in EPS figure, thanks to some utilities