Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
Rasterization without scans?

By lower triangular in Op-Ed
Tue May 29, 2001 at 12:22:36 PM EST
Tags: Software (all tags)
Software

The fundamental unit of games programming is the good old filled convex polygon (FCP). And the Old Faithful method of displaying the FCP is scan-conversion, followed by line drawing followed by blit. And about 25% of the effort put into improving the quality of games over the last few years has been in throwing more and more hardware acceleration at the scan-draw-blit cycle. Here's a suggestion for an alternative way to deal with polygons.

Update [2001-5-29 18:1:11 by cp]: Streetlawyer has owned up to writing this article as a hoax.


Why bother?

Obviously, scan conversion wouldn't be so widely used if it wasn't the best algorithm ... for most purposes. But that doesn't mean that other ways of doing the same job aren't worth considering...

  • Horses for Courses: scan conversion is the best for FCPs, sure, as it takes advantage of the coherence of the scan line and follows the pattern of the raster storage. But it's not so obviously the best way to go about complex or complicated concave polygons, where the active edge table (see above link) is large. The method I describe below is almost certainly less efficient than scan conversion in terms of algorithmic efficiency, as it requires the same kind of point-in-polygon calculation (see below) as SC plus extra operations. But I can see how there could be cases in which, because it doesn't require edge tables, for very complicated polygons, it could be significantly more RAM-efficient, freeing up space that could potentially be used to cache something else which was slow and important.
  • Art for art's sake. I have a personal agenda in trying to do things in different ways for the sake of creativity. But even if you don't think that this is a valid goal for programming, ideas like this have a right to exist because they suggest other areas of usefulness, and stimulate lateral thinking which helps with design solutions.
The alternative approach

In general, and at the highest level, the scan-conversion algorithm goes:

for each scanline
{
get active edges from active edge table;
set bytes in offscreen buffer to plotted or unplotted using odd parity rule;
update active edge table;
}
copy offscreen buffer to screen memory (i.e., blit);
The reason that the two-step approach is used (first fill the offscreen buffer, then blit to screen memory) is that drawing directly to screen tends to give a flickery display [discussion]. However, this flickering effect arises largely because the pattern of updating which is observed if a scan-conversion algorithm writes directly to screen memory (left to right, top to bottom) is one which is very easy for the human eye to pick out. Part of the reason for this is that the raster sequence has a very high discrepancy -- it fills up the space in a very predictable, uneven manner. If, instead, we used a function which filled the space more evenly (a "low-discrepancy sequence"), then the screen flicker would be distributed around the screen, giving the eye less to notice. One such sequence is the Sobol sequence, for which there are good routines widely available.

The obvious problem with rasterising according to the Sobol sequence is that it does not take advantage of the coherence of the raster line. Of course, this is the whole point ... the coherence of the line is a function of its high discrepancy. But it means that some other, potentially expensive function needs to be calculated for every pixel to determine whether the next point to be drawn is inside or outside the polygon. There is some benefit from using winding-number rather than crossing-number algorithms.

So the proposed filled-polygon drawing algorithm would look more like this

determine maximum and minimum x and y coordinates of polygon:
for (i=0,i<((xmax-xmin)*(ymax-ymin)),i++)
{
generate next point in Sobol sequence;
calculate wn=winding number for (point, polygon);
if (wn!=0), draw point into screen memory;
}
I doubt that this is ever going to take the place of SC-blit. In fact, I doubt it'll catch on at all. But it might be useful as a special effect, and it helps to take your mind off the stultifying effect of DirectX. Viva Muerte!

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Poll
This idea is ....
o Stupid 35%
o Crazy 0%
o Inspired 6%
o Stupid, but in an inspired way 40%
o Viva Muerte! 17%

Votes: 45
Results | Other Polls

Related Links
o blit
o owned
o writing
o scan conversion
o best algorithm
o personal agenda
o discussion
o discrepanc y
o Sobol sequence
o good routines
o winding-nu mber
o Viva Muerte!
o Also by lower triangular


