A note on progress

Progress is slightly behind at this point!

This was due to unforseen circumstances though( applications to Dare to be digital take longer than you think).
The project plan has changed vastly from the original submitted with the proposal.

1. Isosurface construction now just involves searching through the volume data set and removing inside faces. This then generates a list of vertices for the vertex buffer.
2. Voxelisation ( yes i know i said about voxels but its the best suited term) is now going to be done through the KD tree.

With these two changes in mind the isosurface and voxelisations of the object is now going to be done through the data structures so they go hand in hand and the plan was adjusted accordingly.

I have attached an image of an updated gantt chart. Though as i type this i am now one day behind but that should be sorted with some good old fashioned elbow grease over the next few days.

Out with the Octree in with KD tree

The original plan of using octree data structures for getting basic primitives to work on for the physics implementation was flawed. The size of the initial object would have to be a cube and the object smallest destroyable part would have to be in equal powers of 2 in each dimension.
This is best thought of in terms of a wall that's dimensions are 10*5*1. If the smallest component part, a brick, is 2*1*1 one subdivision of the of the initial root volume would immediately exceed the smallest part on the z-axis. This was therefore no use for modelling destroyable objects that have set smallest parts.
I had to research and find a new solution to this problem. I continued with the idea of using a tree based data structure and look into using a BSP tree. This was more suited as you could choose the split point on the object. However a BSP is limited to two dimensions. This leads onto the KD tree. The KD tree is a special Circumstance of the BSP. It allows for multiple dimensions in the data structure and the split can be down any of those dimensions. This the allows for smallest destroyable parts of any size to be made for the objects without any issues.
The original octree will still be useful in some respects for the project although i cant see any real need to use it now as the KD tree is far more efficient for what im trying to do.

Bye Bye Voxels

This post is more of a rant than anything else. After being consistently asked "How are the voxels coming on?" and having to reply there not voxels im just using volume data for modelling fully destroyable objects.
You might ask you self whats the difference? Well from what I've read voxels appear to be the actual rendered objects and they are not rasterised in the same way that traditional meshes are. The volume data I am using in theory could be rendered this way but im not going down that path. I'm simply using a complementary volume data set for modelling collisions.
So i hope this clears a few things up.

Again its been while since i posted

So since the submission of the proposal in December I have been working almost exclusively on data structures for the project. These are mostly changes to the data structures I will be using and the complexity of the project. Each of these i will present in the next few posts.

Full Proposal

This is going to be a long post. It will include my full proposal.

INTRODUCTION

This may come as a shock to some, but the world is not made up of corridors composed of completely planar surfaces. We live in a wildly organic place. Hills roll, muscles bulge and fountains splash. The world around you is filled with organic shapes which cannot easily be created out of triangles (Lander J, 2000). The use of voxels (a portmanteau of the words volumetric and pixel) is one approach that may afford a more organic way to render. Unfortunately for years the computational power available to the average home user has been nowhere near capable of handling the massive amounts of data and processing power involved in carrying out volume rendering in real-time. Until recently graphics hardware suffered from having a fixed function render pipeline preventing any form of rendering other than that of traditional triangle based forms. Any direct forms of volume rendering previously had to be done solely on the CPU and real-time results are not achievable using these methods. Many different methods were developed to overcome the shortcomings of the CPU, through optimisations or by playing to the strengths of the graphics hardware of the time. Yet the limitations of memory still represented a problem with handling the massive data sets, and, in turn the image quality would suffer greatly.
The tremendous evolution of programmable graphics hardware has made high-quality real-time volume graphics a reality (SIGGRAPH 2004, p. ii). This is true as the hardware can now be programmed to handle the ray tracing algorithms to render volumetric data. Ray-tracing, nevertheless, does not take advantage of graphics hardware and requires a large number of CPU’s for interactivity (Livnat, Hansen, 1998). This statement still holds true today as using a triangle based rendering approach is still the most optimized because even though the pipeline is programmable it is still designed to render triangles more efficiently.
Interactive rendering of large volumetric data sets is a hard task. Besides direct volume rendering methods, such as ray casting, splatting, or 3D texture mapping, indirect volume rendering techniques , such as iso-surface extraction are applied ( Gerstner 2001). The first algorithm to reduce the problem of isosurface generation to a closed form problem with a simple solution was the marching cubes algorithm(Gallagher 1995 p. 109). This however was patented by General Electric and so various other methods have been developed as a way of bypassing the patent. The algorithms operate by extracting the surface information of the volumetric data and convert it into a triangle mesh for use on the graphics hardware. Similarly techniques can be used to “voxelise” triangle based models.

RESEARCH TOPIC

