Bug 1501

commit 18fc81fab7ba11ae3a4cdd1e94c199371f7c2e91
Date:   Mon Feb 6 02:31:14 2023 +0100

    Graph: Path2D -> self-contained Path2D (w/ Iterator) fixed; OutlineShape: Add Path2F addPath(..), emphasize required Winding.CW
    
    GPURegionGLListener01 used by TestRegionRendererNEWT01 covers Path2F CCW and CW (reverse add) methods.

+++

commit e72dbd286ba95913711ac812bc979204f2073b7c
Date:   Fri Feb 17 12:17:57 2023 +0100

    Graph: Fix Loop.initFromPolyline()'s Winding determination, document Winding rules for OutlineShape and add get/setWinding in Outline
    
    Loop.initFromPolyline()'s Winding determination used a 3-point triangle-area method,
    which is insufficent for complex shapes like serif 'g' or 'æ'.
    Solved by using the whole area over the Outline shape.
    
    Note: Loop.initFromPolyline()'s Winding determination is used to convert
    the inner shape or holes to CW only.
    Therefor the outter bondary shapes must be CCW.
    
    This details has been documented within OutlineShape, anchor 'windingrules'.
    Since the conversion of 'CCW -> CW' for inner shapes or holes is covered,
    a safe user path would be to completely create CCW shapes.
    However, this has not been hardcoded and is left to the user.
    
    Impact: Fixes rendering serif 'g' or 'æ'.
    
    The enhanced unit test TestTextRendererNEWT01 produces snapshots for all fonts within FontSet01.
    While it shows proper rendering of the single Glyphs it exposes another Region/Curve Renderer bug,
    i.e. sort-of a Region overflow crossing over from the box-end to the start.

+++

