CDTriangulator2D.hpp

Go to the documentation of this file.

/*
 * Author: Sven Gothel <sgothel@jausoft.com> (C++, Java) and Rami Santina (Java)
 * Copyright Gothel Software e.K. and the authors
 *
 * SPDX-License-Identifier: MIT
 *
 * This Source Code Form is subject to the terms of the MIT License
 * If a copy of the MIT was not distributed with this file,
 * you can obtain one at https://opensource.org/license/mit/.
 */
#ifndef JAU_GAMP_GRAPH_TESS_CDTesselator2D_HPP_
#define JAU_GAMP_GRAPH_TESS_CDTesselator2D_HPP_
 
#include <jau/backtrace.hpp>
#include <jau/cpp_lang_util.hpp>
#include <jau/debug.hpp>
#include <jau/int_types.hpp>
#include <jau/io_util.hpp>
#include <jau/math/geom/geom3f2D.hpp>
#include <jau/string_util.hpp>
 
#include <gamp/GampTypes.hpp>
#include <gamp/graph/Graph.hpp>
#include <gamp/graph/Outline.hpp>
#include <gamp/graph/PrimTypes.hpp>
#include <gamp/graph/tess/impl/GraphOutline.hpp>
#include <gamp/graph/tess/impl/Loop.hpp>
 
namespace gamp::graph::tess {
 
    using namespace jau::math;
    using namespace jau::math::geom;
    using namespace gamp::graph;
 
    /** \addtogroup Gamp_Graph
     *
     *  @{
     */
 
    /**
     * Constrained Delaunay Triangulation
     * implementation of a list of Outlines that define a set of
     * Closed Regions with optional n holes.
     */
    class CDTriangulator2D { // : public Triangulator {
      private:
        impl::LoopRefList loops;
 
        bool complexShape;
        size_t m_addedVerticeCount;
        int32_t m_maxTriID;
 
      public:
        /** Constructor for a new Delaunay triangulator
         */
        constexpr CDTriangulator2D() noexcept
        : complexShape(false) { reset(); }
 
        constexpr void setComplexShape(bool complex) noexcept { complexShape = complex; }
 
        constexpr void reset() noexcept {
            m_maxTriID = 0;
            m_addedVerticeCount = 0;
            loops.clear();
        }
 
        constexpr size_t getAddedVerticeCount() const noexcept { return m_addedVerticeCount; }
 
        constexpr static bool FixedWindingRule = impl::Loop::FixedWindingRule;
 
