Simple 3D Scene
Please note - this problem is split into two tasks to make explanation and debugging less complicated. Here is the second part.
Nowadays 3-dimensional games are very usual. However at the
1990-s they looked like some fantastic from the future -
notwithstanding that image and scene quality was far lower. Wolfenstein
and Doom were met with great enthusiasm among
gamers - while puzzling programmers with question "How could this be done?"
Let us learn the rendering of basic 3D scene. Games with such graphics were preceding two mentioned above - they could be met even on platforms like ZX-Spectrum. Instead of putting user into some whimsical maze of rooms they gave you an image of open and almost plain space. You should be able to play with the demo above to get the feeling of such games.
Though simple, it allowed wide range of game ideas - from rallying through the forest to hunting enemy tanks etc. This approach allows rendering simple sprites (images like these fir-trees) and opaque shapes like pyramids (hills and mountains) or cubes (buildings etc.) - though often without any texture.
Let us concentrate on rendering sprites - you will easily invent any other tricks if you understand necessary calculations.
Assume for simplicity that the sprite is a vertical segment of the line, sticking upwards from the ground. (When you
are ready to draw images instead of lines, they only need to be scaled to the same height and placed so that the line
passes through their center). So the sprite on the plane is determined by its coordinates (
Y) and its height.
The player also is at any moment placed somewhere - his position is described not only by two coordinates, but also by direction in which he is looking. The first step to render the scene is to translate coordinates to player's frame of reference. This operation is just an extention of Rotation in 2D Space problem.
Look at the scene through the prism of math (as seen from above). Green dots are objects surrounding the player (like trees). The player himself is small blue dot - and blue arrow shows the direction which he is looking at.
Imagine that the player holds before him transparent glass screen, through which he is observing the scene. This screen is shown as a red segment in a picture. Surely it is not possible for player to see objects which fall outside the bounds of this screen. So the visible part of the scene is an angular sector (outlined with grey).
Before rendering anything on the screen it is quite convenient to translate the coordinate system in two steps:
Below is the same image, but with coordinate system translated to user's:
As a first part of scene rendering, you are to perform coordinates translation and rotation and then output new coordinates of objects, but only of visible ones. Besides limiting visible area by angle let us also agree that it is limited by range - i.e. objects very far away are not visible (which is convenient if the scene is very large).
-50 <= X,Y <= 50;
0.5units and width of the screen is
0.5) and not further than
Input data contains total amount
N of objects (points) in the first line.
The second line contains coordinates of the player
pA (angle in radians, counterclockwise from the
N lines follow giving
Answer should contain coordinates of the objects after translation, in the same order as given in input, but skipping those out of visibility. Values should have precision
1e-7 or better.
input data: 3 1 1 0.78540 40 -2 11 11 -8 -3 answer: 14.142135624 0
After we have all coordinates translated, we need only sort objects by decreasing of distance to them (so we can drow the furthest at furst and they will not overlay nearer ones) - and then draw images of these objects on the screen calculating screen coordinates as explained in the sequel to this task.