XOR filling

[Celius]

So I started this topic because I heard about XOR filling in the "Polygon Filling..." thread, and I couldn't quite wrap my mind around it. I tried finding info with google, and there's really little info about it, so please don't post a link to just f-ing google it. I basically understand that you go through column by column and do something with EOR, haha. Could someone fill in the gaps (Slight pun intended)? Please, and thanks in advance.

EDIT: Actually, I read a little more about it and it clicked. So nevermind... Thanks anyways.

[No Carrier]

Here's a good page with info:

http://student.kuleuven.be/~m0216922/CG/xortexture.html

Even if you don't need it anymore, it may help others.

[Celius]

Thanks, but I think this is something different. The XOR filling technique I'm referring to is one where you just fill a wireframe polygon in with solid color. This seems to be something else. Thanks though.

[tokumaru]

Celius, I too couldn't find much info on it... Is this that technique where you define the outlines of the polygons and then to render them you go through the scanline switching the state from filled to empty and vice versa when an edge is encountered? Sounds painfully slow for the NES!

[Celius]

Yes, you start out with an outline of a polygon, but the lines have to be drawn a certain way as to not screw things up. Doynax explained it in the "Polygon Filling" thread, and at first I was a little confused. In C, which I only understand a little of, he wrote it like this:

Code: Select all

for(x = 0; x < 256; ++x) {
 pixel acc = 0;
 for(y = 0; y < 240; ++y) {
  acc ^= screen[x][y];
  screen[x][y] = acc;
 }
}

Basically you run through the screen column by column, with "Acc" starting out as 0 at the beggining of each column. You go down one pixel at a time, and XOR the pixels there with Acc, and make Acc equal to that value. This will basically take 2 pixels in a column and fill in the space between them. It's a great and simple method a lot of the time. It doesn't take that long, because we knock out 8 columns of pixels at once. And I have a loop that walks through tile by tile. If a tile is blank but between two pixels, I just have a solid tile I stick in there, so it saves time/CHR space.

[tokumaru]

I see... but you said you were having trouble drawing more than one polygon, right? I guess the only way is to draw one polygon at a time, on top of the others. Of course this would slow things down a lot.

Another option would be to have a few (as many as the amount of polygons in a scene) accumulators and bitmasks, and work on all of them at the same time as you work your way through the screen pixels. But it still sounds too slow... I wonder what exact method Doynax used in his demos.

[Celius]

Yeah, I wish I could get a hold of doynax; it's obvious he knows how to do this efficiently. The one-at-a-time polygon thing seems incredibly tedious. Here's what I'm thinking though.

Since this is the NES, I'm working with 2 bitplanes. I won't take one wireframe bitmap and fill it in; I'll have 2 bitmaps; one for each plane. Also, the polygons that are touching that will be the same color don't need to be separate; they can be one polygon by itself. So I'll walk through these bitmaps for each plane, and I'll have myself multi colored polygons! Oh, yay, I'm gonna go start coding I'm excited.

[tokumaru]

I'll have 2 bitmaps; one for each plane.

That's a very good idea! So, in order to use the 3rd color both planes must be set then? I guess it could work.

Are you planning on using this for real 3D or just for polygonal animation like in Another World/Out of This World? Whichever it is, you're gonna need a separate tool to prepare all the data, no?

[Celius]

I'm doing an Out of this World type of thing, at least I think what I'm doing is like that. I'm basically doing this for CG sequences. I don't really think I'm ready to try code game logic + real time 3D along side all these complications =).

I figure I'll make some sort of application to make my life easier. I at the very least have MS paint to plan out each frame in. I still need to come up with a space-efficient format for storing these frames. I figure in each frame there'll be similar elements, so it won't be too hard. I still am unsure of what the frame rate will be, but I hope for it to be 10+ FPS. While Doynax has successfully done this + 3D calculations at incredible speeds, I plan for a very space-efficient NTSC engine that doesn't use illegal opcodes. This sacrifices speed, obviously.

The other thing is that I might want to apply some dithering effects to have a total of 16 "colors". This would be a little harder, so for now I'll just stick to 4.

[tokumaru]

The other thing is that I might want to apply some dithering effects to have a total of 16 "colors".

Oh yeah, that'd be essential for producing decent videos. I have no idea how that could be implemented fast enough.

[Celius]

Well my sequences wouldn't be very complex, as there are only 256 tiles to deal with. But good news! I've got the 4 color polygon frame draw working! So now all I have to do is come up with an efficient way to store my frames and now add frame change capabilities. Other good news is that polygon filling goes by much faster than line drawing, which is ironic.

The hard part will then be making the frames. I definitely need some sort of application/conversion program for this. I'm not sure how I'll go about this, but once I have a movie, I'll definitely be posting it up!

[tokumaru]

Well my sequences wouldn't be very complex, as there are only 256 tiles to deal with.

I was thinking about that. How will you arrange the 256 tiles? It woldn't look good if the movie played inside a square, video looks better when the "screen" is wider than it's tall, which is why widescreen is so popular nowadays.

Also, if you're gonna use all background tiles on the video, all the area around the video should be hidden with blank palettes. This does introduce the problem that color 0 must not be changed while the video plays or the border would change colors also, and that might keep you from selecting the best 4 colors for each scene.

Personally, I'd have the video screen use 18x14 tiles, which would make it a bit wider and would leave 4 tiles available for use on the border, so that the video could change all 4 colors freely.

So now all I have to do is come up with an efficient way to store my frames

