edgeintersector.h

Go to the documentation of this file.

/*
* Copyright 2016 Autodesk, Inc. All rights reserved.
* Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
* or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
*/

#pragma once

#include "gwnavruntime/base/memory.h"
#include "gwnavruntime/math/vec2i.h"
#include "gwnavruntime/math/vec3i.h"
#include "gwnavruntime/containers/kyarray.h"
#include "gwnavruntime/visualsystem/color.h"
#include "gwnavruntime/dynamicnavmesh/dynamicnavmeshquerytypes.h"

namespace Kaim
{
// For Debug render
class DisplayList;
class Color;
class WorkingMemory;
class WorkingMemBitField;
template <class T>
class WorkingMemArray;

//----------------------------------------------------------------------
// Compute all the intersections between all the edges passed as input.
// The intersection points will be snapped to an integer grid and injected as "Cuts" on the original edges supplied.
// The snapping is done in a way that prevents spurious intersections that normally result from such process.
// This approach is similar to:
//----------------------------------------------------------------
// Hobby, J. - 1993
// Practical segment intersection with finite precision output.
// Technical Report 93/2-27, Bell Laboratories (Lucent Technologies)
//------------------------------------------------------------------

class EdgeIntersector
{
    KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)

public:
    EdgeIntersector() : m_debugDisplayListBeforeSnap(nullptr), m_debugDisplayListAfterSnap(nullptr), m_rasterPrecision(0.0f) {}

public:
    KyResult ComputeIntersections(WorkingMemory* workingMemory);

    static bool Intersects_grid_rounded(const Vec2i& hotPoint, const Vec2i& start, const Vec2i& end);

private:
    KyResult ComputeIntersections_Pass1(WorkingMemory* workingMemory, const WorkingMemArray<InputEdge>& rawEdges, const WorkingMemArray<Box2i>& edgeBoundingBoxes,
                                        WorkingMemArray<Vec2i>& points);

    void ComputeIntersections_Pass2(const WorkingMemArray<InputEdge>& rawEdges, const WorkingMemArray<Box2i>& edgeBoundingBoxes, const WorkingMemArray<Vec2i>& points);

    void ComputeIntersectionsOuputEdgePieces(const WorkingMemArray<InputEdge>& rawEdges, const WorkingMemArray<Vec2i>& points, KyArray<InputEdgePiece>& intersectedEdges);

    void InitEdges(const KyArray<InputEdge>& rawEdges);

    void ComputeBoundingBoxesOfInputEdges(const WorkingMemArray<InputEdge>& rawEdges, WorkingMemArray<Box2i>& edgeBoundingBoxes);

    void ComputeBoundingBoxesIntersection(const WorkingMemArray<InputEdge>& rawEdges, const WorkingMemArray<Box2i>& edgeBoundingBoxes, WorkingMemBitField& boxIntersect);

    KyResult SortHotPointAndRemoveDuplicate(WorkingMemory* workingMemory, const WorkingMemArray<InputEdge>& rawEdges, WorkingMemArray<IndexedPos>& hotPoints,
                                            WorkingMemArray<Vec2i>& uniqueHotPoints);

    void SortCutList(const WorkingMemArray<InputEdge>& rawEdges, const WorkingMemArray<Vec2i>& points);

    KyArray<KyArray<KyUInt32> > m_cuts; // an array of hotPoint Idx

public:
    // those functions are empty unless KY_FULL_DEBUG_EdgeIntersector is defined in the edgeintersector.cpp
    // displayListBeforeSnap and displayListAfterSnap pointers are use to distinguish what we want to display
    void FullDebugInit(KyFloat32 rasterPrecision, const Vec2i& cellOffset, DisplayList* displayListBeforeSnap, DisplayList* displayListAfterSnap);
    void FullDebugIntersections(const WorkingMemArray<InputEdge>& rawEdges, const WorkingMemArray<Vec2i>& hotPoints, DisplayList& displayList);
    KyResult FullDebugCheck(const WorkingMemArray<InputEdge>& rawEdges, const WorkingMemArray<Vec2i>& hotPoints, DisplayList* displayList);

    DisplayList* m_debugDisplayListBeforeSnap;
    DisplayList* m_debugDisplayListAfterSnap;
    KyFloat32 m_rasterPrecision;
    Vec2i m_cellOffset;
};

} // namespace Kaim