How to fill a triangle using lines?

Question

I'm trying to fill a triangle using horizontal lines and I can't figure out what's wrong with my current method. Before anyone says to just use fillPolygon, I can't use that. I need to fill it using lines. It seems to work ok in some situations and completely break in others.

That's how it should look. But then I tried applying my method to a rotating 3D cube and...

I have no idea what's wrong. Also, the red borders are also one of my triangle methods. Those work perfectly and the filled triangles and the outlined triangles have the same vertices inputted.

public void filledTri(int x1,int y1,int x2,int y2,int x3,int y3){
    int[] xs = {x1,x2,x3};
    int[] ys = {y1,y2,y3};
    //Sort vertices in vertical order so A/1 is highest and C/3 is lowest
    int I,tempx,tempy;
    for(int i=1;i<3;i++){
        I = i-1;
        tempx = xs[i];
        tempy = ys[i];
        while(I>=0&&tempy<ys[I]){
            xs[I+1] = xs[I];
            ys[I+1] = ys[I];
            I--;
        }
        xs[I+1] = tempx;
        ys[I+1] = tempy;
    }
    //Set left and right edges
    linepts ab = new linepts(xs[0],ys[0],xs[1],ys[1]),
    ac = new linepts(xs[0],ys[0],xs[2],ys[2]);
    linepts[] lines = {ab.getEndX() < ac.getEndX() ? ab : ac,
    ab.getEndX() > ac.getEndX() ? ab : ac,
    new linepts(xs[1],ys[1],xs[2],ys[2])};
    //Fill triangle
    int startY = ys[0],endY = ys[2];
    for(int y=startY;y<=endY;y++){
        if(y>ys[1])
        horizontalLine((int)Math.round(lines[2].getX(y)),
        y,
        (int)Math.round(lines[1].getX(y)));
        else
        horizontalLine((int)Math.round(lines[0].getX(y)),
        y,
        (int)Math.round(lines[1].getX(y)));
    }

getX(int y) gets me the x coordinate where the line passes through the y value. If it's a horizontal line it just returns the line's start x

Point A is the highest on screen and the lowest value, B is the middle, and C is the lowest on screen and highest value

I'm using a buffered image on a jframe to draw it if that helps.

Answer 1

I've seen what you are doing in a Software Renderer tutorial. It is explained in this and this episodes.

What he does there is scanning the longest to get every pixel on that line, it stores the min X value and max X value, (given by the other 2 lines). He originally makes it for specific triangles, but then he upgrades the code to accept generic triangles.

Here's a nice diagram to explain that:

I assume what you're experiencing is because of projecting 3D triangles into 2D ones (clipping, triangles get infinite coordinates, or because you're program doesn't takes too well empty triangles.

Answer 2

One way is to draw the lines to an image, then use that image in a TexturePaint to fill a Shape (the triangle in this case).

It might look something like this: (if you use a single image containing one red line, put it over a random BG color, and use a smoothed 1.5 pixel stroke to draw the shape itself in blue).

import java.awt.*;
import java.awt.geom.*;
import java.awt.image.BufferedImage;
import javax.swing.*;
import javax.swing.border.EmptyBorder;
import java.util.*;

public class LinesFillShape {

    private JComponent ui = null;

    LinesFillShape() {
        initUI();
    }

    public final void initUI() {
        if (ui != null) {
            return;
        }

        ui = new JPanel(new BorderLayout(4, 4));
        ui.setBorder(new EmptyBorder(4, 4, 4, 4));

        ui.add(new JLabel(new ImageIcon(getImage())));
    }

    private void drawPolygon(Graphics2D g, int sz, Random r) {
        int[] xpoints = {
            r.nextInt(sz), r.nextInt(sz), r.nextInt(sz)
        };
        int[] ypoints = {
            r.nextInt(sz), r.nextInt(sz), r.nextInt(sz)
        };
        Polygon p = new Polygon(xpoints, ypoints, 3);
        Color bg = new Color(r.nextInt(255),r.nextInt(255),r.nextInt(255));
        g.setColor(bg);
        g.fill(p);

        g.setPaint(
                new TexturePaint(getTexture(),
                        new Rectangle2D.Double(0, 0, 8, 8)));
        g.fill(p);
        g.setStroke(new BasicStroke(1.5f));
        g.setColor(Color.BLUE);
        g.draw(p);
    }

    private BufferedImage getImage() {
        int sz = 600;
        BufferedImage bi = new BufferedImage(sz, sz, BufferedImage.TYPE_INT_ARGB);
        Graphics2D g = bi.createGraphics();
        g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);

        Random r = new Random();
        drawPolygon(g, sz, r);
        drawPolygon(g, sz, r);
        drawPolygon(g, sz, r);

        g.dispose();
        return bi;
    }

    private BufferedImage getTexture() {
        BufferedImage bi = new BufferedImage(8, 8, BufferedImage.TYPE_INT_ARGB);
        Graphics g = bi.getGraphics();
        g.setColor(Color.RED);
        // TODO: something more interesting here.. 
        g.drawLine(0, 0, 0, 8);
        g.dispose();

        return bi;
    }

    public JComponent getUI() {
        return ui;
    }

    public static void main(String[] args) {
        Runnable r = () -> {
            try {
                UIManager.setLookAndFeel(
                        UIManager.getSystemLookAndFeelClassName());
            } catch (Exception useDefault) {
            }
            LinesFillShape o = new LinesFillShape();

            JFrame f = new JFrame(o.getClass().getSimpleName());
            f.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
            f.setLocationByPlatform(true);

            f.setContentPane(o.getUI());
            f.pack();
            f.setMinimumSize(f.getSize());

            f.setVisible(true);
        };
        SwingUtilities.invokeLater(r);
    }
}

Answer 3

I have not scrutinized your code but I can tell you that you are not always joining intersections with the relevant sides.

You can work as follows:

For a given scanline (some Y),

• compare the ordinates of the endpoints of the three sides in pairs (Y0-Y1, Y1-Y2, Y2-Y0),

• there will be zero or two sides that straddle Y; use the condition (Yi > Y) != (Yi+1 > Y) (indexes modulo 3), and no other,

• for the sides that straddle Y, compute the intersection point.

You will scan from min(Y0, Y1, Y2) to max(Y0, Y1, Y2) and each time join the two intersections.