Sinking Balls - Using Google Earth's Seafloor View

by Gong Liu July 21, 2011 14:01

Introduction

Recently Google, in collaboration with Columbia University and about a dozen research labs, has released a set of high res maps of seafloor terrain. See the following intro video about the new dataset:

This looks pretty amazing. Possible uses? You can probably use it as the background of some aquarium screensaver or some underwater game, for example. But before you start to develop your next Google Earth based hit game "Angry Penguins", you need to know how to sink an object properly. And this is what this post is about - sink an object in a physically correct way using Google Earth's new seafloor terrain. 

Formulation

When an object sinks in a medium, such as sea water, at certain velocity, there are three major forces involved, gravity, buoyant and drag. 

  

Fig. 1. Gravity, buoyant and drag forces exerted on a sinking object. 

The drag force is a function of the velocity of the sinking object and can be expressed as:

(1)

where,

      Fd - drag force
      Cd - drag coefficient
      ρ - the density of the medium
      A - the object's cross section area
      v - the velocity of the object 

The drag coefficient, Cd, is a function of a dimensionless number called Reynolds number, which in turn is a function of, among other factors, the object's velocity. However, within a relatively large range of Reynolds number, the drag coefficient remains approximately a constant (≈0.44). So in this post we'll stick with constant drag coefficient. In other words, the drag on the object is considered quadratic in the velocity.

Referring to Fig. 1, the equation of motion of the object reads:   

(2)

Here the second term to the right is the buoyant force. m* is the mass of the displaced medium. Substitute Equ. 1 into Equ. 2 and we have:

(3)

where,

(4)
(5)

      ρ - the density of the medium
      ρobj - the density of the object
      m - the mass of the object
      m* - the mass of the displaced medium 

The differential Equ. 3 has an analytical solution. For the initial condition

(6)

the solution (the velocity of the object at any moment t) is:

(7)

Since the hyperbolic tangent is bounded to (-1, 1), v(t) has a maximum value of -1/γ, which is called terminal velocity, i.e.

(8)

The negative sign indicates that the direction of velocity is toward the seafloor. The elevation of the object at any moment t can be obtained by integrating Equ. 7:

(9)

with the initial condition

(10)

When v0 = 0, Equs. 7 and 9 are reduced to

(11)

and

(12)

respectively. If you are interested in how all these are derived, please refer to the last section of this post.

Fig. 2 is a plot of Equ. 12 and Fig. 3, a plot of Equ. 11 for a basketball-sized object with various densities. 

 
Fig. 2. The object's elevation change over time


Fig. 3. The object's velocity change over time

The plots show that the heavier the object, the faster it sinks, and the higher its terminal velocity. For a good sized object like the one in the example, it only takes a few seconds for it to reach its terminal velocity. After that it maintains the terminal velocity until it lands on the seafloor. So if you want to simulate an object sinking into very deep water, you can pretty much ignore the cumbersome Equ. 7 and use Equ. 8 instead.   

Implementation

I wrote a small program in C# that utilizes the above formulas to calculate the dynamics of multiple sinking objects and spits out a KML file, which can be rendered in Google Earth with the new seafloor terrain. Fig. 4 shows a screenshot of the user interface of the program. 

    

Fig. 4. Sink KML Generator UI

The object to be sunk is actually a 3D model in COLLADA format. You can download a 3D model from numerous online 3D warehouses, or you can create your own one using 3D tools such as Google Sketchup. In the above example, a 3D ball or globe is used. Once a 3D model for the object is selected, you can specify how many copies of the object to be generated and where exactly they are located. The location data in the input field has this format:

      lat0,lon0,elev0 lat1,lon1,elev1 lat2,lon2,elev2 ... 

The elevation here means seafloor (below sea level) and is in meters, not feet. You can read out the coordinates from Google Earth by hovering your mouse pointer over a desired location.

Each object will be assigned a random density (within certain range) so that they will sink in different speeds. The program also adds a gentle random spin to each object to enhance the visual effects. 

The following is a snip of KML generated by the program:

