Siggraph '08 Realtime Raycasting

For any interested parties, I'm doing a talk this year at siggraph on raycasting. The course is called Beyond Programmable Graphics: In Action. It covers some sparse voxel octtree raycasting stuff.

--
Jon Olick
id Software

[Phantom]

That sounds interesting. And it's also interesting to have an id guy visiting the forum. I guess John is a lurker?

The Carmack? Yeah he measures out how many public appearances he does a year.

From the official program:

Beyond Programmable Shading: In Action
Thursday, 1:45 - 5:30 pm
Level: Intermediate

This class, the second in a series, explores case studies of combining traditional rendering API usage with advanced parallel computation from game developers, researchers, and graphics hardware vendors. There are strong indications that the future of interactive graphics programming
is a more flexible model than today’s OpenGL/Direct3D pipelines. Graphics developers will need to have a basic understanding of how to combine emerging parallel programming techniques and more flexible graphics processors with the traditional interactive rendering pipeline. Each case study in the class includes a live demo and discusses the mix of parallel programming constructs used, details of the graphics algorithm, and how the rendering pipeline and computation interact to achieve the technical goals.

Prerequisites
Experience with a modern graphics API (OpenGL or Direct3D), including basic experience with shaders, textures, and frame buffers and/or background in parallel programming languages. Some background in parallel programming on CPUs or GPUs is useful but not required, as an overview will be provided in the course. Attendees are strongly encouraged to attend the first SIGGRAPH 2008 class in this series: Beyond Programmable Shading: Fundamentals.

Instructors
Aaron Lefohn
Intel Corporation

Mike Houston
AMD Corporation

David Luebke
NVIDIA Corporation

Jon Olick
Id Software

Fabio Pellacini
Dartmouth University


Zelex, thanks for the extra frosting by telling us that you'll talk about raycasting. I was going to attend this class anyway, but now it's even more interesting ...

[toxie]

uhmmm.. wow.. so all the talking/speculation about id using some voxel grid ray tracing/casting were indeed true..
are you allowed to leak some details at this point?
(rough info on geometry handling vs. textures vs. dynamic/moving/new objects vs. lighting vs. ...)

Wow, very impressive track record:

Heavenly Sword (2007), Sony Computer Entertainment Europe Ltd.
Ratchet & Clank Future: Tools of Destruction (2007), Sony Computer Entertainment America, Inc.
Warhawk (2007), Sony Computer Entertainment America, Inc.
MotorStorm (2006), Sony Computer Entertainment Incorporated
Resistance: Fall of Man (2006), Sony Computer Entertainment Incorporated
Jak X: Combat Racing (2005), SCEA
Men of Valor (2004), Vivendi Universal Games, Inc.
Medal of Honor: Allied Assault (2002), Electronic Arts, Inc.
CIA Operative: Solo Missions (2001), ValuSoft, Inc.

http://www.mobygames.com/developer/sheet/view/developerId,54871/

Lead Programmer, Naughty Dog
SCE, Playstation Edge
and now id!

on topic: do you perform raycasting on the GPU or CPU?

[toxie]

ray tracey, you're a stalker..

ray tracey, you're a stalker..

that made my day


Jon, I would love more detail, too

uhmmm.. wow.. so all the talking/speculation about id using some voxel grid ray tracing/casting were indeed true..
are you allowed to leak some details at this point?
(rough info on geometry handling vs. textures vs. dynamic/moving/new objects vs. lighting vs. ...)

Hybrid rendering
Characters/Dynamic Objects with traditional rendering techniques
World with raycasting (and is completely static, so lighting is baked)

Wow, very impressive track record:

Heavenly Sword (2007), Sony Computer Entertainment Europe Ltd.
Ratchet & Clank Future: Tools of Destruction (2007), Sony Computer Entertainment America, Inc.
Warhawk (2007), Sony Computer Entertainment America, Inc.
MotorStorm (2006), Sony Computer Entertainment Incorporated
Resistance: Fall of Man (2006), Sony Computer Entertainment Incorporated
Jak X: Combat Racing (2005), SCEA
Men of Valor (2004), Vivendi Universal Games, Inc.
Medal of Honor: Allied Assault (2002), Electronic Arts, Inc.
CIA Operative: Solo Missions (2001), ValuSoft, Inc.

http://www.mobygames.com/developer/sheet/view/developerId,54871/

Lead Programmer, Naughty Dog
SCE, Playstation Edge
and now id!

on topic: do you perform raycasting on the GPU or CPU?

Thanks

Currently using CUDA, but I plan on trying out Larabee.

[beason]

Sweet!

But, as a class, does that mean it will have very limited seating? Say, around 30?
I want to witness the awesome tech but don't want to either stand in line for hours nor take up a spot from a more applicable participant.

Lastly, a nub question: why do ray casting for the scene? What does ray casting give you that the traditional hw API can't do? If I had to guess, I would say you could get more polys on screen, but maybe only by a factor of 10 or less, depending on system memory vs. video card memory. (I don't do much hw rasterization so I don't know its limits.)

Sweet!

But, as a class, does that mean it will have very limited seating? Say, around 30?
I want to witness the awesome tech but don't want to either stand in line for hours nor take up a spot from a more applicable participant.

Lastly, a nub question: why do ray casting for the scene? What does ray casting give you that the traditional hw API can't do? If I had to guess, I would say you could get more polys on screen, but maybe only by a factor of 10 or less, depending on system memory vs. video card memory. (I don't do much hw rasterization so I don't know its limits.)

I'm not sure if it will be a small room or not. I don't have that info yet.

