3D Engine: Any Tips?

Contests 4K Game Competition - 2011
#1

Hello there ladies and gents,

I’ve begun a 3D J4k project, and was wondering if any of you had tips or experiences you’d like to share regarding the 3D engine stuff. I’ve already implemented a renderer for a single cube (pic below), and I can move around it and view it from all angles and distances. But I’d like to generalize the polygon rendering for many more shapes (for some definition of “many”).

There are a few approaches to 3D rendering. Right now I project the polygon vertices onto the screen plane and check which screen pixels are within the polygon. And that works plenty fine for one cube. But I’m concerned that it might not scale well. Plus there’d be the added work for a z-buffer (the calculations for the distance to the object are not performed in this implementation, so it’s extra work for every pixel).

So, I was thinking of moving to ray casting, and I see that there are a few games that use this method (e.g. Wolfenstein 4k and Star Wars: The Battle for Hoth 4k – both of which are from the same developer, I see). I’m not sure that this will scale well either, given that i’d like to draw more than just a few walls or sprites.

Anyway, please pass along your tips and suggestions. Thanks!

–Ben

#2

I am working an something similar currently.
I concentrated first to implement a polygon-clipping for the scene.
So the polygons (well triangles) are clipped on the view-frustrum (sides and depth)

For the sorting I use a simple depth-sorting algorythm.

Objects dont need sorting, when they are constructed in a convex shape, as the polygons will not overlap.
(polygons on the back are invisible)
So only the Objects are sorted by their mid-point distance to the camera.

I like to have a rendering similar to the tech they used in “1990” 3D vectorgraphic games.
Wich is really fast.
For performance reasons they could not use zBuffer or raycasting mechanisms in realtime back then.

#3

Every year i threaten to finally complete my realtime ray tracing engine for use in a 4k competition entry. but I always loose the motivation. Perhaps this year i will complete it. The real problem is that it is very hard to create a compelling game in the remaining 1k or so bytes, especially after a very models and resources the size becomes less than 500 bytes for the game play.

  1. I guess it is a given, but there is simply no room for bitmap textures, you need to use procedurally generated textures.
  2. ensure that your first 4 most commonly referenced local variables are assigned first, this allows the compiler to use special shorter bytecode operations for these variables. i.e. iload_0 to iload_3
  3. avoid reference to any String (unsure about string literals) as it will reduce the size of your Symbol Table.
  4. using do while loops instead of while loops generates smaller byte code

may not be applicable for your solution but I might be able to leverage pack200’s ability to tersely pack multiple classes to help simplify and hopefully reduce the byte cost of my last RTRT4k attempt.

#4

Love doing 3D, but Moogie is right; there is precious little room for gameplay after doing the graphics code. But using pack200, there is now enough.

Last year MageWars was my latest raycaster/tracer hybrid (source code on Java4k.com). I got a bit carried away and added network code, after which there wasn’t enough room for any complex gameplay. I’ll probably do something without network code this year.

It’s also worth considering doing a 2D game and then using isometric projection to give a 3D look.

#5

I think i rendered the level and and cube separately in 4kube, first the level then the cube. The faces aren’t sorted, only backface culling is used to get the cube rendered correctly.

  • Get a tool chain script going so you can see approximately at what size you are.
  • Functions can be ok IFF they will be used in several places with varying parameters and have a reasonable size to them.
  • Accept that the code probably will look like shit.
#6

I’ve been playing with 3d in 4k for literally YEARS now. I wrote my first attempt using the ‘painters’ algorithm and Graphics.fillPolygon for the 2005 contest. It was an applet hosted on geocities so the page is gone now. I still have the source:

http://www.java4k.com/index.php?action=games&method=view&gid=46

Using the painters algorithm allows you go without z buffering, but then all your meshes should be convex. This is a severe limitation in my opinion. An option is to check for overlapping polygons and then split one into two so they render correctly. I’m not sure how to do this but I think it would involve a lot more and intricate code.

The last work I did on it was flat shaded ‘half space’ polygon rendering. As you can see from the code in that thread, calculating z values using the half space method is a mother f**ker. Took me a LONG TIME to figure that out. And I’m still not convinced I got it exactly correct.

Going forward, I think the way to go is to use scanline triangle rasterizing. It’s relatively easy to do z buffering, texture mapping, and gauroud shading using the scanline method, plus there are lots of tutorials and examples on the web.

I have a lot more to say about this subject but will leave it at that :slight_smile:

Edit removed link.

#7

Im using polygon drawing without a z-buffer too.

I wrote a clipping-algorythm for the polygons, and a very fast sorting for them.
So I can render continuous terrain (and fully free camera movement), with almost no “sorting” bugs.

Im not shure if it would work with smaller (convex) objects too yet.

The big advantage over “per pixel” rendering using a zBuffer or Raycasting is the much better scalability.
So the performance drops almost not when rendering a large screen.
The disadvantagers are of course the lack of textures (when just using classic flat polygons)
But I like this style as they used in the early 90s.

#8

Hey folks,

