Sunday, August 20, 2006

Triangle Clipping

After Wednesday's news I wanted to keep everyone up to date with what I've been working on over the past few days.

With Wednesday's changes incorporated, I reprofiled a few roms to see where most of the CPU time was going. Things have changed considerably since I initially talked about deciding what to optimise. Looking at the profiler for Mario 64 the time spent executing display lists is now a much more significant fraction of the total time spent on each frame. Back around R3/R4 only around 20% of the time was spent here. With the latest build display list processing now accounts for around 35-40% of the time. The display list processing hasn't become any slower, it's just becoming more significant as I've optimised the CPU emulation.

One of the settings I mentioned was worth disabling for a speed boost when I released R7 was the 'Tesselate Large Triangles' option. When this setting is enabled, it causes the display list processor to recursively break up large triangles into smaller pieces. This has been necessary to overcome the PSPs poor hardware clipping support; without breaking the triangles up into smaller pieces, the PSP will often fail to render large triangles as shown below:

Super Mario 64 without clipping
Super Mario 64 without clipping


The large triangles that make up the floor that Mario is standing on are rejected by the PSP, leaving a large hole where the floor should be. By breaking the triangles into smaller pieces before attempting to render them, it reduces the chance that the PSP will decide to discard them.

There were a few problems with the 'Tesselate Large Triangles' setting which I've been working on overcoming this weekend. Firstly, it's not perfect - there were plenty of cases where visible triangles would still be culled even when they had been subdivided 3-4 times (which generates 27-81 triangles for each input triangle!). This was always quite noticable in games with a relatively low camera, such as racing games. The other big problem with this setting was that it was very slow - often adding over 20ms per frame.

This setting was always intended as a quick fix rather than a long term solution, so I've been looking at fixing both of these problems over the past few days. I started by ripping out all the exisiting polygon clipping and tesselation code and starting from scratch. After a couple of days of hacking I've finally got a replacement system that seems to be clipping everything I've thrown at it perfectly. Here's a shot of the same location in Mario 64:

Super Mario 64 with new clipping code
Super Mario 64 with new clipping code


Now that I have a working version of the code in place, I'm going to look at optimising it. At the moment the new clipping code is roughly as expensive as the tesselation code, but due to the way it's implemented I think it should be much easier to make work with the PSP's VFPU, as I can process batches of vertices in parallel. Ideally I'd like to get this change into the next release, so I'm going to hold off putting the R8 build together until it's ready. I'll let you know how I get on.

-StrmnNrmn

33 comments:

StevIEmw said...

wow,i didnt know the triangle thingy did that! thanks for keeping us updated

Mario Kart God said...

So does this mean it would also help out Mario Kart with this subject?

BHSPitMonkey said...

Fascinating post as always. I look forward to every new release from you.

Morgan said...

So if I understand correctly now we get the same speed boost from this setting except we get better graphics (actually still alot like the normal settings). With this new code do we get a bigger speed boost than the old code or is it just the same? Thanks StrmnNrmn for the update I really appreciate it and just release R8 when your ready man, but things are really looking great!

Chaz said...

Wow great work with the new clipping code.

and 'mario kart god' stop bugging StrmnNrmn about mario kart he will get to it in good time.

salomon st said...

yes!!!!!! it will be much better to show off now!!!!!!

stee said...

Great work so does this mean that other parts in mario are fixed which have similer problems

E.G: at the start of mario 64 when the camera man is shown flying over the water outside the castle the water disapears.

Tinnus said...

morgan: that's wrong. The 'normal' is Tesselate Tris OFF. Tesselate Tris is an extra step done to prevent some polygons from disapeearing. He just replaced that with a more effective method.

Morgan said...
This comment has been removed by a blog administrator.
Morgan said...

Oh okay I get it now nevermind.

wally*won_kenobie said...

Good to have someone who knows his stuff here tinnus :)

Strmnnrmn: Good going for the update, BTW did you get my email?
I have encounted a few games not working as they should be.

Ok people now its time to allow people to enjoy full speedness.
1. Extreme-G
2. Forsaken
and the bust a move games
are close to or full speed

Enjoy!

Steven said...

StrmnNrmn, your posts facinate me almost as much as your coding talent. Great news! Can't wait for R8! keep working hard

RetroGamer said...

This is awesome! Hey StrmnNrmn! Is it possible for you to add polygon clipping for far away polygons so the framerate is faster? The reason why, is because I got to Bowser's sub which is past the 30 star door in the basement of the castle and the emulator will go to a steady 20fps at the beginning of the tunnel, and then to about 6-9fps once mario has swam halfway through the tunnel. The reason why is because the 'game' itself will render the next room with Bowser's sub and it adds a lot of overhead. Anyway, thanks for Deadalus64! It's awesome! Will sound be in Release 10?

salomon st said...

honestly does sound really matter?!? itl just slow everything down so u can hear ringtone like music i mean wats the point...also has n e one gotten turok to run??

wally*won_kenobie said...

salmon st:
Sound wont slow anything down as it will be in the ME

Chaz said...

Retro, I think that sound is going to be farther off then R10 and anyway it will reduce fps too much to be worth it (at least for the fist sound release).

