Filling a 2D curved concave shape in libgdx

Question

What are the approaches to color-filling a curved concave shape in libgdx?

Let us assume that:

1) The shape-to-be-rendered is built from an array of vertices that are close to each other.

2) Edges between the vertices are known.

3) The vertices' positions might dynamically change over time. We are guaranteed that no self-intersections will occur (and that the shape will not be hollow).

The right-most picture is what I'm trying to render in libgdx (with-or-without the outline).

From what I've read, triangulation is a popular approach to non-curved shapes, but in order for it look any good for shapes with curvature, I imagine we would need a huge number of vertices (so that the many lines "zoomed out" resemble a smooth curve).

Then triangulation will work just fine. If the result is too coarse, you can apply subdivision schemes to make the result smoother. — Nico Schertler, Mar 05 '18 at 17:04
@P.Lance: why do you show isolated dots if the edges are known ? This is misleading. — Yves Daoust, Mar 05 '18 at 17:08
@P.Lance: if you want a smoother curve than the given polyline, try cubic spline interpolation with "closed curve" limit conditions. — Yves Daoust, Mar 05 '18 at 17:10
@YvesDaoust Specified the edges in assumptions. About the closed curve interpolation - isn't that applicable for the outline only? I don't think this will help in filling the inner space. — P. Lance, Mar 05 '18 at 17:20
@P.Lance: flatten the curve and fill the resulting polygon. direct filling of a cubic spline is also possible but you'll have to roll your sleaves. — Yves Daoust, Mar 05 '18 at 17:53

Spektre · Answer 1 · 2018-03-06T08:57:35.117

Triangulatin is not the only one way to go with this. I am not familiar with your gfx lib but I would do this in low level:

Subdivide your polyline to set of convex ones

you need to know which segment is line and which is curve and for the curve you also need to know the control points from neighboring patch so the connection is smooth. The concave boundary can be detected by the fact that angle change swaps sign so if you got consequent points p(0)...p(n) with consistent widing rule then
```
d(i  ) = p(i+1)-p(i  )
d(i-1) = p(i  )-p(i-1)
n(i) = cross( d(i) , d(i-1) )
n(i).z * n(i-1).z < 0.0
```
so the cross product will give you normal and if the direction of the normal swaps it mean the winding is changed... The equatio assumes points are in xy plane or parallel to it. If not the case the last line should be
```
dot( n(i) , n(i-1) ) < 0.0
```
if true p(i) is your concave boundary and you should split your shape by it
fill the polylines

you can use the same approach as for triangles or convex polygons see:
- how to rasterize rotated rectangle
- Algorithm to fill triangle
render polyline outline

Of coarse if you do not have fast pixel access or horizontal line rendering available is this not a good way to go. There is one simple but not as fast option:

render outline
flood fill inside

this step is slow which might cause problems for bigger resolutions.

Filling a 2D curved concave shape in libgdx

1 Answers1