The Coming Public Point Cloud

One of the most important elements of Augmented Reality is the ability to seamlessly mesh 3D graphics with the real world.  Current AR technology simply overlays graphics on top of video–even when tracking and recognizing objects like cards and markers. The AR SDK gives the position and orientation of the tracked object to a 3D engine which then renders geometry on top of the video frame coming from the device’s camera.

A 3D scan of myself overlaid on an AR card with Vuforia.

A 3D scan of myself overlaid on an AR card with Vuforia.

New technologies like Google’s Tango Tablet use Kinect-style depth cameras to store not only the color of each pixel, but the depth and position, too. (Well, sort of–the depth camera’s resolution is much lower than that of the color camera). This means that you can build a 3D model out of what the tablet’s camera sees as you move around an environment.

Tango displaying point cloud data of what it currently sees.

Tango displaying point cloud data of what it currently sees.

This feature has huge ramifications. Tango uses this data to do what is called “localization.” This means once an area is scanned, the tablet can compare the internal 3D model of the current environment it has stored with what the camera is currently seeing. When fused with compass and gyro data, the Tango tablet can compute its precise location inside the scanned area. This doesn’t take long either. Tango starts building the model immediately. Walk back to where you started using the tablet, and Tango knows where it is.

Usually this 3D data is stored as a point cloud. This is basically a 3D point for every position the 3D camera records.  Hence, a sufficiently complicated area will look like a cloud of dots–a point cloud. You can see an example of the Tango building a point cloud with the Room Scanner Tango app.

These point clouds are important for not only localization, but AR graphical effects such as occluding rendered 3D objects with the real world.  This is because a 3D mesh can be built out of these points which can be used for occlusion, collision and other features. Having objects in between you and the augmentation occlude the 3D render is essential to nailing the feeling that an AR object is really there.

Point clouds are awesome, but building them can be frustrating. Current point cloud scanners are bulky and slow, not to mention their accuracy issues can lead to jitter and other artifacts. Also, some depth cameras run at a frame rate low enough to make it hard to create point clouds without moving very slowly through an environment. Who wants to play a game where you have to walk around and meticulously scan a room before you can start?

In order for AR games and apps to succeed, devices need to effortlessly be able to sense and detect the 3D geometry of their surroundings. Yet, quick and instant generation of point clouds is far beyond the capabilities of current mobile sensor technology.

That’s where the public point cloud comes in.

A truly great Augmented Reality platform needs to upload point clouds generated by devices to the cloud.  Then, when a user uses some hot new wearable AR glasses, it can pull down a pre-made point cloud for the current location off of a server and use that until the glasses can update it from its own sensors. The device will then upload a fresh point cloud which can be used to refine the version stored online.

You can kind of see this already–Google and Apple Maps’ 3D satellite mode use similar point cloud reconstruction techniques presumably from aerial photos and other sources. Whereas these 3D models often look like something you’d see on the original PlayStation, the public point cloud will have to be much more detailed.  As sensors on mobile devices become more advanced, the crowdsourced point cloud data will become incredibly detailed.

Apple Maps' 3D reconstruction kind of looks like an original PlayStation game. The public point cloud will have to be higher resolution.

This 3D reconstruction kind of looks like an original PlayStation game. The public point cloud will have to be higher resolution. Oh, this is also where you can bet the best pastrami sandwich on the planet.

A massive, publicly accessible point cloud is not just necessary for the next generation of AR wearable devices. But also for self driving cars, drone navigation, and robotics (which is indeed where many of these algorithms came from in the first place). Privacy implications do exist, but perhaps not more so than Google Maps’ street view, or other current technologies that give you very precise information about your location.

In the near future, almost every public place on the planet will be stored in the cloud as 3D reconstructed geometry–passively built up and constantly refined by sensors embedded on countless mobile and wearable devices, perhaps without the user even knowing.

Social Recruiting: Google App Engine Experiments 3

My latest experiment is a “social hiring” tool built on top of Google App Engine: zenthousand.

We don’t have a tech talent crisis in America, we have a hiring crisis. Between clueless recruiters and the oblivious companies that rely on them, it’s no wonder nobody can hire effectively.

The thinking exhibited by a lot of employers is if you actually respond to a job post or are actively looking for a position, you must be a total loser. The race is on to hire people who don’t want a job. So, I decided to build a site that pulled in data from Github, Meetup, Stackoverflow, Behance, and other social networks developers gather on to allow people to search for so-called passive candidates. There are countless startups doing the exact same thing under the banner of social recruiting.

This didn’t deter me because last time I tried to build a startup it was something nobody else had done before. It turns out, doing something that’s been done half a dozen times is preferable–at least to investors. Plus, it really didn’t seem that hard to make. How is it that so many companies have raised rounds to do something seemingly so trivial? I wanted to find out.

It took about 3 weeks, but the end result is zenthousand. It’s rough, buggy, and features a useless and sparsely populated database. Still, it gets the point across. Sign up for an account and start searching for candidates based on location and skill set. Bookmark the ones you like so you can browse and annotate them later. Oh, and the paid options use Stripe for billing, but just use the free demo account to test it out. I don’t expect anyone to actually pay for this in its current state.

Building a service like this is like being a detective. Think about where developers hang out and what footprints they may leave. Then write an algorithm using publicly available APIs to extract this information and organize it in a searchable way.

