[General Algorithme] 3D engines

[benryves]

I found this tutorial, it's quite clear about the process, though implementing that in z80 is still a big step
http://www.permadi.com/tutorial/raycast/index.html

I never really liked Permadi's tutorial, I found it overcomplicated things (or maybe I was being a bit dim).
Maybe I should write a raycaster tutorial at some point (I did write one, after all that's a bit more plain English).

[Timendus]

I'd certainly like to read how you made that

How does Permadi overcomplicate things, except for that fact that English doesn't seem to be his native language?

Edit: Oh, by the way; I'm the anonymous poster on Brain Damage@12:30:21

[benryves]

How does Permadi overcomplicate things, except for that fact that English doesn't seem to be his native language?

I find referring to the "projection plane" in the way he does wholly unnecessary (I tend to simplify it down a lot).

[Timendus]

Would that also happen to simplify the neccessary calculations? In that case I would be most interested

[threefingeredguy]

I remember reading a book on 3D transformations and thinking that the stuff about the projection plane was needlessly complicated. However, I didn't understand much else, so I gave up.

[benryves]

Would that also happen to simplify the neccessary calculations? In that case I would be most interested

It doesn't change any of the maths, I just a way of thinking about it.
I just think of it as - we have a FOV of ~90 degrees. We want to ideally use one pixel column for one 'degree', so on the calculator I'd use a screen width of 64 pixels and have 256 degrees to a complete revolution. (In fact, using the full 96 pixels width would work, just giving us a slightly larger FOV). We cast the rays for each column, and the height of the column drawn is simply <screenheight>/<distance> (with a bit of fudging to get a sensible scale). Usual fisheye rules apply to "fixing" the distance, of course.

I've thought about jumping on the 3D engine bandwagon, but not using a raycasting type idea. I'm going the 2D map route (hopefully easily extendable to 2.5D), and a world built up of lines (vector-based). The calculations to rotate a point in 2D are extremely simple, so I've got the basic spinning square demo up and running already (though I've thought of a way to shave off two trig-table lookups). Backface culling is trivial, as long as I design the map properly, but clipping lines and ordering is going to be more challenging. (BSP for the latter..?)

[coelurus]

I usually prefer the hack-n-slash method of describing things too, but the problem is that it doesn't last long once you put your nose into a bit more complex things. Projection can be thought of as "big distance = small object, small distance = big object" which works well for raycasting/mode7/whatnot, but projecting a view space map into light space, the "big -> small, small -> big"-approach won't work
Alright, what I wrote up there isn't needed for raycasting, but the spinning point is that raycasting is simple business and thus gives a perfect opportunity to examine how every little bit of the algo works. Raycasting can give the intuitive feeling for how projection does its thing, but not the proper understanding which is needed in order to advance further. Gosh, university is making me crazy

