The Most Scenic Lunch in Vancouver

---

Shape Processing Siggraph Papers

Another day, another set of Siggraph papers.

The first paper session today concerned clever things to do with shapes.

The first paper was Making Burr Puzzles From 3D Models by Shiqing Xin, Chi-Fu Lai, Chi-Wing Fu, Tien-Tsin Wong, Ying He, and Daniel Cohen-Or.

A Burr Puzzle is a collection of puzzle pieces that only fit together one particular way, in a particular order, to create the final shape.

Once the last piece is inserted, the entire puzzle holds together.

These puzzles are very popular in China and Japan.

Currently, most Burr Puzzles are designed manually.

The paper proposes a way to automate the process.





The canonical design of the puzzle, a set of six interlocking beams called a knot, was developed in Germany in the late 1600s.

The paper shows a method of inserting a knot in the middle of a 3-D shape, and then projecting the piece cuts of the knot onto the surface.

This causes problems with outlying features (the ears of a bunny, etc.) so the algorithm has methods to detect these and adjust the cuts.

Some shapes, such as a donut, can’t be handled this way.

The paper describes how to use a more complicated type of puzzle design, the knot network, to handle them.

A knot network is a series of knots where one can only be completed if other knots in the network are already assembled.

The paper has several examples of shapes turned into puzzles, including one shape used in early graphics research that has become a cliché, a clay bunny from Stanford University.

For the final step of this very through paper, the researchers printed some puzzles with a 3-D printer and assembled them, to show they had the needed properties of the puzzle.





I really enjoyed this paper.

It thoroughly details a clever solution to an interesting problem.

The math is easy to follow and the effects of the algorithm were easy to visualize.





The next paper was A Geometric Study of V-Style Pop-Ups: Theories and Algorithms by Xianying Li, Yan Gu, Tao Ju, Yan Gu and Shi-min Hu.

Most people are familiar with the pop-up books read as kids.

Open the page, and a structure lifts up.

Some of these structures have incredible complexity.

Currently, all of them are designed by artists through trial and error.

The paper analyzes the design process as an applied geometry problem.

It lists a set of requirements that pop-ups must satisfy in order to work (for example, two parts can’t collide while moving) and translates them into vector constraints.

Next, the paper describes a set of canonical design primitives and proves that all of them meet the constraints.

Finally, the paper presents a way of taking an input shape and turning it into a pop-up by combining the design primitives.





This paper has incredibly complex math, with the most intense vector algebra I have ever seen.

During the presentation I got very lost.

Reading the paper afterward I was able to follow the equations by visualizing the vectors and planes in space.

As noted yesterday, I process math by visualization; the equations by themselves are too abstract.





The next paper was Depixelizing Pixel Art by Johannes Kopf and Dani Lischinski.

Early personal computers did not have much display memory.

Artists became really adept at creating aesthetically pleasing designs using a small number of screen pixels, for games in particular.

Many people who used computers in those days have a remarkable fondness for this type of artwork, which now looks as retro as 1950s space age design.

Computers quickly gained more processor power and memory, which led to the ability to display ever more complex graphics.

Large blocky characters in few colors gave way to ones with thousands of pixels in near lifelike color.

When old characters are displayed on these new machines, they appear like collections of large blocks, which look horrible.





The paper addresses this problem.

It describes how to apply techniques from machine vision to extract the underlying structure of a character.

The algorithm includes lots of heuristics to handle tricky cases like two set pixels joining on a corner.

With the underlying structure in hand, the algorithm then applies standard anti-aliasing techniques to round corners, smooth out angled lines, and otherwise make the graphic look better.





The algorithm works remarkably well on characters created for eight-bit machines.

They showed a number of examples.

Atari’s space invader character (which has only seventeen set pixels) looks like an alien afterward.

A blocky dolphin from an early Nintendo game became a cartoon.

They took a picture of the pixilated whale outside the convention center (see The Possible Future) and ran it through the algorithm; the result was a cartoon whale.

With characters from sixteen bit machines, however, the algorithm broke down.

These machines allow a much wider range of colors, which affects heuristics that do color matching.

The algorithm tended to see these characters as lots of little blotches like an Impressionist painting, and created mush as a result.