        void addCurve(TriangleRefList& sink, Outline& polyline, float sharpness) {
            impl::LoopRef loop = getContainerLoop(polyline);
 
            if( !loop ) {
                // HEdge.BOUNDARY -> Winding.CCW
                if( !FixedWindingRule ) {
                    const Winding winding = polyline.getWinding();
                    if( Winding::CCW != winding ) {
                        WARN_PRINT("CDT2.add.xx.BOUNDARY: !CCW but %s", to_string(winding).c_str());
                        // polyline.print(System.err);
                        polyline.setWinding(Winding::CCW); // FIXME: Too late?
                    }
                }
                impl::GraphOutlineRef outline = impl::GraphOutline::create(polyline);
                impl::GraphOutlineRef innerPoly = extractBoundaryTriangles(sink, outline, false /* hole */, sharpness);
                // vertices.addAll(polyline.getVertices());
                if( innerPoly->graphPoints().size() >= 3 ) {
                    loop = impl::Loop::createBoundary(innerPoly, complexShape);
                    if( loop ) {
                        loops.push_back(loop);
                    }
                } else if ( Graph::DEBUG_MODE ) {
                    /*
                     * Font FreeMono-Bold: ID 0 + 465: Glyph[id 465 'uni020F', advance 600, leftSideBearings 42, kerning[size 0, horiz true, cross true], shape true], OutlineShape@5e8a459[outlines 2, vertices 34]
                        Drop innerPoly ctrlpts < 3
                        - innerPo[vertices 2, ctrlpts 2] < 3
                        - outline[vertices 4, ctrlpts 4]
                        -   Input[vertices 4]
                     *
                     * Font FreeSans-Regular: ID 0 + 409: Glyph[id 409 'Udieresiscaron', advance 720, leftSideBearings 80, kerning[size 0, horiz true, cross false], shape true], OutlineShape@5eb97ced[outlines 3, vertices 33]
                        Drop innerPoly ctrlpts < 3
                        - innerPo[vertices 1, ctrlpts 1] < 3
                        - outline[vertices 1, ctrlpts 1]
                        -   Input[vertices 1]
 
                     * Stack:
                       at jogamp.graph.curve.tess.CDTriangulator2D.addCurve(CDTriangulator2D.java:97)
                       at com.jogamp.graph.curve.OutlineShape.triangulateImpl(OutlineShape.java:988)
                       at com.jogamp.graph.curve.OutlineShape.getTriangles(OutlineShape.java:1012)
                       at com.jogamp.graph.curve.Region.countOutlineShape(Region.java:503)
                       at com.jogamp.graph.ui.shapes.GlyphShape.<init>(GlyphShape.java:77)
                     */
                    jau::PLAIN_PRINT(true, "Drop innerPoly ctrlpts < 3");
                    // jau::PLAIN_PRINT(true, "- innerPo[vertices "+innerPoly.getOutline().getVertexCount()+", ctrlpts "+innerPoly.getGraphPoint().size()+"] < 3");
                    // jau::PLAIN_PRINT(true, "- outline[vertices "+outline.getOutline().getVertexCount()+", ctrlpts "+outline.getGraphPoint().size()+"]");
                    // jau::PLAIN_PRINT(true, "-   Input[vertices "+polyline.getVertexCount()+"]");
                    jau::print_backtrace(true, 4);
                }
            } else {
                // HEdge.HOLE -> Winding.CW, but Winding.CCW is also accepted!
                // Winding.CW not required, handled in Loop.initFromPolyline(): polyline.setWinding(winding);
                impl::GraphOutlineRef outline = impl::GraphOutline::create(polyline);
                impl::GraphOutlineRef innerPoly = extractBoundaryTriangles(sink, outline, true /* hole */, sharpness);
                // vertices.addAll(innerPoly.getVertices());
                loop->addConstraintCurveHole(innerPoly);
            }
        }
 
        void generate(TriangleRefList& sink) {
            size_t loopsSize = loops.size();
            size_t size;
            for(size_t i=0;i<loopsSize;i++) {
                impl::LoopRef& loop = loops[i];
                size_t numTries = 0;
                size = loop->computeLoopSize();
                while(!loop->isSimplex()){
                    TriangleRef tri;
                    bool delaunay;
                    if(numTries > size) {
                        tri = loop->cut(false);
                        delaunay = false;
                    } else {
                        tri = loop->cut(true);
                        delaunay = true;
                    }
                    numTries++;
 
                    if(tri) {
                        tri->id() = m_maxTriID++;
                        sink.push_back(tri);
                        // if (Graph::DEBUG_MODE ) {
                            // jau::PLAIN_PRINT(true, "CDTri.gen["+i+"].0: delaunay "+delaunay+", tries "+numTries+", size "+size+", "+tri); // FIXME
                        // }
                        numTries = 0;
                        size--;
                    }
                    if(numTries > size*2){
                        // if (Graph::DEBUG_MODE ) {
                            // jau::PLAIN_PRINT("CDTri.gen["+i+"].X: Triangulation not complete!"); // FIXME
                        // }
                        break;
                    }
                    (void)delaunay;
                }
                TriangleRef tri = loop->cut(true);
                if(tri) {
                    tri->id() = m_maxTriID++;
                    sink.push_back(tri);
                    // if (Graph::DEBUG_MODE ) {
                        // jau::PLAIN_PRINT("CDTri.gen["+i+"].1: size "+size+"/"+loopsSize+", "+tri); // FIXME
                    // }
                }
            }
        }
 
