Monday, March 16, 2009

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]