User:Evanlezar/GSoC2008-Application

From K-3D

Jump to: navigation, search

Google Summer of Code 2008 - GPU-Based Processing Proposal

Overview

Advances in GPU technology over the past couple of years has seen not only an advancement in their ability to render complex 3D scenes, but also their ability to perform general purpose calculations [1] with significant performance gains being obtained in certain applications. GPU manufacturers have released API's to specifically leverage this additional computational power [2, 3]. In addition, a number of both open source and commercial third-party solutions exist [4, 5, 6].

The purpose of this project is to investigate the use of GPU's to accelerate the execution of a number of the filters available in K-3D. These filters include simple image manipulation and linear transforms of meshes describing the 3D objects. Owing to their nature, these filters are an ideal starting point for GPU implementation. More advanced filters can then be considered.

The hope is not only that the GPU implementation of some of the existing filters will result in an increase in performance, but that a better understanding of the types of filters that can be successfully converted will also be obtained.

Details

The focus of this project is not to create new plugins, but to provide alternate implementations for existing ones - with these alternate implementations hopefully being more efficient than existing ones. It is important to note that these improved implementations do not necessarily need to replace the existing ones since their implementation may be somewhat hardware dependant and thus the existing plugins would still be required. The existence of the original plugins allow us to test whether or not the new implementations are correct in that each of the implementations should yield the same output regardless of the input received.

The deliverables for this project are thus these improved plugins as well as information regarding the improvement (if any) they offer. To ensure that the development and delivery is spread over the duration of Summer of Code and, importantly, starts as soon as possible after the project has commenced, it is important to start with the simpler plugins. The following modules with their plugins have been identified

module : bitmap

The majority of the plugins in this module use the boost::gil::transform_pixels() method to apply a specific functor to each of the pixels in the input bitmap. The simplest of these are add, multiply and subtract which add (multiply or subtract) a specified value (which is constant over the image) to (by or from) each one of the color channels of each pixel. These three plugins will constitute the first deliverable.

Other plugins in this module which apply slightly more complex functors to the pixels are (alphabetical order):

color_monochrome

gamma

invert

matte_colordiff

matte_invert

treshold

These plugins will be delivered on completion of their implementation and testing.

module : deformation

Many of the plugins in this module take the form of a linear transform which can be written as a matrix product. These simple cases all use a linear_transformation_worker to actually perform the operation required by the filter and only differ in the transformation matrix used. The most general case is the plugin transform_points where the transformation matrix is user-specified. The other plugins of this kind are (in alphabetical order):

center_points

rotate_points

scale_points

shear_points

translate_points

Once the general transformation has been implemented and tested, these plugins will be implemented without much additional effort since it is only the transformation matrix that needs to be constructed in each case.

The remaining deformation plugins are slightly more complex in their implementations and are thus, one could argue, more interesting with respect to their GPU implementation. These more complex plugins will only be implemented after the simple ones that have already been mentioned - a walk before you run approach. The remaining deformation plugins are (in alphabetical order):

bend_points

bulge_points

cylindrical_wave_points

linear_point_noise

linear_wave_points

smooth_points

sphereize_points

taper_points

tweak_points

twist_points

other modules

Plugins from other modules may also benefit from a GPU-based implementation. These include the plugins in the mesh module. One other module that I would like to implement on a GPU (time permitting) is qslim which deals with quadric error metric based mesh decimation [7]. The implementation of the quadric_decimation plugin is definitely non-trivial and will serve as a good general-purpose plugin to be delivered. Although this list is already quite long, the similar nature of many of the plugins mean that their implementation will be rapid once one of the plugins has been successfully implemented. Therefore, further plugins or groups of plugins will be considered once the initial list has been exhausted.

Deliverables

The following plugins will be adapted for GPU implementation

bitmap/add (already implemented)

bitmap/multiply

bitmap/subtract

bitmap/color_monochrome

bitmap/gamma

bitmap/invert

bitmap/matte_colordiff

bitmap/matte_invert

bitmap/treshold

deformation/transform_points

deformation/center_points

deformation/rotate_points

deformation/scale_points

deformation/shear_points

deformation/translate_points

deformation/bend_points

deformation/bulge_points

deformation/cylindrical_wave_points

deformation/linear_point_noise

deformation/linear_wave_points

deformation/smooth_points

deformation/sphereize_points

deformation/taper_points

deformation/tweak_points

deformation/twist_points

qslim/quadric_decimation

Additional plugins

Additional Comments

The biggest bottleneck in GPU-Based processing is often the fact that data needs to be transfered between the main memory of the host and the GPU memory on the device. To minimize the effect of this, it is possible to start processing before all the data has been transfered and continuing the transfer in the background. When considering the visualization pipeline, it may be possible to chain a number of GPU-Based filters together keeping the data in GPU memory, thereby eliminating most of the transfers required. This will be investigated further once more plugins have been implemented.

References

[1] GPGPU (http://www.gpgpu.org)

[2] Nvidia CUDA (http://www.nvidia.com/object/cuda_home.html)

[3] ATI CTM (http://ati.amd.com/companyinfo/researcher/documents/ATI_CTM_Guide.pdf)

[4] BrookGPU (http://graphics.stanford.edu/projects/brookgpu/)

[5] Sh (http://libsh.org/)

[6] Rapidmind (http://www.rapidmind.com/)

[7] M Garland PhD Thesis (http://www-cgi.cs.cmu.edu/afs/cs.cmu.edu/user/garland/www/thesis/thesis-onscreen.pdf)

Biography

I am a first year PhD student at Stellenbosch University, South Africa, where I plan to investigate the use of high performance methods (including GPU computation) in the field of computational electromagnetics. For my masters thesis I investigated adaptivity in the finite element method. I also have my electronic engineering degree and a bachelor of science in physics and computer science. I have been programming since 1997 and the languages I have experience in include C, C++, Java, Pascal, Oberon, Delphi, Python, and Intel Assembler.

Summer Agenda

The only fixed obligations that I have is that I have to do some development work for two non-consecutive weeks during the coding period. However, this development work involves implementing existing isosurface extraction and surface simplification algorithms for GPU-Based execution and thus overlaps well with my proposed summer of code project. Additionally I must continue to so some work for my own research, but at the momement this mostly entails reading and background study, the latter being contributed to greatly by my summer of code project.

I do not in any way feel that any of these obligations will adversley affect my ability to give the required attention to the proposed project.

Personal tools