The primary benefit to a single player game is that it gives you a generational skip in geometric complexity. (Which is about 8x additional geometry) However there are lots of development pipeline benefits behind the scenes that come in for free. If you never have to worry about geometric complexity and you never have to worry about texture detail, then development is greatly simplified. You can simply throw a ton of artists at the problem without worrying about impacts on performance or runtime memory requirements. Thats huge and should save lots of development effort.

The primary benefit to a single player game is that it gives you a generational skip in geometric complexity. (Which is about 8x additional geometry) However there are lots of development pipeline benefits behind the scenes that come in for free. If you never have to worry about geometric complexity and you never have to worry about texture detail, then development is greatly simplified. You can simply throw a ton of artists at the problem without worrying about impacts on performance or runtime memory requirements. Thats huge and should save lots of development effort.

So no more hexagonal trees and tubes in the next generation

Currently using CUDA, but I plan on trying out Larabee.

Can you tell what performance you're getting on a GTX280 for a 720p scene?
Which architecture (Larrabee or GPU) do you think is better for sparse voxel ray casting?


Carmack said in the PCPer interview:

I’ve been pitching this idea to both NVIDIA and Intel and just everybody about directions as we look toward next generation technologies.

and

PCPER: How dramatic would a hardware change have to be to take advantage of the structures you are discussing here?
CARMACK: It’s interesting in that the algorithms would be something that, it’s almost unfortunate in the aspect that these algorithms would take great advantage of simpler bit-level operations in many cases and they would wind up being implemented on this 32-bit floating point operation-based hardware. Hardware designed specifically for sparse voxel ray casting would be much smaller and simpler and faster than a general purpose solution but nobody in their right mind would want to make a bet like that and want to build specific hardware for technology that no one has developed content for. The idea would be that you have to have a general purpose solution that can approach all sorts of things and is at least capable of doing the algorithms necessary for this type of ray tracing operation at a decent speed. I think it’s pretty clear that that’s going to be there in the next generation. In fact, years and years ago I did an implementation of this with complete software based stuff and it was interesting; it was not competitive with what you could do with hardware, but it’s likely that I’ll be able to put something together this year probably using CUDA. If I can make something that renders a small window at a modest frame rate and we can run around some geometrically intricate sparse voxel octree world and make a 320x240 window at 10 fps and realize that on next-generation hardware that’s optimized more for doing this we can go ahead and get 1080p 60 Hz on there.

Will "next-generation" graphics cards (or Larrabee) contain special hardware to accelerate the ray casting and if so, what performance boost could be expected from that?

One last question

Hybrid rendering
Characters/Dynamic Objects with traditional rendering techniques
World with raycasting (and is completely static, so lighting is baked)

So is it correct to say that the world is raycasted voxels and characters/dynamic objects is rasterized polygons?

So no more hexagonal trees and tubes in the next generation

Nope! and no more normal maps anymore either. Real geometry only.

Can you tell what performance you're getting on a GTX280 for a 720p scene?

I'm not done yet, but I think 60fps consistently should be possible. Definitely 30fps.

Which architecture (Larrabee or GPU) do you think is better for sparse voxel ray casting?

Thats a tough question. CUDA has some interesting benefits, but lacks a general caching architecture. That significantly hurts raycasting. Larrabee on the other hand has generic CPUs with generic caches, so probably larrabee on that one. However its impossible to tell without real hardware in hand.

Carmack said in the PCPer interview:

I’ve been pitching this idea to both NVIDIA and Intel and just everybody about directions as we look toward next generation technologies.

and

PCPER: How dramatic would a hardware change have to be to take advantage of the structures you are discussing here?
CARMACK: It’s interesting in that the algorithms would be something that, it’s almost unfortunate in the aspect that these algorithms would take great advantage of simpler bit-level operations in many cases and they would wind up being implemented on this 32-bit floating point operation-based hardware. Hardware designed specifically for sparse voxel ray casting would be much smaller and simpler and faster than a general purpose solution but nobody in their right mind would want to make a bet like that and want to build specific hardware for technology that no one has developed content for. The idea would be that you have to have a general purpose solution that can approach all sorts of things and is at least capable of doing the algorithms necessary for this type of ray tracing operation at a decent speed. I think it’s pretty clear that that’s going to be there in the next generation. In fact, years and years ago I did an implementation of this with complete software based stuff and it was interesting; it was not competitive with what you could do with hardware, but it’s likely that I’ll be able to put something together this year probably using CUDA. If I can make something that renders a small window at a modest frame rate and we can run around some geometrically intricate sparse voxel octree world and make a 320x240 window at 10 fps and realize that on next-generation hardware that’s optimized more for doing this we can go ahead and get 1080p 60 Hz on there.

Will "next-generation" graphics cards (or Larrabee) contain special hardware to accelerate the ray casting and if so, what performance boost could be expected from that?

This is a particular point in my talk. I basically explain how its kind of the destiny of graphics cards to have hardware that enhances raycasting as it will likely be developed to enhance rasterization and then raycasting can piggyback on the technology.

So is it correct to say that the world is raycasted voxels and characters/dynamic objects is rasterized polygons?

Thats the plan, but there is a plan B if raycasting characters/dynamic objects are feasible on hardware/development tools. I think voxelized characters may be better for next next generation though.

Very cool, thanks for all the answers.
Real geometry for everything instead of normal maps . I kinda dislike normal maps, they only look good under certain lighting conditions. I assume parallax mapping and relief mapping won't be needed anymore as well.

I basically explain how its kind of the destiny of graphics cards to have hardware that enhances raycasting as it will likely be developed to enhance rasterization and then raycasting can piggyback on the technology.

That's very interesting. Do you think GPU's are going to have/need generic caches?

Well, can't wait for Siggraph.