The project overall was incredibly clever, but not something I’d want to do.

The main thrust of the algorithm is machine vision and analyzing existing images, while I’m more interested in how to create new ones.





The last paper was Digital Micrography by Ron Maharik, Mikhail Bessmeltsev, Alla Sheffer, Ariel Shamir, and Nathan Carr.

Micrography is a type of artwork made by arranging words, often a poem, to create a graphic.

These are currently done mostly by hand, a very tedious process.

Computers can automate some of it.

The paper presents an algorithm to generate these artworks fully automatically.





It generates the artwork by combining several existing concepts in a clever way.

The first step uses a vector field, a well known concept in mathmatics.

The field is defined by an equation, making easy to derive computationally.

This particular field is generated by drawing lines within a 2-D shape certain distances from the walls.

The text then follows the lines of the vector fields.

Creating the field strictly by following the shape would not produce a readable result, because it would contain sharp corners, places where lines join (called singularities) and other issues.

The solution is to start and end the vector field lines on some edges of the shape.

The question then becomes which ones?

Another well known mathematical concept, the graph cut, provides this data.

Every part of the shape is given weights based on various criteria (curvature, distance to other features, etc.) and the algorithm shows how to divide it up between which edges the vector field intersects and which edges it follows.

The final stage is to lay out the text, which is done by heuristic rules, and tweak the typography to make it readable.





The paper shows a clever reuse of existing algorithms to create something new.

I followed the math, easily visualized it, and the write up is very through.

I enjoyed the artwork it produced too.

This is my favorite paper of the conference so far.

Differential Geometry

My other paper session today was on differential geometry.

Various equations can be set up where the value of something varies over the surface of an object.

An object blowing in the wind, for example, has different air pressure over different parts.

Many graphics algorithms care about the value changes over the object surface.

These papers dealt with that type of calculation and how it can be applied to various problems.





First up was Discrete Laplacians on General Polygonal Meshes byMarc Alexa and Max Wardetzky.

Laplacians are a second order differential (a type of calculus operation) that comes up incredibly often in surface geometry operations.

Since computers can only calculate results to a certain precision, the result always contains some amount of error.

A vast body of research exists on how to do these calculations accurately.

Virtually all of it involves calculations over the surface of triangles.

The paper shows how to extend those algorithms to other types of polygons.

Much of the talk was the theoretical mathematics needed to derive the final algorithm; the actual implementation was simple.

I got very lost during this talk due to missing crucial background knowledge, and I could not visualize it either.





Next was the paper HOT: Hodge-Optimized Triangulations by Patrick Mullen, Pooran Memari, Fernando De Goes, and Mathieu Desbrun.

Objects in computer graphics are specified by meshes, mostly made of triangles.

Nearly all algorithms also need the normals to those triangles, the vector ninety degrees to the face.

These are always calculated by some equation (usually in linear algebra) which must be solved numerically in code.

These calculations always have some degree of error in the final results.

The algorithms based on the mesh and normals are sensitive to this error, so a great deal of research has been done to minimize it.

Traditionally, an algorithm can get the numeric error of either the mesh triangle locations or the normals very small, at the cost of the error in the other being larger.

This paper presents an algorithm that tries to minimize the effective collective error of both.

The presentation was incredibly math intensive.

I understood the concepts but found the particulars really hard to follow, and impossible to visualize.





Another paper was Spin Transformations of Discrete Surfaces by Keenan Crane, Ulrich Pinkall, andPeter Schröder.

The paper explored a new method of deforming shapes in a way that all parts are distorted roughly equally.

In graphics terminology, they avoid shearing the shape.

These transformations have the nice property that the shapes of the triangles in the mesh stay the same (although the size changes), preserving fine detail.

The main insight is a formula for embedding a 3D object into a 4D space with particular properties.

The embedding can be done in many ways.

Embed the object in the space in one way and then extract it out in another, and the result is a deformed object with the wanted properties.

The paper deals with how to express these concepts as equations, shows the properties they need to have to create a useful transformation, and then shows how to solve them respecting the inherit precision limitations of mathematical calculations on a computer.

This paper is also incredibly math intensive.

Like the other papers in this session, I found the math hard to follow due to missing background knowledge.

