Bug 1501: Apply intersection tests for non-convex shapes to reject new CCW and non-circulcircle triangulation candidates in our Delaunay tessellator

<https://jogamp.org/bugzilla//show_bug.cgi?id=1501#c6>

The used Delaunay tessellation works well with (almost) convex shapes.
In case e.g. a glyph gets to the extremes like 'M' in FreeMono
or any other complex Chinese symbol - it may just simply happen
that the new non-circumcircle triangle point crosses the inner (hope)
or outer boundaries of the given polygon.

Applying further constraint at Loop.cut() resolves most cases
by rejecting the proposed CCW and non-circumcircle triangle candidate
if its new two line-segments intersects with the original polygon.

This results in mostly proper rendered Chinese fonts and also
FreeMono is now readable - overal remaining bugs in Glyphs is low.

+++

Of course, this intersection test is costly around >= O(log(n)*n) costs,
practically adding a measured ~65% processing time.
E.g. for FontView01 using FreeSerif.ttf
- orig total took 1430.817638ms, per-glyph 0.2236ms, glyphs 6399
- fix  total took 2377.337359ms, per-glyph 0.371517ms, glyphs 6399

Pure Glyph/Shape instantiation shows > 2x costs:
 750 ms 100% convex (fake)
1875 ms   0% convex (fake)
1870 ms  13% convex 824/6399

+++

Hence it is desired to either
(1) Manually mark a polygon non-convex to add described intersection test for accuracy.
    Also may be used to just drop the additional costs despite the lack of correctness.

PROVIDED

(2) Determine non-convex nature of a polygon with a and overall less expensive algorithm.
    If considerably cheaper, this could reduce O(log(n) * n) -> O(n) or even O(log n).

Added convex/non-convex classification while ignoring off-curve points,
but only ~13% of FreeSerif is pure convex,
hence there is no benefit with this classification type.

It might be desired to attempt other classes, i.e.
being rendered in non-convex mode w/o intersection tests.
See
- GENERALIZED DELAUNAY TRIANGULATIONS OF NON-CONVEX DOMAINS
  https://deepblue.lib.umich.edu/bitstream/handle/2027.42/28782/0000614.pdf;sequence=1

- https://en.wikipedia.org/wiki/List_of_self-intersecting_polygons
- https://en.wikipedia.org/wiki/Complex_polygon

0 files changed, 0 insertions, 0 deletions