5

I need to find a way of drawing the inside of a closed 2D curve. This curve is actually created using a bicubic Bezier curve, but that's not important I believe.

At the moment there should be no "holes" within the drawn shape. So it will just be totally filled in. It seems like constrained Delaunay triangulation would be the way to go? But there seems to be different ways of doing this. I am looking for a quick and simple solution (but will implement what's needed to make it working).

Programs such as Illustrator have that sort of feature (or SVG -- with the option fill).

I am looking for:

  • techniques to do that
  • point me to a paper/document where the algorithm is explained
  • is the source code of a SVG renderer available somewhere?

EDIT:

  • The application uses OpenGL. I draw the curves myself. Just need to find a way of filling them in.
  • the shape can either be concave or convex
user18490
  • 3,546
  • 4
  • 33
  • 52
  • 1
    A good answer would depend on the environment you are drawing in. For example, Windows directly supports drawing filled shapes with a Bezier outline. So does PostScript and PDF. On the other hand, if you are directly manipulating bits, then the question becomes: can your draw the outline? – Logicrat Sep 21 '14 at 22:07
  • 1
    Flatten the bezier curves to straight lines and use ear clipping. – Jongware Sep 21 '14 at 22:10
  • @Logicrat: yes sorry the question is not clear enough. I am using OpenGL. I am drawing the Bezier curve myself, just need to draw the inside now. – user18490 Sep 21 '14 at 22:11
  • 1
    If you approximate the Bezier curve by line segments, you can treat the shape as a polygon. You can render concave polygons directly with OpenGL. See this question/answer: http://stackoverflow.com/questions/25422846/how-to-force-opengl-to-draw-a-non-convex-filled-polygon. – Reto Koradi Sep 21 '14 at 22:19
  • Yes that would actually do it;-) guess it's getting late where I am. I'd be still interested to learn how this is done, as to potentially make it myself. At some point I may have to deal with holes inside the shape. – user18490 Sep 21 '14 at 22:32
  • See http://stackoverflow.com/questions/15519142/resolution-independent-cubic-bezier-drawing-on-gpu-blinn-loop and http://stackoverflow.com/questions/20970673/how-to-solve-rendering-artifact-in-blinn-loops-resolution-independent-curve-ren. – lhf Sep 21 '14 at 22:33
  • @Lhf: I saw this paper indeed. Not the easiest to understand but very interesting approach. The thing is that they use a constrained Delaunay triangulation at some point anyway, and all I find about this method are really old papers/references. I try to find a modern one in which things are explained in plain english;) – user18490 Sep 21 '14 at 22:35
  • See also https://developer.nvidia.com/gpu-accelerated-path-rendering. – lhf Sep 21 '14 at 22:37
  • @lhf: yes thes is also a very good reference indeed. – user18490 Sep 21 '14 at 22:38
  • It is unclear if you are looking for a raster filling algorithm (setting pixels in a bitmap, either one by one or in "runs"), or a decomposition into polygonal primitives (triangles or other). –  Sep 23 '14 at 09:49
  • 1
    http://cs.haifa.ac.il/~gordon/crit.pdf (in case it helps, I also have it implemented as part of a larger OpenGL project). – barak manos Sep 23 '14 at 10:38
  • @Yves Daouat - both solution would work, but I'd prefer the polygon/triangle approach as it can then be rendered directly by OpenGL. – user18490 Sep 24 '14 at 21:40

2 Answers2

9

Polygons can be filled using the Scanline method. The principle is easy: move an horizontal line and keep a list of the edges it meets. It is called the active list. Then join the intersections from left to right, in pairs. When the edges are sorted by increasing ordinate, the update of the active list from one scanline to the next can be done efficiently.

This works with concave/convex polygons and polygons with holes, and even crossed ones.

To fill a Bezier path, you can flatten it, i.e. turn it to a polygon of many sides.

A direct approach is also possible, based on the scanline idea: first decompose the Bezier curves in monotone sections, i.e. portions that meet on horizontal line only once. This can be done analytically for cubic Beziers by detecting the curve maxima and minima (the equation is quadratic).

Now you can treat the curvilinear polygon exactly as a polygon, knowing that you have one intersection per side. There is a slightly delicate point, computing the intersection. But this is eased by the fact that you know a good approximation of the Bezier arc (the line segment between the same endpoints), and you can update the intersection incrementally, from one scanline to the next.

On the picture, the original endpoints appear in blue. Splitting endoints have been added to obtain monotone sections (the other control points are omitted). The dotted lines shows the polygon that approximates the shape and has the same topology (same active list, same number of intersections with the scanlines).

enter image description here

  • Thank you Yves - that's a very good solution. As you suggested in your comment I am interested in all methods. May I ask how you did this figure? Which application did you use? – user18490 Sep 24 '14 at 21:35
  • MS Word, using the Shapes tools. –  Sep 24 '14 at 21:37
  • I did not elaborate on the ways to find the intersections, which involves solving a third degree equation. Of course the Cardano formula can be used, but a numerical approach should be better. Possibly Newton, but also the secant method. Using the latter, in a way you will be flattening the curve "on the fly". –  Sep 24 '14 at 21:40
2

If you must use polygon filling, there is no other option than flattening the curve to get straight sides.

Then use a polygon filling primitive.

If all you have is a triangle filling primitive, you can

  • triangulate the polygon by ear clipping, or decomposition in monotone polygons, or

  • use a simple sweepline method: if you draw an horizontal through every vertex, you will slice the polygon in triangles and trapezoids. A trapezoid can be cut in two triangles. For efficiency, use the active list method.