Thanks for your thoughts. Based on my design, I can assume some nice things like axis-aligned polygons, so that should help with some of it. But it’s good to keep in mind that it’s going to be the main “feature” of the game: there won’t be much room for else. So thanks for pointing this out. I should mention that this is my first J4k project, so I don’t have any intuition about how much room something will take: thanks for providing some!

I’ll consider polygon sorting instead of a z-buffer. Any good algorithms to suggest? If not, I can certainly work out the math myself, but if there are ones that clearly work well for 4k games, then I’d love to hear about them.

bysse, thanks for the info about functions. I’m primarily a C++ programmer, so it hurts to not have macros: that would allow for function-like operations without the overhead of passing parameters. Or even inline functions. So maybe I’ll sort of take your advice: write some functions that I need, then consider hand-inlining them when it comes down to the final builds. (I already have a compression script set up, and am using Mercurial to both preserve version and also keep track of the size, which I record to a file)

moogie, generated textures should work fine for my game, so that’s what I was looking at anyway. I imagine that a full raytracer would be challenging to squeeze into 4kB (while still having something interesting to play), so best of luck with that! Me, I’ll keep it simpler. :slight_smile:

Alan_W, I am using pack200, and am pleased by how well the whole compression process works. It’s quite the satisfying experience, actually. Unfortunately, I’d prefer to have 3D movement in the game, so isometric isn’t really an option. I’ll keep it in mind, though, if I decide to change things up.

Anyway, thanks everyone for your thoughts. Please feel free to share any other considerations. I have confidence that I could work out some of these things on my own, but thought it prudent to see if others were willing to share their knowledge and save me the time and trouble. So thanks again!

–Ben

#9

No problem, I’m glad if I can help. Btw I’ve found my source for 4kube and uploaded it to the game.

http://www.java4k.com/index.php?action=games&method=view&gid=315

Please let me know if something in the code is retarded :slight_smile:

#10

I would say, based on experience with adding z-buffering to a Java software scanline triangle rasteriser, that it’s a lot harder (and bigger) than you think. You have to break it down into a number of cases and then it’s really easy to have a bug in one case which takes an inordinate amount of time to track down.

If you don’t have too many polygons then you’ll be hard-pressed to write a more compact sort than one of the standard n^2 ones (bubble, selection, insertion). Can’t say offhand which is shortest, and it’s really quite complicated to measure because when you use pack200 and gzip a saving of 4 bytes in the .class file can lead to a growth of 12 bytes in the final product.

If you’re really struggling to squeeze out the last few bytes then you can always use jasmin to disassemble the bytecode, hand-optimise it, and reassemble it. If you do this you might be able to exploit the jsr/ret subroutine mechanism to “inline” your functions. I’ve never actually experimented with subroutines (although I did use jasmin for Gravitational Fourks) because I was never quite that desperate.

#11

Interesting, are you clipping polygons to polygons or polygons to screen? How does your algorithm work?

I think you just have interpolate the z values between vertices and then between spans as you draw each span, are you saying it’s more complicated than that?

#12

No the polygons get clipped on the view frustrum (in 3d), which resolves to be clipped on the sides of the screen.

A triangle can be cut into 1 or 2 triangles by this clipping for each side.
It is also clipped on the near and the far view-plane.

The sorting takes about n*5 steps not n^2. So it grows liniary with the number of polygons.
This is kind of faster than most other sorts.

I dont need to clip the polygons between each other, as the terrain is a regular grid.

(-> look at my Java4k2012 Cave4k entry)
http://damocles11.byethost9.com/cave4k.html

My 3dEngine code is not optimized at all yet.
I sould be able to squeeze 20% out overall if I find to time to do it.
Nevertheless the pack200 archive reached the 4k limit already.

#13

Looks really good, especially for 4k!

I assume you’re using Graphics.fillPolygon()? If so then why clip to the view frustum at all? FillPolygon will clip to the visible display. You could just check if polygons are in the view only. Same for near/far plane.

Sorting; is there a reason you didn’t use Collections.sort or Arrays.sort?

#14

I think you just have interpolate the z values between vertices and then between spans as you draw each span, are you saying it’s more complicated than that?
[/quote]
No, it’s precisely that complicated. It’s the scanline triangle rasteriser which has a lot of cases, not specifically the z-buffer.

#15

without the clipping, I ran into some rendering bugs.

And also because I wanted to do it “propperly” anyhow.
Where the clipping algorythm was actually done before thinking to advance it to a game.

The clipping you need anyhow when calculating the near-plane.
(or how else should triangles which are only half in front of you be rendered)

For the sorting I wrote my own function.
Partly to avoid importing another Java-class.
But mainly because Im not smart enough to understand the provided sorting classes. :persecutioncomplex:

#16

My solution to near plane clipping was to simply not draw objects that are behind or intersect the near plane. That wasn’t an option in your cave game I suppose.

#17

For a topdown RTS or Shooter its not needed indeed.
There the propper sorting of the polygons it more the key-point.

But in a 1st person view you cant really get around implementing a clipping.
Else it look akward.
(one cheap solution would be to make very close objects fade out, like in a racinggame where the camera moves
in a preciclable direction, keeping the center clear, and rendering the terrain with a different method.)