PhD Thesis - Geometric Processing Techniques for Urban Aerial Laser Scan Data

Keywords: LIDAR, Urban ALS, Building Extraction, Occlusion Images, Voxelization.

My PhD studies focused on the acquisition and processing of high resolution Aerial Laser Scanning (ALS) data sets. In particular, processing task such as building extraction and modeling for urban areas were studied.

Abstract

Current Aerial Laser Scanning (ALS) technology rapidly produces large amounts of accurate point data for urban regions, making it a suitable tool for city-scale geometric modeling of buildings. However, acquisition and processing of urban ALS data remains a challenge because of the geometric complexity of urban scenes. Existing techniques have focused on geometric modeling from elevation data, ignoring details on building walls. This thesis introduces several improvements and simplifications for the acquisition and processing of ALS data: urban flight path planning, scan line analysis, visualization, building extraction, and simple and robust conversion of ALS data into solid models for further processing. By applying geometric reasoning, it is shown that certain flight paths vastly improve the point data quality on building walls. Single scan line analysis then exploits latent information in the data to insert missing echoes caused by undetected pulse reflections, and to identify building wall segments in individual scan lines. Points on building wall segments are then transferred to a digital image and complete building footprints are then extracted using innovative morphological techniques. Finally, a simple and robust method for direct conversion of point data into solid models based on volumetric subdivision rather than surface reconstruction is presented.

Smoke GPU Renderer

Keywords: Smoke, Volume Rendering, Real-time, GPU, Shader.

Volumetric effects, such as smoke, are difficult to capture with standard rasterization techniques because light interacts with volumes rather than surfaces. This real-time renderer was written for Naiad Studio and uses a volume rendering approach based on camera-aligned proxy geometry and shaders. This method is well explained in GPU Gems. Lighting equations are integrated by rendering proxy geometry in multiple passes, storing accumulated light in a view buffer, while simultaneously accumulating visibility from a light source.

Smoke simulation and rendering for this animation were done using Naiad Studio.

Iso-surface GPU Renderer

Keywords: Iso-surface, Level Set, Volume Rendering, Real-time, GPU, Shader.

Iso-surfaces are ubiquitous in computer graphics, especially in applications where geometry undergoes significant topological changes over time. Level sets are a special type of iso-surface where the volumetric data is a Euclidean distance field. Fluid simulations often use level sets to track the fluid surfaces over time, using the distance zero-crossing to represent interfaces. This real-time renderer was written for Naiad Studio and uses a volume rendering approach based on camera-aligned proxy geometry and shaders. This method is well explained in GPU Gems. Volume data is stored as a 3D texture on the GPU and the fragments generated from the proxy geometry are used as sampling locations into this texture. This approach has several advantages over methods that extract explicit geometry from volumetric data (e.g. Marching Cubes) . The distance field is shown "as is", avoiding artefacts caused by super-imposed structures. Per-pixel shading is inherently provided and it becomes trivial to render any iso-value without additional setup.

Fluid simulation and rendering for this animation were done using Naiad Studio.

Single-pass Wireframe Rendering

Keywords: Wireframe, Hidden line, C++, OpenGL, GLSL, Shader.

Wireframe rendering is normally done in two passes; the first renders the filled triangles and the second renders the lines, using the depth buffer from the first pass to remove hidden lines. Not only does this involve passing the geometry twice to the graphics card, there are issues with depth testing for the lines due to slight differences in rasterization techniques between lines and triangles. These differences result in rendering artefacts and there is no good way to resolve this. In 2006 a new technique was proposed in a SIGGRAPH sketch entitled Single-pass Wireframe Rendering. The technique uses a pair of shaders to render triangles and lines in a single pass. Not only does this overcome rasterization issues, it is also faster and produces smooth results. The main idea is to compute the distances from fragments to triangle edges. If a fragment is within a threshold distance (half the line width) from a triangle edge, the fragment is rendered with the line color, otherwise it is rendered with the triangle color. A smoothing function is applied at the boundary between triangle and line to remedy aliasing artefacts. Most of the work is done in a vertex shader, where the distances to all triangle vertices are computed in viewport space. It is these (interpolated) distances that are the input to the fragment shader. A more robust implementation, using geometry shaders, has been proposed by NVIDIA. Their implementation deals with some tricky cases related to primitives having one or more vertices outside the viewing frustum and further reduces the amount of data sent to the graphics card.

Preetham Sky Model

Keywords: Preetham, Sky Model.

