Wednesday, December 3, 2008

Worksheet Four

This worksheet was aimed at giving an overview of what the project would entail. The key areas of what were to be addressed and the method in which the project would be carried out. It also gave some details on what I had already accomplished so far in the project.


Introduction
What is the topic and aim of the project?
The topic of the project is about creating deformable and destroyable objects using volumetric data or voxels as they are known. The aim is to find out if they are better or worse for the aforementioned purpose over using conventional polygon based models.

Issues
What issues do you want to address?
The main issue that I would like to address is the fact that current modelling techniques don't have any internal representations of structures or how the structure is actually put together. By using volumetric data this will allow for the modelling and simulation of structural properties and even the materials that the structures are made of. For example, using standard techniques, if a wrecking ball was to hit a brick wall the physics implementation would create several predetermined pieces that the wall would break into. Conversely if this was done using volumetric data each brick the ball hit could be analysed and then the corresponding mortar bonds between each brick to simulate exactly what would happen.
Research question
What is your current research question?
Using a voxel based approach to creating deformable and destructible objects what are the advantages over using traditional methods?
Addressing the Question
How do you envisage yourself carrying out the project - a short exposition of the project?
Firstly the data structures that are used to represent the volumetric data have to be researched. This will provide the basis for the project.
Secondly an algorithm for controlling the level of detail in representing the volumetric data. This is to stop voxels, if their size is less than one pixel, being rendered when it’s not necessary.
Next collision detection algorithms will need to be put into place to allow the voxel based objects to be destroyed. The idea is to have this done by a physics simulator such as PhysX or a similar program. This is where the voxel based objects will come into their own as they are simply a set of basic primitive objects.
Next the structural properties of the object will be included into the volumetric data. This will be done by either incorporating the structural data directly into the data that is being used to render the objects or as complimentary data set that holds the structures state. The second data set will allow calculation sot be carried out away from rendering on a separate thread and only update the main data set as required. Also for the deformable objects a similar approach will be used but by incorporating Hook’s law its will the shape of the object to be bent and twisted without ever breaking.
Then more complex objects will be implemented using the marching cubes algorithm. This should allow for the generation of voxel based objects from traditional mesh objects. At this stage some of the previous work may need to be revisited and “tweaked”.
Finally the aesthetics of the project will be considered. Using shaders to improve visual quality, effects such as anti-aliasing to reduce jagged edges, motion blur to disguise the rendered data set being updated and possibly depth of field to blur out objects that isn’t being focused on so as to render them at lower level of detail.
To sum up comparisons between using voxel based approach and traditional mesh based approaches will be made to give a justified answer to the question.


Progress
What have you managed to do so far and how has this influenced you vision?
So far I have worked on data structures to represent the volumetric data, and encompassed them into a class based structure. It allows for a search though the data structure and it identifies which parts of the data are to be rendered. At the moment the rendering is comprised of a series of cubes which is volumetric representations at the most basic level.
I have just finished off work on an algorithm to set the search level for the data structure. It calculates the level of detail that each level of the data structures is going to represent and if it’s less than one visible pixel in size it discontinues the search through that branch of the tree. This is to prevent unnecessary render time.
Next I plan to implement collision detection against the voxel based primitives. This is the first step towards answering the part of the research question on destroyable objects.

Worksheet Three

This worksheet came a couple of weeks after worksheet two. It was aimed at a slight draft/mock of the final proposal. At this point I was starting to really focus in on my research question and find very useful papers on the subject area.

Introduction

The aim of the project is to find out, through research, if voxels are a viable method of rendering using today’s hardware. Also what practical applications they can have in real time applications,

Motivation


The tremendous evolution of programmable graphics hardware has made high-quality real-time volume graphics a reality (Engel et al 2004). This quote from a paper published in 2004 is entirely correct in what it says yet there has been little in the way of volume rendering appearing in real-time applications such as games. In addition to the traditional application of rendering volume data in scientific visualization,
The interest in applying these techniques for real-time rendering of atmospheric phenomena and participating media such as fire, smoke, and
Clouds are growing rapidly (Engel et al 2004). Although the interest may have been there a few years ago there, again, has been little to show for this interest. The only exception is that there are certain volume rendering methods used within the Direct X 10 framework, but only in the above instances of what would have previously been particle systems. Volume rendering is used mainly for scientific and medical imaging as it gives a representation of the inside of an object, a requirement in medical imaging. The main reason for this is the speed of graphical hardware, medical images did not need to be updated at least 30 times a second required to give the fluid motion required for games. Also the size of the data sets needed for volumetric data were just too large for the standard memory of the home PC user until recently. With the now midrange graphics cards like the ATI 4870 series coming in with memory bandwidths of 107 G bytes/s( need a reference for this as I got it from the box my graphics card came in) and over 1 teraflop of processing power this should no longer be a problem. With 3D graphics becoming set to move away from traditional rasterisation and into a ray traced method there are big things on the horizon for the future of games. In an interview John Carmack says “I have my own personal hobby horse in this race ....... It involves ray tracing into a sparse voxel octree.” This is when the subject really justifies grabbing a lot of attention once again. John Carmack has always been one of the so called gurus of Graphics technologies and his opinions carry a lot of weight in the games community.