<?xml version="1.0" encoding="UTF-8"?>
<kml xmlns="http://earth.google.com/kml/2.1">
<Document>
   <name>Sinking Balls</name>
   <description><![CDATA[by <a href="http://tofuculture.com">Gong Liu</a>]]></description>
   <Folder>
      <name>Ball 0</name>
      <Placemark>
         <TimeSpan>
            <begin>2011-05-19T00:00:00</begin>
            <end>2011-05-19T00:00:01</end>
         </TimeSpan>
         <Model>
            <altitudeMode>relativeToGround</altitudeMode>
            <Location>
               <longitude>-125.379875</longitude>
               <latitude>36.693736</latitude>
               <altitude>0</altitude>
            </Location>
            <Orientation>
               <heading>206</heading>
               <tilt>169</tilt>
               <roll>10</roll>
            </Orientation>
            <Scale><x>1</x><y>1</y><z>1</z></Scale>
            <Link><href>files/Earth.dae</href></Link>
         </Model>
      </Placemark>
      <Placemark>
         <TimeSpan>
            <begin>2011-05-19T00:00:01</begin>
            <end>2011-05-19T00:00:02</end>
         </TimeSpan>
         <Model>
            <altitudeMode>relativeToGround</altitudeMode>
            <Location>
               <longitude>-125.379875</longitude>
               <latitude>36.693736</latitude>
               <altitude>-3.767087</altitude>
            </Location>
            <Orientation>
               <heading>238.4</heading>
               <tilt>169</tilt>
               <roll>10</roll>
            </Orientation>
            <Scale><x>1</x><y>1</y><z>1</z></Scale>
            <Link><href>files/Earth.dae</href></Link>
         </Model>
      </Placemark>
      ...
   </Folder>
   <Folder>
      <name>Ball 1</name>
      <Placemark>...</Placemark>
      <Placemark>...</Placemark>
      ...
   </Folder>
   ...
</Document>
</kml>

Notice that each object (ball) has its own folder so that when loaded in Google Earth they can be shown or hidden individually. 

Demonstration

The following series of screenshots shows the sinking objects (balls) in Google Earth's seafloor view.

Fig. 5. The objects are at sea level at the beginning

Fig. 6. Showing the path of each object and notice the spin 

Fig. 7. Sinking objects with seafloor as the background 

Fig. 8. Another view closer to the seafloor

You can download the sample KML file at the Downloads section below and play it alive on your own computer with Google Earth. If you are not bothered to install Google Earth or download the KML file, you can watch the following video I made. Enjoy!

Notice that the balls are not moving very smoothly at current one-second interval. This can be fixed by using smaller time interval when generating the KML. Also, it helps to use a joystick to browse around the seafloor terrain. It's like driving a submarine.

Downloads

You can download the program executable and a sample kmz file generated by the program from the following links: 

SinkObj.zip (8.44 kb)
SinkBalls.kmz (135.04 kb)

If you are interested in the C# source code, please contact me.

More Math Stuff

Equ. 3 belongs to a special type of differential equations called Riccati Equations. To solve a Riccati Equation, we need to know a particular solution of it. In our case, we can easily spot a particular solution such as: 

(13)

Now we introduce a new variable z:

(14)

or

(15)

Do a substitution of v for z in Equ. 3 and we have

(16)

Equ. 16 is a linear differential equation. The general solution is given by

(17)

Substituting z back for v in Equ. 17 yields

(18)

The constant C can be determined as

(19)

with this initial condition

(20)

v0 does not always have to be 0. For the situation where we want to drop a dead body to the ocean from an aircraft carrier, for example, before the body hits the water, it has already gained certain speed. Now substitute Equ. 19 into Equ. 18 and with some algebraic manipulations we get

(21)

To prove Equ. 9, integrate Equ. 21

(22)

With the initial condition

(23)

the constant C1 can be determined as

(24)

Substitute Equ. 24 into Equ. 22 and with some algebraic manipulations we get

(25)

Corridor Polygon Generation

by Gong Liu February 13, 2011 14:13

Problem Statement