This may be a lame question here, but what do you exactly mean by "sparse voxel octree ray casting" ? A practical application of ray tracing through a good old octree in order to get some nice secondary/volume effects in a game? And why grids? Because they're useful for things other than ray casting? Because their traversal is stackless? Because they're cheap to build/store?

Do you think GPU's are going to have/need generic caches?

If they plan to compete with larrabee, they better

This may be a lame question here, but what do you exactly mean by "sparse voxel octree ray casting" ? A practical application of ray tracing through a good old octree in order to get some nice secondary/volume effects in a game? And why grids? Because they're useful for things other than ray casting? Because their traversal is stackless? Because they're cheap to build/store?

Lots of good questions. The primary difference between this approach and a typical raycaster is that in this approach you don't have polygons. The oct-tree is the geometry. So why do it this way? You get unqiue texturing and unique geometry as a side effect and it turns out that this is incredibly good for CUDA / Larrabee. I'll attempt to answer those questions in a bit more detail in the talk.

This may be a lame question here, but what do you exactly mean by "sparse voxel octree ray casting" ? A practical application of ray tracing through a good old octree in order to get some nice secondary/volume effects in a game? And why grids? Because they're useful for things other than ray casting? Because their traversal is stackless? Because they're cheap to build/store?

Lots of good questions. The primary difference between this approach and a typical raycaster is that in this approach you don't have polygons. The oct-tree is the geometry. So why do it this way? You get unqiue texturing and unique geometry as a side effect and it turns out that this is incredibly good for CUDA / Larrabee. I'll attempt to answer those questions in a bit more detail in the talk.

im interested in the resolutions you guys can render now.. and are the actual voxels small enough to not be visible. Also, for texture mapping, are textures indepenedent of the geometry or is the geometry the actual texture since artist now just paint geometry...

This octree representation may be very useful for LEGO computer games - a very bricky solution
Is it something like in this paper from Klein et al. : http://cg.cs.uni-bonn.de/default.asp?page=http://www.cg.cs.uni-bonn.de/publications/publication.asp?id=247&language=en ?

im interested in the resolutions you guys can render now.. and are the actual voxels small enough to not be visible. Also, for texture mapping, are textures indepenedent of the geometry or is the geometry the actual texture since artist now just paint geometry...

Because all the data is streamed, you can have as high of a detail as you want. There is also another trick that you can do with oct-trees which I'll talk about in my siggraph talk, but I don't want to give it away just yet.

The geometry and the texture are one in the same. Now, for the source art... if you want to voxelize a triangle mesh which has a texture map associated with it, then you use a texture map for that, but as far as the runtime is concerned... the geometry and texture are the same thing.

This octree representation may be very useful for LEGO computer games - a very bricky solution
Is it something like in this paper from Klein et al. : http://cg.cs.uni-bonn.de/default.asp?page=http://www.cg.cs.uni-bonn.de/publications/publication.asp?id=247&language=en ?

An interesting link. There are definitely some similarities with the voxelization of geometry through enumerating over the surface of a triangle. There is no material data here though, I could see one being used though for things like determining surface type so you know what sound to play when you drive a car over the surface for example, but for rendering it hasn't been necessary so far with this technique.

Hello there, you may find some useful information here before seeing the presentation by ID:
- ray tracing into voxel compressed into an octree (defacto a sparse octree for most data):
http://www.sci.utah.edu/~wald/Publications/2007///MROct/download//mroct.pdf
- the octree texture by Sylvain Lefebvre
http://lefebvre.sylvain.free.fr/octreetex/
- Sylvain also invented the Mega texturing technique which may be found here:
http://www-evasion.imag.fr/Membres/Sylvain.Lefebvre/texprod/

I am finally really eager to know how the streaming (the virtual part of the thing) is done, what the data structures are and all the nice details of the implementation. I however think that the octree may be a better solution than std ray tracing since the mip-mapping of the octree makes the technique less sensitive to the amount of data, memory bandwith problems and geometry aliasing. With ray tracing on triangles, we have to trace the ray until the leaves of the tree. This is also a good reason to choose a voxel octree for a GPU since only a smaller amount of data (which may be coherent) is required for one frame.

However, this amount of data for a given scene may be huge and the streamer has to be really good when the point of view is moving fast.

Do you think there will be some slides on the net? I won't be able to go to Siggraph.

Ben

Finally, I am not sure that virtual sparse octree is the only solution to handle huge quantities of geometry. Brute force tesselation also provides very good result. I wrote a small application which is already able to output subdivision surfaces with 500 millions triangles /sec on a 8800GT i.e. almost the theoretical limit of the rasterizer. The tesselation also provides a very cache efficient result. For the production of data, I am not sure that it is better or worse than octree. Tesselation is natural with characters (think about ZBrush which easily provides a coarse mesh and its displacement map) and of course with terrains. OF course, octree are really good with their ability to be directly painted and there is no required data about the topology of the surface. However, mega-texturing already provides the ability to paint everything. So for the future:
megatexture + tesselation > virtual sparse octree or megatexture + tesselation < virtual sparse octree ??
I have no personal idea about it. But, we are currently investigating the first solution for the current gaming platforms.
Ben

PS: Zelex: you did not try to implement the octree on the CELL ?! It may be nice to have such a nice implementation on dev-net like Edge .

My colleagues and I have been doing some research in this area and the closest paper we have found is this:
http://www.crs4.it/vic/cgi-bin/bib-page ... :2008:SGR'

close second:
http://artis.imag.fr/Publications/2008/CNL08/

For those of us unable to attend will there be any papers, powerpoints, videos, etc. posted afterwards?

the geometry and texture are the same thing.