Research Question

Using a voxel based approach to creating deformable and destructible objects what are the advantages over using traditional methods?




Addressing the Question

To address the question investigations into the data structures and different methods of rendering volumetric data are required. This is going to be done using papers that were generated by the SIGGRAPH conventions for use in courses at their annual conventions. This will provide a basic foundation for building on what needs to be done in creating the deformable and destroyable objects. This will most likely involve using a physics simulator tool like PhysX. This simulation can then also be used on the traditional types of models to see what kinds of results are obtained. It is more than likely that the volumetric data version will need to be highly optimised as current dedicated graphics hardware is not built for this, but to circumvent this the SDK available from ATI that allows calculations on the graphics card will be used if needed.
The information obtained through this experimental work will allow a table to be drawn up comparing performance of the two methods. This will then allow for a reasonable conclusion to be drawn from the experimental work and hence a full answer to be given to the research question.

Resource Requirements

All that will be required for the project will be a computer with visual studio and a good graphics card, which are available. A few other tools such as ATI's stream SDK or possibly Nvidia's CUDA may also be needed but these are freely available from the appropriate websites for download. An application will need to be made to PhysX makers Ageia for this use of their tool but no problems with this can be foreseen as it is made freely available to students.


References and Bibliography

Engel, K. et al 2004 Real-Time Volume Graphics SIGGRAPH


Eisemann E , Decoret X 2008 , Single-Pass GPU Solid Voxelisation for Real-Time Applications GraphicsInterface

Shrout R 2008 PC Perspective – John Carmack on id Tech6, Ray Tracing , Consoles, Physics and more [Online] Available at: http://www.pcper.com/article.php?aid=532 [ accessed 4th November 2008]

Worksheet Two

This worksheet was given just a week after worksheet one. It was aimed at narrowing down the area of research and focusing in on the research question. At this point I truly started looking in to the areas of research that were already being undertaken in voxels and volumetric data.

1. Formulate a research question for your project. Details on the research question can be found in presentation 1 in the module folder.

Using a voxel based approach to creating deformable and destructible objects what are the advantages over using traditional methods?
This is what I have in mind for my research question so far. It will definitely lie along these lines but may well change slightly as I may not need to do a study in to comparing with traditional techniques and may change it to an investigation into what ways voxels can be used to create deformable and destructible objects.

2. When developing a research question you must produce a question that can be answered by performing literature research, practical experimentation and critical analysis. The question should also focus the activities of your project.

a) What is the focus of your project?

The focus of my honours project is most definitely around the use of voxels in creating deformable and destructible objects in real time 3d applications. It seems that this is one of the advantageous characteristics.

b) What information do you need to find out about?

Having already started investigating their properties the first thing that I had to research was quad trees, octrees and KD tress. These types of data structures are fundamental to representing voxel data in a fast and efficient manner. I will also have to look into how to add normal maps and other shaders based effects to the data set to allow for more realistic looking models.
I will also need to look into the other side of the question and figure out how destroyable objects are created in traditional mesh methods.

c) What Experimental work do you need to perform?

So far I have began experimental work with quadtrees. I have created the data structures to allow the complete destruction of a quad. The next logical step for me after this is to extend it into 3 dimensions using an octree and then to optimise it using a KD tree if necessary. I will also need to look into being able to stream data from main memory onto the graphics cards memory as the data sets for the voxels can be very large, possibly as high as 10243. Also the use of threading may be required to keep everything happening in real time while the large data sets are recalculated. To help with this I may look into using SDK's that allow for calculations to be carried out on the graphics card rather than on the CPU. Once I have done this I will need to look into the traditional mesh methods and compare characteristics like speed, memory usage and realism as some examples.

3. How will the information that you obtain in 2 allow you to answer the research question?

