Mercurial > hg > orthanc

comparison OrthancFramework/Sources/Images/ImageProcessing.cpp @ 4874:bee6da5155dc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix polygon filling
author Sebastien Jodogne <s.jodogne@gmail.com>
date Tue, 18 Jan 2022 13:04:47 +0100
parents d68dbe6590ce
children 5dae41084ab7
comparison
equal deleted inserted replaced
4873:d68dbe6590ce 4874:bee6da5155dc
1910 { 1910 {
1911 yUpper = upper.GetY(); 1911 yUpper = upper.GetY();
1912 } 1912 }
1913 } 1913 }
1914 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() 1915 void NextScanLine()
1927 { 1916 {
1928 #if USE_POLYGON_FRACTIONS == 1 1917 #if USE_POLYGON_FRACTIONS == 1
1929 xOffset += dxPerScanNumerator; 1918 xOffset += dxPerScanNumerator;
1930 1919
1957 else 1946 else
1958 { 1947 {
1959 return x + 1; 1948 return x + 1;
1960 } 1949 }
1961 #else 1950 #else
1962 return std::ceil(GetActualX()); // TODO 1951 return static_cast<int>(std::ceil(xIntersect));
1963 #endif 1952 #endif
1964 } 1953 }
1965 1954
1966 int GetExitX() const 1955 int GetExitX() const
1967 { 1956 {
1968 #if USE_POLYGON_FRACTIONS == 1 1957 #if USE_POLYGON_FRACTIONS == 1
1969 assert(xOffset >= 0 && xOffset < dxPerScanDenominator); 1958 assert(xOffset >= 0 && xOffset < dxPerScanDenominator);
1970 return x; 1959 return x;
1971 #else 1960 #else
1972 return std::floor(GetActualX()); // TODO 1961 return static_cast<int>(std::floor(xIntersect));
1973 #endif 1962 #endif
1974 } 1963 }
1975 1964
1976 int GetUpperY() const 1965 int GetUpperY() const
1977 { 1966 {
1978 return yUpper; 1967 return yUpper;
1979 } 1968 }
1980 1969
1981 bool operator< (const PolygonEdge& other) const 1970 bool operator< (const PolygonEdge& other) const
1982 { 1971 {
1972 #if USE_POLYGON_FRACTIONS == 1
1973 assert(xOffset >= 0 && xOffset < dxPerScanDenominator);
1974 assert(other.xOffset >= 0 && other.xOffset < other.dxPerScanDenominator);
1975 return x < other.x;
1976 #else
1983 // cf. "insertEdge()" in textbook 1977 // cf. "insertEdge()" in textbook
1984 return (GetActualX() < other.GetActualX()); 1978 return (xIntersect < other.xIntersect);
1979 #endif
1985 } 1980 }
1986 }; 1981 };
1987 } 1982 }
1988 1983
1989 1984
1990 // For an index, return y-coordinate of next nonhorizontal line 1985 // For an index, return y-coordinate of next nonhorizontal line
1991 static size_t GetPolygonNextY(const std::vector<ImageProcessing::ImagePoint>& points, 1986 static size_t GetPolygonNextY(const std::vector<ImageProcessing::ImagePoint>& points,
1992 size_t k) 1987 size_t k)
1993 { 1988 {
1994 // cf. "yNext()" in textbook 1989 // cf. "yNext()" in textbook
1995 size_t j = k + 1; 1990 size_t j = k;
1996 1991
1997 for (;;) 1992 for (;;)
1998 { 1993 {
1999 if (j >= points.size()) 1994 j++;
1995 if (j == points.size())
2000 { 1996 {
2001 j = 0; 1997 j = 0;
2002 } 1998 }
2003 1999
2004 if (points[k].GetY() == points[j].GetY()) 2000 if (points[k].GetY() != points[j].GetY())
2005 { 2001 {
2006 j ++; 2002 return points[j].GetY();
2003 }
2004 }
2005 }
2006
2007
2008 static size_t GetPolygonPreviousY(const std::vector<ImageProcessing::ImagePoint>& points,
2009 size_t k)
2010 {
2011 size_t j = k;
2012
2013 for (;;)
2014 {
2015 if (j > 0)
2016 {
2017 j --;
2007 } 2018 }
2008 else 2019 else
2009 { 2020 {
2021 j = points.size() - 1;
2022 }
2023
2024 if (points[k].GetY() != points[j].GetY())
2025 {
2010 return points[j].GetY(); 2026 return points[j].GetY();
2011 } 2027 }
2012 } 2028 }
2013 } 2029 }
2014 2030
2015 2031
2016 2032
2017 void ImageProcessing::FillPolygon(IPolygonFiller& filler, 2033 void ImageProcessing::FillPolygon(IPolygonFiller& filler,
2018 const std::vector<ImagePoint>& points) 2034 const std::vector<ImagePoint>& points)
2019 { 2035 {
2020 /** 2036 /**
2021 * This implementation is a C++ adaption of Section 3.11 (pages 2037 * This implementation is a C++ adaption of Section 3.11 (pages
2031 } 2047 }
2032 2048
2033 EdgeTable globalEdgeTable; 2049 EdgeTable globalEdgeTable;
2034 2050
2035 // cf. "buildEdgeList()" in textbook 2051 // cf. "buildEdgeList()" in textbook
2036 int yPrev = points[points.size() - 2].GetY(); 2052
2053 // Error in the textbook: we use "GetPolygonPreviousY()" instead of "points.size() - 2"
2054 int yPrev = GetPolygonPreviousY(points, points.size() - 1);
2037 ImagePoint v1(points[points.size() - 1]); 2055 ImagePoint v1(points[points.size() - 1]);
2038 2056
2039 for (size_t i = 0; i < points.size(); i++) 2057 for (size_t i = 0; i < points.size(); i++)
2040 { 2058 {
2041 ImagePoint v2(points[i]); 2059 ImagePoint v2(points[i]);
2042 2060
2043 if (v1.GetY() < v2.GetY()) 2061 if (v1.GetY() != v2.GetY())
2044 { 2062 {
2045 // Up-going edge 2063 // Non-horizontal line
2046 PolygonEdge edge(v1, v2, GetPolygonNextY(points, i)); 2064 if (v1.GetY() < v2.GetY())
2047 globalEdgeTable[v1.GetY()].push_back(edge); 2065 {
2048 } 2066 // Up-going edge
2049 else if (v1.GetY() > v2.GetY()) 2067 PolygonEdge edge(v1, v2, GetPolygonNextY(points, i));
2050 { 2068 globalEdgeTable[v1.GetY()].push_back(edge);
2051 // Down-going edge 2069 }
2052 PolygonEdge edge(v2, v1, yPrev); 2070 else if (v1.GetY() > v2.GetY())
2053 globalEdgeTable[v2.GetY()].push_back(edge); 2071 {
2054 } 2072 // Down-going edge
2055 2073 PolygonEdge edge(v2, v1, yPrev);
2056 yPrev = v1.GetY(); 2074 globalEdgeTable[v2.GetY()].push_back(edge);
2075 }
2076
2077 // Error in the textbook: "yPrev" must NOT be updated on horizontal lines
2078 yPrev = v1.GetY();
2079 }
2080
2057 v1 = v2; 2081 v1 = v2;
2058 } 2082 }
2059 2083
2060 if (globalEdgeTable.empty()) 2084 if (globalEdgeTable.empty())
2061 { 2085 {
2062 // Degenerate case: There were only horizontal lines 2086 // Degenerate case: There were only horizontal lines
2063 int x1 = points[0].GetX(); 2087 int x1 = points[0].GetX();
2064 int x2 = points[0].GetX(); 2088 int x2 = points[0].GetX();
2116 stillActive.push_back(activeEdges[i]); 2140 stillActive.push_back(activeEdges[i]);
2117 } 2141 }
2118 } 2142 }
2119 2143
2120 activeEdges.swap(stillActive); 2144 activeEdges.swap(stillActive);
2145
2146 assert(activeEdges.size() % 2 == 0);
2121 std::sort(activeEdges.begin(), activeEdges.end()); 2147 std::sort(activeEdges.begin(), activeEdges.end());
2122 2148
2123 // cf. "fillScan()" in textbook 2149 // cf. "fillScan()" in textbook
2124 for (size_t k = 0; k + 1 < activeEdges.size(); k += 2) 2150 for (size_t k = 0; k + 1 < activeEdges.size(); k += 2)
2125 { 2151 {