So basically you're doing quantum physics now (Schrödinger's cat in box is dead and alive at the same time) ?

the streamer has to be really good when the point of view is moving fast

I would like to know that as well. Is there a lag or some kind of progressive refinement happening when you're rapidly streaming in new voxel sets and is this where the lack of caches on GPU's hurts the most?

My colleagues and I have been doing some research in this area and the closest paper we have found is this:
http://www.crs4.it/vic/cgi-bin/bib-page ... :2008:SGR'

close second:
http://artis.imag.fr/Publications/2008/CNL08/

For those of us unable to attend will there be any papers, powerpoints, videos, etc. posted afterwards?

EXCELLENT!

Finally, I am not sure that virtual sparse octree is the only solution to handle huge quantities of geometry. Brute force tesselation also provides very good result. I wrote a small application which is already able to output subdivision surfaces with 500 millions triangles /sec on a 8800GT i.e. almost the theoretical limit of the rasterizer. The tesselation also provides a very cache efficient result. For the production of data, I am not sure that it is better or worse than octree. Tesselation is natural with characters (think about ZBrush which easily provides a coarse mesh and its displacement map) and of course with terrains. OF course, octree are really good with their ability to be directly painted and there is no required data about the topology of the surface. However, mega-texturing already provides the ability to paint everything. So for the future:
megatexture + tesselation > virtual sparse octree or megatexture + tesselation < virtual sparse octree ??
I have no personal idea about it. But, we are currently investigating the first solution for the current gaming platforms.
Ben

PS: Zelex: you did not try to implement the octree on the CELL ?! It may be nice to have such a nice implementation on dev-net like Edge .

What you say is definitely true. An infinite geometry engine is definitely possible on current generation hardware. I wrote one while at Sony. However, it requires lots of man art hours to tweak the art data into submission. Ray casting is kind of the next evolution of that kind of technology where the goal is to make it easy and economical. There are plenty of hurdles still yet to pass before that goal is met in my critical eyes, but I'm making great strides towards it.

So basically you're doing quantum physics now (Schrödinger's cat in box is dead and alive at the same time) ?

Lol!

I would like to know that as well. Is there a lag or some kind of progressive refinement happening when you're rapidly streaming in new voxel sets and is this where the lack of caches on GPU's hurts the most?

There is a progressive refinement of sorts that you need, because you can't have an entire level loaded at the same time. Its a *lot* of data. The lack of great caches hurts ray casting performance, and not necessarily the streaming.

By the way, yes the slides will be made available to the public after siggraph.

There's a thing I cannot understand in that sparse voxel octree thing... You said it can be streamed from the disk... but making some maths:

