Joshua Morey | 2014-05-15

Spatialization Development

When I started building the CloudView LAS viewer, I decided to take advantage of it by updating my CloudAE spatialization algorithm to optimize for fast 3D display without slowing down the processing pipeline. The SATR2 algorithm is now live, and I decided to write up some of the milestones in the development of the CloudAE spatialization. My first algorithm was mostly just a proof-of-concept, similar to something like Isenburg's lastile, but reorganizing the tiles into a single file rather than splitting into separate files. At the present time, my spatialization is extremely fast, and built around a robust indexing framework.

The next set of improvements will involve improved dynamic code generation for filtering and converting points. I am also considering additional changes relating to 3D visualization, such as additional sorting in the SATR2 algorithm or reworking the spatialization to handle general point clouds instead of just focusing on airborne LiDAR.

This list also leaves out the numerous unrelated improvements that may have been developed in parallel with these iterations, such as LAS 1.4 output support, composite readers, unbuffered I/O, and fast allocation. Figuring which development phase all the individual features belong to would require a tedious inspection of my source control history, and that's just not worth it.

SOOT

Compute a tile grid based on the assumption that the points are evenly distributed across the extent. Traverse the file to get the tile counts. Allocate a number of fixed-size buffers and traverse the file again to do the tiling. For each point that doesn't have an active tile buffer, acquire a free buffer and associate it with that tile. If the new point fills a buffer, flush the buffer to the correct location in the file. If there are no free buffers, flush one (last used or most full). When the traversal is complete, flush remaining buffers. As I said, this first attempt is similar to tiling to separate files, except that the separate file approach does not require the initial tile counts because it pushes the buffering problem off to the OS and filesystem, resulting in file fragmentation and varying performance.

  • Simple algorithm.
  • No temporary files.
  • Random write performance is dreadful (especially on magnetic media).
  • Sparse points will result in more points per tile than intended.

STAR

Traverse the file to get estimated tile counts. Use estimated counts to create new tile boundaries (taking into account empty space). Break point data into logical segments which can each fit in a large buffer. Tile each segment individually, but use the same tile boundaries for each (so each segment fills a subset of the counts). For each segment, read the points into memory, count and sort them, and write out the tiled segment. Merge the tiled segments together.

  • Faster than SOOT.
  • Resulting points per tile are more accurate on sparse points.
  • Requires simultaneous open read handles on all intermediate files.
  • Uses 1x the output size for temporary files.

STAR2

During the final merge operation, calculate how much data could be loaded from each intermediate file to fill the large buffer and read much larger chunks before flushing the large buffer to the output.

  • Much faster merge than STAR due to larger sequential operations.
  • Does not require intermediate read handles to stay open.
  • Temporary file usage is the same.
  • More complex interleaving logic.
  • Increased memory usage during merge, but since it reuses the large buffer, no overall increase.

SATR

Traverse the file to create high resolution index. Create tile boundaries from index, but skip populating them with actual counts. Create sparse logical segments from the index data such that they can efficiently read the tiles in the order that they will be written. For each segment, read the sparse file data into the large buffer in an optimized sequence, filtering out the extra points that do not belong in the associated tiles, and sort the remaining points into tile order. Append the buffer directly to the output file.

  • Faster than STAR2 due to halving the data written to disk.
  • No temporary files.
  • Depending on the point order and the buffer size, the sparse read multiplier might be 1.1-1.8x, and since it is sparse, it is similar to the previous 2x sequential read from STAR2.
  • The spatial indexes can be saved either for regenerating the spatialized file without the initial pass, or for direct use instead of spatializing (when disk space is a concern).

SATR2

During the segment sort operation, extract representative low-res grid points from each tile and append them to a common buffer. Medium-res points can be shifted to the beginning of each tile. After the segments have been written, append the common buffer with the low-res points to the end of the file so they can all be read at once. Retrieving tile points now requires pulling the subset of associated low-res points from the common buffer and adding them to the remaining points in the tile location. As part of the emphasis on rendering, grids now use square cells for all tile calculations.

  • Low-resolution points are available immediately in a sequential region.
  • Negligible performance difference for tile operations.
  • Reading the tiles is slightly more complicated internally, but it is hidden by the API.
  • Tile metadata is increased by the addition of a low-res count.
  • Points are "out-of-order", but since they are already in an artificial order, it hardly matters.
  • Slightly slower spatialization than SATR1 due to extra point shifting (it only becomes measurable when using low-res point criteria such as nearest to grid cell center).
  • More complex and time-consuming to debug.
