3D on the Sega Genesis is possible

[gasega68k]

I created this thread to show some 3D demos I've done. The first will be a demo of Starfox, I started doing for about 2 years, although not very optimized, routine filling polygons is a bit slower than the demo did Stef.
This is the link to download it:
http://www.mediafire.com/download/7z..._starfox3d.rar

[Yharnamresident]

Runs a little smoother than Stef's, but you gotta play in a tiny window.

[Stef]

Haha it's just amazing !! Actually your version is a lot faster than the one i posted sometime ago
Of course i know my version could be faster today with my last 3D maths code and rendering code and by optimizing the whole structure but still i am *very* impressed by what you achieved ! It's really really smooth given the number of objects you are drawing ! So definitely it's really possible to achieve something close the SNES version without any enhancement chip, thanks to the 68k blast processing

[Stef]

Runs a little smoother than Stef's, but you gotta play in a tiny window.

Actually it is the same resolution, i only used the H32 mode of the MD so it stretch the image !

[Vector2013]

OP version.



I hope stef and op get together to create a starfox md classic. Joe should be aware of both versions or possible collaboration for his GS video.

[TmEE]

This is really great, and full 3D rotation, no on rails !

[Stef]

And it has texture mapping

[gasega68k]

Stef, I was counting the number of cycles in my routine rotation and projection, and is practically the same as in your case: about 1200 cycles (70 cycles for MULS).
I was watching The polygon fill routine in your case (bmp_a.s) is a bit faster than my demo.
To calculate the edges of the polygon, I do not use any division, instead, I made a table of division of 1 / n (it is actually 65535 / n), in fact the only part I use division is the rotation / projection.

And it has texture mapping

Yes, the average cycles to draw each pair of pixels is about 38-40 cycles.

[Stef]

Import posts from Wolf3D demo topic :

Just to give you an idea where i am with that:

- SGDK is able to transform about 10000 vertices / second (3D rotation+translation and the 2D projection).
That give a maximum of 500 vertices per frame for 20 FPS refresh rate but that is if you only do that, without any rendering or anything XD
And when you manipulate objects, many overheads comes, you need to setup severals contexts, combine transformations... so the usable and realist performance is lower than that, i guess we can probably use scene with a maximum of 100 to 150 vertices per frame. Note that these are numbers for real and complete 3D transformations and maybe we can find trick to only do partials transformations when this is possible. For instance the Starfox case does not need any rotations for world (only for objects).

- The polygon filling code is fast too but i can hardly give an estimation about the fillrate. It really depends from the size of the polygon, the clipping overhead and others stuff. Tiny polygons are time killer as you process many things to finally render very few pixels...
I guess in ideal case (large or very large polygon) the fill rate can be up to 5 MP/s (very rough estimation) but reasonably i think 2 MP/s is a better average estimation. If we take the base resolution : 256 * 160 = 40960 pixels that means we can fill the whole screen about 50 times per second without overdraw... Of course again that is very dependent from polygons size.

Reality now is that we have to share the CPU time between others heavy tasks as well :
- Transfer and convert the main memory bitmap buffer to video memory tiles.
- Clear bitmap buffer at each frame.
- Game logic, 3D collisions...

For the transfer and conversion, i am doing it on the 68k. I would really like to find a trick in tilemap arrangement and bitmap rendering to be able to use the DMA here, that would give an important speed boost (factor > 2x). Currently the transfer and conversion code eat all the blank time which represent almost 40% of the total CPU time !
Also the clear bitmap operation eats many 68k cycles, i tried to implement a Fast Fill Bitmap mode sometime ago which was really nice for fast clear operation but the drawing part brings so much overheads that it ended by being too complex and slower than optimized "brute force" classic rendering :-/

Wow , that's a lot of information Stef .
Well, for the rotation and projection , from what you say I think your code is faster , but in my case I can tell you in terms of cycle count is close to 1000 cycles per vertice ( depends on multiplications ) .
The polygon filling code , I can tell you also in terms of cycles is around 722 cycles per line in the worst case (large polygons) , and about 266 cycles in the best case (small polygons) .
I've done demos with 256 * 128 and 256 * 160 , in fact the demo starfox I did use 256 * 160 as in the demo you did , but I use the resolution of 320 * 224 with a "window" of 256 * 160 .

