Creating Triangles

[George]

I have a problem creating triangles with this program it creates
rectangles and squares but not triangles. For example I would like to
create a triangle with the vertices (1,1), (31,1), (31,31) and have it
be the color red. Here is the code your insights will be very helpful
thanks a lot.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct Pixel {
unsigned char R, G, B; // Red, Green, Blue
};

class ColorImage {
Pixel *pPixel;
int xRes, yRes;
public:
ColorImage();
~ColorImage();
void init(int xSize, int ySize);
void clear(Pixel background);
Pixel readPixel(int x, int y);
void writePixel(int x, int y, Pixel p);
void outputPPM(char *filename);
};

ColorImage::ColorImage()
{
pPixel = 0;
}

ColorImage::~ColorImage()
{
if (pPixel) delete[] pPixel;
pPixel = 0;
}

void ColorImage::init(int xSize, int ySize)
{
Pixel p = {0,0,0};
xRes = xSize;
yRes = ySize;
pPixel = new Pixel[xSize*ySize];
clear(p);
}

void ColorImage::clear(Pixel background)
{
int i;

if (! pPixel) return;
for (i=0; i<xRes*yRes; i++) pPixel = background;
}

Pixel ColorImage::readPixel(int x, int y)
{
assert(pPixel); // die if image not initialized
return pPixel[x + y*yRes];
}

void ColorImage::writePixel(int x, int y, Pixel p)
{
assert(pPixel); // die if image not initialized
pPixel[x + y*yRes] = p;
}

void ColorImage:utputPPM(char *filename)
{
FILE *outFile = fopen(filename, "wb");

assert(outFile); // die if file can't be opened

fprintf(outFile, "P6 %d %d 255\n", xRes, yRes);
fwrite(pPixel, 1, 3*xRes*yRes, outFile );

fclose(outFile);
}

// A test program that generates varying shades of reds.
int main(int argc, char* argv[])
{
ColorImage image;
int x, y;
Pixel p={0,0,0};

image.init(512, 512);
for (y=0; y<300; y++) {
for (x=0; x<30; x++) {
p.R = y;
image.writePixel(x, y, p);
}
}

image.outputPPM("reds.ppm");
return 0;
}

 

[Victor Bazarov]

I have a problem creating triangles with this program it creates
rectangles and squares but not triangles. For example I would like to
create a triangle with the vertices (1,1), (31,1), (31,31) and have it
be the color red. Here is the code your insights will be very helpful
thanks a lot.

Here is some insight: start by trying to create a triangle throught
(1,1) - (3,3) - (1,3). What does it mean? Draw it on a piece of
graph paper. Which pixels need to be colored and why? Then change
it to (1,1) - (3,4) - (1,4). What is different? If that is too
difficult, start with (1,1) - (2,1) - (1,2). Then move the two
last vertices farther out. Then try to come up with a general
approach.

BTW, this is not a C++ langauge question, it's a matter of coming
up with an algorithm. Once you have the algorithm, come back, and
we'll help you translate it into C++.

V

 

[George]

I have this algorithm and have tried to work it into my code but am
unable to grasp exactly what I should do. I get lost and delete
everything and try again and again. Could someone help me incorporate
this algorithm into my code thanks a lot.

alg:

void ScanTriangle(Traingle T, Pixel p)
{
for each pair
{
initialize xl, xr;
compute dxl/dyl and dxr/dyr;
for each scanline at y
for(int x=xl;x<=xr;x++)
SetPixel(x,y,p);
xl+=dxl/dyl;
xr+=dxr/dyr;
}
}

ps this is using the code in the beginning of this post thanks a lot.

 

[John Harrison]

I have this algorithm and have tried to work it into my code but am
unable to grasp exactly what I should do. I get lost and delete
everything and try again and again. Could someone help me incorporate
this algorithm into my code thanks a lot.

alg:

void ScanTriangle(Traingle T, Pixel p)
{
for each pair

For each pair of what?

{
initialize xl, xr;

xl and xr are what? Left and right?

compute dxl/dyl and dxr/dyr;

Where did dxl, dxr, dyl and dyr come from?

for each scanline at y
for(int x=xl;x<=xr;x++)
SetPixel(x,y,p);

The above three lines look like a rectangle to me

xl+=dxl/dyl;
xr+=dxr/dyr;

I give up.

}
}

ps this is using the code in the beginning of this post thanks a lot.

The above is not an algorithm it is a meaningless piece of pseudo-code
that (probably) would draw a rectangle anyway.