The information that I obtain through the experimental work will allow me to draw up tables of data to compare performance of the two different methods and therefore draw conclusions from it to answer the research question.

Worksheet One

This is going back to the beginning of October but I felt it would be a good idea to include this to give a view of the progress though the research. It was given as an exercise to to start focusing in on an area of interest for the project and to start generating ideas for a research question.

1. State the topic of interest that you may wish to take forward into a project.

The topic of interest I would like to carry forward into a project is the practical uses of voxels in real-time 3D computer graphics.

2. Indicate the areas surrounding this topic that you may wish to investigate.

The areas surrounding this topic that I would like to investigate are its applications in fully destructible 3D models. Is it possible to build a voxel based model from traditional 3D mesh data? The advantages/disadvantages over traditional polygonal based graphics. Its uses for terrain generation.

1. Outline your initial ideas about how you would carry out the practical aspects of the project i.e. what do you actually envisage yourself doing for the project?

For the project I would like to able to create a tool that would replace a 3D model in a game with one based on voxels. This would allow the object to be entirely destructible. I would also like to able to create scripts that would allow the user to define properties of the material, so that different materials like wood and stone would break accordingly. To optimise the process I would also like to able to only replace parts of the model that had been destroyed. This would allow for investigations into the advantages and disadvantages of using voxels. As an extension to this I would like to create a tech demo that would demonstrate this tool in a real time game situation. I would create a simple game along the lines or worms or pocket tanks where the scenery and objects would be under constant destruction.

It's Been A While

This is an informal post just about upcoming updates. Okay, so it’s been a while since I’ve updated this blog. Fortunately I have been keeping notes of my progress and investigations in a little black book so to speak. Over the next few days expect a flurry of updates on my progress over the past few weeks.

Wednesday, October 22, 2008

Stepping into the unknown

So far I have discussed general ideas about what I'm going to be doing. Over the past few weeks however I have been working on a small application that allows the destruction of a quad based on quadtree data structure traversal. This was a simple experiment into realising the concepts behind voxels, and to gain and understanding of how the data/object is being represented through this alternate means to surface modelling. This experiment however is in 2d but can easily be extended into 3D by adaptation of the quadtree data structure into an octree data structure.

To look past this experiment and onto future work I am now reading into various methods of rendering volumetric data, how to use shaders and if possible methods of carrying out calculations for the volumetric data on the GPU to speed things up. These I hope will provide a more realistic look for the volumetric data, rather than the very blocky look than it can provide.

Now onto the actual project worksheets. After having now completed two worksheets that help to outline my project idea I have came up with a suitable starting question.

Using voxel based rendering methods, what are the advantages for creating destroyable and deformable objects over traditional surface based rendering methods?

This question will undoubtedly change shape over the next few weeks but for now its focusing my studies into areas that I definitely want to explore. I do not think that I will end up doing a comparison study but instead look into modelling physical properties of objects. Consider a sponge like object modelled using volumetric data; this could have another 3d data set of ties between the voxels that represents the tension/elasticity between each voxel. With hooks law applied to this it would be simple to create a truly sponge like material. Again imagine a data set that represents structural bonds in a building. This could be used to represent the different bond strengths between bricks and mortar and the actual bricks strength. Underlying this could be another data set that holds the building's structural integrity. This would allow for a realistic destruction of a building so that key structural points could be destroyed and that building would collapse on its own.

So for now I'm going to continue reading up on methods for rendering volumetric data and further refine my research question.

Tuesday, October 7, 2008

Introduction

This is my first stab into the world of voxels so I'm basically giving myself a few weeks to get to grips with ideas behind and there applications.
I first took notice of voxels when i was reading an interview with the legend that is John Carmack. In the article he discussed the future of rendering methods and how everyone is looking to real time raytracing. He went on to suggest that this would be good with using voxels. Voxels? I had to find out more about this unknown subject. After some searching i found out that it is an old technique that was almost abandoned due to hardware limitations of the time. The full interview can be found here:
http://www.pcper.com/article.php?aid=532
The Advantages of voxels are that they can form completely destroyable objects. This is what i really want to look into and work on. Most Likely without using a ray tracing algorithm for rendering but simply using a ray cast to determine what parts of the voxel data structure should actually be rendered.
This is all for now while i go off to work on octree data structures that can be searched and used to form voxels based object. In the mean time enjoy this rather awesome tech demo from the lovely poeple at ATI and AMD of real time ray tracing with voxels on current technology.

And the actual Presentation here: