Was Google Earth Stolen?

I recently watched “The Billion Dollar Code” limited-series on Netflix, which claims that Google Earth is a rip-off of a project called TerraVision, created by the German art collective ART+COM. The show chronicles their lawsuit against Google, which ultimately failed.

I am drawn to stories of inventors having their work stolen by greedy assholes. I can genuinely relate to the inventors in this case, and their various struggles. If someone is owed credit or money for their invention, I want them get it. And I truly respect the early and innovative work done by ART+COM.

However, as a co-founder of the startup that built the original “Google Earth” PC app in 1999, and as one person who wrote (from scratch) many of the bits they claim are stolen, I am in a pretty good position to call bullshit on this.

I wrote a blog post in 2008 called “How Google Earth [Really] Works,” which explains in simple terms what’s unique about GE and its patents. You’d think anyone trying to answer “how does Google Earth really work?” would read it.

I’d honestly never heard of ART+COM or TerraVision until a month ago. I wasn’t contacted for the lawsuit, the series, or the “making of” featurette. I was mildly aware of an earlier and similar lawsuit by another company, also failed.

At Keyhole, I worked with the two brilliant real people named in the ART+COM lawsuit who were represented as a single fictional “Brian Andersson” character here. I imagine this was to avoid charges of defamation. One of the two sadly passed away this year. The reason that “Brian” was named in the suit was apparently that ART+COM believes “Brian” learned of their algorithm and then secretly recreated it. They claim “Brian” told them “Google Earth wouldn’t exist without you.”

For the ART+COM side, the series used two more fictional characters: “Juri Müller” and “Carsten Schlüter.” The “Making Of” special episode on Netflix highlights the four or five real people who reportedly built TerraView. I guess their names were fictionalized for dramatic purposes?

ART+COM filed its now-invalidated patent in December 1995, which was the basis of the real lawsuit two decades later. One month earlier, Silicon Graphics (SGI) filed a patent for “Clip Mapping,” which supports high quality whole-earth 3D rendering (flat earth or spherical), as explained in my blog post above. Google Earth uses a kind of clip mapping that goes beyond what SGI had done.

The timing of these two patents suggests one of two things are true:

1. ART+COM met with SGI and inspired a clueless-but-affable SGI executive (“Brian”) to schmooze them until they revealed their secret algorithm. They then flew back to Germany, while SGI flew back in time, not to recreate ART+COM’s code, but to begin work on a superior technique for its own customers, which ART+COM apparently didn’t notice for years.
2. Or, perhaps SGI was already rendering high-quality large-scale 3D earth data, before ever meeting ART+COM. This would have been a natural outgrowth of decades of work on 3D flight and space simulators. Let’s also assume that SGI supported the NSA and NIMA national security analysts in their top secret work. A senior engineering manager (like “Brian”) would likely know about such secret work, but couldn’t disclose it. So when they met the ART+COM folks and saw their cool 3D planet demo, they invited them to a Burning Man like festival. Why? To get them drunk and steal their algorithm? No. To recruit them to join SGI. That explains “Brian’s” repeated praise and why these guys argued about moving to California.

If that’s not obvious enough, SGI built a public-facing demo called “From Space to [Your] Face” shown in 1996 or earlier that zoomed in from space to a 3D spot in the Alps, just like TerraView and Google Earth but constrained, to show off their new InfiniteReality hardware, using their novel clip-map technique. By 1996, the view zoomed all the way into a scale model of a Nintendo-64 console, which SGI had also quietly helped create.

AFAIK, SGI did this all without any ideas or code from ART+COM.

From SGI to Intrinsic Graphics

Chris Tanner (not one of the “Brians,” but a big brain) invented the original “Clip Mapping” algorithm while working at SGI. It required a bit of special hardware to make it work, thus limiting it to SGI supercomputers. However, after leaving SGI, he invented a way to solve this same problem for ordinary consumer PC 3D graphics cards. His new solution was novel and earned its own patent, branded as “Universal Texture.” (see my blog post)

That, plus work that I and others added, is what enabled Keyhole to so quickly launch a PC-based EarthViewer app in 2001. PC-based deployment is a hard problem that ART+COM apparently never solved. Their algorithms apparently weren’t as efficient or advanced to make the leap to PCs.

