Molly Rocket

[ryg]

[sean]

[billyzelsnack]

[quote="sean"]

[billyzelsnack]

btw. Don't bother trying to download the class video from the Siggraph site yet. The tricky bitches don't tell you that it's not available to until Sept 1 until after you pay for it.

[TomF]

[sean]

[skynet]

Hi,

this is my first post here, but I'm too into this topic to resist. I'd like to throw some thoughts into this discussion in the hope to gain some insights I have not yet found. It will be a bit lengthy (I guess...), please bear with me.

First, I'm going to reconsider why we need (better: want) stuff like SVT or SVO. We want almost unlimited detail in our virtual worlds. How did we achieve detail up today? We used textures to approximate detail that we couldn't put into geometry. We used geometry to approximate the surface of real objects which ultimately consist of atoms. So, in theory we could abandon all textures and triangles and build the world out of atoms - voxels.

Is it possible to render scenes with (almost) ulimited detail onto the screen? Yes, because a screen has only a finite number of pixels, the amount of detail it can present is limited as well.

This is _the_ key insight. No matter how large or detailed you world is, at any given time, you _cannot_ see

a) more triangles than there are pixels on the screen
b) more texels than there are pixels on the screen

(things like multiple passes or multisampling act as a constant factor here)


Things that cannot be seen can be classified as
a) out of the screen - frustum culling helps here
b) occluded - occlusion culling helps here
c) too small - level-of-detail and detail culling help.


So, for instance, if you _know_ which texels are needed for a given frame, you don't have to store much more then these texels in RAM. Basically it means, _no matter_ how large or detailed a texture is, you'll never need much more memory at once than a given working set of texels, which is primarily dependend on how large your screen resolution is - which is fixed over the runtime of your program!

This is one of the reasons why Carmack is so happy about his megatexture stuff. The memory footprint for texturing his world is almost independent from how large the textures are or how many of them there are. He can use the same super-detailed-megastuff for all platforms. And all of them seem to behave very good with this system (access times and DVD capacity put aside). The artists can throw any detail they want at the system; at runtime it will gracefully select exactly (more or less) those texels which can actually be percieved. There will be even a tool which automatically determines all possible player locations and then removes mip-texels from the database the player cannot ever possibly see on his screen in order to save some disk space.

Algorithms like this, whose runtime (and storage requirements) is primarily determined by the size of the screen resolution, are often called "output sensitive".

Virtual textures could in this sense be seen as te solution to output sensitive texturing. And Google Earth is the best example that it works


And finally, we come to the _actual_ problem I want to discuss...
Unfortunately, there is no output sensitive solution to geometry yet!


There are a few algorithms that combine hierarchical scenestructure, frustum culling, occlusion culling and forms of LOD to achieve realtime rendering of scenes with billions of triangles but none of them (at least, I doubt that) would be able to render scenes with unlimited detail.

Raytracing promised output sensitivity a long time ago, but yet is not able to keep its promise.
For one, yes, if you employ acceleration structures, the runtime complexity is somwhere at num_pixels*O(log(num_polygons)), thus largely independent from the scene complexity.
But have you ever seen/used an interactive out-of-core raytracer that actually would allow you to explore a really detailed dataset?


So, what's the deal with output sensitive geometry? Level of Detail

Frustum culling and occlusion culling are practically solved problems and can be done in near O(log(num_polygons)) if used with hierarchical datastructures. Raytracing even inherently does both.
But LOD? Uhhm, not that I knew of...
In order to be useful, the LOD algorith must be able to deliver correct LOD-level for any part of the scene anytime.
And here the problem starts... with a triangulated scene, what is a "correct LOD level" ? What is "a part of the scene"?

Why do we need LOD at all, you might ask. Because, in order to be fully output-sensitive our renderer must be "detail-insensitive". Consider this: You've modeled a monster with 1 mio triangles, from which you can see, maybe 500k at any given time. Piece of cake for any modern gfx card! Now you move so far away that the monster is only 10x10 pixels on the screen. But since you are now so far away, you can now see the monster's 1000 brothers, also each occupying 10x10 pixels. That is 500 Million Triangles on an area of 100k pixels now! No current gfx card could handle that amount of vertex data and overdraw. If you had a LOD Algorithm, it would have given you a LOD Level, with say 100 Triangles. Thats 100k Triangles per frame - easy cake for any gfx card. We cannot afford to do work for triangles that are ultimately not visible.

What most people (and even authors of such algorithms) don't seem to realize (at least in this clarity) is that Level-of-Detail should NOT mean to just simplify a geometric object "somehow". Instead LOD algorithms should provide an answer to the sampling question which rasterization/raytracing/raycasting is at its heart.
"Rasterizer: hey LOD, I'm rasterizing this mesh, which is at distance D to the image plane"
"LOD: so your pixels are X units wide at mesh's position, I'm providing you with LOD level L that contains no triangles which project to an area smaller than a pixel."

