ChapterZero

I mentioned earlier my intent to contact one of the CG groups here at Caltech. I finally got around to it, much belatedly, and sent off an email to the lead investigator in the Multiresolution Modeling group. I hate the tension and suspense involved with the search for an advisor, but I do appreciate the opportunities it has given me for exercising my informative-persuasive writing skills.

My fingers are crossed: I don’t have any formal experience in CG at all. On the other hand, I’ve always found it an intriguing area– it certainly produces a lot of really interesting papers that involve math of a tasty geometric flavor (cf. my citeulike links, which are 95%+ CG papers)– and I’ve read a lot on raytracing and some global illumination algorithms, so I’m familiar with the basic ideas.

Then there’s always the wildcards of whether the professor can afford to take on any new students, or even wants to.

I finally got a working implicit curve tracer running in Mathematica. It has severe limitations: the user must supply a seed point, tolerance, and step size, it only traces one connected curve from a given seed point, and if the curve escapes to infinity, so will the tracer.

On the upside, the algorithm does not require any analytic information– a density field would work as well as an analytic expression; all that’s necessary is that the surface is specified by the zero-level set of some function continuously differentiable on a compact neighborhood of the surface (in particular, normals must exist at each point in this set).

Overall, it’s a good starting point for a more robust algorithm.I’ve uploaded the Mathematica notebook– it’s uncommented, but is short enough to be self-explanatory, given the overview in this post. I’ll post any updates in the same place. Here’s a sample of its work for the surface , with starting point

Mathematica’s ImplicitPlot

tracing code’s results

How it works: Given a point on the surface, the outer normal is calculated using a 2nd FDD scheme (the stepsize for this FDD is one of those annoyingly necessary parameters), and the counterclockwise tangent vector is found by rotating the normal. Then a step is taken along this tangent vector (size determined by another parameter) to start looking for another point on the surface. The next surface point is determined by finding a root of the function starting from this candidate point, using Newton’s method. Proceeding in this manner until you return close to the original point (another parameter determined how close that it), you get samples of the curve.

Essentially the same algorithm can be used in 3D to polygonize surfaces, except instead of sampling points, you’re sampling triangles in the tangent plane, and instead of having a 1-dimensional front, the algorithm proceeds along multiple 2-dimensional fronts. I could probably adapt some of the techniques used to resolve the more complicated problems in the 3D regime to ease some of the restrictions of the code.

My reference was A marching method for the triangulation of surfaces by Hartmann. BTW, how can I get my hands on a copy of Hartmann’s paper “Numerical implicitization for intersection and Gn-continuous blending of surfaces”, without actually paying for it– or even a paper with equivalent ideas? Apparently Caltech doesn’t have it available electronically or in a paper copy.

Update While considering how to analyze the error involved with approximating an implicit curve using this algorithm, I realized that this curve tracer is pretty much looking at an implicit curve as the solution to an ODE and solving it using Euler’s method. The projection step is like a reinitialization process that helps keep down cumulative error.

I just lost my ‘huge credit card purchase’ virginity. I wonder if– as my father would probably contend with a smug air of certainty– it’s all down hill from here. Will I join the numberless ranks of the morbidly indebted? Is my credit rating on its way to a number so low that I’ll even stop receiving credit card applications? … Probably not. I’m holding on to the belief that the feelings of nausea and surreality induced by the spending of large sums of money in a short period of time will keep me financially healthy.

So what did I buy? The Canon Rebel XTi, which I’ve been looking at forever, but couldn’t summon up the courage to plunk down the cash for. Photography has been a hobby for another time for me since I took a 35mm photography course in middle school and got addicted to it. Digital camera prices have become compatible with my financial situation, so that other time has arrived. I’m surprised and pleased that newegg had such a good deal on the Rebel– their combo deal was incredible.

And of course, I bought a new computer. After 6 years of faithful service, it’s past time to retire my Compaq Deskpro; even under Debian, I’m noticing major latency issues. Lately, using Iceweasel has involved a torturous routine of periodic restarting and rebooting to keep responsivity up. Forget about, say, running Blender. I’ve decided to use Ubuntu on the new laptop, but since there is exponentially more information on using Photoshop to retouch photos (I’ve only seen one good book on Gimp at amazon), if it’s straightforward, I’ll set it up dual boot with XP.