Being able to search POI (points of interest) along a route within certain lateral range is a desirable feature for location based services. It makes the search result more relevant. For example, we may prefer a gas station that is 10 miles down on our route to a gas station that is 5 miles deviated from our route. Also, in geofencing applications we want to limit a vehicle, say a truck transporting hazardous materials, to travel only in a corridor area encompassing a predefined route. In this post, I will show you how to generate a corridor polygon for a given route and a radius - the lateral distance on each side of the route. 

Formulation

Consider a route consisting of a series of line segments. Take any two adjacent segments such as AB and BC and form a rectangle around each segment such as D'DEE' and G'GHH' as shown in Fig. 1.

 

Fig. 1. Two Adjacent Line Segments

If line segments AB and BC are not exactly in the same line, the two rectangles will have an overlapping region BE'F'G' on one side of the route and a gap BEFG on the other side. If we can find the intersecting points F and F', we can form the polygon D'DFHH'F'D' that closes the gap and eliminates the overlapping region. To do so, we first find the the coordinates of the four corners of the rectangle D'DEE' in terms of coordinates of points A and B and the radius r, as shown in Fig. 2.

Fig. 2. Coordinates of D, D', E and E'

Similarly, we can find the four corners of the rectangle G'GHH' in terms of coordinates of B and C and r, as shown in Fig. 3.

Fig. 3. Coordinates of G', G, H, and H'

The order of the points is important when dealing with polygons. We always order our points clockwise. Note that point F is the intersecting point of lines DF and HF, which can be expressed as follows:  

Fig. 4. Equations for Lines DF and HF

This is based on the fact that line DF has same slope as that of line AB and line HF has same slope as that of line BC. Now substitute point F in both equations and solve them for its coordinates:  

Fig. 5. Coordinates of Point F

Similarly, we can obtain the coordinates of the intersecting point F':

Fig. 6. Coordinates of Point F'

There are some special cases to consider, including when the slope of one of the two segments is infinity, the slopes of both segments are infinity, and the slopes of both segments are equal but not infinity. All of these cases can be solved easily with above formulas in some reduced forms, so I will not cover them here in detail. 

For a route with complex shape and many line segments, finding the corridor polygon is not as easy as just tracking the corner points and intersecting points because the corridor polygon may tangle or intersect itself or may even form holes inside it. To deal with these possible situations we need to apply our formulas in conjunction with polygon union operation. The basic idea is that once we find the intersecting points F and F', we treat D'DFF' and F'FHH' as two separate polygons, which will be called segment polygons, and remove their intersecting line FF' to form a single polygon, which will be called union polygon, through polygon union operation. We can devise an algorithm that applies the idea repeatedly to all adjacent segments of a route. Here is a high-level description of the algorithm:

  1. Find the first and the second segment polygons, a and b;
  2. Assign a to a variable u, representing the current union polygon;
  3. Assign b to a variable p, representing the polygon to be unioned with u;
  4. Find the next pair of adjacent segments' segment polygons, a and b; (Note: if current pair are the 1st and 2nd segments, the next pair will be the 2nd and 3rd, and the next next pair will be the 3rd and 4th, and so on.)
  5. Replace p's two vertexes with a's two corresponding vertexes;
  6. Union p with u and assign the result to u;
  7. Repeat steps 3 to 6 until the second last segment;
  8. Union b, which is by now the last segment polygon, with u and assign the result to u.

At the end of the process u becomes our final result. If at any point during the process a segment polygon may tangle or form holes with u, the polygon union algorithm will take care of it.       

I should point out that the corridor polygon D'DFHH'F'D' is only an approximate encompassing polygon due to the fact that FB > r, meaning some points in the polygon actually have a distance from the route greater than the radius. This problem gets worse when lines AB and BC forms a sharp angle. We could insert an arc with radius r between E and G (Fig. 7), but that changes the nature of a polygon and thus polygon operation, such as union, would not be applicable. Or, we could find point K, where BK = r, and redefine our segment polygon to include this point, instead of point F, as one of the vertexes. This would be a better approximation.

 

Fig. 7. Close the Gap with Arc EKG

Implementation

I wrote a small program in C# to implement the proposed corridor polygon generation algorithm. Fig. 8 shows the user interface of the program:

 