Joshua Morey | 2014-05-08

WebGL LAS Viewer

I have been on an hiatus from development recently, due to injury, but I am now starting to do some coding for a couple of hours a day to build my hand strength back up. Since I have the time, I decided to learn about WebGL and get myself up to speed with modern JavaScript libraries. When I first developed my CloudAE platform, I used WPF 3D for rendering meshes, but I found it to be extremely limited in functionality and performance. I decided to make a WebGL viewer to replace it, starting with rendering simple LAS point clouds and tacking on functionality as I have time. As I brought myself up-to-date, I found that developers have made an enormous number of complex and powerful WebGL demos and applications. Although it was good to know that WebGL and HTML5 would probably be able to handle my needs, it was disconcerting to realize how out-of-date my knowledge was, due to my focus on desktop/server development.

My first basic implementation was in straight-up WebGL, but I found that due to my hand limitations, I just wasn't adequately productive, so I learned about available JavaScript 3D libraries and eventually decided on three.js. Three.js is a reasonably well-maintained library that doesn't have too many limitations for the current scope of my viewer. Eventually, I will have to break down and go back closer to WebGL, but not just yet. The main technical issues I have right now are the inability to do buffer interleaving properly and limitations on the number of scene nodes. It can also be difficult to develop against the unstable three.js API, since I might be able to find two or three different solutions to a problem, but none of them are valid in the current version, which requires me to delve into the source (the migration page is often inadequate).

I have uploaded the demo version of what I am giving the temporary (and uninteresting) name CloudView. Among other things, it is a learning ground for JavaScript frameworks, web workers, and the HTML5 File API.

Next time, I will outline the iterations of my CloudAE spatialization algorithms, including the current SATR2 implementation which is being improved for optimal use by CloudView.

Joshua Morey | 2014-03-27

Filter Chaining

Not long after my last post, I updated the Skhema graph generation to support filter chaining. Functions and variables are now implemented as a new type of evaluation token with a stack of filters, using a shared syntax. The following examples show basic function usage.

{%cycle[white,LightGray]}
{%format-url[post]}

The cycle function is one of the built-in functions that I described previously. The only change is that the syntax has been tweaked to use bracketed options. The format-url function is one of the user-defined functions used by Bramble to generate a URL from a data context. In this case the post option requires that context has both a 'time' and 'slug' variable which can be transformed into a URL such as /2014/01/skhema-filters. It's somewhat opaque this way, since just looking at the template does not necessarily provide enough information to know which variables the model needs to provide, but I think that encapsulating this functionality in user-defined functions is better in the long run.

{$content:subvert[code,root]}
{$time:format-date}
{%first[list/time]:format-date[atom]}

The filter syntax has not changed, but I updated the implementation so that filters can be stacked on variables, functions, and other filters. Bramble has enough functionality at this point to give me an assurance that the current approach should work well.

Joshua Morey | 2014-01-27

Skhema Filters

I finally decided on a syntax, so Skhema now has filter support. As a result, I have updated Bramble by moving the markdown parser references from models to views (where they always belonged). Skhema templates can now use filters on variables like {$var:filter[key1,key2=val]}, where brackets contain the optional filter parameters. This is shown in the following template that Bramble uses during the rendering of this post.

{@PageSection}
<div class="article">
<div class="title">
<h2><a href="{$url}">{$title}</a></h2>
</div>
<div class="post">
<div class="entry">
{$content:subvert[code,root,header=3]}
</div>
</div>
</div>
{/@}

The subvert filter handler needs to be registered with the TemplateManager, and any applicable filter options are the responsibility of the filter handler. From this example template, the Subvert renderer enables code formatting, sets a root URL for relative URL handling, and sets the current header level at h3 (because the page design already uses h1 and h2).

TemplateManager::RegisterFilter('subvert', function($var, $filter_options, $context) {
// handle options
// ...
return Subvert::Parse($var, $options);
});

I added user-defined function handlers, in addition to filters, because they use the same mechanism. I just don't have any use-cases for them at this time.

Joshua Morey | 2014-01-24

