Bumblebee

What would happen if we took and pretended that we didn’t know where it’s origin was? One of the ramifications would be that points and vectors in that space would have to be considered different entities. When the origin is fixed and we know it any point in the space can be represented as the vector . This means that when we are working in an affine space (any point can be the origin), points are regarded as fixed locations in space and vectors are regarded as displacements without an origin — two different things.

Formally, an affine space consists of a vector space and a set of points such that:

• if then
• if and then

So, to specify an affine space we need a basis for (suppose it’s the image plane) and a point to act as the “unknown” origin. becomes the reference frame of the affine space. As usual, every vector in the affine space can be expressed as , while points are expressed as . In other words, vectors are of the form while points are of the form .

Does this remind you of anything? Yup, homogeneous coordinates. I believe this is why my lecture notes mentioned that “ is interpreted as a line (vector, horizon) when and as a point when .” It makes much more sense now then back when I first looked at that black magic of a sentence.

OK, so far so good. What really confuses me now, and confused some of my friends when they took the graphics course at UofT, is the question of why is it necessary to use affine spaces & homogeneous coordinates (and thus differentiate between points and vectors) in computer graphics? Why can’t we use our good old euclidean geometry? I believe the answer has to do with the types of transformations that euclidean geometry allows: only rigid-body transformations (i.e. identity, translations and rotations) are allowed and they preserve distances and angles.

Which classes of transformations are missing from that list and might be very useful in computer graphics? Linear transformations (e.g. scaling, reflection and shear), affine transformations (they preserve parallel lines) and projective transformations (artistic perspective). For instance, euclidean geometry says that two parallel lines never meet thus failing to describe perspective and the vanishing point on the horizon:

Projective geometry allows projective transformations such as the above. Euclidean geometry is a subset of affine and that in turn is a subset of projective, with respect to the classes of transformations each one includes. So, I presume that the answer to my question  is that in computer graphics people use projective geometry because it makes the end result much more realistic.

Some links to whet your appetite: #1, #2, #3, #4, #5, #6, #7

My first two lectures on computer graphics left me puzzled with some unanswered questions that have to do with basic projective geometry and its transformations. I’ll try to collect my thoughts and some links, and write them down primarily for the sake of summarizing to reduce my own confusion.

Basically, both in computer vision and in computer graphics the first geometric problem that we study is that of projecting points from a 3D scene to a 2D image plane (think of it as a photograph), using the pinhole camera model. The projection looks like this:

An important thing to notice on this picture is that any point that lies on one of the dotted lines will be projected to the same image location. This leads us to write for any nonzero , where is the euclidean coordinate system that we are accustomed to. This “equality” holds in the sense of equivalence classes, not in the sense of euclidean geometry.

Using a similar triangles argument we can prove that the pixel on the image is equal to . However, can also be viewed as part of the 3D scene like this provided that . The correspondence between image pixels and representatives of the equivalence classes of is one-to-one. The equivalence class corresponding to an image pixel is called the homogeneous coordinates of that pixel. Many of the articles that I found online assumed for the sake of simplicity and mentioned that the mapping is “just a trick” to be followed blindly because

What happens when ? In that case does not correspond to any point in the euclidean space, but to a unique point-at-infinity along the direction . The proof is in the first link.

Here are some of the links that might prove to be helpful for this topic: #1, #2

I am still alive; alive and feeling well. “When humans make plans, God laughs,” is a saying that can describe very well my life since September. After finishing an extremely satisfying summer, working with my friends and profs at the Department of Computer Science at UofT, I thought…no wait…I was sure that I was going to regain my focus to my classes. In a way, I was expecting that my third year here at UofT would simply be an improvement in terms of my academic efficiency over my previous couple of years. “Yes,” I thought, “this year I will be so focused that I’ll be able to manage my homework, get involved in extracurricular activities and go out to have fun with my friends,” assuming that nothing extremely unusual will happen to me.

Thankfully, I was wrong. I met a lot of new friends, most of them Albanians, who welcomed me to their group. Meeting other people from Albania is always fun, because there are so few of us and yet we have spread in almost every corner of the world (although, I still haven’t heard of any Albanians living in the Arctic, but who knows) . Our language and common background unites us immediately, even if our families are not related, and even our hometowns are far apart.

A s far as courses are concerned, I have realized that the more high-level Math courses I take, the less they relate to any aspect of Computer Science and the less they seem helpful to anything I do outside the classroom, even if it is technical. Take Group Theory for example: we study groups (sets together with an addition-like operation), rings (sets together with an addition and a multiplication-like operation) and fields (sets together with basic operations, just like the ones you’ve been almost unconsciously using since grade 1). Of course, the material is not that easy because otherwise I wouldn’t be complaining about it. There are literally hundreds of theorems that you have to be familiar with, few of which are applicable to a wide collection of problems. Unfortunately, there are few standard methods that you can use to solve problems, as opposed to first-year Calculus, where you had a “standard” arsenal of techniques that could solve 90% of your problems — I mean math ones. In Group Theory it seems to me so far, after 1.5 semesters in this year-long course, I haven’t used the same technique in more than one problem — it’s fascinating, the complete opposite of what I think of the material.

And then of course, there is Real Analysis. I frequently think that the very reason I decided to study Math together with CS was Analysis. But taking this course is really testing my will. We have been studying convergence of sequences of functions and then measurability and Lebesgue integration. Again, I have to admit: this material is extremely interesting, but there is an asterisk at the end of that phrase saying “if you want to be a mathematician,” written in tiny font.

That’s what the people who design programs of study that combine a major in X with Math have got wrong, in my opinion. Including these courses in programs of study for non-mathematicians does indeed guarantee that their preparation in math is solid, but it does not attempt at all to teach math skills that might be somewhat applicable to discipline X. For instance, if Johnny is doing a double specialist in Comp Sci and Math then why not teach Johnny material that might help him in his main course of study, say Combinatorics or Graph Theory or Linear Programming & Network Flows, or Discrete Math, or Number Theory or something that will be more than just another course to him. Because when Johnny decided to include math in his studies, I’m sure he didn’t do it just for the “coolness” of it, or just because math is “generally interesting and useful.” No! It has to be interesting and useful to Johnny, by supplementing his studies in CS with a more theoretical preparation.

So, after three years the time to decide which rabbit to chase finally came, and I chose Comp Sci, simply because at this point, even a Hello World program seems more creative and practical and constructive than studying material whose homework requirements outweigh its benefits by miles. Don’t worry though, I haven’t become soft and whiny yet; I can still handle hard times. The fact that I haven’t changed my program of studies and I am still trying proves that. Nevertheless, the requirements of these courses are starting to become scary –maybe it’s time to hug my mom. Yes, that will fix everything, for sure.