Fig. 8. Corridor Polygon Generator UI 

Here are some highlights about the implementation.

  • The program takes a route KML file as input and produces a corridor polygon KML as output. The reason for this is that we can visualize the result in Google Earth or Google Maps. In a POI search application, we would probably want to write the corridor polygon to a database so that it can be used in a SQL query to get POIs in the corridor.
  • The program uses General Polygon Clipping (GPC) library by The University of Manchester for polygon union operation. You can get more information about the library here.  
  • For a long, complex route the number of points used to describe the shape of the route (called shape points) can be huge. Lots of points are used to describe small turns, ramps and other trivial road features. Depending on the application, this level of detail may not be needed. If this is the case we can reduce the number of shape points dramatically (while still keeping the basic shape of the route) through a polyline reduction algorithm. In this program the Douglas-Peucker polyline reduction algorithm is used. Polyline Reduction Tolerance controls how severe you want the reduction to be. The bigger the number, the more points are removed from the original data set. Please refer to my earlier post regarding the Douglas-Peucker polyline reduction algorithm here.  
  • The idea of a "dog bone" shaped polygon is based on the thinking that once you are at the origin or destination of your route, you may want to look at POIs in a wider area. The feature is implemented by first creating two squares centered at the origin and destination, and then unioning them with the corridor polygon.  
  • The program supports 3D KML output. This is particular useful for visualization of a geo-fence. 

Examples

The following screenshots of Google Earth show the results from the Corridor Polygon Generator program. You can also view them "live" in Google Earth or Google Maps by clicking corresponding links at the bottom of each screenshot. 

Fig. 9 shows a corridor polygon of a simple route. The route consists of only 7 points, as shown under the Route Points folder in the left pane as well as in the map. The corridor polygon is actually drawn as a KML path.

Fig. 9. Corridor Polygon of a Simple Route

Fig. 10 shows a corridor polygon with a hole. In this case the corridor polygon and the hole are drawn as two separate paths as shown in the left pane. If there are more holes, each will be drawn separately.  

Fig. 10. Corridor Polygon with a Hole

Fig. 11 shows a corridor polygon for a complex route. To exam how well our algorithm works with a route that has a lot of twists and turns, I select a route that contains a section of highway 330 that passes through San Bernardino National Forest. Notice that the big spike is caused by the sharp angle formed by points 46, 47 and 48. If we have more shape points to describe the route more closely, we can expect that the sharp points will get smoothed out. This is exactly the case demonstrated in Fig. 12.

Fig. 11. Corridor Polygon of a Complex Route

Fig. 12. Corridor Polygon of a Complex Route with More Shape Points (less reduction)

Fig. 13. Dog Bone Shaped Corridor Polygon

Fig. 14. 3D Corridor Polygon Useful for Visualization of a Geo-fence

Download

You can download the executable of the program and all the example route files below. The download also includes the GPC library (gpc.dll). You need to install the .exe and .dll to the same folder. The C# wrapper of the GPC library depends on Microsoft Visual C++ run-time libraries (msvcr71.dll). So make sure it exists on your computer. 

CorridorPolygon.zip (36.1 kb)

Visualization of a Bike Route

by Gong Liu October 15, 2009 05:44

[Just realize that you need Google Earth 5.x to play the video at the end of the article] 

Introduction 

I have a few favorite bike routes that I use for my weekend biking exercise. Depending on my mood and physical conditions, sometimes I choose a route with a strenuous climb followed by a thrilling 40-50 mph downhill. Sometimes I like to have a long, easy cruise along the beaches enjoying the sunshine and sea breeze. Well, other times I want to get a bit more technical about my bike routes than just the readings from my unsophisticated bike computer. Where exactly is the route located? Where is the hardest part of the route? How long and how steep is that slope? So I have assembled a couple of tools to help me to visualize my bike routes in Google Earth. Here is an example:

This visualization presentation has these main characteristics:

  • The route is highlighted (in red) on the map, showing the starting and ending points, as well as mile markers.
  • An elevation profile of the route is overlayed on top of the map.
  • The mile markers help to correlate between the profile and the route on the map, so I can easily find out the elevation and slope of any point on the mapped route.

