Shiru Otaku on reykastinge
RAYCASTING - make yourself a little DOOM'a.
Shiru Otaku
It has long, very long I dream about that
anyone ever do the same on
Speccy toy genre full 3d action
- Not Doom, of course, or there Duke, but khotyaby analog
Wolf3d. At this moment there are very good attempt - Wolf3d
demo (by Alone Coder), Citadel.
Ed.: The game engine Citadel is not based on
reykastinge, so we no longer mention it
will not.
Surprising just why they (attempt) so
small compared with the amount of writing
brethren. Maybe it's just a lack of
knowledge (in my time, I also burned the idea
write something similar, but not enough
it is knowledge - and now do not have the desire)? Based on
this assumption, I decided to dash off an article that
describes the method used in the original Wolf3d by ID
Software, as well as dozens of similar Toy of the time. The
method is called raycasting (not to be confused with
raytracing'om) and was previously used for fast rendering of
pseudo-Space toys genre 3d action. At the moment it is believed
that this method is obsolete because it imposed restrictions on
the complexity of the display space, but he still used on
machines with limited processing power - Such as Palm Pilot,
GameBoy Advance. Think that this method is quite suitable for
implementation actually playable analogue
Wolf3d and Speccy (which proves itself,
For example, Wolf3d demo - it uses
a special case of reykastinga).
I describe a method reykastinga in its simplest form (the
walls of the same height with the texture only at right angles
to each other, gender and ceiling without textures). I will not
give kakielibo specific solutions - only general principles,
algorithms, formulas. Specific solutions depends upon the
encoder implements These algorithms - than optimal code had
come, the better the result (there is no limit to perfection,
giving 15fps at 3.5 MHz:) I warn once - like all morochki with
3d-graphics, all described hereafter will require some
knowledge - the Pythagorean theorem and other mathematics at
secondary school level.
WHAT IS RAYCASTING?
Reykasting - a method of converting
limited form of data (a very simple
Map of floors) in a three-dimensional projection by tracing
rays from the viewpoint of volume of the review. It is not I
clever to express, just read of the book:) In general, the
following figure, I think, will explain more clearly:
It should be noted that the application reykastinga not
limited to the construction such a projection - it can be used,
for example in the construction of voxel surfaces (a la the
background in the Commanche to the PC). Defining property
reykastinga is that the rays are traced from the viewpoint of
volume - as opposed to ray tracing, where rays are traced from
the objects in the scene to the point review. Also, if a ray
tracing rays traced for each point of the screen, then
reykastinge always perpendicular to the wall
sex, and so it is possible to trace only one beam to a column
of the screen - which is why reykasting and is the fastest
method for constructing three-dimensional projection.
Ed.: If you compare the speed all
Possible applications of pseudo-then
faster reykastinka will be two methods
visualization of the road surface for racing: Line (usually for
ZX) and a projective plane.
2.5D OR LIMITATION RAYCASTING'a.
Benefits reykastinga in high-speed rendering of space, but
for this rate to be paid - to pay heavy restrictions and
simplifying the display of the world. His are not even the
really three-dimensional - because in reality it is only a
three-dimensional projection of the usual flat map. In the
original method reykastinga does not allow split-level floor
and raznovysotnye wall. In fact, this it is still possible -
see Doom or Duke3d (maximum capacity reykastinga), but, of
course, it requires no longer such a small computational
resources. On the other hand, during the 286-s processors,
where three-dimensional graphics in real time was
possible except on the SGI, these simplifications
were insignificant price. They will not
great price and for Speccy.
The main limitation reykastinga - wall to the floor /
ceiling must be only at right angles (otherwise lost
the possibility of tracing a single ray in
column, and lost all the advantage in speed).
Also, usually, the wall can only be
two kinds - vertical and horizontal
(If you look at the map above). This restriction is necessary,
but it complicates and slows program (hence the diagonal wall
is not in the same Wolf3d).
THIS SQUARE, SQUARE WORLD ...
Thus, when considering the principles reykastinga we will
abide by the following schimi constraints of our world:
- The walls are always at right angles with respect to gender.
- The walls are the equilateral triangle of bricks.
- Paul is always flat (one level).
The size of each cube, we take for 64h64h
x64 conventional units. Of course, it could
be any other number that is the power of two (this is to be
there at all using a shift operation). The more
size of the cube - the greater the simplicity of the space
(large cubes), but higher speed, and vice versa - with small
cubes tracing process will take longer. The size of the cubes
is to choose, based on the estimated amount of future textures
- if they are 32x32 (which most logical for Speccy) - then the
size of the cubes should choose 32h32h32, it will simplify the
calculations. In general, our world would look like this:
WARNING! Before continuing, it is necessary to determine the
very important thing - coordinate system. Further
clarifications will be used the following system of coordinates
(Cartesian):
That is, X - the horizontal axis, positive values - the
right; Y - vertical, positive value - from the bottom. 0
degrees - to the right, and then Counterclockwise arrows (top
90, left 180, bottom 270). This should be taken into account
when considering the reasons mentioned below - otherwise there
will be unnecessary glitches.
Now on. We define some more
things:
- The viewing angle (field of view, Field of
view, FOV), the coordinates of the player (point obzo pa).
- Dimensions of projection plane (projection of the plan - it
sounds ugly, I'd rather have used English term).
- The relationship between the player and the projection
plane.
The player sees what is before him.
His field of vision has a certain angle
(FOV). Angle determines how much the
player sees the world around him. People have
viewing angle of 90 degrees or more (Eds:
170 ° - can check it yourself
spreading his arms and moving his fingers), but
best form on the screen we will FOV for
60 degrees. By the way, if you change the FOV in a wide range
(up to 120 degrees Celsius) - can be get amusing effects, such
as "fish-eye" - as in Duke3d, when the Duke gives a pop
reducers.
Ed.: I like the angle of 90 °. This corner of the screen
still does not match any of the proposed values - it is less
than 40 °, which is obviously not applicable as the FOV.
To move a player in the space
it must have three coordinates - Y, X on
two-dimensional map (seen above), and
and point of view (POV) - "point of view,"
Although it is logical to say - line of sight, in degrees. If
the POV is 0 degrees - player looks right on the map (again,
if you look at the map above).
That explains this picture (for those who do not
understood) that the FOV and a POV, and shows where to look and
what to see player, if its FOV = 60 degrees, and POV =
= 45 degrees.
The last - we need to define our
projection plane, that is, roughly speaking,
size in points (not pixels, since at
Speccy points may be, eg, chunks)
our window where we will draw
projection. In the dock, in explanation of which I write
this article, it was designed for standard resolution VGA
320x200, therefore, not to be confused myself, I will leave
just such window sizes - 320 columns, each 200 pixels in height
(after all it is theoretical example, and not practical), but
for the real problem, of course, have to choose
a more reasonable size - for example, 64 * 48
points. Keep in mind that the wider the projection plane, the
more rays will trace, and hence the slower
work program. Height of the projection
plane does not affect the rate of trace
rays, but can affect performance
scaling procedure column. Coordinates of points on the
projection plane are common - the origin (0,0) is at the top
left corner.
"CAST A RAY".
Now that all the initial parameters are defined, you can
begin to describe the principle of constructing the projection.
To start small, but nice chertezhik (hell-whack;):
From all this we know:
- The size of projection plane is 320x200
points.
- The Center is located in the projection plane
160.100.
- The distance to the projection plane = 277
units (half the width of the projection plane /
tangent of half the FOV).
- The angle between adjacent rays = 60/320
degrees (60 degrees FOV / width of the projection plane).
These values are constants, they
will not change further (unless you do not
want to make a variable in realtime FOV
:), So if you wonder where are the
different values - you can not wrestle, but just use them.
The angle between neighboring rays - is the same as the angle
between adjacent columns, we will use this value for the
transition from the column to a column in the trace. Distance to
projection plane will be needed to get a picture of a normal
scale.
Our projection (wall display) can be regarded as a 320
(width of the projection plane) of vertical columns. For each
of them we traced a single beam. Leftmost column is fitting the
angle POV-(FOV / 2) for the rightmost POV + (FOV / 2). From
column to column, you can move, adding to the initial value of
POV-(FOV / 2) at each iteration FOV/320.
Thus, an algorithm for constructing the projection is as
follows: 1. Subtracted from the current POV half FOV -
This is our corner of the current beam.
2. Starting from column 0 (left):
- "Cast a ray", as they say amerikosy
;) - Emit luch.Luch proceeds of which
ordinate in the direction of the player POV.
- Go to the ray cells, while not a priest
We introduce into the cell with the wall.
- Remember the length of the resulting beam.
3. Adding to the corner of the current beam FOV/320.
4. And so all the columns (320 times in our case).
While everything is simple, but there are two important
momenta.Pervy - need to be sure that the beam will sooner or
later will meet stenku.To has at least the entire map of the
perimeter wall must be fringed. Also do not forget that the
further necessary to trace the beam - the slower the
construction of the projection as a whole. Therefore it is
necessary to limit the range of reasonable review of the limit
formulas (pick up by eye).
Ed.: This limitation will add little
velocity in the Wolf-like games - well
planned labyrinths contain no halls where on one wall can not
see the opposite. Restriction helps in games open landscape.
The second important point - we do not need
take each point of each cell (accuracy is required - otherwise,
do not build a projection), enough to check the boundary cells
- Figure:
We are only interested in points A, B, C, D, E, F
We have to go through them one by one, checking for the
presence / absence of the wall in the cage. The simplest (but
not the fastest) way - to trace the beam twice, checking
at first only horizontal, and then only vertical intersection;
remember both found the distance to the walls, and select
blizhayshee.Razumeetsya of them, you can check
and merge, but it is much more complex algorithm for ray
tracing (and maybe add speed, but maybe not;). I will describe
simple way to separate.
The whole trick is that the distance between
all horizontal (or vertical)
odinakovy.Eto intersections can be seen
from the figure (on the left for horizontal, right for vertical
intersection):
We call the vertical distance to the next point, Ya,
horizontal Xa. Will find all horizontal crossings. Ya
easy to find - is the height of the cell (64 in our case). Xa
can be found by the formula Xa = = 64/tan (beam angle). Of
course, for Speccy tan every time considered too expensive, but
you can find a sign for all possible angles in advance. To find
the vertical intersection Xa is the width of the cell, Ya = 64
* * Tan (angle beam).
Now a more detailed algorithm. WARNING! Remember the used
coordinate system! Y-axis positive values is at the bottom,
and negative - on top!
Ed.: If you write a program, but not
guess this sign (which, I fear, has happened in
this article;), try to take corners curled not against it, or
clockwise.
Tracing the intersection of horizontal (position player Py,
Px; coordinates inspected point Ay, Ax):
1. Find the first nearest intersection (point A). If the beam
goes up - Ay = int (Py / 64) * 64 - 1, if the down -
Ay = int (Py / 64) * 64 + 64. Ax is
after calculating the Ay: Ax = Px + (Py-Ay) /
/ Tan (angle beam).
2. Find Ya. It is the height of the cell,
ie 64 in our case. If the beam should be
traced upwards - Ya must be of negative if down - yes.
3. Find Xa. Xa = 64/tan (beam angle).
4. Check the intersection for the presence of the wall. To
check the current position to convert the coordinates of the
cells - that is, divided by cell size (shift)
In our case, to check the cell in the coordinates Ay/64, Ax/64.
If the wall is - remember the distance of Py, Px to Ay, Ax and
stop the cycle.
5. If the wall does not - go to the next intersection. Ax =
Ax + Xa, Ay = Ay + Ya, and way to victory.
Trace of vertical intersection is not much different
(position player Py, Px; coordinates of the points tested By,
Bx):
1. Find the first nearest intersection (point B). If the beam
goes to the right - Bx = int (Px / 64) * 64 + 64, if the left -
Bx = int (Px / 64) * 64 - 1. Further, By =
= Py + (Px - Bx) * tan (angle beam).
2. Find Xa. It is equal to the width of the cell,
ie 64 in our case. If the beam should be
trace left - Xa must be of negative, if the right - yes.
3. Find Ya. Ya = 64 * tan (angle beam).
4. Check the intersection for the presence of the wall. If
the wall is - remember the distance yanie of Py, Px to By, Bx,
and stop the cycle.
5. If the wall does not - go to the next intersection. Bx =
Bx + Xa, By = By + Ya.
After two traces choose that point which is closer (Compare
the distance), for her and we will draw a column. In the above
example, it is in the pictures is the point E.
Need to elaborate on how
find the distance from the player to the wall. There
several ways. I'll tell you about the two. Lack of them is that
one must assume square root, and in another - the sine and
cosine. Can simply calculate the distance (X = X2-X1, Y =
Y2-Y1), but it will be harder to deal with distortions (for
them - next section).
The first way - the distance from Px, Py to
endpoint Ex, Ey = sqrt ((Px-Ex) ^ 2 +
+ (Py-Ey) ^ 2). This method is inconvenient,
that a lot of slow operations - two of multiplication and
taking the square root.
The second method - distance = abs (Px -
Ex) / cos (a) = abs (Py - Ey) / sin (a), where a =
beam angle. This method is convenient in that sign of the
cosine and sine can be calculated in advance, and from slow
operations - one division.
Once we found the distance to
columns, you can already begin drawing projections.
CHANGES file.
But there is one "but." If right now
draw the columns (no texture) to found the distances to them,
we can greatly break off - instead of, say, a straight wall, we
see something like this:
Ed.: Think of the game Doom Mania.
This is because we do not take into account the singularity
monitor screen. The fact that he, unlike the human eye is not
spherical, and flat. And therefore, if the distance from
point of view to straight wall in the middle
one, the distance from the point of view to the edge
View area - another. So, we need to adjust the distances to the
column, given that fact.
Distortion is easy to remove by this formula: distance =
correct the distorted distance * cos (a), where a - angle of
the current beam. The value of cos (a) can be calculated in
advance for each of the columns, then we have get a plate of
320 numbers (the angle a varies from 30 to -30 degrees - do you
remember about our coordinate system!), and all found
distances need to be multiplied by the values of this plate.
Ed.: Do not forget that we remove this
only vertical, but horizontal
iskazheniya.Tekstury at the edges of the screen compared to the
center will be compressed horizontally. In the Wolf demo for ZX
do not, because not applicable arithmetic method and scanning
ahead, the scale has been adjusted in the "fan" vertorov scan
(periphery of the screen is scanned over major steps, the ends
of scan vectors, collected in one bundle, indicate points
uniformly located on the same Line).
In general, for Speccy these multiplications - a big loss of
speed, and therefore worth trying to remove or turn down the
distortion kakimlibo other sposobom.Nu yes it's already on your
discretion:). And now, finally ...
BUILD THE WALL.
Yes, now we need to - to draw
on the screen of columns desired height (which
You can learn from the distance found for
each column). Well, so let's draw. Until
You can draw just completed one
color bars to see the corridors,
later add texture.
The height of the column is as follows: height
Textures / distance to the column * 277 (I hope you remember
where it came from a 277 - I mentioned this at the beginning).
The top point on the screen with which to draw
column is even simpler - the height of projection plane / 2
minus column height / 2. You can draw.
But we must point out one pitfall.
If you do everything as written above,
can observe small distortions
seemingly straight walls, as if to pull on
their texture (see below) - sometimes on the flat lines will be
visible teeth - the closer to the wall, so they bolshe.Chestno
speaking, I did not understand from where they arise, but to
get rid of this effect is simple, if you round off the height
of the column to an even number (Was 31 - will be 30, etc.). It
is almost completely removes the effect of teeth (a bit
remain, but this is due to errors District leniya).
Ed.: Indeed, the steps can be
kill the rounded heights of up to a multiple of 2. But
it lowers the accuracy of scale! Therefore it is better to
scale each column from the middle - may even be fractional
height.
Sticking WALLPAPERS (Texture on the wall).
It remains quite a bit - pull on
wall teksturu.Eto very prosto.Nam need
only to find out which of the columns of the texture
you want to display for each of the columns of the screen, then
pull it through a scaling procedure (I will not tell you how to
write such a procedure - it is much easier than the algorithm
reykastinga, so that help themselves). And to know quite easy -
we take the coordinate Y, if was found by a column of vertical
walls, or X, if the column is horizontal trims
it, for example, AND'om, leaving the last 6
bit (cell size 64) - it will be necessary shift in the texture.
Remains to derive the column texture, stretching it vertically
to the desired size.
FIRST STEPS IN A SQUARE WORLD.
Well, now we have a wonderful
wall, with a texture, without distortion. But while
We consider only one point, not having
opportunity to wander through the okrestnostyam.Nado
still make the normal movement of the player
in prostranstve.Normalnoe - is when your left and right players
are deploying around its axis, and forward-backward allow move
in this direction. Yes More would be nice to not be like a ghost
and yet not go through stenki.Eto too easy.
We have the coordinates of the player Px, Py, and the angle
Pa (POV). We still need two parameters - the speed of movement
and speed Pspd reversal Prot. On your left and right
changes need to hang Pa - add and
diminish its value to the Prot. At the same time
a good idea to make sure that Pa was in the range of 0-359. To
move forward (key up), we need to find the next point on
vector Pa, at a distance from the current Pspd.
We find:
Px = Px + cos (Pa) * 10; Py = Py + sin (Pa) * 10.
To move backward to, respectively, subtract, not add
znacheniya.Chtoby not pass through walls, you need to check
new point found for the presence of
wall, and if there is a wall - that or just do not
go, or - even better - to try to reduce Pspd, until a free
point of the.
Ed.: It is recommended to consider the wall space, separated
from the real wall is closer than on the "radius of character."
This is due to the fact that the wall at zero distance visible
in the infinite (in any case, large and unaesthetic)
magnification.
You can also add inertia when walking
and the turn - but that's not me you
to teach:).
Sit down on the track.
You can add our engine features such as the effect of jump
squats or player. To do this, merely to shift the center of
projection plane in the calculation of the top of the output
column - if reduce, then sit down, increase - jump. Very simple.
Not just as simple and portray glance
floor or potolok.Dlya this when calculating the highest point
to take away from half the height of projection plane is not
half the height of column, and a third or a quarter - in
general, Experiment on health.
And about the object.
The result was almost a game - there are
three-dimensional maze, it is possible to wander. But apart
from the walls did not, but it is not very interesting. Need
enemies, many enemies, and some pistols:) Yes and no doors
would have prevented. Only now I'm very tired
writing this article, therefore, briefly discuss
general ideas, and you really think out for yourself.
Door a la the original Wolf3d. They can be made as follows.
If, ray tracing was in a cage with a door -
this cell, we will be tracing the point-wise. If at some point
in the beam cross the cage in the middle - the place where the
door - then this point we take as found distance. The door will
then be like in the opening half the width of the wall
(Itself the door will, of course, "cardboard" -
thickness of a pixel, but it is invisible, because
not often prhoditsya watch the door in the butt
;).
Objects - the enemies, all sorts of vases and night
Other utensils - can be displayed using
conventional methods of 3D-graphics. That is stored
their X, Y coordinates, and when you turn the player
rotated around the axis of all these coordinates, with
output using the usual projection
3D-point on the plane (3D coordinate X = X
in our space, Y = 0, Z = coordinate
X our level). The main conclusions of those too
on the vertical columns, given the distance to the wall - if
the wall is closer than some of the columns of the object -
display wall, then - display wall first, then on top of her
column object.
If possible (for the derivation
screen using chunks, for example) - is
use change in the brightness of columns in
Depending on the distance - can improve
intelligibility of the picture (the farther wall,
those "dark").
IN CONCLUSION.
Well, all I enlighten you - now let's go
All rivet Woolf and the Duma:) I also want to
notice that the engine can be really fast
done only if a well thought golovoy.Napisat ray tracing can be
dozens of ways, there are many opportunities minimize the
number of required realtime-computing, simplifying the
algorithm etc., etc. So it all depends on you:)
Behind the scenes there are many themes, for example,
rendering using textures reykastinga
floor and ceiling - I did not describe this
process, since for Speccy he clearly is not acceptable because
of speed - even on the PC it does not work very quickly
(because the original Mr. Wolf3d and no textures on the floor /
ceiling)
Ed.: The cost of floor and ceiling are more
the cost of scaling the walls - which
itself occupies about half of all time
algorithm. That is, from the floor and ceiling slowly two times.
Nevertheless, if something interesting -
necessary information without any problems in
Network. For example, I can recommend chapter
of the PC-GPE "Doom technique", or referred to the line below
the dock.
This is all based on the dock
"Ray-Casting Tutorial" by F. Permadi, (C)
1996-01 (English original can be found
on http://permadi.com/tutorial/raycast/),
for which I was self taught, and is arbitrary
a translation / paraphrase of his words,
greatly shortened and my doubt is very valuable additions;)
Shiru Otaku/ANGEL2 (shiru@mail.ru)
