Drawing polygons: use only triangles or use bigger ones, splitting them if needed?

[TCH]

Out of theoretical curiosity, which would be the smarter thing?

If we only use triangles, they always will be convex polygons, so we can just simply get the horizontal coordinates of the two edges on each line and fill between them.
However, if we need to draw a polygon with a higher number of vertices, then we need to draw several triangles to draw it, which means we need to draw all the edges "inside" the big polygon and also fill it triangle by triangle, instead of filling it once.
On the other hand, if we try to draw a polygon which is not convex, then we cannot just use the horizontal coordinates of the edges to fill between them, as it is not known, how much edges - and thus horizontal points - we will have. So, to avoid these gaps, we need to split the non convex polygon into convex ones. But for that we first have to determine if it needs splitting at all.

So, in short, which approach would be the faster? On Amiga of course. If the answer depends on which model we're talking about, then A500 and A1200.

[VladR]

What is the use case scenario?
I presume we aren't talking about a classic game scenario as you would already have specific triangles.

Edge traversal, scanline by scanline is expensive. If you can merge multiple consecutive runs within same scanline into one, then that's the way to go.
But the merge must be faster than the brute Force.

[deimos]

Originally Posted by TCH

Out of theoretical curiosity, which would be the smarter thing?

I think the smarter thing would be to arrange it such that your polygons are always convex, which is easy if you're in control. I think you'd get the most benefit from reducing the number of polygons by making them bigger where possible. I have polygons with up to 6 vertices, for instance.

I don't think there's much more complexity in the code to scanline fill polygons with any number of vertices compared to just triangles. The calculations are little more than just a pair of Bresenhams.

Otherwise you don't always have to decompose polygons all the way to triangles to get them convex, just clipping an ear or two is often enough.

You may find that restricting to triangles gives you other benefits though, particularly in with 3D code.

[TCH]

Originally Posted by VladR

What is the use case scenario?

Experimenting with filled vectorgraphics.

Originally Posted by VladR

Edge traversal, scanline by scanline is expensive. If you can merge multiple consecutive runs within same scanline into one, then that's the way to go.
But the merge must be faster than the brute Force.

Thanks. In the meantime i've concluded that the best is if i use only convex polygons.

Originally Posted by deimos

I think the smarter thing would be to arrange it such that your polygons are always convex, which is easy if you're in control. I think you'd get the most benefit from reducing the number of polygons by making them bigger where possible. I have polygons with up to 6 vertices, for instance.

Yep, in the meantime i've come to this conclusion too.

Originally Posted by deimos

I don't think there's much more complexity in the code to scanline fill polygons with any number of vertices compared to just triangles. The calculations are little more than just a pair of Bresenhams.

Exactly, until they are convex polygons. I just make a list with the line drawing algorithm of an y addressed x0, x1 pairs and simply do the filling between the two horizontal coordinates.

Originally Posted by deimos

Otherwise you don't always have to decompose polygons all the way to triangles to get them convex, just clipping an ear or two is often enough.

Yeah, i know that it's enough to split the part which makes it concave, but i did not know what would be the faster, just split it up entirely, or do an "is it convex" check after each split.

Originally Posted by deimos

You may find that restricting to triangles gives you other benefits though, particularly in with 3D code.

What benefits? I just begun experimenting with this and i thought since it is much more faster to draw one convex octagon than eight triangles, it would perform better in 3D too. Am i mistaken?

BTW, i implemented the algorithm for transforming a 3D point to 2D from Wikipedia, but it did not give any hint about the display surface's coordinates. I suspect that

ex

,

ey

, and

ez

are ought to be constants, but what? Have you guys any ideas about what they should be?

[VladR]

If you don't have a specific 2D game scenario in mind and this is just experimenting, there's plenty googlable approaches how to break down a generic polygon into renderable parts.

Most of them, as far as I can recall have a condition or two per scanline.

If the target machine is A500, it's going to add up real fast.

