Research Interests: Patrick Marais

Computer Graphics

Work in this area centres on applied computer graphics: 

Real-time GPU Sand for Games

Sand is poorly modelled in current 3D games:  it does not deform under contact, form sand piles etc. Even worse, it is usually rendered as a simple texture draped over static scene geometry.  This low fidelity approximation is in stark contrast to the modelling and rendering of other environmental scene components such as vegetation, water and clouds.  This divide has arisen because the accurate modelling of granular physics is computationally demanding and would require too many system resources when combined with regular rendering tasks.
Work has recently been completed on a physically accurate GPU sand simulation framework. This framework uses the massive parallelisation afforded by modern GPUs to simulate realistic sand physics, albeit in a small volume.  Unfortunately, to use sand effectively in a game, there needs to be an appropriate level of detail system.  In this case, we wish to use a crude (low fidelity) approximation at a distance and only switch to accurate granular physics when the camera viewpoint is close to the deforming sand.  The LOD system could uses textures and geometry to approximate distant sand deformation, for example. The issues involved in the design and GPU implementation of such a system are not trivial, but successfully tackling this problem would provide an important step towards increases realism in games.

Point-cloud algorithms for Heritage applications

UCT is involved in an ongoing project to capture 3D models of heritage sites across Africa. The data is captured by means of lase range scanners and stored as massive collections of point data. This data needs to be 'meshed' and textured to produce the 3D models that users expect - a decidedly non-trivial task. This project aims to produce new algorithms to help manage the computational complexity of this task. In particular, my interest here centres on new approaches to repairing scanner artifacts directly in the point cloud, as well as finding ways to improving the speed and robustness of scan registration. Scan registration refers to the process of amalgamating separate scans (taken from different viewpoints) into one large scan.

Compression of unstructured point-based surfaces

Surface geometry can be represented as a collection of individual points, a point-sampled surface, or as a collection of point-based surface elements, such as a triangle mesh. Triangle mesh compression techniques provide extremely high compression ratios by exploiting the topological information in the mesh and using this in tandem with the available geometric information.  Unfortunately, techniques to compress point data yield very poor compression ratios, unless the point surface has been sampled with some kind of regularity, such as those produced by laser range scanners.

The intention of this project is to investigate the efficient compression of point-sampled surfaces, without the requirement for regular point sampling. Effective compression relies on exploiting prior knowledge about the compression target. If one assumes that the underlying surface that generated the point data is smooth, this provides a very basic compression constraint. Additionally, in the case of point compression we do not have to reconstruct point connections or ‘topology’: we simply want to recover each point to reasonable accuracy. By combing evolving information about likely point locations it should be possible to improve on existing spatial subdivisions schemes as well as those that assume ‘dense’ point sampling.

Visualisation of scientic data

Many scientific disciplines generate high dimensional data sets which are hard to interpret. The purpose of this theme is to provide tools to assist scientists in analysing their data. This encompasses both visualisation techniques, aimed at drawing attention to feaures of interest, as well as low-level graphics/rendering optimizations intended to speed up the investigation of large data sets with many graphical primtives. We are particularly interested in visualisation techniques  suited to astronomy data, since this ties in to current projects in that area.

High Performance Computing

Work in this theme concentrates on the effective use of multi-core CPU's of multi-GPU systems:

GPU base computing for astronomical algorithms

Interpreting and processing astronomical data requries significant computational resources. We are working with the Department of Astronomy to map current algorithms for radio interferometry onto the GPU. Current work includes 'source detection' algorithms - which examine a large data cube to isolate and categorise galactic cources - and GPU accelertaion of radio interferometry processing (direct fourier methods). Possible future projects involve parallelising galaxy evolution simulations and the segmentation (extraction) of galactic structures from large galaxy point cloud data sets.

Parallelisation of simulations for GPU and multi-GPU systems

Many numerical algorithms are embarrassingly parallel - or would appear so initially. GPU's offer huge potential speedups for certain types of algorithms, since they have hundreds of (small) cores. However, the peculiarities of GPU architecture mean that this mapping is seldom simple.  Our particular interest is on the efficient mapping and scaling of physical simulation algorithms (such as particle interactions) onto GPU's. Communication overheads and synchronization amongst GPU cores need to be carefully examined in these cases. This project will evolve as our simulation needs change.

Image Processing and Computer Vision

Current work is centred in medical imaging (brain segmentation algorithms), but other areas may be explored in future. While no new projects have been lined up in this area, this is due more to a lack of interested students then research ideas. Interested students should speak to me about possible projects.