diff options
Diffstat (limited to 'Source/WebCore/platform/graphics/gpu')
28 files changed, 5142 insertions, 0 deletions
diff --git a/Source/WebCore/platform/graphics/gpu/DrawingBuffer.cpp b/Source/WebCore/platform/graphics/gpu/DrawingBuffer.cpp new file mode 100644 index 0000000..d2415ca --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/DrawingBuffer.cpp @@ -0,0 +1,253 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#if ENABLE(ACCELERATED_2D_CANVAS) || ENABLE(3D_CANVAS) + +#include "DrawingBuffer.h" + +#include "Extensions3D.h" + +namespace WebCore { + +PassRefPtr<DrawingBuffer> DrawingBuffer::create(GraphicsContext3D* context, const IntSize& size) +{ + RefPtr<DrawingBuffer> drawingBuffer = adoptRef(new DrawingBuffer(context, size)); + Extensions3D* extensions = context->getExtensions(); + bool multisampleSupported = extensions->supports("GL_ANGLE_framebuffer_blit") && extensions->supports("GL_ANGLE_framebuffer_multisample"); + if (multisampleSupported) { + extensions->ensureEnabled("GL_ANGLE_framebuffer_blit"); + extensions->ensureEnabled("GL_ANGLE_framebuffer_multisample"); + } + drawingBuffer->m_multisampleExtensionSupported = multisampleSupported; + return (drawingBuffer->m_context) ? drawingBuffer.release() : 0; +} + +void DrawingBuffer::clear() +{ + if (!m_context) + return; + + m_context->makeContextCurrent(); + m_context->deleteTexture(m_colorBuffer); + m_colorBuffer = 0; + + if (m_multisampleColorBuffer) { + m_context->deleteRenderbuffer(m_multisampleColorBuffer); + m_multisampleColorBuffer = 0; + } + + if (m_multisampleDepthStencilBuffer) { + m_context->deleteRenderbuffer(m_multisampleDepthStencilBuffer); + m_multisampleDepthStencilBuffer = 0; + } + + if (m_depthStencilBuffer) { + m_context->deleteRenderbuffer(m_depthStencilBuffer); + m_depthStencilBuffer = 0; + } + + if (m_multisampleFBO) { + m_context->bindFramebuffer(GraphicsContext3D::FRAMEBUFFER, m_multisampleFBO); + m_context->deleteFramebuffer(m_multisampleFBO); + m_multisampleFBO = 0; + } + + m_context->bindFramebuffer(GraphicsContext3D::FRAMEBUFFER, m_fbo); + m_context->deleteFramebuffer(m_fbo); + m_fbo = 0; + + m_context.clear(); +} + +void DrawingBuffer::reset(const IntSize& newSize) +{ + if (m_size == newSize) + return; + m_size = newSize; + + if (!m_context) + return; + + m_context->makeContextCurrent(); + + const GraphicsContext3D::Attributes& attributes = m_context->getContextAttributes(); + unsigned long internalColorFormat, colorFormat, internalDepthStencilFormat = 0; + if (attributes.alpha) { + internalColorFormat = GraphicsContext3D::RGBA; + colorFormat = GraphicsContext3D::RGBA; + } else { + internalColorFormat = GraphicsContext3D::RGB; + colorFormat = GraphicsContext3D::RGB; + } + if (attributes.stencil || attributes.depth) { + // We don't allow the logic where stencil is required and depth is not. + // See GraphicsContext3D constructor. + if (attributes.stencil && attributes.depth) + internalDepthStencilFormat = GraphicsContext3D::DEPTH_STENCIL; + else + internalDepthStencilFormat = GraphicsContext3D::DEPTH_COMPONENT; + } + + // resize multisample FBO + if (multisample()) { + int maxSampleCount = 0; + + m_context->getIntegerv(Extensions3D::MAX_SAMPLES, &maxSampleCount); + int sampleCount = std::min(8, maxSampleCount); + + m_context->bindFramebuffer(GraphicsContext3D::FRAMEBUFFER, m_multisampleFBO); + + m_context->bindRenderbuffer(GraphicsContext3D::RENDERBUFFER, m_multisampleColorBuffer); + m_context->getExtensions()->renderbufferStorageMultisample(GraphicsContext3D::RENDERBUFFER, sampleCount, internalColorFormat, m_size.width(), m_size.height()); + m_context->framebufferRenderbuffer(GraphicsContext3D::FRAMEBUFFER, GraphicsContext3D::COLOR_ATTACHMENT0, GraphicsContext3D::RENDERBUFFER, m_multisampleColorBuffer); + if (attributes.stencil || attributes.depth) { + m_context->bindRenderbuffer(GraphicsContext3D::RENDERBUFFER, m_multisampleDepthStencilBuffer); + m_context->getExtensions()->renderbufferStorageMultisample(GraphicsContext3D::RENDERBUFFER, sampleCount, internalDepthStencilFormat, m_size.width(), m_size.height()); + if (attributes.stencil) + m_context->framebufferRenderbuffer(GraphicsContext3D::FRAMEBUFFER, GraphicsContext3D::STENCIL_ATTACHMENT, GraphicsContext3D::RENDERBUFFER, m_multisampleDepthStencilBuffer); + if (attributes.depth) + m_context->framebufferRenderbuffer(GraphicsContext3D::FRAMEBUFFER, GraphicsContext3D::DEPTH_ATTACHMENT, GraphicsContext3D::RENDERBUFFER, m_multisampleDepthStencilBuffer); + } + m_context->bindRenderbuffer(GraphicsContext3D::RENDERBUFFER, 0); + if (m_context->checkFramebufferStatus(GraphicsContext3D::FRAMEBUFFER) != GraphicsContext3D::FRAMEBUFFER_COMPLETE) { + // Cleanup + clear(); + return; + } + } + + // resize regular FBO + m_context->bindFramebuffer(GraphicsContext3D::FRAMEBUFFER, m_fbo); + + m_context->bindTexture(GraphicsContext3D::TEXTURE_2D, m_colorBuffer); + m_context->texImage2DResourceSafe(GraphicsContext3D::TEXTURE_2D, 0, internalColorFormat, m_size.width(), m_size.height(), 0, colorFormat, GraphicsContext3D::UNSIGNED_BYTE); + m_context->framebufferTexture2D(GraphicsContext3D::FRAMEBUFFER, GraphicsContext3D::COLOR_ATTACHMENT0, GraphicsContext3D::TEXTURE, m_colorBuffer, 0); + m_context->bindTexture(GraphicsContext3D::TEXTURE_2D, 0); + if (!multisample() && (attributes.stencil || attributes.depth)) { + m_context->bindRenderbuffer(GraphicsContext3D::RENDERBUFFER, m_depthStencilBuffer); + m_context->renderbufferStorage(GraphicsContext3D::RENDERBUFFER, internalDepthStencilFormat, m_size.width(), m_size.height()); + if (attributes.stencil) + m_context->framebufferRenderbuffer(GraphicsContext3D::FRAMEBUFFER, GraphicsContext3D::STENCIL_ATTACHMENT, GraphicsContext3D::RENDERBUFFER, m_depthStencilBuffer); + if (attributes.depth) + m_context->framebufferRenderbuffer(GraphicsContext3D::FRAMEBUFFER, GraphicsContext3D::DEPTH_ATTACHMENT, GraphicsContext3D::RENDERBUFFER, m_depthStencilBuffer); + m_context->bindRenderbuffer(GraphicsContext3D::RENDERBUFFER, 0); + } + if (m_context->checkFramebufferStatus(GraphicsContext3D::FRAMEBUFFER) != GraphicsContext3D::FRAMEBUFFER_COMPLETE) { + // Cleanup + clear(); + return; + } + + if (multisample()) + m_context->bindFramebuffer(GraphicsContext3D::FRAMEBUFFER, m_multisampleFBO); + + if (!m_context->getExtensions()->supports("GL_CHROMIUM_resource_safe")) { + // Initialize renderbuffers (depth/stencil). + float clearDepth = 0; + int clearStencil = 0; + unsigned char depthMask = true; + unsigned int stencilMask = 0xffffffff; + unsigned char isScissorEnabled = false; + unsigned long clearMask = 0; + if (attributes.depth) { + m_context->getFloatv(GraphicsContext3D::DEPTH_CLEAR_VALUE, &clearDepth); + m_context->clearDepth(1); + m_context->getBooleanv(GraphicsContext3D::DEPTH_WRITEMASK, &depthMask); + m_context->depthMask(true); + clearMask |= GraphicsContext3D::DEPTH_BUFFER_BIT; + } + if (attributes.stencil) { + m_context->getIntegerv(GraphicsContext3D::STENCIL_CLEAR_VALUE, &clearStencil); + m_context->clearStencil(0); + m_context->getIntegerv(GraphicsContext3D::STENCIL_WRITEMASK, reinterpret_cast<int*>(&stencilMask)); + m_context->stencilMaskSeparate(GraphicsContext3D::FRONT, 0xffffffff); + clearMask |= GraphicsContext3D::STENCIL_BUFFER_BIT; + } + if (clearMask) { + isScissorEnabled = m_context->isEnabled(GraphicsContext3D::SCISSOR_TEST); + m_context->disable(GraphicsContext3D::SCISSOR_TEST); + + m_context->clear(clearMask); + + if (attributes.depth) { + m_context->clearDepth(clearDepth); + m_context->depthMask(depthMask); + } + if (attributes.stencil) { + m_context->clearStencil(clearStencil); + m_context->stencilMaskSeparate(GraphicsContext3D::FRONT, stencilMask); + } + if (isScissorEnabled) + m_context->enable(GraphicsContext3D::SCISSOR_TEST); + else + m_context->disable(GraphicsContext3D::SCISSOR_TEST); + } + } + + m_context->flush(); + + didReset(); +} + +void DrawingBuffer::commit(long x, long y, long width, long height) +{ + if (!m_context) + return; + + if (width < 0) + width = m_size.width(); + if (height < 0) + height = m_size.height(); + + m_context->makeContextCurrent(); + + if (m_multisampleFBO) { + m_context->bindFramebuffer(Extensions3D::READ_FRAMEBUFFER, m_multisampleFBO); + m_context->bindFramebuffer(Extensions3D::DRAW_FRAMEBUFFER, m_fbo); + m_context->getExtensions()->blitFramebuffer(x, y, width, height, x, y, width, height, GraphicsContext3D::COLOR_BUFFER_BIT, GraphicsContext3D::LINEAR); + } + + m_context->bindFramebuffer(GraphicsContext3D::FRAMEBUFFER, m_fbo); +} + +void DrawingBuffer::bind() +{ + if (!m_context) + return; + + m_context->bindFramebuffer(GraphicsContext3D::FRAMEBUFFER, m_multisampleFBO ? m_multisampleFBO : m_fbo); + m_context->viewport(0, 0, m_size.width(), m_size.height()); +} + +} // namespace WebCore + +#endif diff --git a/Source/WebCore/platform/graphics/gpu/DrawingBuffer.h b/Source/WebCore/platform/graphics/gpu/DrawingBuffer.h new file mode 100644 index 0000000..9f79889 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/DrawingBuffer.h @@ -0,0 +1,124 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef DrawingBuffer_h +#define DrawingBuffer_h + +#include "GraphicsContext3D.h" +#include "GraphicsLayer.h" +#include "IntSize.h" + +#include <wtf/Noncopyable.h> +#include <wtf/OwnPtr.h> +#include <wtf/PassOwnPtr.h> +#if PLATFORM(MAC) +#include <wtf/RetainPtr.h> +#endif + +namespace WebCore { + +#if PLATFORM(CHROMIUM) +struct DrawingBufferInternal; +#endif + +// Manages a rendering target (framebuffer + attachment) for a canvas. Can publish its rendering +// results to a PlatformLayer for compositing. +class DrawingBuffer : public RefCounted<DrawingBuffer> { +public: + friend class GraphicsContext3D; + + ~DrawingBuffer(); + + void reset(const IntSize&); + void bind(); + IntSize size() const { return m_size; } + + // Clear all resources from this object, as well as context. Called when context is destroyed + // to prevent invalid accesses to the resources. + void clear(); + + // Copies the multisample color buffer to the normal color buffer and leaves m_fbo bound + void commit(long x = 0, long y = 0, long width = -1, long height = -1); + + bool multisample() const { return m_context && m_context->getContextAttributes().antialias && m_multisampleExtensionSupported; } + + Platform3DObject platformColorBuffer() const; + +#if USE(ACCELERATED_COMPOSITING) + PlatformLayer* platformLayer(); + void publishToPlatformLayer(); +#endif + +#if PLATFORM(CHROMIUM) + class WillPublishCallback : public Noncopyable { + public: + virtual ~WillPublishCallback() { } + + virtual void willPublish() = 0; + }; + + void setWillPublishCallback(PassOwnPtr<WillPublishCallback> callback) { m_callback = callback; } +#endif + + PassRefPtr<GraphicsContext3D> graphicsContext3D() const { return m_context; } + +private: + static PassRefPtr<DrawingBuffer> create(GraphicsContext3D*, const IntSize&); + + DrawingBuffer(GraphicsContext3D*, const IntSize&); + + // Platform specific function called after reset() so each platform can do extra work if needed + void didReset(); + + RefPtr<GraphicsContext3D> m_context; + IntSize m_size; + bool m_multisampleExtensionSupported; + Platform3DObject m_fbo; + Platform3DObject m_colorBuffer; + Platform3DObject m_depthStencilBuffer; + + // For multisampling + Platform3DObject m_multisampleFBO; + Platform3DObject m_multisampleColorBuffer; + Platform3DObject m_multisampleDepthStencilBuffer; + +#if PLATFORM(CHROMIUM) + OwnPtr<WillPublishCallback> m_callback; + OwnPtr<DrawingBufferInternal> m_internal; +#endif + +#if PLATFORM(MAC) + RetainPtr<WebGLLayer> m_platformLayer; +#endif +}; + +} // namespace WebCore + +#endif // DrawingBuffer_h diff --git a/Source/WebCore/platform/graphics/gpu/LoopBlinnClassifier.cpp b/Source/WebCore/platform/graphics/gpu/LoopBlinnClassifier.cpp new file mode 100644 index 0000000..672b4d7 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/LoopBlinnClassifier.cpp @@ -0,0 +1,126 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#if ENABLE(ACCELERATED_2D_CANVAS) + +#include "LoopBlinnClassifier.h" + +#include "LoopBlinnMathUtils.h" + +namespace WebCore { + +using LoopBlinnMathUtils::approxEqual; +using LoopBlinnMathUtils::roundToZero; + +LoopBlinnClassifier::Result LoopBlinnClassifier::classify(const FloatPoint& c0, + const FloatPoint& c1, + const FloatPoint& c2, + const FloatPoint& c3) +{ + // Consult the chapter for the definitions of the following + // (terse) variable names. Note that the b0..b3 coordinates are + // homogeneous, so the "z" value (actually the w coordinate) must + // be 1.0. + FloatPoint3D b0(c0.x(), c0.y(), 1.0f); + FloatPoint3D b1(c1.x(), c1.y(), 1.0f); + FloatPoint3D b2(c2.x(), c2.y(), 1.0f); + FloatPoint3D b3(c3.x(), c3.y(), 1.0f); + + // Compute a1..a3. + float a1 = b0 * b3.cross(b2); + float a2 = b1 * b0.cross(b3); + float a3 = b2 * b1.cross(b0); + + // Compute d1..d3. + float d1 = a1 - 2 * a2 + 3 * a3; + float d2 = -a2 + 3 * a3; + float d3 = 3 * a3; + + // Experimentation has shown that the texture coordinates computed + // from these values quickly become huge, leading to roundoff errors + // and artifacts in the shader. It turns out that if we normalize + // the vector defined by (d1, d2, d3), this fixes the problem of the + // texture coordinates getting too large without affecting the + // classification results. + FloatPoint3D nd(d1, d2, d3); + nd.normalize(); + d1 = nd.x(); + d2 = nd.y(); + d3 = nd.z(); + + // Compute the discriminant. + // term0 is a common term in the computation which helps decide + // which way to classify the cusp case: as serpentine or loop. + float term0 = (3 * d2 * d2 - 4 * d1 * d3); + float discriminant = d1 * d1 * term0; + + // Experimentation has also shown that when the classification is + // near the boundary between one curve type and another, the shader + // becomes numerically unstable, particularly with the cusp case. + // Correct for this by rounding d1..d3 and the discriminant to zero + // when they get near it. + d1 = roundToZero(d1); + d2 = roundToZero(d2); + d3 = roundToZero(d3); + discriminant = roundToZero(discriminant); + + // Do the classification. + if (approxEqual(b0, b1) && approxEqual(b0, b2) && approxEqual(b0, b3)) + return Result(kPoint, d1, d2, d3); + + if (!discriminant) { + if (!d1 && !d2) { + if (!d3) + return Result(kLine, d1, d2, d3); + return Result(kQuadratic, d1, d2, d3); + } + + if (!d1) + return Result(kCusp, d1, d2, d3); + + // This is the boundary case described in Loop and Blinn's + // SIGGRAPH '05 paper of a cusp with inflection at infinity. + // Because term0 might not be exactly 0, we decide between using + // the serpentine and loop cases depending on its sign to avoid + // taking the square root of a negative number when computing the + // cubic texture coordinates. + if (term0 < 0) + return Result(kLoop, d1, d2, d3); + + return Result(kSerpentine, d1, d2, d3); + } + + if (discriminant > 0) + return Result(kSerpentine, d1, d2, d3); + + // discriminant < 0 + return Result(kLoop, d1, d2, d3); +} + +} // namespace WebCore + +#endif diff --git a/Source/WebCore/platform/graphics/gpu/LoopBlinnClassifier.h b/Source/WebCore/platform/graphics/gpu/LoopBlinnClassifier.h new file mode 100644 index 0000000..c665844 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/LoopBlinnClassifier.h @@ -0,0 +1,84 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +// Cubic curve classification algorithm from "Rendering Vector Art on +// the GPU" by Loop and Blinn, GPU Gems 3, Chapter 25: +// http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html . + +#ifndef LoopBlinnClassifier_h +#define LoopBlinnClassifier_h + +#include <wtf/Noncopyable.h> + +namespace WebCore { + +class FloatPoint; + +// Classifies cubic curves into specific types. +class LoopBlinnClassifier : public Noncopyable { +public: + // The types of cubic curves. + enum CurveType { + kSerpentine, + kCusp, + kLoop, + kQuadratic, + kLine, + kPoint + }; + + // The result of the classifier. + struct Result { + public: + Result(CurveType inputCurveType, float inputD1, float inputD2, float inputD3) + : curveType(inputCurveType) + , d1(inputD1) + , d2(inputD2) + , d3(inputD3) { } + + CurveType curveType; + + // These are coefficients used later in the computation of + // texture coordinates per vertex. + float d1; + float d2; + float d3; + }; + + // Classifies the given cubic bezier curve starting at c0, ending + // at c3, and affected by control points c1 and c2. + static Result classify(const FloatPoint& c0, + const FloatPoint& c1, + const FloatPoint& c2, + const FloatPoint& c3); + +private: + // This class does not need to be instantiated. + LoopBlinnClassifier() { } +}; + +} // namespace WebCore + +#endif // LoopBlinnClassifier_h diff --git a/Source/WebCore/platform/graphics/gpu/LoopBlinnConstants.h b/Source/WebCore/platform/graphics/gpu/LoopBlinnConstants.h new file mode 100644 index 0000000..1997d9f --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/LoopBlinnConstants.h @@ -0,0 +1,40 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LoopBlinnConstants_h +#define LoopBlinnConstants_h + +namespace WebCore { +namespace LoopBlinnConstants { + +enum FillSide { + LeftSide, + RightSide +}; + +} // namespace LoopBlinnConstants +} // namespace WebCore + +#endif // LoopBlinnConstants_h diff --git a/Source/WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp b/Source/WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp new file mode 100644 index 0000000..1517a67 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp @@ -0,0 +1,279 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#if ENABLE(ACCELERATED_2D_CANVAS) + +#include "LoopBlinnLocalTriangulator.h" + +#include "LoopBlinnMathUtils.h" +#include <algorithm> + +namespace WebCore { + +using LoopBlinnMathUtils::approxEqual; +using LoopBlinnMathUtils::linesIntersect; +using LoopBlinnMathUtils::pointInTriangle; + +bool LoopBlinnLocalTriangulator::Triangle::contains(LoopBlinnLocalTriangulator::Vertex* v) +{ + return indexForVertex(v) >= 0; +} + +LoopBlinnLocalTriangulator::Vertex* LoopBlinnLocalTriangulator::Triangle::nextVertex(LoopBlinnLocalTriangulator::Vertex* current, bool traverseCounterClockwise) +{ + int index = indexForVertex(current); + ASSERT(index >= 0); + if (traverseCounterClockwise) + ++index; + else + --index; + if (index < 0) + index += 3; + else + index = index % 3; + return m_vertices[index]; +} + +int LoopBlinnLocalTriangulator::Triangle::indexForVertex(LoopBlinnLocalTriangulator::Vertex* vertex) +{ + for (int i = 0; i < 3; ++i) + if (m_vertices[i] == vertex) + return i; + return -1; +} + +void LoopBlinnLocalTriangulator::Triangle::makeCounterClockwise() +{ + // Possibly swaps two vertices so that the triangle's vertices are + // always specified in counterclockwise order. This orders the + // vertices canonically when walking the interior edges from the + // start to the end vertex. + FloatPoint3D point0(m_vertices[0]->xyCoordinates()); + FloatPoint3D point1(m_vertices[1]->xyCoordinates()); + FloatPoint3D point2(m_vertices[2]->xyCoordinates()); + FloatPoint3D crossProduct = (point1 - point0).cross(point2 - point0); + if (crossProduct.z() < 0) + std::swap(m_vertices[1], m_vertices[2]); +} + +LoopBlinnLocalTriangulator::LoopBlinnLocalTriangulator() +{ + reset(); +} + +void LoopBlinnLocalTriangulator::reset() +{ + m_numberOfTriangles = 0; + m_numberOfInteriorVertices = 0; + for (int i = 0; i < 4; ++i) { + m_interiorVertices[i] = 0; + m_vertices[i].resetFlags(); + } +} + +void LoopBlinnLocalTriangulator::triangulate(InsideEdgeComputation computeInsideEdges, LoopBlinnConstants::FillSide sideToFill) +{ + triangulateHelper(sideToFill); + + if (computeInsideEdges == ComputeInsideEdges) { + // We need to compute which vertices describe the path along the + // interior portion of the shape, to feed these vertices to the + // more general tessellation algorithm. It is possible that we + // could determine this directly while producing triangles above. + // Here we try to do it generally just by examining the triangles + // that have already been produced. We walk around them in a + // specific direction determined by which side of the curve is + // being filled. We ignore the interior vertex unless it is also + // the ending vertex, and skip the edges shared between two + // triangles. + Vertex* v = &m_vertices[0]; + addInteriorVertex(v); + int numSteps = 0; + while (!v->end() && numSteps < 4) { + // Find the next vertex according to the above rules + bool gotNext = false; + for (int i = 0; i < numberOfTriangles() && !gotNext; ++i) { + Triangle* tri = getTriangle(i); + if (tri->contains(v)) { + Vertex* next = tri->nextVertex(v, sideToFill == LoopBlinnConstants::RightSide); + if (!next->marked() && !isSharedEdge(v, next) && (!next->interior() || next->end())) { + addInteriorVertex(next); + v = next; + // Break out of for loop + gotNext = true; + } + } + } + ++numSteps; + } + if (!v->end()) { + // Something went wrong with the above algorithm; add the last + // vertex to the interior vertices anyway. (FIXME: should we + // add an assert here and do more extensive testing?) + addInteriorVertex(&m_vertices[3]); + } + } +} + +void LoopBlinnLocalTriangulator::triangulateHelper(LoopBlinnConstants::FillSide sideToFill) +{ + reset(); + + m_vertices[3].setEnd(true); + + // First test for degenerate cases. + for (int i = 0; i < 4; ++i) { + for (int j = i + 1; j < 4; ++j) { + if (approxEqual(m_vertices[i].xyCoordinates(), m_vertices[j].xyCoordinates())) { + // Two of the vertices are coincident, so we can eliminate at + // least one triangle. We might be able to eliminate the other + // as well, but this seems sufficient to avoid degenerate + // triangulations. + int indices[3] = { 0 }; + int index = 0; + for (int k = 0; k < 4; ++k) + if (k != j) + indices[index++] = k; + addTriangle(&m_vertices[indices[0]], + &m_vertices[indices[1]], + &m_vertices[indices[2]]); + return; + } + } + } + + // See whether any of the points are fully contained in the + // triangle defined by the other three. + for (int i = 0; i < 4; ++i) { + int indices[3] = { 0 }; + int index = 0; + for (int j = 0; j < 4; ++j) + if (i != j) + indices[index++] = j; + if (pointInTriangle(m_vertices[i].xyCoordinates(), + m_vertices[indices[0]].xyCoordinates(), + m_vertices[indices[1]].xyCoordinates(), + m_vertices[indices[2]].xyCoordinates())) { + // Produce three triangles surrounding this interior vertex. + for (int j = 0; j < 3; ++j) + addTriangle(&m_vertices[indices[j % 3]], + &m_vertices[indices[(j + 1) % 3]], + &m_vertices[i]); + // Mark the interior vertex so we ignore it if trying to trace + // the interior edge. + m_vertices[i].setInterior(true); + return; + } + } + + // There are only a few permutations of the vertices, ignoring + // rotations, which are irrelevant: + // + // 0--3 0--2 0--3 0--1 0--2 0--1 + // | | | | | | | | | | | | + // | | | | | | | | | | | | + // 1--2 1--3 2--1 2--3 3--1 3--2 + // + // Note that three of these are reflections of each other. + // Therefore there are only three possible triangulations: + // + // 0--3 0--2 0--3 + // |\ | |\ | |\ | + // | \| | \| | \| + // 1--2 1--3 2--1 + // + // From which we can choose by seeing which of the potential + // diagonals intersect. Note that we choose the shortest diagonal + // to split the quad. + if (linesIntersect(m_vertices[0].xyCoordinates(), + m_vertices[2].xyCoordinates(), + m_vertices[1].xyCoordinates(), + m_vertices[3].xyCoordinates())) { + if ((m_vertices[2].xyCoordinates() - m_vertices[0].xyCoordinates()).diagonalLengthSquared() < + (m_vertices[3].xyCoordinates() - m_vertices[1].xyCoordinates()).diagonalLengthSquared()) { + addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[2]); + addTriangle(&m_vertices[0], &m_vertices[2], &m_vertices[3]); + } else { + addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[3]); + addTriangle(&m_vertices[1], &m_vertices[2], &m_vertices[3]); + } + } else if (linesIntersect(m_vertices[0].xyCoordinates(), + m_vertices[3].xyCoordinates(), + m_vertices[1].xyCoordinates(), + m_vertices[2].xyCoordinates())) { + if ((m_vertices[3].xyCoordinates() - m_vertices[0].xyCoordinates()).diagonalLengthSquared() < + (m_vertices[2].xyCoordinates() - m_vertices[1].xyCoordinates()).diagonalLengthSquared()) { + addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[3]); + addTriangle(&m_vertices[0], &m_vertices[3], &m_vertices[2]); + } else { + addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[2]); + addTriangle(&m_vertices[2], &m_vertices[1], &m_vertices[3]); + } + } else { + // Lines (0->1), (2->3) intersect -- or should, modulo numerical + // precision issues + if ((m_vertices[1].xyCoordinates() - m_vertices[0].xyCoordinates()).diagonalLengthSquared() < + (m_vertices[3].xyCoordinates() - m_vertices[2].xyCoordinates()).diagonalLengthSquared()) { + addTriangle(&m_vertices[0], &m_vertices[2], &m_vertices[1]); + addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[3]); + } else { + addTriangle(&m_vertices[0], &m_vertices[2], &m_vertices[3]); + addTriangle(&m_vertices[3], &m_vertices[2], &m_vertices[1]); + } + } +} + +void LoopBlinnLocalTriangulator::addTriangle(Vertex* v0, Vertex* v1, Vertex* v2) +{ + ASSERT(m_numberOfTriangles < 3); + m_triangles[m_numberOfTriangles++].setVertices(v0, v1, v2); +} + +void LoopBlinnLocalTriangulator::addInteriorVertex(Vertex* v) +{ + ASSERT(m_numberOfInteriorVertices < 4); + m_interiorVertices[m_numberOfInteriorVertices++] = v; + v->setMarked(true); +} + +bool LoopBlinnLocalTriangulator::isSharedEdge(Vertex* v0, Vertex* v1) +{ + bool haveEdge01 = false; + bool haveEdge10 = false; + for (int i = 0; i < numberOfTriangles(); ++i) { + Triangle* tri = getTriangle(i); + if (tri->contains(v0) && tri->nextVertex(v0, true) == v1) + haveEdge01 = true; + if (tri->contains(v1) && tri->nextVertex(v1, true) == v0) + haveEdge10 = true; + } + return haveEdge01 && haveEdge10; +} + +} // namespace WebCore + +#endif diff --git a/Source/WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.h b/Source/WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.h new file mode 100644 index 0000000..ea3d7e3 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.h @@ -0,0 +1,268 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LoopBlinnLocalTriangulator_h +#define LoopBlinnLocalTriangulator_h + +#include "FloatPoint.h" +#include "FloatPoint3D.h" +#include "LoopBlinnConstants.h" +#include <wtf/Assertions.h> +#include <wtf/Noncopyable.h> + +namespace WebCore { + +// Performs a localized triangulation of the triangle mesh +// corresponding to the four control point vertices of a cubic curve +// segment. +class LoopBlinnLocalTriangulator : public Noncopyable { +public: + // The vertices that the triangulator operates upon, containing both + // the position information as well as the cubic texture + // coordinates. + class Vertex : public Noncopyable { + public: + Vertex() + { + resetFlags(); + } + + const FloatPoint& xyCoordinates() const + { + return m_xyCoordinates; + } + + const FloatPoint3D& klmCoordinates() const + { + return m_klmCoordinates; + } + + // Sets the position and texture coordinates of the vertex. + void set(float x, float y, + float k, float l, float m) + { + m_xyCoordinates.set(x, y); + m_klmCoordinates.set(k, l, m); + } + + // Flags for walking from the start vertex to the end vertex. + bool end() + { + return m_end; + } + + void setEnd(bool end) + { + m_end = end; + } + + bool marked() + { + return m_marked; + } + + void setMarked(bool marked) + { + m_marked = marked; + } + + bool interior() + { + return m_interior; + } + + void setInterior(bool interior) + { + m_interior = interior; + } + + void resetFlags() + { + m_end = false; + m_marked = false; + m_interior = false; + } + + private: + // 2D coordinates of the vertex in the plane. + FloatPoint m_xyCoordinates; + // Cubic texture coordinates for rendering the curve. + FloatPoint3D m_klmCoordinates; + + // Flags for walking from the start vertex to the end vertex. + bool m_end; + bool m_marked; + bool m_interior; + }; + + // The triangles the Triangulator produces. + class Triangle { + public: + Triangle() + { + m_vertices[0] = 0; + m_vertices[1] = 0; + m_vertices[2] = 0; + } + + // Gets the vertex at the given index, 0 <= index < 3. + Vertex* getVertex(int index) + { + ASSERT(index >= 0 && index < 3); + return m_vertices[index]; + } + + // Returns true if this triangle contains the given vertex (by + // identity, not geometrically). + bool contains(Vertex* v); + + // Returns the vertex following the current one in the specified + // direction, counterclockwise or clockwise. + Vertex* nextVertex(Vertex* current, bool traverseCounterClockwise); + + // Sets the vertices of this triangle, potentially reordering them + // to produce a canonical orientation. + void setVertices(Vertex* v0, + Vertex* v1, + Vertex* v2) + { + m_vertices[0] = v0; + m_vertices[1] = v1; + m_vertices[2] = v2; + makeCounterClockwise(); + } + + private: + // Returns the index [0..2] associated with the given vertex, or + // -1 if not found. + int indexForVertex(Vertex* vertex); + + // Reorders the vertices in this triangle to make them + // counterclockwise when viewed in the 2D plane, in order to + // achieve a canonical ordering. + void makeCounterClockwise(); + + // Note: these are raw pointers because they point to the + // m_vertices contained in the surrounding triangulator. + Vertex* m_vertices[3]; + }; + + LoopBlinnLocalTriangulator(); + + // Resets the triangulator's state. After each triangulation and + // before the next, call this to re-initialize the internal + // vertices' state. + void reset(); + + // Returns a mutable vertex stored in the triangulator. Use this to + // set up the vertices before a triangulation. + Vertex* getVertex(int index) + { + ASSERT(index >= 0 && index < 4); + return &m_vertices[index]; + } + + enum InsideEdgeComputation { + ComputeInsideEdges, + DontComputeInsideEdges + }; + + // Once the vertices' contents have been set up, call triangulate() + // to recompute the triangles. + // + // If computeInsideEdges is ComputeInsideEdges, then sideToFill + // will be used to determine which side of the cubic curve defined + // by the four control points is to be filled. + // + // The triangulation obeys the following guarantees: + // - If the convex hull is a quadrilateral, then the shortest edge + // will be chosen for the cut into two triangles. + // - If one of the vertices is contained in the triangle spanned + // by the other three, three triangles will be produced. + void triangulate(InsideEdgeComputation computeInsideEdges, + LoopBlinnConstants::FillSide sideToFill); + + // Number of triangles computed by triangulate(). + int numberOfTriangles() const + { + return m_numberOfTriangles; + } + + // Returns the computed triangle at index, 0 <= index < numberOfTriangles(). + Triangle* getTriangle(int index) + { + ASSERT(index >= 0 && index < m_numberOfTriangles); + return &m_triangles[index]; + } + + // Number of vertices facing the inside of the shape, if + // ComputeInsideEdges was passed when triangulate() was called. + int numberOfInteriorVertices() const + { + return m_numberOfInteriorVertices; + } + + // Fetches the given interior vertex, 0 <= index < numberOfInteriorVertices(). + Vertex* getInteriorVertex(int index) + { + ASSERT(index >= 0 && index < m_numberOfInteriorVertices); + return m_interiorVertices[index]; + } + +private: + void triangulateHelper(LoopBlinnConstants::FillSide sideToFill); + + // Adds a triangle to the triangulation. + void addTriangle(Vertex* v0, Vertex* v1, Vertex* v2); + + // Adds a vertex to the list of interior vertices. + void addInteriorVertex(Vertex* v); + + // Indicates whether the edge between vertex v0 and v1 is shared + // between two or more triangles. + bool isSharedEdge(Vertex* v0, Vertex* v1); + + // The vertices being triangulated. + Vertex m_vertices[4]; + + // The vertices corresponding to the edges facing the inside of the + // shape, in order from the start vertex to the end vertex. The more + // general triangulation algorithm tessellates this interior region. + Vertex* m_interiorVertices[4]; + // The number of interior vertices that are valid for the current + // triangulation. + int m_numberOfInteriorVertices; + + // There can be at most three triangles computed by this local + // algorithm, which occurs when one of the vertices is contained in + // the triangle spanned by the other three. Most of the time the + // algorithm computes two triangles. + Triangle m_triangles[3]; + int m_numberOfTriangles; +}; + +} // namespace WebCore + +#endif // LoopBlinnLocalTriangulator_h diff --git a/Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp b/Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp new file mode 100644 index 0000000..5b155a5 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp @@ -0,0 +1,568 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#if ENABLE(ACCELERATED_2D_CANVAS) + +#include "LoopBlinnMathUtils.h" + +#include "FloatPoint.h" +#include <algorithm> +#include <wtf/MathExtras.h> + +namespace WebCore { +namespace LoopBlinnMathUtils { + +namespace { + +// Utility functions local to this file. +int orientation(const FloatPoint& p1, + const FloatPoint& p2, + const FloatPoint& p3) +{ + float crossProduct = (p2.y() - p1.y()) * (p3.x() - p2.x()) - (p3.y() - p2.y()) * (p2.x() - p1.x()); + return (crossProduct < 0.0f) ? -1 : ((crossProduct > 0.0f) ? 1 : 0); +} + +bool edgeEdgeTest(const FloatSize& v0Delta, + const FloatPoint& v0, + const FloatPoint& u0, + const FloatPoint& u1) +{ + // This edge to edge test is based on Franlin Antonio's gem: "Faster + // Line Segment Intersection", in Graphics Gems III, pp. 199-202. + float ax = v0Delta.width(); + float ay = v0Delta.height(); + float bx = u0.x() - u1.x(); + float by = u0.y() - u1.y(); + float cx = v0.x() - u0.x(); + float cy = v0.y() - u0.y(); + float f = ay * bx - ax * by; + float d = by * cx - bx * cy; + if ((f > 0 && d >= 0 && d <= f) || (f < 0 && d <= 0 && d >= f)) { + float e = ax * cy - ay * cx; + + // This additional test avoids reporting coincident edges, which + // is the behavior we want. + if (approxEqual(e, 0) || approxEqual(f, 0) || approxEqual(e, f)) + return false; + + if (f > 0) + return e >= 0 && e <= f; + + return e <= 0 && e >= f; + } + return false; +} + +bool edgeAgainstTriangleEdges(const FloatPoint& v0, + const FloatPoint& v1, + const FloatPoint& u0, + const FloatPoint& u1, + const FloatPoint& u2) +{ + FloatSize delta = v1 - v0; + // Test edge u0, u1 against v0, v1. + if (edgeEdgeTest(delta, v0, u0, u1)) + return true; + // Test edge u1, u2 against v0, v1. + if (edgeEdgeTest(delta, v0, u1, u2)) + return true; + // Test edge u2, u1 against v0, v1. + if (edgeEdgeTest(delta, v0, u2, u0)) + return true; + return false; +} + +// A roundoff factor in the cubic classification and texture coordinate +// generation algorithms. It primarily determines the handling of corner +// cases during the classification process. Be careful when adjusting it; +// it has been determined empirically to work well. When changing it, you +// should look in particular at shapes that contain quadratic curves and +// ensure they still look smooth. Once pixel tests are running against this +// algorithm, they should provide sufficient coverage to ensure that +// adjusting the constant won't break anything. +const float Epsilon = 5.0e-4f; + +} // anonymous namespace + +// Exported routines + +float roundToZero(float val) +{ + if (val < Epsilon && val > -Epsilon) + return 0; + return val; +} + +bool approxEqual(const FloatPoint& v0, const FloatPoint& v1) +{ + return (v0 - v1).diagonalLengthSquared() < Epsilon * Epsilon; +} + +bool approxEqual(const FloatPoint3D& v0, const FloatPoint3D& v1) +{ + return (v0 - v1).lengthSquared() < Epsilon * Epsilon; +} + +bool approxEqual(float f0, float f1) +{ + return fabsf(f0 - f1) < Epsilon; +} + +bool linesIntersect(const FloatPoint& p1, + const FloatPoint& q1, + const FloatPoint& p2, + const FloatPoint& q2) +{ + return (orientation(p1, q1, p2) != orientation(p1, q1, q2) + && orientation(p2, q2, p1) != orientation(p2, q2, q1)); +} + +bool pointInTriangle(const FloatPoint& point, + const FloatPoint& a, + const FloatPoint& b, + const FloatPoint& c) +{ + // Algorithm from http://www.blackpawn.com/texts/pointinpoly/default.html + float x0 = c.x() - a.x(); + float y0 = c.y() - a.y(); + float x1 = b.x() - a.x(); + float y1 = b.y() - a.y(); + float x2 = point.x() - a.x(); + float y2 = point.y() - a.y(); + + float dot00 = x0 * x0 + y0 * y0; + float dot01 = x0 * x1 + y0 * y1; + float dot02 = x0 * x2 + y0 * y2; + float dot11 = x1 * x1 + y1 * y1; + float dot12 = x1 * x2 + y1 * y2; + float denominator = dot00 * dot11 - dot01 * dot01; + if (!denominator) + // Triangle is zero-area. Treat query point as not being inside. + return false; + // Compute + float inverseDenominator = 1.0f / denominator; + float u = (dot11 * dot02 - dot01 * dot12) * inverseDenominator; + float v = (dot00 * dot12 - dot01 * dot02) * inverseDenominator; + + return (u > 0.0f) && (v > 0.0f) && (u + v < 1.0f); +} + +bool trianglesOverlap(const FloatPoint& a1, + const FloatPoint& b1, + const FloatPoint& c1, + const FloatPoint& a2, + const FloatPoint& b2, + const FloatPoint& c2) +{ + // Derived from coplanar_tri_tri() at + // http://jgt.akpeters.com/papers/ShenHengTang03/tri_tri.html , + // simplified for the 2D case and modified so that overlapping edges + // do not report overlapping triangles. + + // Test all edges of triangle 1 against the edges of triangle 2. + if (edgeAgainstTriangleEdges(a1, b1, a2, b2, c2) + || edgeAgainstTriangleEdges(b1, c1, a2, b2, c2) + || edgeAgainstTriangleEdges(c1, a1, a2, b2, c2)) + return true; + // Finally, test if tri1 is totally contained in tri2 or vice versa. + // The paper above only performs the first two point-in-triangle tests. + // Because we define that triangles sharing a vertex or edge don't + // overlap, we must perform additional tests to see whether one + // triangle is contained in the other. + if (pointInTriangle(a1, a2, b2, c2) + || pointInTriangle(a2, a1, b1, c1) + || pointInTriangle(b1, a2, b2, c2) + || pointInTriangle(b2, a1, b1, c1) + || pointInTriangle(c1, a2, b2, c2) + || pointInTriangle(c2, a1, b1, c1)) + return true; + return false; +} + +namespace { + +// Helper routines for public XRay queries below. All of this code +// originated in Skia; see include/core/ and src/core/, SkScalar.h and +// SkGeometry.{cpp,h}. + +const float NearlyZeroConstant = (1.0f / (1 << 12)); + +bool nearlyZero(float x, float tolerance = NearlyZeroConstant) +{ + ASSERT(tolerance > 0.0f); + return ::fabsf(x) < tolerance; +} + +// Linearly interpolate between a and b, based on t. +// If t is 0, return a; if t is 1, return b; else interpolate. +// t must be [0..1]. +float interpolate(float a, float b, float t) +{ + ASSERT(t >= 0 && t <= 1); + return a + (b - a) * t; +} + +float evaluateCubic(float controlPoint0, float controlPoint1, float controlPoint2, float controlPoint3, float t) +{ + ASSERT(t >= 0 && t <= 1); + + if (!t) + return controlPoint0; + + float ab = interpolate(controlPoint0, controlPoint1, t); + float bc = interpolate(controlPoint1, controlPoint2, t); + float cd = interpolate(controlPoint2, controlPoint3, t); + float abc = interpolate(ab, bc, t); + float bcd = interpolate(bc, cd, t); + return interpolate(abc, bcd, t); +} + +// Evaluates the point on the source cubic specified by t, 0 <= t <= 1.0. +FloatPoint evaluateCubicAt(const FloatPoint cubic[4], float t) +{ + return FloatPoint(evaluateCubic(cubic[0].x(), cubic[1].x(), cubic[2].x(), cubic[3].x(), t), + evaluateCubic(cubic[0].y(), cubic[1].y(), cubic[2].y(), cubic[3].y(), t)); +} + +bool xRayCrossesMonotonicCubic(const XRay& xRay, const FloatPoint cubic[4], bool& ambiguous) +{ + ambiguous = false; + + // Find the minimum and maximum y of the extrema, which are the + // first and last points since this cubic is monotonic + float minY = std::min(cubic[0].y(), cubic[3].y()); + float maxY = std::max(cubic[0].y(), cubic[3].y()); + + if (xRay.y() == cubic[0].y() + || xRay.y() < minY + || xRay.y() > maxY) { + // The query line definitely does not cross the curve + ambiguous = (xRay.y() == cubic[0].y()); + return false; + } + + const bool pointAtExtremum = (xRay.y() == cubic[3].y()); + + float minX = std::min(std::min(std::min(cubic[0].x(), cubic[1].x()), + cubic[2].x()), + cubic[3].x()); + if (xRay.x() < minX) { + // The query line definitely crosses the curve + ambiguous = pointAtExtremum; + return true; + } + + float maxX = std::max(std::max(std::max(cubic[0].x(), cubic[1].x()), + cubic[2].x()), + cubic[3].x()); + if (xRay.x() > maxX) + // The query line definitely does not cross the curve + return false; + + // Do a binary search to find the parameter value which makes y as + // close as possible to the query point. See whether the query + // line's origin is to the left of the associated x coordinate. + + // MaxIterations is chosen as the number of mantissa bits for a float, + // since there's no way we are going to get more precision by + // iterating more times than that. + const int MaxIterations = 23; + FloatPoint evaluatedPoint; + int iter = 0; + float upperT; + float lowerT; + // Need to invert direction of t parameter if cubic goes up + // instead of down + if (cubic[3].y() > cubic[0].y()) { + upperT = 1; + lowerT = 0; + } else { + upperT = 0; + lowerT = 1; + } + do { + float t = 0.5f * (upperT + lowerT); + evaluatedPoint = evaluateCubicAt(cubic, t); + if (xRay.y() > evaluatedPoint.y()) + lowerT = t; + else + upperT = t; + } while (++iter < MaxIterations && !nearlyZero(evaluatedPoint.y() - xRay.y())); + + // FIXME: once we have more regression tests for this code, + // determine whether this should be using a fuzzy test. + if (xRay.x() <= evaluatedPoint.x()) { + ambiguous = pointAtExtremum; + return true; + } + return false; +} + +// Divides the numerator by the denominator safely for the case where +// the result must lie in the range (0..1). Result indicates whether +// the result is valid. +bool safeUnitDivide(float numerator, float denominator, float& ratio) +{ + if (numerator < 0) { + // Make the "numerator >= denominator" check below work. + numerator = -numerator; + denominator = -denominator; + } + if (!numerator || !denominator || numerator >= denominator) + return false; + float r = numerator / denominator; + if (isnan(r)) + return false; + ASSERT(r >= 0 && r < 1); + if (!r) // catch underflow if numerator <<<< denominator + return false; + ratio = r; + return true; +} + +// From Numerical Recipes in C. +// +// q = -1/2 (b + sign(b) sqrt[b*b - 4*a*c]) +// x1 = q / a +// x2 = c / q +// +// Returns the number of real roots of the equation [0..2]. Roots are +// returned in sorted order, smaller root first. +int findUnitQuadRoots(float a, float b, float c, float roots[2]) +{ + if (!a) + return safeUnitDivide(-c, b, roots[0]) ? 1 : 0; + + float discriminant = b*b - 4*a*c; + if (discriminant < 0 || isnan(discriminant)) // complex roots + return 0; + discriminant = sqrtf(discriminant); + + float q = (b < 0) ? -(b - discriminant) / 2 : -(b + discriminant) / 2; + int numberOfRoots = 0; + if (safeUnitDivide(q, a, roots[numberOfRoots])) + ++numberOfRoots; + if (safeUnitDivide(c, q, roots[numberOfRoots])) + ++numberOfRoots; + if (numberOfRoots == 2) { + // Seemingly have two roots. Check for equality and sort. + if (roots[0] == roots[1]) + return 1; + if (roots[0] > roots[1]) + std::swap(roots[0], roots[1]); + } + return numberOfRoots; +} + +// Cubic'(t) = pt^2 + qt + r, where +// p = 3(-a + 3(b - c) + d) +// q = 6(a - 2b + c) +// r = 3(b - a) +// Solve for t, keeping only those that fit between 0 < t < 1. +int findCubicExtrema(float a, float b, float c, float d, float tValues[2]) +{ + // Divide p, q, and r by 3 to simplify the equations. + float p = d - a + 3*(b - c); + float q = 2*(a - b - b + c); + float r = b - a; + + return findUnitQuadRoots(p, q, r, tValues); +} + +void interpolateCubicCoords(float controlPoint0, float controlPoint1, float controlPoint2, float controlPoint3, float* dst, float t) +{ + float ab = interpolate(controlPoint0, controlPoint1, t); + float bc = interpolate(controlPoint1, controlPoint2, t); + float cd = interpolate(controlPoint2, controlPoint3, t); + float abc = interpolate(ab, bc, t); + float bcd = interpolate(bc, cd, t); + float abcd = interpolate(abc, bcd, t); + + dst[0] = controlPoint0; + dst[2] = ab; + dst[4] = abc; + dst[6] = abcd; + dst[8] = bcd; + dst[10] = cd; + dst[12] = controlPoint3; +} + +#ifndef NDEBUG +bool isUnitInterval(float x) +{ + return x > 0 && x < 1; +} +#endif + +void chopCubicAtTValues(const FloatPoint src[4], FloatPoint dst[], const float tValues[], int roots) +{ +#ifndef NDEBUG + for (int i = 0; i < roots - 1; ++i) { + ASSERT(isUnitInterval(tValues[i])); + ASSERT(isUnitInterval(tValues[i+1])); + ASSERT(tValues[i] < tValues[i+1]); + } +#endif + + if (!roots) { + // nothing to chop + for (int j = 0; j < 4; ++j) + dst[j] = src[j]; + return; + } + + float t = tValues[0]; + FloatPoint tmp[4]; + for (int j = 0; j < 4; ++j) + tmp[j] = src[j]; + + for (int i = 0; i < roots; ++i) { + chopCubicAt(tmp, dst, t); + if (i == roots - 1) + break; + + dst += 3; + // Make tmp contain the remaining cubic (after the first chop). + for (int j = 0; j < 4; ++j) + tmp[j] = dst[j]; + + // Watch out for the case that the renormalized t isn't in range. + if (!safeUnitDivide(tValues[i+1] - tValues[i], 1.0f - tValues[i], t)) { + // If it isn't, just create a degenerate cubic. + dst[4] = dst[5] = dst[6] = tmp[3]; + break; + } + } +} + +void flattenDoubleCubicYExtrema(FloatPoint coords[7]) +{ + coords[2].setY(coords[3].y()); + coords[4].setY(coords[3].y()); +} + +int chopCubicAtYExtrema(const FloatPoint src[4], FloatPoint dst[10]) +{ + float tValues[2]; + int roots = findCubicExtrema(src[0].y(), src[1].y(), src[2].y(), src[3].y(), tValues); + + chopCubicAtTValues(src, dst, tValues, roots); + if (roots) { + // we do some cleanup to ensure our Y extrema are flat + flattenDoubleCubicYExtrema(&dst[0]); + if (roots == 2) + flattenDoubleCubicYExtrema(&dst[3]); + } + return roots; +} + +} // anonymous namespace + +// Public cubic operations. + +void chopCubicAt(const FloatPoint src[4], FloatPoint dst[7], float t) +{ + ASSERT(t >= 0 && t <= 1); + + float output[14]; + interpolateCubicCoords(src[0].x(), src[1].x(), src[2].x(), src[3].x(), &output[0], t); + interpolateCubicCoords(src[0].y(), src[1].y(), src[2].y(), src[3].y(), &output[1], t); + for (int i = 0; i < 7; i++) + dst[i].set(output[2 * i], output[2 * i + 1]); +} + +// Public XRay queries. + +bool xRayCrossesLine(const XRay& xRay, const FloatPoint pts[2], bool& ambiguous) +{ + ambiguous = false; + + // Determine quick discards. + // Consider query line going exactly through point 0 to not + // intersect, for symmetry with xRayCrossesMonotonicCubic. + if (xRay.y() == pts[0].y()) { + ambiguous = true; + return false; + } + if (xRay.y() < pts[0].y() && xRay.y() < pts[1].y()) + return false; + if (xRay.y() > pts[0].y() && xRay.y() > pts[1].y()) + return false; + if (xRay.x() > pts[0].x() && xRay.x() > pts[1].x()) + return false; + // Determine degenerate cases + if (nearlyZero(pts[0].y() - pts[1].y())) + return false; + if (nearlyZero(pts[0].x() - pts[1].x())) { + // We've already determined the query point lies within the + // vertical range of the line segment. + if (xRay.x() <= pts[0].x()) { + ambiguous = (xRay.y() == pts[1].y()); + return true; + } + return false; + } + // Ambiguity check + if (xRay.y() == pts[1].y()) { + if (xRay.x() <= pts[1].x()) { + ambiguous = true; + return true; + } + return false; + } + // Full line segment evaluation + float deltaY = pts[1].y() - pts[0].y(); + float deltaX = pts[1].x() - pts[0].x(); + float slope = deltaY / deltaX; + float b = pts[0].y() - slope * pts[0].x(); + // Solve for x coordinate at y = xRay.y() + float x = (xRay.y() - b) / slope; + return xRay.x() <= x; +} + +int numXRayCrossingsForCubic(const XRay& xRay, const FloatPoint cubic[4], bool& ambiguous) +{ + int numCrossings = 0; + FloatPoint monotonicCubics[10]; + int numMonotonicCubics = 1 + chopCubicAtYExtrema(cubic, monotonicCubics); + ambiguous = false; + FloatPoint* monotonicCubicsPointer = &monotonicCubics[0]; + for (int i = 0; i < numMonotonicCubics; ++i) { + if (xRayCrossesMonotonicCubic(xRay, monotonicCubicsPointer, ambiguous)) + ++numCrossings; + if (ambiguous) + return 0; + monotonicCubicsPointer += 3; + } + return numCrossings; +} + +} // namespace LoopBlinnMathUtils +} // namespace WebCore + +#endif diff --git a/Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.h b/Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.h new file mode 100644 index 0000000..b9d19c5 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.h @@ -0,0 +1,108 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LoopBlinnMathUtils_h +#define LoopBlinnMathUtils_h + +#include "FloatPoint.h" +#include "FloatPoint3D.h" +#include <math.h> + +namespace WebCore { + +// Use a namespace for these so we can easily import them. +namespace LoopBlinnMathUtils { + +float roundToZero(float val); +bool approxEqual(const FloatPoint& v0, const FloatPoint& v1); +bool approxEqual(const FloatPoint3D& v0, const FloatPoint3D& v1); +bool approxEqual(float f0, float f1); + +// Determines whether the line segment between (p1, q1) intersects +// that between (p2, q2). +bool linesIntersect(const FloatPoint& p1, + const FloatPoint& q1, + const FloatPoint& p2, + const FloatPoint& q2); + +// Determines whether "point" is inside the 2D triangle defined by +// vertices a, b, and c. This test defines that points exactly on an +// edge are not considered to be inside the triangle. +bool pointInTriangle(const FloatPoint& point, + const FloatPoint& a, + const FloatPoint& b, + const FloatPoint& c); + +// Determines whether the triangles defined by the points (a1, b1, c1) +// and (a2, b2, c2) overlap. The definition of this function is that +// if the two triangles only share an adjacent edge or vertex, they +// are not considered to overlap. +bool trianglesOverlap(const FloatPoint& a1, + const FloatPoint& b1, + const FloatPoint& c1, + const FloatPoint& a2, + const FloatPoint& b2, + const FloatPoint& c2); + +// Given a src cubic bezier, chops it at the specified t value, +// where 0 < t < 1, and returns the two new cubics in dst[0..3] +// and dst[3..6]. +void chopCubicAt(const FloatPoint src[4], FloatPoint dst[7], float t); + +// "X-Ray" queries. An XRay is a half-line originating at the given +// point and extending to x=+infinity. +typedef FloatPoint XRay; + +// Given an arbitrary cubic bezier, return the number of times an XRay +// crosses the cubic. Valid return values are [0..3]. +// +// By definition the cubic is open at the starting point; in other +// words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the +// left of the curve, the line is not considered to cross the curve, +// but if it is equal to cubic[3].fY then it is considered to +// cross. +// +// Outgoing "ambiguous" argument indicates whether the answer is ambiguous +// because the query occurred exactly at one of the endpoints' y +// coordinates or at a tangent point, indicating that another query y +// coordinate is preferred for robustness. +int numXRayCrossingsForCubic(const XRay& xRay, + const FloatPoint cubic[4], + bool& ambiguous); + +// Given a line segment from lineEndpoints[0] to lineEndpoints[1], and an +// XRay, returns true if they intersect. Outgoing "ambiguous" argument +// indicates whether the answer is ambiguous because the query occurred +// exactly at one of the endpoints' y coordinates, indicating that another +// query y coordinate is preferred for robustness. +bool xRayCrossesLine(const XRay& xRay, + const FloatPoint lineEndpoints[2], + bool& ambiguous); + +} // namespace LoopBlinnMathUtils + +} // namespace WebCore + +#endif // LoopBlinnMathUtils_h diff --git a/Source/WebCore/platform/graphics/gpu/LoopBlinnTextureCoords.cpp b/Source/WebCore/platform/graphics/gpu/LoopBlinnTextureCoords.cpp new file mode 100644 index 0000000..d272fe1 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/LoopBlinnTextureCoords.cpp @@ -0,0 +1,175 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#if ENABLE(ACCELERATED_2D_CANVAS) + +#include "LoopBlinnTextureCoords.h" + +#include <math.h> +#include <wtf/Assertions.h> + +namespace WebCore { + +LoopBlinnTextureCoords::Result LoopBlinnTextureCoords::compute(const LoopBlinnClassifier::Result& classification, LoopBlinnConstants::FillSide sideToFill) +{ + // Loop and Blinn's formulation states that the right side of the + // curve is defined to be the inside (filled region), but for some + // reason it looks like with the default orientation parameters we + // are filling the left side of the curve. Regardless, because we + // can receive arbitrarily oriented curves as input, we might have + // to reverse the orientation of the cubic texture coordinates even + // in cases where the paper doesn't say it is necessary. + bool reverseOrientation = false; + static const float OneThird = 1.0f / 3.0f; + static const float TwoThirds = 2.0f / 3.0f; + LoopBlinnClassifier::CurveType curveType = classification.curveType; + + LoopBlinnTextureCoords::Result result; + + switch (curveType) { + case LoopBlinnClassifier::kSerpentine: { + float t1 = sqrtf(9.0f * classification.d2 * classification.d2 - 12 * classification.d1 * classification.d3); + float ls = 3.0f * classification.d2 - t1; + float lt = 6.0f * classification.d1; + float ms = 3.0f * classification.d2 + t1; + float mt = lt; + float ltMinusLs = lt - ls; + float mtMinusMs = mt - ms; + result.klmCoordinates[0] = FloatPoint3D(ls * ms, + ls * ls * ls, + ms * ms * ms); + result.klmCoordinates[1] = FloatPoint3D(OneThird * (3.0f * ls * ms - ls * mt - lt * ms), + ls * ls * (ls - lt), + ms * ms * (ms - mt)); + result.klmCoordinates[2] = FloatPoint3D(OneThird * (lt * (mt - 2.0f * ms) + ls * (3.0f * ms - 2.0f * mt)), + ltMinusLs * ltMinusLs * ls, + mtMinusMs * mtMinusMs * ms); + result.klmCoordinates[3] = FloatPoint3D(ltMinusLs * mtMinusMs, + -(ltMinusLs * ltMinusLs * ltMinusLs), + -(mtMinusMs * mtMinusMs * mtMinusMs)); + if (classification.d1 < 0.0f) + reverseOrientation = true; + break; + } + + case LoopBlinnClassifier::kLoop: { + float t1 = sqrtf(4.0f * classification.d1 * classification.d3 - 3.0f * classification.d2 * classification.d2); + float ls = classification.d2 - t1; + float lt = 2.0f * classification.d1; + float ms = classification.d2 + t1; + float mt = lt; + + // Figure out whether there is a rendering artifact requiring + // the curve to be subdivided by the caller. + float ql = ls / lt; + float qm = ms / mt; + if (0.0f < ql && ql < 1.0f) { + result.hasRenderingArtifact = true; + result.subdivisionParameterValue = ql; + return result; + } + + if (0.0f < qm && qm < 1.0f) { + result.hasRenderingArtifact = true; + result.subdivisionParameterValue = qm; + return result; + } + + float ltMinusLs = lt - ls; + float mtMinusMs = mt - ms; + result.klmCoordinates[0] = FloatPoint3D(ls * ms, + ls * ls * ms, + ls * ms * ms); + result.klmCoordinates[1] = FloatPoint3D(OneThird * (-ls * mt - lt * ms + 3.0f * ls * ms), + -OneThird * ls * (ls * (mt - 3.0f * ms) + 2.0f * lt * ms), + -OneThird * ms * (ls * (2.0f * mt - 3.0f * ms) + lt * ms)); + result.klmCoordinates[2] = FloatPoint3D(OneThird * (lt * (mt - 2.0f * ms) + ls * (3.0f * ms - 2.0f * mt)), + OneThird * (lt - ls) * (ls * (2.0f * mt - 3.0f * ms) + lt * ms), + OneThird * (mt - ms) * (ls * (mt - 3.0f * ms) + 2.0f * lt * ms)); + result.klmCoordinates[3] = FloatPoint3D(ltMinusLs * mtMinusMs, + -(ltMinusLs * ltMinusLs) * mtMinusMs, + -ltMinusLs * mtMinusMs * mtMinusMs); + reverseOrientation = ((classification.d1 > 0.0f && result.klmCoordinates[0].x() < 0.0f) + || (classification.d1 < 0.0f && result.klmCoordinates[0].x() > 0.0f)); + break; + } + + case LoopBlinnClassifier::kCusp: { + float ls = classification.d3; + float lt = 3.0f * classification.d2; + float lsMinusLt = ls - lt; + result.klmCoordinates[0] = FloatPoint3D(ls, + ls * ls * ls, + 1.0f); + result.klmCoordinates[1] = FloatPoint3D(ls - OneThird * lt, + ls * ls * lsMinusLt, + 1.0f); + result.klmCoordinates[2] = FloatPoint3D(ls - TwoThirds * lt, + lsMinusLt * lsMinusLt * ls, + 1.0f); + result.klmCoordinates[3] = FloatPoint3D(lsMinusLt, + lsMinusLt * lsMinusLt * lsMinusLt, + 1.0f); + break; + } + + case LoopBlinnClassifier::kQuadratic: { + result.klmCoordinates[0] = FloatPoint3D(0, 0, 0); + result.klmCoordinates[1] = FloatPoint3D(OneThird, 0, OneThird); + result.klmCoordinates[2] = FloatPoint3D(TwoThirds, OneThird, TwoThirds); + result.klmCoordinates[3] = FloatPoint3D(1, 1, 1); + if (classification.d3 < 0) + reverseOrientation = true; + break; + } + + case LoopBlinnClassifier::kLine: + case LoopBlinnClassifier::kPoint: + result.isLineOrPoint = true; + break; + + default: + ASSERT_NOT_REACHED(); + break; + } + + if (sideToFill == LoopBlinnConstants::RightSide) + reverseOrientation = !reverseOrientation; + + if (reverseOrientation) { + for (int i = 0; i < 4; ++i) { + result.klmCoordinates[i].setX(-result.klmCoordinates[i].x()); + result.klmCoordinates[i].setY(-result.klmCoordinates[i].y()); + } + } + + return result; +} + +} // namespace WebCore + +#endif diff --git a/Source/WebCore/platform/graphics/gpu/LoopBlinnTextureCoords.h b/Source/WebCore/platform/graphics/gpu/LoopBlinnTextureCoords.h new file mode 100644 index 0000000..5fdeb3b --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/LoopBlinnTextureCoords.h @@ -0,0 +1,82 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LoopBlinnTextureCoords_h +#define LoopBlinnTextureCoords_h + +#include "FloatPoint3D.h" +#include "LoopBlinnClassifier.h" +#include "LoopBlinnConstants.h" + +#include <wtf/Noncopyable.h> + +namespace WebCore { + +// Computes three-dimensional texture coordinates for the control +// points of a cubic curve for rendering via the shader in "Rendering +// Vector Art on the GPU" by Loop and Blinn, GPU Gems 3, Chapter 25. +class LoopBlinnTextureCoords { +public: + // Container for the cubic texture coordinates and other associated + // information. + struct Result { + Result() + : isLineOrPoint(false) + , hasRenderingArtifact(false) + , subdivisionParameterValue(0.0f) { } + + // The (k, l, m) texture coordinates that are to be associated + // with the four control points of the cubic curve. + FloatPoint3D klmCoordinates[4]; + + // Indicates whether the curve is a line or a point, in which case + // we do not need to add its triangles to the mesh. + bool isLineOrPoint; + + // For the loop case, indicates whether a rendering artifact was + // detected, in which case the curve needs to be further + // subdivided. + bool hasRenderingArtifact; + + // If a rendering artifact will occur for the given loop curve, + // this is the parameter value (0 <= value <= 1) at which the + // curve needs to be subdivided to fix the artifact. + float subdivisionParameterValue; + }; + + // Computes the texture coordinates for a cubic curve segment's + // control points, given the classification of the curve as well as + // an indication of which side is to be filled. + static Result compute(const LoopBlinnClassifier::Result& classification, + LoopBlinnConstants::FillSide sideToFill); + +private: + // This class does not need to be instantiated. + LoopBlinnTextureCoords() { } +}; + +} // namespace WebCore + +#endif // LoopBlinnTextureCoords_h diff --git a/Source/WebCore/platform/graphics/gpu/PODArena.h b/Source/WebCore/platform/graphics/gpu/PODArena.h new file mode 100644 index 0000000..f68baef --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/PODArena.h @@ -0,0 +1,211 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef PODArena_h +#define PODArena_h + +#include <stdint.h> +#include <wtf/Assertions.h> +#include <wtf/FastMalloc.h> +#include <wtf/Noncopyable.h> +#include <wtf/OwnPtr.h> +#include <wtf/PassOwnPtr.h> +#include <wtf/RefCounted.h> +#include <wtf/Vector.h> + +namespace WebCore { + +// An arena which allocates only Plain Old Data (POD), or classes and +// structs bottoming out in Plain Old Data. NOTE: the constructors of +// the objects allocated in this arena are called, but _not_ their +// destructors. + +class PODArena : public RefCounted<PODArena> { +public: + // The arena is configured with an allocator, which is responsible + // for allocating and freeing chunks of memory at a time. + class Allocator : public RefCounted<Allocator> { + public: + virtual void* allocate(size_t size) = 0; + virtual void free(void* ptr) = 0; + protected: + virtual ~Allocator() { } + friend class WTF::RefCounted<Allocator>; + }; + + // The Arena's default allocator, which uses fastMalloc and + // fastFree to allocate chunks of storage. + class FastMallocAllocator : public Allocator { + public: + static PassRefPtr<FastMallocAllocator> create() + { + return adoptRef(new FastMallocAllocator); + } + + virtual void* allocate(size_t size) { return fastMalloc(size); } + virtual void free(void* ptr) { fastFree(ptr); } + + protected: + FastMallocAllocator() { } + }; + + // Creates a new PODArena configured with a FastMallocAllocator. + static PassRefPtr<PODArena> create() + { + return adoptRef(new PODArena); + } + + // Creates a new PODArena configured with the given Allocator. + static PassRefPtr<PODArena> create(PassRefPtr<Allocator> allocator) + { + return adoptRef(new PODArena(allocator)); + } + + // Allocates an object from the arena. + template<class T> T* allocateObject() + { + void* ptr = allocateBase<T>(); + if (ptr) { + // Use placement operator new to allocate a T at this location. + new(ptr) T(); + } + return static_cast<T*>(ptr); + } + + // Allocates an object from the arena, calling a single-argument constructor. + template<class T, class Argument1Type> T* allocateObject(const Argument1Type& argument1) + { + void* ptr = allocateBase<T>(); + if (ptr) { + // Use placement operator new to allocate a T at this location. + new(ptr) T(argument1); + } + return static_cast<T*>(ptr); + } + + // The initial size of allocated chunks; increases as necessary to + // satisfy large allocations. Mainly public for unit tests. + enum { + DefaultChunkSize = 16384 + }; + +protected: + ~PODArena() { } + friend class WTF::RefCounted<PODArena>; + +private: + PODArena() + : m_allocator(FastMallocAllocator::create()) + , m_current(0) + , m_currentChunkSize(DefaultChunkSize) { } + + explicit PODArena(PassRefPtr<Allocator> allocator) + : m_allocator(allocator) + , m_current(0) + , m_currentChunkSize(DefaultChunkSize) { } + + // Returns the alignment requirement for classes and structs on the + // current platform. + template <class T> static size_t minAlignment() + { + return WTF_ALIGN_OF(T); + } + + template<class T> void* allocateBase() + { + void* ptr = 0; + size_t roundedSize = roundUp(sizeof(T), minAlignment<T>()); + if (m_current) + ptr = m_current->allocate(roundedSize); + + if (!ptr) { + if (roundedSize > m_currentChunkSize) + m_currentChunkSize = roundedSize; + m_chunks.append(adoptPtr(new Chunk(m_allocator.get(), m_currentChunkSize))); + m_current = m_chunks.last().get(); + ptr = m_current->allocate(roundedSize); + } + return ptr; + } + + // Rounds up the given allocation size to the specified alignment. + size_t roundUp(size_t size, size_t alignment) + { + ASSERT(!(alignment % 2)); + return (size + alignment - 1) & ~(alignment - 1); + } + + // Manages a chunk of memory and individual allocations out of it. + class Chunk : public Noncopyable { + public: + // Allocates a block of memory of the given size from the passed + // Allocator. + Chunk(Allocator* allocator, size_t size) + : m_allocator(allocator) + , m_size(size) + , m_currentOffset(0) + { + m_base = static_cast<uint8_t*>(m_allocator->allocate(size)); + } + + // Frees the memory allocated from the Allocator in the + // constructor. + ~Chunk() + { + m_allocator->free(m_base); + } + + // Returns a pointer to "size" bytes of storage, or 0 if this + // Chunk could not satisfy the allocation. + void* allocate(size_t size) + { + // Check for overflow + if (m_currentOffset + size < m_currentOffset) + return 0; + + if (m_currentOffset + size > m_size) + return 0; + + void* result = m_base + m_currentOffset; + m_currentOffset += size; + return result; + } + + private: + Allocator* m_allocator; + uint8_t* m_base; + size_t m_size; + size_t m_currentOffset; + }; + + RefPtr<Allocator> m_allocator; + Chunk* m_current; + size_t m_currentChunkSize; + Vector<OwnPtr<Chunk> > m_chunks; +}; + +} // namespace WebCore + +#endif // PODArena_h diff --git a/Source/WebCore/platform/graphics/gpu/PODInterval.h b/Source/WebCore/platform/graphics/gpu/PODInterval.h new file mode 100644 index 0000000..5c1dcc2 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/PODInterval.h @@ -0,0 +1,165 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef PODInterval_h +#define PODInterval_h + +#ifndef NDEBUG +#include <wtf/text/StringBuilder.h> +#endif + +namespace WebCore { + +// Class representing a closed interval which can hold an arbitrary +// Plain Old Datatype (POD) as its endpoints and a piece of user +// data. An important characteristic for the algorithms we use is that +// if two intervals have identical endpoints but different user data, +// they are not considered to be equal. This situation can arise when +// representing the vertical extents of bounding boxes of overlapping +// triangles, where the pointer to the triangle is the user data of +// the interval. +// +// *Note* that the destructors of type T and UserData will *not* be +// called by this class. They must not allocate any memory that is +// required to be cleaned up in their destructors. +// +// The following constructors and operators must be implemented on +// type T: +// +// - Copy constructor (if user data is desired) +// - operator< +// - operator== +// - operator= +// +// If the UserData type is specified, it must support a copy +// constructor and assignment operator. +// +// In debug mode, printing of intervals and the data they contain is +// enabled. This requires the following template specializations to be +// available: +// +// template<> struct WebCore::ValueToString<T> { +// static String string(const T& t); +// }; +// template<> struct WebCore::ValueToString<UserData> { +// static String string(const UserData& t); +// }; +// +// Note that this class requires a copy constructor and assignment +// operator in order to be stored in the red-black tree. + +#ifndef NDEBUG +template<class T> +struct ValueToString; +#endif + +template<class T, class UserData = void*> +class PODInterval { +public: + // Constructor from endpoints. This constructor only works when the + // UserData type is a pointer or other type which can be initialized + // with 0. + PODInterval(const T& low, const T& high) + : m_low(low) + , m_high(high) + , m_data(0) + , m_maxHigh(high) + { + } + + // Constructor from two endpoints plus explicit user data. + PODInterval(const T& low, const T& high, const UserData data) + : m_low(low) + , m_high(high) + , m_data(data) + , m_maxHigh(high) + { + } + + const T& low() const { return m_low; } + const T& high() const { return m_high; } + const UserData& data() const { return m_data; } + + bool overlaps(const T& low, const T& high) const + { + if (this->high() < low) + return false; + if (high < this->low()) + return false; + return true; + } + + bool overlaps(const PODInterval& other) const + { + return overlaps(other.low(), other.high()); + } + + // Returns true if this interval is "less" than the other. The + // comparison is performed on the low endpoints of the intervals. + bool operator<(const PODInterval& other) const + { + return low() < other.low(); + } + + // Returns true if this interval is strictly equal to the other, + // including comparison of the user data. + bool operator==(const PODInterval& other) const + { + return (low() == other.low() + && high() == other.high() + && data() == other.data()); + } + + const T& maxHigh() const { return m_maxHigh; } + void setMaxHigh(const T& maxHigh) { m_maxHigh = maxHigh; } + +#ifndef NDEBUG + // Support for printing PODIntervals. + String toString() const + { + StringBuilder builder; + builder.append("[PODInterval ("); + builder.append(ValueToString<T>::string(low())); + builder.append(", "); + builder.append(ValueToString<T>::string(high())); + builder.append("), data="); + builder.append(ValueToString<UserData>::string(data())); + builder.append(", maxHigh="); + builder.append(ValueToString<T>::string(maxHigh())); + builder.append("]"); + return builder.toString(); + } +#endif + +private: + T m_low; + T m_high; + UserData m_data; + T m_maxHigh; +}; + +} // namespace WebCore + +#endif // PODInterval_h diff --git a/Source/WebCore/platform/graphics/gpu/PODIntervalTree.h b/Source/WebCore/platform/graphics/gpu/PODIntervalTree.h new file mode 100644 index 0000000..320ce60 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/PODIntervalTree.h @@ -0,0 +1,224 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef PODIntervalTree_h +#define PODIntervalTree_h + +#include "PODArena.h" +#include "PODInterval.h" +#include "PODRedBlackTree.h" +#include <wtf/Assertions.h> +#include <wtf/Noncopyable.h> +#include <wtf/Vector.h> + +namespace WebCore { + +#ifndef NDEBUG +template<class T> +struct ValueToString; +#endif + +// An interval tree, which is a form of augmented red-black tree. It +// supports efficient (O(lg n)) insertion, removal and querying of +// intervals in the tree. +template<class T, class UserData = void*> +class PODIntervalTree : public Noncopyable, + public PODRedBlackTree<PODInterval<T, UserData> > { +public: + // Typedef to reduce typing when declaring intervals to be stored in + // this tree. + typedef PODInterval<T, UserData> IntervalType; + + PODIntervalTree() + : PODRedBlackTree<IntervalType>() + { + init(); + } + + explicit PODIntervalTree(PassRefPtr<PODArena> arena) + : PODRedBlackTree<IntervalType>(arena) + { + init(); + } + + // Returns all intervals in the tree which overlap the given query + // interval. The returned intervals are sorted by increasing low + // endpoint. + Vector<IntervalType> allOverlaps(const IntervalType& interval) const + { + Vector<IntervalType> result; + allOverlaps(interval, result); + return result; + } + + // Returns all intervals in the tree which overlap the given query + // interval. The returned intervals are sorted by increasing low + // endpoint. + void allOverlaps(const IntervalType& interval, Vector<IntervalType>& result) const + { + // Explicit dereference of "this" required because of + // inheritance rules in template classes. + searchForOverlapsFrom(this->root(), interval, result); + } + + // Helper to create interval objects. + static IntervalType createInterval(const T& low, const T& high, const UserData data = 0) + { + return IntervalType(low, high, data); + } + + virtual bool checkInvariants() const + { + if (!PODRedBlackTree<IntervalType>::checkInvariants()) + return false; + if (!this->root()) + return true; + return checkInvariantsFromNode(this->root(), 0); + } + +private: + typedef typename PODRedBlackTree<IntervalType>::Node IntervalNode; + + // Initializes the tree. + void init() + { + // Explicit dereference of "this" required because of + // inheritance rules in template classes. + this->setNeedsFullOrderingComparisons(true); + } + + // Starting from the given node, adds all overlaps with the given + // interval to the result vector. The intervals are sorted by + // increasing low endpoint. + void searchForOverlapsFrom(IntervalNode* node, const IntervalType& interval, Vector<IntervalType>& res) const + { + if (!node) + return; + + // Because the intervals are sorted by left endpoint, inorder + // traversal produces results sorted as desired. + + // See whether we need to traverse the left subtree. + IntervalNode* left = node->left(); + if (left + // This is phrased this way to avoid the need for operator + // <= on type T. + && !(left->data().maxHigh() < interval.low())) + searchForOverlapsFrom(left, interval, res); + + // Check for overlap with current node. + if (node->data().overlaps(interval)) + res.append(node->data()); + + // See whether we need to traverse the right subtree. + // This is phrased this way to avoid the need for operator <= + // on type T. + if (!(interval.high() < node->data().low())) + searchForOverlapsFrom(node->right(), interval, res); + } + + virtual bool updateNode(IntervalNode* node) + { + // Would use const T&, but need to reassign this reference in this + // function. + const T* curMax = &node->data().high(); + IntervalNode* left = node->left(); + if (left) { + if (*curMax < left->data().maxHigh()) + curMax = &left->data().maxHigh(); + } + IntervalNode* right = node->right(); + if (right) { + if (*curMax < right->data().maxHigh()) + curMax = &right->data().maxHigh(); + } + // This is phrased like this to avoid needing operator!= on type T. + if (!(*curMax == node->data().maxHigh())) { + node->data().setMaxHigh(*curMax); + return true; + } + return false; + } + + bool checkInvariantsFromNode(IntervalNode* node, T* currentMaxValue) const + { + // These assignments are only done in order to avoid requiring + // a default constructor on type T. + T leftMaxValue(node->data().maxHigh()); + T rightMaxValue(node->data().maxHigh()); + IntervalNode* left = node->left(); + IntervalNode* right = node->right(); + if (left) { + if (!checkInvariantsFromNode(left, &leftMaxValue)) + return false; + } + if (right) { + if (!checkInvariantsFromNode(right, &rightMaxValue)) + return false; + } + if (!left && !right) { + // Base case. + if (currentMaxValue) + *currentMaxValue = node->data().high(); + return (node->data().high() == node->data().maxHigh()); + } + T localMaxValue(node->data().maxHigh()); + if (!left || !right) { + if (left) + localMaxValue = leftMaxValue; + else + localMaxValue = rightMaxValue; + } else + localMaxValue = (leftMaxValue < rightMaxValue) ? rightMaxValue : leftMaxValue; + if (localMaxValue < node->data().high()) + localMaxValue = node->data().high(); + if (!(localMaxValue == node->data().maxHigh())) { +#ifndef NDEBUG + String localMaxValueString = ValueToString<T>::string(localMaxValue); + LOG_ERROR("PODIntervalTree verification failed at node 0x%p: localMaxValue=%s and data=%s", + node, localMaxValueString.utf8().data(), node->data().toString().utf8().data()); +#endif + return false; + } + if (currentMaxValue) + *currentMaxValue = localMaxValue; + return true; + } +}; + +#ifndef NDEBUG +// Support for printing PODIntervals at the PODRedBlackTree level. +template<class T, class UserData> +struct ValueToString<PODInterval<T, UserData> > { + static String string(const PODInterval<T, UserData>& interval) + { + return interval.toString(); + } +}; +#endif + +} // namespace WebCore + +#endif // PODIntervalTree_h diff --git a/Source/WebCore/platform/graphics/gpu/PODRedBlackTree.h b/Source/WebCore/platform/graphics/gpu/PODRedBlackTree.h new file mode 100644 index 0000000..6d5954c --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/PODRedBlackTree.h @@ -0,0 +1,757 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +// A red-black tree, which is a form of a balanced binary tree. It +// supports efficient insertion, deletion and queries of comparable +// elements. The same element may be inserted multiple times. The +// algorithmic complexity of common operations is: +// +// Insertion: O(lg(n)) +// Deletion: O(lg(n)) +// Querying: O(lg(n)) +// +// The data type T that is stored in this red-black tree must be only +// Plain Old Data (POD), or bottom out into POD. It must _not_ rely on +// having its destructor called. This implementation internally +// allocates storage in large chunks and does not call the destructor +// on each object. +// +// Type T must supply a default constructor, a copy constructor, and +// the "<" and "==" operators. +// +// In debug mode, printing of the data contained in the tree is +// enabled. This requires the template specialization to be available: +// +// template<> struct WebCore::ValueToString<T> { +// static String string(const T& t); +// }; +// +// Note that when complex types are stored in this red/black tree, it +// is possible that single invocations of the "<" and "==" operators +// will be insufficient to describe the ordering of elements in the +// tree during queries. As a concrete example, consider the case where +// intervals are stored in the tree sorted by low endpoint. The "<" +// operator on the Interval class only compares the low endpoint, but +// the "==" operator takes into account the high endpoint as well. +// This makes the necessary logic for querying and deletion somewhat +// more complex. In order to properly handle such situations, the +// property "needsFullOrderingComparisons" must be set to true on +// the tree. +// +// This red-black tree is designed to be _augmented_; subclasses can +// add additional and summary information to each node to efficiently +// store and index more complex data structures. A concrete example is +// the IntervalTree, which extends each node with a summary statistic +// to efficiently store one-dimensional intervals. +// +// The design of this red-black tree comes from Cormen, Leiserson, +// and Rivest, _Introduction to Algorithms_, MIT Press, 1990. + +#ifndef PODRedBlackTree_h +#define PODRedBlackTree_h + +#include "PODArena.h" +#include <wtf/Assertions.h> +#include <wtf/Noncopyable.h> +#include <wtf/RefPtr.h> +#ifndef NDEBUG +#include "Logging.h" +#include <wtf/text/CString.h> +#include <wtf/text/StringBuilder.h> +#include <wtf/text/WTFString.h> +#endif + +namespace WebCore { + +#ifndef NDEBUG +template<class T> +struct ValueToString; +#endif + +template<class T> +class PODRedBlackTree { +public: + // Visitor interface for walking all of the tree's elements. + class Visitor { + public: + virtual void visit(const T& data) = 0; + protected: + virtual ~Visitor() { } + }; + + // Constructs a new red-black tree, allocating temporary objects + // from a newly constructed PODArena. + PODRedBlackTree() + : m_arena(PODArena::create()) + , m_root(0) + , m_needsFullOrderingComparisons(false) +#ifndef NDEBUG + , m_verboseDebugging(false) +#endif + { + } + + // Constructs a new red-black tree, allocating temporary objects + // from the given PODArena. + explicit PODRedBlackTree(PassRefPtr<PODArena> arena) + : m_arena(arena) + , m_root(0) + , m_needsFullOrderingComparisons(false) +#ifndef NDEBUG + , m_verboseDebugging(false) +#endif + { + } + + virtual ~PODRedBlackTree() { } + + void add(const T& data) + { + Node* node = m_arena->allocateObject<Node, T>(data); + insertNode(node); + } + + // Returns true if the datum was found in the tree. + bool remove(const T& data) + { + Node* node = treeSearch(data); + if (node) { + deleteNode(node); + return true; + } + return false; + } + + bool contains(const T& data) const { return treeSearch(data); } + + void visitInorder(Visitor* visitor) const + { + if (!m_root) + return; + visitInorderImpl(m_root, visitor); + } + + int size() const + { + Counter counter; + visitInorder(&counter); + return counter.count(); + } + + // See the class documentation for an explanation of this property. + void setNeedsFullOrderingComparisons(bool needsFullOrderingComparisons) + { + m_needsFullOrderingComparisons = needsFullOrderingComparisons; + } + + virtual bool checkInvariants() const + { + int blackCount; + return checkInvariantsFromNode(m_root, &blackCount); + } + +#ifndef NDEBUG + // Dumps the tree's contents to the logging info stream for + // debugging purposes. + void dump() const + { + dumpFromNode(m_root, 0); + } + + // Turns on or off verbose debugging of the tree, causing many + // messages to be logged during insertion and other operations in + // debug mode. + void setVerboseDebugging(bool verboseDebugging) + { + m_verboseDebugging = verboseDebugging; + } +#endif + +protected: + enum Color { + Red = 1, + Black + }; + + // The base Node class which is stored in the tree. Nodes are only + // an internal concept; users of the tree deal only with the data + // they store in it. + class Node : public Noncopyable { + public: + // Constructor. Newly-created nodes are colored red. + explicit Node(const T& data) + : m_left(0) + , m_right(0) + , m_parent(0) + , m_color(Red) + , m_data(data) + { + } + + virtual ~Node() { } + + Color color() const { return m_color; } + void setColor(Color color) { m_color = color; } + + // Fetches the user data. + T& data() { return m_data; } + + // Copies all user-level fields from the source node, but not + // internal fields. For example, the base implementation of this + // method copies the "m_data" field, but not the child or parent + // fields. Any augmentation information also does not need to be + // copied, as it will be recomputed. Subclasses must call the + // superclass implementation. + virtual void copyFrom(Node* src) { m_data = src->data(); } + + Node* left() const { return m_left; } + void setLeft(Node* node) { m_left = node; } + + Node* right() const { return m_right; } + void setRight(Node* node) { m_right = node; } + + Node* parent() const { return m_parent; } + void setParent(Node* node) { m_parent = node; } + + private: + Node* m_left; + Node* m_right; + Node* m_parent; + Color m_color; + T m_data; + }; + + // Returns the root of the tree, which is needed by some subclasses. + Node* root() const { return m_root; } + +private: + // This virtual method is the hook that subclasses should use when + // augmenting the red-black tree with additional per-node summary + // information. For example, in the case of an interval tree, this + // is used to compute the maximum endpoint of the subtree below the + // given node based on the values in the left and right children. It + // is guaranteed that this will be called in the correct order to + // properly update such summary information based only on the values + // in the left and right children. This method should return true if + // the node's summary information changed. + virtual bool updateNode(Node* node) { return false; } + + //---------------------------------------------------------------------- + // Generic binary search tree operations + // + + // Searches the tree for the given datum. + Node* treeSearch(const T& data) const + { + if (m_needsFullOrderingComparisons) + return treeSearchFullComparisons(m_root, data); + + return treeSearchNormal(m_root, data); + } + + // Searches the tree using the normal comparison operations, + // suitable for simple data types such as numbers. + Node* treeSearchNormal(Node* current, const T& data) const + { + while (current) { + if (current->data() == data) + return current; + if (data < current->data()) + current = current->left(); + else + current = current->right(); + } + return 0; + } + + // Searches the tree using multiple comparison operations, required + // for data types with more complex behavior such as intervals. + Node* treeSearchFullComparisons(Node* current, const T& data) const + { + if (!current) + return 0; + if (data < current->data()) + return treeSearchFullComparisons(current->left(), data); + if (current->data() < data) + return treeSearchFullComparisons(current->right(), data); + if (data == current->data()) + return current; + + // We may need to traverse both the left and right subtrees. + Node* result = treeSearchFullComparisons(current->left(), data); + if (!result) + result = treeSearchFullComparisons(current->right(), data); + return result; + } + + void treeInsert(Node* z) + { + Node* y = 0; + Node* x = m_root; + while (x) { + y = x; + if (z->data() < x->data()) + x = x->left(); + else + x = x->right(); + } + z->setParent(y); + if (!y) + m_root = z; + else { + if (z->data() < y->data()) + y->setLeft(z); + else + y->setRight(z); + } + } + + // Finds the node following the given one in sequential ordering of + // their data, or null if none exists. + Node* treeSuccessor(Node* x) + { + if (x->right()) + return treeMinimum(x->right()); + Node* y = x->parent(); + while (y && x == y->right()) { + x = y; + y = y->parent(); + } + return y; + } + + // Finds the minimum element in the sub-tree rooted at the given + // node. + Node* treeMinimum(Node* x) + { + while (x->left()) + x = x->left(); + return x; + } + + // Helper for maintaining the augmented red-black tree. + void propagateUpdates(Node* start) + { + bool shouldContinue = true; + while (start && shouldContinue) { + shouldContinue = updateNode(start); + start = start->parent(); + } + } + + //---------------------------------------------------------------------- + // Red-Black tree operations + // + + // Left-rotates the subtree rooted at x. + // Returns the new root of the subtree (x's right child). + Node* leftRotate(Node* x) + { + // Set y. + Node* y = x->right(); + + // Turn y's left subtree into x's right subtree. + x->setRight(y->left()); + if (y->left()) + y->left()->setParent(x); + + // Link x's parent to y. + y->setParent(x->parent()); + if (!x->parent()) + m_root = y; + else { + if (x == x->parent()->left()) + x->parent()->setLeft(y); + else + x->parent()->setRight(y); + } + + // Put x on y's left. + y->setLeft(x); + x->setParent(y); + + // Update nodes lowest to highest. + updateNode(x); + updateNode(y); + return y; + } + + // Right-rotates the subtree rooted at y. + // Returns the new root of the subtree (y's left child). + Node* rightRotate(Node* y) + { + // Set x. + Node* x = y->left(); + + // Turn x's right subtree into y's left subtree. + y->setLeft(x->right()); + if (x->right()) + x->right()->setParent(y); + + // Link y's parent to x. + x->setParent(y->parent()); + if (!y->parent()) + m_root = x; + else { + if (y == y->parent()->left()) + y->parent()->setLeft(x); + else + y->parent()->setRight(x); + } + + // Put y on x's right. + x->setRight(y); + y->setParent(x); + + // Update nodes lowest to highest. + updateNode(y); + updateNode(x); + return x; + } + + // Inserts the given node into the tree. + void insertNode(Node* x) + { + treeInsert(x); + x->setColor(Red); + updateNode(x); + + logIfVerbose(" PODRedBlackTree::InsertNode"); + + // The node from which to start propagating updates upwards. + Node* updateStart = x->parent(); + + while (x != m_root && x->parent()->color() == Red) { + if (x->parent() == x->parent()->parent()->left()) { + Node* y = x->parent()->parent()->right(); + if (y && y->color() == Red) { + // Case 1 + logIfVerbose(" Case 1/1"); + x->parent()->setColor(Black); + y->setColor(Black); + x->parent()->parent()->setColor(Red); + updateNode(x->parent()); + x = x->parent()->parent(); + updateNode(x); + updateStart = x->parent(); + } else { + if (x == x->parent()->right()) { + logIfVerbose(" Case 1/2"); + // Case 2 + x = x->parent(); + leftRotate(x); + } + // Case 3 + logIfVerbose(" Case 1/3"); + x->parent()->setColor(Black); + x->parent()->parent()->setColor(Red); + Node* newSubTreeRoot = rightRotate(x->parent()->parent()); + updateStart = newSubTreeRoot->parent(); + } + } else { + // Same as "then" clause with "right" and "left" exchanged. + Node* y = x->parent()->parent()->left(); + if (y && y->color() == Red) { + // Case 1 + logIfVerbose(" Case 2/1"); + x->parent()->setColor(Black); + y->setColor(Black); + x->parent()->parent()->setColor(Red); + updateNode(x->parent()); + x = x->parent()->parent(); + updateNode(x); + updateStart = x->parent(); + } else { + if (x == x->parent()->left()) { + // Case 2 + logIfVerbose(" Case 2/2"); + x = x->parent(); + rightRotate(x); + } + // Case 3 + logIfVerbose(" Case 2/3"); + x->parent()->setColor(Black); + x->parent()->parent()->setColor(Red); + Node* newSubTreeRoot = leftRotate(x->parent()->parent()); + updateStart = newSubTreeRoot->parent(); + } + } + } + + propagateUpdates(updateStart); + + m_root->setColor(Black); + } + + // Restores the red-black property to the tree after splicing out + // a node. Note that x may be null, which is why xParent must be + // supplied. + void deleteFixup(Node* x, Node* xParent) + { + while (x != m_root && (!x || x->color() == Black)) { + if (x == xParent->left()) { + // Note: the text points out that w can not be null. + // The reason is not obvious from simply looking at + // the code; it comes about from the properties of the + // red-black tree. + Node* w = xParent->right(); + ASSERT(w); // x's sibling should not be null. + if (w->color() == Red) { + // Case 1 + w->setColor(Black); + xParent->setColor(Red); + leftRotate(xParent); + w = xParent->right(); + } + if ((!w->left() || w->left()->color() == Black) + && (!w->right() || w->right()->color() == Black)) { + // Case 2 + w->setColor(Red); + x = xParent; + xParent = x->parent(); + } else { + if (!w->right() || w->right()->color() == Black) { + // Case 3 + w->left()->setColor(Black); + w->setColor(Red); + rightRotate(w); + w = xParent->right(); + } + // Case 4 + w->setColor(xParent->color()); + xParent->setColor(Black); + if (w->right()) + w->right()->setColor(Black); + leftRotate(xParent); + x = m_root; + xParent = x->parent(); + } + } else { + // Same as "then" clause with "right" and "left" + // exchanged. + + // Note: the text points out that w can not be null. + // The reason is not obvious from simply looking at + // the code; it comes about from the properties of the + // red-black tree. + Node* w = xParent->left(); + ASSERT(w); // x's sibling should not be null. + if (w->color() == Red) { + // Case 1 + w->setColor(Black); + xParent->setColor(Red); + rightRotate(xParent); + w = xParent->left(); + } + if ((!w->right() || w->right()->color() == Black) + && (!w->left() || w->left()->color() == Black)) { + // Case 2 + w->setColor(Red); + x = xParent; + xParent = x->parent(); + } else { + if (!w->left() || w->left()->color() == Black) { + // Case 3 + w->right()->setColor(Black); + w->setColor(Red); + leftRotate(w); + w = xParent->left(); + } + // Case 4 + w->setColor(xParent->color()); + xParent->setColor(Black); + if (w->left()) + w->left()->setColor(Black); + rightRotate(xParent); + x = m_root; + xParent = x->parent(); + } + } + } + if (x) + x->setColor(Black); + } + + // Deletes the given node from the tree. Note that this + // particular node may not actually be removed from the tree; + // instead, another node might be removed and its contents + // copied into z. + void deleteNode(Node* z) + { + // Y is the node to be unlinked from the tree. + Node* y; + if (!z->left() || !z->right()) + y = z; + else + y = treeSuccessor(z); + + // Y is guaranteed to be non-null at this point. + Node* x; + if (y->left()) + x = y->left(); + else + x = y->right(); + + // X is the child of y which might potentially replace y in + // the tree. X might be null at this point. + Node* xParent; + if (x) { + x->setParent(y->parent()); + xParent = x->parent(); + } else + xParent = y->parent(); + if (!y->parent()) + m_root = x; + else { + if (y == y->parent()->left()) + y->parent()->setLeft(x); + else + y->parent()->setRight(x); + } + if (y != z) { + z->copyFrom(y); + // This node has changed location in the tree and must be updated. + updateNode(z); + // The parent and its parents may now be out of date. + propagateUpdates(z->parent()); + } + + // If we haven't already updated starting from xParent, do so now. + if (xParent && xParent != y && xParent != z) + propagateUpdates(xParent); + if (y->color() == Black) + deleteFixup(x, xParent); + } + + // Visits the subtree rooted at the given node in order. + void visitInorderImpl(Node* node, Visitor* visitor) const + { + if (node->left()) + visitInorderImpl(node->left(), visitor); + visitor->visit(node->data()); + if (node->right()) + visitInorderImpl(node->right(), visitor); + } + + //---------------------------------------------------------------------- + // Helper class for size() + + // A Visitor which simply counts the number of visited elements. + class Counter : public Visitor, public Noncopyable { + public: + Counter() + : m_count(0) { } + + virtual void visit(const T& data) { ++m_count; } + int count() const { return m_count; } + + private: + int m_count; + }; + + //---------------------------------------------------------------------- + // Verification and debugging routines + // + + // Returns in the "blackCount" parameter the number of black + // children along all paths to all leaves of the given node. + bool checkInvariantsFromNode(Node* node, int* blackCount) const + { + // Base case is a leaf node. + if (!node) { + *blackCount = 1; + return true; + } + + // Each node is either red or black. + if (!(node->color() == Red || node->color() == Black)) + return false; + + // Every leaf (or null) is black. + + if (node->color() == Red) { + // Both of its children are black. + if (!((!node->left() || node->left()->color() == Black))) + return false; + if (!((!node->right() || node->right()->color() == Black))) + return false; + } + + // Every simple path to a leaf node contains the same number of + // black nodes. + int leftCount = 0, rightCount = 0; + bool leftValid = checkInvariantsFromNode(node->left(), &leftCount); + bool rightValid = checkInvariantsFromNode(node->right(), &rightCount); + if (!leftValid || !rightValid) + return false; + *blackCount = leftCount + (node->color() == Black ? 1 : 0); + return leftCount == rightCount; + } + +#ifdef NDEBUG + void logIfVerbose(const char* output) const { } +#else + void logIfVerbose(const char* output) const + { + if (m_verboseDebugging) + LOG_ERROR("%s", output); + } +#endif + +#ifndef NDEBUG + // Dumps the subtree rooted at the given node. + void dumpFromNode(Node* node, int indentation) const + { + StringBuilder builder; + for (int i = 0; i < indentation; i++) + builder.append(" "); + builder.append("-"); + if (node) { + builder.append(" "); + builder.append(ValueToString<T>::string(node->data())); + builder.append((node->color() == Black) ? " (black)" : " (red)"); + } + LOG_ERROR("%s", builder.toString().ascii().data()); + if (node) { + dumpFromNode(node->left(), indentation + 2); + dumpFromNode(node->right(), indentation + 2); + } + } +#endif + + //---------------------------------------------------------------------- + // Data members + + RefPtr<PODArena> m_arena; + Node* m_root; + bool m_needsFullOrderingComparisons; +#ifndef NDEBUG + bool m_verboseDebugging; +#endif +}; + +} // namespace WebCore + +#endif // PODRedBlackTree_h diff --git a/Source/WebCore/platform/graphics/gpu/Shader.cpp b/Source/WebCore/platform/graphics/gpu/Shader.cpp new file mode 100644 index 0000000..6978322 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/Shader.cpp @@ -0,0 +1,116 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#if ENABLE(ACCELERATED_2D_CANVAS) + +#include "Shader.h" + +#include "AffineTransform.h" +#include "GraphicsContext3D.h" + +#include <wtf/text/CString.h> + +namespace WebCore { + +// static +void Shader::affineTo3x3(const AffineTransform& transform, float mat[9]) +{ + mat[0] = transform.a(); + mat[1] = transform.b(); + mat[2] = 0.0f; + mat[3] = transform.c(); + mat[4] = transform.d(); + mat[5] = 0.0f; + mat[6] = transform.e(); + mat[7] = transform.f(); + mat[8] = 1.0f; +} + +// static +unsigned Shader::loadShader(GraphicsContext3D* context, unsigned type, const char* shaderSource) +{ + unsigned shader = context->createShader(type); + if (!shader) + return 0; + + String shaderSourceStr(shaderSource); + context->shaderSource(shader, shaderSourceStr); + context->compileShader(shader); + int compileStatus = 0; + context->getShaderiv(shader, GraphicsContext3D::COMPILE_STATUS, &compileStatus); + if (!compileStatus) { + String infoLog = context->getShaderInfoLog(shader); + LOG_ERROR("%s", infoLog.utf8().data()); + context->deleteShader(shader); + return 0; + } + return shader; +} + +// static +unsigned Shader::loadProgram(GraphicsContext3D* context, const char* vertexShaderSource, const char* fragmentShaderSource) +{ + unsigned vertexShader = loadShader(context, GraphicsContext3D::VERTEX_SHADER, vertexShaderSource); + if (!vertexShader) + return 0; + unsigned fragmentShader = loadShader(context, GraphicsContext3D::FRAGMENT_SHADER, fragmentShaderSource); + if (!fragmentShader) + return 0; + unsigned program = context->createProgram(); + if (!program) + return 0; + context->attachShader(program, vertexShader); + context->attachShader(program, fragmentShader); + context->linkProgram(program); + int linkStatus = 0; + context->getProgramiv(program, GraphicsContext3D::LINK_STATUS, &linkStatus); + if (!linkStatus) + context->deleteProgram(program); + context->deleteShader(vertexShader); + context->deleteShader(fragmentShader); + return program; +} + +Shader::Shader(GraphicsContext3D* context, unsigned program) + : m_context(context) + , m_program(program) +{ +} + +Shader::~Shader() +{ + m_context->deleteProgram(m_program); +} + +} + +#endif diff --git a/Source/WebCore/platform/graphics/gpu/Shader.h b/Source/WebCore/platform/graphics/gpu/Shader.h new file mode 100644 index 0000000..e5bd8de --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/Shader.h @@ -0,0 +1,58 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef Shader_h +#define Shader_h + +#include <wtf/Noncopyable.h> +#include <wtf/PassOwnPtr.h> + +namespace WebCore { + +class AffineTransform; +class GraphicsContext3D; +class Color; + +class Shader : public Noncopyable { +protected: + Shader(GraphicsContext3D*, unsigned program); + ~Shader(); + + static void affineTo3x3(const AffineTransform&, float mat[9]); + static unsigned loadShader(GraphicsContext3D*, unsigned type, const char* shaderSource); + static unsigned loadProgram(GraphicsContext3D*, const char* vertexShaderSource, const char* fragmentShaderSource); + + GraphicsContext3D* m_context; + unsigned m_program; +}; + +} + +#endif // Shader_h diff --git a/Source/WebCore/platform/graphics/gpu/SharedGraphicsContext3D.cpp b/Source/WebCore/platform/graphics/gpu/SharedGraphicsContext3D.cpp new file mode 100644 index 0000000..9d1298f --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/SharedGraphicsContext3D.cpp @@ -0,0 +1,348 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#if ENABLE(ACCELERATED_2D_CANVAS) + +#include "SharedGraphicsContext3D.h" + +#include "AffineTransform.h" +#include "Color.h" +#include "Extensions3D.h" +#include "FloatRect.h" +#include "IntSize.h" +#include "SolidFillShader.h" +#include "TexShader.h" + +#include <wtf/text/CString.h> +#include <wtf/text/WTFString.h> + +namespace WebCore { + +// static +PassRefPtr<SharedGraphicsContext3D> SharedGraphicsContext3D::create(HostWindow* hostWindow) +{ + GraphicsContext3D::Attributes attr; + attr.canRecoverFromContextLoss = false; // Canvas contexts can not handle lost contexts. + RefPtr<GraphicsContext3D> context = GraphicsContext3D::create(attr, hostWindow); + if (!context) + return 0; + OwnPtr<SolidFillShader> solidFillShader = SolidFillShader::create(context.get()); + if (!solidFillShader) + return 0; + OwnPtr<TexShader> texShader = TexShader::create(context.get()); + if (!texShader) + return 0; + return adoptRef(new SharedGraphicsContext3D(context.release(), solidFillShader.release(), texShader.release())); +} + +SharedGraphicsContext3D::SharedGraphicsContext3D(PassRefPtr<GraphicsContext3D> context, PassOwnPtr<SolidFillShader> solidFillShader, PassOwnPtr<TexShader> texShader) + : m_context(context) + , m_bgraSupported(false) + , m_quadVertices(0) + , m_solidFillShader(solidFillShader) + , m_texShader(texShader) +{ + allContexts()->add(this); + Extensions3D* extensions = m_context->getExtensions(); + m_bgraSupported = extensions->supports("GL_EXT_texture_format_BGRA8888") && extensions->supports("GL_EXT_read_format_bgra"); + if (m_bgraSupported) { + extensions->ensureEnabled("GL_EXT_texture_format_BGRA8888"); + extensions->ensureEnabled("GL_EXT_read_format_bgra"); + } +} + +SharedGraphicsContext3D::~SharedGraphicsContext3D() +{ + m_context->deleteBuffer(m_quadVertices); + allContexts()->remove(this); +} + +void SharedGraphicsContext3D::makeContextCurrent() +{ + m_context->makeContextCurrent(); +} + +void SharedGraphicsContext3D::scissor(const FloatRect& rect) +{ + m_context->scissor(rect.x(), rect.y(), rect.width(), rect.height()); +} + +void SharedGraphicsContext3D::enable(GC3Denum capacity) +{ + m_context->enable(capacity); +} + +void SharedGraphicsContext3D::disable(GC3Denum capacity) +{ + m_context->disable(capacity); +} + +void SharedGraphicsContext3D::clearColor(const Color& color) +{ + float rgba[4]; + color.getRGBA(rgba[0], rgba[1], rgba[2], rgba[3]); + m_context->clearColor(rgba[0], rgba[1], rgba[2], rgba[3]); +} + +void SharedGraphicsContext3D::clear(GC3Dbitfield mask) +{ + m_context->clear(mask); +} + +void SharedGraphicsContext3D::drawArrays(GC3Denum mode, GC3Dint first, GC3Dsizei count) +{ + m_context->drawArrays(mode, first, count); +} + +GC3Denum SharedGraphicsContext3D::getError() +{ + return m_context->getError(); +} + +void SharedGraphicsContext3D::getIntegerv(GC3Denum pname, GC3Dint* value) +{ + m_context->getIntegerv(pname, value); +} + +void SharedGraphicsContext3D::flush() +{ + m_context->flush(); +} + +Platform3DObject SharedGraphicsContext3D::createFramebuffer() +{ + return m_context->createFramebuffer(); +} + +Platform3DObject SharedGraphicsContext3D::createTexture() +{ + return m_context->createTexture(); +} + +void SharedGraphicsContext3D::deleteFramebuffer(Platform3DObject framebuffer) +{ + m_context->deleteFramebuffer(framebuffer); +} + +void SharedGraphicsContext3D::deleteTexture(Platform3DObject texture) +{ + m_context->deleteTexture(texture); +} + +void SharedGraphicsContext3D::framebufferTexture2D(GC3Denum target, GC3Denum attachment, GC3Denum textarget, Platform3DObject texture, GC3Dint level) +{ + m_context->framebufferTexture2D(target, attachment, textarget, texture, level); +} + +void SharedGraphicsContext3D::texParameteri(GC3Denum target, GC3Denum pname, GC3Dint param) +{ + m_context->texParameteri(target, pname, param); +} + +bool SharedGraphicsContext3D::texImage2D(GC3Denum target, GC3Dint level, GC3Denum internalformat, GC3Dsizei width, GC3Dsizei height, GC3Dint border, GC3Denum format, GC3Denum type, const void* pixels) +{ + if (!pixels) + return m_context->texImage2DResourceSafe(target, level, internalformat, width, height, border, format, type); + return m_context->texImage2D(target, level, internalformat, width, height, border, format, type, pixels); +} + +void SharedGraphicsContext3D::texSubImage2D(GC3Denum target, GC3Dint level, GC3Dint xoffset, GC3Dint yoffset, GC3Dsizei width, GC3Dsizei height, GC3Denum format, GC3Denum type, const void* pixels) +{ + m_context->texSubImage2D(target, level, xoffset, yoffset, width, height, format, type, pixels); +} + +void SharedGraphicsContext3D::readPixels(GC3Dint x, GC3Dint y, GC3Dsizei width, GC3Dsizei height, GC3Denum format, GC3Denum type, void* data) +{ + m_context->readPixels(x, y, width, height, format, type, data); +} + +bool SharedGraphicsContext3D::supportsBGRA() +{ + return m_bgraSupported; +} + +Texture* SharedGraphicsContext3D::createTexture(NativeImagePtr ptr, Texture::Format format, int width, int height) +{ + RefPtr<Texture> texture = m_textures.get(ptr); + if (texture) + return texture.get(); + + texture = Texture::create(m_context.get(), format, width, height); + Texture* t = texture.get(); + m_textures.set(ptr, texture); + return t; +} + +Texture* SharedGraphicsContext3D::getTexture(NativeImagePtr ptr) +{ + RefPtr<Texture> texture = m_textures.get(ptr); + return texture ? texture.get() : 0; +} + +void SharedGraphicsContext3D::removeTextureFor(NativeImagePtr ptr) +{ + TextureHashMap::iterator it = m_textures.find(ptr); + if (it != m_textures.end()) + m_textures.remove(it); +} + +// static +void SharedGraphicsContext3D::removeTexturesFor(NativeImagePtr ptr) +{ + for (HashSet<SharedGraphicsContext3D*>::iterator it = allContexts()->begin(); it != allContexts()->end(); ++it) + (*it)->removeTextureFor(ptr); +} + +// static +HashSet<SharedGraphicsContext3D*>* SharedGraphicsContext3D::allContexts() +{ + DEFINE_STATIC_LOCAL(HashSet<SharedGraphicsContext3D*>, allContextsSet, ()); + return &allContextsSet; +} + + +PassRefPtr<Texture> SharedGraphicsContext3D::createTexture(Texture::Format format, int width, int height) +{ + return Texture::create(m_context.get(), format, width, height); +} + +void SharedGraphicsContext3D::applyCompositeOperator(CompositeOperator op) +{ + switch (op) { + case CompositeClear: + m_context->enable(GraphicsContext3D::BLEND); + m_context->blendFunc(GraphicsContext3D::ZERO, GraphicsContext3D::ZERO); + break; + case CompositeCopy: + m_context->disable(GraphicsContext3D::BLEND); + break; + case CompositeSourceOver: + m_context->enable(GraphicsContext3D::BLEND); + m_context->blendFunc(GraphicsContext3D::ONE, GraphicsContext3D::ONE_MINUS_SRC_ALPHA); + break; + case CompositeSourceIn: + m_context->enable(GraphicsContext3D::BLEND); + m_context->blendFunc(GraphicsContext3D::DST_ALPHA, GraphicsContext3D::ZERO); + break; + case CompositeSourceOut: + m_context->enable(GraphicsContext3D::BLEND); + m_context->blendFunc(GraphicsContext3D::ONE_MINUS_DST_ALPHA, GraphicsContext3D::ZERO); + break; + case CompositeSourceAtop: + m_context->enable(GraphicsContext3D::BLEND); + m_context->blendFunc(GraphicsContext3D::DST_ALPHA, GraphicsContext3D::ONE_MINUS_SRC_ALPHA); + break; + case CompositeDestinationOver: + m_context->enable(GraphicsContext3D::BLEND); + m_context->blendFunc(GraphicsContext3D::ONE_MINUS_DST_ALPHA, GraphicsContext3D::ONE); + break; + case CompositeDestinationIn: + m_context->enable(GraphicsContext3D::BLEND); + m_context->blendFunc(GraphicsContext3D::ZERO, GraphicsContext3D::SRC_ALPHA); + break; + case CompositeDestinationOut: + m_context->enable(GraphicsContext3D::BLEND); + m_context->blendFunc(GraphicsContext3D::ZERO, GraphicsContext3D::ONE_MINUS_SRC_ALPHA); + break; + case CompositeDestinationAtop: + m_context->enable(GraphicsContext3D::BLEND); + m_context->blendFunc(GraphicsContext3D::ONE_MINUS_DST_ALPHA, GraphicsContext3D::SRC_ALPHA); + break; + case CompositeXOR: + m_context->enable(GraphicsContext3D::BLEND); + m_context->blendFunc(GraphicsContext3D::ONE_MINUS_DST_ALPHA, GraphicsContext3D::ONE_MINUS_SRC_ALPHA); + break; + case CompositePlusDarker: + case CompositeHighlight: + // unsupported + m_context->disable(GraphicsContext3D::BLEND); + break; + case CompositePlusLighter: + m_context->enable(GraphicsContext3D::BLEND); + m_context->blendFunc(GraphicsContext3D::ONE, GraphicsContext3D::ONE); + break; + } +} + +void SharedGraphicsContext3D::useQuadVertices() +{ + if (!m_quadVertices) { + float vertices[] = { 0.0f, 0.0f, 1.0f, + 1.0f, 0.0f, 1.0f, + 0.0f, 1.0f, 1.0f, + 1.0f, 1.0f, 1.0f }; + m_quadVertices = m_context->createBuffer(); + m_context->bindBuffer(GraphicsContext3D::ARRAY_BUFFER, m_quadVertices); + m_context->bufferData(GraphicsContext3D::ARRAY_BUFFER, sizeof(vertices), vertices, GraphicsContext3D::STATIC_DRAW); + } else { + m_context->bindBuffer(GraphicsContext3D::ARRAY_BUFFER, m_quadVertices); + } +} + +void SharedGraphicsContext3D::setActiveTexture(GC3Denum textureUnit) +{ + m_context->activeTexture(textureUnit); +} + +void SharedGraphicsContext3D::bindTexture(GC3Denum target, Platform3DObject texture) +{ + m_context->bindTexture(target, texture); +} + +void SharedGraphicsContext3D::useFillSolidProgram(const AffineTransform& transform, const Color& color) +{ + m_solidFillShader->use(transform, color); +} + +void SharedGraphicsContext3D::useTextureProgram(const AffineTransform& transform, const AffineTransform& texTransform, float alpha) +{ + m_texShader->use(transform, texTransform, 0, alpha); +} + +void SharedGraphicsContext3D::bindFramebuffer(Platform3DObject framebuffer) +{ + m_context->bindFramebuffer(GraphicsContext3D::FRAMEBUFFER, framebuffer); +} + +void SharedGraphicsContext3D::setViewport(const IntSize& size) +{ + m_context->viewport(0, 0, size.width(), size.height()); +} + +bool SharedGraphicsContext3D::paintsIntoCanvasBuffer() const +{ + return m_context->paintsIntoCanvasBuffer(); +} + +} // namespace WebCore + +#endif diff --git a/Source/WebCore/platform/graphics/gpu/SharedGraphicsContext3D.h b/Source/WebCore/platform/graphics/gpu/SharedGraphicsContext3D.h new file mode 100644 index 0000000..ea1810d --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/SharedGraphicsContext3D.h @@ -0,0 +1,139 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef SharedGraphicsContext3D_h +#define SharedGraphicsContext3D_h + +#include "GraphicsContext3D.h" +#include "GraphicsTypes.h" +#include "ImageSource.h" +#include "Texture.h" + +#include <wtf/HashMap.h> +#include <wtf/HashSet.h> +#include <wtf/OwnPtr.h> +#include <wtf/RefCounted.h> +#include <wtf/RefPtr.h> + +namespace WebCore { + +class AffineTransform; +class Color; +class FloatRect; +class HostWindow; +class IntSize; +class SolidFillShader; +class TexShader; + +typedef HashMap<NativeImagePtr, RefPtr<Texture> > TextureHashMap; + +class SharedGraphicsContext3D : public RefCounted<SharedGraphicsContext3D> { +public: + static PassRefPtr<SharedGraphicsContext3D> create(HostWindow*); + ~SharedGraphicsContext3D(); + + // Functions that delegate directly to GraphicsContext3D, with caching + void makeContextCurrent(); + void bindFramebuffer(Platform3DObject framebuffer); + void setViewport(const IntSize&); + void scissor(const FloatRect&); + void enable(GC3Denum capacity); + void disable(GC3Denum capacity); + void clearColor(const Color&); + void clear(GC3Dbitfield mask); + void drawArrays(GC3Denum mode, GC3Dint first, GC3Dsizei count); + GC3Denum getError(); + void getIntegerv(GC3Denum pname, GC3Dint* value); + void flush(); + + Platform3DObject createFramebuffer(); + Platform3DObject createTexture(); + + void deleteFramebuffer(Platform3DObject framebuffer); + void deleteTexture(Platform3DObject texture); + + void framebufferTexture2D(GC3Denum target, GC3Denum attachment, GC3Denum textarget, Platform3DObject, GC3Dint level); + void texParameteri(GC3Denum target, GC3Denum pname, GC3Dint param); + bool texImage2D(GC3Denum target, GC3Dint level, GC3Denum internalformat, GC3Dsizei width, GC3Dsizei height, GC3Dint border, GC3Denum format, GC3Denum type, const void* pixels); + void texSubImage2D(GC3Denum target, GC3Dint level, GC3Dint xoffset, GC3Dint yoffset, GC3Dsizei width, GC3Dsizei height, GC3Denum format, GC3Denum type, const void* pixels); + + void readPixels(GC3Dint x, GC3Dint y, GC3Dsizei width, GC3Dsizei height, GC3Denum format, GC3Denum type, void* data); + + bool paintsIntoCanvasBuffer() const; + + // Shared logic for canvas 2d + void applyCompositeOperator(CompositeOperator); + void useQuadVertices(); + + void useFillSolidProgram(const AffineTransform&, const Color&); + void useTextureProgram(const AffineTransform&, const AffineTransform&, float alpha); + + void setActiveTexture(GC3Denum textureUnit); + void bindTexture(GC3Denum target, Platform3DObject texture); + + bool supportsBGRA(); + + // Creates a texture associated with the given image. Is owned by this context's + // TextureHashMap. + Texture* createTexture(NativeImagePtr, Texture::Format, int width, int height); + Texture* getTexture(NativeImagePtr); + + // Multiple SharedGraphicsContext3D can exist in a single process (one per compositing context) and the same + // NativeImagePtr may be uploaded as a texture into all of them. This function removes uploaded textures + // for a given NativeImagePtr in all contexts. + static void removeTexturesFor(NativeImagePtr); + + // Creates a texture that is not associated with any image. The caller takes ownership of + // the texture. + PassRefPtr<Texture> createTexture(Texture::Format, int width, int height); + + GraphicsContext3D* graphicsContext3D() const { return m_context.get(); } + +private: + SharedGraphicsContext3D(PassRefPtr<GraphicsContext3D>, PassOwnPtr<SolidFillShader>, PassOwnPtr<TexShader>); + + // Used to implement removeTexturesFor(), see the comment above. + static HashSet<SharedGraphicsContext3D*>* allContexts(); + void removeTextureFor(NativeImagePtr); + + RefPtr<GraphicsContext3D> m_context; + bool m_bgraSupported; + + unsigned m_quadVertices; + + OwnPtr<SolidFillShader> m_solidFillShader; + OwnPtr<TexShader> m_texShader; + + TextureHashMap m_textures; +}; + +} // namespace WebCore + +#endif // SharedGraphicsContext3D_h diff --git a/Source/WebCore/platform/graphics/gpu/SolidFillShader.cpp b/Source/WebCore/platform/graphics/gpu/SolidFillShader.cpp new file mode 100644 index 0000000..86079be --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/SolidFillShader.cpp @@ -0,0 +1,93 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#if ENABLE(ACCELERATED_2D_CANVAS) + +#include "SolidFillShader.h" + +#include "Color.h" +#include "GraphicsContext3D.h" + +namespace WebCore { + +SolidFillShader::SolidFillShader(GraphicsContext3D* context, unsigned program) + : Shader(context, program) +{ + m_matrixLocation = context->getUniformLocation(program, "matrix"); + m_colorLocation = context->getUniformLocation(program, "color"); + m_positionLocation = context->getAttribLocation(program, "position"); +} + +PassOwnPtr<SolidFillShader> SolidFillShader::create(GraphicsContext3D* context) +{ + static const char* vertexShaderSource = + "uniform mat3 matrix;\n" + "uniform vec4 color;\n" + "attribute vec3 position;\n" + "void main() {\n" + " gl_Position = vec4(matrix * position, 1.0);\n" + "}\n"; + static const char* fragmentShaderSource = + "#ifdef GL_ES\n" + "precision mediump float;\n" + "#endif\n" + "uniform mat3 matrix;\n" + "uniform vec4 color;\n" + "void main() {\n" + " gl_FragColor = color;\n" + "}\n"; + unsigned program = loadProgram(context, vertexShaderSource, fragmentShaderSource); + if (!program) + return 0; + return new SolidFillShader(context, program); +} + +void SolidFillShader::use(const AffineTransform& transform, const Color& color) +{ + m_context->useProgram(m_program); + + float rgba[4]; + color.getRGBA(rgba[0], rgba[1], rgba[2], rgba[3]); + m_context->uniform4f(m_colorLocation, rgba[0] * rgba[3], rgba[1] * rgba[3], rgba[2] * rgba[3], rgba[3]); + + float matrix[9]; + affineTo3x3(transform, matrix); + m_context->uniformMatrix3fv(m_matrixLocation, false /*transpose*/, matrix, 1 /*count*/); + + m_context->vertexAttribPointer(m_positionLocation, 3, GraphicsContext3D::FLOAT, false, 0, 0); + + m_context->enableVertexAttribArray(m_positionLocation); +} + +} + +#endif diff --git a/Source/WebCore/platform/graphics/gpu/SolidFillShader.h b/Source/WebCore/platform/graphics/gpu/SolidFillShader.h new file mode 100644 index 0000000..1071e73 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/SolidFillShader.h @@ -0,0 +1,53 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef SolidFillShader_h +#define SolidFillShader_h + +#include "Shader.h" + +namespace WebCore { + +class SolidFillShader : public Shader { +public: + static PassOwnPtr<SolidFillShader> create(GraphicsContext3D* context); + void use(const AffineTransform& transform, const Color& color); + +private: + SolidFillShader(GraphicsContext3D* context, unsigned program); + + int m_matrixLocation; + int m_colorLocation; + int m_positionLocation; +}; + +} + +#endif // SolidFillShader_h diff --git a/Source/WebCore/platform/graphics/gpu/TexShader.cpp b/Source/WebCore/platform/graphics/gpu/TexShader.cpp new file mode 100644 index 0000000..d7ffa17 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/TexShader.cpp @@ -0,0 +1,100 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#if ENABLE(ACCELERATED_2D_CANVAS) + +#include "TexShader.h" + +#include "GraphicsContext3D.h" + +namespace WebCore { + +TexShader::TexShader(GraphicsContext3D* context, unsigned program) + : Shader(context, program) +{ + m_matrixLocation = context->getUniformLocation(program, "matrix"); + m_texMatrixLocation = context->getUniformLocation(program, "texMatrix"); + m_alphaLocation = context->getUniformLocation(program, "alpha"); + m_positionLocation = context->getAttribLocation(program, "position"); + m_samplerLocation = context->getUniformLocation(program, "sampler"); +} + +PassOwnPtr<TexShader> TexShader::create(GraphicsContext3D* context) +{ + static const char* vertexShaderSource = + "uniform mat3 matrix;\n" + "uniform mat3 texMatrix;\n" + "attribute vec3 position;\n" + "varying vec3 texCoord;\n" + "void main() {\n" + " texCoord = texMatrix * position;\n" + " gl_Position = vec4(matrix * position, 1.0);\n" + "}\n"; + static const char* fragmentShaderSource = + "#ifdef GL_ES\n" + "precision mediump float;\n" + "#endif\n" + "uniform sampler2D sampler;\n" + "uniform float alpha;\n" + "varying vec3 texCoord;\n" + "void main() {\n" + " gl_FragColor = texture2D(sampler, texCoord.xy)* vec4(alpha);\n" + "}\n"; + unsigned program = loadProgram(context, vertexShaderSource, fragmentShaderSource); + if (!program) + return 0; + return new TexShader(context, program); +} + +void TexShader::use(const AffineTransform& transform, const AffineTransform& texTransform, int sampler, float alpha) +{ + m_context->useProgram(m_program); + float matrix[9]; + affineTo3x3(transform, matrix); + m_context->uniformMatrix3fv(m_matrixLocation, false /*transpose*/, matrix, 1 /*count*/); + + float texMatrix[9]; + affineTo3x3(texTransform, texMatrix); + m_context->uniformMatrix3fv(m_texMatrixLocation, false /*transpose*/, texMatrix, 1 /*count*/); + + m_context->uniform1i(m_samplerLocation, sampler); + m_context->uniform1f(m_alphaLocation, alpha); + + m_context->vertexAttribPointer(m_positionLocation, 3, GraphicsContext3D::FLOAT, false, 0, 0); + + m_context->enableVertexAttribArray(m_positionLocation); + +} + +} + +#endif diff --git a/Source/WebCore/platform/graphics/gpu/TexShader.h b/Source/WebCore/platform/graphics/gpu/TexShader.h new file mode 100644 index 0000000..535997d --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/TexShader.h @@ -0,0 +1,55 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef TexShader_h +#define TexShader_h + +#include "Shader.h" + +namespace WebCore { + +class TexShader : public Shader { +public: + static PassOwnPtr<TexShader> create(GraphicsContext3D* context); + void use(const AffineTransform& transform, const AffineTransform& texTransform, int sampler, float alpha); + +private: + TexShader(GraphicsContext3D* context, unsigned program); + + int m_matrixLocation; + int m_texMatrixLocation; + int m_samplerLocation; + int m_alphaLocation; + int m_positionLocation; +}; + +} + +#endif // TexShader_h diff --git a/Source/WebCore/platform/graphics/gpu/Texture.cpp b/Source/WebCore/platform/graphics/gpu/Texture.cpp new file mode 100644 index 0000000..e1f8114 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/Texture.cpp @@ -0,0 +1,216 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#if ENABLE(ACCELERATED_2D_CANVAS) + +#include "Texture.h" + +#include "Extensions3D.h" +#include "FloatRect.h" +#include "GraphicsContext3D.h" +#include "IntRect.h" + +#include <algorithm> +#include <wtf/OwnArrayPtr.h> + +using namespace std; + +namespace WebCore { + + +Texture::Texture(GraphicsContext3D* context, PassOwnPtr<Vector<unsigned int> > tileTextureIds, Format format, int width, int height, int maxTextureSize) + : m_context(context) + , m_format(format) + , m_tiles(maxTextureSize, width, height, true) + , m_tileTextureIds(tileTextureIds) +{ +} + +Texture::~Texture() +{ + for (unsigned int i = 0; i < m_tileTextureIds->size(); i++) + m_context->deleteTexture(m_tileTextureIds->at(i)); +} + +static void convertFormat(GraphicsContext3D* context, Texture::Format format, unsigned int* glFormat, unsigned int* glType, bool* swizzle) +{ + *swizzle = false; + switch (format) { + case Texture::RGBA8: + *glFormat = GraphicsContext3D::RGBA; + *glType = GraphicsContext3D::UNSIGNED_BYTE; + break; + case Texture::BGRA8: + if (context->getExtensions()->supports("GL_EXT_texture_format_BGRA8888")) { + *glFormat = Extensions3D::BGRA_EXT; + *glType = GraphicsContext3D::UNSIGNED_BYTE; + } else { + *glFormat = GraphicsContext3D::RGBA; + *glType = GraphicsContext3D::UNSIGNED_BYTE; + *swizzle = true; + } + break; + default: + ASSERT_NOT_REACHED(); + break; + } +} + +PassRefPtr<Texture> Texture::create(GraphicsContext3D* context, Format format, int width, int height) +{ + int maxTextureSize = 0; + context->getIntegerv(GraphicsContext3D::MAX_TEXTURE_SIZE, &maxTextureSize); + TilingData tiling(maxTextureSize, width, height, true); + int numTiles = tiling.numTiles(); + + OwnPtr<Vector<unsigned int> > textureIds(new Vector<unsigned int>(numTiles)); + textureIds->fill(0, numTiles); + + for (int i = 0; i < numTiles; i++) { + int textureId = context->createTexture(); + if (!textureId) { + for (int i = 0; i < numTiles; i++) + context->deleteTexture(textureIds->at(i)); + return 0; + } + textureIds->at(i) = textureId; + + IntRect tileBoundsWithBorder = tiling.tileBoundsWithBorder(i); + + unsigned int glFormat = 0; + unsigned int glType = 0; + bool swizzle; + convertFormat(context, format, &glFormat, &glType, &swizzle); + context->bindTexture(GraphicsContext3D::TEXTURE_2D, textureId); + context->texImage2DResourceSafe(GraphicsContext3D::TEXTURE_2D, 0, glFormat, + tileBoundsWithBorder.width(), + tileBoundsWithBorder.height(), + 0, glFormat, glType); + } + return adoptRef(new Texture(context, textureIds.leakPtr(), format, width, height, maxTextureSize)); +} + +template <bool swizzle> +static uint32_t* copySubRect(uint32_t* src, int srcX, int srcY, uint32_t* dst, int width, int height, int srcStride) +{ + uint32_t* srcOffset = src + srcX + srcY * srcStride; + + if (!swizzle && width == srcStride) + return srcOffset; + + if (swizzle) { + uint32_t* dstPixel = dst; + for (int y = 0; y < height; ++y) { + for (int x = 0; x < width ; ++x) { + uint32_t pixel = srcOffset[x + y * srcStride]; + *dstPixel = (pixel & 0xFF00FF00) | ((pixel & 0x00FF0000) >> 16) | ((pixel & 0x000000FF) << 16); + dstPixel++; + } + } + } else { + for (int y = 0; y < height; ++y) { + memcpy(dst + y * width, srcOffset + y * srcStride, 4 * width); + } + } + return dst; +} + +void Texture::load(void* pixels) +{ + updateSubRect(pixels, IntRect(0, 0, m_tiles.totalSizeX(), m_tiles.totalSizeY())); +} + +void Texture::updateSubRect(void* pixels, const IntRect& updateRect) +{ + IntRect updateRectSanitized(updateRect); + updateRectSanitized.intersect(IntRect(0, 0, m_tiles.totalSizeX(), m_tiles.totalSizeY())); + + uint32_t* pixels32 = static_cast<uint32_t*>(pixels); + unsigned int glFormat = 0; + unsigned int glType = 0; + bool swizzle; + convertFormat(m_context, m_format, &glFormat, &glType, &swizzle); + if (swizzle) { + ASSERT(glFormat == GraphicsContext3D::RGBA && glType == GraphicsContext3D::UNSIGNED_BYTE); + // FIXME: This could use PBO's to save doing an extra copy here. + } + int tempBuffSize = // Temporary buffer size is the smaller of the max texture size or the updateRectSanitized + min(m_tiles.maxTextureSize(), m_tiles.borderTexels() + updateRectSanitized.width()) * + min(m_tiles.maxTextureSize(), m_tiles.borderTexels() + updateRectSanitized.height()); + OwnArrayPtr<uint32_t> tempBuff(new uint32_t[tempBuffSize]); + + for (int tile = 0; tile < m_tiles.numTiles(); tile++) { + // Intersect with tile + IntRect tileBoundsWithBorder = m_tiles.tileBoundsWithBorder(tile); + + IntRect updateRectIntersected = updateRectSanitized; + updateRectIntersected.intersect(tileBoundsWithBorder); + + IntRect dstRect = updateRectIntersected; + dstRect.move(-tileBoundsWithBorder.x(), -tileBoundsWithBorder.y()); + + if (updateRectIntersected.isEmpty()) + continue; + + // Copy sub rectangle out of larger pixel data + uint32_t* uploadBuff = 0; + if (swizzle) { + uploadBuff = copySubRect<true>( + pixels32, updateRectIntersected.x(), updateRectIntersected.y(), + tempBuff.get(), updateRectIntersected.width(), updateRectIntersected.height(), m_tiles.totalSizeX()); + } else { + uploadBuff = copySubRect<false>( + pixels32, updateRectIntersected.x(), updateRectIntersected.y(), + tempBuff.get(), updateRectIntersected.width(), updateRectIntersected.height(), m_tiles.totalSizeX()); + } + + m_context->bindTexture(GraphicsContext3D::TEXTURE_2D, m_tileTextureIds->at(tile)); + m_context->texSubImage2D(GraphicsContext3D::TEXTURE_2D, 0 /* level */, + dstRect.x(), + dstRect.y(), + updateRectIntersected.width(), + updateRectIntersected.height(), glFormat, glType, uploadBuff); + } +} + +void Texture::bindTile(int tile) +{ + m_context->bindTexture(GraphicsContext3D::TEXTURE_2D, m_tileTextureIds->at(tile)); + m_context->texParameteri(GraphicsContext3D::TEXTURE_2D, GraphicsContext3D::TEXTURE_MIN_FILTER, GraphicsContext3D::LINEAR); + m_context->texParameteri(GraphicsContext3D::TEXTURE_2D, GraphicsContext3D::TEXTURE_MAG_FILTER, GraphicsContext3D::LINEAR); + m_context->texParameteri(GraphicsContext3D::TEXTURE_2D, GraphicsContext3D::TEXTURE_WRAP_S, GraphicsContext3D::CLAMP_TO_EDGE); + m_context->texParameteri(GraphicsContext3D::TEXTURE_2D, GraphicsContext3D::TEXTURE_WRAP_T, GraphicsContext3D::CLAMP_TO_EDGE); +} + +} + +#endif diff --git a/Source/WebCore/platform/graphics/gpu/Texture.h b/Source/WebCore/platform/graphics/gpu/Texture.h new file mode 100644 index 0000000..1f35006 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/Texture.h @@ -0,0 +1,66 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef Texture_h +#define Texture_h + +#include "TilingData.h" +#include <wtf/OwnPtr.h> +#include <wtf/PassOwnPtr.h> +#include <wtf/RefCounted.h> +#include <wtf/RefPtr.h> +#include <wtf/Vector.h> + +namespace WebCore { +class GraphicsContext3D; + +class IntRect; + +class Texture : public RefCounted<Texture> { +public: + ~Texture(); + enum Format { RGBA8, BGRA8 }; + static PassRefPtr<Texture> create(GraphicsContext3D*, Format, int width, int height); + void bindTile(int tile); + void load(void* pixels); + void updateSubRect(void* pixels, const IntRect&); + Format format() const { return m_format; } + const TilingData& tiles() const { return m_tiles; } +private: + Texture(GraphicsContext3D*, PassOwnPtr<Vector<unsigned int> > tileTextureIds, Format format, int width, int height, int maxTextureSize); + GraphicsContext3D* m_context; + Format m_format; + TilingData m_tiles; + OwnPtr<Vector<unsigned int> > m_tileTextureIds; +}; + +} + +#endif // Texture_h diff --git a/Source/WebCore/platform/graphics/gpu/TilingData.cpp b/Source/WebCore/platform/graphics/gpu/TilingData.cpp new file mode 100644 index 0000000..a98add7 --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/TilingData.cpp @@ -0,0 +1,227 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#if ENABLE(ACCELERATED_2D_CANVAS) + +#include "TilingData.h" + +#include "FloatRect.h" +#include "IntRect.h" +#include <algorithm> + +using namespace std; + +namespace WebCore { + +static int computeNumTiles(int maxTextureSize, int totalSize, int borderTexels) +{ + return max(1, 1 + (totalSize - 1 - 2 * borderTexels) / (maxTextureSize - 2 * borderTexels)); +} + +TilingData::TilingData(int maxTextureSize, int totalSizeX, int totalSizeY, bool hasBorderTexels) + : m_maxTextureSize(maxTextureSize) + , m_totalSizeX(totalSizeX) + , m_totalSizeY(totalSizeY) + , m_borderTexels(hasBorderTexels ? 1 : 0) +{ + m_numTilesX = computeNumTiles(maxTextureSize, m_totalSizeX, m_borderTexels); + m_numTilesY = computeNumTiles(maxTextureSize, m_totalSizeY, m_borderTexels); +} + +int TilingData::tileXIndexFromSrcCoord(int srcPos) const +{ + int x = (srcPos - m_borderTexels) / (m_maxTextureSize - 2 * m_borderTexels); + return min(max(x, 0), numTilesX() - 1); +} + +int TilingData::tileYIndexFromSrcCoord(int srcPos) const +{ + int y = (srcPos - m_borderTexels) / (m_maxTextureSize - 2 * m_borderTexels); + return min(max(y, 0), numTilesY() - 1); +} + +IntRect TilingData::tileBounds(int tile) const +{ + assertTile(tile); + int ix = tileXIndex(tile); + int iy = tileYIndex(tile); + int x = tilePositionX(ix); + int y = tilePositionY(iy); + int width = tileSizeX(ix); + int height = tileSizeY(iy); + ASSERT(x >= 0 && y >= 0 && width >= 0 && height >= 0); + ASSERT(x <= totalSizeX() && y <= totalSizeY()); + return IntRect(x, y, width, height); +} + +IntRect TilingData::tileBoundsWithBorder(int tile) const +{ + IntRect bounds = tileBounds(tile); + + if (m_borderTexels) { + int x1 = bounds.x(); + int x2 = bounds.right(); + int y1 = bounds.y(); + int y2 = bounds.bottom(); + + if (tileXIndex(tile) > 0) + x1--; + if (tileXIndex(tile) < (numTilesX() - 1)) + x2++; + if (tileYIndex(tile) > 0) + y1--; + if (tileYIndex(tile) < (numTilesY() - 1)) + y2++; + + bounds = IntRect(x1, y1, x2 - x1, y2 - y1); + } + + return bounds; +} + +FloatRect TilingData::tileBoundsNormalized(int tile) const +{ + assertTile(tile); + FloatRect bounds(tileBounds(tile)); + bounds.scale(1.0f / m_totalSizeX, 1.0f / m_totalSizeY); + return bounds; +} + +int TilingData::tilePositionX(int xIndex) const +{ + ASSERT(xIndex >= 0 && xIndex < numTilesX()); + + int pos = 0; + for (int i = 0; i < xIndex; i++) + pos += tileSizeX(i); + + return pos; +} + +int TilingData::tilePositionY(int yIndex) const +{ + ASSERT(yIndex >= 0 && yIndex < numTilesY()); + + int pos = 0; + for (int i = 0; i < yIndex; i++) + pos += tileSizeY(i); + + return pos; +} + +int TilingData::tileSizeX(int xIndex) const +{ + ASSERT(xIndex >= 0 && xIndex < numTilesX()); + + int size = maxTextureSize(); + size = min(size, totalSizeX()); + + if (!xIndex && m_numTilesX == 1) + return m_totalSizeX; + if (!xIndex && m_numTilesX > 1) + return m_maxTextureSize - m_borderTexels; + if (xIndex < numTilesX() - 1) + return m_maxTextureSize - 2 * m_borderTexels; + if (xIndex == numTilesX() - 1) + return m_totalSizeX - tilePositionX(xIndex); + + ASSERT_NOT_REACHED(); + return 0; +} + +int TilingData::tileSizeY(int yIndex) const +{ + ASSERT(yIndex >= 0 && yIndex < numTilesY()); + + int size = maxTextureSize(); + size = min(size, totalSizeY()); + + if (!yIndex && m_numTilesY == 1) + return m_totalSizeY; + if (!yIndex && m_numTilesY > 1) + return m_maxTextureSize - m_borderTexels; + if (yIndex < numTilesY() - 1) + return m_maxTextureSize - 2 * m_borderTexels; + if (yIndex == numTilesY() - 1) + return m_totalSizeY - tilePositionY(yIndex); + + ASSERT_NOT_REACHED(); + return 0; +} + +IntRect TilingData::overlappedTileIndices(const WebCore::IntRect &srcRect) const +{ + int x = tileXIndexFromSrcCoord(srcRect.x()); + int y = tileYIndexFromSrcCoord(srcRect.y()); + int r = tileXIndexFromSrcCoord(srcRect.right()); + int b = tileYIndexFromSrcCoord(srcRect.bottom()); + return IntRect(x, y, r - x, b - y); +} + +IntRect TilingData::overlappedTileIndices(const WebCore::FloatRect &srcRect) const +{ + return overlappedTileIndices(enclosingIntRect(srcRect)); +} + +void TilingData::intersectDrawQuad(const FloatRect& srcRect, const FloatRect& dstRect, int tile, + FloatRect* newSrc, FloatRect* newDst) const +{ + // Intersect with tile + FloatRect tileBounds = this->tileBounds(tile); + FloatRect srcRectIntersected = srcRect; + srcRectIntersected.intersect(tileBounds); + + if (srcRectIntersected.isEmpty()) { + *newSrc = *newDst = FloatRect(0, 0, 0, 0); + return; + } + + float srcRectIntersectedNormX = (srcRectIntersected.x() - srcRect.x()) / srcRect.width(); + float srcRectIntersectedNormY = (srcRectIntersected.y() - srcRect.y()) / srcRect.height(); + float srcRectIntersectedNormW = srcRectIntersected.width() / srcRect.width(); + float srcRectIntersectedNormH = srcRectIntersected.height() / srcRect.height(); + + *newSrc = srcRectIntersected; + newSrc->move( + -tileBounds.x() + ((tileXIndex(tile) > 0) ? m_borderTexels : 0), + -tileBounds.y() + ((tileYIndex(tile) > 0) ? m_borderTexels : 0)); + + *newDst = FloatRect( + srcRectIntersectedNormX * dstRect.width() + dstRect.x(), + srcRectIntersectedNormY * dstRect.height() + dstRect.y(), + srcRectIntersectedNormW * dstRect.width(), + srcRectIntersectedNormH * dstRect.height()); +} + +} + +#endif diff --git a/Source/WebCore/platform/graphics/gpu/TilingData.h b/Source/WebCore/platform/graphics/gpu/TilingData.h new file mode 100644 index 0000000..1bdc51a --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/TilingData.h @@ -0,0 +1,88 @@ +/* + * Copyright (c) 2010, Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef TilingData_h +#define TilingData_h + +#include <wtf/Noncopyable.h> + +namespace WebCore { + +class FloatRect; +class IntRect; + +class TilingData : public Noncopyable { +public: + TilingData(int maxTextureSize, int totalSizeX, int totalSizeY, bool hasBorderTexels); + int maxTextureSize() const { return m_maxTextureSize; } + int totalSizeX() const { return m_totalSizeX; } + int totalSizeY() const { return m_totalSizeY; } + int borderTexels() const { return m_borderTexels; } + + int numTiles() const { return numTilesX() * numTilesY(); } + int numTilesX() const { return m_numTilesX; } + int numTilesY() const { return m_numTilesY; } + int tileIndex(int x, int y) const { return x + y * numTilesX(); } + int tileXIndex(int tile) const { assertTile(tile); return tile % numTilesX(); } + int tileYIndex(int tile) const { assertTile(tile); return tile / numTilesX(); } + int tileXIndexFromSrcCoord(int) const; + int tileYIndexFromSrcCoord(int) const; + + IntRect tileBounds(int tile) const; + IntRect tileBoundsWithBorder(int tile) const; + FloatRect tileBoundsNormalized(int tile) const; + int tilePositionX(int xIndex) const; + int tilePositionY(int yIndex) const; + int tileSizeX(int xIndex) const; + int tileSizeY(int yIndex) const; + IntRect overlappedTileIndices(const IntRect& srcRect) const; + IntRect overlappedTileIndices(const FloatRect& srcRect) const; + + // Given a set of source and destination coordinates for a drawing quad + // in texel units, returns adjusted data to render just the one tile. + void intersectDrawQuad(const FloatRect& srcRect, const FloatRect& dstRect, int tile, FloatRect* newSrc, FloatRect* newDst) const; + +private: + TilingData() : m_maxTextureSize(0), m_totalSizeX(0), m_totalSizeY(0) {} + void assertTile(int tile) const { ASSERT(tile >= 0 && tile < numTiles()); } + + int m_maxTextureSize; + int m_totalSizeX; + int m_totalSizeY; + int m_borderTexels; // 0 or 1 + + // computed values: + int m_numTilesX; + int m_numTilesY; +}; + +} + +#endif // TilingData_h diff --git a/Source/WebCore/platform/graphics/gpu/mac/DrawingBufferMac.mm b/Source/WebCore/platform/graphics/gpu/mac/DrawingBufferMac.mm new file mode 100644 index 0000000..89dcb9c --- /dev/null +++ b/Source/WebCore/platform/graphics/gpu/mac/DrawingBufferMac.mm @@ -0,0 +1,119 @@ +/* + * Copyright (C) 2010 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#if ENABLE(ACCELERATED_2D_CANVAS) || ENABLE(3D_CANVAS) + +#include "DrawingBuffer.h" + +#include "Extensions3D.h" +#include "WebGLLayer.h" + +#import "BlockExceptions.h" + +namespace WebCore { + +DrawingBuffer::DrawingBuffer(GraphicsContext3D* context, const IntSize& size) + : m_context(context) + , m_size(size) + , m_fbo(context->createFramebuffer()) + , m_colorBuffer(0) + , m_depthStencilBuffer(0) + , m_multisampleFBO(0) + , m_multisampleColorBuffer(0) + , m_multisampleDepthStencilBuffer(0) +{ + ASSERT(m_fbo); + if (!m_fbo) { + clear(); + return; + } + + // Create the WebGLLayer + BEGIN_BLOCK_OBJC_EXCEPTIONS + m_platformLayer.adoptNS([[WebGLLayer alloc] initWithGraphicsContext3D:m_context.get()]); +#ifndef NDEBUG + [m_platformLayer.get() setName:@"DrawingBuffer Layer"]; +#endif + END_BLOCK_OBJC_EXCEPTIONS + + // create a texture to render into + m_colorBuffer = context->createTexture(); + context->bindTexture(GraphicsContext3D::TEXTURE_2D, m_colorBuffer); + context->texParameterf(GraphicsContext3D::TEXTURE_2D, GraphicsContext3D::TEXTURE_MAG_FILTER, GraphicsContext3D::LINEAR); + context->texParameterf(GraphicsContext3D::TEXTURE_2D, GraphicsContext3D::TEXTURE_MIN_FILTER, GraphicsContext3D::LINEAR); + context->texParameteri(GraphicsContext3D::TEXTURE_2D, GraphicsContext3D::TEXTURE_WRAP_S, GraphicsContext3D::CLAMP_TO_EDGE); + context->texParameteri(GraphicsContext3D::TEXTURE_2D, GraphicsContext3D::TEXTURE_WRAP_T, GraphicsContext3D::CLAMP_TO_EDGE); + context->bindTexture(GraphicsContext3D::TEXTURE_2D, 0); + + // Create the FBO + m_fbo = context->createFramebuffer(); + ASSERT(m_fbo); + if (!m_fbo) { + clear(); + return; + } + + const GraphicsContext3D::Attributes& attributes = context->getContextAttributes(); + + // Create the stencil and depth buffer if needed + if (!multisample() && (attributes.stencil || attributes.depth)) + m_depthStencilBuffer = context->createRenderbuffer(); + + // create a multisample FBO + if (multisample()) { + m_multisampleFBO = context->createFramebuffer(); + context->bindFramebuffer(GraphicsContext3D::FRAMEBUFFER, m_multisampleFBO); + m_multisampleColorBuffer = context->createRenderbuffer(); + if (attributes.stencil || attributes.depth) + m_multisampleDepthStencilBuffer = context->createRenderbuffer(); + } + + reset(size); +} + +DrawingBuffer::~DrawingBuffer() +{ + clear(); +} + +void DrawingBuffer::didReset() +{ +} + +PlatformLayer* DrawingBuffer::platformLayer() +{ + return m_platformLayer.get(); +} + +Platform3DObject DrawingBuffer::platformColorBuffer() const +{ + return m_colorBuffer; +} + +} + +#endif |