Allegro.cc - Online Community

Allegro.cc Forums » Game Design & Concepts » Polygon rasterizing

This thread is locked; no one can reply to it. rss feed Print
Polygon rasterizing
Kitty Cat
Member #2,815
October 2002
avatar

Hello. I know Allegro's 3d functions kinda leave something to be desired, but I'm using them anyway. I really have two points I'd like answered, and a couple bug-related notes about a couple things I happened to find(one for allegro, the other for fblend.. yes I'll go to fblend's site to report it, but I'm here right now ;))

For one, I originally drew the level seperately from the sky(actually a skybox, an area of the "level" never really played in) by drawing the sky on one buffer(the main video buffer to be displayed), and the actual level on a temporary buffer, using transparent colored polygons where the sky would be(to avoid seeing "through" the sky) and mask blitting it to the video buffer. Obviously that's not very efficient. I reworked it to draw the sky as before(straight to the video buffer), then drawing the level on that, skipping the "sky polygons" all together and using a reject map of sorts to properly hide what shouldn't be seen. Unfortunately, this introduces a bug, which isn't honestly unexpected. I sometimes see dots on the seams of polygons, seeing through to the previously drawn sky, obviously due to inaccurate math. Being (overly) simplistic, the map data(if you're unfamiliar with Doom's map structures) is arranged on a 2d, top down, plane, the ceiling and floor being different only in height, with walls connected top to bottom. I'm thinking of a couple ways to solve this issue, but I'd like you guys' input. :)

Second(OMG, all that was only one? sweatdrops), I'm having a slight overdraw problem(as in, I'm drawing/trying to draw, much more than necessary). Unfortunately, the BSP-tree data doesn't tell what's blocked from view. The reject map is a good start but, especially when dealing with large sectors, isn't very efficient or robust(consider a large sector, of which you can only see a very small amount.. the entire sector will get drawn). I was thinking about making an internal-only reject map, based on subsectors(since that's the smallest amount of space that can safely be culled, on what's effectively a 2d plane). Unfortunately, the algorithm to build that kind of table is pretty intense(my 300Mhz Cyrix M-II takes a significant amount on plain sectors on a moderately sized level). Plus, it doesn't account for closed sectors(ceiling and floor are same height), or sectors that close/open during play. For this, I do not have an immediate solution.

Well, that's it for the help, I guess for now. As for the bugs.. It seems a lit polygon at full brightness(all corners are 255, shading to black) is just a wee tad darker than a non-lit polygon. Barely, but still kinda noticeable.

FBlend's bug.. when drawing a masked image(15/16bit) using fblend_trans(), the masked area seems to slightly darken what's behind it. With the way I do translucent walls(admittedly inefficiently), this causes areas where the sky(and/or other areas behind the wall) to inexplicably darken. And it gets worse the more translucency there is.

Yes, I'm gonna be working on these issues on my own(except the bugs of course), but any help you guys can give is very appreciated.

Peace.

--
"Do not meddle in the affairs of cats, for they are subtle and will pee on your computer." -- Bruce Graham

Bruce Perry
Member #270
April 2000

Re the first point; if you only use POLYTYPE_PTEX, you shouldn't see any gaps. Sadly, I think POLTYPE_PTEX_MASK is buggy, and gaps do appear. This isn't inaccurate maths; it's a bug. I believe the polygon renderers are obfuscated with assembly language, so I have never tried to track it down.

For the second point, I'm not sure what to suggest. Portals maybe? Suffice it to say that I've never done a successful 3D engine that scales well to large worlds. Last time I tried to implement portals, I ran into all sorts of problems, and the display is a complete mess. That was a long time ago though. Maybe I should try again. :)

Re the lit polygon problem: are you in a true colour mode? If so, do you have MMX enabled? I can see why this is the case; shifting right eight is much more efficient than dividing by 255. I suppose you've tried setting c to 256? Failing that, I'd recommend you treat it as a special case and use a non-lit renderer; after all, it's faster :)