To transfer to the VRAM I either use DMA because the bitmap buffer is not organized to be able to use the DMA , but I use a little trick to transfer the bitmap buffer as fast as possible to the VRAM , this is what I do: first I separate into small blocks of 1k bitmap buffer ( for 256 * 128 there are 16 blocks and 256 * 160 there are 20 blocks) , so when I go to move to the VRAM each of these blocks , I first read the Vcount to see if we are in the space of " blanking " ( 256 * 160 would have 102 lines of " blanking " ) , and if there is enough time to transfer one of these blocks of 1k ( about 11 lines would be needed ) , then I disable the video, to transfer to the maximum speed this block and then I enable the video again, but if there is not enough time , I did not disable the video and this block will be transferred slower.
To clear the buffer , I use MOVEM instruction , it takes about 74 lines in 256 * 128 mode and about 92 lines in 256 * 160 mode .
I 'm sure I can improve the code for filling polygons , and the code for the rotation and projection .

I'll create a new thread in a few hours , to show some of the demos I have done, the first will be the demo of Starfox .
The first version I did of this Starfox was in October 2011 and the last modification I did was in June 2013 , but this demo is fully done in 3d , ie can move to any direction.

I tried to count the number of cycle taken by my 3D transform methods and i obtained 814 cycles just for the vertex transformation and almost 400 cycles for vertex 2D projection which is actually more than yours ! But i counted 70 cycles for MULS instruction and 160 cycles for DIVS which is pessimist and probably more than the average case (actually it is as i benchmarked about 10000 vertices transformed per second which mean close to 800 cycles instead of the 1200 counted here).
You can see the source here : https://code.google.com/p/sgdk/sourc...rc/maths3D_a.s

About the polygon filling, i tried to do the count on a per line basis. I think i have a minimum of 250/300 cycles per line and maximum of 650/700 cycles... It's funny to see we have really close numbers here, i guess our code are somehow similar
Same for the bitmap clear stuff, i heavily used the MOVEM instruction to make it as fast as possible.
Again, you can see the code here : https://code.google.com/p/sgdk/sourc...nk/src/bmp_a.s

I think that there is no way to use the DMA for the transfer as it seems you cannot use it neither, or not without heavy changes in the bitmap rendering code.
I'm also using the extended blank area to transfer to VRAM at full speed (at least, full 68k speed). It's why the Bitmap engine use 256x160 resolution, i actually split the transfer on 3 frames in NTSC and 2 frames on PAL systems which also mean you are limited to maximum of 20 FPS for NTSC and 25 FPS for PAL.
See the bitmap engine description for more details in the bmp.h header file :
https://code.google.com/p/sgdk/sourc.../include/bmp.h

Funny enough it seems we done very similar stuff after all, i'm not the only crazy guy attempting doing 3D on the Sega Genesis
I'm really impatient to see your own starfox / 3d demo stuff by the way

[Stef]

Stef, I was counting the number of cycles in my routine rotation and projection, and is practically the same as in your case: about 1200 cycles (70 cycles for MULS).
I was watching The polygon fill routine in your case (bmp_a.s) is a bit faster than my demo.

Oh ok, it's really fun to see how much we are close in term of performance... but that probably mean we cannot get that much faster now except by using some heavy hacks methods (3D calculation approximations and/or double pixel rendering...) :-/

To calculate the edges of the polygon, I do not use any division, instead, I made a table of division of 1 / n (it is actually 65535 / n), in fact the only part I use division is the rotation / projection.

If you do not use any division for the edge calculation, it means you use a multiplication by the inverse then right ? I tried to do that but got some problem with loss of precision... I should revisit this solution.
Anyway in general i am really not happy with the polygon clipping and edge calculation code, it is insanely complex and probably not that fast... but i already spent many time on that
Also having to fill left/right edge array then doing horizontal fill between these 2 edges do not look optimal, it would be better to keep left & width couple in live registers but of course we are quickly running out of registers then.
Also handling polygon nibble border waste a bunch of cycles too.
Anyway good to share that technicals aspects with someone doing almost the same