The project will conduct research into creating simulations of destroyable and deformable objects using voxels, volumetric data and techniques that surround this area such as iso-surface construction. The advantage of using volumetric data is that it can model objects to their smallest component parts, and more if needed. This allows for the simulation of forces on each of the components that make up the object. By adjusting the properties of objects, simulations of a reasonable accuracy should be attainable for a variety of materials such as brick and metal.
A voxel is defined as “the smallest distinguishable unit of volume” (Emery S, 2007).So in a brick wall the smallest unit of volume would be one brick. To model the destruction of the brick wall, by traditional methods, each and every brick would have to be represented by a mesh of triangles. What is proposed is that instead in the wall the wall could be modelled as a cuboid, and use a complementary volumetric data set for the simulation of the destructions. This data set would initially just be used the cuboid as a whole object. Once the destructive force is applied to the object, an octree based subdivision of the data set will be used until individual elements that are small enough are achieved for the simulation purposes. By using this octree based reduction of the data set, the data set will be kept as sparse as possible to reduce memory costs. An iso-surface can then be constructed from this data set to create a new triangle based mesh for what is left of the wall
Rendering iso-surfaces , as opposed to volume rendering is an area of continued interest to the visualisation community (Dong Z , et all, 2004). This principle of iso-surface construction will be the key to rendering the destroyed models. This will allow the new mesh to be constructed from the volumetric data set. The parts of the object that have been separated, through destruction, can then be rendered in their new locations as new separate entities.
To sum up the research will be in combining and modify existing algorithms in the area of volume rendering to create a system for allowing the complete destruction or deformation of objects.

RESEARCH QUESTION

“Can using a voxel based approach to creating simulations of destroyable and deformable objects yield accurate results in real-time?”

PROJECT EXECUTION

There are several stages to the execution of this project, each of which is summarily discussed below.
First off the data structure for the complimentary data set needs to be researched. This is an octree based structure that will allow recursive search and subdivision into smaller areas of representation. There is a possibility however that the use of Kd-trees would be better optimised.
Next the research will move into the implementations of an iso-surface extraction algorithm. There is a myriad of possibilities to choose from in this area. The best suited, by description, is a method that uses particle systems. Crossno and Angel state:
“Advantages of our approach include: vertex densities are based on surface features rather than on the sampling rate of the volume”
This allows the prevention of unnecessary triangle density that comes from using the most well known “Marching Cubes” approach. This method for the moment is only the most obvious route through description. It may turn out on upon implementation that it is not well suited, either through processing time or memory consumption. If this is the case then the project will revert to using the marching cubes algorithm and applying the decimation technique to it discussed by Shekhar, Fayyad, Yagek and Cornhill (1996).
After this the next logical step is to add in the physical simulations of the destruction. This will be done with the PhysX SDK or a similar library that simulates physics. This stage should simply involve incorporating the libraries into the existing project.
Once the physical simulation of the destruction of the objects is in place, addition of materials properties will be added. This will be used to determine the smallest unit of volume for the materials, and the type and strength for the bonds holding the materials together.
Finally voxelisation of models will be undertaken. This will allow for any model to be destroyed by creating the complimentary data set to go along with the mesh. This will involve two stages. First to actually develop the algorithm to “voxelise” mesh data, then secondly to be able to load a directX .x model and “voxelise” it.
All of the above will be put together to form a technical demonstration of the combination of the algorithms. At the most basic level this will be a brick wall that can be destroyed. At an intermediate level the demo will allow the user to be able to select properties from a list and add them to the object so that it can be destroyed in an appropriate manner for the material that it represents. The most advanced level that the demo will be taken to is being able to load in models and then assign them properties in the same way as the intermediate level demo.

PROJECT EVALUATION

The project will be critiqued on two main categories the accuracy and the performance. The performance will simply be evaluated on whether or not the simulations can be carried out in real-time, although the performance will be directly affected by the degree of accuracy that is used. So the best balance between the two categories will need to found. This balance will then be used as a demonstration in peer review situation where comments from the peers will be analysed and a conclusion drawn to the research question.

ISSUES

There are two main issues that may arise during the completion of the project. The first being, that of performance, in extracting the iso-surfaces. This will undoubtedly be the most intensive, in computational terms, part of the simulation. What may need to be done is to run the iso-surface extraction on a thread separate from the main render loop and “disguise” the first few milliseconds of the destruction with particle systems to represent the finer debris that will occur.
There will also be a problem with texturing the new iso-surface as there will be no texture coordinate information for the inside if the objects. It should be possible however to analyse the existing texture that is being used on the object and draw some basic colour representation of what will be on the inside of the object. The use of properties here will also be useful, as procedurally generated textures could be generated based on the material properties. For example perlin noise can be used to generate high quality marble and wood textures. This should present itself as a means to circumvent this issue if a simpler solution does not present itself.