I joined in 1998 as employee #2 of Intrinsic Graphics, where Chris, Remi Arnaud, and the real “Brians” were co-founders. We didn’t work in someone’s garage, but rather a converted post-office in downtown Mountain View. In 1999 we started Keyhole as a spin-off, with John Hanke joining as CEO.

I wrote my part of the codebase from scratch. The only thing we retained from earlier demos was Chris’s Universal Texture code, which became part of our 3D game engine. This was first version of what became “Google Earth.”

The Netflix show depicted the actual app and UI from our 2001 EarthViewer product, but claimed it came out in 2011 from Google. That’s a bizarre aspect to change, making the ART+COM folks seem clueless for a decade.

Keyhole joined Google in 2004, after struggling for several years to make money. In 2001 when EarthViewer was first launched, the real “Brians” were still running the parent company, Intrinsic Graphics, doing what Unity and Epic/Unreal now have billion dollar valuations to do. The main reason that stalled, IMO, was that most game developers preferred to write their own game engines in 2001. [I actually left in 2001 and never joined Google.]

By the 2010s, the source code for Google Earth was evidently rewritten in Javascript to use WebGL and run in ordinary web browsers, which was a long-time goal of ours for lowering “friction.” The lawsuit apparently refers to javascript code, which anyone could have analyzed with the right tools.

The problems ART+COM did solve are worthy of praise for the day, but are too obvious to patent or protect IMO.

For example, quad-trees were invented in the 1970s (maybe 1966 if you consider morton-codes). The idea is to subdivide a large map or image into 4 equal tiles, recursively. Each tile or “node” also gets subdivided into 4, repeating as needed. As you zoom into the planet, you begin with the “root node” or main tile, and then the algorithm finds smaller tiles with effectively higher and higher resolution as needed.

A typical quad-tree for the first four “levels.” Google Earth had 26+ levels.

Clip-mapping and Universal Texture both assume quad-tree subdivision of the source data, as do many other common uses, like storing roads and labels. I came up with a few optimizations that improved efficiency. The traditional “recursive descent” approach visits one node at a time, asking questions like “is this to the left, right, top, bottom, of some dividing lines?”

This suffers from CPU branch-prediction misses and extra overhead. But since our goal was to collect all of the nodes at the ideal resolutions for any given 3D view, non-recursive traversal is a bigger win. That might be what the lawyers poorly explained to the jury in the TV show. Or it could have been a part of Universal Texture. In any event, “quad-trees” are not novel or unique. And we went way beyond the basic approach.

The “addressing scheme” is something ART+COM also claimed was copied. No. My colleagues and I agreed on the simplest approach. Each quad node has four child nodes, named 0, 1, 2, 3 which is 00, 01, 10, 11 in binary. So the “address” of any given tile is just the string of these codes from the root down to the smallest child. Knowing that the first binary bit means up/down and the second means left/right allows the software to know the exact position and boundaries in space of any address, given only this string of bits (we might have reversed X and Y). It’s clever, efficient, but also not patent-worthy.

To be clear, Chris’s “Universal Texture” code is what managed the massive earth texture efficiently on a PC, and that was novel, though we never sued anyone. John Carmack later came up with his “Mega Texture” approach along similar lines, but with even more flexible arrangements. No one claimed Carmack stole his idea, though he did visit Keyhole and got early demos.

I improved Chris’s algorithm by adding compression and streaming, both very obvious things to add, which took me a few weeks early on. Chikai Ohazama and Phil Keslin built the network stack up from that point and made many more significant optimizations on the server.

Running the servers is the most expensive part of all this, so this efficiency matters. Mark Aubin, another Keyhole co-founder, attacked the problem of efficiently assembling many terabytes of source maps into one big map (see ortho-rectification, clip-gen) before we chopped it up into tiles for serving, saving considerable work at runtime. Angus Dorbie later wrote an entire custom tool for us to make this even more efficient.

Another collaborator, David Kornmann, implemented a continuous level of detail (CLOD) 3D terrain system that handled arbitrary surface detail. He added a clever solution to make the resulting terrain seamless (no gaps) by guessing the state of neighboring nodes, again effectively parallelizing the exploration of the dataset for better results.

