From b087c35c98ba31cd0e27d15a6c61d18664bc981a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Konstantin=20Ka=CC=88fer?= Date: Mon, 17 Feb 2014 12:45:57 +0100 Subject: add tessellation library --- src/renderer/fill_bucket.cpp | 134 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 132 insertions(+), 2 deletions(-) (limited to 'src/renderer/fill_bucket.cpp') diff --git a/src/renderer/fill_bucket.cpp b/src/renderer/fill_bucket.cpp index 6270ef0e5c..630b571ef3 100644 --- a/src/renderer/fill_bucket.cpp +++ b/src/renderer/fill_bucket.cpp @@ -9,6 +9,37 @@ #include + + +void *customHeapAlloc(void *userData, unsigned int size) { + // fprintf(stderr, "malloc %d\n", size); + return malloc(size); +} + +void *customHeapRealloc(void *userData, void *ptr, unsigned int size) { + // fprintf(stderr, "realloc %p %d\n", ptr, size); + return realloc(ptr, size); +} + +void customHeapFree(void *userData, void *ptr) { + // fprintf(stderr, "free %p\n", ptr); + free(ptr); +} + +static TESSalloc defaultAlloc = { + &customHeapAlloc, + &customHeapRealloc, + &customHeapFree, + nullptr, // userData + 512, // meshEdgeBucketSize + 512, // meshVertexBucketSize + 256, // meshFaceBucketSize + 512, // dictNodeBucketSize + 256, // regionBucketSize + 128, // extraVertices allocated for the priority queue. +}; + + #include struct geometry_too_long_exception : std::exception {}; @@ -20,32 +51,131 @@ FillBucket::FillBucket(const std::shared_ptr& vertexBuffer, const std::shared_ptr& lineElementsBuffer, const BucketDescription& bucket_desc) : geom_desc(bucket_desc.geometry), + tesselator(tessNewTess(&defaultAlloc)), vertexBuffer(vertexBuffer), triangleElementsBuffer(triangleElementsBuffer), lineElementsBuffer(lineElementsBuffer), vertex_start(vertexBuffer->index()), triangle_elements_start(triangleElementsBuffer->index()), line_elements_start(lineElementsBuffer->index()) { + assert(tesselator); +} + +FillBucket::~FillBucket() { + if (tesselator) { + tessDeleteTess(tesselator); + } } void FillBucket::addGeometry(pbf& geom) { std::vector line; Geometry::command cmd; + std::vector line2; + Coordinate coord; Geometry geometry(geom); int32_t x, y; while ((cmd = geometry.next(x, y)) != Geometry::end) { if (cmd == Geometry::move_to) { if (line.size()) { - addGeometry(line); + // addGeometry(line); line.clear(); } + if (line2.size()) { + tessAddContour(tesselator, vertexSize, line2.data(), stride, line2.size() / vertexSize); + line2.clear(); + hasVertices = true; + } } line.emplace_back(x, y); + line2.push_back(x); + line2.push_back(y); } if (line.size()) { - addGeometry(line); + // addGeometry(line); + } + if (line2.size()) { + tessAddContour(tesselator, vertexSize, line2.data(), stride, line2.size() / vertexSize); + hasVertices = true; + } +} + +void FillBucket::tessellate() { + if (!hasVertices) { + return; + } + + hasVertices = false; + + // First combine contours and then triangulate, this removes unnecessary inner vertices. + if (tessTesselate(tesselator, TESS_WINDING_POSITIVE, TESS_BOUNDARY_CONTOURS, 0, 0, 0)) { + const TESSreal *vertices = tessGetVertices(tesselator); + const int contour_element_count = tessGetElementCount(tesselator); + const TESSindex *contour_elements_p = tessGetElements(tesselator); + std::vector contour_elements = { contour_elements_p, contour_elements_p + contour_element_count * 2 }; + + for (int i = 0; i < contour_element_count; ++i) { + const TESSindex group_start = contour_elements[i * 2]; + const TESSindex group_count = contour_elements[i * 2 + 1]; + const TESSreal *group_vertices = &vertices[group_start * 2]; + tessAddContour(tesselator, 2, group_vertices, stride, group_count); + } + + if (tessTesselate(tesselator, TESS_WINDING_POSITIVE, TESS_POLYGONS, vertices_per_group, 2, 0)) { + const TESSreal *vertices = tessGetVertices(tesselator); + const TESSindex *vertex_indices = tessGetVertexIndices(tesselator); + const int vertex_count = tessGetVertexCount(tesselator); + const TESSindex *elements = tessGetElements(tesselator); + const int element_count = tessGetElementCount(tesselator); + + + if (vertex_count > 65536) { + throw geometry_too_long_exception(); + } + + // Add vertices and create reverse index mapping for drawing the outline. + std::map contour_vertices; + for (int i = 0; i < vertex_count; ++i) { + contour_vertices[vertex_indices[i]] = i; + vertexBuffer->add(vertices[i * 2], vertices[i * 2 + 1]); + } + + { + if (!triangleGroups.size() || (triangleGroups.back().vertex_length + vertex_count > 65535)) { + // Move to a new group because the old one can't hold the geometry. + triangleGroups.emplace_back(); + } + + // We're generating triangle fans, so we always start with the first + // coordinate in this polygon. + triangle_group_type& group = triangleGroups.back(); + uint32_t index = group.vertex_length; + + + for (int i = 0; i < element_count; ++i) { + const TESSindex *element_group = &elements[i * vertices_per_group]; + + if (element_group[0] == TESS_UNDEF || element_group[1] == TESS_UNDEF || element_group[2] == TESS_UNDEF) { + throw std::runtime_error("element group is not a triangle"); + } + + triangleElementsBuffer->add( + index + element_group[0], + index + element_group[1], + index + element_group[2] + ); + } + + group.vertex_length += vertex_count; + group.elements_length += element_count; + } + + } else { + assert(false && "tesselation failed"); + } + } else { + assert(false && "tesselation failed"); } } -- cgit v1.2.1