Skhema Functions

The initial support for functions in Skhema was more for test purposes than anything else. I haven't had any need for functions in my current framework, but I imagine that I probably will at some point. I made sure that they fit into the language design that I was finalizing, but I left the implementation as an inefficient late-evaluation.

I had initially thought that the best approach would be to compile functions during the graph-generation phase, but I have decided instead to compile functions during the evaluation phase and just do a proper lazy evaluation. Compiling during graph-generation would unnecessarily complicate the serialization process with proxy objects that don't improve the situation. A more serious issue is that the graph generator doesn't necessarily know if a particular function will be legal during evaluation. This is an unfortunate side effect of the way I change context scope for data-binding. I will continue to think about this issue.

Here is a contrived example showing the most basic functions: {%iteration} and {%cycle}. I say "contrived" because this can be done with CSS3 or any JavaScript library ever. Technically, the iteration index doesn't need to be a function, but I like the syntax for it. As a current implementation detail, {%iteration} can be written instead as {$__iteration}, but I wouldn't be surprised if that changed.

<table>
{?list}
<tr style="background-color:{%cycle=white,LightGray}">
<td>{%iteration}</td>
<td>{$url}</td>
</tr>
{/}
</table>

I am also still trying to figure out the syntax I want to use for filters, so that I can move logic like markdown rendering from the model to the view, which is more appropriate.

One of the next things I will work on is a proper page cache. Right now, full page renders cost 20-60 ms (depending on the page). That's a bit much even for this slow Dreamhost shared server with no bytecode caching. Almost all of the time is the database queries, so a simple cache should get me back below 20 ms for all pages.

Joshua Morey | 2014-01-24

Merging Personal Blog

I am dismantling my personal blog that I had at joshmorey.com. As expected, based on previous attempts, it didn't get much love from me, so for now I will go ahead and post my one personal entry per year here instead. Deal with it.

I'll start things off by recyling an old image from that blog, back when I did the Thursday Night Ride.

Joshua Morey | 2014-01-17

Skhema Templating Engine

In my last post, I wrote about my new templating engine. As I mentioned, the main unknown at the time was whether the language would adequately cover my use-cases. Since then, I have integrated it into the MVC framework of the Bramble Web Application Framework, and I am very satisfied with the results. As part of the integration, I changed the project name from templ@te to Skhema, since the old name was not web-friendly. This site is now running on Bramble using Skhema for rendering models.

The language has not changed much since last year. My concern was mostly with making sure that it was a good design, but I did find time for a few things. I improved the deserialization performance and provided alternate serialization modes. I improved the graph evaluation performance, and added preliminary function support. Functions are my primary extension-point at the moment, but they aren't particularly fast yet because the graph does an inefficient late-evaluation. All I have at this point are some basic operations like iteration index and cycle, but once I get back to this project I will properly generate the graph nodes for functions and add support for more powerful operations and user extensions.

<table>
{?list}
<tr class="{%cycle=odd,even}">
<td>{%iteration}</td>
<td><a href="{$url}">{$name}</a></td>
</tr>
{/}
</table>

For now, functions are scope-limited. I haven't decided on a syntax yet for accessing the functions of the outer list from the following example.

{?outer}
{?inner}
{%iteration}<br>
{/}
{/}

I didn't cover this in my last post, but one of the main differences that Bramble has from many other PHP templating engines is that mine does not compile to PHP statements, but rather to a graph that is evaluated using the data binding source. Originally, I had intended the graph/tree to be an intermediate structure that would get converted to PHP code for evaluation. Surprisingly, however, the graph evaluation proved to be faster than the alternative template engines that I was using for comparison, so I decided to simply serialize the graph instead.

Joshua Morey | 2013-09-27

Reinventing The Wheel

I haven't posted about development for months, but I have been getting some work done. My current project is a new templating engine that I am preliminarily calling templ@te. I finalized the first draft of the template language recently and just got around to implementing a parser/evaluator in PHP.

So, why on earth would I create another templating language? There are plenty of options out there like Twig, Smarty, Jinja2, Cheetah, Genshi, Django, Mako, Myghty, ctemplate, and many more. The short answer, as with most of my projects, is that I work on whatever grabs my interest. The long answer is that while I like many of the templating languages out there (my favorites being Twig, Smarty, Django, and Jinja2), I wanted something that combined the most useful capabilities of those languages in a more elegant and compact notation with a focus on the particular style of data binding that I want. I have met this goal so far, but it will take some time for me to be sure that the language can be extended to all the uses that I will have for it. Beyond that, I have no idea yet whether this language will be general-purpose enough to compete with the other options that are available.