Can’t wait to get my new stuff! It should be here by mid next week.

How does one determine that a complex integral is multivalued? Like, without knowing that , how would you know that is multivalued? And, since you don’t know a closed form expression for , how can you tell that it’s multivalued?

Let . Show that any compact convex set in with an interior point is homeomorphic to .

I spent about three hours on Friday night converging toward an install process for pbrt– the instructions on the CD that come with the book are outdated, and the forums on pbrt weren’t incredibly helpful. It turned out you have to install some auxiliary libraries first– this was the hard part: I found I had to delve into config.log to solve some problems. So, if you’re interested in compiling pbrt (I expect you probably found the site through Google, so welcome ), here’s the process that worked for me.

These directions assume bash is being used, and that your home directory is /home/gittens. Also, due to the use of the pre tag, some of the longer instructions may be partially occluded by other page elements. To see them in their entirety, copy and paste them into a text editor.

First get the IlmBase and OpenEXR libraries from openexr.com. Install IlmBase with

./configure --prefix=/home/gittens/usr
make; make install

then install OpenEXR with

LD_LIBRARY_PATH=/home/gittens/usr LDFLAGS=-lpthread ./configure --prefix=/home/gittens/usr
make; make install

Now you should be able to install pbrt directly (I’m assuming you have the other, more standard-issue libraries already installed, such as libtiff and zlib– if not, these libraries have been around so long that installing them to /home/gittens/usr should be a streamlined, painless process). There are a couple of changes to be made to the Makefile:

• change the EXRINCLUDE, EXRLIBDIR variables to point to /home/gittens/usr/include/OpenEXR and /home/gittens/urs/lib.
• If you want to instrument the code for debugging with, e.g. gdb, change the line OPT=-O2 to OPT=-g. pbrt will run slower, but being able to debug is necessary for some exercises in the book, and might be useful besides.

Then a simple make should suffice; the pbrt executable is in the bin directory.

If additionally, you want to use the tools in the pbrt distribution (most useful is the exrtotiff application, that converts pbrt’s native EXR output format to TIFF– you’ll probably want this unless you have a working EXR viewer lieing around, and how likely is that?), you need to edit the Makefile in that dir also:

• Change the OPT to -O2 from -g (you’re not going to be debugging any of the tools, right?)
• Change the CXXFLAGS from $(OPT) -I/sw/include -I$(EXRDIR)/include -I$(PBRTDIR)/core to -I/home/gittens/usr/include/OpenEXR -I$(PBRTDIR)/core
• Change LDFLAGS = -L$(EXRDIR)/lib-linux to LDFLAGS=/home/gittens/usr/lib

To run pbrt, you’re going to need to make sure that the auxiliary libraries are in the linker’s search path and set up pbrt’s search path.
Write the following sh script into setupenv.sh:

export LD_LIBRARY_PATH=/home/gittens/usr/lib
export PBRT_SEARCHPATH=/home/gittens/work/pbrt-1.03/bin
export PATH=$PATH:PBRT_SEARCHPATH

and run this before you invoke pbrt.

Wow! I feel like I’ve just discovered a brave new world of possibilities.

I took a study break earlier today and wound up in the library; due to the internal creative pressures that have been building lately, I gravitated towards the CG books. I found a literate programming book which develops, from scratch, pbrt, a C++ production-quality racetracer, while explaining both the algorithms used and their practical implementation. pbrt is designed to be extensible, so if I read my way through the book, I’ll be in a position to implement some of the techniques from the SIGGRAPH papers at citeseer which currently taunt me with their inacessibility.

Also, I picked up a book on nonphotorealistic rendering, which although I have no interest in reading capapie, has a section on simulating various pencil strokes (HB, etc) on different weights of paper– the results look incredible– which has reawakened my very specific interest in that subfield of NPR. So my weekend recreational reading is accounted for.

