navrastercellscanlinepainter.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/navmesh/navmeshtypes.h"
#include "gwnavgeneration/containers/tlsarray.h"
#include "gwnavgeneration/common/generatormemory.h"
#include "gwnavruntime/navmesh/blobs/flooraltituderange.h"
#include "gwnavgeneration/navraster/navrastertypes.h"
#include "gwnavgeneration/navraster/navrastercell.h"

namespace Kaim
{

class DynamicNavRasterCell;
class NavRasterPixel;
class NavRasterWorkingPixel;
class DynamicNavRasterFinalColumn;

class NavRasterCellScanlinePainter
{
public:
    // Scan Pixel is a NavRasterPixel augmented with its own position and floorIdx (that NavRasterPixel does not have)
    // It would be much simpler to add m_pos and m_floorIdx to NavRasterPixel and work only with NavRasterPixel...
    class ScanPixel
    {
    public:
        ScanPixel() : m_navPixel(nullptr), m_pos(KyInt32MAXVAL, KyInt32MAXVAL), m_floorIdx(KyUInt32MAXVAL) {}
        ScanPixel(NavRasterPixel* navPixel, const PixelPos& pos, KyUInt32 floor) : m_navPixel(navPixel), m_pos(pos), m_floorIdx(floor) {}

        void Clear()
        {
            m_navPixel = nullptr;
            m_pos.Set(KyInt32MAXVAL, KyInt32MAXVAL);
            m_floorIdx = KyUInt32MAXVAL;
        }

        PixelColor GetFloorColor() const { return m_navPixel->m_floorColor; }
        void SetFloorColor(PixelColor color) { m_navPixel->m_floorColor = color; }

        PixelColor GetConnectedComponentIdx() const { return m_navPixel->m_connectedComponentIdx; }
        void SetConnectedComponentIdx(KyUInt32 idx) { m_navPixel->m_connectedComponentIdx = idx; }

        // dir could be extracted from neighbor.m_pos and this->m_pos but it's available in call context
        bool IsConnectedWith(CardinalDir dir, const ScanPixel& neighbor) { return m_navPixel->GetNeighborFloorIndex(dir) == neighbor.m_floorIdx; }

    public:
        NavRasterPixel* m_navPixel;
        PixelPos m_pos;
        KyUInt32 m_floorIdx;
    };

    class ColorData
    {
    public:
        ColorData(PixelColor color = PixelColor_Unset, KyUInt32 connectedComponentIdx = KyUInt32MAXVAL)
          : m_color(color), m_pixelCount(0), m_connectedComponentIdx(connectedComponentIdx), m_boundaryPixelBorderCount(0), m_indexInBinaryHeap(BinaryHeapInvalidReference)
        {}

        void UpdateColorDataFromNewPixel(NavRasterPixel* pixel, const PixelPos& pos);

    public:
        PixelColor m_color;
        PixelBox m_box;
        KyUInt32 m_pixelCount;
        KyUInt32 m_connectedComponentIdx;
        KyUInt32 m_boundaryPixelBorderCount;
        KyUInt32 m_indexInBinaryHeap;
        FloorAltitudeRange m_altRange;
    };

public:
    NavRasterCellScanlinePainter() : m_navRaster(nullptr), m_paintingMs(nullptr) {}

    void Clear();
    KyResult Paint();

    void SetNavRasterCell(DynamicNavRasterCell* cell) { m_navRaster = cell; }
    void SetConnexIdxToNavTagIdxArray(KyArrayTLS_POD<KyUInt32>* connexIdxToNavTagIdxArray) { m_connexIdxToNavTagIdxArray = connexIdxToNavTagIdxArray; }
    void SetPaintingMs(KyFloat32* paintingMs) { m_paintingMs = paintingMs; }

    KyUInt32 GetNbColorsUsed() const { return m_colorCount; }

private:
    void Init();                       // step 1
    void RemoveSmallNavTagArea();      // step 2
    void ComputeConnectedComponents(); // step 3
    void ComputeFloorColors();         // step 4
    void MergeFloorColors();           // step 5
    void ComputeConnexes();            // step 6

private:
    void PropagateInSouthWestBox();
    void PropagateInSouthEastBox();
    void PropagateInNorthWestBox();
    void PropagateInNorthEastBox();