I would say around R12-14 because adding an in game menu will at least one release and there is still error fixing, optimizing and adding other options.

KELVIN said...

hey guys ive always visited this website, ive decided to post today cause it seem that i made a save file for zelda ocarina of time, when i play the safe data he starts inside the great tree. i cant go farther because when i throw myself of the top and land on the web, it frezzes cause the water below is a blue texture. anyone got past this part and how?

wally*won_kenobie said...

That problem will probably be fixed in R8 with the new triangle clipping

salomon st said...

how do u save in oot on here i make a save file and i save after i get my sword and when i exit the game then re enter my save isnt there

KELVIN said...

SALOMON:well i was running i think it was tannis or the one i found in psp-hack version of the emulater, then i saved after i got the shild and sword, u gana have to save 3 times in a role, then it will be save. it saves to a file called zelda 64.sra. when i switch back to r7 the save file is still there :)

PSDroideka said...

StrmnNrmn: Good to here! Just a few questions.
1)Have the people who made optimisations on top of your "one line change" given you their source for the changes?
2) Could it be that frameskip doesn't optimise framerate but just the physical speed? That seemed to be the case.
3) Would it take long for SRAM to be fixed so Zelda OOT could be saved? If it would i'm ok with it being a later release (not so sure about sroon though :)

Sroon said...

Nah I can wait! (i guess) its just I got inside the Deku tree and I wanted to go further!
lol!
oH YA AND THE EXPASION PACK!
PAYPAL!

Morgan said...

Calm down guys I'm sure StrmnNrmn will do all he can to help us out but he does have optimizations he wants to incorporate into the next release. Just give him space and time and he'll have this emulator running great! Keep up the amazing work StrmnNrmn and R8 should be very interesting if you get the ingame menu going.

PSDroideka said...

Mario Kart God: Yes this should solve the "choppiness" in Mario Kart because it seems to be caused by untessalated triangles that seems to only render as your leaving that area behind so the game skips as it stops to render the triangles.
Correct me if i'm wrong

StrmnNrmn said...

Sorry I've been neglecting the comments pages over the past couple of posts. When I see 100+ comments I end up feeling quite overwhelmed and not quite sure where to start!

mario kart god: Yes - it helps every rom.

morgan: The new code gives better graphics (much, much better in some cases) and it's also significantly faster than the 'tesselate large triangles' setting (in fact, it's almost as fast as having that setting disabled entirely).

stee: Yes - Mario 64 looks almost perfect now (with the exception of a few places that use mirrored textures.) This should fix the graphics in all roms where large gaps were appearing because polygons weren't being drawn.

wally*won_kenobie: Hiya. Sorry, I haven't checked my email since before the weekend. I have Outlook set up to get all my messages from gmail, and I've not installed that on the new pc yet. I'll get back to you ASAP.

retrogamer: The new clipping code is a lot more efficient at rejecting geometry that's out of the n4's view frustum (i.e. the visible area on screen.) To be honest I'm not sure that the slowdown will be entirely due to this - it's more likely that the CPU emulation is doing a lot more work at this point for some reason. We're not quite ready for sound yet, maybe another couple of releases I think.

psdroideka: 1) As I mentioned above I've not been able to check my email for the past few days, so I don't know yet. 2) It all starts getting confusing when you start talking about frameskip. As I see it the n64's apparent framerate will increase (because every other frame takes 0ms to render), but the psp's framerate will effectively be reduced (as it's doing twice as much CPU work between rendering each frame.) The main question is whehter it feels any better to play or not. 3) Yeah, I'll look into this. I'm planning on taking a good look at the whole savegame system very soon (i.e. R9 or R10)

psdroideka: I actually had a look into why Mario Kart is so choppy. I don't think it's anything to do with the clipping, I think that just makes the problem look worse than it is. Normally, a game will do the following:

Render DList
Flip screens
Render DList
Flip screens
Render DList
Flip screens

It seems that for some reason MarioKart gets a bit out of synch:

Render DList
Render DList
Flip screens
Flip screens
Render DList
Flip screens
Render Dlist
Flip screens
etc

In this example it renders two frames, then flips the display twice. This effectively means that it ends up showing the same frame multiple times, before suddenly catching up, which is causing the choppiness. I've no idea why this has started happening now - I'll have to look into it further.

Chaz said...

"I'm planning on taking a good look at the whole savegame system very soon (i.e. R9 or R10)"
Ya i have been having some saving issues mario 64, so i would be very happy if R9 had a In-game menu and have saving looked at. :D

drew4237 said...

Yeah it is looking better but i cant wait for the release. i would like sound eventually but it isnt that important.

cashvegas said...

I have downloaded the recent R8 version but there does not appear to be any sound. Is that supposed to be the case? thanks

cashvegas said...

I have downloaded the most recent version but there does not appear to be any sound is this supposed to be the case?

cashvegas said...

I have downloaded the most recent version but there does not appear to be any sound is this supposed to be the case?

cashvegas said...

Is there supposed to be sound with the most recent version as I dont seem to be getting any sound?

ExtraKrispy said...
This comment has been removed by a blog administrator.
ExtraKrispy said...
This comment has been removed by a blog administrator.