DelaunayTriangulation.h

/*--------------------------------------------------------------------------------------------
Copyright (c) 2019, NDEVR LLC
tyler.parke@ndevr.org
  __    __   ____     _____ __     __  _______
 |  \  |  | |  __ \  |  ___|\ \   / / |   __  \
 |   \ |  | | |  \ \ | |___  \ \ / /  |  |__)  |
 |  . \|  | | |__/ / | |___   \ V /   |   _   /
 |  |\    |_|_____/__|_____|___\_/____|  | \  \
 |__| \__________________________________|  \__\
 
Subject to the terms of the Enterprise+ Agreement, NDEVR hereby grants 
Licensee a limited, non-exclusive, non-transferable, royalty-free license 
(without the right to sublicense) to use the API solely for the purpose of 
Licensee's internal development efforts to develop applications for which 
the API was provided.
 
The above copyright notice and this permission notice shall be included in all 
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
 
Library: GeometrySurfacing
File: DelaunayTriangulation
Included in API: True
Author(s): Tyler Parke
 *-----------------------------------------------------------------------------------------**/
#pragma once
#include <NDEVR/Geometry.h>
#if NDEVR_SURFACING
#include <NDEVR/GeometrySurfacing.h>
#include <NDEVR/Buffer.h>
#include <NDEVR/Vector.h>
#include <NDEVR/RadialObject.h>
namespace NDEVR
{
    template<uint01 t_dims, class t_type> class RTree;
 
    class SelectionInfo;
    class InfoPipe;
    class DesignObjectLookup;
    class DelaunayPoint : public Vector<2, fltp08>
    {
    public:
        DelaunayPoint();
        DelaunayPoint(fltp08 a, fltp08 b);
        DelaunayPoint(fltp08 a, fltp08 b, fltp08 x);
        DelaunayPoint(const DelaunayPoint& p);
 
        DelaunayPoint& operator=(const DelaunayPoint& p);
        DelaunayPoint& operator=(const Vector<2, fltp08>& p);
        bool operator==(const DelaunayPoint& p2) const;
        bool operator!=(const DelaunayPoint& p2) const;
        bool operator<(const DelaunayPoint& b) const;
    public:
        Vector<2, fltp08> t;    
        uint04 id;              
        uint04 original_id;     
        uint04 trid;            
        fltp08 ro;              
    };
    class DelaunayTriangle : public Triangle<1, uint04>
    {
    public:
        DelaunayTriangle();
        DelaunayTriangle(uint04 a, uint04 b);
        DelaunayTriangle(uint04 a, uint04 b, uint04 c);
        DelaunayTriangle(uint04 a, uint04 b, uint04 c, uint04 ab, uint04 bc, uint04 ac);
        DelaunayTriangle(const DelaunayTriangle& p);
        constexpr uint04& neighborTriangle(TriangleLocation location)
        {
            switch (location)
            {
            case edge_ab: return edges[0];
            case edge_bc: return edges[1];
            case edge_ca: return edges[2];
            default: lib_assert(false, "Not a valid line segment request"); return edges[0];
            }
        }
        constexpr const uint04& neighborTriangle(TriangleLocation location) const
        {
            switch (location)
            {
            case edge_ab: return edges[0];
            case edge_bc: return edges[1];
            case edge_ca: return edges[2];
            default: lib_assert(false, "Not a valid line segment request"); return edges[0];
            }
        }
        constexpr const uint04& neighborTriangle(uint01 location) const
        {
            return edges[location];
        }
        constexpr void swapNeighborTriangle(uint04 old_tri_index, uint04 new_tri_index)
        {
            if (neighborTriangle(edge_ab) == old_tri_index)
                neighborTriangle(edge_ab) = new_tri_index;
            else if (neighborTriangle(edge_bc) == old_tri_index)
                neighborTriangle(edge_bc) = new_tri_index;
            else if (neighborTriangle(edge_ca) == old_tri_index)
                neighborTriangle(edge_ca) = new_tri_index;
            else
                lib_assert(false, "Did not swap valid edge");
        }
        DelaunayTriangle& operator=(const DelaunayTriangle& p);
    public:
        Vector<3, uint04> edges;            
        RadialObject<2, fltp08> circle;     
    };
    class NDEVR_SURFACING_API DelaunayTriangulation : public GeometrySurfacing
    {
    public:
        DelaunayTriangulation();
        virtual ~DelaunayTriangulation() override = default;
        virtual bool runSurfacing(GeometrySurfacingParameters & parameters) override;
        virtual Buffer<SurfacingDescription> defaultSurfacingArguments() override;

        static Buffer<Triangle<1, uint04>> Delaunay(const Matrix<fltp08> matrix, const Buffer<Vertex<3, fltp08>>& points, LogPtr log = LogPtr());
        static void Delaunay(const Matrix<fltp08> matrix, Geometry& points, const void* lock, LogPtr log = LogPtr());
        static bool isDelaunay(const Vector<2, fltp08>& A, const Vector<2, fltp08>& B, const Vector<2, fltp08>& C, const Vector<2, fltp08>& D);
        static void RegisterSurfacingEngine();
        void clipBoundaryTris();
    protected:
        explicit DelaunayTriangulation(LogPtr log);
        void makeDelaunay();
        void setPoints(const Matrix<fltp08> matrix, const Buffer<Vertex<3, fltp08>>& points);
        void setPoints(const Matrix<fltp08> matrix, const Geometry& points);
        void setupMaxCircle();
        void fillLookupTable();
        void triangulate();
        void initHull();
        void formHull(uint04 k);
        void formHullConvex(uint04& hidx, Vector<2, fltp08>& d, const Vector<2, fltp08>& x, DelaunayPoint& point);
        void formHullConcave(uint04& hidx, Vector<2, fltp08>& d, const Vector<2, fltp08>& x, DelaunayPoint& point);
        Buffer<Triangle<1, uint04>> getTris();
        inline void getFlipVars(uint04 tri_index, uint01 t_pos, const DelaunayTriangle& t1, const DelaunayTriangle& t2, Vector<5, uint04>& L, Vector<4, uint04>& p) const;
        template<bool t_protected>
        void checkTriAndFlip(uint04 tri_index, Buffer<uint04>& ids);
    protected:
        bool m_use_tree;                            
        RTree<2, fltp04>* m_r_tree;                 
        Buffer<uint04> m_point_cache;               
        Buffer<uint04> m_tri_cache;                 
        Buffer<DelaunayPoint> m_cache_bounds;       
        Buffer<DelaunayPoint> m_points;             
        Buffer<DelaunayTriangle> m_tris;            
        RadialObject<2, fltp08> m_max_circle;       
        LogPtr m_log;                               
    };
};
#endif