Carmack is knowledgeable of 3D rendering in general, but that doesn't mean he's an expert on ray tracing specifically, and I found nothing in the article to indicate that he is. He appears to be unaware of a large body of research into the acceleration structures and optimization techniques commonly employed by modern ray tracers (Kd-trees, Bounding-interval heirarchies, MLRTA, packet tracing). He correctly claims that ray tracing is not used much by movie studios, but fails to identify one of the main reasons why this is so: ray tracing is not a memory parallel algorithm, and therefore does not perform well rendering scenes that can't fit in main memory on any one computer (citation). This isn't an issue at all for games. Carmack doesn't seem to be aware of the real drawbacks of ray-tracing either (other than a vague notion that it's "really slow", probably based on naive implementations of an algorithm that's been around for almost thirty years), such as the cost of re-building the acceleration structure when something in the scene moves. Can his sparse voxel octree data structure be updated or re-sorted quickly?
I think the parent poster was correct to call attention to the emperor's apparent lack of clothes. Just because Carmack has had a huge influence on interactive 3D gaming doesn't mean his statements should be accepted without scrutiny.
1) Right to communicate and store data using any kind of cryptography.
2) Right to communicate anonymously.
Both of these would be subject to the usual exceptions; slander, libel, copyright law, patents, search warrants, using cryptography or anonymous communication to commit a crime is still a crime, etc..
3) Government data made available to the public shall be accessible in a documented, royalty-free format.
4) Installing private communication cable between adjacent properties shall not be forbidden by local regulations (though it may be regulated to conform to reasonable best practices).
5) Municipalities may provide Internet access to private citizens or businesses, regardless of whether they are competing with local businesses.
what my enemy is: those who actually believe the usa just does evil things. that's not what you are saying, so i have no argument with you on that point
I'm not defending the United States when I say they have good intentions. There have been many atrocities committed with good intentions. I think our foreign policy towards Cuba is guided by, perhaps, one part good intentions (we want them to be a democracy, as long as they make all the "right" decisions), two parts pride (we'd like to forget the whole humiliating bay of pigs thing), two parts revenge (for nationalizing the property of US corporations), and three parts stubbornness (if we stop our embargo, it's an admission that we were wrong all along).
the bad usa policy towards cuba does not make cuba. cuba makes the bad usa policy. castro did not turn his country into an authoritarian dictatorship because the usa doesn't want to trade with it, the usa doesn't want to trade with it because cuba is an authoritarian dictatorship
for the life of me, i can't fathom in a million years how otherwise intelligent people like yourself can get this cause and effect reversed!
Cuba, of course, is at least as responsible for their own government as the United States is for perpetuating things. But, we in the United States can't change Cuba directly (nor can we change the past), we can only change our own foreign policy towards Cuba. As for the causality, my understanding of Cuban history isn't very good, so I'll defer to the other reply to your post, which is written by someone with (perhaps) more understanding than I.
my problem is with the kind of thinking, utterly beyond my grasp, of saying because the usa is hostile towards castro, or iran, and iran or cuba tightens their grip, THAT THEREFORE THE USA IS REPONSIBLE FOR WHAT THOSE GOVERNMENTS DO
I don't think it's a coincidence that many of the countries we don't currently get along with (and generally label "evil", perhaps not incorrectly), are countries that we've interfered with in self-serving ways in the past. (It's funny you mention Iran...) I think we ought to accept our share of the blame for that. Not more than our share, but not less either.
but in your effort to hate and prosecute the usa, how do you get anywhere in that passion of yours by forgiving regimes which, right now, in the PRESENT TIME, are doing clearly worse than the usa, ON THE SUBJECT MATTER YOU SAY IS IMPORTANT, such as freedom of expression?
The United States obviously treats its citizens much better than Cuba treats its citizens in terms of freedom of expression, press, etc.. However, that isn't the only measure of the "goodness" or "evilness" of a nation, one must also look at how that nation treats other nations; we don't have such a good track record in that area. (We have good intentions, perhaps, but bad foreign policy is always based on (or justified by) good intentions.)
In the case of Cuba, we are embargoing the country because we think their leadership is evil and threatening, under the notion that maybe economic pressure will encourage the poor to rise up against their evil regime and inspire a new era of freedom and democracy. This has been tried many times in many contexts, and I'm not aware of a case in which it has actually worked. The poor are not deceived; they know that we're the ones actively trying to starve them, and that just makes their authoritarian government more popular. Authoritarian governments thrive on outside threats; it gives them something to point to, to frighten the population into supporting their "benevolent protector".
Simply comparing the United States to Cuba and saying "we're better than them because we have more freedom" is a little simplistic. One must also consider the role the United States has played in making Cuba what it is.
The problem is that the scanline rendering techniques we use for real-time graphics these aren't an accurate solution to the rendering equation. If you add more processing power you can render more triangles at higher framerates, but there isn't a physically-correct way to deal with the interreflections between objects (i.e. global illumination), and so the output of scanline rendering will never look quite real (it might look pretty close, but only with a lot of manual tweaking).
Plain Whitted Ray tracing doesn't solve the rendering equation either, but many global illumination algorithms employ ray tracing. Photon mapping, for instance, traces rays from the light source, which can then bounce off of objects in the scene, and their hit locations get stored in a data structure. The density of "hits" near any particular location in the scene tells you how much ambient light is there.
It turns out, ray tracing with photon mapping is a pretty good approximation to the rendering equation. The error manifests as noise, which can be reduced by increasing the number of photons. In other words, as you increase the amount of computational capability, a photon mapped image will asymtotically approach realism, whereas a scanline scene will asymtotically approach something that doesn't quite look real.
There is also the argument that ray tracing is O(log N) with scene complexity versus scanline rendering which is O(N). It gets a little more complicated than this when you're dealing with dynamic scenes, but there are cases where ray tracing really is faster.
...getting a "perfect", physically correct result is just not a process that scales well. (Check out The Rendering Equation on wikipedia or somewhere else if you're interested; there's a integral over the hemisphere in there that has to be evaluated, which can recursively turn into a multi-dimension integral over many hemispheres. Without cheating, the evaluation of that thing is going to kick Moore's law's ass for a long, long time.)
Photon mapping is a pretty good way of getting an unbiased approximation to the rendering equation. It's slower than plain ray tracing, but much faster than path tracing. Real-time interactive global illumination isn't as computationally intractable as you are implying; it is likely to follow real-time ray tracing in not too many years.
It's worth pointing out (and it's mentioned in the paper you cite) that the main reason Pixar hasn't been doing much ray tracing until now is not performance or realism, but memory requirements. They need to render scenes that are too complex to fit in a single computer's memory. Scanline rendering is a memory-parallel algorithm, ray tracing is not. So, they're forced to split the scene up into manageable chunks and render them separately with scanline algorithms.
This isn't an issue for games, which are going to be run on a single machine (perhaps with multiple cores, but they share memory).
Designing a game that is fun is hard, I don't deny that. And if you change any of the basic game mechanics people are used to, a lot of players won't like it. (Designing Virtual World by Richard Bartle is a very good book on the subject of the various trade-offs of virtual world design.)
I suppose if you mess with the whole levels/classes/killing stuff for XP/quests formula of the modern MMORPG, it's more likely that you'll end up with a game that sucks than a game that's awesome, and the (extremely risk averse) game studios know this, so I expect it'll take a long time to get out of the current rut.
One of the things I liked about the Lord of the Rings books was that it wasn't all high fantasy all the time; as often as not, the characters were worried about where they'd find the next food or water, or how were they going to get out of the pouring rain, rather than trying not to get killed by orcs and goblins. I wish they'd managed to include that aspect (but of course they'd have to do it in a way that's fun and interesting, not another monotonous chore).
the problem is, a lot of these things are not "fun"
True, but that's where the design challenge is. Eating and sleeping, for instance, aren't much fun. Eating could be made automatic, though. Say, you have a certain supply of food in your inventory, and it diminishes over time. So, the need for food could be an aspect of gameplay without become intrusive (unless you run out). Sleeping can happen when you're logged out, but it requires shelter. WOW models this as accruing rest experience when you're in an inn (including when you're logged out), but you don't really need shelter; something that's a basic survival need is optional in WOW. Nor is it necessary to dress appropriately for the weather. Players jump into rivers and swim across in the middle of winter because they're too lazy to walk around. If you did that in real life, you'd likely die of hypothermia. (In the summer it might be refreshing.) I suppose what I really want is a fundamentally different kind of game, where the designers don't always take the easy way out. It don't expect it to be written any time soon, but it doesn't hurt to advocate for more interesting gameplay.
a world that never changes
on
The Future of MMOs
·
· Score: 4, Insightful
I think one of the fundamental problems with MMORPGs is that the world never changes. Cities are never overrun and burned to the ground, quest givers never die (or if they do, they respawn quickly), trees never grow, the seasons never change, even things like weather and time of day are mostly cosmetic and don't impact gameplay much if at all. Monsters always spawn in the same places and if you kill them all, they'll be back in ten minutes. The modern MMORPG, it would seem, was designed with Sisyphus as the target audience.
A related problem is that too much is abstracted away; players and NPCs don't need to eat, they don't need shelter, items spawn magically in the vendor's shop and money spent disappears into a black hole. Animals spawn, they aren't born in the natural way. Species can't become extinct by killing the last breeding pair. A town does not trade with the outside world, it does not suffer if it is besieged, and there are no famines if the year's harvest is poor. The terrain can't be altered.
Designing a mmorpg around a realistic world would be much harder than the current crop; it may be too much to ask for a MMORPG to be able to support any of the events of the preceding paragraph, but couldn't the world be at least slightly interactive? Like, maybe we could plant a tree every once in awhile and watch it grow, or maybe the grass could be worn down by the passage of many feet? I've played WOW and I'm currently playing Lord of the Rings Online, and I just don't feel like I'm part of the world. It feels more like an amusement park.
The questing/leveling/grinding rut is a big problem too, I'm not disagreeing with you there, but it would take a book for me to say what I want to say about that.
I think this is a better (less biased) illustration of a lapse in basic ethics. I don't claim to know much about him or what he really truly believes, but I don't think that anyone who claims to be opposed to torture but is unwilling to identify waterboarding as torture (when it clearly is) ought to be president.
A friend of a friend of mine got dengue in Indonesia. I was there after he had gotten over it, but from second-hand accounts it didn't sound like much fun. I think he had a mild form, where he ran a horrendous fever for about a week, and then had a full-body painful rash for about a week, and then had some serious depression for a few months until he figured out that you can take pills to counteract the neurological aftereffects (which I hear tend to last about a year). I'm not sure if he had to be hooked up to an IV during the fever, but I hear that's common practice.
I don't know what the right solution is, but I'm glad people are working on it.
In fact, his points actually show why a hybrid is perfect: most surfaces are not shiny, refractive, a portal, etc. Most are opaque - and a rasterizer is much better for this (since no ray intersection tests are necessary).
Actually, primary rays are quite a bit cheaper for a raytracer to compute than secondary rays (reflections, shadows). There are ways to exploit the coherency and do far less work (packet tracing and MLRTA, for instance). In a hybrid scheme, the graphics hardware would only be unloading the easiest portion of the workload.
The point the article was trying to make is that if your ray tracer is fast enough to ray-trace the entire screen, there's no compelling reason to even use rasterization; the ray tracer is going to be fast enough to do that by itself, too. Hybrid schemes might make sense if ray-tracing is too slow to render the whole screen at a decent framerate (basically, where we're at today), but in a few years that will very likely no longer be the case.
Take the best of both worlds, and go hybrid, just like the major CGI studios did.
The reason the movie studios don't use raytracing more often is that raytracing is not memory-parallel, and they need to be able to render scenes that can't fit in the memory of any one computer. Here is some info on how Pixar used ray-tracing in the movie Cars.
The problem is that computing these trees is expensive, and any change to the location of triangles inside the tree means recomputing the entire partition tree.
This isn't entirely true; it is quite possible to build an acceleration structure that contains not triangles but other acceleration structures. For instance, you might have a top-level kd-tree that holds a hundred other kd-trees, where each of those other kd-trees is the pile of triangles representing some movable object in the scene. If one of those objects moves, you only have to recompute the top-level tree, and (if the object's geometry has deformed as well), the tree of that thing that moved. You definitely do not have to recompute everything just because one triangle moved.
Also, we now have BIH trees (link to the paper is here); these can be re-sorted much more quickly than kd-trees (the current favorite for static scenes). They use a fast in-place sort very much like quicksort. Dynamic scenes can be a bottleneck in certain cases (a million swirling snowflakes, for instance), but in the general case it's not a show-stopper.
Everybody has rasterizing GPUs, while nobody has special hardware for raytracing and won't have anytime soon.
It isn't clear that we'll need specialized hardware. A general-purpose multicore CPU will do just fine, if it's fast enough. Maybe we'll have hardware raytracing accelerators at some point, but not right away. A software-only rendering engine would be pretty compelling to game designers; no weird hardware inconsistencies, and the rendering engine can be customized for the specific application. No more "sorry, that feature doesn't work on that one video card that a million people bought three years ago."
All the talk about how it doesn't work so well for dynamic scenes might not have sounded so bad 10 years ago, but today where physics engines are everywhere that sounds pretty problematic.
You may be right there that dynamic scenes are a stumbling block, but I expect the physics engines have to deal with a lot of the same problems. If both the physics engine and the rendering engine can use the same data structures, that saves a lot of memory and overhead. See my other post on how ray tracers deal with dynamic scenes. It's an active area of research right now, but as long as you aren't trying to simulate a million independently-moving snowflakes or something like that, using a top-level BIH tree and then treating all the animated objects as separate sub-trees is a reasonable way to go.
...it would be nice to have a realistic game with millions of polygons where each and every tiny detail is modeled, like this Boeing 777 model with 350mil polygons, but then who would ever have the time and money to build that for a game?
Actually, it's making your models simple enough to render quickly that's the hard part; if you don't have to care how many triangles you throw at the renderer, it makes development that much easier. (Memory will still be a limiting factor, but if you can use regular RAM instead of video card memory, there's a bit more room to work.)
A caveat of the oft-quoted O(log n) number: It's only true for static geometry. The data structure used is the k-tree, and was really intended for off-line rendering. It takes a long time to build it.
You're right, that's a point that a lot of people don't realize; acceleration structure can take a long time to build. However, kd-trees aren't the fastest trees to build; BIH trees can be built much faster. They're both nlogn, but the BIH tree construction algorithm is an in-place sort and uses a predictable amount of memory (it's actually remarkably similar to quicksort). BIH is usually a bit slower to use when you're actually tracing the scene (maybe ~%70 performance of kd-tree depending on scene and implementation), but they can be constructed maybe a couple orders of magnitude faster. (A link to that paper and others can be found here.)
The big difference between the two approaches is that KD-trees are a spacial subdivision, and any objects on both sides of the split plane are referenced from both sides of the tree; BIH is an object subdivision scheme: objects are never duplicated, but the space occupied by both sides of a branch may overlap.
It's possible to get around some of the animation problems by having a top-level BIH tree, that contains a bunch of separate trees, one for each movable object and one for the static scene. (That won't work very well for scenes with a million snowflakes blowing in all directions, but it should be okay for most games.)
Higher polygon counts, sure nice to have, but again not really all that important...
This is a rather good point; at some point, adding more polygons doesn't do anything to make an unrealistic scene look more realistic. This is true for raytracing and polygon rendering alike. Ray tracing has some advantages here, for what it's worth; it scales better with huge scenes, and it can represent non-triangular primitives natively (though all the fast ray-tracers I've seen only deal with triangles). I wouldn't call reflection a non-issue; currently, no one cares because current implementations aren't very good, and there aren't any better alternatives to compare with. Same with refraction. Ray-tracing can do soft shadows, but they're computationally more expensive (at least, all the approaches I know are).
Ray tracing is just the next step towards realism. Once we start doing ray tracing, we can move on to global illumination. Photon mapping is a GI algorithm that works like ray tracing in reverse; it casts rays out from the light source, and then they can bounce of off or be absorbed by the objects they hit (depending on surface properties), and their final location is stored as a point in a data structure called a photon map. Then, when you ray trace, you use the local density of the photon map to approximate the amount of light. Photon mapping can be used to simulate ambient light, caustics (patches of light reflected off of or refracted by shiny things), and subsurface scattering in a way that is physically correct and unbiased. See "The Light of Mies van der Rohe" animation on this page for an example of ambient light, or here for some images of caustics.
Ray tracers can do all the things that polygon renderers can do, plus a bit more. Once the hardware gets fast enough (and it looks like that will happen within a few years), there's no real reason not to use ray tracing. Photon mapping is more expensive (there's an nlogn sort involved in constructing the photon map), so it will probably be quite a while before we start to see real-time global illumination updates, but that's the next big step, and we can't go from here to there with the polygon rendering algorithms we're using now.
Is it just me or do in-game raytracing folks seems to miss a rather dirty point?
You're kind of missing the point; yes, the ray-tracing crowd already knows that ray-tracing is slow, though it's not as slow as public perception (influenced by non-realtime renders like Pov-RAY) would have you believe. What the ray-tracing crowd sees (and they have been seeing this from a long ways off) is where the computational complexity lines cross, where it suddenly becomes cheaper to use ray tracing. Sure, ray tracing on modern hardware is pretty slow; maybe my (several year old) dual-core AMD64 3800 could be made to render ray-traced graphics comparable to an N-64 rather than a Wii, but the great thing about ray tracers is that they don't slow down much when you throw more geometry at them. Rendering a scene with a million triangles only takes twice as long as rendering a scene with a thousand. Once hardware is fast enough to do low-complexity scenes at a good resolution and framerate, it takes only a very small hardware improvement to render extremely high-complexity scenes. The real limitations soon become "how many triangles can we squeeze into physical memory on one machine?" and "how fast is the memory bus?", not "gosh, I wish these ray-intersection tests were faster."
Keep in mind that a 96x performance improvement sounds like a lot, but that's only about ten years if Moore's law holds, and the article points out that Intel already has demos running at 90fps at HD resolutions. (I haven't seen them myself, so I don't know if they're rendering complex scenes with shadow rays and textures or what, but a current quad core processor ought to be able to do complex scenes at quite a bit better than 256x256@15fps, with a well-written renderer. (Not mine; I would be thrilled if it was that fast.)
There are, certainly, some performance issues that need to be worked around; rebuilding an acceleration structure when something moves is expensive (BIH trees are better at this than KD-trees, but they're still O(nlogn)), so more care must be taken to treat static and dynamic parts of the scene differently. Lots of lights can bog a scene down, and certain shapes of scenes are worse than others. Mixing large and small triangles is bad for BIH trees. These are all things that have to be understood in order to make a fast game, at least until the hardware gets fast enough that no one cares about framerates anymore.
I expect maybe we'll see some sort of raytraced game on par with tuxracer this year, and a real high-budget game maybe in one or two years, and then ray tracing will be mainstream in about five, when the average person will have a fast-enough machine to handle it.
50 GB seems reasonable, but I would have to agree with you that a 16kbps cap sounds dracconian. (It's still much better than being completely disconnected, though.) I assume you mean 2 kilobytes per second, not four; at that rate, you could only download a little over 5 GB in the whole month; it sounds like they're trying to punish heavy users painfully, rather than enforce reasonable rate limits; they could more reasonably set the initial cap lower at 40 GB, but set the capped speed at 56kbps, which would at least be halfway usable for the capped users, but a saturated connection would still only transfer about 59 GB per month. (40GB + ((56*60*60*24*31)/8)KB = 40GB + 18.7488GB)
$150 is excessive, I agree. Sounds like a monopoly is involved.
I read that recently as well. Good discussion of the implications of augmented reality, though I think some of his other books were better stories.
For another depiction of AR, I recommend Dennou Coil, a 24 episode anime set in a not-too-distant future, where AR is commonplace and there is a second-life type virtual world overlayed on top of the real world. (It's been fansubbed, but not officially released in English.)
I agree that it would be better for networks to expand capacity than to rate-limit their users, but the current state of things is that Internet access is a scarce resource that ought to be allocated fairly. Bandwidth caps aren't perfect; as you pointed out, avoiding peak hours is important as well, but it would prevent users from running bittorrent cliens 24/7 (which tend to eat up an unfair portion of the bandwith, as they use many TCP connections instead of one).
It would be great if applications like bittorrent could be made to use only the idle network capacity. I read a paper awhile back about the merits and implementation details of having a deliberately less aggressive TCP algorithm; of course, users currently have no incentive to use that sort of thing, and ISPs might have a hard time discriminating between customers based on the fairness of their congestion control algorithms.
It was a number I chose arbitrarily; substitute 2GB or 200GB if you like. I expect the median value of bandwidth usage is far below 20GB per month. Heavy users might find that too low, but they can buy service plans with higher limits with a higher per-month fee. I would much rather have ISPs state their bandwidth caps publicly and let customers decide if they're reasonable, than to randomly disconnect customers who "use too much", or for ISPs to start filtering or rate limiting specific applications or web sites.
Slashdot Mirror
Carmack is knowledgeable of 3D rendering in general, but that doesn't mean he's an expert on ray tracing specifically, and I found nothing in the article to indicate that he is. He appears to be unaware of a large body of research into the acceleration structures and optimization techniques commonly employed by modern ray tracers (Kd-trees, Bounding-interval heirarchies, MLRTA, packet tracing). He correctly claims that ray tracing is not used much by movie studios, but fails to identify one of the main reasons why this is so: ray tracing is not a memory parallel algorithm, and therefore does not perform well rendering scenes that can't fit in main memory on any one computer (citation). This isn't an issue at all for games. Carmack doesn't seem to be aware of the real drawbacks of ray-tracing either (other than a vague notion that it's "really slow", probably based on naive implementations of an algorithm that's been around for almost thirty years), such as the cost of re-building the acceleration structure when something in the scene moves. Can his sparse voxel octree data structure be updated or re-sorted quickly?
I think the parent poster was correct to call attention to the emperor's apparent lack of clothes. Just because Carmack has had a huge influence on interactive 3D gaming doesn't mean his statements should be accepted without scrutiny.
1) Right to communicate and store data using any kind of cryptography.
2) Right to communicate anonymously.
Both of these would be subject to the usual exceptions; slander, libel, copyright law, patents, search warrants, using cryptography or anonymous communication to commit a crime is still a crime, etc..
3) Government data made available to the public shall be accessible in a documented, royalty-free format.
4) Installing private communication cable between adjacent properties shall not be forbidden by local regulations (though it may be regulated to conform to reasonable best practices).
5) Municipalities may provide Internet access to private citizens or businesses, regardless of whether they are competing with local businesses.
I'm not defending the United States when I say they have good intentions. There have been many atrocities committed with good intentions. I think our foreign policy towards Cuba is guided by, perhaps, one part good intentions (we want them to be a democracy, as long as they make all the "right" decisions), two parts pride (we'd like to forget the whole humiliating bay of pigs thing), two parts revenge (for nationalizing the property of US corporations), and three parts stubbornness (if we stop our embargo, it's an admission that we were wrong all along).
Cuba, of course, is at least as responsible for their own government as the United States is for perpetuating things. But, we in the United States can't change Cuba directly (nor can we change the past), we can only change our own foreign policy towards Cuba. As for the causality, my understanding of Cuban history isn't very good, so I'll defer to the other reply to your post, which is written by someone with (perhaps) more understanding than I.
I don't think it's a coincidence that many of the countries we don't currently get along with (and generally label "evil", perhaps not incorrectly), are countries that we've interfered with in self-serving ways in the past. (It's funny you mention Iran...) I think we ought to accept our share of the blame for that. Not more than our share, but not less either.The United States obviously treats its citizens much better than Cuba treats its citizens in terms of freedom of expression, press, etc.. However, that isn't the only measure of the "goodness" or "evilness" of a nation, one must also look at how that nation treats other nations; we don't have such a good track record in that area. (We have good intentions, perhaps, but bad foreign policy is always based on (or justified by) good intentions.)
In the case of Cuba, we are embargoing the country because we think their leadership is evil and threatening, under the notion that maybe economic pressure will encourage the poor to rise up against their evil regime and inspire a new era of freedom and democracy. This has been tried many times in many contexts, and I'm not aware of a case in which it has actually worked. The poor are not deceived; they know that we're the ones actively trying to starve them, and that just makes their authoritarian government more popular. Authoritarian governments thrive on outside threats; it gives them something to point to, to frighten the population into supporting their "benevolent protector".
Simply comparing the United States to Cuba and saying "we're better than them because we have more freedom" is a little simplistic. One must also consider the role the United States has played in making Cuba what it is.
The problem is that the scanline rendering techniques we use for real-time graphics these aren't an accurate solution to the rendering equation. If you add more processing power you can render more triangles at higher framerates, but there isn't a physically-correct way to deal with the interreflections between objects (i.e. global illumination), and so the output of scanline rendering will never look quite real (it might look pretty close, but only with a lot of manual tweaking).
Plain Whitted Ray tracing doesn't solve the rendering equation either, but many global illumination algorithms employ ray tracing. Photon mapping, for instance, traces rays from the light source, which can then bounce off of objects in the scene, and their hit locations get stored in a data structure. The density of "hits" near any particular location in the scene tells you how much ambient light is there.
It turns out, ray tracing with photon mapping is a pretty good approximation to the rendering equation. The error manifests as noise, which can be reduced by increasing the number of photons. In other words, as you increase the amount of computational capability, a photon mapped image will asymtotically approach realism, whereas a scanline scene will asymtotically approach something that doesn't quite look real.
There is also the argument that ray tracing is O(log N) with scene complexity versus scanline rendering which is O(N). It gets a little more complicated than this when you're dealing with dynamic scenes, but there are cases where ray tracing really is faster.
Photon mapping is a pretty good way of getting an unbiased approximation to the rendering equation. It's slower than plain ray tracing, but much faster than path tracing. Real-time interactive global illumination isn't as computationally intractable as you are implying; it is likely to follow real-time ray tracing in not too many years.
It's worth pointing out (and it's mentioned in the paper you cite) that the main reason Pixar hasn't been doing much ray tracing until now is not performance or realism, but memory requirements. They need to render scenes that are too complex to fit in a single computer's memory. Scanline rendering is a memory-parallel algorithm, ray tracing is not. So, they're forced to split the scene up into manageable chunks and render them separately with scanline algorithms.
This isn't an issue for games, which are going to be run on a single machine (perhaps with multiple cores, but they share memory).
There are a bunch of different ones discussed on this forum. Arauna and Radius are two. There's also mine, but it's neither fast nor featureful.
Designing a game that is fun is hard, I don't deny that. And if you change any of the basic game mechanics people are used to, a lot of players won't like it. (Designing Virtual World by Richard Bartle is a very good book on the subject of the various trade-offs of virtual world design.)
I suppose if you mess with the whole levels/classes/killing stuff for XP/quests formula of the modern MMORPG, it's more likely that you'll end up with a game that sucks than a game that's awesome, and the (extremely risk averse) game studios know this, so I expect it'll take a long time to get out of the current rut.
One of the things I liked about the Lord of the Rings books was that it wasn't all high fantasy all the time; as often as not, the characters were worried about where they'd find the next food or water, or how were they going to get out of the pouring rain, rather than trying not to get killed by orcs and goblins. I wish they'd managed to include that aspect (but of course they'd have to do it in a way that's fun and interesting, not another monotonous chore).
True, but that's where the design challenge is. Eating and sleeping, for instance, aren't much fun. Eating could be made automatic, though. Say, you have a certain supply of food in your inventory, and it diminishes over time. So, the need for food could be an aspect of gameplay without become intrusive (unless you run out). Sleeping can happen when you're logged out, but it requires shelter. WOW models this as accruing rest experience when you're in an inn (including when you're logged out), but you don't really need shelter; something that's a basic survival need is optional in WOW. Nor is it necessary to dress appropriately for the weather. Players jump into rivers and swim across in the middle of winter because they're too lazy to walk around. If you did that in real life, you'd likely die of hypothermia. (In the summer it might be refreshing.) I suppose what I really want is a fundamentally different kind of game, where the designers don't always take the easy way out. It don't expect it to be written any time soon, but it doesn't hurt to advocate for more interesting gameplay.
I think one of the fundamental problems with MMORPGs is that the world never changes. Cities are never overrun and burned to the ground, quest givers never die (or if they do, they respawn quickly), trees never grow, the seasons never change, even things like weather and time of day are mostly cosmetic and don't impact gameplay much if at all. Monsters always spawn in the same places and if you kill them all, they'll be back in ten minutes. The modern MMORPG, it would seem, was designed with Sisyphus as the target audience.
A related problem is that too much is abstracted away; players and NPCs don't need to eat, they don't need shelter, items spawn magically in the vendor's shop and money spent disappears into a black hole. Animals spawn, they aren't born in the natural way. Species can't become extinct by killing the last breeding pair. A town does not trade with the outside world, it does not suffer if it is besieged, and there are no famines if the year's harvest is poor. The terrain can't be altered.
Designing a mmorpg around a realistic world would be much harder than the current crop; it may be too much to ask for a MMORPG to be able to support any of the events of the preceding paragraph, but couldn't the world be at least slightly interactive? Like, maybe we could plant a tree every once in awhile and watch it grow, or maybe the grass could be worn down by the passage of many feet? I've played WOW and I'm currently playing Lord of the Rings Online, and I just don't feel like I'm part of the world. It feels more like an amusement park.
The questing/leveling/grinding rut is a big problem too, I'm not disagreeing with you there, but it would take a book for me to say what I want to say about that.
I think this is a better (less biased) illustration of a lapse in basic ethics. I don't claim to know much about him or what he really truly believes, but I don't think that anyone who claims to be opposed to torture but is unwilling to identify waterboarding as torture (when it clearly is) ought to be president.
A friend of a friend of mine got dengue in Indonesia. I was there after he had gotten over it, but from second-hand accounts it didn't sound like much fun. I think he had a mild form, where he ran a horrendous fever for about a week, and then had a full-body painful rash for about a week, and then had some serious depression for a few months until he figured out that you can take pills to counteract the neurological aftereffects (which I hear tend to last about a year). I'm not sure if he had to be hooked up to an IV during the fever, but I hear that's common practice.
I don't know what the right solution is, but I'm glad people are working on it.
I recommend Chad Vader, day shift manager. There's 8 episodes each about 5 minutes long.
Here is an (in my opinion) intelligent and well-informed rebuttal to the article you linked to that I came across today.
Actually, primary rays are quite a bit cheaper for a raytracer to compute than secondary rays (reflections, shadows). There are ways to exploit the coherency and do far less work (packet tracing and MLRTA, for instance). In a hybrid scheme, the graphics hardware would only be unloading the easiest portion of the workload.
The point the article was trying to make is that if your ray tracer is fast enough to ray-trace the entire screen, there's no compelling reason to even use rasterization; the ray tracer is going to be fast enough to do that by itself, too. Hybrid schemes might make sense if ray-tracing is too slow to render the whole screen at a decent framerate (basically, where we're at today), but in a few years that will very likely no longer be the case.
The reason the movie studios don't use raytracing more often is that raytracing is not memory-parallel, and they need to be able to render scenes that can't fit in the memory of any one computer. Here is some info on how Pixar used ray-tracing in the movie Cars.
This isn't entirely true; it is quite possible to build an acceleration structure that contains not triangles but other acceleration structures. For instance, you might have a top-level kd-tree that holds a hundred other kd-trees, where each of those other kd-trees is the pile of triangles representing some movable object in the scene. If one of those objects moves, you only have to recompute the top-level tree, and (if the object's geometry has deformed as well), the tree of that thing that moved. You definitely do not have to recompute everything just because one triangle moved.
Also, we now have BIH trees (link to the paper is here); these can be re-sorted much more quickly than kd-trees (the current favorite for static scenes). They use a fast in-place sort very much like quicksort. Dynamic scenes can be a bottleneck in certain cases (a million swirling snowflakes, for instance), but in the general case it's not a show-stopper.
It isn't clear that we'll need specialized hardware. A general-purpose multicore CPU will do just fine, if it's fast enough. Maybe we'll have hardware raytracing accelerators at some point, but not right away. A software-only rendering engine would be pretty compelling to game designers; no weird hardware inconsistencies, and the rendering engine can be customized for the specific application. No more "sorry, that feature doesn't work on that one video card that a million people bought three years ago."
You may be right there that dynamic scenes are a stumbling block, but I expect the physics engines have to deal with a lot of the same problems. If both the physics engine and the rendering engine can use the same data structures, that saves a lot of memory and overhead. See my other post on how ray tracers deal with dynamic scenes. It's an active area of research right now, but as long as you aren't trying to simulate a million independently-moving snowflakes or something like that, using a top-level BIH tree and then treating all the animated objects as separate sub-trees is a reasonable way to go.
Actually, it's making your models simple enough to render quickly that's the hard part; if you don't have to care how many triangles you throw at the renderer, it makes development that much easier. (Memory will still be a limiting factor, but if you can use regular RAM instead of video card memory, there's a bit more room to work.)You're right, that's a point that a lot of people don't realize; acceleration structure can take a long time to build. However, kd-trees aren't the fastest trees to build; BIH trees can be built much faster. They're both nlogn, but the BIH tree construction algorithm is an in-place sort and uses a predictable amount of memory (it's actually remarkably similar to quicksort). BIH is usually a bit slower to use when you're actually tracing the scene (maybe ~%70 performance of kd-tree depending on scene and implementation), but they can be constructed maybe a couple orders of magnitude faster. (A link to that paper and others can be found here.)
The big difference between the two approaches is that KD-trees are a spacial subdivision, and any objects on both sides of the split plane are referenced from both sides of the tree; BIH is an object subdivision scheme: objects are never duplicated, but the space occupied by both sides of a branch may overlap.
It's possible to get around some of the animation problems by having a top-level BIH tree, that contains a bunch of separate trees, one for each movable object and one for the static scene. (That won't work very well for scenes with a million snowflakes blowing in all directions, but it should be okay for most games.)
This is a rather good point; at some point, adding more polygons doesn't do anything to make an unrealistic scene look more realistic. This is true for raytracing and polygon rendering alike. Ray tracing has some advantages here, for what it's worth; it scales better with huge scenes, and it can represent non-triangular primitives natively (though all the fast ray-tracers I've seen only deal with triangles). I wouldn't call reflection a non-issue; currently, no one cares because current implementations aren't very good, and there aren't any better alternatives to compare with. Same with refraction. Ray-tracing can do soft shadows, but they're computationally more expensive (at least, all the approaches I know are).
Ray tracing is just the next step towards realism. Once we start doing ray tracing, we can move on to global illumination. Photon mapping is a GI algorithm that works like ray tracing in reverse; it casts rays out from the light source, and then they can bounce of off or be absorbed by the objects they hit (depending on surface properties), and their final location is stored as a point in a data structure called a photon map. Then, when you ray trace, you use the local density of the photon map to approximate the amount of light. Photon mapping can be used to simulate ambient light, caustics (patches of light reflected off of or refracted by shiny things), and subsurface scattering in a way that is physically correct and unbiased. See "The Light of Mies van der Rohe" animation on this page for an example of ambient light, or here for some images of caustics.
Ray tracers can do all the things that polygon renderers can do, plus a bit more. Once the hardware gets fast enough (and it looks like that will happen within a few years), there's no real reason not to use ray tracing. Photon mapping is more expensive (there's an nlogn sort involved in constructing the photon map), so it will probably be quite a while before we start to see real-time global illumination updates, but that's the next big step, and we can't go from here to there with the polygon rendering algorithms we're using now.
You're kind of missing the point; yes, the ray-tracing crowd already knows that ray-tracing is slow, though it's not as slow as public perception (influenced by non-realtime renders like Pov-RAY) would have you believe. What the ray-tracing crowd sees (and they have been seeing this from a long ways off) is where the computational complexity lines cross, where it suddenly becomes cheaper to use ray tracing. Sure, ray tracing on modern hardware is pretty slow; maybe my (several year old) dual-core AMD64 3800 could be made to render ray-traced graphics comparable to an N-64 rather than a Wii, but the great thing about ray tracers is that they don't slow down much when you throw more geometry at them. Rendering a scene with a million triangles only takes twice as long as rendering a scene with a thousand. Once hardware is fast enough to do low-complexity scenes at a good resolution and framerate, it takes only a very small hardware improvement to render extremely high-complexity scenes. The real limitations soon become "how many triangles can we squeeze into physical memory on one machine?" and "how fast is the memory bus?", not "gosh, I wish these ray-intersection tests were faster."
Keep in mind that a 96x performance improvement sounds like a lot, but that's only about ten years if Moore's law holds, and the article points out that Intel already has demos running at 90fps at HD resolutions. (I haven't seen them myself, so I don't know if they're rendering complex scenes with shadow rays and textures or what, but a current quad core processor ought to be able to do complex scenes at quite a bit better than 256x256@15fps, with a well-written renderer. (Not mine; I would be thrilled if it was that fast.)
There are, certainly, some performance issues that need to be worked around; rebuilding an acceleration structure when something moves is expensive (BIH trees are better at this than KD-trees, but they're still O(nlogn)), so more care must be taken to treat static and dynamic parts of the scene differently. Lots of lights can bog a scene down, and certain shapes of scenes are worse than others. Mixing large and small triangles is bad for BIH trees. These are all things that have to be understood in order to make a fast game, at least until the hardware gets fast enough that no one cares about framerates anymore.
I expect maybe we'll see some sort of raytraced game on par with tuxracer this year, and a real high-budget game maybe in one or two years, and then ray tracing will be mainstream in about five, when the average person will have a fast-enough machine to handle it.
50 GB seems reasonable, but I would have to agree with you that a 16kbps cap sounds dracconian. (It's still much better than being completely disconnected, though.) I assume you mean 2 kilobytes per second, not four; at that rate, you could only download a little over 5 GB in the whole month; it sounds like they're trying to punish heavy users painfully, rather than enforce reasonable rate limits; they could more reasonably set the initial cap lower at 40 GB, but set the capped speed at 56kbps, which would at least be halfway usable for the capped users, but a saturated connection would still only transfer about 59 GB per month. (40GB + ((56*60*60*24*31)/8)KB = 40GB + 18.7488GB)
$150 is excessive, I agree. Sounds like a monopoly is involved.
I read that recently as well. Good discussion of the implications of augmented reality, though I think some of his other books were better stories.
For another depiction of AR, I recommend Dennou Coil, a 24 episode anime set in a not-too-distant future, where AR is commonplace and there is a second-life type virtual world overlayed on top of the real world. (It's been fansubbed, but not officially released in English.)
I agree that it would be better for networks to expand capacity than to rate-limit their users, but the current state of things is that Internet access is a scarce resource that ought to be allocated fairly. Bandwidth caps aren't perfect; as you pointed out, avoiding peak hours is important as well, but it would prevent users from running bittorrent cliens 24/7 (which tend to eat up an unfair portion of the bandwith, as they use many TCP connections instead of one).
It would be great if applications like bittorrent could be made to use only the idle network capacity. I read a paper awhile back about the merits and implementation details of having a deliberately less aggressive TCP algorithm; of course, users currently have no incentive to use that sort of thing, and ISPs might have a hard time discriminating between customers based on the fairness of their congestion control algorithms.
It was a number I chose arbitrarily; substitute 2GB or 200GB if you like. I expect the median value of bandwidth usage is far below 20GB per month. Heavy users might find that too low, but they can buy service plans with higher limits with a higher per-month fee. I would much rather have ISPs state their bandwidth caps publicly and let customers decide if they're reasonable, than to randomly disconnect customers who "use too much", or for ISPs to start filtering or rate limiting specific applications or web sites.