4 ms·

Well, that's about as many as a modern 3D game engine executes in one second, so, meh.

matthiaskramm 16y ago
Absolutely. Modern graphics card hardware can easily process a few hundred million triangles per second. In all fairness, however, that has nothing to do with polygon intersection. Drawing a triangle on the screen with a z-buffer check is something quite different from actually computing an intersection polygon from two (multiply connected) input polygons.
- petercooper 16y ago
  CamperBob's flippant comment, however, got me thinking as to whether GPUs could be used to speed up this process, even if it were a bit.. "fuzzy." Anyone with GPU chops have any opinions on this?
  - reitzensteinm 16y ago
    Some modern GPUs support double precision floats, so accuracy would not be an issue. GPUs are practically built for this kind of computation, however there are probably two things holding them back: 1) GPU development requires specific developer experience. Making performant GPU code is an even nastier and less intuitive problem than making performant CPU code. A naive implementation would be shockingly inefficient. 2) Leasing GPU hardware in a datacenter is very rare. You'd have to do it at the office, or build your own servers and install them yourself at a colo. Lots of time and effort. Even if the GPU solution was 10x faster (it could be much more, but it depends on how much the CPU, disk, network is a bottleneck), if you're talking about reducing $50k in computer time to $5k in computer time, it's almost certainly not worth it. If you're talking about $2m to $200k, that's a completely different matter.
    - petercooper 16y ago
      This is exactly why I like asking naive questions on Hacker News - thanks!
    - InclinedPlane 16y ago
      Today relying on a GPU solution translates to vendor lock-in, it makes you much more dependent on a particular set of hardware and even a particular OS/driver stack.
      - babs474 16y ago
        I have had a small amount of success implementing GPGPU programs using webGL. If you code your solution to webGL you are able to offload OS/driver stack concerns to the web browser implementers.
        pixelcort 16y ago
        This is very interesting. Do you have links to any examples? This could be very useful for running certain algorithms in web apps...
        babs474 16y ago
        Here are two examples I've done. The first is matrix multiplication on the GPU. The second is a cellular automaton like simulation (the falling sand game popular a few years ago). Each incremental game state is calculated in a shader program and then used as input for the next increment. Below I've linked github urls and two blog posts that were done about them. Unfortunately right now webGL is kind of a moving target and I doubt these examples still work out of the box. However, if you are interested in GPGPU on webGL I would encourage you to get involved as I think there are some tweaks to the standard that would make GPGPU life easier. Matrix Mutliply http://learningwebgl.com/blog/?p=1828 http://learningwebgl.com/blog/?p=1828 http://github.com/bunions1/matrixMultiplyGpu http://github.com/bunions1/matrixMultiplyGpu Falling Sand http://learningwebgl.com/blog/?p=1471 http://learningwebgl.com/blog/?p=1471 http://github.com/bunions1/fallingsand-webgl http://github.com/bunions1/fallingsand-webgl
      - strebler 16y ago
        That's really not true - we've been doing cloud GPU computing for a few years (all in OpenGL shaders and OpenCL) - we run in Windows, Linux, MacOS and on both NVIDIA and ATI.
    - al_james 16y ago
      Hmmmm.... GPU's in the cloud anyone?
    - strebler 16y ago
      We use GPUs for all of our computer vision and image processing, 10X is definitely a low-ball for what they're doing here - it would be much faster. The important bit is at the end where they say "10% of the time is spent on polygon intersection" and the rest on image processing. We do GPU image processing on the cloud and this is (likely) where Scribd could likely obtain a significant speedup - many of our image processing operations run hundreds of times faster than on the CPU.
- daeken 16y ago
  However, a modern game engine does perform a large number of polygon intersections for the purpose of collision detection. Of course, this is generally very rough for the purpose of performance.
reitzensteinm 16y ago
I wasn't going to say anything, but you're being upmodded like crazy, so... It's a complete apples to oranges comparison. Scribd is performing quite complex logic with an emphasis on correctness not speed. I feel like you're dismissing an interesting article for the sake of an amusing one liner, and that's pretty much the antithesis of HN.
- deleted 16y ago
  [deleted]
- CamperBob 16y ago
  I feel like you're dismissing an interesting article for the sake of an amusing one liner, and that's pretty much the antithesis of HN. It is a nicely-written and illustrated article, but it describes a problem that hasn't been considered 'interesting' for decades and can, in any case, be tackled with a caching scheme. Why would they need to run the same intersection logic over and over, when there's only a finite number of glyphs to render in any given document?
  - matthiaskramm 16y ago
    > but it describes a problem that hasn't been considered 'interesting' for decades Actually, polygon operations on grids is still an active research area, with the latest papers on the topic less than two weeks old: http://www.sci.utah.edu/socg2010agenda.html http://www.sci.utah.edu/socg2010agenda.html > Why would they need to run the same intersection logic over and over [...]? We usually don't. It basically depends on the context in which the glyphs appear on the page. For a standard, say, LaTeX document consisting of mostly text and without weird graphic operations taking place around or on top of the text, a given glyph is just processed once.