For textures, this is a solved problem: mipmaps. Computing LOD is easy:
Frequency has a meaning there. Each texel has the same size and each texel has a neighbour, so downsampling them is easy.The MIP-maps have a fixed memory footprint, which is guaranteed to shrink to 1/4 with each level. There is only one way to look at a texture: from above.

For triangle meshes, this is hard:
a) what is the "maximum frequency" of a mesh? can a mesh be treated as "signal" at all?
b) geometry might be placed sparsely in space
c) what is neighbourship here?
d) how to filter? _what_ can be filtered at all?
c) can the 1/2 band-limited version of the mesh guaranteed to be x times smaller in memory than the original?
e) everything is completely view-dependent; the mesh can have completely different properties when view from different angles

There is no triangle-based LOD algorithm known to me that can answer all tese questions.

So, finally we arrive at voxels.
Voxels allow you to compute LOD levels like with textures (especially volume textures). Many things that are hard with triangles are relatively easy with voxels.

I did some tests where I voxelized (and then mipmapped ) an object and rendered it as clouds of point-sprites. Although, it passed the 1000-monsters-test, it quickly showed its ugly side. When many of the points sprites ended up on the same pixels, the overdraw (and pipeline-dependecies?) sucked the fps down. Also, I had to implement a vertexshader which computes the right pointsprite size, so I don't get any holes. Raycasting would get rid of the problem: no holes, no overdraw.

One of the most important things which didn't get covered in Jon Olick's presentation is, why they chose to make their voxels "one sided", as if each voxel would always only represent a part of a surface of a closed body.
But at latest when voxels get mipmapped, they start to represent space. Space that may look different from each view angle... Can you really get away with just averaging colors and normals? The thin-wall-problem can't be solved by the artists, because you just need to go far enough away until you see both walls fall into one pixel...and then the voxel-mipmap-hierarchy must have an answer to this.

Also, there are many papers out there that try to solve signal-reconstruction in the context of point rendering, for instance EWA-splatting. These people go great lengths to achieve good results. Mr. Olick just suggests to "blur the rendered image" to get better looking results.


I'd like to gather your opinions and ideas to all this stuff. How can we achieve the goal of unlimited detail? Is there anything known about a compact representation for view-dependent voxels? How can they be mipmapped?


Sorry for the big post, I'm looking forward to your ideas

[Won]

[TomF]

Current signal processing in textures only works if the surface is locally smooth. With extreme LOD of the sort being discussed here, the surface is usually not locally smooth, and texture sampling starts to have problems. Zoom out enough pretty much everything becomes inherently "crinkly". That doesn't mean you can't do signal processing, just that we don't know how to just yet with existing hardware. We can't even figure out how to mipmap normal maps decently! (cones are a start I guess).

LOD on meshes is pretty evil - meshes are awful to do "algebra" with. But they render really nicely. Even on Larrabee where we don't give a monkey's about custom rasterization hardware, rendering triangles is still faster than any other known method. (tangent - actually I have a sneaking suspicion that splatting could be similarly quick on LRB, but I don't know nearly enough about its quality limitations to do any useful evaluation).

One approach that seems quite promising is take mesh, voxelize, mipmap, turn back into mesh. The important thing is to do all this offline and use it to generate meshes in a standard discrete LOD sequence (and from there you can probably do VIPM to interpolate between however many discrete LODs you choose - but that's another question). I have read about experiments in this area, and they have partial success. The two obvious problems are retaining sharp edges and dealing with material transitions.

I think both of those can be helped a lot by preserving some of the precise positional information from the mesh in the voxel grid to be used during reconstruction, rather than quantising to the voxel grid. They're just hints, and obviously this data might be filtered away by mipmapping when adjacent voxels have incompatible hints, but if it does then the feature was probably "small" and had to be nuked anyway.

I wish I had time to research this stuff more.[/i]

[skynet]

[Zaphos]

[sean]

[ryg]

[sean]

Yeah, I did some "research" many years back about applying that sort of approach hierarchically to tree rendering, so you could smoothly morph between multiple tree LODs that actually really represented the same data. I called them "object space impostors".

I also demo'd a really lamely trivial version of the idea to show a big field of lollipops at the 2001 HardCore game seminars. Lollipop demo (56kb) - use a,d,w,r,v,1,3 to move, press space to stop movement; sorry about the fullscreen. Probably one of my first OpenGL apps; this ran at 30 or 60hz on 1999-ish GPUs, because it's not a pair of quads per lollipop; the idea here was to show how scale-free object-space impostors could be; you could use them with one tree to show all the leaves, or you could use them with one forest to show all the trees, and anywhere in between.

But for the single-tree hierarchical thing, I worked from the initial hierarchy provided by the tree, rather than trying to 'discover' good locations for billboards, which I think is what you really need. And I never got any good results, I just showed that it was workable, and I never did anything with it or published it (this was probably 2000-ish). Everyone bootstraps their trees from clusters-of-leaves-as-billboards anyway now, and most people don't bother with smooth LOD transitions.

But it's good to see somebody actually went ahead and tackled this seriously.

[ryg]