0

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

enter image description here

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

P. Lance
  • 179
  • 2
  • 13
  • Do you only have the vertices or also their connectivity? – Nico Schertler Mar 05 '18 at 16:56
  • @NicoSchertler Edges are known too. – P. Lance Mar 05 '18 at 17:01
  • 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. –  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. –  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. –  Mar 05 '18 at 17:53

1 Answers1

1

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:

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

  2. fill the polylines

    you can use the same approach as for triangles or convex polygons see:

  3. 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:

  1. render outline

  2. flood fill inside

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

Spektre
  • 49,595
  • 11
  • 110
  • 380