The Preetham sky model simulates sky color for a given time (year, day of year and time of day) and location (latitude, longitude). The main idea is to compute the color at zenith and use a clever distribution technique to approximate the rest of the hemisphere. This leads to a cheap, closed-form solution that is reasonably close to meteorological measurements and relatively easy to implement. However, this model is not perfect, and a rigorous criticism was made recently. In spite of this, the Preetham sky model provides nice backgrounds to CG scenes, especially when compared to many of the simpler alternatives, such as single colors or gradients. The main alternative is to go out and acquire panoramic photographs of real skies, a task that requires expensive hardware and is time-consuming. Also, photographs cannot be animated over time, providing only static snapshots of lighting conditions.

Finally, this implementation could be improved by adding physically based glare and some form of tone mapping.

Master Thesis - Animating Wind-Driven Snow Build-up Using an Implicit Approach

Keywords: Snow, Level Set, Wind Field, Navier-Stokes, Stable Fluids, Particle System, Ray Tracing.

My master thesis focused on modeling snow buildup using implicit surfaces (more specifically level sets) by allowing snow to fall in a wind field. Level sets are propagated according to snow particle collisions, with constraints to mimic realistic buildup.

Abstract

We present a physically-based snow modeling approach that handles geometrically complex scenes and arbitrary amounts of accumulated snow. Scene objects are represented with a novel dual level set structure. This implicit surface representation produces smooth snow surfaces that adhere to granular stability constraints at every timestep. Realistic accumulation patterns are achieved by tracing snow-carrying particles in a dynamic wind-field and on the surfaces of objects. Local level set operations are used to deposit snow at surface locations for which accumulation is physically plausible. The effectiveness of our method is demonstrated by applying our method to a number of challenging scenes.

Voxelization

Keywords: LIDAR, Voxelization, Octree, Point Cloud, Streaming.

Large point cloud visualization is challenging because of the huge sizes of modern data sets. Additionally, using points as rendering primitives has significant drawbacks, that are further amplified in situations where large numbers of points are involved. Put simply, mathematical points have no volume, and, therefore do not cast shadows. Further, points have no surface area and no natural normal vector, which is commonly used for shading. Although, both volume and surface area can be approximated, it is difficult to get it right. An alternative is to use cubes as rendering primitives. Cubes have clearly defined volumes and six distinct surfaces, which means they can be rendered with traditional techniques.

Cubes are created and stored in a hierarchical data structure known as an octree. Using a divide-and-conquer strategy, cubes are created to encapsulate the input point set. So, for each cube there is one or more data points inside its volume. The cubes are in fact the bounding boxes of the leaf nodes in the octree, which is recursively sub-divided to a user-defined depth. Data points are streamed, which means that there is no limit to the number of points being used in octree creation. Further, the memory footprint of the octree is orders of magnitude smaller than that of the raw points. The cubes are output to an OBJ-file, which can be rendered in real-time or offline. In the case of offline rendering (especially ray-tracing) it is possible to merge neighboring cube faces, to drastically reduce the amount of geometry to process (approx. an order of magnitude). This greatly speeds up rendering times without compromising visual quality. Images on the left were rendered with Maxwell.

Digital Dublin/VoxelVille

The top-left image above was shortlisted for the UCD Image of Research Competition 2008. The input point set for this image was part of a high-grade aerial laser scan of the city of Dublin.

Radiohead - House of Cards

Famous rockband Radiohead have generously released the data captured during the making of the video for their single House of Cards. The data consists of several thousand frames of real-time laser scan data of singer Thom Yorke's face. A few frames are showed on the left. Two levels of voxelization, rendered in different colors, are overlaid and rendered with depth-of-field and motion blur. Finally, the images were post-processed to remove some saturation from the green and blue channels.

Manipulators

Keywords: Manipulators, Maya, Interactive, User Interface, ArcBall.

Manipulators are a set of interactive tools for controlling transformations of objects. Letting users manipulate objects interactively on the screen is far more intuitive than trial and error tweaking of numbers in pursuit of suitable values. The most common transformations are translation, rotation, and scale. Manipulators are presented to users as widgets attached to objects and by interacting with these widgets the transformation parameters are changed. Many modeling packages, e.g. Maya, offer some form of interactive manipulation of objects. The manipulators shown here were implemented from scratch, using C++ and OpenGL, for Naiad Studio. Rotation was implemented using the famous ArcBall quaternion methods.

Level Set Ray Tracer

Keywords: Level Set, Ray Tracing, CSG, Ray Leaping, Snow.