If you look at their original videos, TerraVision shows visual popping between tiles when they change resolution, which looks more like how Microsoft and NASA implemented their “Virtual Earth” and “WorldWind” apps, respectively. It may take expert eyes to notice, but Google Earth is effectively seamless and can fly anywhere on Earth in about 2.5 seconds, with no lag (only blurriness if the tiles don’t arrive fast enough). It was able to run on circa 1999 PCs that only had 56k modems and 16–32MB of GPU texture memory. ART+COM always required an expensive supercomputer, AFAIK.

Showing two planet browsers side-by-side, as the lawyers are depicted in the TV show, doesn’t mean one of them must be stolen. All 3D planet browsers are supposed to look like the Earth, smoothly roaming and zooming. In fact, I even added cloud layers in my first UX prototypes, as well as stars, sun and moon.

If you’re looking for inspiration, we could cite examples from the 1970s to the early 90s, well before ART+COM did any work on this. It might be the same public inspiration for all of us. I’d certainly been dreaming of this personally, since the early 90s at least.

FWIW, we added many innovations that ART+COM didn’t and were much less obvious. Map makers spend months to years designing the labels for maps. I had to learn many of their techniques. But our real-time system optimized the labels in just 2–3 milliseconds, running sixty times per second. (Microsoft didn’t solve that part well, and did ART+COM at all?)

I also worked hard to make the UI more fun and responsive, using a common computer mouse to fly around — no giant trackball required. I invented an underlying system that’s similar to Functional Reactive Programming (think: React, etc…) to allow us to reprogram the guts of the app based on a simple declarative data-flow syntax. That system made Keyhole’s EarthViewer very fast and extensible and later lead to a global standard file format called KML.

These are just a few of the ways Keyhole went beyond anything I’ve seen from ART+COM, way before we had any resources from Google.

So What Did We Learn?

If Google had stolen anything from ART+COM, I would not defend it.

I’m openly critical of their ad-driven business model, especially since the damage is clearer. That’s broached in the show, but only to point out how much money Google would theoretically owe these guys if they’d agreed or been forced to license at 10 cents per use (which was very unlikely IMO).

Invading people’s privacy for profit is not something to yearn for. It’s one of the reasons I sold all my Google stock. I respect Google’s engineering work and the great “free” information they provide. There are a lot of smart and dedicated people working there. But the biz model is not ok, IMO.

My goal for Keyhole was always to offer a highly efficient “3D trellis” featuring useful spatial data for anyone to add their own geospatial data on top of, while retaining their individual legal rights to their data. This would have been the basis for our future in Augmented Reality. Google has barely scratched the surface of this virtual globe and it’s potential benefits to society.

All of the inventors I’ve mentioned by their real or fictional names deserve credit for their pioneering work on 3D planet browsers. All of them. Google may have acted like a billion-pound gorilla towards multiple small companies, and that could be relevant for government sanctions. However, I don’t believe anything was actually stolen from, copied from, or even directly inspired by ART+COM.

Whenever a movie says “based on a true story,” it’s likely to be fictionalizing large chunks of the story without sufficient validation, for dramatic, political, or other purposes. A lot of the theories in this TV series turn out to be bullshit.

You can interpret this story as being about greedy companies trying not to pay out, or greedy law firms seeking $300M dollar returns on a $10M investment. You can also recognize that even if the dialog in the show was 100% factual (and it strains credulity in places) there is a much simpler explanation to the story than CIA conspiracies and gratuitous and unnecessary IP theft.

ART+COM’s patent was invalidated in 2017 because another group, Sarnoff Research Center (SRI) in Palo Alto had shown a similar system in 1994, also called “TerraView”, which constituted prior art. In a supreme irony, the people asserting they “invented” Google Earth were bested by an earlier system with essentially the same name and function as theirs.

In my view, a bunch of smart people were separately trying to solve similar problems around the same time. They used their wits and the tools in the room to do so. Let’s celebrate their ingenuity and help everyone to achieve more in the future (and hopefully without the exploitive business models).