The frames should just be a collection of polygons, that is, a bunch of points to be connected by lines. Inside such a small screen, two bytes would be enough for defining each point. Also because of the small size, higher values could be used as flags to indicate the end of a polygon, end of a frame, a palette change, and so on. something like this:

Code: Select all

ADDR DATA
$00: 28, 8 (point)
$02: 11, 50 (point)
$04: 58, 48 (point)
$06: [end of polygon]
$07: [end of plane]
$08: [end of frame]

This should be anough to draw a simple frame, with a triangle in plane 0. It seems pretty compact to me! Also, to make things very compact, you should somehow take advantage of temporal redundancy. Like, if a scene has a type of background there should be a way to use the same data in all the frames that use it. This doesn't sound so simple though, because you'd have to draw things on top of other things, so you might at first just go with the independent frames.

Anyway, it would be a good idea to keep each frame under 256 bytes, so that they can be easily (and quickly!) read with indirect indexed addressing. The main timeline could be just a bunch of pointers to frames, so that they can be reused. Although that would be a waste if there weren't many repeated frames... unless there was a frame count for every pointer, indicating how many frames to play from that point on.

Well, let the complicated stuff for later. Just start out simple and get your demo running. I'm sure you'll have some good ideas on the way.

and now add frame change capabilities.

I don't think there is much to it, just alternate the side of the pattern table you use and as soon as a frame is ready start working on the next. Since you don't even need to modify the nametables, after the patterns have been draw all you have to do is update the palette (if the frame requested this) and use the alternate pattern table for the background.

Maybe each frame should specify a delay indicating for how long it should be displayed. You'd decrement this value every NES frame and only switch the new video frame in when this expires. This will allow you to variate the frame rate of the video and make use of some temporal redundancy.

Other good news is that polygon filling goes by much faster than line drawing, which is ironic.

Is it good news? If you have to do both, I guess it doesn't matter which is faster...

The hard part will then be making the frames. I definitely need some sort of application/conversion program for this.

Yeah, coding more than a couple of frames by hand would be crazy!

[Bregalad]

Hey, how would you handle the animations with polygons ?
I've tried to use programs like Blender to have fun, but I could figure nothing out from it. I'd like to make one 3D model or two of characters to have some fun. It would definitely be funier to come with a creation that you can rotate in all sense than just a plain bitmap, for characters at least.

Also, it's very good you want not to use any illegal opcodes at any costs. I don't like them anyay and this preserves portability with other 6502 verions, increasing the chances of your techniques to work on a future day where all orginial NESes will be dead and only clones will be available on the market.

[Celius]

Yeah, all I need to do is define shapes with lines on each bit plane. There are some things I need to be concerned about that are rather annoying. For example, there needs to be an even number of pixels in the polygon outline in each column, otherwise the XOR fill will produce errors. This is only an issue when I have two lines intersecting at a point which is by itself in a column of pixels.

So I'll probably need to draw each frame and fine tune it so there aren't any errors, which will be tedious. I was planning a format similar to what you were saying. The format will probably be something like this:

$00-$FD - usable coordinates
$FE - New line
$FF - End of plane

This will be used for drawing the actual frame. Each "End of plane" should be good enough for defining where a frame ends.

The other part will just be frame address listings... I'm pretty sure I'll list them High/Low instead of Low/High, so I can use $0-$80 for commands. Probably $0-$3F will just mean the amount of time I want to show the frame for, like if I type $20,HighAdd,LowAdd, that means I want to show the frame at HighAdd/LowAdd for $20 frames.I could probably increase this number, as I don't think I need $40 extra bytes for commands.

About the filling taking less time, I was just saying it's good because the line drawing takes long enough as it is, and if the filling were to take longer this would only make things worse.

As for the display area, I'll have to just do some fine tuning for images that exceed the 256 tile limit. I plan for it to use most of the screen, though I might try some timed code to do palette changes during Hblank to make black widescreen bars on the top and bottom of the screen (Where the screen might be blanked anyways), and a different color #0 in the display area.

I have Maya on my computer for making 3D models. Though I barely understand anything from it, I plan to use it for most 3D planning like character creation and what I'm doing now. Though I might just make a 256x240 cartoon with MS paint and then convert it to my NES CG format somehow. I'm still not sure.

[tokumaru]

$FE - New line
$FF - End of plane

I don't think you need to specify when a line starts. Since lines is all that you use, and each of them has always 2 points, it's wasteful to keep indicating when a line starts. If you do it the polygon way, you just have to specify the coordinates of each point, with with only one byte of overhead, the one that finishes the polygon. If you have an overhead byte for each line, you'll be wasting a lot of space.

About the filling taking less time, I was just saying it's good because the line drawing takes long enough as it is, and if the filling were to take longer this would only make things worse.

Makes sense! =)

As for the display area, I'll have to just do some fine tuning for images that exceed the 256 tile limit.

Oh, so instead of having a fixed smaller area for the video you'll try to make use of spacial redundancy in real time? Sounds tough!

I have Maya on my computer for making 3D models. Though I barely understand anything from it, I plan to use it for most 3D planning like character creation and what I'm doing now.

I don't think real 3D is the future of this, just polygonal animation sequences. Although I guess it would be OK to draw stuff over 3D images, just to give the illusion of 3D.

Though I might just make a 256x240 cartoon with MS paint and then convert it to my NES CG format somehow.

Paint wouldn't be the best choice, because detecting lines and polygons in bitmap images is a very complicated and imprecise process. If I were you, I'd look into the SVG format. They are basically XML files with tags for the shapes. With a good program that exports SVG files (Inkscape is free and pretty good!), it'd be a matter of converting a few tags you select to support into your format. Much easier than converting from raster images.