    void PropagateFromCornerColumn(const PixelBox& paintBox, const PixelPos& cornerPos, CardinalDir expandLineDir, CardinalDir lineMoveDir);
    void PropagateFromCornerPixel(const PixelBox& paintBox, const ScanPixel& seedPixel, CardinalDir expandLineDir, CardinalDir lineMoveDir);
    PixelBox ComputeLocalPaintBoxForCorner(const PixelBox& paintBox, const ScanPixel& corner, CardinalDir expandLineDir, CardinalDir lineMoveDir);

    void PropagateFromBoxBorder(const PixelBox& paintBox, const PixelPos& startPos, CardinalDir expandLineDir, CardinalDir lineMoveDir);
    void PropagateFromBorderPixel(const PixelBox& paintBox, const ScanPixel& seedPixel, CardinalDir expandLineDir, CardinalDir lineMoveDir);
    PixelBox ComputeLocalPaintBoxForBorder(const PixelBox& paintBox, const ScanPixel& seedPixel, CardinalDir expandLineDir, CardinalDir lineMoveDir);

    void DisconnectOutsidePixelsAtBoxBounds(const PixelBox& paintBox, const ScanPixel& corner, CardinalDir dirAlongBorder, CardinalDir dirToOutside, PixelColor color);

    void PropagateFromAllRemainingUncoloredPixels();
    void PropagateFromUncoloredNonBorderPixel(const ScanPixel& startPixel);

    void ColorCellBoundaryPixelLineInBox(const PixelBox& localPaintBox, const ScanPixel& startPixel, PixelColor color, CardinalDir expandDir, CardinalDir borderDir,
                                         ScanPixel& lastPixelOnLine);

    bool TwoNeighborPixelHaveSameColor(const ScanPixel& pixel1, const ScanPixel& pixel2, CardinalDir dir, PixelColor currentColor);
    bool CanPropagateToPixel(PixelPos& pixelPos, KyUInt32 currentFloorIdx, KyUInt32 propagationIdx);

    void FindLowerConnectedPixel(const ScanPixel& startPixel, ScanPixel& lowerPixel);
    void CastPixelUntillBoundary(const ScanPixel& startScanPixel, CardinalDir castDir);

    PixelPos CastCellBoundaryPixel(const PixelBox& bbox, const ScanPixel& borderPixel, CardinalDir borderDir, CardinalDir outsideDir);
    void CastPixelCheckingColor(const ScanPixel& scanLine, PixelColor color, const PixelBox& bbox, CardinalDir castdir);
    void PaintLastPixelCastResultAndOutsideNeighbors(PixelColor color, CardinalDir borderDir);

    bool GetNeighbor_InsideNavPixelBox(const ScanPixel& pixel, CardinalDir dir, ScanPixel& neighborPixel); // uses m_navRaster->m_navPixelBox
    bool GetNeighbor(const PixelBox& box, const ScanPixel& pixel, CardinalDir dir, ScanPixel& neighborPixel);

    PixelColor GetNewFloorColor(KyUInt32 connectedComponentIdx);
    void SetFloorColor(const ScanPixel& pixel, PixelColor color);        // takes a const ScanPixel& because const does not propagate to ScanPixel::m_navPixel* m_navPixel
    void SetOutsideFloorColor(const ScanPixel& pixel, PixelColor color); // takes a const ScanPixel& because const does not propagate to ScanPixel::m_navPixel* m_navPixel

    bool CanSetColorToPixel(const PixelPos& pixelPos, KyUInt32 floorIdx, PixelColor newColor);

    bool CanPaintNeighborLine(const ScanPixel& startScanPixel, const ScanPixel& endScanPixel, PixelColor color, const PixelBox& bbox, CardinalDir lineDir, CardinalDir expandDir,
                              ScanPixel& borderLineStartScanPixel, ScanPixel& borderLineEndScanPixel, KyUInt32& neighborLineCount, KyFloat32& altRangeDiffWithNeighborLine);

    void DetectForbiddenColorMergeAndConnectedColors();
    void ComputeMergedColors();
    void ApplyFinalColorToPixels();

    struct ScanPixelSorterByAlt
    {
        bool operator()(const ScanPixel& pixel1, const ScanPixel& pixel2) const { return pixel1.m_navPixel->m_altitude < pixel2.m_navPixel->m_altitude; }
    };

