Observing myself for the last few days my thoughts were mostly about the raycasting++ demo, so that may be what I’ll probably try to do. I started writing a small raycasting library. It should be:
small, simple
written in C => compatible with everything
single header only
using only integer math
using only stdint library
CC0 licensed
focused on small platforms
offering choice between speed and memory efficiency
more of a utility library than a “framework”, to allow flexibility and freedom
I’d also write a C++ wrapper, but it’s supposed to be just a few small functions, so probably no point in that.
What about something ala eye of beholder ?
Or nowdays Legend of Grimrock.
You could take advantage of the sd-card capabilities of Pokitto to prerender the dungeon.
It should be quite easy create a software toolchain to export a 3d dungeon from blender.
Would be awesome, especially if you added the smooth movement I’ve been talking about I’d be interested in helping out.
Obj parsers are trivial, I’ve written several ones. The problem is how to render it – do you think Pokitto could render general 3D in real time? We might try to port some software renderers, there are plenty.
Even if real time wasn’t possible, offline prerendering right on Pokitto would still be useful – you wouldn’t have to store prerenders on the SD card.
I’ve once written a distributed raytracer with obj and ppm parser, maybe the code could be reused, even though I think it’s a mess.
I thought @HomineLudens meant turning a 3D model of a dungeon into something that could be raycasted rather than 3D rendered.
I don’t know. I vaguely remember there being a raytracing demo somewhere that was quite good.
It could do with being broken up into more functions and made more idiomatic, but I’ve seen worse.
Lode Vandevenne turns up quite a lot (I once emailed him about a typo in the floodfill example on his website). His raycasting tutorial is easily the best raycasting tutorial that I’ve seen.
Now I think about it though, I wonder if Doom’s engine could be ported.
The SD card could probably store WAD files.
Oh god, I just looked at it, what a shame… it’s been some time since I wrote it. But some of the math stuff could be copy pasted.
That’s what I’d want to achieve with raycasting++, just not by porting the Doom engine, but writing my own (as @FManga said, it’s often easier to write from scratch than port), more suitable for Pokitto. I don’t know the exact details of the Doom rendering system, but I know it uses BSP trees or something and allows arbitrary polygon walls, right? My engine would still be based on a 2D array of cells, maybe with 45° angled walls allowed, so would be a bit simpler here, but the rendering would otherwise look the same.
Real raytracing or just 1D raycasting? Not even PCs can do full real time raytracing (I think NVidia Turing should be the first GPU to support it). But I was thinking more about classical triangle rasterization – you know, what OpenGL or Direct3D does – I think it could work, but might be lower FPS. But with a low-res high-color screen mode it might be possible.
Now I remember I once found this at GitHub - a SW renderer in 500 lines of C!
@jonne@FManga@Pharap do you guys think it would be possible to port this? I’m becoming quite excited about this. That could really sell Pokitto. Imagine something like Minecraft, or a real FPS, or a 3D racing game on Pokitto.
I think flat-shaded 3D drawing would be easy, but to have texturing and smooth shading you have to do a lot of per-pixel operations, like interpolation, perspective correction, (though some primitive engines simply ignore this), texture sampling (preferably with MIPMapping to prevent aliasing but again, a simple engine could do without). There’d have to be a lot of optimization here. Also depth buffer could eat a lot of RAM.
Look at what Gameboy Advance could do:
(There’s one splat-rendered game, also a nice idea to consider.)
There’s a reasonably in-depth explanation here and a good summary here.
Seems resonable. Octagonal rooms would be fun.
¯\_(ツ)_/¯
I wasn’t necessarily thinking about realtime, I was thinking more of using it as a benchmark for processing speed because it renders fairly quickly for a raytracer.
‘Lines of code’ is a terrible metric.
I’m glad to see it’s somewhat readable though.
Firstly it depends how much memory it allocates.
I’d be concerned that the Pokitto’s file API possible isn’t close enough, and perhaps some of the printing would possibly need to be removed, and obviously the screen format is different (RGB565 instead of RGB888), but otherwise it’s possible.
We did have Blocky World, but development halted.
I think 3D minecraft might be a bit too hard to control with just 7 buttons.
Fixed points should help.
You don’t need a depth buffer, just organise objects in depth order and draw from front to back - if a pixel’s already been drawn, assume it’s occluded and skip over it.
I forget what that’s technique’s called, but I’m pretty sure it’s a thing.
I’m not sure it’s a completely fair comparison
GBA
ARM7TDMI @ 16.78 MHz & Zilog Z80 @ 8 or 4 MHz
32KB internal RAM & 96KB VRAM
256KB external RAM
Special graphics hardware with hardware sprites and other hardware optimisations
Pokitto
ARM Cortex M0+ @ 48 MHz (thumb only)
256KB progmem & 36KB RAM
No special graphics hardware
Edit
Forgot to mention, I remember reading that the GBA’s graphics hardware used fixed points.
I’m not sure if this is where I read it, but there’s some discussion of it here.
Sure, but to give a quick idea LoC in terms of just orders of magnitude is good.
Painter’s algorithm (or actually you maybe described something a little different), but it has drawbacks:
Sort in each frame => slower.
Doesn’t handle intersecting objects.
Fails at overlapping (one object can be partly both in front and behind another object).
We might get creative and try like a half-resolution depth buffer or something.
Oh Yeah, this is it. Anyway, something much simpler than what’s in the video is still possible I think.
I wouldn’t be surprised, fixed points are great. Floating points are necessary for big scenes and big resolution where you notice imprecise placement, but for such small device I think there’s no point (pun) in floating point.
Lots of people attempt to stuff multiple operations into the same line or use single-letter variable names to try to shorten their code which muddies the water.
I prefer things like the number of includes, the number of functions and number of classes/structs (and preferably the average length of all functions).
E.g. that code has 6 includes, 10 structs and 36 functions
*puts ‘write complexity analyser’ on todo list*
If there’s 400 lines and 300 of that is all one function, that implies a greater complexity (or at least a bigger mess) than 500 lines split over 36 functions.
And that’s before factoring in brace style.
More a reverse painter’s algorithm.
Only if you’re sorting every object in a big O(n) sort every frame like Shlemiel The Painter.
If you use binary space partitioning then sorting can be reasonably fast for very little overhead (just the overhead of a binary tree).
Essentially the sorting can happen as the objects and/or camera move (in which case there’s a bit of tree rotation involved) instead of after everything has moved.
As long as the tree is kept balanced (preferably by using a self-balancing implementation) then you should get decent performance.
If there aren’t many objects, one option is to write the object number to the pixel and then if you get a collision, do a hash table lookup to retrieve the object’s depth.
That would large depth values to be used since you’d only need one per object.
Of course of course, I’m just saying assuming normal style (no hardcore code golfing) knowing the order of magnitude of LoC is a good first look at the complexity – you know just knowing it’s 100s LoC as opposed to 10000s can give you a rough idea. Beyond that of course it doesn’t say that much.
The number of classes etc. won’t be much better, someone writes a big utility class to solve a problem while someone else will abuse design patterns heavily to solve the same problem and end up with dozens of classes.
No. of includes/dependencies is good but won’t speak about code complexity, rather about the result size.
So I don’t think there is a simple super-metric. You have to actually study the code, or ask the programmers who work with it.
This is nice until you want to do animation, so good for static Doom levels, but probably not for a general 3D drawing. Actually the painter’s algorithm with normal sorting could work well if applied at triangle level – there wouldn’t be many triangles anyway, because performance, so sorting wouldn’t cause much overhead, plus the overlapping problem can’t happen with triangles.
You mean use the frame buffer instead of having an extra depth buffer? That could be a nice hack. But it would become a two-pass rendering.
Thanks for the ideas, I’ll try to experiment with this (am currently having some issues with getting the Pokitto simulator to work properly Will leave it for tomorrow).
A general-purpose 3D engine that runs at an acceptable framerate, within the memory constraints, and looks good will be pretty hard to make. You’ll have to weigh what’s more important and make trade-offs.
Depending on the final look you’re aiming for, you can do some optimizations that wouldn’t be valid otherwise.
In the Arduboy PodRacer game I’m (sloooowly) making, I use the painter’s algorithm. Instead of sorting objects, it sorts faces (it handles intersecting objects). The trick that makes it quick: bubble sort.
The reason it works is the sort is done by the same loop that does the rendering: If the current face is further than the next face, swap their position in the draw queue; else render the current face. This produces some artifacts, but within a few frames the z-order is correct. Being a racing game, speed is more important than accuracy.
Instead of just looking at existing techniques, think of the game you want to make and then work towards that. For a first Pokitto project I’d recommend trying something less ambitious so you can get used to the hardware and the lib. There might be some surprises in the process.
Thank you @FManga, I agree completely, these are very good advices, and very nice solution with the bubble sort. I’ll leave the general 3D engine for later, will try to do the raycasting++ demo and if there are problems with performance etc., I’ll fall back to good old regular raycasting and make a small game with it.
I am thinking of dropping tracked mail as a shipping option. It is useless. Tracked mail (in my experience) takes longer to deliver than priority normal.
Secondly, if the mail gets lost, guess what? There is no way for me to get a refund. “Your shipment was lost in New York”… yes … and ?
What kind of animation?
If you’re thinking of deforming the models, I’m not sure there’s enough processing power for that.
I was assuming the depth buffer was part of the frame buffer since you end up with one depth value per pixel either way.
What I mean is that instead of having a depth buffer that stores the depth of the pixel written into the corresponding frame buffer position, you have an ‘object id’ buffer that writes the index of the object that’s been written to the corresponding frame buffer position.
Then when you need to compare depth, you look up the depth in a lookup table that maps the object id to a depth.
The idea is that there should be less objects than degrees of depth, in which case the object id buffer + lookup table should use less memory overall.
It would possibly be slower, but it would use less memory.
I’d be interested in helping out.
Yeah, this is it. Anyway, something much simpler than what’s in the video is still possible I think.
Will leave it for tomorrow).
It’s beautiful.