RESOURCE REQUIREMENTS

As this project will mainly consist of research into applying several algorithms together to create a demo application the project the primary resource will be access to a good C++ compiler such as Microsoft’s Visual Studio 2005. Secondary to this will be the personal computers specifications that the programming will be carried out on. These will include a good processor and a modern graphics card with a programmable graphics pipeline. As for the physical simulations the PhysX software development kit will be used which is freely available for non-commercial use.

CONCLUSION

As for the future of rendering techniques John Carmack states:
“I have my own personal hobby horse in this race .... It involves ray tracing into a sparse voxel octree.”
This is a sign the future rendering techniques will involve a greater use of voxels. This therefore makes this project a step towards this future and can possibly be regarded as a stepping stone towards the future of rendering.

REFERENCES

Lander, J. 2000. [online]. Available from http://www.gamasutra.com/features/20000523/lander_pfv.htm [Accessed 29 November 2008].

Engel, K. Hadwiger, M. Kniss, J.M. Lefohn, A.E. Salama, C.R. Weiskopf, D. 2004. Real-time volume graphics. Course Notes 28. pp ii

Hansen, C. Livnat, Y. 1998. View dependent isosurface extraction. [online]. Available from http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=E11211F8A0F1E73BDE8F5CAA45622625?doi=10.1.1.42.3627&rep=rep1&type=pdf [Accessed 27 November 2008]

Gerstner, T. 2001. Fast multiresolution extraction of multiple transparent isosurfaces. [online]. Available from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19.1487&rep=rep1&type=pdf [Accessed 27 November 2008]

Gallagher, S. 1995. Computer visualisation: Graphics techniques for scientific and engineering analysis. 1st ed. CRC Press
Patient Education Foundation. 2007. [online]. Available from http://www.conquerchiari.org/Glossary.htm [Accessed 27 November 2008]

Dong, Z et al. 2004 A smart voxelisation algorithm [online]. Available from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.949&rep=rep1&type=pdf [Accessed 28 November 2008]

Shekhar, R. et al. 1996. Octree-based decimation of marching cubes surfaces. [online]. Available from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.9425&rep=rep1&type=pdf [Accessed 29 November 2008]

Strout, R. 2008 PC Perspective – John Carmack on id tech 6, ray tracing, consoles, physics and more. [online] Available from http://www.pcper.com/article.php?aid=532 [Accessed 28 November 2008]

BIBLIOGRAPHY

Baker, D. and Boyd, C. 2001. Volumetric rendering in real time. [online]. Available from http://www.gamasutra.com/features/20011003/boyd_01.htm [Accessed 27 November 2008]

Krazanowski, M. 2008. A more accurate volumetric particle rendering method using the pixel shader. [online]. Available from
http://www.gamasutra.com/view/feature/3680/a_more_accurate_volumetric_.php [Accessed 27 November 2008]

Cigoni, P. et al. 2004. Adaptive tetrapuzzles: efficient out-of-core construction and visualization of gigantic multiresolution polygonal models. [online]. Available from http://www.crs4.it/vic/data/papers/sig2004-tetrapuzzles.pdf [Accessed 20 November 2008]

Gobbetti, E. and Marton, F. 2005. Far voxels: a multiresolution framework for interactive rendering of huge complex 3D models on commodity graphics platforms. [online]. Available from http://www.crs4.it/vic/data/papers/sig2005-farvox.pdf [Accessed 17 November 2008]

Gregorski, B. Et al. 2002. Interactive view-dependent rendering of large isosurfaces. [online]. Available from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.8.6961&rep=rep1&type=pdf [Accesed 22 November 2008]

Wood, Z. 2000. Semi-regular mesh extraction from volumes. [online]. Available from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.1269&rep=rep1&type=pdf [Accessed 23 November 2008]

Montani, C, Scateni, R. Scopigno, R. 1994. Discretized marching cubes. [online]. Available from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.3182&rep=rep1&type=pdf [Accessed 24 November 2008]

Angel, A. Crossno, P. 1997. Isosurface extraction using particle systems. [online]. Available from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.8732&rep=rep1&type=pdf [Accessed 29 November 2008]

Heidelberger, B. Et al. 2003. Volumetric collision detection for deformable objects. [online]. Available from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.2297&rep=rep1&type=pdf [Accessed 28 November 2008]

Stolte, N. 1997. Robust voxelisation of surfaces. [online] Available from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.1047&rep=rep1&type=pdf [Accessed 26 November 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]