This application ray traces level sets and uses the signed distance function to determine safe distances for rays to "leap" into the data grid. Snow is applied by letting particles fall downward in a 4D simplex noise field and applying a union operation where particles collide with the level set. The build-up of snow is rather slow for small particles, but smaller particles yield a finer grained build-up where individual unions are not visible after a while.

KlickKlacker 2 Solver

Keywords: Game Theory, Game Tree, Pruning, Transposition Table.

The general idea of this game is that areas that are connected by having the same color are removable, and the objective is to remove areas in a strategic way until no further moves are possible. Cells will fall down if there is empty space below them and will be pushed together if there are empty columns. The game ends if there are no possible moves or if all the cells are gone.

My idea was to write a solver that builds a game tree where each leaf contains the final score from making a particular sequence of moves. As one quickly realizes there is a huge number of possible solutions. In order to speed things up, pruning of the game tree can be deployed. However, it is very likely (although unproven for this particular problem, but proven for similar but simpler problems) that the problem of optimally solving this game is NP-complete. This means that pruning won't really help, because all leaves have to be visited in order to guarantee an optimal solution. However, a few obviously strategically flawed paths can be skipped. As with most pruning, evaluation functions must trade greediness and speed for optimal solutions.

A more failsafe optimization would be to implement a transposition table, because it is likely that by following different sequences of moves (in some cases simply changing the order of the moves) we arrive at the same game position, albeit with a different score. However, this involves checking for existens of a game position before solving at each node. This requires a fast hash-function for computing unique ID's for game positions, which is non-trivial to design. In these cases we can terminate the paths where the same position was achieved with a lower score.

Currently, I can solve small grids (5x5) using a brute force approach. I also have a playable version of the game, for verifying the suggested moves (and for fun). The solver and the game are built on the same core-library developed by me.

Moon Lander

Keywords: Physical Modeling, Inertial System, C++, OpenGL.

User input controls the moon lander's five thrusters, visualized by simple particle systems. An inertial system determines rotation and translation of the lander. The moon lander was modeled in 3DS MAX. The main remaining problem here is how to divide thrustor forces between rotation and translation, or to be precise, how to determine the ratio between translation and rotation given a force at a certain point having with a known centre of mass. This factor has been estimated to "feel" good. The simulation was turned into a game, where the user tries to land at a given location within fuel constraints, which is more difficult than it might seem.

Procedural Smoke

Keywords: OpenGL Shading Language, GLSL, Shaders, C++, Procedural Modeling, Perlin Noise, Pixel Shader, Fragment Shader, Vertex Shader.

Smoke is an extremely complicated phenomenon to simulate. Flow equations (Navier-Stokes) must be solved in order to accurately animate smoke. Here, I simply use a kind of 4D vertex noise to displace particles in a vertex shader. This approach is simple, and produces visually pleasing snapshots of smoke. However, the motion of the smoke suffers from the lack of physical simulation. The noise I use has very small look-up tables since these have to be stored in vertex processor registers, as texture memory access was not available from within vertex shaders on my graphics hardware. Particles are rendered using GL_POINT_SPRITE_ARB, which are simply textured billboards that are automatically calculated on hardware.

Game of Life

Keywords: Game of Life, Cellular Automata, Conway.

The game of life is a simple simulation and my first attempt at programming with OpenGL. The game was devised by a mathematician named Conway. The basic idea is that cells change color according to certain rules. The input to the rule decisions are the states of neighboring cells (Cellular Automata). The basic set of rules are very simple, yet generate amazingly complex patterns.

Obamafication

Keywords: Posterize, Illustrator, Vector Graphics.

First, please note that this project does not express any political views whatsoever. Posterization is an art-form with the power to transform images into aesthetic renderings geared towards a particular message, often using few colors for printing purposes. I have taken the impressive style used in the 2008 Obama-campaign and applied it to a picture of myself. The procedure is well described in this tutorial. A lot of manual work is required and it is non-trivial to achieve the professional look produced for the presidential campaign. Also, some of the procedures described in the abovementioned tutorial are needlessly complicated. For instance, I have found that using a combination of blurring and median-filtering on the different threshold levels, followed by manual tweaking, is an intuitive way of shaping the final product. Also, this allows much more efficient use of the live-tracing capabilities of Adobe Illustrator, which eliminates the most time-consuming part of the process, namely the path-tracing. Adobe Photoshop and Illustrator were used to create the different image levels and the following path tracing. The obamafied version of my picture is also available in vector-format [pdf].

Ray Tracer

Keywords: Ray Tracing, Java.

This is a simple ray tracer that only handles spheres and planes. This project was done during a summer break when I was fairly new to computer graphics. The results show the basic concepts of recursive ray tracing. However, there is a lot of room for improvement. When I ray trace images nowadays I typically use pbrt, mentalray or Maxwell.

Relief Texturing

Keywords: Relief Texturing, Parallax Mapping, Fragment Shader, Pixel Shader, LOD.

Regular texturing has many drawbacks. One of them is the fact that a texture is typically applied to a flat surface. Relief texturing uses a color texture along with a depth map and an algorithm for view-dependent depth occlusion. A level-of-detail engine could benefit hugely from this technique by rendering far-away surfaces with regular textures and closer surfaces with relief texturing. The main part of the calculations are done in a fragment shader.

Connex

Keywords: Lisp, Artificial Intelligence, AI, Game Theory.

I don't know if this game has a commonly used name. It was invented (or reinvented) by me and a friend under the name Connex. The rules of the game are simple. Players take turns at drawing a line between two dots on a regular grid. If a line makes an area water-tight, the area belongs to the player that drew the line. The game ends when all areas have been claimed, and the winner is the player with the largest combined area. Our AI is reasonably hard to beat, but can be tricked in some situations by an experienced player. The AI was implemented in Lisp and uses a simple graphics library for the user interface.

PLY Reader

Keywords: PLY, Partial Adjacency List, Toon Shading, Cel Shading.

Together with a friend I developed this application for an assignment at school. The application reads PLY-files and is capable of displaying normals, rendering {polygons | wireframe | points}, smooth or flat shading, and cel shading with edge detection (including interior edges). For efficient geometric queries a partial adjacency list was used.

RenderMan Shader

Keywords: RenderMan, Shader, Noise.

This shader was written for RenderMan. The initial geometry is a simple sphere. The sphere is displaced along the up-axis and further displacement is done to the surface to achieve the crinkles. Crinkles are produced by a noise function with appropriate frequency and amplitude. Green is mixed with brown on the surface for a more organic appearance.

MojoWorld Landscape

Keywords: MojoWorld, fBm, Fractal Noise.

MojoWorld is an application that makes heavy use of fractals for landscape modeling. It is rather simple to create a decent-looking landscape, but mastering the parameters of this application could take a life-time! This is an image I made for a school assignment. Note the blue line across the mountains and the psychedelic clouds.

Room Acoustics

Keywords: Room Acoustics, Transmission Line Matrix (TLM).

A pressure source in a room will cause pressure changes to propagate. Our method of solution uses the Transmission Line Matrix (TLM) approach. Pressure is scattered in four directions at each node (i.e. each pixel in the visualization) and is partially absorbed by walls.

Hough/Radon Transform

Keywords: Hough, Radon, Transform, Parameter Space.

The Hough transform is a feature extraction technique used to detect objects or shapes in images. Features are represented in a suitable parameter space. The transform then casts votes into this space based on processing of the pixels in the input image. Local maxima in parameter space then correspond to the parameterised features.

The Hough transform operates on binary images, and as such often requires a thresholding of the original image. For greyscale images an alternative is to use the Radon transform. The Radon transform is roughly equivalent to a continuous formulation of the Hough transform.

The images to the right show the respective parameter spaces of a Hough and Radon transform applied to an image (not shown here). At first glance we seem to get better contrast in the Hough image. This is often desirable because it makes the task of finding robust local maxima easier. However, the price we pay for this is the constraint of having to input a binary image. Although it is more difficult to find robust local maxima in the Radon image, this method may sometimes be preferrable. One such case would be when the task of finding robust local maxima is easier than finding a suitable threshold for the original image.

Unreal Tournament Modification - SplinterMod

Keywords: Ray Tracing, Java.

The Unreal Engine offers user-friendly editing tools for map-making and game rule modification. This mod was made by me and four friends as a school project. The idea of our mod is to sneak through a number of levels before time runs out. The player has no weapons and has to avoid armed guards throughout the levels, which were custom made for the purpose of sneaking.

Tetrinks

Keywords: Game Engine, Physics, Collision Detection, C++, OpenGL.

This was my pet project while learning C++/OpenGL. The future plan for Tetrinks is to add some demo effects, making it a simple game with a lot of visual content. The game uses gravity instead of constant velocity, normally used in Tetris. Since the game engine is up and running, this is a future outlet for eye-candy shaders and such.