DelaunayTriangulation.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------------------------
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 ProgressInfo;
    class DesignObjectLookup;
    /**--------------------------------------------------------------------------------------------------
    \brief A Point or node used in DelaunayTriangulation
    **/
    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;//Connection graph point
        uint04 id;//Original point id
        uint04 trid;//Temp Id of triangle
        fltp08 ro;//Used for consistant sorting from orginal max circle
    };
    /**--------------------------------------------------------------------------------------------------
    \brief A triangle used in DelaunayTriangulation
    **/
    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 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;
    };
    /**--------------------------------------------------------------------------------------------------
    \brief Creates a surface from random points using Delaunay Triangulation: 
        https://en.wikipedia.org/wiki/Delaunay_triangulation
    **/
    class 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, ProgressInfo* log = nullptr);
        static void Delaunay(const Matrix<fltp08> matrix, Geometry& points, const void* lock, ProgressInfo* log = nullptr);
        static bool isDelaunay(const Vector<2, fltp08>& A, const Vector<2, fltp08>& B, const Vector<2, fltp08>& C, const Vector<2, fltp08>& D);
        NDEVR_SURFACING_API static void RegisterSurfacingEngine();
    protected:
        explicit DelaunayTriangulation(ProgressInfo* 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;
        Buffer<uint04> m_lookup_table;
        RadialObject<2, fltp08> m_max_circle;
        ProgressInfo* m_log;
    };
};
#endif