How to do it? 

Here are the steps involved.  

First, get the route in KML format. There are two ways, manually or with the help of a GPS logger. If the route is short, you can trace it manually with Google Earth. Just click the Add Path button from the toolbar and start tracing, as shown below.

 

You want to trace your route at fairly evenly interval and with enough details. Once you are done with the tracing, the path will be added to the Places pane. Right click the path and select Save Place As from the context menu. Make sure you specify the KML format before hitting the Save button.

If your route is long, you may want to use a GPS logger to record the route and thus save your time doing the tracing manually. I use Pharos GPS Logger, as shown below. The software that comes with the logger allows me to save the recorded route in a KML file. 

Second, once you get your route in a KML file, use the profile tool from GPS Visualizer to generate the elevation profile for the route. The following screenshot shows the web interface of the tool.

 

The interface looks pretty complex, but the key things you need to do include:

  1. Specify the digital elevation model (DEM) you want to use. Note your GPS logger may record elevation data, but it is not accurate enough for our purpose. Also, if your route is outside USA, you have to choose the less accurate data source - NASA SRTM3.
  2. Specify the route KML file on your computer.
  3. Press the Draw the profile button and your profile will be generated as an image (.png). 
  4. Right click the image and save it to your computer.

Third, you need to add your elevation profile to your route KML so that when the KML is displayed in Google Earth the profile is overlayed at the top-left corner of the map. This is accomplished by using the <ScreenOverlay> emelent, something like:

    <ScreenOverlay>
      <name>Profile Overlay</name>
      <visibility>1</visibility>
      <color>c8ffffff</color>
      <Icon>
        <href>url_of_your_elevation_profile_image</href>
      </Icon>
      <overlayXY x="0" y="1" xunits="fraction" yunits="fraction" />
      <screenXY x="0" y="1" xunits="fraction" yunits="fraction" />
      <rotationXY x="0" y="0" xunits="fraction" yunits="fraction" />
      <size x="0.9" y="0" xunits="fraction" yunits="fraction" />
    </ScreenOverlay>

It is assumed that you have uploaded the profile image to your website and know its URL. Note that the color of the overlay is set semi-transparent so that the map underneath can show through partially. Also, the overlay width is set 90% of the map width, leaving enough room to the right for the Google Earth navigation controls.

Fourth, now you can display the route and the profile in Google Earth. So far so good. But without mile markers on the route, you can't really cross reference the two. Of course, you can use Google Earth Ruler tool to measure the distance along the route and then use Add Placemark tool to add mile markers manually. That sounds tedious though. So I wrote this little program called MileMarker in C#. It reads a KML file (containing a <LineString> element) and adds mile markers as placemarks to it. The following screenshot shows the interface of the MileMarker tool:

 

You can download the MileMarker tool executable from the following link:

MileMarker.zip (6.62 kb)

My favorite bike routes

Here is a list of my favorite bike routes. You can download the KMLs that have been enhanced with the above visualization process.

Route Level Length Comments Download
Hawthorne Hard 15.0 mi A series of light climbs and a long steep climb followed by a steep downhill.
Crenshaw Hard 9.8 mi Features a 5-mile continuous steep climb followed by a steep downhill. Narrow shared lane for the first 3 miles.
Lighthouse Intermeditate 16.1 mi Rolling hills. Exclusive bike lane for most parts.
Marina del Rey Easy 28.6 mi Along the beaches, exclusive bike lane.

Note: you need to have Google Earth on your computer in order to view a KML/KMZ file. You can download a free version of Google Earth here. In my opinion, Google Earth is one of the best free mapping programs. It's worth your effort to download and install it.

Touring a bike route and adding background music

Once you have loaded your route KML file into Google Earth, you can tour the route using Google Earth's touring feature. You just highlight the route path and hit the Play Tour button, as shown below (left). The tour player will show up at bottom-left corner of the map screen, as shown below (right). 

  

