Geometric LOD will be back, mf !!
Getting sleepy here.. I had a Melatonin pill of those bought in the USA, made to put asleep bull-sized individuals.
Someone mentioned about posting about graphics, so here is my thoughts about the coming future. Not sure when but it's coming.
First let's think about texture mapping. I remember when Deluxe Paint on the Amiga first implemented perspective projection of images was rather slow and the quality wasn't so good.
The problem was that it would take every single pixel of the source image and try to put it in perspective. This works OK if the perspective image is relatively big respect to the source image, but it's a big waste of calculations if the perspective image is actually using few of the source pixels.
Texture mapping is the same thing. Aside from a few crazy attempts (Sega Saturn and nVidia NV1), texture mapping is done by selecting a texel for each pixel that needs to be drawn (more in case of filtering, but still a fixed number related to the number of pixels).
This works in the assumption that polygons are probably going to be smaller than textures which are big enough to cope with a few bigger polygons.
The real issue is really with perspective projection, where things can get very big or very small and one must take into account this scalability.
Texture mapping is now well optimized and, in combination with mip-mapping, can handle all polygon sizes efficiently.
Enter the geometry: as we put more and more details into geometrical definitions of 3D objects the same problem of not wasting time hitting the same pixels comes up.
A very detailed model with 100,000 quads only really needs about 20,000 quads if it covers 100x200 pixels, for example.
This model will still look pretty ugly when we zoom in into some area that is supposed to be round but that doesn't look so round anymore at that distance.
So basically, we need geometric level of detail (LOD). This is something that was being pursued 10 years ago but that hasn't quite made it yet.
To scale geometry properly one probably needs filtering as it happens with texture mapping. The simplest implementation to understand this is displacement mapping, where one has a texture that can "lift" pixels by crating triangles on the fly.
This is not so easy to implement efficiently in current hardware, but I think it only makes sense... though actually calculating how many triangles one should generate (tessellate) is not trivial to do efficiently.
Still, for the time being it would be good enough if one could use texture samplers to store geometry that would scale nicely without any artifacts.
Another nice solution for geometry LOD is "texture images" from Hoppe which was pushing progressive LOD at Siggraph 97.
Geometry images imply a dense sampling around a whole genus-0 (without any holes) mesh but at the same time it doesn't require explicit primitives definition, no vertex indices, as every triangle/quad is implicit by the grid-like distribution of the texture that makes the geometry image.
mumble mumble
Ummm, I am confused
Ummm, I am confused =)
Geometry LOD is already being used in many games that have to draw open terrains. For example World of Warcraft.
There are problems with it though.
One problem is that it seems like nobody has found a perfect solution for the 'popping' that occurs in transition between different LODs.
Another is that close up the geomtry is still not detailed enough, so you can see edges on objects that are supposed to be round.
LOD in terrains is a must
LOD in terrains is a must because it would generate a lot of polygons otherwise. It's also relatively simple when compared to more complex geometry that can't really be built with random seeds.
It doesn't have to pop-up badly. One could err on the positive side and just kep drawing lots of polys. Theoretically you just need to draw more than 2x2 quads per pixel 8) ..that is still advantage, if your terrain is really very detailed, so we are talking about possibly next generation of hardware here, if not the generation after that.
As for edges showing, there, one would use normal smoothing or more generic subdivision surfaces, stuff that currently can be attempted with DX10 geometry shaders.
ole'
So then why are you saying
So then why are you saying 'Geometric LOD will be back'?
Thats what I was confused about!!
It's being used already.
Pervasive LOD
You were with me in 97 at Siggraph. We followed quite a bit of LOD sessions but things didn't quite evolve as promised.
We have good dynamic LOD for terrains/sea even vegetation, but those details are for the most part generated procedurally.
Otherwise static LOD is used for the remaining stuff.
What I'm saying is that as geometry complexity grows we'll eventually really need to use better dynamic geometric LOD, for pretty much any object. Handling complexity in screen space is the way to go because one needs no more geometry than what the display can represent with the available pixels on screen (granted that more is needed for anti-aliasing 8)
Ah I see, so its not like
Ah I see, so its not like LOD got forgotten, its just that now there will be more need for it than ever.
I guess ultimate LOD is similar to raytracing, draw a vector from eye through each pixel on the screen and find out where it intersects with geometry.
OK, maybe I am dumb because
OK, maybe I am dumb because I do not do 3D stuff, but what is the problem for geometry LOD to have a bounding box for whole object and small bounding boxes for parts of the object and precalculate them at every scene and based on that choose an object with sufficient amount of vertices?
Is there anything wrong with my thinking?
You are talking about object
You are talking about object based LOD. Kaz and I are talking about detail LOD.
For example if you want to draw a smooth looking circle at 1 meter away, you might need 100 line segments, if you draw the same circle at 10 meters, you only need 10 line segments, at 5 meters you will need 50, etc etc... How can you make this work with bounding boxes?
Because with bounding box
Because with bounding box you can know how many pixels it will create in 2D and based on that you choose the geometry level.
You can use bounding box
You can use bounding box pixel coverage to choose the geometry level, but it is not continuous like texture mapping. Unless you want to store every 'intermediate' geometry. So for something that is 100 triangles, you store 100 objects where the smallest only has one triangle.
Also sometimes it will not be accurate. For example if you have a long thin object diagonally across the screen.
Lots of objects
Well.. there is no problem, except for the fact that then you need to have many different objects at many different resolutions.
With texture mapping it's easier because you can somehow interpolate between different mip-maps. With geometry it's not so straightforward to make something that is efficient and that allows you to extrapolate many different LODs without having to precalculate and store them in the video memory.
And this is when you don't need to have round shapes, in which case you need the ability to generate polygons on demand depending on how close the camera is.. unless you want to have a really high resolution object which has been pre-smoothed, but that would be like storing a texture that has been pre-stretched 8)
Yeah ray tracing kind of
Yeah ray tracing kind of makes sense from the rendering point of view, but in the end ray tracing itself already uses some forms of geometry LOD for early ray-object hit detection. Like approximating an object to a sphere or a more defined convex shell, to eventually pick the right triangle depending on more or less advanced strictures (kd-tree, octree, etc etc).
I think a possible solution
I think a possible solution to this is to dump polygons and find another way to implicitly represent a surface. I guess this is leaning towards something ray tracing-like ... Hardware's getting to a point to where it's fast enough to generate triangles on the fly (for "backwards compatibility" with triangle rasterization). Polygons are just an explicit way to represent a surface. Slight change of topic. Whatever happened to voxels anyway ... ? 8P
Polygons y/n ?
I dunno about dumping polygons altogether. With polygons you have linear interpolations, which are really nice and simple to deal with.
Smooth surfaces are better represented by, well, smooth surfaces primitives 8) However they are generally rather complex to do in real-time.
We also have to see where artists are going. In games, Z-Brush has become more and more popular. Z-Brush seems to use some sort of (very fine) 2D mapping on surfaces. It can also export normal maps and displacement maps.
For some mostly curved surfaces it probably makes sense to use a smooth surfaces to approximate the shape plus displacement map on top. However it may not be that useful performance-wise, and also smooth surfaces may be a pain to animate.
We should in general however make a difference between what the artist works with and how we translate that into the engine. ..though that's more tools that we have to write ;)
Let the GPU do the work
I'm not (necessarily) advocating dumping polyons, but just wondering if there's a better way to represent surfaces to help reduce or eliminate the LOD problem. My line of reasoning was that the GPU is what turns this different surface representation into polys. As you know, the LOD "problem" is there because we're feeding hardware with either too many or too few polys depending on the current state of the scene. This is not related, but I was looking at this demo Noumenon over the weekend. I was a bit intrigued by how they did the "infinite 3D" zoom (you can see it from the screen shot).