    void ChangeNavTagOfSmallNavTagConnectedComponent(const PixelBox& safenavTagRemovalBox, const ScanPixel& startPixel, KyUInt32 connectedComponentIdx, KyUInt32 minPixelCount);
    void PropagateConnectedComponent(const ScanPixel& startPixel, KyUInt32 connectedComponentIdx);

    void PropagateConnex_FromColumn(const Box2i& box, const PixelPos& pos, KyUInt32& connexIdx);
    void PropagateConnex_FromPixel(const Box2i& box, const ScanPixel& startPixel, KyUInt32 connexIdx);

    bool IsOutsideBorder(const ScanPixel& pixel);

private:
    DynamicNavRasterCell* m_navRaster;
    PixelBox m_navPixelBox;
    PixelBox m_exclusivePixelBox;
    KyFloat32* m_paintingMs;
    KyUInt32 m_colorCount;
    KyArrayTLS<ScanPixel> m_propagationStack; // cache the array between floodFills to avoid multiple resizes
    KyArrayTLS_POD<ScanPixel> m_navTagArea;
    KyArrayTLS_POD<ScanPixel> m_navTagAreaNeighbors;
    KyArrayTLS<ColorData> m_colorData;

    BitFieldTLS m_forbiddenColorMerge;
    BitFieldTLS m_connectedColors;
    KyArrayTLS_POD<PixelColor> m_finalColor; // m_finalColor[color] = finalColor after merge !

    KyArrayTLS<ScanPixel> m_castForwardResult;
    KyArrayTLS<ScanPixel> m_castBackwardResult;
    KyArrayTLS<ScanPixel> m_onePixelPerFinalColor;

    BinaryHeapTls<ScanPixel, ScanPixelSorterByAlt> m_orderedPixels;
    KyArrayTLS_POD<KyUInt32>* m_connexIdxToNavTagIdxArray;

    PixelPos m_midPos;
    KyUInt32 m_currentPropagationId;
};

inline PixelColor NavRasterCellScanlinePainter::GetNewFloorColor(KyUInt32 connectedComponentIdx)
{
    PixelColor color = m_colorData.GetCount();
    m_colorData.PushBack(ColorData(color, connectedComponentIdx));
    return color;
}

inline void NavRasterCellScanlinePainter::SetFloorColor(const ScanPixel& pixel, PixelColor color)
{
    KY_ASSERT(pixel.m_navPixel != nullptr);
    KY_ASSERT(pixel.m_navPixel->m_floorColor == PixelColor_Unset);
    KY_ASSERT(color < m_colorData.GetCount());
    KY_ASSERT(m_navPixelBox.DoesContain(pixel.m_pos));

    pixel.m_navPixel->m_floorColor = color;
    m_colorData[color].UpdateColorDataFromNewPixel(pixel.m_navPixel, pixel.m_pos);
}

inline void NavRasterCellScanlinePainter::SetOutsideFloorColor(const ScanPixel& pixel, PixelColor color)
{
    KY_ASSERT(pixel.m_navPixel != nullptr);
    KY_ASSERT(IsOutsideBorder(pixel));

    pixel.m_navPixel->m_floorColor = color;
    // We do not call m_colorData[color].UpdateColorDataFromNewPixel(pixel.m_navPixel, pixel.m_pos); on purpose !
    // We do not want the outside pixels to change the color properties(pixelCount, bbox, ...)
}

inline void NavRasterCellScanlinePainter::ColorData::UpdateColorDataFromNewPixel(NavRasterPixel* currentPixel, const PixelPos& pos)
{
    KY_LOG_ERROR_IF(currentPixel->m_floorColor != m_color, ("Wrong color data for this pixel"));
    ++m_pixelCount;
    m_altRange.Update(currentPixel->m_altitude);
    m_box.ExpandByPos(pos);
    for (KyUInt32 i = 0; i < 4; ++i)
    {
        if (currentPixel->m_neighborFloorIdx[i] == NavRasterFloorIdx_Invalid)
            ++m_boundaryPixelBorderCount;
    }
}

inline bool NavRasterCellScanlinePainter::IsOutsideBorder(const ScanPixel& pixel)
{
    return !m_exclusivePixelBox.DoesContain(pixel.m_pos) && m_navPixelBox.DoesContain(pixel.m_pos);
}

}