The location search isn’t very accurate–try using no location for more results. I’m using Google’s beta search API which seems to have some bugs in it. Also, not a lot of Github profiles have location attached to them, so I have to spend a bit more time trying to sniff out where candidates are from. I have yet to run the Meetup and Stackoverflow crawlers either, so most profiles only have a Github profile attached.

Most social recruiting startups claim to use big data analysis to detect how skilled a candidate is in specific technology. This is absolute nonsense. No algorithm can overcome Dunning-Kruger. There is no substitute for an interview facilitated by someone with expertise in the area you are hiring for. That’s not to say big data algorithms aren’t useful for filtering candidates by what’s relevant to the user.

Zenthousand was a 3 week crash course in Google App Engine with Python, social network APIs, and finessing an interface with Twitter Bootstrap. As much as I’m infatuated with GAE as of late, I think a big data service like this is too expensive to run on it. If I take this project further, I’ll most likely re-write the GAE-specific parts, migrate to MongoDB, and move the whole thing to Google Compute Engine or a colo.

Displaying Maps in Unity3D

There have been a few recent examples of real-world maps displayed in Unity3D apps. The first one I noticed was the playfield in the infamous Halo 4 iPhone app that came out late last year. For unknown reasons, I was really into this game for a few months. I hung around my local 7-11 scanning bags of Doritos so much that I thought I was going to get arrested for shoplifting. Eventually this obsession led to me wanting to duplicate the map display used in the game. Here’s how I did it.

Google Maps Plug-In

Naturally the first place I looked was the Asset Store. It turns out there is a free Google Maps plug-in available. The only catch is that it requires UniWeb to work. UniWeb lets you call REST APIs and generally have more control over HTTP requests than Unity’s own WWW class allows. It can be a necessity if you’re using REST API calls but it restricts your code stripping options. This will bump up your binary size.

This asset’s sample scene works flawlessly. It downloads a map from the Google Static Map API and textures it on a cube. The code is clean and well documented, featuring the ability to request paths and markers to be added to the static map. Most attributes can be tweaked through the inspector–such as map resolution, location, etc.

I made a lot of changes to this package. I really wish it was open source. Free code assets really should be in most cases. I will try to isolate my changes into another C# file and post a Gist.

The first change I made was to add support for themed Static Maps. If you look at this wizard, you can see that there are a lot of styling options. This appears to be the same technique used in the Halo 4 app because with the right set of options you can get something that looks really close. Supporting styling in Unity3D is just a simple act of appending the style parameters to the end of the URL used by the Google Maps plug-in.

Displaying Markers in 3D

The next thing I wanted to do is display the markers as 3D objects on top of the map instead of having them inside the texture itself. This requires 3 steps:

  1. Determine where the markers are in pixel coordinates in the static map texture.
  2. Calculate the UV coordinate of the pixel coordinate.
  3. Calculate the world coordinate of the texel the UV coordinate resides at.

Step 1 can be tricky. You have to project the latitude and longitude of the marker with the Mercator projection Google Maps uses to get the pixel coordinate. Luckily, this guy already did it in PHP to create image maps from static maps. I adapted this code to C# and it works perfectly. You can grab the Google Maps utility functions here. (All this great free code on the net is making me lazy–but I digress)

Step 2 is easy. This code snippet does the trick. The only catch is that you have to flip the V so that it matches with how Unity uses UV coordinates.

Step 3 is also tricky. However, someone with much better math skills than I wrote a JavaScript method to compute the world coordinate from a UV coordinate. It searches through each triangle in the mesh and sees if the UV coordinate is contained inside it. If so, it then calculates the resultant world coordinate. The key to using this is to put the static map on a plane (the default scene in the plug-in uses a cube) and use the C# version of this function I wrote here.

3D objects floating over marker locations on a Google Static Map.

3D objects floating over marker locations on a Google Static Map.

Here’s the end result–in this case it’s a display for the Donut Dazzler prototype. 3D donuts are floating over real-world donut shops and cupcakes over cupcake bakeries. I got the locations from the Foursquare API. This is quite easy to do using UniWeb.

Slippy Maps

The aforementioned technique works great if you just want a static map to display stuff around the user’s current location. What if you want to be able to scroll around and see more map tiles, just like Google Maps when you move around with your mouse? This is called a Slippy Map. Slippy Maps are much more elaborate–they require dynamically downloading map tiles and stitching them together as the user moves around the world.

Thankfully Jonathan Derrough wrote an amazing free Slippy Map implementation for Unity3D. It really is fantastic. It displays markers in 3D and pulls map tiles from multiple sources–including OpenStreetMap and Bing/VirtualEarth. It doesn’t use Google Maps because of possible TOS violations.

I couldn’t find a way to style map tiles like Google Static Maps can. So the end result was impressive but kind of ugly. It is possible with OpenStreetMap to run your own tile server and run a custom renderer to draw styled tiles. I suspect that’s how Rescue Rush styles their OpenStreetMap tiles–unless they are doing some image processing on the client.

Either Or

For my prototype I ended up using Google Static Maps because Slippy Maps were overkill. Also, pulling tiles down from the servers seemed much slower than grabbing a single static map. I suppose I could add some tile caching, but in the end static maps worked fine for my purposes.

Keep in mind that Google Maps has some pretty fierce API usage costs. If your app goes viral, you will likely be on the hook for a huge bill. Which is why it might be worth figuring out how to style free OpenStreetMap tiles.