The performance of my first revision is reasonable, considering that I wrote it in PHP. I designed it to provide a good mix of flexibility and performance, so it beats most other templating engines, but not by much. In lieu of a full feature list (since I am still adding functionality), I will just provide an example to demonstrate the syntax. Here is a basic template with variables, in-line template definitions, includes, and binding blocks.

{@TemplateBase}
<!DOCTYPE html>
<html>
<head>
<title>{$title}</title>
</head>
<body>
<div id="header">
{@Header}
<h1><a href="{$root-url}">jacere.net</a></h1>
{@Navigation}
<div id="nav">
<ul>
{?nav-list}
<li><a href="{$url}">{$text}</a></li>
{/?}
</ul>
</div>
{/@}
{/@}
</div>
<div id="content">
{$content}
</div>
<div id="sidebar">
{#Sidebar}
</div>
</body>
</html>
{/@}

Here is an example of inheriting this base template to show a list of posts.

{@Posts}
{^TemplateBase}
{.content}
{?list}
{#PostSection}
{/?}
{/.}
{/@}
{@PostSection}
<div class="article">
<div class="title">
<small>Posted by: <strong>{$author}</strong> | {$date}</small>
<h2><a href="{$url}">{$title}</a></h2>
</div>
<div class="post">
<div class="entry">
{$content}
</div>
<div class="postinfo">
Posted in
<ul class="taglist">
{?categories}
<li><a href="{$url}">{$name}</a></li>
{/?}
</ul>
</div>
</div>
</div>
{/@}

The block closing syntax that I am using is mostly for style reasons. The following closing formats are parsed identically.

{/}
{/@}
{/name}

Similarly, the parser accepts alternate delimiters, so the individual brace format can be replaced as desired (e.g. {$var} could be <$var> or {{$var}}).

As for using the template, right now I am simply binding to nested PHP arrays. I have not yet decided where I want to go from here.

$context = [
'Posts' => [
'title' => 'templ@te',
'list' => [
[
'author' => 'Joshua Morey',
'date' => '2013-03-14',
'url' => '/2013/03/satr-development-finalized/',
'title' => 'SATR Development Finalized',
'content' => '<p>I finally found some time...</p>',
'categories' => [
['url' => '/category/c/', 'name' => 'C#'],
['url' => '/category/cloudae/', 'name' => 'CloudAE'],
['url' => '/category/lidar/', 'name' => 'LiDAR'],
],
],
[
'author' => 'Joshua Morey',
'date' => '2011-12-23',
'url' => '/2011/12/tile-stitching/',
'title' => 'Tile Stitching',
'content' => '<p>I have completed...</p>',
'categories' => [
['url' => '/category/cloudae/', 'name' => 'CloudAE'],
],
],
]
],
'Header' => [
'root-url' => '/template/parse.php',
],
'Navigation' => [
'nav-list' => [
['url' => '/about', 'text' => 'Contact'],
['url' => '/contact', 'text' => 'About'],
],
],
];
$output = TemplateManager::Evaluate('Posts', $context);

There are many things I plan to add/improve, such as filters (e.g. escaping), compacted syntax combinations, more versatile named bindings, and improved caching performance. Eventually, I will also choose a name for the project, since "templ@te" isn't very web-friendly.

Joshua Morey | 2013-05-02

I wrote two lines of code yesterday

Thankfully, they were both correct.

Joshua Morey | 2013-03-14

SATR Development Finalized

I finally found some time to finish my SATR tiling algorithm for CloudAE. Unlike the previous STAR algorithms, which were built around segmented tiling, this approach uses more efficient spatial indexing to eliminate temporary files and to minimize both read and write operations. Another difference with this approach is that increasing the allowed memory usage for the tiling process will substantially improve the performance by lowering the duplicate read multiplier and taking advantage of more sequential reads. For instance, increasing the indexing segment size from 256 MB to 1 GB will generally reduce the tiling time by 50% on magnetic media, and 30% on an SSD.