March 12, 2010 at 00:35Unlimited Detail - interesting, but I have very specific doubts ...
A few days ago a video on Hacker News (and thanks ayambit for reminding them on Habr) skipped about the company Unlimited Detail , which promises to make the most modern NVidia and ATI cards useless and render scenes in billions of points on a regular processor, without 3D acceleration (!) at all. Exceeding the capabilities of modern video cards by hundreds of times (thousands, according to the authors, which I will challenge below).
If anyone has not seen:
First, just in case, about what it is, and then about the fact that I, as a programmer, have doubts that on netbooks without 3D cards they will soon play in Crysis 3 ...
(there are a lot of words and technical details)
So, being carried away by all sorts of graphics algorithms and computer vision and being fairly familiar with OpenGL - I was really interested in this. What does the video talk about? What ordinary graphics, as they are now, consist of polygons - flat surfaces. The better your card, the more polygons it can draw. But real objects are often rounded, as a result, being built from a limited set of polygons - they seem angular (examples with pots, hatches, stones and grass in the video) and although there are methods that can bypass these restrictions in a sense, they have their own problems .
One way to bypass the polygon plane constraint is parallax mapping. Developers talk about him in the video.
The problem is obvious - the edge still remains a straight line. Plus, this gives a large load (due to shader calculations) on the video card, so you won’t get involved with them.
The second option is tesselation. This is already a much more advanced method from the field of DirectX 11 (and OpenGL 3, which by the way today has adopted version 4 already) - but here the video is worth hundreds of words:
As you can see - the stones "honestly" appear on the corner. True demo (if the memory does not change) for a high-end card -GeForce 28x ... for GF100 (GeForce GTX 4x0) and ATI R800 (Radeon 5xxx) (thanks to infi for the amendment)
In general, tesselation on modern boards allows you to bypass In many ways, polygon restrictions are almost the same as Unlimited Detail (UD). This is true, the authors do not say in the video.
Okay, back to our UD. So, the authors claim that they developed a search algorithm that allowed them to render real-time scenes with billions (!) Points. It is the point cloud that is rasterized (rendered), in other words, there are no triangles, there are only many, many, many small points.
For comparison, I once tested with a modern card (8600GTS) and it was able to render only 10 million points at 24 fps. UD claims billions (!), That is, the 8600s need 100 pieces to buy. Despite the fact that the performance growth of video cards is only 22% per year (according to UD in the video), we will have to wait a long time for a similar FPS from 3D accelerators. (23 years seems to be? 1.22 ** 23 = 100)
What makes UD speed? Due to the fact that you have on the screen a total of 1024x768 = 786000 pixels. If we know which specific 3D point - which corresponds to a flat-panel monitor - then we only need 786000 * 25 = 20 million operations per second. A modern processor can do up to 3 billion. So in the municipality - perhaps on the processor. But here's the thing - so far no one has really found an algorithm to accurately calculate this minimal set of points.
In modern games, the so-called occlusion culling is used.
As you can see, when the grid is turned on, some of the houses simply disappear (not drawn). At a more advanced level, culling works at the level of literally polygons - hiding all those that will not be visible (closed by something, behind, out of sight, although the last two are slightly different and very old culling - frustum culling).
So - in fact, the authors of UD invented such an algorithm, but only for points. That is, it allows you to find the minimum number of points that you need to draw and show only them. The same occlusion culling, but at the pixel level - which one will be closed.
It would seem - there is happiness! The grass will cease to be flat, all branches will be visible, and even the sleepers will become convex.
Well, comrades, tunea ... software engineers ... let's turn on our brains now and figure out what's wrong ... (I have doubts) ...
Firstly, as the video says, NVidia and ATI do not really crave this technology. It would seem and is understandable - who will need them with cards for $ 1000 every 2 years, when everyone will play on the CPU. But on the other hand - why not buy and bury? Apparently not worried. And why?
So ... let's try to think. We need 20 million operations in order for 1024x768 to play at 25 fps. The modern percent does 3 billion operations, which means that no more than 150 lower-level commands should go to search and draw one point. Okay, let’s say rendering - this is essentially a multiplication by a 4x4 matrix and there is division there. We admit that this is possible, but we come to the search.
So, 2 billion pixels, as they say, among which you need to look for ...
We do not have any popular algorithms for compressing point clouds (as for pictures - JPG, DDS, etc.), which means that all points are stored in memory. The following is a scene in the jungle, where there are few repeating elements. 2 billion points * (4 bytes (float) * 3 coordinates + 3 colors * 1 byte (uint8)) = 30 gigabytes of RAM ... so, this obviously will not fit into our home computer ...
Well, for absolutely complete paranoia: note that the scene in the jungle (2 billion points, 30 gigabytes in theory) is very small compared to any level in the same Crysis, which once in 100 can be more. So theoretically 30 gigs can be multiplied by 100 ... or at each exit from each glade we will wait for the loading of new 30 gigs of the new glade (at a hard drive speed of 30 MB per second = 1000 seconds or 16 minutes for each clearing). :) As in the good old days of the very first games - 10 steps ... "loading ...."
What are the options? Winchesters - they are large, 30 gigabytes is not a question ... They build some kind of index and store it in memory, these 30 gigabytes are stored on the hard drive, and they are accessed as needed ... here I have questions. Any access to the Winchester (random seek) is 9ms - that is, only a hundred reads per second. That is, no more than 4 searches per frame.
And if you look at the video, then random seek (reading out of order) will be required in any way, because some “elephants” are close to the camera, others in FIG know what distance. That is, any movement a little to the left, a little to the right, and we need to read again not a very large number (maximum 768,000 points), but points scattered across a 30-gig file. If these points were all recorded in a row - there is no problem - modern home hard drives read dozens of megs per second in order, but random reading - they still have trouble ... and we only have 4 searches per frame (760 thousand points in 4 the request essentially needs to be read).
So here we come to two questions - where is it all stored and how is it reproduced ... most likely developers use machines with gig leaders operatives and all the data is in memory. But we do not have dozens of gigs.
Of course, remember to Elite Spectrum almost boundless universe into stuffed 64K andtheprodukkt Fabrausch a city in 181,000 bytes pushed ( very hitrozh .. smart way ). But something tells me that the method of procedural textures here will not particularly save the authors.
Operating time. All technologies have so far been designed for landfills. All 3D editors (with the exception of specific ones, with which I have worked, but even their names will not tell anyone) are designed for polygons. All 3d-artists think in polygons (of course, zBrush changes the game scene a bit, but all the same, initially work is with a low-poly model). All texture designers are used to working with polygon models ... all model optimization algorithms are designed for polygons ... all compression algorithms are designed for flat textures (JPG, DDS).
There is simply not enough means of processing point clouds, nor people who can draw in them, nor compression algorithms. There is shown in the video a small scene, which, aswe found outI assume the above will take (only she!) 30 gigabytes of space ... but there are no special algorithms for compressing this kind of data!
Of course, the developers say that you can take ordinary models and translate them (with textures) into a point cloud, but they admit that they have not done so yet. This may solve the problem of the lack of artists, but it will not solve the problem of compression and volume.
The developers say that “do not pay attention to the flickering shadows - this is not enough for us to map the shadow map” (in principle, we are talking about shadow mapping parameters - it’s clear here, they need to be tuned for specific scenes), but there is still a problem. In particular - almost everything that impresses you in modern games is shaders. Any highlight is the result of the shader. And for shaders, one of the main input things for him is the normal point on the surface. ( figure ) This arrow (only at every point of the triangle) is what determines how strong the “highlight” is in it. It is from her that the same displacement mapping, reflection (especially!) And the refraction of light dance.
Now the problem. At a point in a point cloud, NO NORMALY ... there is nowhere for her to draw an arrow - she's just a point. For a normal, she needs to know at least two other points with which she will form a surface (well, or the direction of the normal). Therefore, it cannot reflect, refract, shine, etc. Simply put, a real point cloud cannot even be glossy plastic (or even not perfectly matte plastic) - glare is excluded - they simply cannot be calculated. Therefore, everything that you see on the video is generally matte - no glare.
In fact, here I am lying a little - and of course, if you use the old methods of polygonal modeling - the points can have normals. But in an honest cloud of pointsthere are no normals. Normals, of course, can be, they just need to be taken from somewhere, but for this there must be triangles or polygons.
This is an example of what a point cloud is, in general, and which render Unlimited Detail. By the way, it should be noted that this explains that the details there are not "endless". It is finite, the authors had in mind that they can look for an almost unlimited size level (which, in general, is doubtful).
The retreat why shadows work somehow: With shadows everything is easier here - the scene is rendered again from the point of view of the sun (invisibly) and compares which of these points ("visible" to the sun) are visible to the observer in the camera - those that are visible are bright ( in the sun), those that are not visible - in the shade.
Of course, in the video we see a reflection (a la Quake 1 :)) in the lake. But the developers admit that they cheated and in fact the scene is double - one up, the other down. True, such a primitive effect (reflection from the plane) could be mathematically simple to calculate. Another question is the already familiar “ripple” ... here it is not so easy to calculate by the processor - time is needed for ray tracing ...
Therefore, all the cool effects such as glare, reflections - will have to be abandoned temporarily (until they figure out how to calculate the normals in real time in a point cloud) points or between points) and do all the games in cloudy weather (a la Doom, although it seems that it already had reflections ...)
Simply put, look here - here are just the first two options without normals and are possible:
Another issue is transparency . If UD is looking only for the pixel closest to the camera that will be visible - then finding which ones behind this nearest one may be a problem, not provided by the search algorithm. And that’s how transparency works - 50% of the front pixel and mix with the colors of those behind.
4. Will a
One of the main problems in the gaming industry right now is that you have to make objects that are too detailed (I am against this - give me a better fun windup game with moderate graphics than a game even more similar to real life ... if I wanted reality, I would go outside and not the game) It is because of this that tens of millions of dollars are already spent on games ... GTA4 - $ 100 million !
So, now the angles are still being cut off ... although no, on the contrary, it is precisely due to the fact that in games there are still angles in 3D models - the price is still moderate for the development of objects. But what if every game item will have to be developed in zBrush ... by the point ... detailing is reduced to millimeters ... the price of games jumps even higher ... of course, Russia does not care much, but nevertheless - this is another reason for the game industry to resist the introduction of such technologies like unlimited detail.
I completely forgot to say this too ... now video cards help developers out by leaving the percent almost free for calculating AI and physics (although the latter is also being transferred to video cards). In the event that the percent will only deal with the calculation of graphics - AI and physics will have no one to count. As well as the so-called skinning - bending a character model during animation using bones. This is also now either a CPU or a GPU. And everything will have to be on the CPU, which will already be occupied already.
So maybe for “infinite detailing” without a video card you have to pay with stupid AI and ossified players passing through the ground due to lack of processor time ...
Of course, multiprocessing can help out, but so far in the current realities - one more small clove in the foot Unlimited Detail.
All in all, the video is impressive. And I have no doubt that the authors did what they show. Perhaps corners were cut off somewhere (like 32gb operatives), but nevertheless it exists. Moreover, hackers from Hacker News have unearthed that the authors of UD are probably one of the leading developers in the world in the field of algorithms (Greg Douglas, perhaps the same as that related to the development of the R-Tree algorithm) and have published works ... but there’s something nevertheless (according to the above), I doubt that it will be allowed in the mainstream game ... (at least not in the next 16 months, as the Unlimited Detail developers promise).
But, as in any good entrepreneurial activity - the more people say that what you do is impossible, the better way (possibly) you have found.So maybe the gentlemen from UD have found how to get around all these problems and this technology can really work on laptops ... But so far, even in theory, I can’t dismiss any of them (... maybe only about normal ...) and IT -experience suggests that usually miracles do not exist.
And even more importantly, the gaming industry does not have such an incentive to adopt this technology and remake all its tools for it, retrain people and develop new algorithms for compressing and storing such data, when with the approaching level of video cards, the detail by eye is already indistinguishable from what UD offers. And visually, UD demos lose almost any modern game for 7 years.
Predicting the course of history is a thankless task; you will never guess where it will turn. I just voiced the theoretical problems that I see.
Well, time will tell ...
Yoi Haji,
view from Habr
PS It turns out Unlimited Detail found their way 2 years ago ...
If anyone has not seen:
First, just in case, about what it is, and then about the fact that I, as a programmer, have doubts that on netbooks without 3D cards they will soon play in Crysis 3 ...
(there are a lot of words and technical details)
Unlimited detail
So, being carried away by all sorts of graphics algorithms and computer vision and being fairly familiar with OpenGL - I was really interested in this. What does the video talk about? What ordinary graphics, as they are now, consist of polygons - flat surfaces. The better your card, the more polygons it can draw. But real objects are often rounded, as a result, being built from a limited set of polygons - they seem angular (examples with pots, hatches, stones and grass in the video) and although there are methods that can bypass these restrictions in a sense, they have their own problems .
Old-fashioned, using OpenGL 3 / DirectX11 methods - parallax mapping, tesselation
One way to bypass the polygon plane constraint is parallax mapping. Developers talk about him in the video.
The problem is obvious - the edge still remains a straight line. Plus, this gives a large load (due to shader calculations) on the video card, so you won’t get involved with them.
The second option is tesselation. This is already a much more advanced method from the field of DirectX 11 (and OpenGL 3, which by the way today has adopted version 4 already) - but here the video is worth hundreds of words:
As you can see - the stones "honestly" appear on the corner. True demo (if the memory does not change) for a high-end card -
In general, tesselation on modern boards allows you to bypass In many ways, polygon restrictions are almost the same as Unlimited Detail (UD). This is true, the authors do not say in the video.
What did Unlimited Detail do?
Okay, back to our UD. So, the authors claim that they developed a search algorithm that allowed them to render real-time scenes with billions (!) Points. It is the point cloud that is rasterized (rendered), in other words, there are no triangles, there are only many, many, many small points.
For comparison, I once tested with a modern card (8600GTS) and it was able to render only 10 million points at 24 fps. UD claims billions (!), That is, the 8600s need 100 pieces to buy. Despite the fact that the performance growth of video cards is only 22% per year (according to UD in the video), we will have to wait a long time for a similar FPS from 3D accelerators. (23 years seems to be? 1.22 ** 23 = 100)
What makes UD speed? Due to the fact that you have on the screen a total of 1024x768 = 786000 pixels. If we know which specific 3D point - which corresponds to a flat-panel monitor - then we only need 786000 * 25 = 20 million operations per second. A modern processor can do up to 3 billion. So in the municipality - perhaps on the processor. But here's the thing - so far no one has really found an algorithm to accurately calculate this minimal set of points.
In modern games, the so-called occlusion culling is used.
As you can see, when the grid is turned on, some of the houses simply disappear (not drawn). At a more advanced level, culling works at the level of literally polygons - hiding all those that will not be visible (closed by something, behind, out of sight, although the last two are slightly different and very old culling - frustum culling).
So - in fact, the authors of UD invented such an algorithm, but only for points. That is, it allows you to find the minimum number of points that you need to draw and show only them. The same occlusion culling, but at the pixel level - which one will be closed.
It would seem - there is happiness! The grass will cease to be flat, all branches will be visible, and even the sleepers will become convex.
Well, comrades, tunea ... software engineers ... let's turn on our brains now and figure out what's wrong ... (I have doubts) ...
Something is wrong here...
Firstly, as the video says, NVidia and ATI do not really crave this technology. It would seem and is understandable - who will need them with cards for $ 1000 every 2 years, when everyone will play on the CPU. But on the other hand - why not buy and bury? Apparently not worried. And why?
So ... let's try to think. We need 20 million operations in order for 1024x768 to play at 25 fps. The modern percent does 3 billion operations, which means that no more than 150 lower-level commands should go to search and draw one point. Okay, let’s say rendering - this is essentially a multiplication by a 4x4 matrix and there is division there. We admit that this is possible, but we come to the search.
So, 2 billion pixels, as they say, among which you need to look for ...
1. Where did you cram all this?
We do not have any popular algorithms for compressing point clouds (as for pictures - JPG, DDS, etc.), which means that all points are stored in memory. The following is a scene in the jungle, where there are few repeating elements. 2 billion points * (4 bytes (float) * 3 coordinates + 3 colors * 1 byte (uint8)) = 30 gigabytes of RAM ... so, this obviously will not fit into our home computer ...
Well, for absolutely complete paranoia: note that the scene in the jungle (2 billion points, 30 gigabytes in theory) is very small compared to any level in the same Crysis, which once in 100 can be more. So theoretically 30 gigs can be multiplied by 100 ... or at each exit from each glade we will wait for the loading of new 30 gigs of the new glade (at a hard drive speed of 30 MB per second = 1000 seconds or 16 minutes for each clearing). :) As in the good old days of the very first games - 10 steps ... "loading ...."
What are the options? Winchesters - they are large, 30 gigabytes is not a question ... They build some kind of index and store it in memory, these 30 gigabytes are stored on the hard drive, and they are accessed as needed ... here I have questions. Any access to the Winchester (random seek) is 9ms - that is, only a hundred reads per second. That is, no more than 4 searches per frame.
And if you look at the video, then random seek (reading out of order) will be required in any way, because some “elephants” are close to the camera, others in FIG know what distance. That is, any movement a little to the left, a little to the right, and we need to read again not a very large number (maximum 768,000 points), but points scattered across a 30-gig file. If these points were all recorded in a row - there is no problem - modern home hard drives read dozens of megs per second in order, but random reading - they still have trouble ... and we only have 4 searches per frame (760 thousand points in 4 the request essentially needs to be read).
So here we come to two questions - where is it all stored and how is it reproduced ... most likely developers use machines with gig leaders operatives and all the data is in memory. But we do not have dozens of gigs.
Of course, remember to Elite Spectrum almost boundless universe into stuffed 64K and
2. Operating time, 3D artists, unemployment, riots ...
Operating time. All technologies have so far been designed for landfills. All 3D editors (with the exception of specific ones, with which I have worked, but even their names will not tell anyone) are designed for polygons. All 3d-artists think in polygons (of course, zBrush changes the game scene a bit, but all the same, initially work is with a low-poly model). All texture designers are used to working with polygon models ... all model optimization algorithms are designed for polygons ... all compression algorithms are designed for flat textures (JPG, DDS).
There is simply not enough means of processing point clouds, nor people who can draw in them, nor compression algorithms. There is shown in the video a small scene, which, as
Of course, the developers say that you can take ordinary models and translate them (with textures) into a point cloud, but they admit that they have not done so yet. This may solve the problem of the lack of artists, but it will not solve the problem of compression and volume.
3. We do not need any glare and reflection, we will play Doom!
The developers say that “do not pay attention to the flickering shadows - this is not enough for us to map the shadow map” (in principle, we are talking about shadow mapping parameters - it’s clear here, they need to be tuned for specific scenes), but there is still a problem. In particular - almost everything that impresses you in modern games is shaders. Any highlight is the result of the shader. And for shaders, one of the main input things for him is the normal point on the surface. ( figure ) This arrow (only at every point of the triangle) is what determines how strong the “highlight” is in it. It is from her that the same displacement mapping, reflection (especially!) And the refraction of light dance.
Now the problem. At a point in a point cloud, NO NORMALY ... there is nowhere for her to draw an arrow - she's just a point. For a normal, she needs to know at least two other points with which she will form a surface (well, or the direction of the normal). Therefore, it cannot reflect, refract, shine, etc. Simply put, a real point cloud cannot even be glossy plastic (or even not perfectly matte plastic) - glare is excluded - they simply cannot be calculated. Therefore, everything that you see on the video is generally matte - no glare.
In fact, here I am lying a little - and of course, if you use the old methods of polygonal modeling - the points can have normals. But in an honest cloud of pointsthere are no normals. Normals, of course, can be, they just need to be taken from somewhere, but for this there must be triangles or polygons.
This is an example of what a point cloud is, in general, and which render Unlimited Detail. By the way, it should be noted that this explains that the details there are not "endless". It is finite, the authors had in mind that they can look for an almost unlimited size level (which, in general, is doubtful).
The retreat why shadows work somehow: With shadows everything is easier here - the scene is rendered again from the point of view of the sun (invisibly) and compares which of these points ("visible" to the sun) are visible to the observer in the camera - those that are visible are bright ( in the sun), those that are not visible - in the shade.
Of course, in the video we see a reflection (a la Quake 1 :)) in the lake. But the developers admit that they cheated and in fact the scene is double - one up, the other down. True, such a primitive effect (reflection from the plane) could be mathematically simple to calculate. Another question is the already familiar “ripple” ... here it is not so easy to calculate by the processor - time is needed for ray tracing ...
Therefore, all the cool effects such as glare, reflections - will have to be abandoned temporarily (until they figure out how to calculate the normals in real time in a point cloud) points or between points) and do all the games in cloudy weather (a la Doom, although it seems that it already had reflections ...)
Simply put, look here - here are just the first two options without normals and are possible:
Another issue is transparency . If UD is looking only for the pixel closest to the camera that will be visible - then finding which ones behind this nearest one may be a problem, not provided by the search algorithm. And that’s how transparency works - 50% of the front pixel and mix with the colors of those behind.
4. Will a Russian American pay $ 500 for a torre game?
One of the main problems in the gaming industry right now is that you have to make objects that are too detailed (I am against this - give me a better fun windup game with moderate graphics than a game even more similar to real life ... if I wanted reality, I would go outside and not the game) It is because of this that tens of millions of dollars are already spent on games ... GTA4 - $ 100 million !
So, now the angles are still being cut off ... although no, on the contrary, it is precisely due to the fact that in games there are still angles in 3D models - the price is still moderate for the development of objects. But what if every game item will have to be developed in zBrush ... by the point ... detailing is reduced to millimeters ... the price of games jumps even higher ... of course, Russia does not care much, but nevertheless - this is another reason for the game industry to resist the introduction of such technologies like unlimited detail.
5. AI? Physics? Bones?
I completely forgot to say this too ... now video cards help developers out by leaving the percent almost free for calculating AI and physics (although the latter is also being transferred to video cards). In the event that the percent will only deal with the calculation of graphics - AI and physics will have no one to count. As well as the so-called skinning - bending a character model during animation using bones. This is also now either a CPU or a GPU. And everything will have to be on the CPU, which will already be occupied already.
So maybe for “
Of course, multiprocessing can help out, but so far in the current realities - one more small clove in the foot Unlimited Detail.
Generally...
All in all, the video is impressive. And I have no doubt that the authors did what they show. Perhaps corners were cut off somewhere (like 32gb operatives), but nevertheless it exists. Moreover, hackers from Hacker News have unearthed that the authors of UD are probably one of the leading developers in the world in the field of algorithms (Greg Douglas, perhaps the same as that related to the development of the R-Tree algorithm) and have published works ... but there’s something nevertheless (according to the above), I doubt that it will be allowed in the mainstream game ... (at least not in the next 16 months, as the Unlimited Detail developers promise).
But, as in any good entrepreneurial activity - the more people say that what you do is impossible, the better way (possibly) you have found.So maybe the gentlemen from UD have found how to get around all these problems and this technology can really work on laptops ... But so far, even in theory, I can’t dismiss any of them (... maybe only about normal ...) and IT -experience suggests that usually miracles do not exist.
And even more importantly, the gaming industry does not have such an incentive to adopt this technology and remake all its tools for it, retrain people and develop new algorithms for compressing and storing such data, when with the approaching level of video cards, the detail by eye is already indistinguishable from what UD offers. And visually, UD demos lose almost any modern game for 7 years.
Predicting the course of history is a thankless task; you will never guess where it will turn. I just voiced the theoretical problems that I see.
Well, time will tell ...
Yoi Haji,
view from Habr
PS It turns out Unlimited Detail found their way 2 years ago ...
