#ifndef BORDERS_EXTRACTOR_HPP
#define BORDERS_EXTRACTOR_HPP
//Toonz includes
#include "raster_edge_iterator.h"
//tcg includes
#include "tcg/tcg_traits.h"
#include "tcg/tcg_containers_reader.h"
#include "tcg/tcg_hash.h"
#include "tcg/tcg_misc.h"
#include "borders_extractor.h"
namespace TRop
{
namespace borders
{
//*********************************************************************************************************
// Private stuff
//*********************************************************************************************************
template <typename PixelSelector>
class _DummyReader
{
public:
void openContainer(const RasterEdgeIterator<PixelSelector> &) {}
void addElement(const RasterEdgeIterator<PixelSelector> &) {}
void closeContainer() {}
};
//*********************************************************************************************************
// Borders Extraction procedure
//*********************************************************************************************************
inline void _signEdge(RunsMapP &runsMap, int x, int y0, int y1, UCHAR increasingSign, UCHAR decreasingSign)
{
for (; y0 < y1; ++y0)
runsMap->runHeader(x, y0) |= increasingSign;
if (y0 > y1) {
--x;
do {
--y0;
runsMap->runHeader(x, y0) |= decreasingSign;
} while (y0 > y1);
}
}
//---------------------------------------------------------------------------------------------
template <typename Pixel, typename PixelSelector, typename ContainerReader>
void _readBorder(const TRasterPT<Pixel> &rin, const PixelSelector &selector,
RunsMapP &runsMap, int x, int y, bool counter, ContainerReader &reader)
{
typedef typename PixelSelector::value_type value_type;
UCHAR increasingSign = _BORDER_LEFT, decreasingSign = _BORDER_RIGHT;
if (!counter)
increasingSign |= _HIERARCHY_INCREASE, decreasingSign |= _HIERARCHY_DECREASE;
//First, read the border entirely, while erasing the border from
//the runsMap.
RasterEdgeIterator<PixelSelector> it(rin, selector, TPoint(x, y), counter ? TPoint(1, 0) : TPoint(0, 1));
//++it; //As we could be in the middle of a straight edge, increment to get a corner
TPoint start(it.pos()), startDir(it.dir());
reader.openContainer(it);
TPoint oldPos(start);
for (++it; it.pos() != start || it.dir() != startDir; ++it) {
const TPoint &currPos(it.pos());
reader.addElement(it);
//Sign the corresponding (vertical) edge
_signEdge(runsMap, oldPos.x, oldPos.y, currPos.y, increasingSign, decreasingSign);
oldPos = currPos;
}
_signEdge(runsMap, oldPos.x, oldPos.y, it.pos().y, increasingSign, decreasingSign);
reader.closeContainer();
}
//---------------------------------------------------------------------------------------------
template <typename Pixel, typename PixelSelector, typename ContainerReader>
void readBorders(const TRasterPT<Pixel> &rin, const PixelSelector &selector,
ContainerReader &reader, RunsMapP *rasterRunsMap)
{
typedef TRasterPT<Pixel> RasterTypeP;
typedef _DummyReader<PixelSelector> DummyReader;
//First, extract the run-length representation for rin
RunsMapP runsMap;
if (rasterRunsMap && *rasterRunsMap) {
//If it was supplied, use it
runsMap = *rasterRunsMap;
runsMap->lock();
} else {
//In case, build it anew
runsMap = RunsMapP(rin->getLx(), rin->getLy());
runsMap->lock();
buildRunsMap(runsMap, rin, selector);
}
if (rasterRunsMap)
//Return the runsMap if requested
*rasterRunsMap = runsMap;
//Build a fake reader for internal borders
DummyReader dummyReader;
//Now, use it to extract borders - iterate through runs and, whenever
//one is found with opaque color (ie not transparent), extract its
//associated border. The border is erased internally after the read.
int lx = rin->getLx(), ly = rin->getLy();
int hierarchyLevel = 0;
int x, y;
for (y = 0; y < ly; ++y) {
Pixel *lineStart = rin->pixels(y), *pix;
TPixelGR8 *runsStart = runsMap->pixels(y), *run;
UCHAR nextHeader, prevHeader = 0;
for (x = 0, pix = lineStart, run = runsStart; x < lx;) {
nextHeader = run->value;
if (hierarchyLevel) {
if (prevHeader & _BORDER_RIGHT) {
if (prevHeader & _HIERARCHY_DECREASE)
--hierarchyLevel;
} else //Every right border in a region should be signed. Do so now.
_readBorder(rin, selector, runsMap, x, y, true, dummyReader);
}
if (hierarchyLevel) {
if (nextHeader & _BORDER_LEFT) {
if (nextHeader & _HIERARCHY_INCREASE)
++hierarchyLevel;
} else {
++hierarchyLevel;
_readBorder(rin, selector, runsMap, x, y, false, reader);
}
} else {
if (!(selector.transparent(*pix))) //External transparent region - do not extract
{
++hierarchyLevel;
if (!(nextHeader & _BORDER_LEFT))
_readBorder(rin, selector, runsMap, x, y, false, reader);
}
}
//Increment variables
x += runsMap->runLength(x, y), pix = lineStart + x, run = runsStart + x;
prevHeader = (run - 1)->value;
}
assert(x == lx);
if (hierarchyLevel) {
assert((prevHeader & _BORDER_RIGHT) && (prevHeader & _HIERARCHY_DECREASE));
--hierarchyLevel;
}
assert(!hierarchyLevel);
}
runsMap->unlock();
}
//*********************************************************************************************************
// New Mesh Extraction procedure
//*********************************************************************************************************
enum { _PROCESSED = 0x1,
_HIERARCHY_UP = 0x2,
_HIERARCHY_DN = 0x4,
_PROCESSED_AND_HIERARCHY_UP = (_PROCESSED | _HIERARCHY_UP) };
//-------------------------------------------------------------------
template <typename RasterEdgeIter>
inline bool _isVertex(const RasterEdgeIter &it, const typename RasterEdgeIter::value_type &oldOtherColor)
{
return (it.otherColor() != oldOtherColor) ||
(it.turn() == it.adherence() && (!(it.turn() & RasterEdgeIter::AMBIGUOUS)) &&
it.elbowColor() != oldOtherColor);
}
//-------------------------------------------------------------------
inline size_t _pointHash(const TPoint &point) { return point.x ^ point.y; }
//-------------------------------------------------------------------
template <typename RasterEdgeIter>
struct _ExternalEdgeSigner {
static inline void signAndIncrement(RunsMapP &runsMap, RasterEdgeIter &it)
{
if (it.dir().y > 0) {
TPoint pos = it.pos();
int newY = (++it).pos().y;
for (; pos.y != newY; ++pos.y)
runsMap->runHeader(pos.x, pos.y) |= _PROCESSED_AND_HIERARCHY_UP;
} else if (it.dir().y < 0) {
TPoint pos = it.pos();
int newY = (++it).pos().y;
TPixelGR8 *pix = runsMap->pixels(pos.y - 1) + pos.x;
for (; pos.y != newY; --pos.y, --pix) {
pix->value |= _PROCESSED;
(--pix)->value |= _HIERARCHY_DN;
}
} else
++it;
}
};
//-------------------------------------------------------------------
template <typename RasterEdgeIter>
struct _InternalEdgeSigner {
static inline void signAndIncrement(RunsMapP &runsMap, RasterEdgeIter &it)
{
if (it.dir().y) {
TPoint pos = it.pos();
int newY = (++it).pos().y;
int dir = it.dir().y;
TPixelGR8 *pix = runsMap->pixels((it.dir().y > 0) ? pos.y : pos.y - 1) + pos.x;
for (; pos.y != newY; pos.y += dir, pix += dir) {
pix->value |= _PROCESSED_AND_HIERARCHY_UP;
(--pix)->value |= _HIERARCHY_DN;
}
} else
++it;
}
};
//-------------------------------------------------------------------
template <typename RasterEdgeIter, typename Mesh, typename ContainersReader, typename EdgeSigner>
int _readEdge(RasterEdgeIter &it, const RasterEdgeIter &end, RunsMapP runsMap,
int &vIdx, Mesh &mesh, tcg::hash<TPoint, int> &pointsHash, ContainersReader &reader)
{
typedef tcg::container_reader_traits<ContainersReader, typename Mesh::edge_type> edge_output;
typename Mesh::edge_type ed;
ed.addVertex(vIdx);
ed.direction(0) = it.dir();
edge_output::openContainer(reader, it);
typename RasterEdgeIter::value_type oldOtherColor = it.otherColor();
do {
EdgeSigner::signAndIncrement(runsMap, it);
edge_output::addElement(reader, it);
} while ((it != end) && !_isVertex(it, oldOtherColor));
// Identify the newly found vertex. If it's a brand new one, add it
tcg::hash<TPoint, int>::iterator ht = pointsHash.find(it.pos());
vIdx = (ht == pointsHash.end()) ? pointsHash[it.pos()] = mesh.addVertex(typename Mesh::vertex_type(it.pos())) : ht.m_idx;
ed.addVertex(vIdx);
ed.direction(1) = (it.turn() == RasterEdgeIter::STRAIGHT) ? -it.dir() : (it.turn() == RasterEdgeIter::LEFT) ? tcg::point_ops::ortLeft(it.dir()) : tcg::point_ops::ortRight(it.dir());
int eIdx = mesh.addEdge(ed);
edge_output::closeContainer(reader, &mesh, eIdx);
return eIdx;
}
//---------------------------------------------------------------------------------------------
template <typename RasterEdgeIter, typename Mesh, typename ContainersReader>
void _readMeshes(const RasterEdgeIter &begin, RunsMapP &runsMap, ContainersReader &reader)
{
typedef tcg::container_reader_traits<ContainersReader, typename Mesh::face_type> face_output;
// Iterate it clockwise. Process lines with vertical displacement. In each line, search
// for unprocessed raster edges.
// Use hierarchy signs in the runsMap to understand the search scope in this sub-region.
int hierarchyLevel = 0;
RasterEdgeIter it(begin);
do {
if (it.dir().y > 0) {
// Process line
TPoint pos = it.pos();
const TPixelGR8 *pix = runsMap->pixels(pos.y) + pos.x;
hierarchyLevel = 0;
assert((pix->value & _PROCESSED) && (pix->value & _HIERARCHY_UP));
do {
// Iterate through the line. Extract a mesh each time an unprocessed raster edge is found.
if (!(pix->value & _PROCESSED)) {
assert(hierarchyLevel == 1);
Mesh *meshPtr = new Mesh;
_readMesh(it.raster(), it.selector(), runsMap, pos.x, pos.y, *meshPtr, reader);
face_output::addElement(reader, meshPtr);
}
if (pix->value & _HIERARCHY_UP)
++hierarchyLevel;
TUINT32 l = runsMap->runLength(pos.x, pos.y);
pos.x += l;
pix += l;
if ((pix - 1)->value & _HIERARCHY_DN)
--hierarchyLevel;
} while (hierarchyLevel > 0);
}
++it;
} while (it != begin);
}
//-------------------------------------------------------------------
template <typename RasterEdgeIter, typename Mesh, typename ContainersReader>
void _readBorder(const RasterEdgeIter &begin, RunsMapP runsMap,
int vIdx, Mesh &mesh, tcg::hash<TPoint, int> &pointsHash,
ContainersReader &reader)
{
typedef typename Mesh::face_type face_type;
typedef typename Mesh::edge_type edge_type;
typedef tcg::container_reader_traits<ContainersReader, typename Mesh::face_type> face_output;
// As long as we don't get back to the initial iterator, extract edges
RasterEdgeIter it(begin);
// Create the face to be extracted at the right of processed border, and add it to
// the mesh. Observe that insertion is made manually in the mesh's faces list.
// This prevents the mesh from automatically link edges to the face.
face_type fc;
do {
// Retrieve current vertex
typename Mesh::vertex_type &vx = mesh.vertex(vIdx);
// Search in it the edge corresponding to current iterating direction
int e, edgesCount = vx.edgesCount(), eIdx = -1, side = -1;
for (e = 0; e < edgesCount; ++e) {
edge_type &ed = mesh.edge(vx.edge(e));
side = ed.vertex(0) == vIdx ? 0 : 1;
if (ed.direction(side) == it.dir()) {
eIdx = ed.getIndex();
break;
}
}
if (e == edgesCount) {
// In case the edge was not found, it needs to be extracted now.
eIdx = _readEdge<RasterEdgeIter, Mesh, ContainersReader, _InternalEdgeSigner<RasterEdgeIter>>(
it, begin, runsMap, vIdx, mesh, pointsHash, reader);
} else {
// The edge was already extracted. We just need to update the iterator then.
const edge_type &ed = mesh.edge(eIdx);
vIdx = ed.vertex(1 - side);
const TPoint &oppositePos = mesh.vertex(vIdx).P();
const TPoint &oppositeDir = ed.direction(1 - side);
// We need to perform the last ++it in the already extracted edge since we need
// to give it the incoming direction.
it.setEdge(oppositePos + oppositeDir, -oppositeDir), ++it;
}
fc.addEdge(eIdx);
} while (it != begin);
// The face has now been described (from the mesh viewpoint). Add it to the mesh.
int fIdx = mesh.addFace(fc);
// We still need to extract its sub-meshes content now.
face_output::openContainer(reader, &mesh, fIdx, begin.rightColor());
_readMeshes<RasterEdgeIter, Mesh, ContainersReader>(begin, runsMap, reader);
face_output::closeContainer(reader);
}
//-------------------------------------------------------------------
template <typename PixelSelector, typename Mesh, typename ContainersReader>
void _readMesh(const TRasterPT<typename PixelSelector::pixel_type> &rin,
const PixelSelector &selector, RunsMapP &runsMap, int x, int y,
Mesh &mesh, ContainersReader &reader)
{
typedef typename Mesh::vertex_type vertex_type;
typedef typename Mesh::edge_type edge_type;
typedef tcg::container_reader_traits<ContainersReader, edge_type> edge_output;
typedef typename PixelSelector::value_type value_type;
typedef RasterEdgeIterator<PixelSelector> raster_edge_iterator;
// Iterate silently until a vertex is encountered (or until the initial point is found)
raster_edge_iterator it(rin, selector, TPoint(x, y), TPoint(0, 1)), begin(it);
it.setAdherence(raster_edge_iterator::LEFT);
value_type beginColor = begin.rightColor();
for (++it; it != begin && !_isVertex(it, beginColor); ++it)
;
// Use a hash to keep track of found vertices
tcg::hash<TPoint, int> pointsHash(&_pointHash);
int vIdx = pointsHash[it.pos()] = mesh.addVertex(it.pos());
// The outer edges are extracted first in clockwise orientation.
begin = it;
do {
_readEdge<raster_edge_iterator, Mesh, ContainersReader, _ExternalEdgeSigner<raster_edge_iterator>>(
it, begin, runsMap, vIdx, mesh, pointsHash, reader);
} while (it != begin);
// Then, their associated faces are extracted.
it.setAdherence(raster_edge_iterator::RIGHT);
int e, outerEdgesCount = mesh.edgesCount();
for (e = 0; e < outerEdgesCount; ++e) {
const edge_type &ed = mesh.edge(e);
if (ed.face(0) < 0) {
vIdx = ed.vertex(0);
const vertex_type &vx = mesh.vertex(vIdx);
it.setEdge(vx.P(), ed.direction(0));
_readBorder(it, runsMap, vIdx, mesh, pointsHash, reader);
}
}
// Edges following those must have either side associated with a face.
// Which must be extracted too.
for (e = outerEdgesCount; e < mesh.edgesCount(); ++e) {
const edge_type &ed = mesh.edge(e);
if (ed.face(1) < 0) {
vIdx = ed.vertex(1);
const vertex_type &vx = mesh.vertex(vIdx);
it.setEdge(vx.P(), ed.direction(1));
_readBorder(it, runsMap, vIdx, mesh, pointsHash, reader);
}
}
}
//---------------------------------------------------------------------------------------------
template <typename PixelSelector, typename Mesh, typename ContainersReader>
void readMeshes(const TRasterPT<typename PixelSelector::pixel_type> &rin, const PixelSelector &selector,
ContainersReader &reader, RunsMapP *rasterRunsMap)
{
typedef typename PixelSelector::pixel_type pixel_type;
typedef TRasterPT<pixel_type> RasterTypeP;
typedef Mesh mesh_type;
typedef tcg::container_reader_traits<ContainersReader, typename Mesh::face_type> face_output;
// First, extract the run-length representation for rin
RunsMapP runsMap;
if (rasterRunsMap && *rasterRunsMap) {
// If a runsmap was supplied, use it
runsMap = *rasterRunsMap;
runsMap->lock();
assert((runsMap->getLx() == rin->getLx() + 1) && (runsMap->getLy() == rin->getLy()));
} else {
// In case, build it anew
runsMap = RunsMapP(rin->getLx() + 1, rin->getLy());
// Observe the +1 on the x-axis. One additional pixel is currently required on the right
// side of the runsmap - for ease of use in the algorithm.
runsMap->lock();
buildRunsMap(runsMap, rin, selector);
}
if (rasterRunsMap)
// Return the runsMap if requested
*rasterRunsMap = runsMap;
face_output::openContainer(reader, 0, -1, selector.transparent());
// Now, use it to extract borders - iterate through runs and, whenever
// one is found with opaque color (ie not transparent), extract its
// associated border. The border is erased internally after the read.
int lx = rin->getLx(), ly = rin->getLy();
int x, y;
for (y = 0; y < ly; ++y) {
// Process each row
pixel_type *lineStart = rin->pixels(y), *pix;
TPixelGR8 *runsStart = runsMap->pixels(y), *run;
UCHAR nextHeader, prevHeader = 0;
for (x = 0, pix = lineStart, run = runsStart; x < lx;) {
nextHeader = run->value;
if (!(selector.transparent(*pix) || nextHeader & _PROCESSED)) {
mesh_type *meshPtr = new mesh_type;
// Read the mesh. All its internal sub-meshes are read as well.
_readMesh(rin, selector, runsMap, x, y, *meshPtr, reader);
face_output::addElement(reader, meshPtr);
}
//Increment variables
x += runsMap->runLength(x, y), pix = lineStart + x, run = runsStart + x;
prevHeader = (run - 1)->value;
}
assert(x == lx);
}
face_output::closeContainer(reader);
runsMap->unlock();
}
}
} //namespace TRop::borders
#endif //BORDERS_EXTRACTOR_HPP