As you are playing a tour, you can also record it with the tour recorder, as shown above (right). You display the tour recorder by pressing  button in the Google Earth toolbar. When you finish/stop recording a tour, you can save it using the Save button on the tour player. The saved tour will show up in the Places pane. As everything in the Places pane, a tour is also in KML format but with elements in the Google Extension Namespace. The tour recorder also allows you to add sound cue, such as narrative or background music, to your tour from a microphone connected to your computer. Of course, if you have a prerecorded sound cue, you can insert it into your tour by editing the tour KML directly. Here I'll show you how to package your route KML, its recorded tour and a piece of prerecorded background music into one KMZ file so you can publish it on the web and share it with other people.

  • Prepare your route KML, elevation profile and everything as described previously. Let's name this file as doc.kml.
  • Tour the route and record the tour. You can adjust touring options at Tools -> Options -> Touring. Save the tour as tour.kml.
  • Raid your music collection and find a piece you like or record your own. You may need to edit it with a sound editor to match the tour length. Let's name it backmusic.mp3.
  • Create the following folder structure: 

    

  • Put doc.kml in BikeRoute folder, tour.kml in tour folder and backmusic.mp3 in sound folder.
  • Open tour.kml in a text editor and insert the background music as <gx:SoundCue> like so: 
<?xml version="1.0" encoding="UTF-8"?>
<kml xmlns="http://www.opengis.net/kml/2.2" xmlns:gx="http://www.google.com/kml/ext/2.2"
xmlns:kml="http://www.opengis.net/kml/2.2" xmlns:atom="http://www.w3.org/2005/Atom">
<gx:Tour>
   <name>Howthorne Route Tour</name>
   <description>Howthorne Route Tour with background music</description>
   <gx:Playlist>
      <gx:SoundCue>
         <href>sound/backmusic.mp3</href>
      </gx:SoundCue>
      <gx:FlyTo>
         ...
      </gx:FlyTo>
      ...
   </gx:Playlist>
</gx:Tour>
</kml>
  • Open doc.kml in a text editor and include the tour like so:
<?xml version="1.0" encoding="UTF-8"?>
<kml xmlns="http://www.opengis.net/kml/2.2" xmlns:gx="http://www.google.com/kml/ext/2.2"
xmlns:kml="http://www.opengis.net/kml/2.2" xmlns:atom="http://www.w3.org/2005/Atom">
  <Document>
    <name>Hawthorne Route</name>
    <NetworkLink>
       <name>Tour</name>
       <refreshVisibility>1</refreshVisibility>
       <flyToView>1</flyToView>
       <Link><href>tour/tour.kml</href></Link>
    </NetworkLink>
    ...
  </Document>
</kml>
  • Select everything inside the BikeRoute folder, right click, and select Send To -> Compressed (zipped) Folder. This will generate a doc.zip file.
  • Rename doc.zip to whatever name you like and change its extension to kmz. Now you can upload the KMZ file to your website and share it. 

Note:

  • You can also package the elevation profile image (.png) inside the KMZ file. In this case, you need to change the URL inside the <ScreenOverlay> tag of the doc.kml file to reference a local file.
  • You can reference a remote mp3 file as your background music in the tour.kml file, and thus reduce the KMZ file size significantly. However if you are experiencing choppy sound during playback of the KMZ file, your best bet is to package the mp3 file inside the KMZ.
  • If you host your KML/KMZ files in a web hosting environment, make sure you talk to the hosting company and let them enable the KML/KMZ MIME types on their web servers, because by default they are blocked. 

When someone downloads your bike tour KMZ file, he can play it in Google Earth by expanding the package, selecting the tour (the item with a camera icon), and pressing the Play Tour button, as shown below.

 

You can try out one of my bike tours here . Just sit tight, crank up your speakers and enjoy the ride!

About

A seasoned computer professional. A tofu culture evangelist...
more >>

Tag Cloud

Calendar

<<  April 2017  >>
MoTuWeThFrSaSu
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

View posts in large calendar
Copyright © 2008-2011 Gong Liu. All rights reserved. | credits | contact me
The content on this site represents my own personal opinions, and does not reflect those of my employer in any way.