Absolutely. Modern graphics card hardware can easily process a few hundred million triangles per second. In all fairness, however, that has nothing to do with polygon intersection. Drawing a triangle on the screen with a z-buffer check is something quite different from actually computing an intersection polygon from two (multiply connected) input polygons.

petercooper 16y ago
CamperBob's flippant comment, however, got me thinking as to whether GPUs could be used to speed up this process, even if it were a bit.. "fuzzy." Anyone with GPU chops have any opinions on this?
- reitzensteinm 16y ago
  Some modern GPUs support double precision floats, so accuracy would not be an issue. GPUs are practically built for this kind of computation, however there are probably two things holding them back: 1) GPU development requires specific developer experience. Making performant GPU code is an even nastier and less intuitive problem than making performant CPU code. A naive implementation would be shockingly inefficient. 2) Leasing GPU hardware in a datacenter is very rare. You'd have to do it at the office, or build your own servers and install them yourself at a colo. Lots of time and effort. Even if the GPU solution was 10x faster (it could be much more, but it depends on how much the CPU, disk, network is a bottleneck), if you're talking about reducing $50k in computer time to $5k in computer time, it's almost certainly not worth it. If you're talking about $2m to $200k, that's a completely different matter.
  - petercooper 16y ago
    This is exactly why I like asking naive questions on Hacker News - thanks!
  - InclinedPlane 16y ago
    Today relying on a GPU solution translates to vendor lock-in, it makes you much more dependent on a particular set of hardware and even a particular OS/driver stack.
    - babs474 16y ago
      I have had a small amount of success implementing GPGPU programs using webGL. If you code your solution to webGL you are able to offload OS/driver stack concerns to the web browser implementers.
      - pixelcort 16y ago
        This is very interesting. Do you have links to any examples? This could be very useful for running certain algorithms in web apps...
        babs474 16y ago
        Here are two examples I've done. The first is matrix multiplication on the GPU. The second is a cellular automaton like simulation (the falling sand game popular a few years ago). Each incremental game state is calculated in a shader program and then used as input for the next increment. Below I've linked github urls and two blog posts that were done about them. Unfortunately right now webGL is kind of a moving target and I doubt these examples still work out of the box. However, if you are interested in GPGPU on webGL I would encourage you to get involved as I think there are some tweaks to the standard that would make GPGPU life easier. Matrix Mutliply http://learningwebgl.com/blog/?p=1828 http://learningwebgl.com/blog/?p=1828 http://github.com/bunions1/matrixMultiplyGpu http://github.com/bunions1/matrixMultiplyGpu Falling Sand http://learningwebgl.com/blog/?p=1471 http://learningwebgl.com/blog/?p=1471 http://github.com/bunions1/fallingsand-webgl http://github.com/bunions1/fallingsand-webgl
    - strebler 16y ago
      That's really not true - we've been doing cloud GPU computing for a few years (all in OpenGL shaders and OpenCL) - we run in Windows, Linux, MacOS and on both NVIDIA and ATI.
  - al_james 16y ago
    Hmmmm.... GPU's in the cloud anyone?
  - strebler 16y ago
    We use GPUs for all of our computer vision and image processing, 10X is definitely a low-ball for what they're doing here - it would be much faster. The important bit is at the end where they say "10% of the time is spent on polygon intersection" and the rest on image processing. We do GPU image processing on the cloud and this is (likely) where Scribd could likely obtain a significant speedup - many of our image processing operations run hundreds of times faster than on the CPU.
daeken 16y ago
However, a modern game engine does perform a large number of polygon intersections for the purpose of collision detection. Of course, this is generally very rough for the purpose of performance.

reitzensteinm 16y ago

I wasn't going to say anything, but you're being upmodded like crazy, so... It's a complete apples to oranges comparison. Scribd is performing quite complex logic with an emphasis on correctness not speed. I feel like you're dismissing an interesting article for the sake of an amusing one liner, and that's pretty much the antithesis of HN.

deleted 16y ago
[deleted]
CamperBob 16y ago
I feel like you're dismissing an interesting article for the sake of an amusing one liner, and that's pretty much the antithesis of HN. It is a nicely-written and illustrated article, but it describes a problem that hasn't been considered 'interesting' for decades and can, in any case, be tackled with a caching scheme. Why would they need to run the same intersection logic over and over, when there's only a finite number of glyphs to render in any given document?
- matthiaskramm 16y ago
  > but it describes a problem that hasn't been considered 'interesting' for decades Actually, polygon operations on grids is still an active research area, with the latest papers on the topic less than two weeks old: http://www.sci.utah.edu/socg2010agenda.html http://www.sci.utah.edu/socg2010agenda.html > Why would they need to run the same intersection logic over and over [...]? We usually don't. It basically depends on the context in which the glyphs appear on the page. For a standard, say, LaTeX document consisting of mostly text and without weird graphic operations taking place around or on top of the text, a given glyph is just processed once.