Ben, that sounds a lot like Doom BSP + PVS is a good approach (PVS = [in a hack-n-slash'ish description] a set of lists of visible nodes in each node of the BSP tree).

[Timendus]

so on the calculator I'd use a screen width of 64 pixels and have 256 degrees to a complete revolution. (In fact, using the full 96 pixels width would work, just giving us a slightly larger FOV). We cast the rays for each column, and the height of the column drawn is simply <screenheight>/<distance>

Hmm, that's a pretty good idea, Ben. It's so tempting to try to write one of these things... must... do... useful... stuff

Alright, what I wrote up there isn't needed for raycasting, but the spinning point is that raycasting is simple business and thus gives a perfect opportunity to examine how every little bit of the algo works. Raycasting can give the intuitive feeling for how projection does its thing, but not the proper understanding which is needed in order to advance further. Gosh, university is making me crazy

You're probably right, but I don't think a z80 processor is the best place to learn it the proper way If you can simplify these things on our platform, I think you certainly should to increase performance. And to be able to simplify things you'll need a proper understanding, so...

[benryves]

so on the calculator I'd use a screen width of 64 pixels and have 256 degrees to a complete revolution. (In fact, using the full 96 pixels width would work, just giving us a slightly larger FOV). We cast the rays for each column, and the height of the column drawn is simply <screenheight>/<distance>

Hmm, that's a pretty good idea, Ben. It's so tempting to try to write one of these things... must... do... useful... stuff

Hehe, indeed, this is the way I always did it. Initially, though, I'd use a single ray and shoot it out very very slowly until it hit something - very slow, and horribly inaccurate. The method used by Permadi's tutorials (two rays) is very fast and much more accurate.

[coelurus]

Gemini uses the separate two rays-approach as well, but there's a problem: rays with shallow angles against grid edges can jump and in the worst case mark grid cells as visible when they are in fact not, leading to unnecessary processing of objects that are thought of as visible (recall an earlier post in this thread?). The best way to solve this is to hop between the two rays all the time and only do the grid-processing for the ray that has traveled the shortest path (Wolfenstein 3D does this, of course). Won't give as tight a loop as "akimbo-rays", but there will be less processing steps.

And no, z80 is not that helpful when it comes to "understanding". I generally refer to "seeing solutions" in two different categories: "understanding" (deep, you could even bet your life on it) and "feeling" (shallow, you're pretty sure it'll work ). Playing with a raycaster will give you feeling (you know the algos, how they can be built together, great), digging deeper theoretically will give you understanding (you see through the algos and develop new tech from the old). Feeling will only help you when you approach similar problems, understanding will help you design new solutions. Feeling will help develop understanding, hence my statement that it's a good idea to read through the proper theory while developing a raycaster.
Alright, I'll leave this off-topic crap

[thecheat]

I came up with yet ANOTHER idea, perhaps you had the calc preform an operation where it used two maps to locate where something should be, a basic layout with a 2D map(something like OOT zelda dungeon maps for the N64) and a "vertical" map showing a "2D" distance, AKA the how "high" the uh... ship is floating, and the walls extend.

here's where it gets fun, The two maps are invisible but the Calc morphs them together letting it know (relative to your position on both of them) how much "depth-distortion" to apply to them.

If you get what I'm saying, great, as I'm trying to find a way to get around using polygons, yet, have a 3D feel with all the looking and such. Tell me if you understand, PLEASE.

[Fr0stbyte124]

Polygon rendering was invented to make the process more efficient. It takes advantage of the fact that every pixel in the shape is related to one-another in a linear fashon. To render a square takes the 3D calculation of three or four points followed by a much quicker (per pixel) filling or texturing routine. To add Z coordinates would require every pixel that doesn't lie in the same plane to be calculated separately across 3 dimensions. In other words, it would accomplish the same thing as ray-tracing, and would be frightfully slow on a calculator.

Modern graphic cards have something similar called bumpmapping. But what that is is a lighting map that creates the illusion of 3D texture on a flat surface by changing how light rays are affected by the surface at different angles. While it is good for fake 3D, as there is little extra overhead, it is only effective on (relatively) high res images with dynamic lighting, and preferably more than 4-shade greyscale.

I'm not saying the idea is impossible. With some finely tailored coding and using it sparingly, perhaps for some hard-coded effect, I think you could make some pretty neat stuff.

[benryves]

...leading to unnecessary processing of objects that are thought of as visible (recall an earlier post in this thread?).

By objects are you referring to the things that roam in the maze (enemies, weapons, decorations (lights) and so on? In which case, I assume you're using the raycasting process to identify them to cull objects not in your field of view, and not to draw them... I'd normally render the walls/floors in the main raycasting loop, then do a simple 3D transformation and scaled sprite rendering trick, based against a depth buffer created by the raycasting process.

[Timendus]

Yes, that would seem more logical; just store object data as your rays pass by them, and only use the data for the shortest of the two rays..? You'd have a position and a depth then, which you can use to render sprites over the scene.

Only problem would be; how does your ray pass by them when it uses Permadi's idea of jumping from gridline to gridline

[benryves]

Only problem would be; how does your ray pass by them when it uses Permadi's idea of jumping from gridline to gridline

You'd need to round the position of each element into a complete "block" to detect it, then mark it as visible (not just add it to a queue, as it'd end up on there twice...). Then you'd run through the list of seen objects, perform the 3D transformation and draw.