Back to the main topic: DIY fabrication. I did not know it was feasible, until I came across an Evil Mad Scientist Laboratory entry on the CandyFab 4000– a home-built fabrication system that uses sugar as the molding material. They assert that the system can be built for under $500. It can also be driven by POV models. Anyone here at Caltech interested in working on a little project with me?

The same article mentions the RepRap and Fab@Home home fabrication systems, which both handle multiple fabrication materials (e.g. the Fab@Home system has been used to fabricate a working flashlight from silicon, conductive silicon, and epoxy), but are limited to producing models of smaller sizes, and just aren’t as cool!

Finally, there’s San Francisco’s Tech Shop, with its $100 monthly membership, which provides its members with access to a smorgasborg of manufacturing machines. Theirs must be a unique business model– imagine the liability issues– but, it’s an idea that I hope catches on elsewhere. I can tell you, if there had been such a business in Houston when I was a child, I’d be a different person today in a different place doing something very different.

I’ve been busy studing for my quals lately… at the slow rate of about 1 problem per day. In the interest of sharing the joy,

You are lost in the National Park of Bandrika. Tourists comprise two-thirds of the visitors to the park, and give a correct answer to request for directions with probability 3/4. (Answers to repeated questions are independent, even if the question and the person are the same). If you ask a Bandrikan for directions, the answer is always false.

1. You ask a passer-by whether the exit from the park is East or West. The answer is East. What is the probability that it is correct?
2. You ask the same person again, and receive the same reply. Show the probability that it is correct is 1/2.
3. You ask the same person again, and receive the same reply. What is the probability that it is correct?
4. You ask for the fourth time, and receive the answer East. Show that the probability it is correct is 27/70.
5. Show that, had the fourth answer been West instead, the probability that that East is nevertheless correct is 9/10.

— Grimmet and Stirzaker 3rd ed prob 35 in chapter 1.

Here’s another (more interesting, and easier) probability problem:

10 per cent of the surface of a sphere is coloured blue, the rest is red. Show that, irrespective of the manner in which the colours are distributed, it is possible to inscribe a cube in S with all its vertices red.

Caltech’s library system is disappointing. The technical books are split between two libraries in two separate buildings– one is for ‘engineering’, and the other is more theoretical– but there doesn’t seem to be a consistent criterion used in determining what books go where. For instance, the vast majority of the computer books are in the engineering library (SFL), but there is maybe half a shelf of (dated, almost useless) computer books in the Millikan library.

The math selection is small in comparison to the University of Houston’s or Texas A&M at College Station’s, but it is comprehensive enough that I can’t complain I can’t find some book on a subject I’m interested in. The situation is more dire with the computer books — there are some huge gaps in books on specific programming languages and tools, e.g. there are virtually no books on web application development. I believe we just started the popular fiction collection, so it’s small enough that at a leisurely pace I read all the available good science fiction within months of arriving here. Requesting books to be put on hold is not as convenient as it could be: instead of using a website, you have to call in or go to a librarian’s desk.

All these failing pale in comparison to the lack of a sane interlibrary loan system. I didn’t realize how sweet I had it as an undergraduate: if I came across a book not in our library, I could go the library’s website and submit an ILL request with no questions asked, and get the book in a week or so. All of this was no charge– I never questioned this; it seems like a reasonable service for a university or college to provide, considering their role in the dissemination of knowledge, and the amount of money you pay in tuition. Imagine my surprise when I discovered that Caltech doesn’t provide ILL for free! Instead, it charges $6.50 per book. I’m (theoretically at least, since as a grad student, the institute comps my tuition) paying a heck of a lot more money here than I was as an undergrad, and they expect me to pay $6.50 per book?

A quick check verified that UCLA and USC provide ILL free to their students, and UC Irvine has a more complicated but still essentially free ILL policy. My question: what’s the reasoning behind CalTech’s ILL policy? And am I the only person who cares?

Not all things are bad about the library system here, though. The libraries are accessible until 1am; unless books are requested by other patrons, the borrowing period is the entire term; and as a consequence of that last fact, I haven’t had to pay a late fee, ever. Maybe the lack of late fees is the problem– revenue from those could help offset the logistical costs of ILL.