There's one other bug you should be aware of: the polygon routines tend to overrun the clipping rectangle by one pixel to the right. If the clipping rectangle extends to the bottom right-hand corner of the screen, it will overrun the buffer. If you get intermittent crashes on exit, and like me spent several days trying to track the bug down, maybe this is why ::) I normally solve it as follows:

bmp->cl++; bmp->ct++; bmp->cr--; bmp->cb--; /* Evil polygon routines */
/* Draw stuff */
bmp->cl--; bmp->ct--; bmp->cr++; bmp->cb++; /* Evil polygon routines */
rect(bmp, bmp->cl, bmp->ct, bmp->cr-1, bmp->cb-1, 0);

Actually, the polygon routines used to be a lot better. I'm sure the overrun bug wasn't there in Allegro 3.12. Theoretically the routines have got better - they now support true colour, they support subpixel accuracy, and they can handle cases where two vertices coincide - but sadly bugs have been introduced. It's a real shame. If you do track down any of the bugs, and fix them, be sure to post them to the Allegro mailing lists!

Nice to see I'm not the only one who uses these routines though. Good luck with what sounds like a very good engine in the making 8-)

--
Bruce "entheh" Perry [ Web site | DUMB | Set Up Us The Bomb !!! | Balls ]
Programming should be fun. That's why I hate C and C++.
The brxybrytl has you.

Thomas Fjellstrom
Member #476
June 2000
avatar

Quote:

Actually, the polygon routines used to be a lot better.

IIRC In one of the earlier WIPs they swaped out the 3D code for P3D by some guy (Colin??) who dissapeared before it was merged. So the one guy who REALLY know how it all worked was never around to see it merged...

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

Kitty Cat
Member #2,815
October 2002
avatar

Quote:

if you only use POLYTYPE_PTEX, you shouldn't see any gaps. Sadly, I think POLTYPE_PTEX_MASK is buggy

I use which ever type fits the polygon. If it's full bright and not colored, it uses POLYTYPE_PTEX, if it contains masked parts, it uses *_MASK, ect..

Quote:

For the second point, I'm not sure what to suggest. Portals maybe?

I'm not really sure what portals are. I think I have the basic concept, but I have no idea how to do it.

Quote:

Re the lit polygon problem: are you in a true colour mode? If so, do you have MMX enabled? I can see why this is the case; shifting right eight is much more efficient than dividing by 255.

I can understand that. Thanks for the clear up. :) It's honestly not too noticeable unless you're looking for it.

Quote:

There's one other bug you should be aware of: the polygon routines tend to overrun the clipping rectangle by one pixel to the right. If the clipping rectangle extends to the bottom right-hand corner of the screen, it will overrun the buffer. If you get intermittent crashes on exit, and like me spent several days trying to track the bug down, maybe this is why

Hmm. Interesting. I wonder if this is what's been causing me problems. Thanks, I'll try that. :) BTW, when I first started developing this, I noticed flicker on the very top and left most border of the screen. I thought it was because I was using the (inaccurate) fixed point functions(namely clip3d(), which I wrote using clip3d_f() as a base). I fixed that by extending the viewport one pixel on all sides.

Quote:

Nice to see I'm not the only one who uses these routines though. Good luck with what sounds like a very good engine in the making 8-)

Heh. Thank you. :) I'll see what I can do about at least getting some pics up somewhere.

--
"Do not meddle in the affairs of cats, for they are subtle and will pee on your computer." -- Bruce Graham

Bruce Perry
Member #270
April 2000

Quote:

I'm not really sure what portals are. I think I have the basic concept, but I have no idea how to do it.