(In reply to Sven Gothel from comment #1)
These were the 1st commits addressing the issue, i.e. resolving winding determination.
After further analysis, mixed winding seems to be still an issues.

+++

Further, VectorUtil.isInCircleVec2() from paper by Guibas and Stolfi (1985)
is identified to produce wrong results for corner cases 
like square-box (rectangle) with a thin line-width.

A replacement version using the determinant with CCW triangle point order
has been initially tested to resolve this.

+++

(In reply to Sven Gothel from comment #2)

commit 277ad1ba1453b7e2e0164f1a609482a36469b2ea

    Bug 1501: Graph Delaunay: Add double triAreaVec2() and isInCircleVec2() version, overcome float precision; Loop: Pass edgeType not Winding, simplify findClosestValidNeighbor() -> isValidNeighbor(); CDTriangulator2D.addCurve() enforces Winding.CCW on BOUNDARY null == loop case
    
    Add double version of triAreaVec2() and isInCircleVec2() in VectorUtil, overcoming float precision limits
    - Analysis exposed float precision limits within isInCircleVec2()
    
    Loop: Pass edgeType not Winding, simplify findClosestValidNeighbor() -> isValidNeighbor()
    - Enhance code clarity
    
    CDTriangulator2D.addCurve() enforces Winding.CCW on BOUNDARY null == loop case

commit bf882af1675f390500cc36c5396f75c394372d52

    Bug 1501: Graph: Add UIShapeDemo02a test for rectangular shape provoking tessellation issue / or use Glyph03FreeMonoRegular_M

+++

commit a77b487a44124a9e55fa9a53d1f9c3ae20b9c3ba

    Bug 1501: Graph Delaunay: Use default winding outer-boundary:=CCW and inner-hole:=CW w/o using winding determination (might be incorrect)
    
    This simplifies our code further and it has been validated that our polygon shoelace-algo for area >= 0 ? CCW
    doesn't produce correct results with all curves.
    Hence rely on given winding depending on outer-boundary and inner-hole if CDTriangulator2D.FixedWindingRule == true (default and fixed).
    
    This also removes the more costly winding shoelace calculus,
    hence Outline ctor only sets dirtyWinding:=true w/o calculating the winding.

+++

commit dcacff437e23d93f1fa835bc4fff0a73242e51f6 (bug1501_01)

    Bug 1501 Graph Delaunay: Replace MaterialIconsRound-Regular.ttf with fixed winding direction (outer-bondary TTF CW (Graph CCW) and inner-hole TTF CCW (Graph CW)

(In reply to Sven Gothel from comment #4)
the above address the winding rule, assuming CDTriangulator2D.getContainerLoop(..)
works properly.

Still, Chinese Fonts and FreeMono show a considerable number of bugs :-(

Hence I would appreciate Rami's take on this, 
i.e. root cause and how to resolve.

(In reply to Sven Gothel from comment #5)
OK, I have figured things out myself.

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.

Of course, this intersection test is costly and at O(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

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.

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

(In reply to Sven Gothel from comment #6)
complexity of the intersection test in Loop.cut() is more costly than O(n),
since Loop.cut() itself is called over n, i.e. O(n).

Since the Loop.cut() set is reduced each step (sort of halved in total),
we may can claim the overall intersection test costs O(log(n)*n) 
or maybe even O(n/2*n) -> O(n*n)?

Hence a method determine whether the polygon is non-convex using O(n)
would give some speedup here - not too great, but better than nothing.

commit 101ec44f9d6df7faa0695accccfd43f51e48e7a4

    Bug 1501: Graph RenderState add debug-bits, i.e. DEBUG_LINESTRIP used in VBORegionSPES2 to just render lines instead of the filled area -> Used in UIShapeDemo02a

+++

commit 06e5b0503a0b32b8b1e5985a9da0d5373f8b7096

    Bug 1501: Graph Shape: onInit(ListenerBool) -> onDraw(DrawListener) w/ added capability for code injection to render
    
    Besides the one-shot on-init functionality, this allows us to re-render the shape differently.

+++

commit 220880f8105a35423a5c3dc3ea06147f9a8fd7e2

    VectorUtil: Consolidate names, remove unused float prevision variants (if any)

+++

commit 08f0d34424aab6a496a71fa5d83af6c407c7c569

    Bug 1501: VectorUtil: Deprecate prev line2line intersection tests, adding new impl; Add isConvex*() to determine whether a polyline is convex
    
    I had problems using the previous line2line intersection methods in my (and my son's) C++ gfxbox2 project, e.g. freefall01.
    Hence I found a different solution, also using less operations:
    <https://jausoft.com/cgit/cs_class/gfxbox2.git/tree/include/pixel/pixel2f.hpp#n660>
    
    While adding intersection tests for our Delaunay (Bug 1501) .. I came across this issue again
    and hence swapped the implementation.

(In reply to Sven Gothel from comment #6)

commit 949676fb8cac4d6aa626a375501e41a65a1a11fa

    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>

...    

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

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

Resolved 1st part for now, see Part II -> Bug 1503. 
Also Bug 1502 to perhaps address performance issues.

Will link upcoming blog entry w/ results here.

https://jausoft.com/blog/2024/02/13/fixing-jogamps-graph-delaunay-tessellation-of-complex-non-convex-shapes/

commit d4d4a797ab0e53db59dac1ea915825845861667e

    Bug 1501: Graph CDTriangulator2D: Add properties to enforce convex and non-convex treatment to simplify debugging etc

+++

commit e4b49663f6c6f138a8718847b68d1d78fba8fe73

    Bug 1501: Refine convex == !complex: Use 'complex' term, have env-property toggle OutlineShape's isComplex() for visibility
    
    We may use complex for other criteria than !convex, i.e. self-intersecting etc.

+++

commit b4d91c9df427122759df6b76ee06f535406f7074

    VectorUtil: Bring back specialized testSeg2segIntersection() w/ build-in FloatUtil.EPSILON epsilon and no collinear test
    
    commit 5488665474cc7b88577cedfca6416784f0fda3ba Generalize *seg2segIntersection* w/ epsilon and doCollinear
    caused a big performance hit about 1/3 due to added doCollinear case and manual epsilon adding branches
    and having the method being longer - probably not 'hotspot'ed.

+++

commit 840ffdf17f7c985f271f080b602bc2426223dcb8

    VectorUtil: Add experimental isSelfIntersecting1() with O(n*n) complexity
    
    This doesn't bring reliable results for Graph and also is pretty expensive.