## Polygon filling..

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems.

Moderator: Moderators

doynax
Posts: 162
Joined: Mon Nov 22, 2004 3:24 pm
Location: Sweden
Contact:

### Re: Polygon filling..

jargon wrote:remember, for drawing a triangle, always split a render into the upper and lower portion at the corner vertically between the other two, then render those two triangles top half first, also check whether the corners are clockwise or counter-clockwise in order to deduce faster if that surface is even a visible side, i usually use clockwise for polygons on the inner surface of a polyhedron.
Right.. Except I use XOR-filling rather than traditional polygon scan conversion. And that changes a lot of things.
beyond that i use simple z-order split of existing polyhedrons in event two overlap.
As in drawing the polygons in back-to-front order? As I've stated earlier XOR-filling can't handle overlapping polygons, it's the main drawback of the method. I would have to do actual clipping to display overlapping or concave objects, and I have no idea how to do that with reasonable performance (well, aside from precalculating everything).
creating a multiplication matrix for the 3 axis using sums of binary-split increments of rotation from within a look-up table instead of raw cos/sin works much more effectively.
Sorry, but I don't understand what you're trying to tell me.
I'm using precalculated (co)sine tables, and the trigonometric product rules to avoid multiplications, if that's what you mean. At any rate the whole thing is running in less than 500 cycles for 16-bit precision so it's not really a bottleneck anymore.
beyond that, if you decide to implement textures, i highly advise to not take perspective into account for textures and simply render them as if they were an orthogonal re-orientation of each triangle, as the NES would suck CPU cycles like crazy taking that into account.
Right, no.. Just plain flat-shaded polygons for me. I don't even want to think about how slow texture mapping would get..
my advice for perspective is to use exponential projection as i described here:
http://nesdev.com/bbs/viewtopic.php?p=32745#32745

i only left out of that description that is best to simplify the look-up table so that only each depth plane is used in which the scalar comes to a full integer when translated.
Again, I don't quite follow you. However I am using logarithm and exponential tables for the perspective division.

Posts: 7990
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland
There is just one thing with XOR flling... The way you described it at least :
- Two vertical consecutive pixels should never be both set, as it would normally be with all lines where dy>dx
- All hidden lines should effectively be hidden, else they'll affect the filling
- No polygon should be on the top of the screen else the whole culumn will be inverted.

Did I get it right ? I'm not the one using it anyway, but I guess it's kind interesting. And congratulations for your multiplication matrix. Mastering trigonometric identities (there is hundred of them !) is necessary to speed things up.

doynax
Posts: 162
Joined: Mon Nov 22, 2004 3:24 pm
Location: Sweden
Contact:
Bregalad wrote:There is just one thing with XOR flling... The way you described it at least :
- Two vertical consecutive pixels should never be both set, as it would normally be with all lines where dy>dx
- All hidden lines should effectively be hidden, else they'll affect the filling
- No polygon should be on the top of the screen else the whole culumn will be inverted.

Did I get it right ?
Yeah, that's pretty much it =)
The top edge is usually handled by drawing a horizontal line along the clipped part of the polygon. Naturally you wouldn't draw anything when clipping the sides or bottom though.
I'm not the one using it anyway, but I guess it's kind interesting. And congratulations for your multiplication matrix. Mastering trigonometric identities (there is hundred of them !) is necessary to speed things up.
I'm just surprised that I've never seen that trick before, but presumably everyone is using floating point these days so the multiplications don't matter.
Another neat application of the same identities is to easily generate sines waves of different amplitudes from a single table. It's the sort of trick that might save you some ROM space if you're working on a 32k game ;)

Posts: 7990
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland
I'm just surprised that I've never seen that trick before, but presumably everyone is using floating point these days so the multiplications don't matter.
Yeah, but one day will come where the power of consummer electronics will stop to double each year, but the demand will continue to increase as usual, and this may happen sooner than what some belive. That day, people that know little dirty tricks will be able to survive fine, but people who grown used to apparently-clean-but-in-reality-dirty very high level language will be screwed and will break down.
Another neat application of the same identities is to easily generate sines waves of different amplitudes from a single table. It's the sort of trick that might save you some ROM space if you're working on a 32k game
Yeah, if I were to do such a trick the first idea I'd have would be to use shift instructions to get multiple of the table entries.

