RasterTriangle.h

Go to the documentation of this file.

/*
 * Copyright (C) 2012 by
 *   MetraLabs GmbH (MLAB), GERMANY
 * and
 *   Neuroinformatics and Cognitive Robotics Labs (NICR) at TU Ilmenau, GERMANY
 * All rights reserved.
 *
 * Contact: info@mira-project.org
 *
 * Commercial Usage:
 *   Licensees holding valid commercial licenses may use this file in
 *   accordance with the commercial license agreement provided with the
 *   software or, alternatively, in accordance with the terms contained in
 *   a written agreement between you and MLAB or NICR.
 *
 * GNU General Public License Usage:
 *   Alternatively, this file may be used under the terms of the GNU
 *   General Public License version 3.0 as published by the Free Software
 *   Foundation and appearing in the file LICENSE.GPL3 included in the
 *   packaging of this file. Please review the following information to
 *   ensure the GNU General Public License version 3.0 requirements will be
 *   met: http://www.gnu.org/copyleft/gpl.html.
 *   Alternatively you may (at your option) use any later version of the GNU
 *   General Public License if such license has been publicly approved by
 *   MLAB and NICR (or its successors, if any).
 *
 * IN NO EVENT SHALL "MLAB" OR "NICR" BE LIABLE TO ANY PARTY FOR DIRECT,
 * INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF
 * THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF "MLAB" OR
 * "NICR" HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * "MLAB" AND "NICR" SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING,
 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND "MLAB" AND "NICR" HAVE NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS OR MODIFICATIONS.
 */

#ifndef _MIRA_RASTERTIRANGLE_H_
#define _MIRA_RASTERTIRANGLE_H_

#include <geometry/Bresenham.h>
#include <geometry/Polygon.h>
#include <error/Exceptions.h>

namespace mira {


namespace Private {


struct LeftVisitor {
    std::vector<int>& mP;
    LeftVisitor(std::vector<int>& p) : mP(p) {}
    void operator()(int x, int y, int length) {
        mP[y] = x;
    }
};

struct RightVisitor {
    std::vector<int>& mP;
    RightVisitor(std::vector<int>& p) : mP(p) {}
    void operator()(int x, int y, int length) {
        mP[y] = x+length-1;
    }
};

template<typename Visitor>
struct AdaptVisitor {
    Visitor&& v; // this can be an lvalue reference or rvalue reference depending on
                 // how the constructor is called (assuming type Visitor is deduced)
                 // in both cases, keeping a (l/rvalue) reference to visitor is ok as
                 // long as its lifetime does not end before ours!
                 // (e.g. we are created and directly used as param to a function call)
    AdaptVisitor(Visitor&& visitor) : v(std::forward<Visitor>(visitor)) {}
    void operator()(int x, int y, int length) {
        v(x, x+length-1, y);
    }
};


} // namespace Private {


template<typename Visitor>
inline void rasterTriangle(Point2i p0, Point2i p1, Point2i p2,
                           Visitor&& visitor)
{
    if(p1[1]<p0[1] || ((p1[1]==p0[1]) && (p1[0]<p0[0]))) {
        std::swap(p1[0], p0[0]);
        std::swap(p1[1], p0[1]);
    }

    if(p2[1]<p1[1] || ((p2[1]==p1[1]) && (p2[0]<p1[0]))) {
        std::swap(p2[0], p1[0]);
        std::swap(p2[1], p1[1]);
    }

    if(p1[1]<p0[1] || ((p1[1]==p0[1]) && (p1[0]<p0[0]))) {
        std::swap(p1[0], p0[0]);
        std::swap(p1[1], p0[1]);
    }

    // possible cases for the triangle

    // CASE 1:
    //    0
    //    |\.
    //    | \.
    //  p *  1
    //    | /
    //    |/
    //    2

    // CASE 2:
    //    0
    //   /|
    //  / |
    // 1  * p
    //  \ |
    //   \|
    //    2

    // compute the x-coordinate of p:
    int x0(p0[0]), x1(p1[0]), x2(p2[0]);
    int y0(p0[1]), y1(p1[1]), y2(p2[1]);

    const int dx01 = x1-x0;
    const int dy01 = y1-y0;

    const int dx02 = x2-x0;
    const int dy02 = y2-y0;

    // just raster a single line if all 3 points are on a straight line (for efficiency)
    if (dx01*dy02 == dx02*dy01) {
        bresenhamRunSlice(x0, y0, x2, y2, Private::AdaptVisitor<Visitor>(std::forward<Visitor>(visitor)));
        return;
    }

    assert(dy02!=0); // dy02 == 0 --> dy01 == 0 (because of sorting on y) -->  dx01*dy02 == dx02*dy01 (case above)

    float p = float(dx02 * dy01) / dy02 + x0;

    std::vector<int> left(dy02+1);
    std::vector<int> right(dy02+1);

    Private::LeftVisitor  leftVisitor(left);
    Private::RightVisitor rightVisitor(right);
    if(p <= x1) { // CASE 1:
        // left edge 0->2
        bresenhamRunSlice(x0, y0-y0, x2, y2-y0, leftVisitor);
        // right edge 0->1
        bresenhamRunSlice(x0, y0-y0, x1, y1-y0, rightVisitor);
        // right edge 1->2
        bresenhamRunSlice(x1, y1-y0, x2, y2-y0, rightVisitor);
    } else { // CASE 2:
        // left edge 0->1
        bresenhamRunSlice(x0, y0-y0, x1, y1-y0, leftVisitor);
        // left edge 1->2
        bresenhamRunSlice(x1, y1-y0, x2, y2-y0, leftVisitor);
        // right edge 0->2
        bresenhamRunSlice(x0, y0-y0, x2, y2-y0, rightVisitor);
    }

    for(int i=0; i<=dy02; ++i)
        visitor(left[i], right[i], i+y0);
}

template<typename Visitor>
inline void rasterTriangle(const Polygon2i& polygon, Visitor&& visitor)
{
    // only polygons with 3 points or 4 points are valid
    if((polygon.size() < 3)||(polygon.size() > 4))
    {
        throw XRuntime("Only polygons with 3 points and no inner rings are triangles");
    }

    auto pointIter = polygon.begin();

    Point2i A = *pointIter; pointIter++;
    Point2i B = *pointIter; pointIter++;
    Point2i C = *pointIter;

    rasterTriangle(A, B, C, visitor);
}


}

#endif