Mercurial > hg > orthanc
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
4871:55469ccfb384 | 4872:b1556cefa5c6 |
---|---|
40 #pragma GCC diagnostic ignored "-Wimplicit-int-float-conversion" | 40 #pragma GCC diagnostic ignored "-Wimplicit-int-float-conversion" |
41 #endif | 41 #endif |
42 | 42 |
43 #include <boost/math/special_functions/round.hpp> | 43 #include <boost/math/special_functions/round.hpp> |
44 | 44 |
45 #include <algorithm> | |
45 #include <cassert> | 46 #include <cassert> |
47 #include <limits> | |
48 #include <list> | |
49 #include <map> | |
50 #include <stdint.h> | |
46 #include <string.h> | 51 #include <string.h> |
47 #include <limits> | |
48 #include <stdint.h> | |
49 #include <algorithm> | |
50 | 52 |
51 namespace Orthanc | 53 namespace Orthanc |
52 { | 54 { |
53 ImageProcessing::ImagePoint::ImagePoint(int32_t x, | 55 ImageProcessing::ImagePoint::ImagePoint(int32_t x, |
54 int32_t y) : | 56 int32_t y) : |
1858 bottom = std::max(p.GetY(), bottom); | 1860 bottom = std::max(p.GetY(), bottom); |
1859 top = std::min(p.GetY(), top); | 1861 top = std::min(p.GetY(), top); |
1860 } | 1862 } |
1861 } | 1863 } |
1862 | 1864 |
1863 template <PixelFormat TargetFormat> | 1865 |
1864 void FillPolygon_(ImageAccessor& image, | 1866 namespace |
1865 const std::vector<ImageProcessing::ImagePoint>& points, | 1867 { |
1866 int64_t value_) | 1868 #define USE_POLYGON_FRACTIONS 1 |
1867 { | 1869 |
1868 typedef typename PixelTraits<TargetFormat>::PixelType TargetType; | 1870 class PolygonEdge |
1869 | 1871 { |
1870 TargetType value = PixelTraits<TargetFormat>::IntegerToPixel(value_); | 1872 private: |
1871 int imageWidth = static_cast<int>(image.GetWidth()); | 1873 int yUpper; |
1872 int imageHeight = static_cast<int>(image.GetHeight()); | 1874 |
1873 int32_t left; | 1875 #if USE_POLYGON_FRACTIONS == 1 |
1874 int32_t right; | 1876 int x; |
1875 int32_t top; | 1877 int xOffset; |
1876 int32_t bottom; | 1878 int dxPerScanNumerator; |
1877 | 1879 int dxPerScanDenominator; |
1878 // TODO: test clipping in UT (in Trello board) | 1880 #else |
1879 ComputePolygonExtent(left, right, top, bottom, points); | 1881 float xIntersect; |
1880 | 1882 float dxPerScan; |
1881 // clip the computed extent with the target image | 1883 #endif |
1882 // L and R | 1884 |
1883 left = std::max(0, left); | 1885 public: |
1884 left = std::min(imageWidth, left); | 1886 PolygonEdge(const ImageProcessing::ImagePoint& lower, |
1885 right = std::max(0, right); | 1887 const ImageProcessing::ImagePoint& upper, |
1886 right = std::min(imageWidth, right); | 1888 int yComp) |
1887 if (left > right) | 1889 { |
1888 std::swap(left, right); | 1890 // cf. "makeEdgeRec()" in textbook |
1889 | 1891 |
1890 // T and B | 1892 assert(upper.GetY() != lower.GetY()); |
1891 top = std::max(0, top); | 1893 |
1892 top = std::min(imageHeight, top); | 1894 #if USE_POLYGON_FRACTIONS == 1 |
1893 bottom = std::max(0, bottom); | 1895 x = lower.GetX(); |
1894 bottom = std::min(imageHeight, bottom); | 1896 xOffset = 0; |
1895 if (top > bottom) | 1897 dxPerScanNumerator = upper.GetX() - lower.GetX(); |
1896 std::swap(top, bottom); | 1898 dxPerScanDenominator = upper.GetY() - lower.GetY(); |
1897 | 1899 #else |
1898 // from http://alienryderflex.com/polygon_fill/ | 1900 dxPerScan = (static_cast<float>(upper.GetX() - lower.GetX()) / |
1899 | 1901 static_cast<float>(upper.GetY() - lower.GetY())); |
1900 // convert all "corner" points to double only once | 1902 xIntersect = lower.GetX(); |
1901 std::vector<double> cpx; | 1903 #endif |
1902 std::vector<double> cpy; | 1904 |
1903 size_t cpSize = points.size(); | 1905 if (upper.GetY() < yComp) |
1906 { | |
1907 yUpper = upper.GetY() - 1; | |
1908 } | |
1909 else | |
1910 { | |
1911 yUpper = upper.GetY(); | |
1912 } | |
1913 } | |
1914 | |
1915 float GetActualX() const | |
1916 { | |
1917 #if USE_POLYGON_FRACTIONS == 1 | |
1918 return (static_cast<float>(x) + | |
1919 static_cast<float>(xOffset) / | |
1920 static_cast<float>(dxPerScanDenominator)); | |
1921 #else | |
1922 return xIntersect; | |
1923 #endif | |
1924 } | |
1925 | |
1926 void NextScanLine() | |
1927 { | |
1928 #if USE_POLYGON_FRACTIONS == 1 | |
1929 xOffset += dxPerScanNumerator; | |
1930 | |
1931 while (xOffset >= dxPerScanDenominator) | |
1932 { | |
1933 x++; | |
1934 xOffset -= dxPerScanDenominator; | |
1935 } | |
1936 | |
1937 while (xOffset < 0) | |
1938 { | |
1939 x--; | |
1940 xOffset += dxPerScanDenominator; | |
1941 } | |
1942 | |
1943 #else | |
1944 xIntersect += dxPerScan; | |
1945 #endif | |
1946 } | |
1947 | |
1948 | |
1949 int GetEnterX() const | |
1950 { | |
1951 #if USE_POLYGON_FRACTIONS == 1 | |
1952 assert(xOffset >= 0 && xOffset < dxPerScanDenominator); | |
1953 if (xOffset == 0) | |
1954 { | |
1955 return x; | |
1956 } | |
1957 else | |
1958 { | |
1959 return x + 1; | |
1960 } | |
1961 #else | |
1962 return std::ceil(GetActualX()); // TODO | |
1963 #endif | |
1964 } | |
1965 | |
1966 int GetExitX() const | |
1967 { | |
1968 #if USE_POLYGON_FRACTIONS == 1 | |
1969 assert(xOffset >= 0 && xOffset < dxPerScanDenominator); | |
1970 return x; | |
1971 #else | |
1972 return std::floor(GetActualX()); // TODO | |
1973 #endif | |
1974 } | |
1975 | |
1976 int GetUpperY() const | |
1977 { | |
1978 return yUpper; | |
1979 } | |
1980 | |
1981 bool operator< (const PolygonEdge& other) const | |
1982 { | |
1983 // cf. "insertEdge()" in textbook | |
1984 return (GetActualX() < other.GetActualX()); | |
1985 } | |
1986 }; | |
1987 } | |
1988 | |
1989 | |
1990 // For an index, return y-coordinate of next nonhorizontal line | |
1991 static size_t GetPolygonNextY(const std::vector<ImageProcessing::ImagePoint>& points, | |
1992 size_t k) | |
1993 { | |
1994 // cf. "yNext()" in textbook | |
1995 size_t j = k + 1; | |
1996 | |
1997 for (;;) | |
1998 { | |
1999 if (j >= points.size()) | |
2000 { | |
2001 j = 0; | |
2002 } | |
2003 | |
2004 if (points[k].GetY() == points[j].GetY()) | |
2005 { | |
2006 j ++; | |
2007 } | |
2008 else | |
2009 { | |
2010 return points[j].GetY(); | |
2011 } | |
2012 } | |
2013 } | |
2014 | |
2015 | |
2016 | |
2017 void ImageProcessing::FillPolygon(IPolygonFiller& filler, | |
2018 const std::vector<ImagePoint>& points) | |
2019 { | |
2020 /** | |
2021 * This implementation is a C++ adaption of Section 3.11 (pages | |
2022 * 117-124) of textbook "Computer Graphics - C Version (2nd | |
2023 * Edition)" by Hearn and Baker, 1997. | |
2024 **/ | |
2025 | |
2026 typedef std::map<int, std::list<PolygonEdge> > EdgeTable; | |
2027 | |
2028 if (points.size() < 2) | |
2029 { | |
2030 return; | |
2031 } | |
2032 | |
2033 EdgeTable globalEdgeTable; | |
2034 | |
2035 // cf. "buildEdgeList()" in textbook | |
2036 int yPrev = points[points.size() - 2].GetY(); | |
2037 ImagePoint v1(points[points.size() - 1]); | |
2038 | |
1904 for (size_t i = 0; i < points.size(); i++) | 2039 for (size_t i = 0; i < points.size(); i++) |
1905 { | 2040 { |
1906 if (points[i].GetX() < 0 || points[i].GetX() >= imageWidth | 2041 ImagePoint v2(points[i]); |
1907 || points[i].GetY() < 0 || points[i].GetY() >= imageHeight) | 2042 |
1908 { | 2043 if (v1.GetY() < v2.GetY()) |
1909 throw OrthancException(ErrorCode_ParameterOutOfRange); | 2044 { |
1910 } | 2045 // Up-going edge |
1911 cpx.push_back((double)points[i].GetX()); | 2046 PolygonEdge edge(v1, v2, GetPolygonNextY(points, i)); |
1912 cpy.push_back((double)points[i].GetY()); | 2047 globalEdgeTable[v1.GetY()].push_back(edge); |
1913 } | 2048 } |
1914 | 2049 else if (v1.GetY() > v2.GetY()) |
1915 // Draw the lines segments | 2050 { |
1916 for (size_t i = 0; i < (points.size() -1); i++) | 2051 // Down-going edge |
1917 { | 2052 PolygonEdge edge(v2, v1, yPrev); |
1918 ImageProcessing::DrawLineSegment(image, points[i].GetX(), points[i].GetY(), points[i+1].GetX(), points[i+1].GetY(), value_); | 2053 globalEdgeTable[v2.GetY()].push_back(edge); |
1919 } | 2054 } |
1920 ImageProcessing::DrawLineSegment(image, points[points.size() -1].GetX(), points[points.size() -1].GetY(), points[0].GetX(), points[0].GetY(), value_); | 2055 |
1921 | 2056 yPrev = v1.GetY(); |
1922 std::vector<int32_t> nodeX; | 2057 v1 = v2; |
1923 nodeX.resize(cpSize); | 2058 } |
1924 int pixelX, pixelY, i, swap ; | 2059 |
1925 | 2060 if (globalEdgeTable.empty()) |
1926 // Loop through the rows of the image. | 2061 { |
1927 for (pixelY = top; pixelY < bottom; pixelY++) | 2062 // Degenerate case: There were only horizontal lines |
1928 { | 2063 int x1 = points[0].GetX(); |
1929 double y = (double)pixelY; | 2064 int x2 = points[0].GetX(); |
1930 // Build a list of nodes. | 2065 for (size_t i = 1; i < points.size(); i++) |
1931 int nodes = 0; | 2066 { |
1932 int j = static_cast<int>(cpSize) - 1; | 2067 assert(points[i].GetY() == points[0].GetY()); |
1933 | 2068 x1 = std::min(x1, points[i].GetX()); |
1934 for (i = 0; i < static_cast<int>(cpSize); i++) | 2069 x2 = std::max(x2, points[i].GetX()); |
1935 { | 2070 } |
1936 if ((cpy[i] < y && cpy[j] >= y) || (cpy[j] < y && cpy[i] >= y)) | 2071 filler.Fill(points[0].GetY(), x1, x2); |
1937 { | 2072 return; |
1938 nodeX[nodes++] = (int32_t)(cpx[i] + (y - cpy[i])/(cpy[j] - cpy[i]) * (cpx[j] - cpx[i])); | 2073 } |
1939 } | 2074 |
1940 j=i; | 2075 std::vector<PolygonEdge> activeEdges; |
1941 } | 2076 |
1942 | 2077 for (EdgeTable::const_iterator it = globalEdgeTable.begin(); it != globalEdgeTable.end(); ++it) |
1943 // Sort the nodes, via a simple “Bubble” sort. | 2078 { |
1944 i=0; | 2079 // cf. "buildActiveList()" in textbook |
1945 while (i < nodes-1) | 2080 activeEdges.reserve(activeEdges.size() + it->second.size()); |
1946 { | 2081 for (std::list<PolygonEdge>::const_iterator it2 = it->second.begin(); it2 != it->second.end(); ++it2) |
1947 if (nodeX[i] > nodeX[i+1]) | 2082 { |
1948 { | 2083 activeEdges.push_back(*it2); |
1949 swap = nodeX[i]; | 2084 } |
1950 nodeX[i] = nodeX[i+1]; | 2085 |
1951 nodeX[i+1] = swap; | 2086 assert(!activeEdges.empty()); |
1952 if (i > 0) | 2087 |
2088 EdgeTable::const_iterator next = it; | |
2089 ++next; | |
2090 | |
2091 int rampEnd; | |
2092 if (next == globalEdgeTable.end()) | |
2093 { | |
2094 rampEnd = activeEdges[0].GetUpperY() + 1; | |
2095 | |
2096 for (size_t i = 1; i < activeEdges.size(); i++) | |
2097 { | |
2098 rampEnd = std::max(rampEnd, activeEdges[0].GetUpperY() + 1); | |
2099 } | |
2100 } | |
2101 else | |
2102 { | |
2103 rampEnd = next->first; | |
2104 } | |
2105 | |
2106 for (int y = it->first; y < rampEnd; y++) | |
2107 { | |
2108 // cf. "updateActiveList()" in textbook | |
2109 std::vector<PolygonEdge> stillActive; | |
2110 stillActive.reserve(activeEdges.size()); | |
2111 | |
2112 for (size_t i = 0; i < activeEdges.size(); i++) | |
2113 { | |
2114 if (y <= activeEdges[i].GetUpperY()) | |
1953 { | 2115 { |
1954 i--; | 2116 stillActive.push_back(activeEdges[i]); |
1955 } | 2117 } |
1956 } | 2118 } |
1957 else | 2119 |
1958 { | 2120 activeEdges.swap(stillActive); |
1959 i++; | 2121 std::sort(activeEdges.begin(), activeEdges.end()); |
1960 } | 2122 |
1961 } | 2123 // cf. "fillScan()" in textbook |
1962 | 2124 if (y >= 0) |
1963 TargetType* row = reinterpret_cast<TargetType*>(image.GetRow(pixelY)); | 2125 { |
1964 // Fill the pixels between node pairs. | 2126 for (size_t k = 0; k + 1 < activeEdges.size(); k += 2) |
1965 for (i = 0; i < nodes; i += 2) | |
1966 { | |
1967 if (nodeX[i] >= right) | |
1968 break; | |
1969 | |
1970 if (nodeX[i + 1] >= left) | |
1971 { | |
1972 if (nodeX[i] < left) | |
1973 { | 2127 { |
1974 nodeX[i] = left; | 2128 int a = activeEdges[k].GetExitX(); |
2129 int b = activeEdges[k + 1].GetEnterX(); | |
2130 filler.Fill(y, std::min(a, b), std::max(a, b)); | |
1975 } | 2131 } |
1976 | 2132 } |
1977 if (nodeX[i + 1] > right) | 2133 |
1978 { | 2134 // cf. "updateActiveList()" in textbook |
1979 nodeX[i + 1] = right; | 2135 for (size_t k = 0; k < activeEdges.size(); k++) |
1980 } | 2136 { |
1981 | 2137 activeEdges[k].NextScanLine(); |
1982 for (pixelX = nodeX[i]; pixelX <= nodeX[i + 1]; pixelX++) | 2138 } |
1983 { | 2139 } |
1984 *(row + pixelX) = value; | 2140 } |
1985 } | 2141 } |
1986 } | 2142 |
1987 } | 2143 |
1988 } | |
1989 } | |
1990 | |
1991 void ImageProcessing::FillPolygon(ImageAccessor& image, | 2144 void ImageProcessing::FillPolygon(ImageAccessor& image, |
1992 const std::vector<ImagePoint>& points, | 2145 const std::vector<ImagePoint>& points, |
1993 int64_t value) | 2146 int64_t value) |
1994 { | 2147 { |
1995 switch (image.GetFormat()) | 2148 class Filler : public IPolygonFiller |
1996 { | 2149 { |
1997 case PixelFormat_Grayscale8: | 2150 private: |
1998 { | 2151 ImageAccessor& image_; |
1999 FillPolygon_<PixelFormat_Grayscale8>(image, points, value); | 2152 int64_t value_; |
2000 break; | 2153 |
2001 } | 2154 public: |
2002 case PixelFormat_Grayscale16: | 2155 Filler(ImageAccessor& image, |
2003 { | 2156 int64_t value) : |
2004 FillPolygon_<PixelFormat_Grayscale16>(image, points, value); | 2157 image_(image), |
2005 break; | 2158 value_(value) |
2006 } | 2159 { |
2007 case PixelFormat_SignedGrayscale16: | 2160 } |
2008 { | 2161 |
2009 FillPolygon_<PixelFormat_SignedGrayscale16>(image, points, value); | 2162 virtual void Fill(int y, |
2010 break; | 2163 int x1, |
2011 } | 2164 int x2) ORTHANC_OVERRIDE |
2012 default: | 2165 { |
2013 throw OrthancException(ErrorCode_NotImplemented); | 2166 assert(x1 <= x2); |
2167 | |
2168 if (x1 < static_cast<int>(image_.GetWidth()) && | |
2169 x2 >= 0 && | |
2170 y >= 0 && | |
2171 y < static_cast<int>(image_.GetHeight())) | |
2172 { | |
2173 unsigned int yy = static_cast<unsigned int>(y); | |
2174 unsigned int a = static_cast<unsigned int>(std::max(0, x1)); | |
2175 unsigned int b = static_cast<unsigned int>(std::min(x2, static_cast<int>(image_.GetWidth()) - 1)); | |
2176 | |
2177 assert(a <= b); | |
2178 | |
2179 ImageAccessor region; | |
2180 image_.GetRegion(region, a, yy, b - a + 1, 1); | |
2181 Set(region, value_); | |
2182 } | |
2183 } | |
2184 }; | |
2185 | |
2186 | |
2187 if (image.GetFormat() == PixelFormat_Grayscale8 || | |
2188 image.GetFormat() == PixelFormat_Grayscale16 || | |
2189 image.GetFormat() == PixelFormat_SignedGrayscale16) | |
2190 { | |
2191 Filler filler(image, value); | |
2192 FillPolygon(filler, points); | |
2193 } | |
2194 else | |
2195 { | |
2196 throw OrthancException(ErrorCode_NotImplemented); | |
2014 } | 2197 } |
2015 } | 2198 } |
2016 | 2199 |
2017 | 2200 |
2018 template <PixelFormat Format> | 2201 template <PixelFormat Format> |