Anders_A
Posts: 88
Joined: Mon Nov 27, 2006 11:56 pm
Location: Sollentuna, Sweden
doynax wrote:Behold!
Wow! That's amazing. If you get that thing to run on a real NES it'll be the coolest thing made for the NES to date.

I find the distorted perspective cool. 3D on retro machines is usually very "vanilla", and it adds a bit of flavour. I'd love to see a version with one palette entry reserved for each of the visible faces of the cube and a nice color ramp for shading.

I've been thinking about doing something like this, but considering all the tricks you've mentioned in this thread I never thought of and the speed you got it running at there is no chance in hell I would have been able to pull it off.

Kudos!

thefox
Posts: 3141
Joined: Mon Jan 03, 2005 10:36 am
Location: Tampere, Finland
Contact:
Very cool! Nice to finally see some real progress in the NES demo department If you need help debugging it so it works on the real deal, I might be able to help (I have a PowerPak and decent amount of NES development experience).
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi

jargon
B&: This is not your blog
Posts: 208
Joined: Fri Dec 07, 2007 11:40 pm
Location: 480/85260
Contact:
this is my goal with my game engine:

Cheers,
Timothy Robert Keal alias jargon

Miser's House Anthology Project

doynax
Posts: 162
Joined: Mon Nov 22, 2004 3:24 pm
Location: Sweden
Contact:
Lately I haven't been working as much as I might have on this. But at least I've reworked the transformation code for better precision, added a couple models and fixed a few bugs.
Anders_A wrote:I'd love to see a version with one palette entry reserved for each of the visible faces of the cube and a nice color ramp for shading.
I'm working on it but updating the NES palette wasn't as easy as I thought it'd be. Apparently it has to be written during hblank or the true vblank period, not just in a blanked part of the screen.
Anders_A wrote:I've been thinking about doing something like this, but considering all the tricks you've mentioned in this thread I never thought of and the speed you got it running at there is no chance in hell I would have been able to pull it off.
I may have made it seem harder than it really is, you know.. ;)
thefox wrote:If you need help debugging it so it works on the real deal, I might be able to help (I have a PowerPak and decent amount of NES development experience).
I'd love to have your help with testing it on hardware. There's still a quadrillion emulator-visible bugs left to deal with but I'll send you a PM (or something) when I get around to writing some test ROMs.

I'm still searching for a musician by the way, or just a donation of an unreleased tune for that matter. Any ideas where I might find such a creature?

Posts: 7990
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland
Honestly, your third demo is amazing, way better than the other 2. Seeing all regular polygons fitting a simple demo like this is amazing, and it actually looks 3D unlike the other two.

And yeah palette have to be uploaded during VBlank. Memblers and I tried to upload it during HBlank, but even for changing only color 0, this is a lot of bothering and while it's fun to deal with this, in the best case you see glitches on the rightmost 16 pixels or so.
Useless, lumbering half-wits don't scare us.

hap
Posts: 355
Joined: Thu Mar 24, 2005 3:17 pm
Contact:
Yeah, looks good
as for the music, you could ask on the NES Music subforum.

Celius
Posts: 2157
Joined: Sun Jun 05, 2005 2:04 pm
Location: Minneapolis, Minnesota, United States
Contact:
Yes this looks very good. However, there's still some weird distortion for the triangle faced ones.

And I didn't know you couldn't update the palette in a blanked period of the screen. What happens if you do?

Zepper
Formerly Fx3
Posts: 3221
Joined: Fri Nov 12, 2004 4:59 pm
Location: Brazil
Contact:
doynax, you're pretty impressive, my congrats dude! Awesome work, it's a cool 3D demo!

By the way, what unofficial opcodes do you use?