Vancouver Harbor, and the Sea Bus

Between the two paper sessions, I had what may be the most scenic lunch in Vancouver.

The city sits on an absolutely beautiful natural harbor.

The towers of the city rise on the south side, and a long chain of mountains rises on the other.

I could see the mountains from the convention center in many places.

When the fog cooperated, they were as beautiful as the Olympics.





Like many cities with great harbors, Vancouver has several companies that offer scenic cruises.

Most of them sold tickets outside the convention center.

Knowledgeable visitors mostly ignore these, because another method exists that is nearly as good and much cheaper.

We head for the Sea Bus.





The Sea Bus is a commuter ferry.

This particular ferry crosses from a pier near the convention center directly across the harbor.

The view is stupendous.

Big cargo ships float by along the way.

Since this is a ferry, the fare is ridiculously cheap.

Also since this is a ferry, it has very few window seats, and they are uncomfortable.

To get the view, arrive early enough to get a spot near the front of the queue, and grab a spot near the front door when the ferry docks.





On the north side of the harbor, the ferry docks at an area called Lonsdale Quay.

In 1986, for the same expo the original convention center was built for, the city turned these docks into a mall.

A giant red ‘Q’ sign revolves above it.

The mall has an incredible food court, close to that at Pikes Place in Seattle (see Do you Like Green Eggs and Ham, SAM I Am?).

The mall also has a nice open air deck, with a plaque listing all the ship types that come through the harbor.





The combination of the Sea Bus and that mall creates the scenic lunch.

A Sea Bus ticket is good for one free transfer within an hour.

Vancouver workers will take the Sea Bus to London Quay, quickly eat lunch there, exchange their original ticket for one going the other way, and return.

That is exactly what I did today.

The food was descent, and the view is incredible.

Flame Production Talk

I finished up the conference with a production talk, Light My Fire.

I have avoided animation and special effects for the entire conference so far, except for the festival screening, and I won’t have the full experience without seeing at least a bit of that side.

The one I went to is on simulating flame and dust effects.

The basic algorithm is called fluid simulation, where the computer models the flow of air as a fluid with the effect embedded in it, to various degrees of accuracy.

The physics is usually not completely accurate, both because it takes too long to compute and it may generate effects different to what the art director wants.

The panelists in this session talked about techniques they used to design their simulations.





The presenters were a team that worked on the movie Megamind, and a group from video game developer Q-Games.

The Megamind team showed a scene where a huge spaceship crashes down a city street, generating dust as it goes.

The dust cloud must bounce off buildings to look realistic.

The talk was on how they added custom extensions to a fluid animation package to get the level of detail they needed.

The amount of dust generated by the ship is much larger than most projects.

They showed a preliminary result of the cloud moving through random geometry, then the preliminary animation, and finally the finished scene with all the lighting detail added.

It was impressive.





Q-Games showed scenes from a game called PixelJunk Shooter 2.

The player runs around shooting things until they blow up.

In the past, the explosions would be pre-created animation.

In this case, the explosions change other parts of the game grid, so they have to be simulated.

They described the fluid solver they used to handle this, along with the optimizations they needed to get it to run at interactive rates.





I enjoyed the session as a movie fan.

I got to peek behind the curtain and see how the magic works.

I liked it much less as a software developer.

The projects are fundamentally about optimization.

The physics equations for fluid movement, the Navier Stokes were formulated in 1845.

Almost all work related to computer graphics has been about optimizing their implementation, to get needed levels of detail, speed, or both.

I’m less interested in this than other parts of software development.





What I experienced in the session matches up with what I learned talking to the animators yesterday.

From the perspective of an outsider, special effects work is incredibly fun and glamorous.

On the screen, people only see the thrilling results.

In reality, those results are produced by endless research and careful work, which gives a very different impression.

The conference gave me the chance to see that perspective, an unexpected and valuable benefit to being here.

I’ll never look at a special effects movie the same way again, for better and worse.





On the whole, Siggraph was well worth the expense of attending.

I got to experience a wide range of things related to graphics in one place.

I discovered that I really like artwork, especially things that resemble painting.

I particularly liked research that found clever solutions to problems, such as the digital micrography algorithm, the Burr Puzzle paper, and the papers that treated furniture arrangement as an application of the well studied cost algorithm.

