orthanc: OrthancFramework/Sources/Images/ImageProcessing.cpp comparison

comparison OrthancFramework/Sources/Images/ImageProcessing.cpp @ 4872:b1556cefa5c6

reimplementation from scratch of ImageProcessing::FillPolygon()

author	Sebastien Jodogne <s.jodogne@gmail.com>
date	Mon, 17 Jan 2022 21:11:40 +0100
parents	43e613a7756b
children	d68dbe6590ce

comparison

equal deleted inserted replaced

-:55469ccfb384
+:b1556cefa5c6
 #pragma GCC diagnostic ignored "-Wimplicit-int-float-conversion"
 #endif
 #include <boost/math/special_functions/round.hpp>
+#include <algorithm>
 #include <cassert>
+#include <limits>
+#include <list>
+#include <map>
+#include <stdint.h>
 #include <string.h>
-#include <limits>
-#include <stdint.h>
-#include <algorithm>
 namespace Orthanc
 {
 ImageProcessing::ImagePoint::ImagePoint(int32_t x,
 int32_t y) :
 bottom = std::max(p.GetY(), bottom);
 top = std::min(p.GetY(), top);
 }
 }
-template <PixelFormat TargetFormat>
-void FillPolygon_(ImageAccessor& image,
+namespace
-const std::vector<ImageProcessing::ImagePoint>& points,
+{
-int64_t value_)
+#define USE_POLYGON_FRACTIONS 1
-{
-typedef typename PixelTraits<TargetFormat>::PixelType  TargetType;
+class PolygonEdge
+{
-TargetType value = PixelTraits<TargetFormat>::IntegerToPixel(value_);
+private:
-int imageWidth = static_cast<int>(image.GetWidth());
+int   yUpper;
-int imageHeight = static_cast<int>(image.GetHeight());
-int32_t left;
+#if USE_POLYGON_FRACTIONS == 1
-int32_t right;
+int  x;
-int32_t top;
+int  xOffset;
-int32_t bottom;
+int  dxPerScanNumerator;
+int  dxPerScanDenominator;
-// TODO: test clipping in UT (in Trello board)
+#else
-ComputePolygonExtent(left, right, top, bottom, points);
+float xIntersect;
+float dxPerScan;
-// clip the computed extent with the target image
+#endif
-// L and R
-left = std::max(0, left);
+public:
-left = std::min(imageWidth, left);
+PolygonEdge(const ImageProcessing::ImagePoint& lower,
-right = std::max(0, right);
+const ImageProcessing::ImagePoint& upper,
-right = std::min(imageWidth, right);
+int yComp)
-if (left > right)
+{
-std::swap(left, right);
+// cf. "makeEdgeRec()" in textbook
-// T and B
+assert(upper.GetY() != lower.GetY());
-top = std::max(0, top);
-top = std::min(imageHeight, top);
+#if USE_POLYGON_FRACTIONS == 1
-bottom = std::max(0, bottom);
+x = lower.GetX();
-bottom = std::min(imageHeight, bottom);
+xOffset = 0;
-if (top > bottom)
+dxPerScanNumerator = upper.GetX() - lower.GetX();
-std::swap(top, bottom);
+dxPerScanDenominator = upper.GetY() - lower.GetY();
+#else
-// from http://alienryderflex.com/polygon_fill/
+dxPerScan = (static_cast<float>(upper.GetX() - lower.GetX()) /
+static_cast<float>(upper.GetY() - lower.GetY()));
-// convert all "corner"  points to double only once
+xIntersect = lower.GetX();
-std::vector<double> cpx;
+#endif
-std::vector<double> cpy;
-size_t cpSize = points.size();
+if (upper.GetY() < yComp)
+{
+yUpper = upper.GetY() - 1;
+}
+else
+{
+yUpper = upper.GetY();
+}
+}
+float GetActualX() const
+{
+#if USE_POLYGON_FRACTIONS == 1
+return (static_cast<float>(x) +
+static_cast<float>(xOffset) /
+static_cast<float>(dxPerScanDenominator));
+#else
+return xIntersect;
+#endif
+}
+void NextScanLine()
+{
+#if USE_POLYGON_FRACTIONS == 1
+xOffset += dxPerScanNumerator;
+while (xOffset >= dxPerScanDenominator)
+{
+x++;
+xOffset -= dxPerScanDenominator;
+}
+while (xOffset < 0)
+{
+x--;
+xOffset += dxPerScanDenominator;
+}
+#else
+xIntersect += dxPerScan;
+#endif
+}
+int GetEnterX() const
+{
+#if USE_POLYGON_FRACTIONS == 1
+assert(xOffset >= 0 && xOffset < dxPerScanDenominator);
+if (xOffset == 0)
+{
+return x;
+}
+else
+{
+return x + 1;
+}
+#else
+return std::ceil(GetActualX());  // TODO
+#endif
+}
+int GetExitX() const
+{
+#if USE_POLYGON_FRACTIONS == 1
+assert(xOffset >= 0 && xOffset < dxPerScanDenominator);
+return x;
+#else
+return std::floor(GetActualX());  // TODO
+#endif
+}
+int GetUpperY() const
+{
+return yUpper;
+}
+bool operator< (const PolygonEdge& other) const
+{
+// cf. "insertEdge()" in textbook
+return (GetActualX() < other.GetActualX());
+}
+};
+}
+// For an index, return y-coordinate of next nonhorizontal line
+static size_t GetPolygonNextY(const std::vector<ImageProcessing::ImagePoint>& points,
+size_t k)
+{
+// cf. "yNext()" in textbook
+size_t j = k + 1;
+for (;;)
+{
+if (j >= points.size())
+{
+j = 0;
+}
+if (points[k].GetY() == points[j].GetY())
+{
+j ++;
+}
+else
+{
+return points[j].GetY();
+}
+}
+}
+void ImageProcessing::FillPolygon(IPolygonFiller& filler,
+const std::vector<ImagePoint>& points)
+{
+/**
+* This implementation is a C++ adaption of Section 3.11 (pages
+* 117-124) of textbook "Computer Graphics - C Version (2nd
+* Edition)" by Hearn and Baker, 1997.
+**/
+typedef std::map<int, std::list<PolygonEdge> > EdgeTable;
+if (points.size() < 2)
+{
+return;
+}
+EdgeTable globalEdgeTable;
+// cf. "buildEdgeList()" in textbook
+int yPrev = points[points.size() - 2].GetY();
+ImagePoint v1(points[points.size() - 1]);
 for (size_t i = 0; i < points.size(); i++)
 {
-if (points[i].GetX() < 0 || points[i].GetX() >= imageWidth
+ImagePoint v2(points[i]);
-|| points[i].GetY() < 0 || points[i].GetY() >= imageHeight)
-{
+if (v1.GetY() < v2.GetY())
-throw OrthancException(ErrorCode_ParameterOutOfRange);
+{
-}
+// Up-going edge
-cpx.push_back((double)points[i].GetX());
+PolygonEdge edge(v1, v2, GetPolygonNextY(points, i));
-cpy.push_back((double)points[i].GetY());
+globalEdgeTable[v1.GetY()].push_back(edge);
 }
+else if (v1.GetY() > v2.GetY())
-// Draw the lines segments
+{
-for (size_t i = 0; i < (points.size() -1); i++)
+// Down-going edge
-{
+PolygonEdge edge(v2, v1, yPrev);
-ImageProcessing::DrawLineSegment(image, points[i].GetX(), points[i].GetY(), points[i+1].GetX(), points[i+1].GetY(), value_);
+globalEdgeTable[v2.GetY()].push_back(edge);
 }
-ImageProcessing::DrawLineSegment(image, points[points.size() -1].GetX(), points[points.size() -1].GetY(), points[0].GetX(), points[0].GetY(), value_);
+yPrev = v1.GetY();
-std::vector<int32_t> nodeX;
+v1 = v2;
-nodeX.resize(cpSize);
+}
-int  pixelX, pixelY, i, swap ;
+if (globalEdgeTable.empty())
-//  Loop through the rows of the image.
+{
-for (pixelY = top; pixelY < bottom; pixelY++)
+// Degenerate case: There were only horizontal lines
-{
+int x1 = points[0].GetX();
-double y = (double)pixelY;
+int x2 = points[0].GetX();
-//  Build a list of nodes.
+for (size_t i = 1; i < points.size(); i++)
-int nodes = 0;
+{
-int j = static_cast<int>(cpSize) - 1;
+assert(points[i].GetY() == points[0].GetY());
+x1 = std::min(x1, points[i].GetX());
-for (i = 0; i < static_cast<int>(cpSize); i++)
+x2 = std::max(x2, points[i].GetX());
-{
+}
-if ((cpy[i] < y && cpy[j] >=  y) || (cpy[j] < y && cpy[i] >= y))
+filler.Fill(points[0].GetY(), x1, x2);
-{
+return;
-nodeX[nodes++] = (int32_t)(cpx[i] + (y - cpy[i])/(cpy[j] - cpy[i]) * (cpx[j] - cpx[i]));
+}
-}
-j=i;
+std::vector<PolygonEdge> activeEdges;
-}
+for (EdgeTable::const_iterator it = globalEdgeTable.begin(); it != globalEdgeTable.end(); ++it)
-//  Sort the nodes, via a simple “Bubble” sort.
+{
-i=0;
+// cf. "buildActiveList()" in textbook
-while (i < nodes-1)
+activeEdges.reserve(activeEdges.size() + it->second.size());
-{
+for (std::list<PolygonEdge>::const_iterator it2 = it->second.begin(); it2 != it->second.end(); ++it2)
-if (nodeX[i] > nodeX[i+1])
+{
-{
+activeEdges.push_back(*it2);
-swap = nodeX[i];
+}
-nodeX[i] = nodeX[i+1];
-nodeX[i+1] = swap;
+assert(!activeEdges.empty());
-if (i > 0)
+EdgeTable::const_iterator next = it;
+++next;
+int rampEnd;
+if (next == globalEdgeTable.end())
+{
+rampEnd = activeEdges[0].GetUpperY() + 1;
+for (size_t i = 1; i < activeEdges.size(); i++)
+{
+rampEnd = std::max(rampEnd, activeEdges[0].GetUpperY() + 1);
+}
+}
+else
+{
+rampEnd = next->first;
+}
+for (int y = it->first; y < rampEnd; y++)
+{
+// cf. "updateActiveList()" in textbook
+std::vector<PolygonEdge> stillActive;
+stillActive.reserve(activeEdges.size());
+for (size_t i = 0; i < activeEdges.size(); i++)
+{
+if (y <= activeEdges[i].GetUpperY())
 {
-i--;
+stillActive.push_back(activeEdges[i]);
 }
 }
-else
-{
+activeEdges.swap(stillActive);
-i++;
+std::sort(activeEdges.begin(), activeEdges.end());
-}
-}
+// cf. "fillScan()" in textbook
+if (y >= 0)
-TargetType* row = reinterpret_cast<TargetType*>(image.GetRow(pixelY));
+{
-//  Fill the pixels between node pairs.
+for (size_t k = 0; k + 1 < activeEdges.size(); k += 2)
-for (i = 0; i < nodes; i += 2)
-{
-if (nodeX[i] >= right)
-break;
-if (nodeX[i + 1] >= left)
-{
-if (nodeX[i] < left)
 {
-nodeX[i] = left;
+int a = activeEdges[k].GetExitX();
+int b = activeEdges[k + 1].GetEnterX();
+filler.Fill(y, std::min(a, b), std::max(a, b));
 }
+}
-if (nodeX[i + 1] > right)
-{
+// cf. "updateActiveList()" in textbook
-nodeX[i + 1] = right;
+for (size_t k = 0; k < activeEdges.size(); k++)
-}
+{
+activeEdges[k].NextScanLine();
-for (pixelX = nodeX[i]; pixelX <= nodeX[i + 1]; pixelX++)
+}
-{
+}
-*(row + pixelX) = value;
+}
 }
-}
-}
-}
-}
 void ImageProcessing::FillPolygon(ImageAccessor& image,
 const std::vector<ImagePoint>& points,
 int64_t value)
 {
-switch (image.GetFormat())
+class Filler : public IPolygonFiller
 {
-case PixelFormat_Grayscale8:
+private:
-{
+ImageAccessor& image_;
-FillPolygon_<PixelFormat_Grayscale8>(image, points, value);
+int64_t        value_;
-break;
-}
+public:
-case PixelFormat_Grayscale16:
+Filler(ImageAccessor& image,
-{
+int64_t value) :
-FillPolygon_<PixelFormat_Grayscale16>(image, points, value);
+image_(image),
-break;
+value_(value)
-}
+{
-case PixelFormat_SignedGrayscale16:
+}
-{
-FillPolygon_<PixelFormat_SignedGrayscale16>(image, points, value);
+virtual void Fill(int y,
-break;
+int x1,
-}
+int x2) ORTHANC_OVERRIDE
-default:
+{
-throw OrthancException(ErrorCode_NotImplemented);
+assert(x1 <= x2);
+if (x1 < static_cast<int>(image_.GetWidth()) &&
+x2 >= 0 &&
+y >= 0 &&
+y < static_cast<int>(image_.GetHeight()))
+{
+unsigned int yy = static_cast<unsigned int>(y);
+unsigned int a = static_cast<unsigned int>(std::max(0, x1));
+unsigned int b = static_cast<unsigned int>(std::min(x2, static_cast<int>(image_.GetWidth()) - 1));
+assert(a <= b);
+ImageAccessor region;
+image_.GetRegion(region, a, yy, b - a + 1, 1);
+Set(region, value_);
+}
+}
+};
+if (image.GetFormat() == PixelFormat_Grayscale8 ||
+image.GetFormat() == PixelFormat_Grayscale16 ||
+image.GetFormat() == PixelFormat_SignedGrayscale16)
+{
+Filler filler(image, value);
+FillPolygon(filler, points);
+}
+else
+{
+throw OrthancException(ErrorCode_NotImplemented);
 }
 }
 template <PixelFormat Format>

Mercurial > hg > orthanc

comparison OrthancFramework/Sources/Images/ImageProcessing.cpp @ 4872:b1556cefa5c6