Portals work best for closed-in worlds, like in Descent. They do require you to design the game world with portals in mind; Descent uses connected cubes. (That said, I don't think Descent actually uses portals.) The nice thing about portals is that there's zero overdraw. However, they result in traversing a tree that can become quite complex, and the number of polygons actually drawn to the screen can soar. Use with care - especially as Allegro's polygon renderers have quite a bit of overhead.

A quick search found this. It looks good; I'll have to read it myself at some stage :)

Quote:

BTW, when I first started developing this, I noticed flicker on the very top and left most border of the screen.

This is probably because coordinates are always rounded up when drawing. I argued that rounding to the nearest would be a better idea; but the person who implemented it didn't speak very good English, and he thought I was talking about the rounding towards zero you get when you cast to int. In any case, the rounding up causes the polygons to detach from the left and top edges of the screen, so if you're drawing something highly contrasting underneath, that's what happens.

When I bring the clipping rectangle in one pixel, I don't move the viewport at all. So these inaccuracies get clipped off (by the normal 2D clipping rectangle, not by clip3d_f()).

Quote:

I thought it was because I was using the (inaccurate) fixed point functions(namely clip3d(), which I wrote using clip3d_f() as a base).

Which version of Allegro do you have? Because clip3d() has been implemented in the library, and it will probably clash with your function on some compilers (I think gcc lets you override functions this way at the linking stage, although you get a compiler error if the prototypes don't match).

The clipping routines should be very accurate though. The vertices generated by the clipping process will (nearly always) be accurate to the nearest representable value, when using fixed-point maths. Provided your objects are at least SCREEN_W units from the camera (which is considerably less than itofix(1)), you should be OK.

Maybe I'll try and fix up my old portal code, and upload it somewhere. Don't hold your breath though :)

--
Bruce "entheh" Perry [ Web site | DUMB | Set Up Us The Bomb !!! | Balls ]
Programming should be fun. That's why I hate C and C++.
The brxybrytl has you.

Kitty Cat
Member #2,815
October 2002
avatar

Quote:

because coordinates are always rounded up when drawing. I argued that rounding to the nearest would be a better idea

nods I always thought rounding down was the best(and safest) for almost any drawing code. Saves from having to check the precision number all together when you can just throw it out when the time comes to draw it.

Quote:

Which version of Allegro do you have? Because clip3d() has been implemented in the library, and it will probably clash with your function on some compilers (I think gcc lets you override functions this way at the linking stage, although you get a compiler error if the prototypes don't match).

:-[ That was actually an ego booster.. meaning I'm the one that wrote the clip3d() function in the Allegro library. :-[

But excluding that, I did rewrite what's there, to handle only texture mapped polygons(there's no other kinds, so its worthless to constantly check). I also moved the z checking to the end, since the side clipping may make it unnecessary in the end, as well as passing a 'char flag[4]' parameter which is a bitfield that tells which sides need to be clipped(otherwise they're just copied). fyi, I named it clip3d_ex().

I tried keeping custom code to a minimal, but sometimes doing it all through Allegro is way too wasteful(ie. normalized vector rotation.. instead of how its done in excamera.c with the extra matrices and such, a half dozen lines of code or so does the same job much more efficiently).

Quote:

The clipping routines should be very accurate though. The vertices generated by the clipping process will (nearly always) be accurate to the nearest representable value, when using fixed-point maths. Provided your objects are at least SCREEN_W units from the camera (which is considerably less than itofix(1)), you should be OK.

Actually I use itofix(1) as the minimum z distance. I tried 1(smallest fixed number above zero), but there's really no noticable difference, so why waste the time drawing those extra pixels(every one clipped counts).

And I'll look at that link tomorrow. gotta go now. Thanks :)

--
"Do not meddle in the affairs of cats, for they are subtle and will pee on your computer." -- Bruce Graham

Bruce Perry
Member #270
April 2000

D'OH!! Oh well, I normally goof up once a day; that means the rest of today should go well. Now, if you were using your real name on these boards, I'd have known who you were ::) ;D *cough* Anyway, nice work - and sorry if I offended you :-/

Well, if you rounded down, you'd get problems at the right and bottom edges. That's why I say round to the nearest :)

--
Bruce "entheh" Perry [ Web site | DUMB | Set Up Us The Bomb !!! | Balls ]
Programming should be fun. That's why I hate C and C++.
The brxybrytl has you.

frenchfry
Member #2,636
August 2002
avatar

is there any tutorials anywhere to do polygonal crap in Allegro. I could probably learn by looking in the manual a lot, but it would take me forever. Before I do any 3D stuff though, I need to learn the theory behind it. Any links? NO SEARCH ENGINE BITCHING OR LINKS.

------------------------------
"You can't catch me, I'm the gingerbread man!" - The Gingerbread Man

Bruce Perry
Member #270
April 2000

USE A SEARCH ENGINE YOU BITCHING err rude person ;) Or buy a book. We had a really old book called "Graphics Programming on your BBC Micro" or something, and that covered 3D graphics. Back in those days the computer could only do wireframe 3D graphics in real time. I was pretty young, and I didn't understand it at first. But I kept coming back to it, and it started to make sense.