I discovered that I depend heavy on spatial visualization, either of actual objects or abstract data structures, to understand algorithms.

Mathematics by itself is too abstract; I had to think about what people did with it.

I liked the art gallery, although some work was too focused on process for my taste.

I loved the piece on visualizing psychology through twitter feeds (see Explorations).

When I get home, I should spend time investigating visualization projects, digital art, and mobile graphics applications with WebGL.

Gastown

After the conference, I decided to wander around downtown Vancouver for a while.

I ultimately went to one of the oldest neighborhoods, Gastown.

Gastown is knocked by many residents as tourist central, with nothing but tacky souvenir shops.

It had plenty of those, but also beautiful old architecture, atmospheric cobblestone streets, and some great restaurants.





In one shop window, I noticed a large white blanket with colored stripes on it in various patterns.

Looking it up later, the blanket is a modern copy of one of Canada’s icons, the Hudson Bay point blanket.

The Hudson Bay Company was chartered in 1670 to harvest beaver pelts.

They developed towns across the far north of Canada, and ultimately built the largest beaver fur market in the world.

Like their compatriots to the south, they traded blankets to Native Americans in return for the beavers, the point blankets.

The pattern and color of the stripes indicate how many pelts they are worth.

The Hudson Bay Company still exists, although they have mutated into a department store chain.





Gastown is also notable because it is the only place in Vancouver I saw Canucks jerseys.

The Canucks are the Vancouver NHL team.

Roughly three months ago they lost the Stanly Cup finals to the Boston Bruins in a closely contested seven game series.

Fans reacted with one of the worst riots the city has ever seen.

It says something about Canadian politeness that I personally suffered no negativity while in the city this week.

Of course, I didn’t advertise that I live in New England either.





The neighborhood contains one of the city’s unmissible pieces of tourist kitsch, the steam clock.

It’s just what it sounds like, an outdoor mechanical clock powered by steam.

Hot water drips off the sides.

Every hour, the clock chimes with a series of old fashioned steam whistles, the type once found on trains.

This is less exciting than it sounds once the novelty wears off.





To celebrate the end of the conference, I wanted a meal a cut above the usual fare.

The front desk at my hotel recommended Steamworks Brewery.

Located near the clock, they are one of Vancouver’s best brew pubs.

Like Washington and Oregon next door, Vancouver has a vigorous beer culture.

Steamworks is notable for serving beer soon after brewing it.

The tanks are visible behind the bar.

For a brewpub, the food is quite good.

My one disappointment is that they served food exactly like what I have had across the border with nothing distinctly Canadian.

---

Photos

Sea Bus
The Sea Bus with downtown Vancouver in the background, from Lonsdale Quay

North Vancouver
North Vancouver and North Shore Mountains, from the Sea Bus

North Shore Mountains
From the Sea Bus

Burrard Inlet east
Eastern portion of Burrard Inlet, from the Sea Bus

Lonsdale Quay
Lonsdale Quay from the Sea Bus. Look for the large red Q sign on the right

Downtown Vancouver East
View from across the harbor at Lonsdale Quay

Vancouver and Convention Center
Downtown Vancouver and the Convention Center, from Lonsdale Quay across the harbor

Downtown Vancouver, West
View of Vancouver from across the harbor at from Lonsdale Quay

Stanley Park
Stanley Park, the largest in Vancouver, from Lonsdale Quay

Freighters
Freighters in Vancouver Harbor, from the Sea Bus

Downtown Vancouver
Downtown Vancouver from the Sea Bus, with the convention center front and center

Downtown Vancouver from Sea Bus
Section to the west of the Convention Center

Downtown Vancouver
Another shot of downtown Vancouver from the Sea Bus, centered on Waterfront Station

Waterfront Station
Inside of Waterfront Station where the Sea Bus docks. It was built in 1914 by the Canadian Pacific Railroad.

North Shore Mountains
From the Convention Center

North Shore Mountains
From the Convention Center

North Shore Mountains
From the Convention Center

North Shore Mountains
From the Convention Center

North Shore Mountains
From the Convention Center

North Shore Mountains
From the Convention Center