This demo unfortunately uses an incorrect perspective transformation. There is no reason to go to trig if you represent the camera plane as a vector, and step along it one pixel at a time, and allowing the wall height to vary linearly in the distance to the camera vector (taking lines to lines). In addition to being correct[1], it has the added benefit of being faster if implemented well.
I think what's most interesting about the original article is the write-up and not necessarily the implementation itself. I find reading and following >~ 500 LOC to be burdensome and difficult so keeping it short and small is certainly an advantage for this style of article.
I'd really enjoy seeing your write-up on your implementation. If there's going to be an article we're going to link new people to in order to teach them ray-casting I'd hope we could teach them the best techniques that we can.
I'm not sure I'm convinced, as finding the cosine does in fact find the linear distance from the camera plane to the intersection. This is, as far as I have seen, the standard implementation, eg: http://www.permadi.com/tutorial/raycast/rayc8.html#FINDING DISTANCE TO WALLS
However, I would love to see your proposed solution demonstrated. Would you care to fork the raycaster and compute the results with an alternative method?
My implementation above complies, but I can send you binaries if you need them. Be forewarned that I neglected to implement atmosphere. Here's a screenshot http://i.imgur.com/7LJocjS.jpg
I'm less interested in seeing binary output and more interested in understanding the principles behind what you're saying. The wikipedia page you mentioned: http://en.wikipedia.org/wiki/3D_projection#Diagram
...appears to be describing exactly how this example works, right down to the diagram:
Why is it incorrect? From looking at the demo, it doesn't seem incorrect at all. If it's incorrect, then the incorrectness doesn't affect the end product, which is all that matters. Lines seem to map to lines, so it seems mistaken to call it incorrect.
I'd be interested in further explanation about why you feel the underlying math could be improved, though.
He ought to be using what Wikipedia calls a "perspective projection", or, sufficiently in this case, a restriction thereof. Notice how the edges of walls do not appear straight on the screen, even though he mentioned correcting "a fisheye effect" (tellingly alluding to a popular tutorial on this topic at lodev.org).
A correct formula is on line 485 of my implementation linked above, found the old fashioned way using basic geometry.
On my old laptop, the demo looked fine. But after switching over to a widescreen (and higher FPS) you can tell that it's slightly wrong up close, and noticeably wrong (jittery) in the distance.
It is very interesting to me that you need to multiply the distance-to-wall by the cosine of the angle to transform the image from fisheye to normal. It makes me wonder, why is it that our eye in real life sees straight lines as straight, the way this demo renders the image?
To illustrate the question, see https://en.wikipedia.org/wiki/File:Panotools5618.jpg – why do we see the world as in the bottom image instead of in the top one? After all, our eye really is at different distances from different parts of a straight wall, so it sounds logical that we would see the fisheye effect describe in the article. Is the rectilinearity of the image we see caused by the shape of the lens in our eye, or by post-processing in our brain?
> It makes me wonder, why is it that our eye in real life sees straight lines as straight, the way this demo renders the image?
Your eye doesn't see it as straight, your brain does. Your eye doesn't actually gather a single coherent image, in fact. It's constantly moving[1], bringing the higher-precision fovea at the center of your retina to bear on interesting parts of the scene.
Your brain then accumulates all of that data into a single coherent "image" which is what you consciously perceive. This is why, for example, you are unaware of the blind spot caused by your optic nerve obstructing your retina[2].
A straight line in the world isn't projected onto a straight line on your eye: after all, the back of your eye is curved. (Even if it was, so what, it's not like your rods and cones are aligned in a nice neat grid.) It's just that you've learned that a line of stimulus curved just so across your visual field corresponds to a straight line in 3D space.
Wow, the blind-spot test on that Wikipedia page just blew my mind.
There were situations in traffic when I was driving a car and simply did not see cyclists or pedestrians coming. At the time I was aware that one of my eyes were obstructed by the rear-view mirror on the windshield, but that did not explain why I did not see them coming with the other eye.
I wonder why are people not alerted about this when taking the test for the drivers license.
I was trying to crack exactly the same problem a decade ago - I was very frustrated by "classical" perspective distortions (such as looking up and down at a very tall pole, you notice in 3D projection the projected width at a given height changes depending on the pitch angle, which is counter-intuitive as your eye doesn't do that).
I searched for answers, read Denis Zorin's disertation from Caltech, various different camera models etc.
After one talk with a neurosurgeon he mentioned that those "perspective distortions" are perceived often by patients after a brain surgery and as the brain heals the normal undistorted picture begins to emerge.
I am still curious if there is a more realistic mathematic formula that would allow us to have exactly the same perspective projection in 3D graphics as we have with our eyes. Anyone knows any recent research on this subject?
At any given moment we're only looking at a very small slice of that larger spherical panorama. Our brains are constantly constructing a coherent 3d model, with the help of various schematic constraints, such as expectations about straight lines being straight.
We perceive straight lines. but that's not what we see. But the curvature is usually so slight that it is very difficult to see.
You need a curved display. A 240 degree sphere segment stretching all around you will allow you to display a fully realistic-looking perspective, as long as the viewer's head is exactly in the centre. Or a head-mounted display like the Oculus could accomplish the same thing.
I would hazard a guess that it's a result of the brain interpreting the electrical impulses before providing the "image" that we "see."
It does a lot of pre-processing, so to speak -- which is why we get such awesome illusions as the Poggendorff illusion [0], tricks like the Pulfrich effect [1], etc.
I don't know enough about the mechanics of how light enters and is interpreted by the eye, but I wouldn't be surprised at ALL if we "should" be seeing more like a fisheye lens but our brain is saying no, no, those lines are straight, based on the countless other stimuli it's receiving.
The brain adjusts the images after learning about the physical world using other senses. If you start wearing glasses turning everything upside down the brain adapts within days.
I've always figured the latter explanation - that the picture from our eyes is distorted like that, but the brain corrects the image (it also doesn't hurt that we have two eyes, where as cameras typically don't; I wonder if multi-lens cameras are also subject to that fisheye effect?).
I think it's simpler than some of explanations here. You're not rendering onto the curved eye, you're rendering onto a flat monitor. If you imagine the game view as a window, a straight line outside always projects toward your eye onto a straight line on the window.
Similarly, I used to wonder why an image constructed with 3-point perspective [1] looks perfectly normal, while one with 4-point perspective [2] does not.
> It makes me wonder, why is it that our eye in real life sees straight lines as straight, the way this demo renders the image?
Not always. Next time the Sun and the Moon happen to be in view at the same time, look at the dividing line X on the Moon between the parts illuminated and in shadow. Then draw a straight line Y from the Moon to the Sun.
Common sense tells us that the two lines are perpendicular, but often this is not the case. I don't understand it completely myself, but it is something to do with us residing on a curved surface.
> After all, our eye really is at different distances from different parts of a straight wall, so it sounds logical that we would see the fisheye effect describe in the article.
It's not the distance to the points in the scene that determine where they appear in a perspective projection, it's the angle. For any single point on the screen/retina/projective plane, it can actually correspond to any distance from the camera/eye (i.e., a ray of possible points).
> for the same reason the effect works in a mechanical DSLR camera
The sensor on the back of a camera is a flat plane, which is why (with most lenses) you get an image where straight lines appear straight. The sensor on the back of your eye (the retina) is curved.
straight lines are straight in a photograph because of precision manufactured optics shaped specifically to achieve that effect, to reduce "chromatic aberrations" and "barrel distortion".
As someone with no experience in computer graphics it's always insane to see demos like this. Especially using just around 250 lines of javascript. Really impressive.
Also on the topic, the demo scene stuff is mind blowing, too. [0]
The nice thing about this implementation is that the code is very clear and easy to follow. You could easily make it much shorter if that were the goal.
Me three. It's covered the 're-read in 6 months time' criteria. I must confess I do change from reading to scanning as soon as the heavy math kicks in.
There's a niche for a website that does a bunch of sub-500 LOC javascript examples of tiny bits of computer graphics, to give a very brief introduction and demonstration of the math, and which then chains them together for some other software.
> Rain is simulated with a bunch of very short walls in random places.
This made me laugh. I would have never thought of that way of doing it, but before I knew how it was implemented, I didn't even notice! That's a pretty good approximation!
Great work. I had a huge amount of fun converting your last article (terrain renderer in a tiny number of JS) to WebGL and that was only fun because of your clean, easy to understand code. Thanks for sharing.
I'm really surprised that it's 265 and not 256... I mean, there's got to be a good reason not to make it a round number, right?
I'm mind blown anyways...
I've seen some people suggest that voxels are like sprites for 3d programming (as far as sheer simplicity goes), but this strikes even more so as that. How does this compare to using actual 3d/voxels? Can you still have interesting physics or do you miss out on a lot?
Thanks! As with most software decisions, raycasters involve a tradeoff. They are related to voxels in that they impose constraints on what can be rendered. Voxels render grids in 3 dimensions while raycasters (typically) render them in 2.
For this reason, you can generally build a raycaster faster and simpler than either voxels or meshes, but there will be things you can't do. Rotation on the x axis is tricky, for example.
It's probably best to think of physics in a raycaster as the same sort of physics you could apply in a top-down 2D game.
Interesting. Does FF 29 on linux perhaps have purely software graphics? It runs much faster than 1 fps on iphones and most androids, 60 fps on modern desktops in safari/chrome, and 30 fps on FF / osx.
Note that it is using canvas 2d rather than canvas 3d (aka WebGL[1]).
But if you take ray casting to extreme, you end up with Ray Tracing[2], which is kinda expensive. Which is why we had such an effusive conversation a few months ago about hardware accelerated RayTracing[3].
Yes, however the raycasting is drawing pixel by pixel. That part is not hardware accelerated, and that is the expensive part. That is that part that shaders speedup a lot, by delegating a lot of the work to the GPU.
That page froze my browser (Firefox 29) and started leaking oodles of memory until I killed it (along with a bunch of other shit I was working on), so I guess I'll count that as a point in favor of software raycasting.
Raycasting brings back memories! I remember poring through raycasting techniques to make my Wolf and Doom clones as a teenager. When I was almost done I demoed this for a group of friends at our school's computer club and boy were they were impressed up until the point the clipping algorithm failed and objects stopped disappearing when they fell out of the players field of view. Was teased for months after that. ... .
Didn't games like Duke Nukem 3d, post-Doom, Wolf games use what was called a scanline algorithm? Drawing the lines in the players FOV as you just stated and then using a clipping algorithm to keep unwanted information out. I think raycasting would be a type of scanline algorithm, but the technique is less primitive since your not using a proper 3d engine. It's a long time since I programmed games like this so am now a bit fuzzy on the specifics.
Thanks for letting me know! It's referenced as a raycaster in several places, and of course the output looks very much like a raycaster's, so I checked up on this.
After a little reading, it sounds like DN3D uses a cousin of a raycaster, as it's still rendering independent columns. Instead of casting rays to find them, it's projecting their vertices. Neat!
I remember being amazed how simple raycasting was when I wrote a similar (though much simpler) engine in Java for a high school project. The "engine" itself was like ~200 lines of code in just 2 or 3 functions. Raycasting is a really clever technology. Cool demo!
I know that the arrow keys have actual arrows on them, but so many modern games have trained us to use WASD to navigate, that if you're going to insist upon the arrow keys for navigation, you should probably mention this somewhere before the link to the demo.
this is incredible. I remember doing something in C in openGL with triple the line count and not nearly as impressive results during a bachelor computer graphics class. This would have been a much more interesting lab.
Thanks for the great work, i can't wait to play around with this!
I (mistakenly) thought it would access faster. In looking for benchmarks to link you to, I found out that's a false assumption. So - no reason to at all :)
https://www.scene.org/file.php?file=%2Fparties%2F2004%2Fbrea...