// Copyright 2013 The Flutter Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef FLUTTER_IMPELLER_TESSELLATOR_TESSELLATOR_H_ #define FLUTTER_IMPELLER_TESSELLATOR_TESSELLATOR_H_ #include #include #include #include "impeller/core/formats.h" #include "impeller/core/host_buffer.h" #include "impeller/core/vertex_buffer.h" #include "impeller/geometry/arc.h" #include "impeller/geometry/path_source.h" #include "impeller/geometry/point.h" #include "impeller/geometry/stroke_parameters.h" #include "impeller/geometry/trig.h" namespace impeller { /// The size of the point arena buffer stored on the tessellator. [[maybe_unused]] static constexpr size_t kPointArenaSize = 4096u; //------------------------------------------------------------------------------ /// @brief A utility that generates triangles of the specified fill type /// given a polyline. This happens on the CPU. /// /// Also contains functionality for optimized generation of circles /// and ellipses. /// /// This object is not thread safe, and its methods must not be /// called from multiple threads. /// class Tessellator { public: /// Essentially just a vector of Trig objects, but supports storing a /// reference to either a cached vector or a locally generated vector. /// The constructor will fill the vector with quarter circular samples /// for the indicated number of equal divisions if the vector is new. /// /// A given instance of Trigs will always contain at least 2 entries /// which is the minimum number of samples to traverse a quarter circle /// in a single step. The first sample will always be (0, 1) and the last /// sample will always be (1, 0). class Trigs { public: explicit Trigs(Scalar pixel_radius); // Utility forwards of the indicated vector methods. size_t inline size() const { return trigs_.size(); } std::vector::iterator inline begin() const { return trigs_.begin(); } std::vector::iterator inline end() const { return trigs_.end(); } const inline Trig& operator[](size_t index) const { return trigs_[index]; } size_t inline GetSteps() const { return trigs_.size() - 1u; } private: friend class Tessellator; explicit Trigs(std::vector& trigs, size_t divisions) : trigs_(trigs) { FML_DCHECK(divisions >= 1); init(divisions); FML_DCHECK(trigs_.size() == divisions + 1); } explicit Trigs(size_t divisions) : local_storage_(std::make_unique>()), trigs_(*local_storage_) { FML_DCHECK(divisions >= 1); init(divisions); FML_DCHECK(trigs_.size() == divisions + 1); } // nullptr if a cached vector is used, otherwise the actual storage std::unique_ptr> local_storage_; // Whether or not a cached vector or the local storage is used, this // this reference will always be valid std::vector& trigs_; // Fill the vector with the indicated number of equal divisions of // trigonometric values if it is empty. void init(size_t divisions); }; enum class Result { kSuccess, kInputError, kTessellationError, }; /// @brief A callback function for a |VertexGenerator| to deliver /// the vertices it computes as |Point| objects. using TessellatedVertexProc = std::function; /// @brief An object which produces a list of vertices as |Point|s that /// tessellate a previously provided shape and delivers the vertices /// through a |TessellatedVertexProc| callback. /// /// The object can also provide advance information on how many /// vertices it will generate. /// /// @see |Tessellator::FilledCircle| /// @see |Tessellator::StrokedCircle| /// @see |Tessellator::RoundCapLine| /// @see |Tessellator::FilledEllipse| class VertexGenerator { public: /// @brief Returns the |PrimitiveType| that describes the relationship /// among the list of vertices produced by the |GenerateVertices| /// method. /// /// Most generators will deliver |kTriangleStrip| triangles virtual PrimitiveType GetTriangleType() const = 0; /// @brief Returns the number of vertices that the generator plans to /// produce, if known. /// /// This value is advisory only and can be used to reserve space /// where the vertices will be placed, but the count may be an /// estimate. /// /// Implementations are encouraged to avoid overestimating /// the count by too large a number and to provide a best /// guess so as to minimize potential buffer reallocations /// as the vertices are delivered. virtual size_t GetVertexCount() const = 0; /// @brief Generate the vertices and deliver them in the necessary /// order (as required by the PrimitiveType) to the given /// callback function. virtual void GenerateVertices(const TessellatedVertexProc& proc) const = 0; }; /// @brief The |VertexGenerator| implementation common to all shapes /// that are based on a polygonal representation of an ellipse. class EllipticalVertexGenerator : public virtual VertexGenerator { public: /// |VertexGenerator| PrimitiveType GetTriangleType() const override { return PrimitiveType::kTriangleStrip; } /// |VertexGenerator| size_t GetVertexCount() const override { return trigs_.size() * vertices_per_trig_; } /// |VertexGenerator| void GenerateVertices(const TessellatedVertexProc& proc) const override { impl_(trigs_, data_, proc); } private: friend class Tessellator; struct Data { // Circles and Ellipses only use one of these points. // RoundCapLines use both as the endpoints of the unexpanded line. // A round rect can specify its interior rectangle by using the // 2 points as opposing corners. const Point reference_centers[2]; // Circular shapes have the same value in radii.width and radii.height const Size radii; // half_width is only used in cases where the generator will be // generating 2 different outlines, such as StrokedCircle const Scalar half_width; }; typedef void GeneratorProc(const Trigs& trigs, const Data& data, const TessellatedVertexProc& proc); GeneratorProc& impl_; const Trigs trigs_; const Data data_; const size_t vertices_per_trig_; EllipticalVertexGenerator(GeneratorProc& generator, Trigs&& trigs, PrimitiveType triangle_type, size_t vertices_per_trig, Data&& data); }; /// @brief The |VertexGenerator| implementation common to all shapes /// that are based on a polygonal representation of an ellipse. class ArcVertexGenerator : public virtual VertexGenerator { public: /// |VertexGenerator| PrimitiveType GetTriangleType() const override; /// |VertexGenerator| size_t GetVertexCount() const override; /// |VertexGenerator| void GenerateVertices(const TessellatedVertexProc& proc) const override; static ArcVertexGenerator MakeFilled(const Arc::Iteration& iteration, Trigs&& trigs, const Rect& oval_bounds, bool use_center, bool supports_triangle_fans); static ArcVertexGenerator MakeStroked( const Arc::Iteration& iteration, Trigs&& trigs, const Rect& oval_bounds, Scalar half_width, Cap cap, std::unique_ptr round_cap_trigs); private: friend class Tessellator; const Arc::Iteration iteration_; const Trigs trigs_; const Rect oval_bounds_; // Used only in filled arcs. const bool use_center_; const bool supports_triangle_fans_; // Used only in stroked arcs. half_width_ is set to -1.0f for filled arcs. const Scalar half_width_; const Cap cap_; const std::unique_ptr round_cap_trigs_; ArcVertexGenerator(const Arc::Iteration& iteration, Trigs&& trigs, const Rect& oval_bounds, bool use_center, bool supports_triangle_fans, Scalar half_width, Cap cap, std::unique_ptr round_cap_trigs); }; explicit Tessellator(bool supports_32bit_primitive_indices = true); virtual ~Tessellator(); //---------------------------------------------------------------------------- /// @brief Given a convex path, create a triangle fan structure. /// /// @param[in] path The path to tessellate. /// @param[in] host_buffer The host buffer for allocation of vertices/index /// data. /// @param[in] tolerance The tolerance value for conversion of the path to /// a polyline. This value is often derived from the /// Matrix::GetMaxBasisLengthXY of the CTM applied to /// the path for rendering. /// /// @return A vertex buffer containing all data from the provided curve. VertexBuffer TessellateConvex(const PathSource& path, HostBuffer& data_host_buffer, HostBuffer& indexes_host_buffer, Scalar tolerance, bool supports_primitive_restart = false, bool supports_triangle_fan = false); /// Visible for testing. /// /// This method only exists for the ease of benchmarking without using the /// real allocator needed by the [host_buffer]. static void TessellateConvexInternal(const PathSource& path, std::vector& point_buffer, std::vector& index_buffer, Scalar tolerance); //---------------------------------------------------------------------------- /// @brief The pixel tolerance used by the algorighm to determine how /// many divisions to create for a circle. /// /// No point on the polygon of vertices should deviate from the /// true circle by more than this tolerance. static constexpr Scalar kCircleTolerance = 0.1f; /// @brief Create a |VertexGenerator| that can produce vertices for /// a filled circle of the given radius around the given center /// with enough polygon sub-divisions to provide reasonable /// fidelity when viewed under the given view transform. /// /// Note that the view transform is only used to choose the /// number of sample points to use per quarter circle and the /// returned points are not transformed by it, instead they are /// relative to the coordinate space of the center point. EllipticalVertexGenerator FilledCircle(const Matrix& view_transform, const Point& center, Scalar radius); /// @brief Create a |VertexGenerator| that can produce vertices for /// a stroked circle of the given radius and half_width around /// the given shared center with enough polygon sub-divisions /// to provide reasonable fidelity when viewed under the given /// view transform. The outer edge of the stroked circle is /// generated at (radius + half_width) and the inner edge is /// generated at (radius - half_width). /// /// Note that the view transform is only used to choose the /// number of sample points to use per quarter circle and the /// returned points are not transformed by it, instead they are /// relative to the coordinate space of the center point. EllipticalVertexGenerator StrokedCircle(const Matrix& view_transform, const Point& center, Scalar radius, Scalar half_width); /// @brief Create a |VertexGenerator| that can produce vertices for /// a stroked arc inscribed within the given oval_bounds with /// the given stroke half_width with enough polygon sub-divisions /// to provide reasonable fidelity when viewed under the given /// view transform. The outer edge of the stroked arc is /// generated at (radius + half_width) and the inner edge is /// generated at (radius - half_width). /// /// Note that the view transform is only used to choose the /// number of sample points to use per quarter circle and the /// returned points are not transformed by it, instead they are /// relative to the coordinate space of the oval bounds. ArcVertexGenerator FilledArc(const Matrix& view_transform, const Arc& arc, bool supports_triangle_fans); /// @brief Create a |VertexGenerator| that can produce vertices for /// a stroked arc inscribed within the given oval_bounds with /// the given stroke half_width with enough polygon sub-divisions /// to provide reasonable fidelity when viewed under the given /// view transform. The outer edge of the stroked arc is /// generated at (radius + half_width) and the inner edge is /// generated at (radius - half_width). /// /// Note that the arc may not include the center and its bounds /// must be a perfect circle (width == height) /// /// Note that the view transform is only used to choose the /// number of sample points to use per quarter circle and the /// returned points are not transformed by it, instead they are /// relative to the coordinate space of the oval bounds. ArcVertexGenerator StrokedArc(const Matrix& view_transform, const Arc& arc, Cap cap, Scalar half_width); /// @brief Create a |VertexGenerator| that can produce vertices for /// a line with round end caps of the given radius with enough /// polygon sub-divisions to provide reasonable fidelity when /// viewed under the given view transform. /// /// Note that the view transform is only used to choose the /// number of sample points to use per quarter circle and the /// returned points are not transformed by it, instead they are /// relative to the coordinate space of the two points. EllipticalVertexGenerator RoundCapLine(const Matrix& view_transform, const Point& p0, const Point& p1, Scalar radius); /// @brief Create a |VertexGenerator| that can produce vertices for /// a filled ellipse inscribed within the given bounds with /// enough polygon sub-divisions to provide reasonable /// fidelity when viewed under the given view transform. /// /// Note that the view transform is only used to choose the /// number of sample points to use per quarter circle and the /// returned points are not transformed by it, instead they are /// relative to the coordinate space of the bounds. EllipticalVertexGenerator FilledEllipse(const Matrix& view_transform, const Rect& bounds); /// @brief Create a |VertexGenerator| that can produce vertices for /// a filled round rect within the given bounds and corner radii /// with enough polygon sub-divisions to provide reasonable /// fidelity when viewed under the given view transform. /// /// Note that the view transform is only used to choose the /// number of sample points to use per quarter circle and the /// returned points are not transformed by it, instead they are /// relative to the coordinate space of the bounds. EllipticalVertexGenerator FilledRoundRect(const Matrix& view_transform, const Rect& bounds, const Size& radii); /// Retrieve a pre-allocated arena of kPointArenaSize points. std::vector& GetStrokePointCache(); /// Return a vector of Trig (cos, sin pairs) structs for a 90 degree /// circle quadrant of the specified pixel radius Trigs GetTrigsForDeviceRadius(Scalar pixel_radius); private: class ConvexTessellator { public: virtual ~ConvexTessellator() = default; virtual VertexBuffer TessellateConvex(const PathSource& path, HostBuffer& data_host_buffer, HostBuffer& indexes_host_buffer, Scalar tolerance, bool supports_primitive_restart, bool supports_triangle_fan) = 0; }; template friend class ConvexTessellatorImpl; /// Used for polyline generation. std::unique_ptr convex_tessellator_; /// Used for stroke path generation. std::vector stroke_points_; // Data for various Circle/EllipseGenerator classes, cached per // Tessellator instance which is usually the foreground life of an app // if not longer. static constexpr size_t kCachedTrigCount = 300; std::vector precomputed_trigs_[kCachedTrigCount]; Trigs GetTrigsForDivisions(size_t divisions); static void GenerateFilledCircle(const Trigs& trigs, const EllipticalVertexGenerator::Data& data, const TessellatedVertexProc& proc); static void GenerateStrokedCircle(const Trigs& trigs, const EllipticalVertexGenerator::Data& data, const TessellatedVertexProc& proc); static void GenerateFilledArcFan(const Trigs& trigs, const Arc::Iteration& iteration, const Rect& oval_bounds, bool use_center, const TessellatedVertexProc& proc); static void GenerateFilledArcStrip(const Trigs& trigs, const Arc::Iteration& iteration, const Rect& oval_bounds, bool use_center, const TessellatedVertexProc& proc); static void GenerateStrokedArc(const Trigs& trigs, const Arc::Iteration& iteration, const Rect& oval_bounds, Scalar half_width, Cap cap, const std::unique_ptr& round_cap_trigs, const TessellatedVertexProc& proc); static void GenerateRoundCapLine(const Trigs& trigs, const EllipticalVertexGenerator::Data& data, const TessellatedVertexProc& proc); static void GenerateFilledEllipse(const Trigs& trigs, const EllipticalVertexGenerator::Data& data, const TessellatedVertexProc& proc); static void GenerateFilledRoundRect( const Trigs& trigs, const EllipticalVertexGenerator::Data& data, const TessellatedVertexProc& proc); // Generates vertices for the start round cap of a stroke. // // The perpendicular input points 90 degrees clockwise to the direction the // stroke is traveling and is the length of half of the stroke width. // // The start round cap covers a semicircle formed by sweeping the // perpendicular input clockwise 180 degrees about point p. This sweeps a // semicircle with a curve facing away from the stroke's direction of travel. // // The first generated vertex is the midpoint of the semicircle's curve, // directly opposite the semicircle's straight diameter. Vertices progress // in the stroke's direction of travel, ending with two vertices at // (p + perpendicular) and (p - perpendicular) that form the semicircle's // diameter. static void GenerateStartRoundCap(const Point& p, const Vector2& perpendicular, const Trigs& trigs, const TessellatedVertexProc& proc); // Generates vertices for the end round cap of a stroke. // // The perpendicular input points 90 degrees clockwise to the direction the // stroke is traveling and is the length of half of the stroke width. // // The end round cap covers a semicircle formed by sweeping the // perpendicular input counterclockwise 180 degrees about point p. This sweeps // a semicircle with a curve facing toward the stroke's direction of travel. // // The generated vertices begin with two vertices at (p + perpendicular) and // (p - perpendicular) which form the semicircle's diameter. Vertices progress // in the stroke's direction of travel, ending with the vertex at the midpoint // of the semicircle's curve. static void GenerateEndRoundCap(const Point& p, const Vector2& perpendicular, const Trigs& trigs, const TessellatedVertexProc& proc); Tessellator(const Tessellator&) = delete; Tessellator& operator=(const Tessellator&) = delete; }; } // namespace impeller #endif // FLUTTER_IMPELLER_TESSELLATOR_TESSELLATOR_H_