I hope you experiment in some C/C++ and not an assembler?
Edit:
I just realized that a very common scenario could be a demo production where animated convex polygons are, indeed, desirable.
In which case you have the option to adjust speed of movement to match the performance of the rasterizer, so the performance might not be critical as it's up to you to decide what you want on screen.

[deimos]

Originally Posted by TCH

What benefits? I just begun experimenting with this and i thought since it is much more faster to draw one convex octagon than eight triangles, it would perform better in 3D too. Am i mistaken?

Benefits other than performance, such as knowing that your polygons are always planer, things you probably know.

Originally Posted by TCH

BTW, i implemented the algorithm for transforming a 3D point to 2D from Wikipedia, but it did not give any hint about the display surface's coordinates. I suspect that

ex

,

ey

, and

ez

are ought to be constants, but what? Have you guys any ideas about what they should be?

That description of the perspective transform seems overly complex for what is really just a bunch of similar triangles. I've always seen it done using just the distance to the display surface. Perhaps setting

ex

and

ey

to 0, and

ez

to the viewing distance will give you what you want. This part of the process is typically the only one that involves division, so it's often done separately to all the matrix based transformations.

[TCH]

Originally Posted by VladR

If you don't have a specific 2D game scenario in mind and this is just experimenting, there's plenty googlable approaches how to break down a generic polygon into renderable parts.

Most of them, as far as I can recall have a condition or two per scanline.

If the target machine is A500, it's going to add up real fast.

Maybe, but i already went for alway convex polygons.

Originally Posted by VladR

I hope you experiment in some C/C++ and not an assembler?

No, of course not, it's C. Assembly will be used when it's working and the optimization will come into the picture. But until then, a lot of work has to be done.

Originally Posted by VladR

I just realized that a very common scenario could be a demo production where animated convex polygons are, indeed, desirable.
In which case you have the option to adjust speed of movement to match the performance of the rasterizer, so the performance might not be critical as it's up to you to decide what you want on screen.

No, this is not a demo. I am too amateur for that. Later when this is works, i am planning to do some games with it, but not a demo.

Originally Posted by deimos

Benefits other than performance, such as knowing that your polygons are always planer, things you probably know.

No, i don't. I have no experience with 3D.

Originally Posted by deimos

That description of the perspective transform seems overly complex for what is really just a bunch of similar triangles. I've always seen it done using just the distance to the display surface. Perhaps setting

ex

and

ey

to 0, and

ez

to the viewing distance will give you what you want. This part of the process is typically the only one that involves division, so it's often done separately to all the matrix based transformations.

I did not used the matrix algorithm there, but the alternative one:

x = p3D->x - c->x;
y = p3D->y - c->y;
z = p3D->z - c->z;
cx = cos(c->thx);
cy = cos(c->thy);
cz = cos(c->thz);
sx = sin(c->thx);
sy = sin(c->thy);
sz = sin(c->thz);

dx = cy * (sz * y + cz * x) - sy * z;
dy = sx * (cy * z + sy * (sz * y + cz * x)) + cx * (cz * y - sz * x);
dz = cx * (cy * z + sy * (sz * y + cz * x)) - sx * (cz * y - sz * x);

p2D->x = (ez / dz) * dx + ex;
p2D->y = (ez / dz) * dy + ey;