There's no easy way to learn the theory behind 3D graphics. I would seriously recommend buying a book on it, and spending lots of time with it :)

If you aren't willing to shell out for a book, then I'm afraid search engines it is. Google's pretty good these days, you know...

--
Bruce "entheh" Perry [ Web site | DUMB | Set Up Us The Bomb !!! | Balls ]
Programming should be fun. That's why I hate C and C++.
The brxybrytl has you.

Kitty Cat
Member #2,815
October 2002
avatar

Quote:

Anyway, nice work - and sorry if I offended you

Nah, it's okay. I honestly didn't expect anyone to know that its me. I don't really care either, but sometimes I like a little self indulgence. ;)

Quote:

Well, if you rounded down, you'd get problems at the right and bottom edges. That's why I say round to the nearest

I don't think so.. I'm not really sure how Allegro's asm polygon functions work(I don't know asm), but if you allow(for instance) 0.0 to SCREEN_W-0.0001, it'll cover the whole screen, even if it all rounds down, without going out of bounds.

Quote:

is there any tutorials anywhere to do polygonal crap in Allegro

I found examples/excamera.c to be extremely helpful. Though I tend to do better when I work with things myself, instead of reading(though I do plenty of that too)

--
"Do not meddle in the affairs of cats, for they are subtle and will pee on your computer." -- Bruce Graham

Bruce Perry
Member #270
April 2000

Quote:

I don't think so.. I'm not really sure how Allegro's asm polygon functions work(I don't know asm), but if you allow(for instance) 0.0 to SCREEN_W-0.0001, it'll cover the whole screen, even if it all rounds down, without going out of bounds.

Unlike rectfill(), the polygon routines are high-exclusive. In other words, if you specify a rectangle with points (0,0), (0,10), (10,10), (10,0), then the last column that gets drawn to has x-coordinate 9. The resulting rectangle is exactly 10x10 pixels (not 11x11). That means there should be no overdraw when you draw polygons with common edges. :)

--
Bruce "entheh" Perry [ Web site | DUMB | Set Up Us The Bomb !!! | Balls ]
Programming should be fun. That's why I hate C and C++.
The brxybrytl has you.

Kitty Cat
Member #2,815
October 2002
avatar

Quote:

Unlike rectfill(), the polygon routines are high-exclusive. In other words, if you specify a rectangle with points (0,0), (0,10), (10,10), (10,0), then the last column that gets drawn to has x-coordinate 9. The resulting rectangle is exactly 10x10 pixels (not 11x11). That means there should be no overdraw when you draw polygons with common edges.

Okay.. so the last point gets a slight subtraction((10<<16) - 1).

Most of my experience has shown me that you should always round down, unless there's a specific reason not to. I'm not saying that I'm right and you're wrong, but that's my humble opinion. :)

BTW, here's a couple test screenies. Actually it's really just one, but it shows the effect of the FBlend bug I mentioned.

http://perv.cm.nu/~chris/misc/scrsht00.png
http://perv.cm.nu/~chris/misc/scrsht01.png

--
"Do not meddle in the affairs of cats, for they are subtle and will pee on your computer." -- Bruce Graham

Go to: