Jo Engine Forum

Sega Saturn Development => Share your code => Topic started by: XL2 on July 21, 2017, 08:57:49 pm

Title: 3D Map tool + FPS demo
Post by: XL2 on July 21, 2017, 08:57:49 pm
Hi all,

I wrote a little tool to convert a level's polygons into bounding boxes (axis-aligned).
It merges the bounding boxes (BB) with their neighbour to reduce the amount of boxes.
It also calculates the slopes on one axis (x or z), but it doesn't generate the heigth masks yet (on my to do list).
It will be complicated to explain as I didn't add an example (on my to do list), so read carefuly and don't hesitate if you have questions.

Ok, now for the explanations (I'll try to explain, but I hope you guys will understand)

The idea is like this : you use a function similar to the Jo_intersect, but add the z axis... or just do 2 jo_intersect and replace the x with the z value for the second function.
Do 2 or 3 collision checks (x/z and y, or x and z and y - I suggest you go for 3)

If the collision mask value is -1, then just use it as is : you have a collision and just stop the movement on that direction.

If the mask is 0 or higher, then you just do a lookup in an array of values. The arrays I use are only 2 dimensions (because of memory constraints), but you could do 3 dimensions arrays as well for hills and other shapes.

Example : You know you have a slope if the rotation value on the x-axis isn't 0. So you look for a mask.
As an example, for a 45 degrees slope on the x-axis, your slopeRXangle will be 45 (or -45 depending on the direction).
So you look for the heigth mask returned by the function, and you look it up with your current Z position (not x since the axis of rotation is on the x axis - look for z as you go up or down on the slope), which will return a heigth value.

So let's say your relative Z position to the current BB is 100, and the BB has a length of 200.
Look at the array at position 100 (your z position minus the BB minimum z position), which will return a heigth value.

Just look for that value added to the minimum Y value of the bounding box to see if you have a collision (like, the minimum Y of the BB being -200, Y length being 200, and the heigth mask returns 100, so you look to see if you currently have a collision for an object with Y values ranging from -100 to 0)
Do another intersect check with your current Y value, if there is a hit, return it, else there is no collision.

This way, you can have smooth slopes with very little CPU usage. An it works for all 3 axis collision checks.
I need to improve my code to better merge the BB together and improve memory usage and CPU usage.
If you have a slope with side walls (looking "out" of the slope), you will hit an invisible wall as it won't merge them and it will cover your slope.
Just remove these walls for now and only keep the "ground" part (you might have to manualy ajust the heigth as well in the resulting file)
I didn't do much testing, so there might still be bugs I haven't found.

I'll also share my collision code at a later date, but right now I'm pretty much rewriting many parts of it so it's far from complete.

Hope this helps someone creating a 3D game!

EDIT : I added another version of the collision tool (still not good enough, it's buggy with slopes)
EDIT 2 : Added a function to write using Danny's code, but it's not 100% complete (WIP). Also got rid of the need to link to SGL.h, if it's causing issues make sure you tell me as I didn't test properly. I also quickly coded a .Obj exporter to Danny's code, but I didn't test it. Some stuff is wrong for sure and it might not work with all .Obj formatting, I will have to spend more time on this.
EDIT 3 : Added reading .OBJ files and binary file output. The FPS demo now uses the binary file format to load maps. I will add more features to the binary format.
EDIT 4 : Many bug fixed such as unaligned read/write, issues with multiple meshes. The .OBJ to binary seems to work fine now, tell me if you have issues. I also added basic view frustum culling to the FPS demo, put a HUD using Jo Engine functions (causes issues with other VDP2 functions, just uncomment other lines to revert to the RBG0 plane), removed the gouraud shading depth (made the game way too slow on real Saturn).

EDIT (2017-08-16) : Upgraded to Jo Engine 9.0 (make sure you upgrade also). I also fixed the memory allocation, so you should be able to load much bigger files now (try map 3 to see).

EDIT (2017-08-25) : You can now write textures directly in the binary file. The map program will read TGA textures (uncompressed only) and write them. Also added auto-subdivision of the map for culling, you just need to specify how many "cuts" you want (there is a bug that will sometimes "lose" polygons, so just try different values for "cuts" (x, y, z axis) if one setting doesn't work well). I also changed the FPS demo's collision code to reduce CPU usage.
Title: Re: Collision BB generator (WIP)
Post by: XL2 on July 26, 2017, 12:43:57 am
Ok, as promised, a small demo (source code attached here) with a simple 3D collision engine.

I haven't spent much time on this, so it's buggy and far from perfect, and isn't modular enough.

I wanted to use the smooth control made by Danny, but I just used a 2-axis system for straffing and really didn't do much control-wise.

So, don't go burn this for your Saturn expecting a Quake-killer or Lobotoby software quality!
That being said, it should still be better than the SGL FPS demo (which had terrible collision detection).

Ingame : D-Pad for turning and going forward/backward, L/R for straffing and B for jumping.

The collision generator tool worked well for the Sonic level I tested, but it didn't work well with the small level I made for this demo (the slopes had problems, getting merged with other BB). I will have to improve the tool and share it again here once I do.

EDIT : Moved the file to the first post. I also added the map changing functions which now reads the binary file format (press L or R + start to switch maps)

Video here :
Title: Re: Collision BB generator (WIP) + FPS demo
Post by: mindslight on July 26, 2017, 08:33:49 am
Nice demo  :)
This should help people to start an fps style game
Title: Re: Collision BB generator (WIP) + FPS demo
Post by: Danny on July 28, 2017, 05:17:31 pm
I'm sharing a modified version I made of the "Advanced 3D" that loads the mesh from ROM to RAM using direct memory access instead of a static allocation.
This requires a little bit of knowledge of pointer arithmetic but is worth the effort because it makes loading different meshes easier. The same approach can be used to load other stuff so I guess it's also a good starting point to learn.
I made this to help our friend XL2 with his game and he will be incorporating this on his great tool, but for now I thought it would be nice to share this with all of you in case you are curious :P.
Title: Re: Collision BB generator (WIP) + FPS demo
Post by: XL2 on July 28, 2017, 05:30:05 pm
Like usual, thank you and amazing work Danny! I integrated your smooth FPS control in the FPS demo.
I didn't make a video of it, but you can see I updated the video in the previous post to show what it looks like with a VDP2 plane (with transparency), and I think it shows how much potential the Saturn has for beautiful effects!
I'll try over the weekend to update the collision tool to output .h files compatible with the format you made and integrate that in the FPS demo as a starting point for others.
Title: Re: Collision BB generator (WIP) + FPS demo
Post by: Danny on July 28, 2017, 05:58:28 pm
You have been making a really wonderful job, your effort and dedication are inspiring!
I really like your videos, they show your progress from scratch and the evolution you have been having since the beginning.
It makes me really glad to see all the little bits of stuff I have been making put to good use ;D which makes me want to help out even more!
Title: Re: Collision BB generator (WIP) + FPS demo
Post by: XL2 on July 28, 2017, 10:55:40 pm
Your contribution is highly appreciated!
I will improve the FPS demo (and tool) to work with the mesh loading you wrote.
People will be able to turn it easily into other genres (3d person games, RPG, etc.).
Hopefully this will bring more people on board! ;)

About the FPS demo : There is a bug with the controls, and I have the same problem with Sonic Z-Treme : it seems to always go faster one direction. Now, it might be something I don't understand about the >>#  and <<# functions and negatives/positives, but it's quite anoying when you are trying to move in diagonal.
Anyone got an idea about that? Johannes suggested a weird overflow issue, but I really can't find it.
Any suggestions for modifications to avoid that?
Title: Re: Collision BB generator (WIP) + FPS demo
Post by: Danny on July 30, 2017, 01:37:01 am
Humm, it seems you are using the logical shift operators (, they might not be doing what you need/want, have you tried to change the code to use the "+=" and "-=" assignment operators instead?
Title: Re: Collision BB generator (WIP) + FPS demo
Post by: XL2 on July 30, 2017, 02:55:03 am
Yes, I played quite a lot with both in Sonic Z-Treme, overall I had much better results with logical shifts (You just wouldn't believe it unless you saw it).
But after reading the link you sent me, you are right, for signed int the shift right is different for positive and negative values.
Funny thing is that I wrote a workaround in Sonic Z-Treme by  adding 512 (Instead of using floats, I used integers where 1=1024 to keep precision at low cost, but shifted right when sending these for drawing and collisions, so >>10), but I thought I just wrote a cheap workaround.
I guess that might be correct as it will get rounded down after being shifted (-1+1)>>1=0, or (-1024+512)>>10=0.
I guess that also explains why SGL demos are almost always using Unsigned integers and are always doing shifts.

One small question : just how much does shifting saves/costs in Cpu cycles? And SGL demos doing shifts for just about everything, doesn't that waste some CPU ressources?

Title: Re: Collision BB generator (WIP) + FPS demo
Post by: Danny on July 30, 2017, 11:54:01 am
In the early days logical shifts would be usually faster because the compilers were not very good at optimizing and the outcome would be more CPU cycles than needed, on more recent compilers that is no longer the case, the one we are using is relatively recent and I think will optimize correctly.
The problem with logical shifts its that it makes the code harder to read, at least the SGL demos were in my opinion messy and hard to understand at some points because of this.
In the end, if the outcome of the operation is the same, for instance the result of (10 << 1) and (10*2)  is the same (20), the compiler should compile to a binary left shift in either case, the difference is that its easier to understand on the second example. Now if you really want to do a binary shift and you really know what the binary shift is doing (for example, you really want some binary digits truncated) you should comment that line unlike those guys at Sega did. The code will be cleaner for someone else that reads it and even for yourself if you haven't picked it up in a long time.
I hope this helps  :P.
Title: Re: Collision BB generator (WIP) + FPS demo
Post by: XL2 on July 30, 2017, 01:52:09 pm
I took a quick look at the latest version of my code, and I don't use shifts for movements (since I just integrated your code).

The Jo_cos_mult/sin functions use JO_DIV_BY_32768 (or >>15) and they accept signed integers returned by the cosinus/sinus lookup table.
Code: [Select]
static  __jo_force_inline int	jo_sin_mult(const int value, const int angle) { return JO_DIV_BY_32768(value * jo_sin(angle)); }

Maybe adding a check would help?
Like, instead of simply returning the value >> 15 :

Code: [Select]
int val = value * jo_sin(angle)
if  (val<0)
    return -JO_DIV_BY_32768(JO_ABS(val)); 
    return JO_DIV_BY_32768(val);

Or is it supposed to be dealed with by the compiler?

EDIT : Did a small test by modifying the math.h file directly, it didn't really help.
Here is a video of the issue, but without the modification to the math.h file :
Title: Re: Collision BB generator (WIP) + FPS demo
Post by: Danny on July 30, 2017, 03:26:07 pm
The first time I used the JO Engine to make the First Person movement I had a similar issue, I pointed in a certain direction and I wouldn't go exactly in that direction. That was because of loss of precision, my workaround for that was just increasing the amount of space I was traveling forward so that the precision loss wasn't so problematic.
The problem is that if you have smaller 3D objects on your world when you are moving you will be going too fast.
Later when I re-used some of the SGL example code to make the VDP2 demo I just used the SGL functions, in that case I did not have the same issue. Maybe that was because I was using the SGL functions directly instead of the JO Engine functions for handling sinus and cosinus.
My guess is that you are having trouble in a part like this one:

Code: [Select]
position_increment[X] -= movement_speed * slSin(angle[Z]) / 10;
position_increment[Y] -= movement_speed * slCos(angle[Z]) / 10;

position[X] = position_increment[X];
position[Y] = position_increment[Y];
position[Z] = toFIXED(-35.0);

I can try to take at look at this later, in the meanwhile could you try with the slSin() and slCos() to check if it makes any difference?
I also used the SGL "ANGLE" data type and used the corresponding function to convert from degrees to it like in this example:
Code: [Select]
ANGLE testAngle = DEGtoANG(90.0);

I noticed that there is something in the SGL that might cause some confusion:
There is a macro that simplifies coordinate handling in a way of just declaring an array of 3 positions differently.
Let me just elaborate a simple example:

Code: [Select]
int test[XYZ];   // this is basically the same thing as "int test[3];"

test[X] = 1; // same as test[0] = 1;
test[Y] = 2; // same as test[1] = 2;
test[Z] = 3; // same as test[2] = 3;
Title: Re: Collision BB generator (WIP) + FPS demo
Post by: XL2 on July 30, 2017, 04:16:11 pm
I'm also using larger values to prevent loss of precision, but the issue must be different than that since -1 doesn't result im the opposite of 1.
Even if you only move on one axis, one direction goes faster than the other.
The negative int shift issue seems to fit the actual seen problem.

I guess I should use the SGL functions for now until a solution is found.
I updated the demo in the second post, the only difference is the use of gouraud shading, weapon switching and look up/down (Euler only for now)
Title: Re: Collision BB generator (WIP) + FPS demo
Post by: Danny on July 30, 2017, 10:43:20 pm
Yeah, you are right, sorry man, I got distracted by the weird forward movement which had happened to me before so I over-focused on that.
I haven't taken a good look at your code yet  :-\, I will however be checking it during the next days to try to find a solution  :), it might be something simple we are missing.
Title: Re: Collision BB generator (WIP) + FPS demo
Post by: XL2 on August 10, 2017, 03:49:28 pm
Huge update!
The map tool now reads .Obj files and outputs a binary map format.
The FPS demo is now using this map format and you can change maps by reading them on the disk.
Just press L/R + start in game to switch maps.

I still have lot of work to do on the tool and there might be bugs that I didn't find out yet, so if you find any make sure to tell me!
Title: Re: 3D Map tool + FPS demo
Post by: XL2 on August 26, 2017, 03:44:29 am
I made a big update, the map tool now reads TGA files and writes to the binary custom file for texture mapped levels.
I also added a function to auto-subdivide the map for view frustum culling.
I'm still using SGL culling function, which isn't great.
I also changed the collision code to reduce CPU usage (I didn't do much testing, so it's possible that it's buggy now).

I succesfully imported levels from Project AXSX, but performance isn't that great for now as you can see in the video.

I still have to fix bugs, do more testing and find a way to precompute visibility (suggestions are welcome!) in order to improve performance further.
Title: Re: 3D Map tool + FPS demo
Post by: itsstillthinking1999 on August 27, 2017, 12:51:56 am
Very nice! what video are you talking about?
Title: Re: 3D Map tool + FPS demo
Post by: XL2 on August 27, 2017, 04:20:31 am
Second post, the youtube link.
Title: Re: 3D Map tool + FPS demo
Post by: corvusd on August 28, 2017, 10:16:24 pm
Again!! Great work and progress XL2!!!

I am curious... which is possible cause of the slow performance of the gouraud distance code in the real SS???

Thanks in advance!! :D
Title: Re: 3D Map tool + FPS demo
Post by: XL2 on August 29, 2017, 05:05:30 am
I removed gouraud shading because it's much slower with it (25% at 60 fps). The "slow" performance is in fact between 30 and 60 fps on real hardware. I just need to add precalculated visibility and I should be able to hit 60 fps. If not I will just display a low quality model at distance and use lower quality textures on that model. Either way, I will get to stable 60 fps, I just need lot of work to get there, but I'm confident.
Precalculated visibility is my next headache, I plan to just subdivide the map in a few zones (say 64 zones) and do ray tracing checks (on the PC) at the limits and middle of each zone, then store the results compressed in an interger. So say I'm at zone 2 and can potentially see 6 meshes (out of 32 as an example) from there, I will just flip the bits of that integer to 1, the rest to 0. If I have 128 meshes, I will need 4 integers per zone (like 64 again), which means it will only take 256 bytes, which isn't too bad for the huge speed gain. Anyway, that's the plan for now, it might not work when I try it and it won't be that easy to pull.
Title: Re: 3D Map tool + FPS demo
Post by: lostgame on November 07, 2017, 12:47:05 am
Just wanted to thank you for this. I've been toying around with the current collision tool demo. It's neat! I'd love to speed it up a bit and implement a sprite object-based system...I'd love to create a BUG!-ish 3D platformer of my own...


I assume the VDP1 is being used primarily for the 3D polygons...

How much effort would be required to hack a scrolling background with a VPD2 image in there?
Title: Re: 3D Map tool + FPS demo
Post by: XL2 on November 07, 2017, 01:50:42 am
Using the vdp2 is quite hard. You could DMA sprites to the VDP2 NBG1, but you would be limited to not too big sprites and would need to clear the screen each frame. You would probably also have to store them in the main RAM, taking precious memory away.

I didn't update the FPS demo for a long while, so it's really dated now compared to what I have in Z-Treme (it gives me a speed boost of around 40% compared to what's in the FPS demo). The map converter is also old now compared to what I have in Z-treme.

I still plan to update it within the next few months.
Title: Re: 3D Map tool + FPS demo
Post by: lostgame on November 07, 2017, 02:46:07 am
I was messing with the baked-in-but-commented-out BG VDP2 code...but yeah, it's messy at best.

I'm sure your Z-Treme engine is far more advanced, but even this is tremendous. This Jo-Engine has really quickly allowed me to fulfill my long-term dreams of developing for this platform.