impeller/tessellator/c/tessellator.cc - mirrors/engine - Git at Google

 // 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.

 #include "tessellator.h"

 #include <memory>
 #include <vector>

 #include "third_party/libtess2/Include/tesselator.h"

 namespace impeller {

 void DestroyTessellator(TESStesselator* tessellator) {
   if (tessellator != nullptr) {
     ::tessDeleteTess(tessellator);
   }
 }

 using CTessellator =
     std::unique_ptr<TESStesselator, decltype(&DestroyTessellator)>;

 static int ToTessWindingRule(FillType fill_type) {
   switch (fill_type) {
     case FillType::kOdd:
       return TESS_WINDING_ODD;
     case FillType::kNonZero:
       return TESS_WINDING_NONZERO;
   }
   return TESS_WINDING_ODD;
 }

 static void* HeapAlloc(void* userData, unsigned int size) {
   return malloc(size);
 }

 static void* HeapRealloc(void* userData, void* ptr, unsigned int size) {
   return realloc(ptr, size);
 }

 static void HeapFree(void* userData, void* ptr) {
   free(ptr);
 }

 // Note: these units are "number of entities" for bucket size and not in KB.
 static const TESSalloc kAlloc = {
     HeapAlloc, HeapRealloc, HeapFree, 0, /* =userData */
     16,                                  /* =meshEdgeBucketSize */
     16,                                  /* =meshVertexBucketSize */
     16,                                  /* =meshFaceBucketSize */
     16,                                  /* =dictNodeBucketSize */
     16,                                  /* =regionBucketSize */
     0                                    /* =extraVertices */
 };

 class LibtessTessellator {
  public:
   LibtessTessellator() : c_tessellator_(nullptr, &DestroyTessellator) {
     TESSalloc alloc = kAlloc;
     {
       // libTess2 copies the TESSalloc despite the non-const argument.
       CTessellator tessellator(::tessNewTess(&alloc), &DestroyTessellator);
       c_tessellator_ = std::move(tessellator);
     }
   }

   ~LibtessTessellator() {}

   enum class Result {
     kSuccess,
     kInputError,
     kTessellationError,
   };

   /// @brief A callback that returns the results of the tessellation.
   ///
   ///        The index buffer may not be populated, in which case [indices] will
   ///        be nullptr and indices_count will be 0.
   using BuilderCallback = std::function<bool(const float* vertices,
                                              size_t vertices_count,
                                              const uint16_t* indices,
                                              size_t indices_count)>;

   //----------------------------------------------------------------------------
   /// @brief      Generates filled triangles from the path. A callback is
   ///             invoked once for the entire tessellation.
   ///
   /// @param[in]  path  The path to tessellate.
   /// @param[in]  tolerance  The tolerance value for conversion of the path to
   ///                        a polyline. This value is often derived from the
   ///                        Matrix::GetMaxBasisLength of the CTM applied to the
   ///                        path for rendering.
   /// @param[in]  callback  The callback, return false to indicate failure.
   ///
   /// @return The result status of the tessellation.
   ///
   Result Tessellate(const Path& path,
                     Scalar tolerance,
                     const BuilderCallback& callback) {
     if (!callback) {
       return Result::kInputError;
     }

     std::unique_ptr<std::vector<Point>> buffer =
         std::make_unique<std::vector<Point>>();
     auto polyline = path.CreatePolyline(tolerance, std::move(buffer));

     auto fill_type = path.GetFillType();

     if (polyline.points->empty()) {
       return Result::kInputError;
     }

     auto tessellator = c_tessellator_.get();
     if (!tessellator) {
       return Result::kTessellationError;
     }

     constexpr int kVertexSize = 2;
     constexpr int kPolygonSize = 3;

     //----------------------------------------------------------------------------
     /// Feed contour information to the tessellator.
     ///
     static_assert(sizeof(Point) == 2 * sizeof(float));
     for (size_t contour_i = 0; contour_i < polyline.contours.size();
          contour_i++) {
       size_t start_point_index, end_point_index;
       std::tie(start_point_index, end_point_index) =
           polyline.GetContourPointBounds(contour_i);

       ::tessAddContour(tessellator,  // the C tessellator
                        kVertexSize,  //
                        polyline.points->data() + start_point_index,  //
                        sizeof(Point),                                //
                        end_point_index - start_point_index           //
       );
     }

     //----------------------------------------------------------------------------
     /// Let's tessellate.
     ///
     auto result = ::tessTesselate(tessellator,                   // tessellator
                                   ToTessWindingRule(fill_type),  // winding
                                   TESS_POLYGONS,                 // element type
                                   kPolygonSize,                  // polygon size
                                   kVertexSize,                   // vertex size
                                   nullptr  // normal (null is automatic)
     );

     if (result != 1) {
       return Result::kTessellationError;
     }

     int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;

     // We default to using a 16bit index buffer, but in cases where we generate
     // more tessellated data than this can contain we need to fall back to
     // dropping the index buffer entirely. Instead code could instead switch to
     // a uint32 index buffer, but this is done for simplicity with the other
     // fast path above.
     if (element_item_count < USHRT_MAX) {
       int vertex_item_count = tessGetVertexCount(tessellator);
       auto vertices = tessGetVertices(tessellator);
       auto elements = tessGetElements(tessellator);

       // libtess uses an int index internally due to usage of -1 as a sentinel
       // value.
       std::vector<uint16_t> indices(element_item_count);
       for (int i = 0; i < element_item_count; i++) {
         indices[i] = static_cast<uint16_t>(elements[i]);
       }
       if (!callback(vertices, vertex_item_count, indices.data(),
                     element_item_count)) {
         return Result::kInputError;
       }
     } else {
       std::vector<Point> points;
       std::vector<float> data;

       int vertex_item_count = tessGetVertexCount(tessellator) * kVertexSize;
       auto vertices = tessGetVertices(tessellator);
       points.reserve(vertex_item_count);
       for (int i = 0; i < vertex_item_count; i += 2) {
         points.emplace_back(vertices[i], vertices[i + 1]);
       }

       int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;
       auto elements = tessGetElements(tessellator);
       data.reserve(element_item_count);
       for (int i = 0; i < element_item_count; i++) {
         data.emplace_back(points[elements[i]].x);
         data.emplace_back(points[elements[i]].y);
       }
       if (!callback(data.data(), element_item_count, nullptr, 0u)) {
         return Result::kInputError;
       }
     }

     return Result::kSuccess;
   }

   CTessellator c_tessellator_;
 };

 PathBuilder* CreatePathBuilder() {
   return new PathBuilder();
 }

 void DestroyPathBuilder(PathBuilder* builder) {
   delete builder;
 }

 void MoveTo(PathBuilder* builder, Scalar x, Scalar y) {
   builder->MoveTo(Point(x, y));
 }

 void LineTo(PathBuilder* builder, Scalar x, Scalar y) {
   builder->LineTo(Point(x, y));
 }

 void CubicTo(PathBuilder* builder,
              Scalar x1,
              Scalar y1,
              Scalar x2,
              Scalar y2,
              Scalar x3,
              Scalar y3) {
   builder->CubicCurveTo(Point(x1, y1), Point(x2, y2), Point(x3, y3));
 }

 void Close(PathBuilder* builder) {
   builder->Close();
 }

 struct Vertices* Tessellate(PathBuilder* builder,
                             int fill_type,
                             Scalar tolerance) {
   auto path = builder->CopyPath(static_cast<FillType>(fill_type));
   std::vector<float> points;
   if (LibtessTessellator{}.Tessellate(
           path, tolerance,
           [&points](const float* vertices, size_t vertices_count,
                     const uint16_t* indices, size_t indices_count) {
             // Results are expected to be re-duplicated.
             std::vector<Point> raw_points;
             for (auto i = 0u; i < vertices_count * 2; i += 2) {
               raw_points.emplace_back(Point{vertices[i], vertices[i + 1]});
             }
             for (auto i = 0u; i < indices_count; i++) {
               auto point = raw_points[indices[i]];
               points.push_back(point.x);
               points.push_back(point.y);
             }
             return true;
           }) != LibtessTessellator::Result::kSuccess) {
     return nullptr;
   }

   Vertices* vertices = new Vertices();
   vertices->points = new float[points.size()];
   if (!vertices->points) {
     return nullptr;
   }
   vertices->length = points.size();
   std::copy(points.begin(), points.end(), vertices->points);
   return vertices;
 }

 void DestroyVertices(Vertices* vertices) {
   delete vertices->points;
   delete vertices;
 }

 }  // namespace impeller
	// 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.

	#include "tessellator.h"

	#include <memory>
	#include <vector>

	#include "third_party/libtess2/Include/tesselator.h"

	namespace impeller {

	void DestroyTessellator(TESStesselator* tessellator) {
	if (tessellator != nullptr) {
	::tessDeleteTess(tessellator);
	}
	}

	using CTessellator =
	std::unique_ptr<TESStesselator, decltype(&DestroyTessellator)>;

	static int ToTessWindingRule(FillType fill_type) {
	switch (fill_type) {
	case FillType::kOdd:
	return TESS_WINDING_ODD;
	case FillType::kNonZero:
	return TESS_WINDING_NONZERO;
	}
	return TESS_WINDING_ODD;
	}

	static void* HeapAlloc(void* userData, unsigned int size) {
	return malloc(size);
	}

	static void* HeapRealloc(void* userData, void* ptr, unsigned int size) {
	return realloc(ptr, size);
	}

	static void HeapFree(void* userData, void* ptr) {
	free(ptr);
	}

	// Note: these units are "number of entities" for bucket size and not in KB.
	static const TESSalloc kAlloc = {
	HeapAlloc, HeapRealloc, HeapFree, 0, /* =userData */
	16, /* =meshEdgeBucketSize */
	16, /* =meshVertexBucketSize */
	16, /* =meshFaceBucketSize */
	16, /* =dictNodeBucketSize */
	16, /* =regionBucketSize */
	0 /* =extraVertices */
	};

	class LibtessTessellator {
	public:
	LibtessTessellator() : c_tessellator_(nullptr, &DestroyTessellator) {
	TESSalloc alloc = kAlloc;
	{
	// libTess2 copies the TESSalloc despite the non-const argument.
	CTessellator tessellator(::tessNewTess(&alloc), &DestroyTessellator);
	c_tessellator_ = std::move(tessellator);
	}
	}

	~LibtessTessellator() {}

	enum class Result {
	kSuccess,
	kInputError,
	kTessellationError,
	};

	/// @brief A callback that returns the results of the tessellation.
	///
	/// The index buffer may not be populated, in which case [indices] will
	/// be nullptr and indices_count will be 0.
	using BuilderCallback = std::function<bool(const float* vertices,
	size_t vertices_count,
	const uint16_t* indices,
	size_t indices_count)>;

	//----------------------------------------------------------------------------
	/// @brief Generates filled triangles from the path. A callback is
	/// invoked once for the entire tessellation.
	///
	/// @param[in] path The path to tessellate.
	/// @param[in] tolerance The tolerance value for conversion of the path to
	/// a polyline. This value is often derived from the
	/// Matrix::GetMaxBasisLength of the CTM applied to the
	/// path for rendering.
	/// @param[in] callback The callback, return false to indicate failure.
	///
	/// @return The result status of the tessellation.
	///
	Result Tessellate(const Path& path,
	Scalar tolerance,
	const BuilderCallback& callback) {
	if (!callback) {
	return Result::kInputError;
	}

	std::unique_ptr<std::vector<Point>> buffer =
	std::make_unique<std::vector<Point>>();
	auto polyline = path.CreatePolyline(tolerance, std::move(buffer));

	auto fill_type = path.GetFillType();

	if (polyline.points->empty()) {
	return Result::kInputError;
	}

	auto tessellator = c_tessellator_.get();
	if (!tessellator) {
	return Result::kTessellationError;
	}

	constexpr int kVertexSize = 2;
	constexpr int kPolygonSize = 3;

	//----------------------------------------------------------------------------
	/// Feed contour information to the tessellator.
	///
	static_assert(sizeof(Point) == 2 * sizeof(float));
	for (size_t contour_i = 0; contour_i < polyline.contours.size();
	contour_i++) {
	size_t start_point_index, end_point_index;
	std::tie(start_point_index, end_point_index) =
	polyline.GetContourPointBounds(contour_i);

	::tessAddContour(tessellator, // the C tessellator
	kVertexSize, //
	polyline.points->data() + start_point_index, //
	sizeof(Point), //
	end_point_index - start_point_index //
	);
	}

	//----------------------------------------------------------------------------
	/// Let's tessellate.
	///
	auto result = ::tessTesselate(tessellator, // tessellator
	ToTessWindingRule(fill_type), // winding
	TESS_POLYGONS, // element type
	kPolygonSize, // polygon size
	kVertexSize, // vertex size
	nullptr // normal (null is automatic)
	);

	if (result != 1) {
	return Result::kTessellationError;
	}

	int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;

	// We default to using a 16bit index buffer, but in cases where we generate
	// more tessellated data than this can contain we need to fall back to
	// dropping the index buffer entirely. Instead code could instead switch to
	// a uint32 index buffer, but this is done for simplicity with the other
	// fast path above.
	if (element_item_count < USHRT_MAX) {
	int vertex_item_count = tessGetVertexCount(tessellator);
	auto vertices = tessGetVertices(tessellator);
	auto elements = tessGetElements(tessellator);

	// libtess uses an int index internally due to usage of -1 as a sentinel
	// value.
	std::vector<uint16_t> indices(element_item_count);
	for (int i = 0; i < element_item_count; i++) {
	indices[i] = static_cast<uint16_t>(elements[i]);
	}
	if (!callback(vertices, vertex_item_count, indices.data(),
	element_item_count)) {
	return Result::kInputError;
	}
	} else {
	std::vector<Point> points;
	std::vector<float> data;

	int vertex_item_count = tessGetVertexCount(tessellator) * kVertexSize;
	auto vertices = tessGetVertices(tessellator);
	points.reserve(vertex_item_count);
	for (int i = 0; i < vertex_item_count; i += 2) {
	points.emplace_back(vertices[i], vertices[i + 1]);
	}

	int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;
	auto elements = tessGetElements(tessellator);
	data.reserve(element_item_count);
	for (int i = 0; i < element_item_count; i++) {
	data.emplace_back(points[elements[i]].x);
	data.emplace_back(points[elements[i]].y);
	}
	if (!callback(data.data(), element_item_count, nullptr, 0u)) {
	return Result::kInputError;
	}
	}

	return Result::kSuccess;
	}

	CTessellator c_tessellator_;
	};

	PathBuilder* CreatePathBuilder() {
	return new PathBuilder();
	}

	void DestroyPathBuilder(PathBuilder* builder) {
	delete builder;
	}

	void MoveTo(PathBuilder* builder, Scalar x, Scalar y) {
	builder->MoveTo(Point(x, y));
	}

	void LineTo(PathBuilder* builder, Scalar x, Scalar y) {
	builder->LineTo(Point(x, y));
	}

	void CubicTo(PathBuilder* builder,
	Scalar x1,
	Scalar y1,
	Scalar x2,
	Scalar y2,
	Scalar x3,
	Scalar y3) {
	builder->CubicCurveTo(Point(x1, y1), Point(x2, y2), Point(x3, y3));
	}

	void Close(PathBuilder* builder) {
	builder->Close();
	}

	struct Vertices* Tessellate(PathBuilder* builder,
	int fill_type,
	Scalar tolerance) {
	auto path = builder->CopyPath(static_cast<FillType>(fill_type));
	std::vector<float> points;
	if (LibtessTessellator{}.Tessellate(
	path, tolerance,
	[&points](const float* vertices, size_t vertices_count,
	const uint16_t* indices, size_t indices_count) {
	// Results are expected to be re-duplicated.
	std::vector<Point> raw_points;
	for (auto i = 0u; i < vertices_count * 2; i += 2) {
	raw_points.emplace_back(Point{vertices[i], vertices[i + 1]});
	}
	for (auto i = 0u; i < indices_count; i++) {
	auto point = raw_points[indices[i]];
	points.push_back(point.x);
	points.push_back(point.y);
	}
	return true;
	}) != LibtessTessellator::Result::kSuccess) {
	return nullptr;
	}

	Vertices* vertices = new Vertices();
	vertices->points = new float[points.size()];
	if (!vertices->points) {
	return nullptr;
	}
	vertices->length = points.size();
	std::copy(points.begin(), points.end(), vertices->points);
	return vertices;
	}

	void DestroyVertices(Vertices* vertices) {
	delete vertices->points;
	delete vertices;
	}

	} // namespace impeller