      private:
        impl::GraphOutlineRef extractBoundaryTriangles(TriangleRefList& sink, const impl::GraphOutlineRef& outline, bool hole, float sharpness) {
            impl::GraphOutlineRef innerOutline = impl::GraphOutline::create();
            const impl::GraphVertexRefList& outVertices = outline->graphPoints();
            size_t size = outVertices.size();
            for(size_t i=0; i < size; i++) {
                const impl::GraphVertexRef& gv1 = outVertices[i];               // currentVertex
                const impl::GraphVertexRef& gv0 = outVertices[(i+size-1)%size]; // -1
                const impl::GraphVertexRef& gv2 = outVertices[(i+1)%size];      // +1
 
                if( !gv1->vertex().onCurve() ) {
                    Vertex v0 = gv0->vertex().clone(); // deep copy w/ a max id marker
                    Vertex v2 = gv2->vertex().clone();
                    Vertex v1 = gv1->vertex().clone();
                    m_addedVerticeCount += 3;
                    Triangle::tribit_t boundaryVertices;
                    boundaryVertices.put(0, true);
                    boundaryVertices.put(1, true);
                    boundaryVertices.put(2, true);
 
                    gv0->setBoundaryContained(true);
                    gv1->setBoundaryContained(true);
                    gv2->setBoundaryContained(true);
 
                    const bool holeLike = !is2DCCW(v0.coord(), v1.coord(), v2.coord());
                    if( hole || holeLike ) {
                        v0.texCoord() = Vec3f(0.0f,           -0.1f, 0);
                        v2.texCoord() = Vec3f(1.0f,           -0.1f, 0);
                        v1.texCoord() = Vec3f(0.5f, -sharpness-0.1f, 0);
                        innerOutline->addVertex(gv1);
                    } else {
                        v0.texCoord() = Vec3f(0.0f,            0.1f, 0);
                        v2.texCoord() = Vec3f(1.0f,            0.1f, 0);
                        v1.texCoord() = Vec3f(0.5f,  sharpness+0.1f, 0);
                    }
                    TriangleRef t;
                    if( holeLike ) {
                        t = Triangle::create(v2, v1, v0, boundaryVertices);
                    } else {
                        t = Triangle::create(v0, v1, v2, boundaryVertices);
                    }
                    t->id() = m_maxTriID++;
                    sink.push_back(t);
                    // if (Graph::DEBUG_MODE ) {
                        // PLAIN_PRINT(true, "CDTri.ebt[%zu].0: hole %d %s, %s", i, (hole || holeLike), gv1->toString().c_str(), t->toString().c_str());
                    // }
                } else {
                    if( !gv2->vertex().onCurve() || !gv0->vertex().onCurve() ) {
                        gv1->setBoundaryContained(true);
                    }
                    innerOutline->addVertex(gv1);
                    // if (Graph::DEBUG_MODE ) {
                        // PLAIN_PRINT(true, "CDTri.ebt[%zu].1: %s", i, gv1->toString().c_str());
                    // }
                }
            }
            return innerOutline;
        }
 
        impl::LoopRef getContainerLoop(const Outline& polyline) noexcept {
            size_t count = loops.size();
            if( 0 < count ) {
                const VertexList& vertices = polyline.vertices();
                for(size_t i=0; i < count; ++i) {
                    impl::LoopRef loop = loops[i];
                    for(size_t j=0; j < vertices.size(); ++j) { // NOLINT
                        if( loop->checkInside( vertices[j] ) ) {
                            return loop;
                        }
                    }
                }
            }
            return nullptr;
        }
    };
 
    /**@}*/
 
} // namespace gamp::graph::tess
 
#endif /*  JAU_GAMP_GRAPH_TESS_CDTesselator2D_HPP_ */