(Of course not like this, i've put the repeated calculations into temporary variables and the camera angles are separaterly calculated and stored when the camera has changed, not during render.)

What do you mean by "viewing distance"? Isn't viewing distance is the distance between the camera and the point?

[deimos]

Originally Posted by TCH

What do you mean by "viewing distance"? Isn't viewing distance is the distance between the camera and the point?

I mean the distance between you and the "viewing surface", i.e. the screen.

The way I do it (and other people are welcome to tell me why I'm wrong), is to use pixels as the unit size for everything, and to approximate one pixel = one millimetre.

Your screen is a clear glass grid ranging from -160 to 159 in x and 127 to -128 in y. Your scene, the things you're rendering, sit behind the screen. You sit at viewing distance in front of it.

Chose a vertex in your scene, imagine a line from your eye (the camera) to that vertex, and imagine the point where that line intersects the screen. Note it's x and y coordinates.

Job done, and calculated through similar triangles.

All the matrix stuff leads up to this point. Without looking closely, I think your code is just another representation of the matrices.

EDIT: So, viewing distance is probably ez.

[TCH]

Originally Posted by deimos

I mean the distance between you and the "viewing surface", i.e. the screen.

The way I do it (and other people are welcome to tell me why I'm wrong), is to use pixels as the unit size for everything, and to approximate one pixel = one millimetre.

Your screen is a clear glass grid ranging from -160 to 159 in x and 127 to -128 in y. Your scene, the things you're rendering, sit behind the screen. You sit at viewing distance in front of it.

So, you're saying i should set

ez

to

500.0

?

Originally Posted by deimos

Chose a vertex in your scene, imagine a line from your eye (the camera) to that vertex, and imagine the point where that line intersects the screen. Note it's x and y coordinates.

Job done, and calculated through similar triangles.

Okay, now i am confused. How can my eye be the camera? The camera supposed to be a point inside the vectorspace which symbolise my eye's imaginary position; in short the position of my "avatar". If my real eye would be the camera, then all of the camera related calculations would be entirely futile as my eye never changes it's position or angle regarding the objects in the vectorspace, since i always look at the monitor from the very same position and in the very same angle.

Originally Posted by deimos

All the matrix stuff leads up to this point. Without looking closely, I think your code is just another representation of the matrices.

It's not my code. I mean, i wrote this piece of code, but i did not come up with the algorithm, it's just the implementation of the "alternative" algorithm on Wikipedia. I do not even understand how it works.

Originally Posted by deimos

EDIT: So, viewing distance is probably ez.

Okay, but what value should i give it?

[deimos]

Originally Posted by TCH

So, you're saying i should set

ez

to

500.0

?Okay, now i am confused. How can my eye be the camera? The camera supposed to be a point inside the vectorspace which symbolise my eye's imaginary position; in short the position of my "avatar". If my real eye would be the camera, then all of the camera related calculations would be entirely futile as my eye never changes it's position or angle regarding the objects in the vectorspace, since i always look at the monitor from the very same position and in the very same angle.It's not my code. I mean, i wrote this piece of code, but i did not come up with the algorithm, it's just the implementation of the "alternative" algorithm on Wikipedia. I do not even understand how it works.Okay, but what value should i give it?

Well, I think wikipedia hasn't given you the best explanation.

You, your eye, your camera, does move, but the final step of the matrix stuff is the "camera transform", which moves and spins everything in the world, including yourself, around backwards so that you end up at the origin looking straight down the z axis. Then the screen is a plane parallel to xy and around 500mm away from your eye.

I recommend you implement the "matrix stuff". It's not hard, and most other sites / tutorials / blogs you find will expect you to have it.

[TCH]

Even if i implement the matrix version, i still have no idea what to write into

ez

when i calculate the projected point's coordinates. You say, it's

500.0

?

[deimos]

Originally Posted by TCH

Even if i implement the matrix version, i still have no idea what to write into

ez

when i calculate the projected point's coordinates. You say, it's

500.0

?

It's totally up to you. What kind of effect do you want?

EDIT:



In this image the "near plane" or "plane of projection" is your computer monitor. Imagine an object placed behind that plane. You should be able to see that moving the eye point closer to the screen will give a more exaggerated 3D effect, just as in real life photography.

500 is a good starting point, as you're probably sitting around 500mm from your screen. If you find that things need to be more 3D, or your field of view isn't big enough, then you can decrease that value.

Alternatively, if you have a specific field of view in mind, then you can calculate your

ez

from that.

[TCH]

Thanks. I'll start with 500 and then i'll see.

[Juz400]

Not sure if this is of any help but there are a number of Vids following this one

[ Show youtube player ]

[TCH]

Thanks, i'll check them.