Vector Product Format (VPF) & Vector Features
Introduction
This project started because I needed some good coastline data for the world, and this was an interesting way to get it. The goal of the project was to be able to load the linear features from the VPF file into internal vector feature classes which could then be used for rendering, tiling, and LOD generation.

Phase 1: Parsing
Some people report that the VPF format is a big ugly to parse, but I found that it came together fairly quickly. The key to parsing the format is building a base table class which can parse the column definitions and then the rows without making any assumptions about the file contents other than what the column definitions offer.


North America Coastlines (coastl), Political Boundaries (polbndl), and Depth Contours (depthl).
For this implementation, I use a generic value class to represent the data in the tables. This generic value class can contain single values or multiple values. Types can be int, short, float, and string. The support of multiple values is important because a number of fields in the VPF format can have multiple values (coordinates, tile triplets, etc.)

The next step was to add methods to the table for efficiently finding columns by name, and attributes in in the rows. In the VPF format, tables refer to other tables which can refer to other tables. Values in one table may be column names (keys) into another table. The ability to easily take a value out of a table and look it up as a column name in another table is key. How many columns a table has, and the ordering of the columns in the tables, can be a dynamic matter based upon whether the table contains optional items.

Enough about parsing, because I doubt anyone comes to a webpage like this to read about parsing!

Phase 2: Initial Vector Feature Classes
To test the initial parsing and to get the vector feature of the project under way, a couple vector feature classes were written:
  • Basic Vector Feature - Simple storage of line segments/strips and rendering.
  • Indexed Vector Feature - Indexed storage of the line segments/strips and rendering.
All vector feature classes inherit from a pure virtual vector feature interface class. The Vector Feature Interface requires methods for adding line strips, rendering them, optimizing, and bounding box access.

The Basic Vector Feature class is little more than a test class which supports storing the line strips using STL vectors and rendering them. Its goal was simply to provide support for a vector feature while testing the parsing logic. Using this basic logic, the north american coastlines contain about 501k vertices, and almost 13,000 line strips.

The Indexed Vector Feature Class implemented the vector feature interface while internally supporting a vertex table, and storing the line segments as a series of indices into the vertex table. It uses a STL multiset to store vertex search information to provide fast searching for existing vertices, when adding line strips to the feature. The indexed vertex table shows that the unique vertex count for the north american coastlines is actually 489k vertices not 501k. Not a large savings, but this is just a building block for later vector feature classes.

Phase 3: Optimizing Vector Feature Classes
The planned use for the vector feature library will support tiled representations, but not necessarily tiled at the location that the VPF files may be tiled. Therefore, when reading the VPF file, I remove the tiling. This produces line strips which may have been broken at tile boundaries. To reduce the impact of this, optimizing the vector features was added.

In the case of the Indexed Vector Feature, this optimization is searching for line segments which can be merged together into one segment. To do this efficiently, it iterates through the line strips adding the line strip index to a STL vector for the starting and end vertex of the line strip. Then it iterates through the vertices checking to see if the vertex has more than one line strip associated with it. If so, it can merge those line strips. (It may have to reorder one or both to get the line strips merged at the given vertex.) This processing (which is rather efficient) reduces the line strip count by 1000 line strips!

Phase 4: Level of Detail & Simplification
All of the work getting the vertices indexed and merging the line strips was done to enhance the ability to produce levels of details for the strips. By having indexed primitives, we can efficient store additional levels of detail of the vector features. By merging as many strips as possible, we can produce the best levels of details. (Otherwise we could have a large number of small features which don't simplify well.)

The simplification algorithm was leveraged from one I developed for some other polygon simplification work that I have done. In this case, it could be described as a Douglas-Peucker algorithm reversed. The initial implementation simplified based on the number of vertices, reducing features more that had more vertices. The following images illustrates how effective it was at a global level and a more local level.
Simplification of vector features to a desired number of vertices works because the simplification algorithm removes vertices in order from the smallest to largest amount of error introduced. The problem is that it isn't the best way to do it, because we may simplify an island more than it should be, but not simplify a coast as much as it should (because we are targeting vertex counts.) To fix this, Simplification based on a maximum error factor was added. The following images illustrate that this worked quite well:

The vertex totals are for the entire file, not just the section shown in the images.

Click here to see an animated version of the simplification.

Implementation: A new vector feature class was added, LOD Vector Feature, which inherits from the IndexedVectorFeature. It adds creating, drawing, and deletion of the LOD levels. It uses the maximum error factor as its mechanism for specifying the LOD levels. The Vector Feature Interface supports specifying a parametric value [0..1] when drawing for how detailed the resulting draw should be. This parameter is used by the LOD Vector Feature to compute a target number of vertices and to then look up in its list of LODs for the best level of detail to draw.

Phase 5: Tiling
Finally, the tiling was re-introduced by producing a Tiled Vector Feature class. This class uses a grid of LOD Vector Features to represent the tiled space. This allows each tile to individually support LODs, which, as described above, are represented as indices making them extremely memory efficient.

The following images illustrate the difference between the original 553k vertices, and an automatically generated low level of detail (62k vertices.) It is pretty much impossible to determine the difference at this zoom factor. This technology will be used to display the vector features at various levels of details based upon the zoom factor. When zoomed closer, only a few tiles will be in view, but they will rendered at higher levels of detail. This will keep the polygon budget per frame for vector features at a fairly consistent level.

Phase 6: I/O
The final steps were adding file reading and writing to the Vector Feature classes. This allows us to load from the VPF files, but to save into our own file format. Now the bulky VPF files (which contain quite a bit more information than what we typically are looking for) can be replaced with smaller files.

To close the page out, below is an image of all four VMap Level 0 files loaded together into 2 tiled vector features. One feature for coastlines and one feature for political boundaries.

glenn@raudins.com