The first thing you need for an algorithm is some inputs, in your case
the imputs would tell you where the triangle is going to be drawn (and
maybe some other stuff like what colour it would be). So think first
about the inputs to the algorithm.

Now I'm going to take a guess and assume that you specify the triangle
as four numbers, xleft, xright, ytop, and ybottom. The first two are
x-coordinates and the last two are y-coordinates. If you drew every
pixel between those coordinates you would get a rectangle.

Here's the start of an algorithm.

void DrawTriangle(int xleft, int xright, int ytop, int ybottom)
{
for (int x = xleft; x <= xright; ++x)
{
for (int y = ytop; y <= ybottom; ++y)
{
if (x, y) is inside the triangle
draw pixel
}
}
}

Now the only bit you have to solve is how to tell if the (x, y) point is
insode the triangle or not. That is the whole point of the exercise you
have been given, the rest is just distraction. Try drawing xleft,
xright, ytop, ybottom on a piece of paper, then draw where you want the
traingle to be, and then see if you can work out what the formula is for
telling whether a point (x, y) is inside the triangle or not.

john

 

[Jim Langston]

I have a problem creating triangles with this program it creates
rectangles and squares but not triangles. For example I would like to
create a triangle with the vertices (1,1), (31,1), (31,31) and have it
be the color red. Here is the code your insights will be very helpful
thanks a lot.

[code snipped]

(1,1), (31,1), (31,1). something like this:

xxxxxxxxxxx
xxxxxxxxx
xxxxxxx
xxxx
x

?

First think about a for loop to draw the above.
Notice each row doesnt' start at 1, but one more over.
Easy to do when you can hard code the coordinates and figure it out before
hand.

Not so easy to do when the values are arbitrary (user input).

 

[Howard]

For each pair of what?


xl and xr are what? Left and right?

Left and right endpoints of a given "scan line", which is one horizontal
line in the triangle.

Where did dxl, dxr, dyl and dyr come from?

He just said... compute them! Those describe the slopes of the left and
right lines which border the triangle. If you need to know, they're the
difference in x and y between the top and bottom of each of the left and
right lines that define the triangle. Not so hard to figure out, (if you
recognize the algorithm being described).

The above three lines look like a rectangle to me


I give up.

The above two lines of code are intended to be within the "for x" loop
above. They modify the endpoints of the horizontal line to be drawn at each
y position, using the slope formula for the left and right edges of the
triangle. That gives you the new enpoints of the line at the following y
position. (But care needs to be taken here, because divisions like this
imply floating-point operations, while the resulting left and right x
potisions must be integers. Some rounding scheme is appropriate, which is
dependant on how you decide to relate your pixel display to the real world.)

The above is not an algorithm it is a meaningless piece of pseudo-code
that (probably) would draw a rectangle anyway.

Not if the loop contains those two lines. (And what's so wrong with using
pseudo-code to describe an algorithm?)

The first thing you need for an algorithm is some inputs, in your case the
imputs would tell you where the triangle is going to be drawn (and maybe
some other stuff like what colour it would be). So think first about the
inputs to the algorithm.

Now I'm going to take a guess and assume that you specify the triangle as
four numbers, xleft, xright, ytop, and ybottom. The first two are
x-coordinates and the last two are y-coordinates. If you drew every pixel
between those coordinates you would get a rectangle.

Here's the start of an algorithm.

void DrawTriangle(int xleft, int xright, int ytop, int ybottom)
{
for (int x = xleft; x <= xright; ++x)
{
for (int y = ytop; y <= ybottom; ++y)
{
if (x, y) is inside the triangle
draw pixel
}
}
}

Now the only bit you have to solve is how to tell if the (x, y) point is
insode the triangle or not. That is the whole point of the exercise you
have been given, the rest is just distraction. Try drawing xleft, xright,
ytop, ybottom on a piece of paper, then draw where you want the traingle
to be, and then see if you can work out what the formula is for telling
whether a point (x, y) is inside the triangle or not.

That's a very inefficient way to draw a triangle.

The algorithm given wasn't bad, but needs more specifics as to how the xl
and xr values are initialized, and how/when they change. In similar code
I've written, a triangle _always_ has either the top as a point and the
bottom as a line, or the top as a line and the bottom as a point. To draw
triangles that don't fit that mold, you split it into a top and bottom
triangle that _do_ fit that mold.

So the algorithm draws all pixels between a line of some non-zero slope on
the left, and another on the right, moving down (or up) one "scan line" at a
time. Fast, and easy.

(But as Victor said, not really a C++ question.)

-Howard