doynax
Posts: 162
Joined: Mon Nov 22, 2004 3:24 pm
Location: Sweden
Contact:
Bregalad wrote:And yeah palette have to be uploaded during VBlank. Memblers and I tried to upload it during HBlank, but even for changing only color 0, this is a lot of bothering and while it's fun to deal with this, in the best case you see glitches on the rightmost 16 pixels or so.
I only need to update three colors, and it did seem to work fairly well for me. By initially placing the PPU address at \$3f00 and then writing the other three entries in rapid succession (i.e. preloading values into A/X/Y and using an indexed dummy read to skip over the background color) the "buggy" span is reduced to nine clocks plus whatever variance you've got in your synchronization method. The annoying part is that Nestopia and Nintendulator set the sprite overflow flag at very different parts of the scanline (and I wouldn't be the least bit surprised if real hardware is different still), so I'd have to use some other timing mechanism to get hblank uploads to work.
At any rate I figure it just isn't worth the compatibility nightmare since splitting up the character upload loop and inserting the palette code somewhere in the middle would work nicely, it'll just mean a shitload of extra work for me..
Celius wrote:Yes this looks very good. However, there's still some weird distortion for the triangle faced ones.
I know.. I'll just have to tweak the tetrahedron and octahedron someone without sacrificing the depth for the rest of the models. Not that there's anything wrong with it per se, the objects are just very large and/or very close to the viewer.
Celius wrote:And I didn't know you couldn't update the palette in a blanked period of the screen. What happens if you do?
When you point the PPU at the palette RAM it decides to render the palette entry it's currently hovering over for some reason.
Sometimes I wonder whether at some stage the NES design team sat down and brainstormed how to create the nastiest, most insidious system ever for writing raster code..
Fx3 wrote:By the way, what unofficial opcodes do you use?
Lets see.. There's LAX, SAX, SBX, DCP, ISC, ASR, ARR, ANC and a few illegal NOPs. That ought to about cover it I think, but I wouldn't be too surprised if an immediate LAX or SLO/SRE/RLA/RRA instruction snuck in there as well. Plus the halt instructions for debugging of course but that doesn't really count.
If you're trying to decide which instructions to implement in your emulator then I suggest supporting everything except perhaps for the unstable ones (though even those have occasional uses). With some decent documentation and a good sample implementation (VICE for instance) it shouldn't take too long.

Anders_A
Posts: 88
Joined: Mon Nov 27, 2006 11:56 pm
Location: Sollentuna, Sweden
doynax wrote:The annoying part is that Nestopia and Nintendulator set the sprite overflow flag at very different parts of the scanline (and I wouldn't be the least bit surprised if real hardware is different still),
You really need to test on the real NES as there are no emulators as accurate as those for the C64. I have my copynes stashed away at the moment, as I didn't want to have an extra computer set up just for the compatible parallell port, but I just ordered an USB copynes. I'll be glad to help you test stuff out when I get it. It'll be PAL only though.
doynax wrote:Sometimes I wonder whether at some stage the NES design team sat down and brainstormed how to create the nastiest, most insidious system ever for writing raster code..
Yeah, that truly sucks. You can't do much more then scrolling or changing the color emphasis bits.
Lets see.. There's LAX, SAX, SBX, DCP, ISC, ASR, ARR, ANC and a few illegal NOPs. That ought to about cover it I think, but I wouldn't be too surprised if an immediate LAX or SLO/SRE/RLA/RRA instruction snuck in there as well. Plus the halt instructions for debugging of course but that doesn't really count.
If you're trying to decide which instructions to implement in your emulator then I suggest supporting everything except perhaps for the unstable ones (though even those have occasional uses). With some decent documentation and a good sample implementation (VICE for instance) it shouldn't take too long.
Are you certain all of these work on the NES? the NES cpu is a modified 6502 after all. Couldn't those modifications alter the behaviour of the undocumented opcodes?

tepples
Posts: 22160
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:
I seem to remember reading that the only modification from the original 6502 to the 2A03's CPU core was erasing the part of the chip that had the decimal mode circuitry, as Ricoh couldn't afford to license that from MOS Technology. That wouldn't have changed the values of the don't cares in the decoder gate array, which is where most of the extra instructions come from. But anything that involves \$EE or \$EF or \$11 or other values where bit 4 is prominent might have changed behavior, as those values seem to originate from decimal mode.