- Assume you want a moderate view distance ( like 500m or 1Km in an outdoor scene ).
- Assume a 256Mb graphics card ( think in a PS3, for example ).
- 1 voxel = RGBA color(4 bytes) + 1 quantized normal(let's say... 1byte) + 1 materialID ( for properties like specular, etc...) = 6bytes

- That's a 355^3 voxel scene.

How can be 355x355x355 enough for an outdoor scene like a beach+mountains in Crysis? Ok, Ok... you can perform some kind of adaptive voxeling so furthest voxels won't be displayed at full detail. Ok, a tri-linear LOD can help but I bet you'll need like 5k^3 to get a good result for a Crysis/Quake Wars outdoor level ( because you want clouds, mountains, forest, etc... ). ZBrush uses pixols(voxels with extended data)... but a model is not a large scene...

On the other hand... what you do if, for example, you change the point of view suddently ( think in Portal )... how do you stream that without a big loading laaaaaaaag? And more considering a FPS game where frames per second are important...

And... what about dynamic objects? You could stream a static scene... but to voxelize a character, a barrel falling due to gravity, etc... you gonna need a super-fast octree construction.

And other problem... do you convert polygons to voxels using an offline tool or do you make it on real time? Or do your artist model directly using voxels/point clouds?

Perhaps an uniform grid + simple raycast could handle better uniformly-distributed scenes? Uniform grids can be dynamically updated at lightspeed and they are cache-friendly and easily parallelizable... but the teapot-in-stadium can be a problem when your traverse it...

Btw.. have you seen this article?
http://www.tkarena.com/Articles/tabid/59/ctl/ArticleView/mid/382/articleId/38/Death-of-the-GPU-as-we-Know-It.aspx

Model made of 1,5M voxels:


Tons of instances of that model with shadows and reflection:


It seems the return to Delta Force, Comanche 3 and Outcast is closer than we think

[toxie]

so finally someone used point clouds for a commercial(?) engine.. but i still wonder how they control the memory (should be impossible to keep everything in mem all the time).. impressive pictures nevertheless..

- Assume you want a moderate view distance ( like 500m or 1Km in an outdoor scene ).
- Assume a 256Mb graphics card ( think in a PS3, for example ).
- 1 voxel = RGBA color(4 bytes) + 1 quantized normal(let's say... 1byte) + 1 materialID ( for properties like specular, etc...) = 6bytes

- That's a 355^3 voxel scene.

How can be 355x355x355 enough for an outdoor scene like a beach+mountains in Crysis? Ok, Ok... you can perform some kind of adaptive voxeling so furthest voxels won't be displayed at full detail. Ok, a tri-linear LOD can help but I bet you'll need like 5k^3 to get a good result for a Crysis/Quake Wars outdoor level ( because you want clouds, mountains, forest, etc... ). ZBrush uses pixols(voxels with extended data)... but a model is not a large scene...

Its a next generation engine, PS3 doesn't exactly have the system requirements necessary for a full game.

On the other hand... what you do if, for example, you change the point of view suddently ( think in Portal )... how do you stream that without a big loading laaaaaaaag? And more considering a FPS game where frames per second are important...

There are a few techniques to mitigate that problem, but Quake Wars solved a similar issue by dropping the player in by parachute. So there are technology solutions and game play solutions to that issue.

And... what about dynamic objects? You could stream a static scene... but to voxelize a character, a barrel falling due to gravity, etc... you gonna need a super-fast octree construction.

While it is possible to construct oct-trees on the GPU, I'm thinking that for at least the near future, hybrid rendering with dynamic objects using standard rasterization is the way to go.

And other problem... do you convert polygons to voxels using an offline tool or do you make it on real time? Or do your artist model directly using voxels/point clouds?

The tools side of things has yet to be explored in great detail. I'm hoping that they will be able to work with the voxels directly as that makes things much nicer.

Perhaps an uniform grid + simple raycast could handle better uniformly-distributed scenes? Uniform grids can be dynamically updated at lightspeed and they are cache-friendly and easily parallelizable... but the teapot-in-stadium can be a problem when your traverse it...

I don't think a uniform grid will work for most games.

Btw.. have you seen this article?
Model made of 1,5M voxels:
Tons of instances of that model with shadows and reflection:

Yes, that stuff is interesting for sure.

On the other hand... what you do if, for example, you change the point of view suddently ( think in Portal )... how do you stream that without a big loading laaaaaaaag? And more considering a FPS game where frames per second are important...

There are a few techniques to mitigate that problem, but Quake Wars solved a similar issue by dropping the player in by parachute. So there are technology solutions and game play solutions to that issue.

Have you been experimenting with solid state drives yet and do you think they will be cheap enough for next generation systems?

Have you been experimenting with solid state drives yet and do you think they will be cheap enough for next generation systems?

Doesn't the Wii already have a solid state drive? That being said, If microsoft and Sony want their consoles to be entertainment centers, they are going to need massive storage. So, probably not solid state for this next generation, but one can hope!

Doesn't the Wii already have a solid state drive?

Point taken (damn Wii)

If microsoft and Sony want their consoles to be entertainment centers, they are going to need massive storage. So, probably not solid state for this next generation, but one can hope!

I was thinking (actually hoping) more in the direction of like a 64GB SSD for storing geometry+textures (price of SSD in July 2008: $169 for 32GB, $259 64GB and $479 for 128GB, SSD prices should fall by about 60% annually) and a regular 1TB HDD for everything else, which should be dirt cheap by then (there are 1TB HDD's for about $200 now). Of course I'm not sure if even 64GB would suffice for a next gen game. But since you have figured out a couple solutions already, the streaming issue may not be that important.

Forgot to provide a source for those crazy low prices: http://blog.laptopmag.com/new-low-cost-ssds-from-ocz-could-lead-to-wave-of-upgrades

Fascinating stuff

Perhaps an uniform grid + simple raycast could handle better uniformly-distributed scenes? Uniform grids can be dynamically updated at lightspeed and they are cache-friendly and easily parallelizable... but the teapot-in-stadium can be a problem when your traverse it...

I don't think a uniform grid will work for most games.

Could you elaborate on that? Is it mainly because of the teapot in the stadium problem or are there other limitations compared to octrees?

BTW Do you know if John Carmack is going to give some details on the sparse voxel octree raycasting in his Quakecon keynote this thursday?

I am still a bit puzzled about one fact : you seem to say that sparse voxel octree can only handle static geometry, at least for now.

Don't you think a fully static world is a bit problematic for a next-gen engine ?

It seems to me that the "half-fail" of the id Tech 4 (fully dynamic lighting, but very hard to use because of the lack faked-radiosity, not so eye-candy because there was no physics engine to fully demonstrate it) has left John Carmack convinced to never attempt dynamics solutions anymore.

I understood this choice for id Tech 5, because achieving 60 hz on current-gen consoles is quite problematic, but focus all of your efforts on a displaying solution for static geometry for id Tech 6 seems a little... anachronistic to me. Displaying characters as polygons seems like a fail acknowledgment.

I don't want to say that every game should have entirely destructive environments or whatever, but building and engine around a static-geometry-based technique is not futur-proof for me.

Dynamic lighting became so simple. Deferred techniques had been technically and commercially proven. There is even already attempts to derive radiosity techniques from screen-space ambient occlusion based stuff.
The rendering part of an engine should be the more transparent as possible, so to impose static geometry is a very strong specification point.

But maybe I'm wrong and sparse voxel octree has no theorical problem with dynamic geometry, and I wrote this whole piece for nothing

I hope this doesn't look aggressive, it is just a question (maybe a naive one).

I look forward reading your response.

Clément ELBAZ

Could you elaborate on that? Is it mainly because of the teapot in the stadium problem or are there other limitations compared to octrees?

A pure uniform grid would be far too expensive memory wise to be practical at a good detail level. A uniform grid of oct-trees is more viable, but would only really work for a corridor shooter game. The uniform grid would have to be so coarse to be efficient in a different scenario that it doesn't really make sense to use it over a straight oct-tree. A uniform grid of oct-trees also has problem with register usage in CUDA.

BTW Do you know if John Carmack is going to give some details on the sparse voxel octree raycasting in his Quakecon keynote this thursday?

If Carmack has plans about what he is going to talk about, he hasn't given that information to anybody. That being said I would expect some talk about it.

I am still a bit puzzled about one fact : you seem to say that sparse voxel octree can only handle static geometry, at least for now.
...

So, to summarize, why static. Wouldn't dynamic be better? Of course dynamic would be better. The limitations here are on the hardware, not our ideas In my talk I lay out some preliminary plans on how a dynamic world could work. Taking that route might be viable if next generation hardware exceeds expectations.

Hardware limitations can be bypassed.

Games like Crysis, STALKER, even Doom 3 have succeeded providing complex non-static environments.

At a smaller scale, my team's work on a rendering engine supporting fully dynamic scenes has been not only feasible, but somewhat easy, given current computer graphics state-of-the-art.

But surely I will not be able to change id Software next engine specifications, so there's no meaning to continue

And I could very well change my mind if the results were effectively astonishing. Carmack talked about a proof-of-concept released this year, do you know if it will be publicly available ? If he wants to convince hardware manufacturers to pay attention to sparse voxel octrees, you will have to give some details at one point, right ? (and that is what you will do in your SIGGRAPH course ).

A straightforward method for handling octrees based dynamic scenes composed of instances of static objects is to have one octree per "base object", and shoot rays converted by instance from world space to octree space into the tree, handling without problems multiple instances of the data contained in the octree. Does that kind of approach would be feasible with SVO ?

I'm still very curious about your work, thanks for taking the time to respond.

Clément ELBAZ

Thanks for the explanation! Makes perfect sense, now that I think of it.
Was going to watch Carmack's speech anyway for the id Tech 5 stuff, but the probability of some raycasting info has gotten me even more excited.

Hardware limitations can be bypassed.

In some respects, you are correct. Certainly some rasterization tricks are still applicable like deferred shading and we plan on using them for dynamic objects. However, if you want to use ray tracing to light your environment entirely, the hardware just isn't fast enough for the resolutions required by next generation games.

Games like Crysis, STALKER, even Doom 3 have succeeded providing complex non-static environments.

Doom 3 had static environments and dynamic objects, but non-static lighting. Rage and Half-life 2 have certainly proven that a static environment with mostly static lighting and dynamic objects produces compelling gameplay and visuals.

Carmack talked about a proof-of-concept released this year, do you know if it will be publicly available ?

I highly doubt it, but you never know!

A straightforward method for handling octrees based dynamic scenes composed of instances of static objects is to have one octree per "base object", and shoot rays converted by instance from world space to octree space into the tree, handling without problems multiple instances of the data contained in the octree. Does that kind of approach would be feasible with SVO ?

There are some complications in the details here. Putting additional work into the ray casting kernel would make it noticably slower, even if the code was rarely executed due to register limitations. So that means that you have to dynamically update the oct-tree to avoid that. Which means uploading more traffic to the GPU, or alternatively generating the modified oct-tree data structure on the GPU. In any of those cases, it means dynamically managing the allocation of nodes in the oct-tree which adds all sorts of complications such as fragmentation related cache issues. Doing node allocation on the GPU sounds nice but requires lots of extra data to do properly. And what happens if you need to modify a section of data which isn't loaded into memory? Do you modify that section at load time? If you do then you have to coordinate your dynamic updating of the oct-tree with the GPU who may also be dynamically updating the geometry. There is a different approach which I talk about in my talk which does not require updating of the oct-tree, but would require slight modifications to the tracing code, which will affect performance which is why I say that its probably not a good idea for current generation technology. Emphasis on the "probably" and "current generation technology". If the next generation console technology is better than I expect it to be some of these issues may no longer be a problem, in which case there is definitely a plan for that.

In some respects, you are correct. Certainly some rasterization tricks are still applicable like deferred shading and we plan on using them for dynamic objects. However, if you want to use ray tracing to light your environment entirely, the hardware just isn't fast enough for the resolutions required by next generation games.

I agree. Carmack precisely said that pure ray tracing for games was a bad idea, and I agree with him either. But what about an hybrid approach ? We can use SVO to "fetch" the scene and getting typicals gBuffer informations (depth, albedo, normal) for each pixel of the screen, then send it to a deferred shader which work with dynamic lighting.

Doom 3 had static environments and dynamic objects, but non-static lighting. Rage and Half-life 2 have certainly proven that a static environment with mostly static lighting and dynamic objects produces compelling gameplay and visuals.

Half-Life 2 was great... in 2004. All of the upcoming Source-based games are starting to be criticized for the static-aspect of their environment. And in others hands than Valve's experts ones, it becomes a clearly problematic engine (Vampire Bloodlines was ugly, Dark Messiah was beautiful but needed tons of RAM...).

For Rage, I never had the pleasure to play it yet
( In fact, never even seen more than the id Tech 5 presentation for the Mac conference one or two years ago... Development keeps going well ?)

I highly doubt it, but you never know!

So sad
And unfortunately I will not be able to attend SIGGRAPH... Good news you said the slides would be available online.

There are some complications in the details here. Putting additional work into the ray casting kernel would make it noticably slower, even if the code was rarely executed due to register limitations. So that means that you have to dynamically update the oct-tree to avoid that. Which means uploading more traffic to the GPU, or alternatively generating the modified oct-tree data structure on the GPU. In any of those cases, it means dynamically managing the allocation of nodes in the oct-tree which adds all sorts of complications such as fragmentation related cache issues. Doing node allocation on the GPU sounds nice but requires lots of extra data to do properly. And what happens if you need to modify a section of data which isn't loaded into memory? Do you modify that section at load time? If you do then you have to coordinate your dynamic updating of the oct-tree with the GPU who may also be dynamically updating the geometry. There is a different approach which I talk about in my talk which does not require updating of the oct-tree, but would require slight modifications to the tracing code, which will affect performance which is why I say that its probably not a good idea for current generation technology. Emphasis on the "probably" and "current generation technology". If the next generation console technology is better than I expect it to be some of these issues may no longer be a problem, in which case there is definitely a plan for that.

Mmmmh, so if I summarize as I understand it :
- In your implementation, the octree never leaves the GPU. However you precedently talked about a progressive refinement. I guess it is kept at a minimal traffic, so am I correct if I say that for a static scene and a static point of view, the octree stays indefinitely in the GPU and there is no octree data sent to the GPU at each frame ?
- If you wanted to implement my proposal, that would implies that you have to put in place an indexer of multiples octrees, and a ray-converter from world-space to instance-object-space, to have the ray correctly travelling into the octree. You said that this was not a good idea because theses additions would take place in the ray casting kernel, and would make it too slow to perform well.
- You suggested another option, modifying the octree on the fly on the GPU, but you doubt (and I totally agree) about it possible to be manageable both in terms of speed and memory consumptions. And if you have a modification on a part that is not on the GPU, you have to wait for the part to be loaded on the GPU to dynamically modify it. As it is not displayed, I suppose you could also modify it on the CPU without taking all the processor ressources, then keep the result in the RAM.
- Finally, you have a trick that you plan to use, which is roughly to keep the octree intact and to apply a delta on it during ray casting.

I begin to become conscious that you are really stuck

Moreover, even the notion dynamicity is somewhat disturbing when we are talking about voxels.

Maybe we need to handle things separately.

Roughly, I think of two times of animated voxel stuff :
- (1) A static pack of voxels which has to be transformed with a matrix.
- (2) An "animated" pack of voxels, with keyframes composed of voxel state for each voxel of the pack, and a blending between those keyframes.
- (3) Procedurally generated animation of a pack of voxel, for example a character with reverse kinematics which is then voxelized.

( Moreover, I would assume that contrary to id Tech 6, lighting is not pre baked, and the result of ray tracing the SVO is a gbuffer and not a shaded image... So whatever the animations are, the lighting would not be affected).

If we have the VRAM saturated with the main octree, we are indeed a bit stuck. Maybe there is room for a second octree, with less memory allocated to it, that would be constantly changing data ? You could instanciate the same objects many times by simply changing the rays directions, as I described precedently. So with this kind of "instancing", the bandwidth would be less problematic (but it implies that dynamic geometry to be not unique, I'm aware that fits pretty bad with id Tech 5 and 6 philosophy). You could also uploading a "frame" of an animated pack of voxel (or two frames to blend, or three or four to blend even more smoothly...).
As we increase the size of the dynamic octree, we probably would have to decrease the size of the static one indeed, but remember it could be kept coherent with the dynamic / static ratio of the rendered world. More parts of the world are becoming dynamic, less are staying static, and so the size of the two octrees.
The rendering of two octrees doesn't seams to have very strong problems. You render the static one, obtain the depth for each pixel on the screen, then you render the dynamic one and z-kill the dynamic pixels against the depth of the static ones to obtain a properly fit between the two images.

But as we increase the size of the dynamic octree, we drastically increase the bandwith requirement either, as the dynamic octree requires an update per frame contrary to the static one. And when we have somes animations of type (3), we still have to generate the octree on the fly, which is another processing bottleneck.

Thanks for reading

Mmmmh, so if I summarize as I understand it :
...
...

Thats an awful lot of assumptions based on a single paragraph. I would love to explain it all to you, but I don't really have the time at the moment. I'll do my best to answer all your questions in the siggraph talk.

If we have the VRAM saturated with the main octree, we are indeed a bit stuck. Maybe there is room for a second octree, with less memory allocated to it, that would be constantly changing data ? You could instanciate the same objects many times by simply changing the rays directions, as I described precedently. So with this kind of "instancing", the bandwidth would be less problematic (but it implies that dynamic geometry to be not unique, I'm aware that fits pretty bad with id Tech 5 and 6 philosophy). You could also uploading a "frame" of an animated pack of voxel (or two frames to blend, or three or four to blend even more smoothly...).
As we increase the size of the dynamic octree, we probably would have to decrease the size of the static one indeed, but remember it could be kept coherent with the dynamic / static ratio of the rendered world. More parts of the world are becoming dynamic, less are staying static, and so the size of the two octrees.
The rendering of two octrees doesn't seams to have very strong problems. You render the static one, obtain the depth for each pixel on the screen, then you render the dynamic one and z-kill the dynamic pixels against the depth of the static ones to obtain a properly fit between the two images.

Certainly a valid technique, however that doesn't solve many of the problems I mentioned.

Thats an awful lot of assumptions based on a single paragraph. I would love to explain it all to you, but I don't really have the time at the moment. I'll do my best to answer all your questions in the siggraph talk.

Too bad I will not attend SIGGRAPH
Currently, what are you working on ? Implementing a robust version of your theorical work on SVO ? (or maybe another kind of work at id which has no links with id Tech 6 ? )

Certainly a valid technique, however that doesn't solve many of the problems I mentioned.

Sure, generally speaking, dynamics environments can't be as optimized as statics ones, that is a fact.

But speaking of that kind of algo :

Code: Select all

for each frame
   // Drawing static
   if( static octree deprecated ) stream to GPU the static octree update
   ray trace static octree into gBuffer using point of view aligned rays

   // Handling of dynamic objects
   for each type of dynamic object
       load the dynamic octree on the GPU with data of this dynamic object from the RAM
       for each instance of this dynamic object in the world
           load the matrix World, matrix world of this instance
           create matrix WorldView, multiplication of World with the point of view matrix
           ray trace dynamic octree into gBuffer, using WorldView aligned rays (and zkill the result against the current gBuffer).

   // Handling dynamic lighting
    get shaded image from deferred shader and current gBuffer.

    display shaded image !



I think the ray casting kernel could be left unchanged with this algo. I suppose that at one point you have a kind of pointer (in CUDA) to the root of the octree, which is a global variable or a parameter of the kernel function. In the second case, handling multiples octrees would come in for free.
We have also to multiply the POV aligned ray by a world matrix. At some point you're obviously giving the current POV direction and position, as an input for the ray tracer. This POV direction and position would just have to be multiplied with a world matrix before being sent.
I think the whole CUDA code could be left intact.

But certainly, with that algo we have many more bandwith consumptions than with static worlds, but we talk about dynamic objects, so as I said we could assume the dynamic octree to be far smaller than the static one.
A character, a car, a crate or whatever need a very different scale than an octree for a whole scene seen from one POV, but as it is far smaller, we could have the same resolution for the dynamic object than the static world with a smaller octree.


Thus we could achieve infinite resolution rendering on static worlds but also on dynamics objects and characters, which would allow to have next-next-gen on next-gen hardware

Games like Crysis have proven than there was a lot of interesting gameplay arising from a good-balanced ratio between static and dynamics stuff. If id Tech 6 could additionnaly provide voxel quality for dynamics objects...


I see two immediates benefits of using an octree :
- You can have a very strong precision in the world data
- You can display it at the precision you want, since the octree data filter linearly (each case containing the filtered result of its eight children).

Did you manage to do that ? Do you have some kind of cursor "From Best performances to Best quality" which scale the perf and graphics linearly ?
A renderer that could scale linearly performances vs graphics quality... Groundbreaking indeed

Thanks for reading.

Too bad I will not attend SIGGRAPH
Currently, what are you working on ?

Last I checked, I was working on a presentation for Siggraph on Beyond Programmable Shading

Sure, generally speaking, dynamics environments can't be as optimized as statics ones, that is a fact.
...

Let ask the question though.... Is it really all that necessary? Dynamic objects being primarily characters. Characters in existing games already look really darn good. Usually many times better than environments. Characters in Rage still use rasterization and they look absolutely amazing. I have always thought about the next next generation being all about lighting, and not really about the massive amount of detail you can get on characters. I like being a technical idealist and saying that everything voxels is the best way to do things, but I'll only let it hurt me so much. If the difference between rasterized characters and raycasted characters is visually small, and rasterizing them is twice as fast, then I think my choice is pretty clear for 60 fps.

Finally, I am not sure that virtual sparse octree is the only solution to handle huge quantities of geometry. Brute force tesselation also provides very good result. I wrote a small application which is already able to output subdivision surfaces with 500 millions triangles /sec on a 8800GT i.e. almost the theoretical limit of the rasterizer. The tesselation also provides a very cache efficient result. For the production of data, I am not sure that it is better or worse than octree. Tesselation is natural with characters (think about ZBrush which easily provides a coarse mesh and its displacement map) and of course with terrains. OF course, octree are really good with their ability to be directly painted and there is no required data about the topology of the surface. However, mega-texturing already provides the ability to paint everything. So for the future:
megatexture + tesselation > virtual sparse octree or megatexture + tesselation < virtual sparse octree ??
I have no personal idea about it. But, we are currently investigating the first solution for the current gaming platforms.
Ben

PS: Zelex: you did not try to implement the octree on the CELL ?! It may be nice to have such a nice implementation on dev-net like Edge .

What you say is definitely true. An infinite geometry engine is definitely possible on current generation hardware. I wrote one while at Sony. However, it requires lots of man art hours to tweak the art data into submission. Ray casting is kind of the next evolution of that kind of technology where the goal is to make it easy and economical. There are plenty of hurdles still yet to pass before that goal is met in my critical eyes, but I'm making great strides towards it.

My impression is that the only problem with tesselation is direct3d{9|10} and the difficulty to integrate it with d3d. With d3d9, you can instantiate patch along the surface, it is efficient but you need to tweak the vertex buffers / index buffers which is a *pain* to integrate. With d3d10 and the use of streams, it is easier but slooooowww (30 millions tri/ s which is ridiculous). On the contrary, both xbox and ps3 (through edge) support it pretty well. You do not change the buffers and we can keep the "volatility" of the tesselation i.e. the triangles only exists when rasterized. When directx 11 will go out, the tools and PC games which will able to support it and I do not see any reason not to use it since the tesselated models may be seen in real time and the machines (and the specific data exports) will be homoegenous (except for the Wii but Nintendo will have certainly stopped selling video games and will be selling wii-sport-elec machines, wii-diet drinks, wi-cars, wii-motos, wii-wii, wii-pen and wii-ketchup ). Unfortunately, if you want to make a game compatible with PCs, it is true that it is pretty hard today. We are currently testing tesselation and as we do not plan to do PC games with d3d9 or d3d10, we simply use a software tesselation (which may be turned into a non-tesselated hardware buffer of course). As for the dynamic octree, a good solution will be also to adaptativly rasterize a displaced mesh inside it.

Ben

I've been interested in voxels ever since I learned about them a couple of years ago. I'm really interested in hearing they'll be in common use! I can't wait to read the slides when they become publicly available.

Mmmmh, so if I summarize as I understand it :
- In your implementation, the octree never leaves the GPU. However you precedently talked about a progressive refinement. I guess it is kept at a minimal traffic, so am I correct if I say that for a static scene and a static point of view, the octree stays indefinitely in the GPU and there is no octree data sent to the GPU at each frame ?

I don't think he said the octree never leaves the GPU. In fact, I think he implied that the octree has to leave the GPU. I just tried to do some initial calculations, and if you had an octree of about 1000x1000x1000 in size, which I don't believe would even be big enough for a game although I could be wrong, that would be roughly 1000 megabytes, given that each voxel is only 1 byte! Even if you were only storing the object, which may consist of only 10% of the space, that would be 100 megs.