Display: Sort:
Rasterization without scans? | 60 comments (37 topical, 23 editorial, 0 hidden)
Very Interesting. (2.33 / 6) (#2)
by Anya on Wed May 23, 2001 at 11:28:17 AM EST

This is interesting because it is so far off the beaten track of subjects I usually come into contact with. I can't say I understand it, because I am not very mathematically inclined at all, but I do find your artistic directions interesting.

Games seem to be one region where art is not really considered, and if it is, it is only incidental. Games may have pretty artwork and sound, but the programmers aren't really artistic; they are mathematical. It would be very interesting to play a game designed from the ground up with a holistic eye turned towards Art. Not only the pictures and sound, but the very design of the game itself executed in the name of art.

I may well be woffling, because it isn't a field I understand, but I still think it is an interesting idea.

Stars, stars! And all eyes else dead coals.

ha ha ha ha (1.83 / 6) (#5)
by codemonkey_uk on Wed May 23, 2001 at 12:23:03 PM EST

Games seem to be one region where art is not really considered ...
Thats so wrong I could cry!

Please don't pontificate on subjects about which you know nothing.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

Woah! (3.75 / 4) (#6)
by leviathan on Wed May 23, 2001 at 12:32:54 PM EST

Please don't pontificate on subjects about which you know nothing.
But if people didn't spout on subjects they know little about, there'd be precious little of k5 left, and nothing for streetlawyer to do!

The comment on the amount of pure techies in games development is interesting considering recent outbursts. Not that I agree with it (after all, it's the designer who designs, not the coders), but it's worth airing if it's an honest perception. And it's certainly true that in artistic terms, most plot and character development in games could be said to be a little lacking.

--
I wish everyone was peaceful. Then I could take over the planet with a butter knife.
- Dogbert
[ Parent ]

read it in context! (3.80 / 5) (#7)
by lower triangular on Wed May 23, 2001 at 12:40:21 PM EST

read the _whole_ damn post before you start being rude to people ....
Games seem to be one region where art is not really considered, and if it is, it is only incidental. Games may have pretty artwork and sound, but the programmers aren't really artistic; they are mathematical.
in other words, there's a lot of art in games, but the actual code is written with more concern for brute power and less for elegance than almost anywhere else. look at some games code and you will see highly optimised, architecture specific, nasty down and dirty stuff. You will _not_ see anything you could describe as "code is art". don't be such a smart-ass ... please don't _you_ talk about things you haven't _thought_ about.

Linux - the ultimate Windows Service Pack!
Windows - the ultimate Linux Productivity Suite!

[ Parent ]

Oi! (3.25 / 4) (#14)
by deefer on Wed May 23, 2001 at 01:08:51 PM EST

in other words, there's a lot of art in games, but the actual code is written with more concern for brute power and less for elegance than almost anywhere else.

As someone who used to code that low down, dirty, brute power stuff, I'm telling you, it *is* art. In assembler, there are more than one ways of skinning a cat; the art of it is to get it running like a bastard. And that is art. And frequently, there *is* a twisted kind of beauty in the ugly hacks required for performance... It's just not "elegant". Because elegance frequently costs a clock cylce or two more... Wish I still had the code I wrote many moons ago which creatively used the XLAT instruction to do clever things with 2d Huffman tables; now that would be a good K5 article ! :)

Oh, and lower_triangle, I know you must have put a lot of effort in this story, and it feels like one of your babies that you must protect. But please be a bit more moderate and objective in your postings to this story, because you'll be alienating the very people who want to mod it up...


Kill the baddies.
Get the girl.
And save the entire planet.

[ Parent ]

efficiency is elegance (none / 0) (#30)
by codemonkey_uk on Thu May 24, 2001 at 07:28:45 AM EST

Although I don't want this discussion to go down the "is code art" road, I have to say that I know what games code looks like, because I write games code. As a job. For a living. Its what I'm paid to do, and games development takes more than pure science - it takes imagination. It is art.

Oh, and while I'm here, beauty is in the eye of the beholder, just because you can't see it doesn't mean its not there.

Just because I didn't quote it all, doesn't mean I didn't read it all.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

so what? (none / 0) (#35)
by lower triangular on Thu May 24, 2001 at 07:55:42 AM EST

And I happen to be an artist ... for a living, or at least, full time. And if you are a games developer, and if games development requires imagination, then you can't be all that good at it. spare me your "efficiency is elegance" assertions ... unlike you, I'm not telling anybody to "shut the fuck up", but I think it is generally accepted that code which is highly optimised for a specific architecture is not "elegant" in any conventional sense.

just because you can see something doesn't mean it is there ... when you specifically ignore what I wrote and make criticisms which are specifically adressed in the article, then why should I care whether you read it ... you didn't understand it.

Linux - the ultimate Windows Service Pack!
Windows - the ultimate Linux Productivity Suite!

[ Parent ]

Oh (4.60 / 5) (#15)
by Anya on Wed May 23, 2001 at 01:18:36 PM EST

Well I'm sorry, but I did explicitly state that games really aren't my thing. Isn't that good enough for you? Are k5 articles only to be commented on by elitists and 'experts'? You didn't even rebut what I said, and just stated I was wrong (which I probably am), so why should I believe you?

I'd be quite happy to be corrected, but my point is that although lots of artists and musicians are employed in games development, they aren't really central to it. Compare games and film. Where is the Orsonne Welles of game development? Do games move someone emotionally? No, they don't. Great Art can inspire awe and wonder, tears of joy and sadness. Do computer games do this? When was the last time you cried playing a computer game?

It really seems quite obvious to me that Art is not central to games.

Stars, stars! And all eyes else dead coals.
[ Parent ]

the game experience can be art (3.50 / 4) (#22)
by eLuddite on Wed May 23, 2001 at 05:09:32 PM EST

It really seems quite obvious to me that Art is not central to games.

It would be if the code had consequences. Miss a health bonus? Have a random byte changed in the registry. Miss a shot and die? Lose a file.

DoomProphet: Where ya camping, bro?
BeatnikChix0r: got fragged, lost the phd thesis.
DoomProphet: Viva Muerte!
BeatnikChix0r: indeed
DoomProphet: Verdad.
BeatnikChix0r: Again?
DoomProphet: cant. automatic reboot every 13 minutes.
BeatnikChix0r: *swoon*

---
God hates human rights.
[ Parent ]

hehe, funny (none / 0) (#23)
by Anya on Wed May 23, 2001 at 05:19:28 PM EST

That would be one way of stirring emotion alright, but it is still quite different from Art. Art allows you to feel for someone else, a fictional character or idea. This suggestion would mean that the player is only feeling emotions for himself, and only for the most simple and selfish of reasons.

It would still make games much more interesting if there was a gambling element though.

Stars, stars! And all eyes else dead coals.
[ Parent ]

I vehemently disagree (3.66 / 3) (#25)
by SIGFPE on Wed May 23, 2001 at 08:18:19 PM EST

Do games move someone emotionally? No, they don't.
Come on! This is so wrong I wonder where you've been living all your life :-) Ah...it's just clicked...you don't consider the effects of adrenaline to be 'true' emotion. People aren't automata. They play games because of the emotional highs they get. That's true of much of human behaviour.

they aren't really central to it
They absolutely 100% are. When I was developing 3d rasterisation software for a living I had it repeatedly pointed out to me that the coding is not the game. On a typical game there is often a handful of developers and an army of artists. The direction the game takes is frequently determined by the game designers - not the developers. Look at a game like Alice. It was clearly artist led. Look at the architecture in Quake. Look at the monsters in Doom. (OK, they seemed scary at the time). Art, art, emotion, emotion.

Just not 'Great Art'.
SIGFPE
[ Parent ]

As a professional games developer... (1.80 / 5) (#29)
by codemonkey_uk on Thu May 24, 2001 at 07:18:24 AM EST

As a professional games developer I take offence at the assertion that "[game] programmers aren't really artistic".

As a professional games developer I know from experience that much game design is art-led.

You should believe me because its my job to know. I live it.

Now, I may have been a little sharp in my reply, but there is a huge difference between stating something outright, and stating an opinion. You may have meant to state an opinion, but what you did was state as a fact a obvious, and insulting, falsehood.

Now, if k5 is going to scale, and maintain a good signal to noise ratio, people are going to have to learn to shut the fuck up when they don't know what there talking about.

If you must post on subjects you don't understand, at least have the decency to ask questions.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

Don't be so childish. (2.50 / 4) (#33)
by Anya on Thu May 24, 2001 at 07:40:18 AM EST

1)Don't be so bloody sensitive.

2)You haven't provided any justification or anything. Just 'oh I work in the industry so I know, shut up, I feel so insulted'. I'm sorry, but that isn't an argument. Its a whine.

3)Stop moaning about signal to noise when you are the one providing all the noise.

4)I'm still right anyway. I don't care if games companies employ lots of artists, animators, musicians and coders, it doesn't make one whit of difference, because I am talking about the end result, the game, when considered from an artistic perspective. And let me tell you, games aren't art. I'm not saying they can't be art, just that they aren't art at the moment. If you read my comment properly, you would understand that, but obviously you didn't.

If you want to get arrogant about things, consider this: I have a degree in Art History. If anybody here is qualified to judge what is art and what is not, it is me, not you, the arrogant coder, too close to his work to see any sense.

How the games are designed or who by is irrelevant to the issue being discussed. It is the end product that counts.

Now, if k5 is going to scale, and maintain a good signal to noise ratio, people are going to have to learn to shut the fuck up when they don't know what there talking about.

I agree. Shut up.

Stars, stars! And all eyes else dead coals.
[ Parent ]

ooh a point by point rebutal ... scary (1.66 / 3) (#36)
by codemonkey_uk on Thu May 24, 2001 at 07:57:50 AM EST

I have provided just as much (if not more) justification for my poistion as you have. As I work in the industry I know first hand what happens, and am in a position to correct your orignal position.

It seems however that you have changed that position. You now seem to be saying that most games suck, and are not in your opinion of artisic merit. If this is your position then I agree.

However, this is now what you said in your origanal comment, where you implied that the algorithm proposed in the story had and element of artistic merit that is lacking from the game. So unless you have programmed games yourself, or worked with games programmers, or have any experiance of games programming in practice, then you don't have a leg to stand on.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

pull the other leg (3.33 / 3) (#39)
by lower triangular on Thu May 24, 2001 at 08:12:33 AM EST

So unless you have programmed games yourself, or worked with games programmers, or have any experiance of games programming in practice, then you don't have a leg to stand on.

I think you are being a bit disingenuous here ... I am the author of the article, and I have such experience (I am an artist who is interested in working with the medium of computer games, and I have experience of programming in practice) and you have not shown me any more respect that you have Anya.

Linux - the ultimate Windows Service Pack!
Windows - the ultimate Linux Productivity Suite!

[ Parent ]

Oh do butt out (2.00 / 1) (#42)
by codemonkey_uk on Thu May 24, 2001 at 08:25:14 AM EST

We (Anya and I) were discussing art in game devlopment. As it happens most of the disagreement was a misunderstanding. Your constant attacks don't help resolve anything.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
constant attacks? (none / 0) (#45)
by lower triangular on Thu May 24, 2001 at 08:31:16 AM EST

all I am doing is responding to your points and managing to do so without swearing or calling other people's opinions worthless or telling people to butt out. Anya seems to understand my point about the relationship between games, games programming, art in games and games which *are* art (there are distinctions) and you don't, and you were patronising her as well.

Linux - the ultimate Windows Service Pack!
Windows - the ultimate Linux Productivity Suite!

[ Parent ]

No (2.33 / 3) (#40)
by Anya on Thu May 24, 2001 at 08:12:54 AM EST

I haven't changed my position at all. My arguments now are exactly the same as they were at the top of the thread. You just appear to have realised it though.

btw - rating the comments of the person you are arguing with to 1 is generally considered bad manners. But what am I to expect from a primate?

Stars, stars! And all eyes else dead coals.
[ Parent ]

moderation (3.00 / 2) (#41)
by codemonkey_uk on Thu May 24, 2001 at 08:22:29 AM EST

Yeah. My bad. I got caught up in things, set moderation to 1, clicked the button, then realised what I'd done. I tried to change it back to "none" but it didn't apply. I was going to change it to a '3', but by that time you'd already done the same to my comment, so I though - fuck it. I can't be bothered.

Anywho, sorry about the misunderstanding. But remember, communication is a two way street. You have to be careful to state your position clearly if you want to avoid misunderstandings like the one that occurred in this thread.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

Heh (1.00 / 1) (#43)
by Anya on Thu May 24, 2001 at 08:25:33 AM EST

Okay great. I have heard it said that k5 threads tend to end with both people disagreeing with each other, I suppose this is an example.

Stars, stars! And all eyes else dead coals.
[ Parent ]

Er, (1.00 / 1) (#44)
by Anya on Thu May 24, 2001 at 08:29:53 AM EST

I meant agreeing, obviously.

Stars, stars! And all eyes else dead coals.
[ Parent ]

A month ago... (none / 0) (#53)
by magney on Sat May 26, 2001 at 03:27:10 AM EST

...playing Skies of Arcadia. Perhaps we haven't seen the Shakespeare of this medium yet, but I can tell you that some games can be very moving indeed. Of course, maybe I'm just easily moved. :)

Do I look like I speak for my employer?
[ Parent ]

Games as art (none / 0) (#56)
by greycat on Tue May 29, 2001 at 02:27:23 PM EST

Great Art can inspire awe and wonder, tears of joy and sadness. Do computer games do this? When was the last time you cried playing a computer game?

I generally don't cry when I read novels, but that doesn't mean they aren't an art form.

There are some games out there that I consider to be at least on par with a short story, if not a novel. For example, Myst makes a decent short story, as do most of the original text adventures from the Infocom days.

Sid Meier's Alpha Centauri is also a great example of the game as a literary form -- although in this case, the "story" is heavily borrowed from Herbert, and the literary aspects of the game are closer to philosophy than fiction.



[ Parent ]
You know... (3.00 / 1) (#16)
by slaytanic killer on Wed May 23, 2001 at 01:21:50 PM EST

Most of the best painters whose names are well-known to everyone, have made rigorous sciences out of pigments and techniques.

Just because creating computer games has the same maturity of cave paintings, doesn't mean you should underestimate it.

Science alone is the realm of machines. Art alone is the domicile of dreamers. Takes rare skills to imagine something astonishing and then execute on it. Everyone else studies it, dreams, or machines.

[ Parent ]
Games designed as Art (2.50 / 2) (#24)
by Zarniwoop on Wed May 23, 2001 at 07:45:48 PM EST

It would be very interesting to play a game designed from the ground up with a holistic eye turned towards Art.

Hrm... I seem to remember that Daikatana was designed in a similar vein, with the emphasis on telling a story. Not having played it, I won't comment on the results. However, I'm positive you can find many many reviews around the net...

Of course, you could argue that even this isn't going far enough to be art. I personally don't care if they're art or not. They're a great challenge to program and design, and as long as they're fun to play*, so they're worth my spare time either way :)

* Let's not forget the point, eh?

[ Parent ]

The Artistic Merit Of Games (none / 0) (#46)
by codemonkey_uk on Thu May 24, 2001 at 08:34:35 AM EST

Apparently I misunderstood this comment previously. I took it to mean that games programmers where not artistic in their approach to implementation ... apparently not. Apparently the comment referred to the artistic merit of the final product.

What follows is based on this assumption:

The main thing preventing innovation within the games industry is the financial demands placed on developers by publishers and investors.

The current market makes games development & publishing a very risky business, and most publishers are afraid to go with an original game design because it represents an unknown return, and is high risk.

Having been working an a game without a publisher of quite a while now, I have seen it metamorphosis from an original genre busting design, into one that fits nicely into the categorisations and preconceptions of the market, because publishers don't "get it".

Of course, you could blame the public. If they don't by "art" who's going to pay more 1+ million to develop it?

Of course, all this has very little to do with the techniques used to implement said games.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

I imagine originality is a problem. (none / 0) (#47)
by Anya on Thu May 24, 2001 at 09:15:17 AM EST

Thats the problem with a lot of artistic media - the backers want something they are sure to sell, and tend to be conservative. In the world of literature, painting, sculpture and music it tends not to be so bad because the works can be produced relatively cheaply by just one person. However, in film, TV and computer games the investment required is much greater, so the creators are always under the cosh.

However, film and television often have government or charity based backers, for example film 4 in the UK or even the BBC, which despite its recent decline is still significantly removed from market pressures. Both organisations do produce reasonably original work from time to time.

It is a pity that something similar could not be set up for the games industry - something with a Reithian ethos, if you will. I realise this is unlikely, but hopefully one day when games programming becomes established (by which I mean, when people in government and the 'Establishment' have grown up with computer games) there will exist organisations willing to take a real risk.

Either that or the games industry will move on fast, as it always does. Every now and then there is an original game produced that produces hype and sells well, creating a new category. If artistic and moving games were to sell better than the manufactured stuff, made to a recipie, then it really only takes one brave publisher somewhere to find this out. I think artistic games would have a broader appeal anyway, as both sexes and all age ranges would like them, if done well. And as the games playing consumers get older, they may well hanker for such games.

Thats my guess/wish anyway :)

Stars, stars! And all eyes else dead coals.
[ Parent ]

the term I was taught... (2.42 / 7) (#20)
by persimmon on Wed May 23, 2001 at 03:34:09 PM EST

was "rasterbation".

'Course, I spent too much time with the graphics monkeys on the school paper back in the day.
--
It's funny because it's a blancmange!
some limitations (4.00 / 7) (#21)
by spacejack on Wed May 23, 2001 at 04:19:57 PM EST

I'm not sure if I understand your article fully (it's been a while since I've been done any low-level rasterization primitives). However, the actual triangle rasteration these days is handled by the videocard... so if you're preaching a different polygon rasterizer, the only people who can really do anything about it are ATI and NVidia, or maybe Microsoft or Nintendo. (Unless you're working on a new engine for the PS2 in which case you may be experimenting with all sorts of different rasterization techniques.)

As for trying to draw directly to the front buffer without flicker on a PC, IMHO this is far more trouble than it's worth. You're better off setting up page flipping, which takes virtually no time, and synchronizing the flip with the vsync (which is typically done for you by the API if you tell it to do so).

The only time I can see you wanting to draw to the front buffer is when you can't use page flipping (i.e., in a window) and your screen updates are small. But for most cases, if you're drawing to the font buffer, it seems too hard to ensure you're going to draw everything before tearing becomes evident; even if the tearing is distributed around the screen in small bits (which will probably just look wierd & shakey). You may also run into problems with certain older video cards, attempting to draw straight to the front buffer (eg Voodoo?). It's never really been a reliable animation system.. not since the DOS days anyhow. Modern (i.e., multitasking) OS's are too unpredictable.. you never know when they're going to be stealing some CPU away from you -- right in the middle of a frame.

If you're forced to draw to a back buffer and blt to the front (as opposed to page flip), just about any video card from the past few years is fully fast enough to do this, fullscreen @ 32bpp, during the vretrace, provided your offscreen buffer is in video memory (you can sometimes do it with a sysram back buffer, provided it's small enough).

The only real advantage I can see is that if your method is faster overall for a particular software renderer (perhaps something like Flash) then you may see an overall performance increase.

And finally, one thing to note is that drawing left->right, top->bottom is likely to be more cache friendly than drawing randomly all over the buffer. So, yes, while drawing the actual polygons, it is unpredictable where you're going to be drawing, but when transferring to the screen, doing left->right, top->bottom is probably easier to sync with the vretrace than drawing the polys directly to the front.

blit (3.50 / 6) (#34)
by codemonkey_uk on Thu May 24, 2001 at 07:45:27 AM EST

Actually, very little bliting occurs in real world games development.

Polygons are textured & shaded, much more complex than a simple copy. The back buffer is usually in video ram (as the back buffer is usually only accessed by the GPU - which is fed triangles by the CPU) so the frame is not copied on screen, but a flip occurs. Simply swapping two pointers. This normally happens between screen refreshes.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell

An old idea (2.50 / 2) (#55)
by ucblockhead on Tue May 29, 2001 at 01:05:40 PM EST

That brings back memories, because way, way back when I fooled around with game programming in high school on Apple ][s, that's exactly how we avoided flicker. The Apple had multiple screen buffers. You'd draw to one while the other was displaying and then swap them.


-----------------------
This is k5. We're all tools - duxup
[ Parent ]

Nothing but trouble (4.33 / 6) (#52)
by fluffy grue on Sat May 26, 2001 at 01:26:16 AM EST

First of all, calculating the winding number on a per-pixel basis is frotzing slow, and it requires pretty intense floating-point math (cross-products and such). This does not lend itself very well to being deferred to raster-scan time as you are (apparently) proposing.

Second, although doing edgelists is slow, tesselating a complex polygon down into basic triangles is somewhat quicker. It's still O(n^2), but you only have to do it once.

Third, using winding numbers gives you absolutely no way to do simple things such as

  • Z-buffering
  • Texturemapping
  • Gouraud shading
  • Anything else which requires interpolation across the surface of the polygon
Fourth, there are many other interesting mechanisms to consider. For example, raycasting against the intersections of infinite planes (which is how the PowerVR chipset, used in the Dreamcast and Neon250 among others, does all its rendering). This mechanism also eliminates useless overdraw (since each pixel is raycast only until it hits a non-transparent surface), and leads to useful side-effects such as "infinitely"-precise depth buffering (in fact, no zbuffer is required), implicit infinite-precision stencil buffers, and other coolness. You really should concentrate on that instead. In addition, the raycasting can easily happen at scan-time, eliminating the need for a backbuffer.

Fifth, there are other mechanisms by which the blitting can be deferred until the last possible instance which are much more efficient, such as span-buffering (which is used in Unreal Tournament), and would be great to be implemented in hardware.

Sixth, why would complex polygons help anything out anyway? Any complex polygon can be tesselated down into convex polygons, which can be handled very efficiently by an O(ysize)-time edge scan, and you can't define an entire 3D scene by a single complex polygon, at least not without a LOT of preprocessing (which would be a lot slower than just software rendering - hell, a lot slower than raytracing).

Then again, judging by your multiply-linked-to diary rant, you think that hardware acceleration is the tool of the devil, and that any sort of abstract API is a bad, unartistic thing. I can't argue with illogic like that.

As others have pointed out, the only real bottleneck in 3D rendering right now is the bus between the CPU and the video card, and nVidia's "vertex shaders" (horrible term IMO) do a lot to help with that, as do a lot of tried-and-true techniques such as compiled displaylists and other things which are standardized by things like OpenGL, in an abstract way.

[Editorial note: I can't believe this article's about to be posted.]
--
"Is not a quine" is not a quine.
I have a master's degree in science!

[ Hug Your Trikuare ]

Raycasting infinite planes (none / 0) (#58)
by MfA on Thu May 31, 2001 at 01:24:39 AM EST

A set of infinite planes can only describe a convex polytope, which indeed used to be the basic primitive with which PowerVR worked (nowaday's the lack of API support has degraded it to only supporting triangles, which I assume it internally transforms into a basic set of infinite planes). Their method can only raycast one at a time though, that then generates per pixel Z values they use for bog standard Z-buffering.

PowerVR is not so much insensitive to overdraw, it can just render invisible pixels very fast regardless of rendering order (thanks to the deferred shading and fast on chip tile buffer made possible through tiling).

[ Parent ]
Well, yeah (none / 0) (#59)
by fluffy grue on Fri Jun 01, 2001 at 12:01:05 AM EST

I was oversimplifying (mostly because this isn't something I know too much about, just the basic ideas), and I wasn't saying that infinite-plane rendering solves the concavity problems. However, decomposing concave polygons into a boolean set of infinite planes is pretty much the same as decomposing concave polygons into a set of convex polygons.

I was under the impression, however, that the raycasting was indeed sorted by plane, and that there was no need for a zbuffer (and that if you wanted one, it'd be fast to compute one based on the plane intersections so it goes ahead and creates one while it's going). I suppose that by "deferred shading" you mean pretty much the same thing that I do though - it finds the nearest raycast before doing any shading operations.

Again, I've only heard a basic description of how PowerVR's rendering works, and based on your response it sounds like you're more familiar with it (though I don't think you've said anything which really contradicts what I said, it's just more specific).

Well, there is one contradiction. I was under the impression that every screen tile has its own separate processing unit, and that they're all done in parallel. Or are the tiles just a low-resolution render thing to say, "in this tile, use this set of triangles, in this tile use this set," etc.etc.? I'd imagine that pipelining the rendering could still be possible, even assuming that it makes use of scanline coherence to speed things up (which'd make a lot of sense) - just have a separate processor for each scanline. Or did I misunderstand what you meant by "one at a time?"
--
"Is not a quine" is not a quine.
I have a master's degree in science!

[ Hug Your Trikuare ]
[ Parent ]

PVR&Tiling (none / 0) (#60)
by MfA on Mon Jun 04, 2001 at 02:16:11 PM EST

Tiling means it renders the frame a tile at a time, it completes rendering on it entirely before moving on to the next tile (except in the extremely rare circumstances that the developer wants to read back the Z-buffer, which is discouraged since it means it has to write it to memory). Scanline coherence is not an issue for 3D cards nowaday's, all of them use tiled framebuffers and tiled texture storage such that 2D spatial coherence is taken advantage of (which is of much more use than scanline coherence with the ever smaller polygons used).

Sure you can split up a scene entirely into convex objects, in fact thats what PVR was promoting developers do in the early days (nowaday's they gave up on it though). Also you might be able to render a pixel by raycasting all the infinite planes of all the objects, but PVR doesnt work that way. They can find intersections fast for a single convex object through raycasting and that is what they do, for the rest Z-buffering was probably quite simply the better solution.

They dont do any sorting, sorting alone is a waste of time anyway... due to inter object intersections (which prevent you from even being able to unambiguously sort) you would still have to test every object individually if you just sorted.

The Z-buffer wont be going away for realtime 3D I think, its the best way to test for the eye ray's first intersection IMO (at least once VSD can be done using the Z-buffer again, which should be really soon, poor VSD is limiting 3D at the moment). Even for testing for visibility from point lightsources (for shadows) it could be the best solution in the future. In the far future finding the first intersection and determining simple shadows from point lightsources could be such a small part of computations that putting too much time into optimizing them wont be worth the bother, only then would Z-buffers disappear IMO.

[ Parent ]
Good direction, odd idea. (2.00 / 3) (#54)
by jackmh on Tue May 29, 2001 at 01:38:57 AM EST

I've given this article a +1 for the section as I think that K5 could use more technical articles (being the proper nerd that I am) however it's like the old quote says, "Just because something can be done doesn't mean it should be." An artistic piece of code and a brilliant algorithm are seperated by the effectiveness of the code ;)

Not the first coding prank. (3.00 / 1) (#57)
by SIGFPE on Tue May 29, 2001 at 05:18:34 PM EST

I enjoyed posting this spoof book review that certainly caught a few people out - some of whom actually read the article. Maybe I should have posted it as a story ;-)
SIGFPE
Rasterization without scans? | 60 comments (37 topical, 23 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!