Hacks like radiosity? Indeed, a ray tracer needs to be supplemented with a global illumination algorithm in order to produce plausibly realistic images, but there are many global illumination algorithms to choose from, and radiosity is the only one I know of that can be implemented without tracing rays.
Photon mapping, for instance, is quite nice, and performs comparatively well. (Normal computers aren't fast enough to do it in real time yet, but they'll get there eventually if the Lord tarries and the creek don't rise.) It also correctly handles non-lambertian textures, unlike radiosity.
What global illumination algorithm would you suggest that isn't a hack and can run on a GPU? (Pre-baked textures don't count.)
I see your 1 million triangles and raise you 349 million more. (Disclaimer: I'm not affiliated with OpenRT, I just think this is a neat demonstration.)
Textures, verticies, and the like take up memory with ray tracing just like rasterization. There's a bit more flexibility with a ray tracer, though, to store non-triangular primitives. Most fast real-time ray tracers just use triangles, though.
As for acceleration structures, octrees have largely been superseded by kd-trees (preferably constructed using a surface-area heuristic), and more recently bounding interval hierarchies, which can be constructed much more quickly than kd-trees.
Only thing ray-tracers have advantage over GPU is fast dynamic scenes.
I would say it's the other way around; ray tracers aren't particularly good at dynamic scenes because then you have to rebuild the acceleration structure when something moves.
That said, there has been a lot of progress lately into addressing this. The Bounding Interval Heirarchy (bih) for instance can be updated very quickly using an in-place sort very much akin to quicksort, and produces trees that are, in general, a bit slower to traverse than kd-trees but can be constructed a few orders of magnitude faster.
Ray tracing a million snowflakes all moving in different directions is going to be a very hard problem for awhile, but basic animation is quite doable.
There are some fine real-time ray tracers out there that have interactive frame-rates with moderately complex scenes on reasonable hardware. Try the arauna demo, for instance. (Note: you probably need windows to run it, wine didn't work for me.) There are others as well; Arauna just happens to be one I've tried out recently. I got about 20fps or so on a friend's dual-core laptop at a resolution somewhere around 640x480. Not fast enough to throw out the GPU just yet, but usable. Somewhere between N-64 and Gamecube-level performance.
Real-time ray tracing is still quite a bit slower than GPU rendering on typical scenes, but hardly "hours per frame", unless you're rendering frames for a movie or doing an art project and care more about realistic lighting effects than performance. (I think too many people have tried povray in the 90's on their old 486s and still think somehow that's as fast as ray tracers ever will be.)
There are a lot of ways to make a ray-tracer slow: photon mapping, radiosity, path tracing, using primitives that have slow ray-intersection tests, using the wrong acceleration structure, excessive reflection, many light sources, etc.. but if you're just rendering triangles, it's quite possible to get usable interactive performance out of a good ray tracer on current hardware. We can add all those "slow" features that pixar et. al. use when the hardware (and algorithms) are ready for it.
Using the known minimum mass of the previously detected Gliese 581 b, and assuming the existence of Gliese 581 d, Gliese 581 c has a mass at least 5.03 times that of Earth. The mass of the planet cannot be very much larger than this or the system would be dynamically unstable.
It seems like it may be a little premature to assume that the new planet is the smallest, even when comparing to planets around main-sequence stars.
I agree the radius is probably a made up number.
Scientist: "Assuming a density similar to earth's, the radius of the planet would be 50% greater than Earth's."
Science reporter: "The planet's radius is 50% greater than Earth's."
You can do that at the edge ISP level because you know who your customers are. The core routers (which is what the article was about) don't have that kind of information available to them.
An ISP at the "edge" knows who is logged on to that IP and so can treat them accordingly..... Roberts proposal (and company's product) however appears to be more focused at the core rather than the edge (if it's the edge I don't even see why it's such a great benefit).
I agree with you there. ISPs at the edge have enough information to treat each user (ie paying customer) fairly. That doesn't help if the core routers are congested, though.
If ISPs start treating P2P different from regular traffic, they might lose their common carrier status and be liable for copyright infringement that happens on their network. They don't want that to happen.
I don't think giving different types of data differing priorities is a good idea; users will just learn to hide their p2p data better. I think if the ISPs are congested, they ought to throttle their highest bandwidth consumers, regardless of traffic type. (And their throttling policy should be public knowledge; users should know where the caps are.)
The core routers ought to keep doing what their doing, unless they can come up with a reliable heuristic for determining how many real people are hiding behind each IP address.
That's just going to encourage people to waste IP addresses. They're scarce already, we don't need organizations to start configuring their nats to use multiple IPs just to get more throughput.
The status quo now is that actual users are not evenly distributed about the address space, and dividing bandwidth by IP doesn't make any more sense than the current situation, in which bandwidth is divided amongst competing sockets.
One reason why that might be problematic in practice, is that, iirc, TCP doesn't like getting packets out of order, and tends to respond to out-of-order packets similarly to dropped packets. If you have packets taking multiple paths, they are very likely to arrive out of order.
One could mitigate this, I suppose, by making sure all packets that are part of the same flow take the same path.
Control each flow so that the total traffic to each IP address (home) is equally and fairly distributed no matter how many flows they use.
This sounds like a pretty good idea until you start thinking about NAT'ed networks. Is it really fair to treat an entire office or dorm (or even a small country) the same as a single user who happens to have a unique IP from their ISP? And what about the transition to IPV6, when presumably IP addresses are no longer going to be scarce?
Why are people always trying to reinvent the fucking wheel?
Because raytracers are useful, and there aren't that many free raytracers with good performance, a reasonably complete set of features and support for distributing the workload across hundreds of processors.
That raytracer looks like shit. It is about the same quality that POV-Ray was at 20 years ago.
That's because they didn't use antialiasing for that teapot render. They do support anti-aliasing, according to the documentation.
Besides, the SPD teapot scene isn't supposed to look awesome, it's supposed to show that your rendering algorithm is functioning properly.
Povray is great, but it isn't particularly fast, and it until the current beta releases they haven't even supported multi-core parallelism in the standard distribution, much less MPI.
Also, tachyon is, according to the changelog, at least 13 years old. Not as old as povray perhaps, but not incredibly modern either.
If you want to see pretty renderings, check out pbrt. If you want to see performance, download a demo of arauna. Both are considerably more modern. If you just want to complain about terrible renderings and pointless projects, then you should check out my ray tracer.
Haskell has parMap for that sort of situation. I've been using parMap to speed up a raytracer I'm writing. I'm getting less than linear speedups for some unknown reason, but it does help and it's easy to use. (I switched from ocaml to haskell partly because I wanted the parallelism, and partly because I wanted to learn haskell.)
Any bandwidth greater than zero over a multi-hop link is an improvement over the status quo, in which that sort of thing typically just isn't supported. Ad-hoc networks are slow (I'm not sure where the sqrt(n) comes from), but they are very practical in situations where a star topology isn't practical, and you want something that just works, right now, without a lot of manual configuration.
Ad-hoc routing doesn't get around the need for ISPs; someone has to have a gateway to the Internet. (And as long as ad-hoc routing doesn't scale up to networks of billions of nodes rather than hundreds or maybe thousands, we're going to have to peer with the Internet somehow.) ISPs may have fewer customers, since a lot of them will be leeching off of their neighbors, but most people who can afford it are probably going to go ahead and pay for their access, since it's faster (multihop wireless networks aren't known for their speed), and there's someone they can blame if it breaks, and they might not have any neighbors willing to share. That's just how people are (at least in the suburban wasteland where I live).
Computing power isn't that big of an issue; I have five consumer-grade wireless routers running OpenWRT with the OLSR routing protocol, and most of them have 16 megs of ram, 4 megs of flash, and about a 200 mhz processor or so. OLSR doesn't scale very well (at least according to what I've read - I don't have enough routers to test), but it should work pretty good for networks of a few dozen nodes at least. For city-wide networks, you'll need something better. OLSR is link-state. Distance vector algorithms like AODV and DSR are less resource-intensive. CPU and memory are less likely to be bottlenecks, but routing overhead is probably the limiting factor.
High transmit power would be nice, but regular 802.11 gear can go surprisingly far with the right antennas. It's also important that all the radios aren't drowning each other out. (There are topology control algorithms to adapt transmit power automatically. I'm not sure if any are widely used.)
Would a tree with a higher degree of branching would be more efficient? It would reduce the maximum depth of the tree, but would introduce more empty subspaces, so it would depend on whether it is faster to iterate over many empty child volumes of the same size versus descending down the tree at each step.
I was wondering the opposite; octrees have largely been superseded by kd-trees (basically, axis aligned binary space partition trees) for a lot of ray tracing tasks. I suppose the octree is convenient since you don't need to store an axis or offset, and you might be able to avoid a bit of math if all the voxels are perfect cubes. kd-trees can be stored pretty compactly, though. It's hard to know which is better without running benchmarks. By a higher degree of branching, do you mean like 27-branch (3x3x3) or 64-branch (4x4x4) nodes? There would be a lot of wasted space if most of those cells were empty.
Ok, I can see the benefit of being able to bail out early in cases where geometry is far away or the full resolution hasn't been loaded in from disk or network or wherever it comes from. I can also see the benefit of storing the texture and geometry in the same data structure. It sound kind of like roam but in three dimensions. I'm not sure if you'd have problems with discontinuities between neighboring voxels of different sizes.
I'm not very knowledgeable of volume rendering, but this seems to be pretty similar, though they only tested the algorithm on a very small dataset. I shall look forward to seeing this sort of thing in a modern game.
I am proposing that it REPLACE hierarchies of triangles or other primitives for some data sets, and this brings about significant improvements (data size) that you wouldn't have with even infinitely fast conventional ray tracing.
So, it's like a variable-resolution three-dimensional bitmap? I can see how you might reduce memory consumption that way, but it would also reduce the fidelity of the rendered image. I'd be curious to know if the memory-quality tradeoff is better than if you were to just (intelligently) simplify the triangle mesh. It's an interesting idea at least.
Perhaps part of the misunderstanding of the article can be attributed to this quote:
But, I do think that there is a very strong possibility as we move towards next generation technologies for a ray tracing architecture that uses a specific data structure; rather than just taking triangles like everybody uses and tracing rays against them and being really, really expensive.
Which would seem to imply that your approach is not really, really expensive, which would make sense if you were comparing with a ray tracer with no acceleration structure at all, and if by "expensive" we assume that you mean "processor intensive" rather than "memory intensive". Your sparse voxel octree approach, if I am understanding correctly, gets rid of a lot of ray-primitive intersections. However, those tend not to be the most CPU-expensive part of ray tracing; rather, it's the acceleration structure lookups where most of the time is spent, so I wouldn't expect your approach to be vastly superior to any other real-time ray tracer.
(Perhaps my criticism in another branch of this thread comes across a little too harsh; if so, I apologize. I thought that DragonWriter was being unfairly criticized for treating the article with the same degree of skepticism as if it had been written by someone other than John Carmack, and was perhaps a little over-enthusiastic in backing up his assessment of the article.)
In retrospect I was perhaps a little too harsh, given that it's just an interview and not an academic paper. However, I don't think that anyone should be given a free ride, either. Rasterization algorithms have some things in common with ray tracing, but a thorough understanding of rasterization does not imply a thorough understanding of ray tracing. Similarly, I would not automatically consider Henry Ford an expert on airplanes, nor Albert Einstein an expert on anthropology, unless I had convincing evidence that it was so. As far as I'm concerned, John Carmack is just another ray tracing hobbyist, and I would hold him to the same standard as any other ray tracing hobbyist: he may have a breakthrough algorithm to make real-time ray traced games happen a bit sooner than they would otherwise, but maybe not. And if he thinks he does, he'll have to convince me of that with a clear argument (and that includes comparing his ideas to the state of the art), or a working demo.
There's a lot of research that goes on in the background that most people don't know about because it doesn't (currently) have much influence on the gaming industry. I don't know if Carmack has kept up with the latest in academic ray tracing research or not, but I'm not going to assume that he has just because he's a well-known game developer; it's quite common for ideas that first show up in academia to take ten or twenty years before they reach the attention of mainstream industry.
I think that goes too far: if the algorithm isn't memory parallel, then the multiple cores that are working on it in parallel have to access shared memory with the accompanying coordination issues. This isn't problematic in the sense that it doesn't work: it certainly works. But it does result in sublinear speedup whereas a memory parallel algorithm could conceptually see a linear speedup. So there is some reason to prefer a memory parallel algorithm (all other things being equal) if you can find one.
So the thing that isn't memory parallel is the scene itself; you can't stick half the scene on one computer, half the scene on another computer, and then merge the results and expect a 2x speedup (but you can do that with scanline algorithms, which is one reason why they're so popular). A ray tracer would have to have a separate copy of the scene on every machine.
But, you can have 2 or 4 or 8 CPU cores all reading from the same scene data sitting in shared memory; these are all reads, not writes, so there aren't big coordination issues like cache invalidations and the like. As far as I know, scaling on a single machine is pretty linear as long as the threading implementation is sane. I don't know much about GPUs, they might not be set to efficiently run tasks in parallel that do unpredictable memory reads.
Slashdot Mirror
post-bachelor disorder
Agreed. The strips may seem like they must surely be an exaggeration, but for the most part they aren't.
Hacks like radiosity? Indeed, a ray tracer needs to be supplemented with a global illumination algorithm in order to produce plausibly realistic images, but there are many global illumination algorithms to choose from, and radiosity is the only one I know of that can be implemented without tracing rays.
Photon mapping, for instance, is quite nice, and performs comparatively well. (Normal computers aren't fast enough to do it in real time yet, but they'll get there eventually if the Lord tarries and the creek don't rise.) It also correctly handles non-lambertian textures, unlike radiosity.
What global illumination algorithm would you suggest that isn't a hack and can run on a GPU? (Pre-baked textures don't count.)
I see your 1 million triangles and raise you 349 million more. (Disclaimer: I'm not affiliated with OpenRT, I just think this is a neat demonstration.)
Textures, verticies, and the like take up memory with ray tracing just like rasterization. There's a bit more flexibility with a ray tracer, though, to store non-triangular primitives. Most fast real-time ray tracers just use triangles, though.
As for acceleration structures, octrees have largely been superseded by kd-trees (preferably constructed using a surface-area heuristic), and more recently bounding interval hierarchies, which can be constructed much more quickly than kd-trees.
I would say it's the other way around; ray tracers aren't particularly good at dynamic scenes because then you have to rebuild the acceleration structure when something moves.
That said, there has been a lot of progress lately into addressing this. The Bounding Interval Heirarchy (bih) for instance can be updated very quickly using an in-place sort very much akin to quicksort, and produces trees that are, in general, a bit slower to traverse than kd-trees but can be constructed a few orders of magnitude faster.
Ray tracing a million snowflakes all moving in different directions is going to be a very hard problem for awhile, but basic animation is quite doable.
There are some fine real-time ray tracers out there that have interactive frame-rates with moderately complex scenes on reasonable hardware. Try the arauna demo, for instance. (Note: you probably need windows to run it, wine didn't work for me.) There are others as well; Arauna just happens to be one I've tried out recently. I got about 20fps or so on a friend's dual-core laptop at a resolution somewhere around 640x480. Not fast enough to throw out the GPU just yet, but usable. Somewhere between N-64 and Gamecube-level performance.
Real-time ray tracing is still quite a bit slower than GPU rendering on typical scenes, but hardly "hours per frame", unless you're rendering frames for a movie or doing an art project and care more about realistic lighting effects than performance. (I think too many people have tried povray in the 90's on their old 486s and still think somehow that's as fast as ray tracers ever will be.)
There are a lot of ways to make a ray-tracer slow: photon mapping, radiosity, path tracing, using primitives that have slow ray-intersection tests, using the wrong acceleration structure, excessive reflection, many light sources, etc.. but if you're just rendering triangles, it's quite possible to get usable interactive performance out of a good ray tracer on current hardware. We can add all those "slow" features that pixar et. al. use when the hardware (and algorithms) are ready for it.
From the article:
From wikipedia article on Gliese 581c:
It seems like it may be a little premature to assume that the new planet is the smallest, even when comparing to planets around main-sequence stars.
I agree the radius is probably a made up number.
Scientist: "Assuming a density similar to earth's, the radius of the planet would be 50% greater than Earth's."
Science reporter: "The planet's radius is 50% greater than Earth's."
This was the default for some version of emacs at one time (maybe it still is), and it's been my favorite ever since.
Wheat (0xF5DEB3) text, darkslategray (0x2F4F4F) background.
You can do that at the edge ISP level because you know who your customers are. The core routers (which is what the article was about) don't have that kind of information available to them.
I agree with you there. ISPs at the edge have enough information to treat each user (ie paying customer) fairly. That doesn't help if the core routers are congested, though.
If ISPs start treating P2P different from regular traffic, they might lose their common carrier status and be liable for copyright infringement that happens on their network. They don't want that to happen.
I don't think giving different types of data differing priorities is a good idea; users will just learn to hide their p2p data better. I think if the ISPs are congested, they ought to throttle their highest bandwidth consumers, regardless of traffic type. (And their throttling policy should be public knowledge; users should know where the caps are.)
The core routers ought to keep doing what their doing, unless they can come up with a reliable heuristic for determining how many real people are hiding behind each IP address.
That's just going to encourage people to waste IP addresses. They're scarce already, we don't need organizations to start configuring their nats to use multiple IPs just to get more throughput.
The status quo now is that actual users are not evenly distributed about the address space, and dividing bandwidth by IP doesn't make any more sense than the current situation, in which bandwidth is divided amongst competing sockets.
One reason why that might be problematic in practice, is that, iirc, TCP doesn't like getting packets out of order, and tends to respond to out-of-order packets similarly to dropped packets. If you have packets taking multiple paths, they are very likely to arrive out of order.
One could mitigate this, I suppose, by making sure all packets that are part of the same flow take the same path.
This sounds like a pretty good idea until you start thinking about NAT'ed networks. Is it really fair to treat an entire office or dorm (or even a small country) the same as a single user who happens to have a unique IP from their ISP? And what about the transition to IPV6, when presumably IP addresses are no longer going to be scarce?
Because raytracers are useful, and there aren't that many free raytracers with good performance, a reasonably complete set of features and support for distributing the workload across hundreds of processors.
That's because they didn't use antialiasing for that teapot render. They do support anti-aliasing, according to the documentation.
Besides, the SPD teapot scene isn't supposed to look awesome, it's supposed to show that your rendering algorithm is functioning properly.
Povray is great, but it isn't particularly fast, and it until the current beta releases they haven't even supported multi-core parallelism in the standard distribution, much less MPI.
Also, tachyon is, according to the changelog, at least 13 years old. Not as old as povray perhaps, but not incredibly modern either.
If you want to see pretty renderings, check out pbrt. If you want to see performance, download a demo of arauna. Both are considerably more modern. If you just want to complain about terrible renderings and pointless projects, then you should check out my ray tracer.
Haskell has parMap for that sort of situation. I've been using parMap to speed up a raytracer I'm writing. I'm getting less than linear speedups for some unknown reason, but it does help and it's easy to use. (I switched from ocaml to haskell partly because I wanted the parallelism, and partly because I wanted to learn haskell.)
Any bandwidth greater than zero over a multi-hop link is an improvement over the status quo, in which that sort of thing typically just isn't supported. Ad-hoc networks are slow (I'm not sure where the sqrt(n) comes from), but they are very practical in situations where a star topology isn't practical, and you want something that just works, right now, without a lot of manual configuration.
Ad-hoc routing doesn't get around the need for ISPs; someone has to have a gateway to the Internet. (And as long as ad-hoc routing doesn't scale up to networks of billions of nodes rather than hundreds or maybe thousands, we're going to have to peer with the Internet somehow.) ISPs may have fewer customers, since a lot of them will be leeching off of their neighbors, but most people who can afford it are probably going to go ahead and pay for their access, since it's faster (multihop wireless networks aren't known for their speed), and there's someone they can blame if it breaks, and they might not have any neighbors willing to share. That's just how people are (at least in the suburban wasteland where I live).
Computing power isn't that big of an issue; I have five consumer-grade wireless routers running OpenWRT with the OLSR routing protocol, and most of them have 16 megs of ram, 4 megs of flash, and about a 200 mhz processor or so. OLSR doesn't scale very well (at least according to what I've read - I don't have enough routers to test), but it should work pretty good for networks of a few dozen nodes at least. For city-wide networks, you'll need something better. OLSR is link-state. Distance vector algorithms like AODV and DSR are less resource-intensive. CPU and memory are less likely to be bottlenecks, but routing overhead is probably the limiting factor.
High transmit power would be nice, but regular 802.11 gear can go surprisingly far with the right antennas. It's also important that all the radios aren't drowning each other out. (There are topology control algorithms to adapt transmit power automatically. I'm not sure if any are widely used.)
I was wondering the opposite; octrees have largely been superseded by kd-trees (basically, axis aligned binary space partition trees) for a lot of ray tracing tasks. I suppose the octree is convenient since you don't need to store an axis or offset, and you might be able to avoid a bit of math if all the voxels are perfect cubes. kd-trees can be stored pretty compactly, though. It's hard to know which is better without running benchmarks. By a higher degree of branching, do you mean like 27-branch (3x3x3) or 64-branch (4x4x4) nodes? There would be a lot of wasted space if most of those cells were empty.
Ok, I can see the benefit of being able to bail out early in cases where geometry is far away or the full resolution hasn't been loaded in from disk or network or wherever it comes from. I can also see the benefit of storing the texture and geometry in the same data structure. It sound kind of like roam but in three dimensions. I'm not sure if you'd have problems with discontinuities between neighboring voxels of different sizes.
I'm not very knowledgeable of volume rendering, but this seems to be pretty similar, though they only tested the algorithm on a very small dataset. I shall look forward to seeing this sort of thing in a modern game.
So, it's like a variable-resolution three-dimensional bitmap? I can see how you might reduce memory consumption that way, but it would also reduce the fidelity of the rendered image. I'd be curious to know if the memory-quality tradeoff is better than if you were to just (intelligently) simplify the triangle mesh. It's an interesting idea at least.
Perhaps part of the misunderstanding of the article can be attributed to this quote:
Which would seem to imply that your approach is not really, really expensive, which would make sense if you were comparing with a ray tracer with no acceleration structure at all, and if by "expensive" we assume that you mean "processor intensive" rather than "memory intensive". Your sparse voxel octree approach, if I am understanding correctly, gets rid of a lot of ray-primitive intersections. However, those tend not to be the most CPU-expensive part of ray tracing; rather, it's the acceleration structure lookups where most of the time is spent, so I wouldn't expect your approach to be vastly superior to any other real-time ray tracer.
(Perhaps my criticism in another branch of this thread comes across a little too harsh; if so, I apologize. I thought that DragonWriter was being unfairly criticized for treating the article with the same degree of skepticism as if it had been written by someone other than John Carmack, and was perhaps a little over-enthusiastic in backing up his assessment of the article.)
In retrospect I was perhaps a little too harsh, given that it's just an interview and not an academic paper. However, I don't think that anyone should be given a free ride, either. Rasterization algorithms have some things in common with ray tracing, but a thorough understanding of rasterization does not imply a thorough understanding of ray tracing. Similarly, I would not automatically consider Henry Ford an expert on airplanes, nor Albert Einstein an expert on anthropology, unless I had convincing evidence that it was so. As far as I'm concerned, John Carmack is just another ray tracing hobbyist, and I would hold him to the same standard as any other ray tracing hobbyist: he may have a breakthrough algorithm to make real-time ray traced games happen a bit sooner than they would otherwise, but maybe not. And if he thinks he does, he'll have to convince me of that with a clear argument (and that includes comparing his ideas to the state of the art), or a working demo.
There's a lot of research that goes on in the background that most people don't know about because it doesn't (currently) have much influence on the gaming industry. I don't know if Carmack has kept up with the latest in academic ray tracing research or not, but I'm not going to assume that he has just because he's a well-known game developer; it's quite common for ideas that first show up in academia to take ten or twenty years before they reach the attention of mainstream industry.
So the thing that isn't memory parallel is the scene itself; you can't stick half the scene on one computer, half the scene on another computer, and then merge the results and expect a 2x speedup (but you can do that with scanline algorithms, which is one reason why they're so popular). A ray tracer would have to have a separate copy of the scene on every machine.
But, you can have 2 or 4 or 8 CPU cores all reading from the same scene data sitting in shared memory; these are all reads, not writes, so there aren't big coordination issues like cache invalidations and the like. As far as I know, scaling on a single machine is pretty linear as long as the threading implementation is sane. I don't know much about GPUs, they might not be set to efficiently run tasks in parallel that do unpredictable memory reads.