Yes, the average cycles to draw each pair of pixels is about 38-40 cycles.

38-40 for pixel pair in texturing sounds really nice ! Indeed it do not slowdown much the rendering... It's really impressive to see how close you are from the original Starfox in term of performance. Of course it still miss a lot to make a complete game, but the real starfox is on rail which make clipping far easier to handle, you can even restrict the world transformation for static objects (but maybe it does not deserve the added complexity overhead to handle it)... and honestly the rest is almost nothing compared to what the 3D transformation and the rendering eats !

[saturndual32]

stef and gasega68k, you guys ROCK!

[gasega68k]

If you do not use any division for the edge calculation, it means you use a multiplication by the inverse then right ?

Yes, the method I use to draw polygons is based on this:
http://www.mediafire.com/download/lz...u6tr71i/cube.c
It is a demo for gba, I found on the PDROMS page some time ago.

I first did the calculations for the polygon edges so:

    move.w  d1,d5   ;y2
    sub.w   d0,d5   ;y2-y1
    move.w  d2,d4   ;y3
    sub.w   d0,d4   ;y3-y1
    move.w  d2,d6   ;y3
    sub.w   d1,d6   ;y3-y2
    move.w  d6,($ff0400)
    swap    d0
    swap    d1
    swap    d2
    move.w  d2,d6   ;x3
    sub.w   d1,d6   ;x3-x2
    move.w  d6,($ff0402)
    moveq   #00,d6
    tst.w   d4      ;y3-y1
    beq     Lzero
    move.w  d2,d6   ;x3
    sub.w   d0,d6   ;x3-x1
    ext.l   d6
    lsl.w   #8,d6
    divs    d4,d6   ;((x3-x1)<<8)/(y3-y1))
Lzero:
    moveq   #00,d7
    tst.w   d5
    beq     Rzero
    move.w  d1,d7   ;x2
    sub.w   d0,d7   ;x2-x1
    ext.l   d7
    lsl.w   #8,d7
    divs    d5,d7   ;((x2-x1)<<8)/(y2-y1))
Rzero:
    ext.l   d6
    lsl.l   #8,d6
    ext.l   d7
    lsl.l   #8,d7
    move.l  d6,a2          'L
    move.l  d7,a3          'R

And then modify it like this:

    move.w  d1,d5   ;y2
    sub.w   d0,d5   ;y2-y1
    move.w  d2,d4   ;y3
    sub.w   d0,d4   ;y3-y1
    move.w  d2,d6   ;y3
    sub.w   d1,d6   ;y3-y2
    move.w  d2,($ff0408)    ;y3
    move.w  d6,($ff0400)    ;y3-y2
    swap    d0
    swap    d1
    swap    d2
    move.w  d2,d6   ;x3
    sub.w   d1,d6   ;x3-x2
    move.w  d6,($ff0402)

    move.w  d2,d6  ;x3
    sub.w   d0,d6  ;x3-x1
    add.w   d4,d4
    lea  tabladiv,a4
    muls   0(a4,d4),d6        ;L = tabladiv[y3-y1] * (x3-x1)

    move.w  d1,d7   ;x2
    sub.w   d0,d7   ;x2-x1
    add.w   d5,d5
    ;lea  tabladiv,a4
    muls  0(a4,d5),d7         ;R = tabladiv[y2-y1] * (x2-x1)

    move.l  d6,a2          ;L
    move.l  d7,a3          ;R

[Stef]

Yes i see the idea, as i am always working with my fix16 type i probably messed up something...
By the way, are you doing triangle drawing only or you allow to have more than 3 points in your polygon ?
I though than handling N vertices polygon would be better as you only calculate one left and one right edge compared to triangle rendering but it make the clippings and pre process a lot more complexe ! Maybe it was not a good idea after all...

[john8248]

stef and gasega68k, you guys ROCK!

This x 1000. Amazing stuff!

[FuturePrimitive]

That demo is just mind boggling. Our good old Genesis is really pulling this off unassisted! Could a full game be possible?