Took the wonderful project of NCase’s Sight & Light code, and started tweaking it to my own uses.
I really love the project, since there is such immediate gratification when just scrolling through the demo page, and reading and grasping how the ray casting is done, step by step. The page shows how the end result is built.
- is written during when I’m learning basics of 2D graphics
- introduces fundamental concepts: point, ray, intercept
- talks a bit about performance of finding an intercept of two lines
- Khan Academy: Ray tracing intuition (superb video lesson)
I keep talking about intercept pretty much. Let’s get that out of the way.
Intercept in ray casting
An intercept is the Point where a ray meets another piece of line. You may call the piece of line also segment. Purpose is to shoot a ray, and see where (or whether) it collides on the other lines in the Scene.
Here’s a image to explain the intercept:
The question that raycasting answers is basically:
if you (the viewer) are on a point in a 2D plane, where (a point) will your ray first collide into a wall?
There are a lot of applications of ray casting. Some are:
- determine visibility of objects to a viewer
- bullet collisions
- determine the angle of collision between ray and object (though not directly from Intercept alone)
- reflection of light beams (especially in ray tracing method of producing images)
Determine shadow areas vs visible areas
If a whole bunch of rays area cast, you will get basically 2 areas:
- areas that are visible to you (where you can see into)
- areas that will fall into shadow regions
Let’s look at picture probably worth a thousand words.
The crucial code is about finding out the (X,Y) point of a Ray, in relation to all polygon objects present. The polygons are those oblique boxes. Poly means “many” – the object is made of many points connected by lines. If we have more than 3 points in a shape, it’s basically a polygon, whereas only 3 points would make a triangle.
What are rays?
Segments represent something concrete in the scene, like walls, or boundaries of objects. Rays are ‘invisible’ things used to gauge. They work as part of the graphics engineer’s toolbox.
Ray starts from a point (X,Y) and ends up in another point.
Rays are fundamentally important building blocks in computer graphics. They represent how light actually travels in our world: it’s a rather straight line. Real light does bend, however. This is due to the physics of light: light has both a wave and particle behavior. It’s called dualism.
But in many instances, especially your first 2D games, you don’t really need to think about bending of light. Think of rays. They are cast from a point to a direction.
Rays are represented often in parametric form. This kind of ray has three properties:
- ray Point of origin
The ‘T’ runs from 0 to 1, smoothly. When it is 0, we will be at Ray origin. The T=1 will give end of the ray Point. So a line between these points will draw us the whole ray.
- a drawing command line (P, E) will draw us a ray
- P = (X,Y)
- E = P + T*delta
Rays (think of them as lines) are stored in parametric form. If one were to do everything from scratch, you might possibly first consider a very primitive way to check the collision.
At least I thought of something like this: move along the line’s direction by using X and Y increments, until you either hit a boundary pixel of a polygon (“a building wall”), or you run out of the canvas – in which case you know the line does not collide with any of the polygons in scene.
The problem with such a traveling worm method is it’s s-l-o-w.