Re: [webkit-dev] Checking allocation failures [was: Re: Naked new considered harmful]
Date: Fri, 27 Aug 2010 11:07:02 +0530 Subject: Re: [webkit-dev] Checking allocation failures [was: Re: Naked new considered harmful] From: sriram.neelakan...@gmail.com To: marchy...@hotmail.com CC: jam...@google.com; aba...@webkit.org; webkit-dev@lists.webkit.org Hi all, I am still a newbie in this ocenaous wekbit ... here are some thoughts from me.. please correct me if i have misunderstood some thing; Talking on the same lines of Resource allocations.. I have seen already snips of code that handle Large Resource allocations gracefully. For instance i think the ImageReosource has a check on maximum decoded image size..But that just applies to a single image being decoded; That is just an example I use because I've seen it happen- sure the image can be too big but the data can be corrupt too. What webkit may need is something like maximum amount of memory available for all Image Resources in a page.. and when the limit is hit inform the Client/embedder of the same. So basically in this case the page can get gracefully degraded and the user can be informed of the same; I think some other stuff like CSS can also be gracefully handled I guess there are two issues- being able to kill the thing least relevant to the user when you encounter resource limitations and optimizing the use of resources prior to that. One issue with the latter is often memory coherence- no one wants to here my stories about the disk light coming on everytime I try to fill out a web form- and this goes along with things like Planner or Strategy or whatever you want to call them. If everytime you were about to do something significant you may an estimate of the memory or IO or CPU cycles to accomplish some part of that task, first you could maybe pick among implementations suited to the immediate situation and then you could allocate memory in a single heap for that task. I guess my only point is that probably many exceptions due to alloc failure may be predictable with effort that is not a distraction from larger issues like optimiztion. As a browser user there are many times when I'd simply like to download text instead of images, certainly turn off Flash as when I'm on a modem. It may be possible to set criteria however rather than just on/off( turn off images if bw hits 56kbps unless I click on the substitute text). I guess you could consider a feature like this to be picking among rendering things that render images as their alt text or not. But Now lets say there is a cap for maximum JS memory and we run out of it some reason; then it would be safe to inform the user and unload the page itself; This always bothers me- hard limits need to be set somehow. And ok sure there is probably a fixed amount of memory on the platform that gives you some numbers to work from but still trying to limit certain things to fixed amounts seems to create arbitrary things that may be had to pick well. I have seen lot of cache storage code that is already checking for resource object sizes (including decoded sizes).. I think this may be a worthy to try On 8/26/10, Mike Marchywka wrote: this reminds me that I've always been wondering about checks for allocation failure in WebCore (versus concerns about leaks). A plain call to new may throw an std::bad_alloc exception. If this is not considered, it may leave objects in an invalid state, even when using objects such as RefPtr to wrap arround allocations. I don't remember any specific place in the WebCore code where it would be a problem, I just don't remember seeing any code that deals with allocation failures. Is this a design choice somehow? If so, is there some online documentation/discussion about it? (Tried to google it but found nothing...) Failed allocations in WebKit call CRASH(). This prevents us from ending up in an inconsistent state. Ok, but WebKit is used on devices where allocation failure is somewhat of a realistic possibility, no? Wouldn't it be desirable to handle such a situation gracefully? (I.e. display of an error message when trying to open one more tab rather than crashing the entire browser, for example.) Hopefully I am not missing something obvious. Dunno. The crash-on-allocation failure assumption is baked into lots of lines of code. We do have a tryFastMalloc() path that returns NULL on allocation failure instead of crashing. It's used in some pieces of code that are carefully written to handle an allocation failure gracefully. However, this is rare. In general it's very difficult to recover from an allocation failure in an arbitrary piece of code with an arbitrary callstack. - James ( hotmail is still having all kinds of problems, doesn't seem to like text or a modem connection, sorry for eidting slop ). I guess this relates to many earlier
[webkit-dev] Accelerated 2D Tesselation Implementation
Hi Ken, It would help me, and I think many others, if we could have a discussion of how exactly your tessellation logic works and what it is intended to do. For instance, is the algorithm you're using based on Loop-Blinn? I'm a bit familiar with that algorithm and some of the problems it has with rendering this type of geometry. For instance, there are typically anti-aliasing artifacts at the points where the interior triangles touch the edges. These are described in section 5.1 of the paper and the authors added additional (and not well described) logic to solve the problem. If you could describe your algorithm a bit and show some expected results with typical cases, that would be really helpful. For those not familiar with Loop-Blinn, here is a link to their original paper, presented at Siggraph 2005: Resolution Independent Curve Rendering using Programmable Graphics ... It's a great algorithm for rendering resolution independent 2D objects using the GPU. It has potential to render both 2D shapes (as used in Canvas and SVG) and text glyphs. It's advantage is that once you generate the triangles for the shape, you can render the shape at any resolution. It's disadvantage is that the triangle generation is quite expensive, so mutating shapes can potentially be slower than a simpler resolution dependent tessellation. - ~Chris cmar...@apple.com ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
Re: [webkit-dev] Accelerated 2D Tesselation Implementation
On Fri, Aug 27, 2010 at 10:18 AM, Chris Marrin cmar...@apple.com wrote: Hi Ken, It would help me, and I think many others, if we could have a discussion of how exactly your tessellation logic works and what it is intended to do. For instance, is the algorithm you're using based on Loop-Blinn? I'm a bit familiar with that algorithm and some of the problems it has with rendering this type of geometry. For instance, there are typically anti-aliasing artifacts at the points where the interior triangles touch the edges. These are described in section 5.1 of the paper and the authors added additional (and not well described) logic to solve the problem. If you could describe your algorithm a bit and show some expected results with typical cases, that would be really helpful. For those not familiar with Loop-Blinn, here is a link to their original paper, presented at Siggraph 2005: Resolution Independent Curve Rendering using Programmable Graphics ... It's a great algorithm for rendering resolution independent 2D objects using the GPU. It has potential to render both 2D shapes (as used in Canvas and SVG) and text glyphs. It's advantage is that once you generate the triangles for the shape, you can render the shape at any resolution. It's disadvantage is that the triangle generation is quite expensive, so mutating shapes can potentially be slower than a simpler resolution dependent tessellation. I think there's a variant of the algorithm that uses the stencil buffer polygon rendering method ( http://zrusin.blogspot.com/2006/07/hardware-accelerated-polygon-rendering.html ) instead of triangulation. The paper I think I read on that only covered quadratic splines, but maybe somehow has extended that method to cubic splines by now? Nico - ~Chris cmar...@apple.com ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
Re: [webkit-dev] Accelerated 2D Tesselation Implementation
On Fri, Aug 27, 2010 at 10:51 AM, Chris Marrin cmar...@apple.com wrote: On Aug 27, 2010, at 10:32 AM, Nico Weber wrote: On Fri, Aug 27, 2010 at 10:18 AM, Chris Marrin cmar...@apple.com wrote: Hi Ken, It would help me, and I think many others, if we could have a discussion of how exactly your tessellation logic works and what it is intended to do. For instance, is the algorithm you're using based on Loop-Blinn? I'm a bit familiar with that algorithm and some of the problems it has with rendering this type of geometry. For instance, there are typically anti-aliasing artifacts at the points where the interior triangles touch the edges. These are described in section 5.1 of the paper and the authors added additional (and not well described) logic to solve the problem. If you could describe your algorithm a bit and show some expected results with typical cases, that would be really helpful. For those not familiar with Loop-Blinn, here is a link to their original paper, presented at Siggraph 2005: Resolution Independent Curve Rendering using Programmable Graphics ... It's a great algorithm for rendering resolution independent 2D objects using the GPU. It has potential to render both 2D shapes (as used in Canvas and SVG) and text glyphs. It's advantage is that once you generate the triangles for the shape, you can render the shape at any resolution. It's disadvantage is that the triangle generation is quite expensive, so mutating shapes can potentially be slower than a simpler resolution dependent tessellation. I think there's a variant of the algorithm that uses the stencil buffer polygon rendering method ( http://zrusin.blogspot.com/2006/07/hardware-accelerated-polygon-rendering.html ) instead of triangulation. The paper I think I read on that only covered quadratic splines, but maybe somehow has extended that method to cubic splines by now? It looks like that technique deals with polygons, so as long as you convert the shape to a piecewise linear curve it seems like it can handle any curve form, right? What I linked is how to render polygons with the z buffer. http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html says: Recently, Kokojima et al. 2006 presented a variant on our approach for quadratic splines that used the stencil buffer to avoid triangulation. Their idea is to connect all points on the curve path and draw them as a triangle fan into the stencil buffer with the invert operator. Only pixels drawn an odd number of times will be nonzero, thus giving the correct image of concavities and holes. Next, they draw the curve segments, treating them all as convex quadratic elements. This will either add to or carve away a curved portion of the shape. A quad large enough to cover the extent of the stencil buffer is then drawn to the frame buffer with a stencil test. The result is the same as ours without triangulation or subdivision, and needing only one quadratic curve orientation. Furthermore, eliminating the triangulation steps makes high-performance rendering of dynamic curves possible. The disadvantage of their approach is that two passes over the curve data are needed. For static curves, they are trading performance for implementation overhead. Maybe someone extended Kokojima et al's work to cover cubic splines. - ~Chris cmar...@apple.com ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
Re: [webkit-dev] Accelerated 2D Tesselation Implementation
On Aug 27, 2010, at 10:59 AM, Nico Weber wrote: On Fri, Aug 27, 2010 at 10:51 AM, Chris Marrin cmar...@apple.com wrote: On Aug 27, 2010, at 10:32 AM, Nico Weber wrote: On Fri, Aug 27, 2010 at 10:18 AM, Chris Marrin cmar...@apple.com wrote: Hi Ken, It would help me, and I think many others, if we could have a discussion of how exactly your tessellation logic works and what it is intended to do. For instance, is the algorithm you're using based on Loop-Blinn? I'm a bit familiar with that algorithm and some of the problems it has with rendering this type of geometry. For instance, there are typically anti-aliasing artifacts at the points where the interior triangles touch the edges. These are described in section 5.1 of the paper and the authors added additional (and not well described) logic to solve the problem. If you could describe your algorithm a bit and show some expected results with typical cases, that would be really helpful. For those not familiar with Loop-Blinn, here is a link to their original paper, presented at Siggraph 2005: Resolution Independent Curve Rendering using Programmable Graphics ... It's a great algorithm for rendering resolution independent 2D objects using the GPU. It has potential to render both 2D shapes (as used in Canvas and SVG) and text glyphs. It's advantage is that once you generate the triangles for the shape, you can render the shape at any resolution. It's disadvantage is that the triangle generation is quite expensive, so mutating shapes can potentially be slower than a simpler resolution dependent tessellation. I think there's a variant of the algorithm that uses the stencil buffer polygon rendering method ( http://zrusin.blogspot.com/2006/07/hardware-accelerated-polygon-rendering.html ) instead of triangulation. The paper I think I read on that only covered quadratic splines, but maybe somehow has extended that method to cubic splines by now? It looks like that technique deals with polygons, so as long as you convert the shape to a piecewise linear curve it seems like it can handle any curve form, right? What I linked is how to render polygons with the z buffer. http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html says: Recently, Kokojima et al. 2006 presented a variant on our approach for quadratic splines that used the stencil buffer to avoid triangulation. Their idea is to connect all points on the curve path and draw them as a triangle fan into the stencil buffer with the invert operator. Only pixels drawn an odd number of times will be nonzero, thus giving the correct image of concavities and holes. Next, they draw the curve segments, treating them all as convex quadratic elements. This will either add to or carve away a curved portion of the shape. A quad large enough to cover the extent of the stencil buffer is then drawn to the frame buffer with a stencil test. The result is the same as ours without triangulation or subdivision, and needing only one quadratic curve orientation. Furthermore, eliminating the triangulation steps makes high-performance rendering of dynamic curves possible. The disadvantage of their approach is that two passes over the curve data are needed. For static curves, they are trading performance for implementation overhead. Maybe someone extended Kokojima et al's work to cover cubic splines. Ok, that makes sense. One thing that strikes me about that technique is that it touches many pixels outside the actual shape. Some edge cases could have overdraw of several hundred, which seems like it would affect performance. But I have not seen any data about this. - ~Chris cmar...@apple.com ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
[webkit-dev] Misplaced files
Looking through WebCore/html I noticed the files below. I'm not sure they belong in WebCore/html because they don't appear to be HTML-specific. Rather, they seem like generic web platform APIs (e.g., they could be exposed to SVG or whatever other markup languages we choose to support in the future). Should we move these to WebCore/page, WebCore/dom, or should we make a new location for these sorts of things? Adam == Blob-related == Blob.cpp Blob.h Blob.idl BlobBuilder.cpp BlobBuilder.h BlobBuilder.idl BlobURL.cpp BlobURL.h ThreadableBlobRegistry.cpp ThreadableBlobRegistry.h == File-related == File.cpp File.h File.idl FileError.h FileError.idl FileList.cpp FileList.h FileList.idl FileReader.cpp FileReader.h FileReader.idl FileStreamProxy.cpp FileStreamProxy.h FileThread.cpp FileThread.h FileThreadTask.h FileWriter.cpp FileWriter.h FileWriter.idl ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
Re: [webkit-dev] Misplaced files
On Aug 27, 2010, at 3:55 PM, Adam Barth wrote: Looking through WebCore/html I noticed the files below. I'm not sure they belong in WebCore/html because they don't appear to be HTML-specific. Rather, they seem like generic web platform APIs (e.g., they could be exposed to SVG or whatever other markup languages we choose to support in the future). Should we move these to WebCore/page, WebCore/dom, or should we make a new location for these sorts of things? I think the File API (which all of these are related to) deserves its own directory right under WebCore. - Maciej Adam == Blob-related == Blob.cpp Blob.h Blob.idl BlobBuilder.cpp BlobBuilder.h BlobBuilder.idl BlobURL.cpp BlobURL.h ThreadableBlobRegistry.cpp ThreadableBlobRegistry.h == File-related == File.cpp File.h File.idl FileError.h FileError.idl FileList.cpp FileList.h FileList.idl FileReader.cpp FileReader.h FileReader.idl FileStreamProxy.cpp FileStreamProxy.h FileThread.cpp FileThread.h FileThreadTask.h FileWriter.cpp FileWriter.h FileWriter.idl ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
Re: [webkit-dev] Misplaced files
Considering there are already specific WebCore subdirs for notifications, storage, workers, svg, mathml and others, it seems having a new subdirectory named perhaps 'blob' wouldn't be out of line. There is quite a few of those Blob/File files already... Dmitry On Fri, Aug 27, 2010 at 3:55 PM, Adam Barth aba...@webkit.org wrote: Looking through WebCore/html I noticed the files below. I'm not sure they belong in WebCore/html because they don't appear to be HTML-specific. Rather, they seem like generic web platform APIs (e.g., they could be exposed to SVG or whatever other markup languages we choose to support in the future). Should we move these to WebCore/page, WebCore/dom, or should we make a new location for these sorts of things? Adam == Blob-related == Blob.cpp Blob.h Blob.idl BlobBuilder.cpp BlobBuilder.h BlobBuilder.idl BlobURL.cpp BlobURL.h ThreadableBlobRegistry.cpp ThreadableBlobRegistry.h == File-related == File.cpp File.h File.idl FileError.h FileError.idl FileList.cpp FileList.h FileList.idl FileReader.cpp FileReader.h FileReader.idl FileStreamProxy.cpp FileStreamProxy.h FileThread.cpp FileThread.h FileThreadTask.h FileWriter.cpp FileWriter.h FileWriter.idl ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
Re: [webkit-dev] Accelerated 2D Tesselation Implementation
On Fri, Aug 27, 2010 at 10:18 AM, Chris Marrin cmar...@apple.com wrote: Hi Ken, It would help me, and I think many others, if we could have a discussion of how exactly your tessellation logic works and what it is intended to do. For instance, is the algorithm you're using based on Loop-Blinn? I'm a bit familiar with that algorithm and some of the problems it has with rendering this type of geometry. For instance, there are typically anti-aliasing artifacts at the points where the interior triangles touch the edges. These are described in section 5.1 of the paper and the authors added additional (and not well described) logic to solve the problem. If you could describe your algorithm a bit and show some expected results with typical cases, that would be really helpful. For those not familiar with Loop-Blinn, here is a link to their original paper, presented at Siggraph 2005: Resolution Independent Curve Rendering using Programmable Graphics ... It's a great algorithm for rendering resolution independent 2D objects using the GPU. It has potential to render both 2D shapes (as used in Canvas and SVG) and text glyphs. It's advantage is that once you generate the triangles for the shape, you can render the shape at any resolution. It's disadvantage is that the triangle generation is quite expensive, so mutating shapes can potentially be slower than a simpler resolution dependent tessellation. The code that is out for review (see https://bugs.webkit.org/show_bug.cgi?id=44729 ) is, as described in the bug report, precisely an implementation of Loop and Blinn's algorithm. It comes from their simplified reformulation in Chapter 25 of GPU Gems 3, which can be found online at http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html . Their GPU Gems chapter discusses the antialiasing artifacts you mention, where interior triangles not handled by their shader touch the surface of the shape. They point out that enabling multisampling antialiasing solves this problem; the contents of these pixels are antialiased via MSAA, and the pixels covered by their shader are handled by their antialiasing formula. My own experience has been that this works very well; there are no distinguishable bumps or aliasing artifacts with both MSAA enabled and using the antialiasing version of their shader. This is actually the second implementation of this algorithm I have done. In the first, we did much more experimentation, including trying Kokojima et al's stencil buffer algorithm rather than tessellating the interior of the shape. We found that the increased fill rate requirements of Kokojima's technique was detrimental to performance, and that it was better to tessellate to reduce overdraw. In my first implementation of this algorithm, we found that detecting and resolving overlaps of cubic curve control points (section 25.4 in the GPU Gems 3 chapter) was by far the most expensive part of the algorithm. It is also absolutely necessary in order to handle arbitrary inputs. After some investigation I realized that the plane-sweep algorithm mapped well to the problem of detecting overlaps of control point triangles, and incorporating a variant of this algorithm reduced the curve processing time dramatically. This optimization is included in the code out for review. Currently we have hooked up this code to a 2D Canvas implementation, and are performing no caching; we tessellate each path as it comes in. Performance of the classic SVG butterfly drawn using CanvasRenderingContext2D is similar to that of the software renderer, although I do not have concrete performance numbers yet. For retained mode APIs like SVG where the processing results can be cached easily, I expect significant performance improvements based on previous experience. Here is a screenshot from our current implementation: http://www.rawbw.com/~kbrussel/tmp/butterfly.jpg This does not have multisampling turned on yet. For comparison, here is a screenshot from the version in O3D, which does: http://www.rawbw.com/~kbrussel/tmp/butterfly-o3d.jpg Does this help answer your questions? -Ken ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
Re: [webkit-dev] Accelerated 2D Tesselation Implementation
On Fri, Aug 27, 2010 at 4:21 PM, Kenneth Russell k...@google.com wrote: On Fri, Aug 27, 2010 at 10:18 AM, Chris Marrin cmar...@apple.com wrote: Hi Ken, It would help me, and I think many others, if we could have a discussion of how exactly your tessellation logic works and what it is intended to do. For instance, is the algorithm you're using based on Loop-Blinn? I'm a bit familiar with that algorithm and some of the problems it has with rendering this type of geometry. For instance, there are typically anti-aliasing artifacts at the points where the interior triangles touch the edges. These are described in section 5.1 of the paper and the authors added additional (and not well described) logic to solve the problem. If you could describe your algorithm a bit and show some expected results with typical cases, that would be really helpful. For those not familiar with Loop-Blinn, here is a link to their original paper, presented at Siggraph 2005: Resolution Independent Curve Rendering using Programmable Graphics ... It's a great algorithm for rendering resolution independent 2D objects using the GPU. It has potential to render both 2D shapes (as used in Canvas and SVG) and text glyphs. It's advantage is that once you generate the triangles for the shape, you can render the shape at any resolution. It's disadvantage is that the triangle generation is quite expensive, so mutating shapes can potentially be slower than a simpler resolution dependent tessellation. The code that is out for review (see https://bugs.webkit.org/show_bug.cgi?id=44729 ) is, as described in the bug report, precisely an implementation of Loop and Blinn's algorithm. It comes from their simplified reformulation in Chapter 25 of GPU Gems 3, which can be found online at http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html . Their GPU Gems chapter discusses the antialiasing artifacts you mention, where interior triangles not handled by their shader touch the surface of the shape. They point out that enabling multisampling antialiasing solves this problem; the contents of these pixels are antialiased via MSAA, and the pixels covered by their shader are handled by their antialiasing formula. My own experience has been that this works very well; there are no distinguishable bumps or aliasing artifacts with both MSAA enabled and using the antialiasing version of their shader. This is actually the second implementation of this algorithm I have done. In the first, we did much more experimentation, including trying Kokojima et al's stencil buffer algorithm rather than tessellating the interior of the shape. We found that the increased fill rate requirements of Kokojima's technique was detrimental to performance, and that it was better to tessellate to reduce overdraw. In my first implementation of this algorithm, we found that detecting and resolving overlaps of cubic curve control points (section 25.4 in the GPU Gems 3 chapter) was by far the most expensive part of the algorithm. It is also absolutely necessary in order to handle arbitrary inputs. After some investigation I realized that the plane-sweep algorithm mapped well to the problem of detecting overlaps of control point triangles, and incorporating a variant of this algorithm reduced the curve processing time dramatically. This optimization is included in the code out for review. Currently we have hooked up this code to a 2D Canvas implementation, and are performing no caching; we tessellate each path as it comes in. Performance of the classic SVG butterfly drawn using CanvasRenderingContext2D is similar to that of the software renderer, although I do not have concrete performance numbers yet. For retained mode APIs like SVG where the processing results can be cached easily, I expect significant performance improvements based on previous experience. Here is a screenshot from our current implementation: http://www.rawbw.com/~kbrussel/tmp/butterfly.jpg This does not have multisampling turned on yet. For comparison, here is a screenshot from the version in O3D, which does: http://www.rawbw.com/~kbrussel/tmp/butterfly-o3d.jpg Does this help answer your questions? Since I decided not to attach these files, here are the non-quantized versions: http://www.rawbw.com/~kbrussel/tmp/butterfly.png http://www.rawbw.com/~kbrussel/tmp/butterfly-o3d.png -Ken ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
Re: [webkit-dev] Accelerated 2D Tesselation Implementation
On Aug 27, 2010, at 4:21 PM, Kenneth Russell wrote: On Fri, Aug 27, 2010 at 10:18 AM, Chris Marrin cmar...@apple.com wrote: Hi Ken, It would help me, and I think many others, if we could have a discussion of how exactly your tessellation logic works and what it is intended to do. For instance, is the algorithm you're using based on Loop-Blinn? I'm a bit familiar with that algorithm and some of the problems it has with rendering this type of geometry. For instance, there are typically anti-aliasing artifacts at the points where the interior triangles touch the edges. These are described in section 5.1 of the paper and the authors added additional (and not well described) logic to solve the problem. If you could describe your algorithm a bit and show some expected results with typical cases, that would be really helpful. For those not familiar with Loop-Blinn, here is a link to their original paper, presented at Siggraph 2005: Resolution Independent Curve Rendering using Programmable Graphics ... It's a great algorithm for rendering resolution independent 2D objects using the GPU. It has potential to render both 2D shapes (as used in Canvas and SVG) and text glyphs. It's advantage is that once you generate the triangles for the shape, you can render the shape at any resolution. It's disadvantage is that the triangle generation is quite expensive, so mutating shapes can potentially be slower than a simpler resolution dependent tessellation. The code that is out for review (see https://bugs.webkit.org/show_bug.cgi?id=44729 ) is, as described in the bug report, precisely an implementation of Loop and Blinn's algorithm. It comes from their simplified reformulation in Chapter 25 of GPU Gems 3, which can be found online at http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html . Ok, great, thanks. That makes everything much more clear. Their GPU Gems chapter discusses the antialiasing artifacts you mention, where interior triangles not handled by their shader touch the surface of the shape. They point out that enabling multisampling antialiasing solves this problem; the contents of these pixels are antialiased via MSAA, and the pixels covered by their shader are handled by their antialiasing formula. My own experience has been that this works very well; there are no distinguishable bumps or aliasing artifacts with both MSAA enabled and using the antialiasing version of their shader. Yeah, this is what I thought might be the solution. The problem with multisampling is that it's not hardware accelerated everywhere and where it is, it increases expense in both storage and rendering time. I'm not saying this is a showstopper, it's just an issue. So here's my concern. If you have to multisample for anti-aliasing anyway, why not just tesselate the shape at an appropriate sampling resolution and multisample the resulting triangle rendering. That would have the disadvantage of not being resolution independent, but it would be much simpler. And you can control the re-tessellation by oversampling the curve and only re-tesselating every few frames (maybe in the background) or only re-tesselating when not animating, or something like that. Would it be significantly faster or slower? Would the quality be better or worse? We'd have to run some tests. I just don't want to jump into a big expensive algorithm when something simpler would suffice. This is actually the second implementation of this algorithm I have done. In the first, we did much more experimentation, including trying Kokojima et al's stencil buffer algorithm rather than tessellating the interior of the shape. We found that the increased fill rate requirements of Kokojima's technique was detrimental to performance, and that it was better to tessellate to reduce overdraw. Yeah, I can see that algorithm have some really horrible edge cases. In my first implementation of this algorithm, we found that detecting and resolving overlaps of cubic curve control points (section 25.4 in the GPU Gems 3 chapter) was by far the most expensive part of the algorithm. It is also absolutely necessary in order to handle arbitrary inputs. After some investigation I realized that the plane-sweep algorithm mapped well to the problem of detecting overlaps of control point triangles, and incorporating a variant of this algorithm reduced the curve processing time dramatically. This optimization is included in the code out for review. Currently we have hooked up this code to a 2D Canvas implementation, and are performing no caching; we tessellate each path as it comes in. Performance of the classic SVG butterfly drawn using CanvasRenderingContext2D is similar to that of the software renderer, although I do not have concrete performance numbers yet. For retained mode APIs like SVG where the processing results can be cached easily, I expect significant performance improvements based on previous
Re: [webkit-dev] Misplaced files
On Fri, Aug 27, 2010 at 4:08 PM, Maciej Stachowiak m...@apple.com wrote: On Aug 27, 2010, at 3:55 PM, Adam Barth wrote: Looking through WebCore/html I noticed the files below. I'm not sure they belong in WebCore/html because they don't appear to be HTML-specific. Rather, they seem like generic web platform APIs (e.g., they could be exposed to SVG or whatever other markup languages we choose to support in the future). Should we move these to WebCore/page, WebCore/dom, or should we make a new location for these sorts of things? I think the File API (which all of these are related to) deserves its own directory right under WebCore. Ok. I can take care of that. Thoughts on names? WebCore/file ? Adam ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
Re: [webkit-dev] Accelerated 2D Tesselation Implementation
On Fri, Aug 27, 2010 at 5:10 PM, Chris Marrin cmar...@apple.com wrote: On Aug 27, 2010, at 4:21 PM, Kenneth Russell wrote: On Fri, Aug 27, 2010 at 10:18 AM, Chris Marrin cmar...@apple.com wrote: Hi Ken, It would help me, and I think many others, if we could have a discussion of how exactly your tessellation logic works and what it is intended to do. For instance, is the algorithm you're using based on Loop-Blinn? I'm a bit familiar with that algorithm and some of the problems it has with rendering this type of geometry. For instance, there are typically anti-aliasing artifacts at the points where the interior triangles touch the edges. These are described in section 5.1 of the paper and the authors added additional (and not well described) logic to solve the problem. If you could describe your algorithm a bit and show some expected results with typical cases, that would be really helpful. For those not familiar with Loop-Blinn, here is a link to their original paper, presented at Siggraph 2005: Resolution Independent Curve Rendering using Programmable Graphics ... It's a great algorithm for rendering resolution independent 2D objects using the GPU. It has potential to render both 2D shapes (as used in Canvas and SVG) and text glyphs. It's advantage is that once you generate the triangles for the shape, you can render the shape at any resolution. It's disadvantage is that the triangle generation is quite expensive, so mutating shapes can potentially be slower than a simpler resolution dependent tessellation. The code that is out for review (see https://bugs.webkit.org/show_bug.cgi?id=44729 ) is, as described in the bug report, precisely an implementation of Loop and Blinn's algorithm. It comes from their simplified reformulation in Chapter 25 of GPU Gems 3, which can be found online at http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html . Ok, great, thanks. That makes everything much more clear. Their GPU Gems chapter discusses the antialiasing artifacts you mention, where interior triangles not handled by their shader touch the surface of the shape. They point out that enabling multisampling antialiasing solves this problem; the contents of these pixels are antialiased via MSAA, and the pixels covered by their shader are handled by their antialiasing formula. My own experience has been that this works very well; there are no distinguishable bumps or aliasing artifacts with both MSAA enabled and using the antialiasing version of their shader. Yeah, this is what I thought might be the solution. The problem with multisampling is that it's not hardware accelerated everywhere and where it is, it increases expense in both storage and rendering time. I'm not saying this is a showstopper, it's just an issue. So here's my concern. If you have to multisample for anti-aliasing anyway, why not just tesselate the shape at an appropriate sampling resolution and multisample the resulting triangle rendering. That would have the disadvantage of not being resolution independent, but it would be much simpler. And you can control the re-tessellation by oversampling the curve and only re-tesselating every few frames (maybe in the background) or only re-tesselating when not animating, or something like that. Would it be significantly faster or slower? Would the quality be better or worse? We'd have to run some tests. I just don't want to jump into a big expensive algorithm when something simpler would suffice. I don't have experience comparing to an algorithm which creates this sort of high density mesh. However, I do have experience comparing a full implementation of Loop and Blinn's algorithm to one which only supported the (simpler) quadratic case. This required cubics to be approximated with quadratics, and the resulting meshes contained many more triangles than when cubics were handled directly. For complex scenes involving many paths, the reduction in triangle count from supporting cubics improved performance significantly. I imagine the performance improvements of having a resolution-independent mesh will be even more pronounced compared to approximating curves with line segments. The tessellation cost will also be much higher in the latter case because of the dramatic increase in the number of vertices to consider. If using an algorithm like Kokojima's to avoid tessellation, the number of triangles drawn will skyrocket. This is actually the second implementation of this algorithm I have done. In the first, we did much more experimentation, including trying Kokojima et al's stencil buffer algorithm rather than tessellating the interior of the shape. We found that the increased fill rate requirements of Kokojima's technique was detrimental to performance, and that it was better to tessellate to reduce overdraw. Yeah, I can see that algorithm have some really horrible edge cases. In my first implementation of this algorithm, we
Re: [webkit-dev] Misplaced files
On Aug 27, 2010, at 5:15 PM, Adam Barth wrote: On Fri, Aug 27, 2010 at 4:08 PM, Maciej Stachowiak m...@apple.com wrote: On Aug 27, 2010, at 3:55 PM, Adam Barth wrote: Looking through WebCore/html I noticed the files below. I'm not sure they belong in WebCore/html because they don't appear to be HTML-specific. Rather, they seem like generic web platform APIs (e.g., they could be exposed to SVG or whatever other markup languages we choose to support in the future). Should we move these to WebCore/page, WebCore/dom, or should we make a new location for these sorts of things? I think the File API (which all of these are related to) deserves its own directory right under WebCore. Ok. I can take care of that. Thoughts on names? WebCore/file ? I would say file-api or fileapi or something, since it seems more likely than other cases to get confused with the general concept of files. Regards, Maciej ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
Re: [webkit-dev] Misplaced files
(Sending from the right address) We have bunch of FileSystem (which is a part of File API) related files in WebCore/storage/. Maybe we should move them to the new directory too? On Fri, Aug 27, 2010 at 6:01 PM, Maciej Stachowiak m...@apple.com wrote: On Aug 27, 2010, at 5:15 PM, Adam Barth wrote: On Fri, Aug 27, 2010 at 4:08 PM, Maciej Stachowiak m...@apple.com wrote: On Aug 27, 2010, at 3:55 PM, Adam Barth wrote: Looking through WebCore/html I noticed the files below. I'm not sure they belong in WebCore/html because they don't appear to be HTML-specific. Rather, they seem like generic web platform APIs (e.g., they could be exposed to SVG or whatever other markup languages we choose to support in the future). Should we move these to WebCore/page, WebCore/dom, or should we make a new location for these sorts of things? I think the File API (which all of these are related to) deserves its own directory right under WebCore. Ok. I can take care of that. Thoughts on names? WebCore/file ? I would say file-api or fileapi or something, since it seems more likely than other cases to get confused with the general concept of files. Regards, Maciej ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
Re: [webkit-dev] Misplaced files
On Aug 27, 2010, at 6:19 PM, Kinuko Yasuda wrote: We have bunch of FileSystem (which is a part of File API) related files in WebCore/storage/. Maybe we should move them to the new directory too? Yes. The file-related stuff should all be in one directory, I think. Regards, Maciej On Fri, Aug 27, 2010 at 6:01 PM, Maciej Stachowiak m...@apple.com wrote: On Aug 27, 2010, at 5:15 PM, Adam Barth wrote: On Fri, Aug 27, 2010 at 4:08 PM, Maciej Stachowiak m...@apple.com wrote: On Aug 27, 2010, at 3:55 PM, Adam Barth wrote: Looking through WebCore/html I noticed the files below. I'm not sure they belong in WebCore/html because they don't appear to be HTML-specific. Rather, they seem like generic web platform APIs (e.g., they could be exposed to SVG or whatever other markup languages we choose to support in the future). Should we move these to WebCore/page, WebCore/dom, or should we make a new location for these sorts of things? I think the File API (which all of these are related to) deserves its own directory right under WebCore. Ok. I can take care of that. Thoughts on names? WebCore/file ? I would say file-api or fileapi or something, since it seems more likely than other cases to get confused with the general concept of files. Regards, Maciej ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
Re: [webkit-dev] Misplaced files
On Fri, Aug 27, 2010 at 8:12 PM, Maciej Stachowiak m...@apple.com wrote: On Aug 27, 2010, at 6:19 PM, Kinuko Yasuda wrote: We have bunch of FileSystem (which is a part of File API) related files in WebCore/storage/. Maybe we should move them to the new directory too? Yes. The file-related stuff should all be in one directory, I think. Regards, Maciej The exception being the bits in WebCore/platform/ (just to state the obvious). -Darin On Fri, Aug 27, 2010 at 6:01 PM, Maciej Stachowiak m...@apple.com wrote: On Aug 27, 2010, at 5:15 PM, Adam Barth wrote: On Fri, Aug 27, 2010 at 4:08 PM, Maciej Stachowiak m...@apple.com wrote: On Aug 27, 2010, at 3:55 PM, Adam Barth wrote: Looking through WebCore/html I noticed the files below. I'm not sure they belong in WebCore/html because they don't appear to be HTML-specific. Rather, they seem like generic web platform APIs (e.g., they could be exposed to SVG or whatever other markup languages we choose to support in the future). Should we move these to WebCore/page, WebCore/dom, or should we make a new location for these sorts of things? I think the File API (which all of these are related to) deserves its own directory right under WebCore. Ok. I can take care of that. Thoughts on names? WebCore/file ? I would say file-api or fileapi or something, since it seems more likely than other cases to get confused with the general concept of files. Regards, Maciej ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev ___ webkit-dev mailing list webkit-dev@lists.webkit.org http://lists.webkit.org/mailman/listinfo.cgi/webkit-dev
