TD 2 - Shoot'em Up!

Introduction

The goal of this exercice session is to implement a (very basic) version of a First-Person Shooter (FPS) videogame "à la Doom", making use of a so-called 2.5D perspective (also called pseudo-3D). More precisely, we are going to design a very basic 3D engine, based on a a ray tracing technique in 2D. In order to represent the 2D domain of the game (possibly including walls, obstacles, ...) we will make use, as main underlying data structure, of the well known 2D constrained Delaunay triangulation (refer to the slides of the lecture): each constraint edge will represent a piece of a wall. The remaining (normal) edges will provide a partition of the planar domain into simple cells (triangles in our case), which will allows us to efficiently perform ray tracing. Observe that Delaunay triangulations are one tool for implementing fast ray tracing, among many others: other possible solutions for this problem include trapezoidal decompositions, Binary Space Partition trees, or other hierarchical volume decompositions such as Ball trees.

couverture du jeu Doom

Doom en action

Fig. 1 - A few screenshots of the videogame Doom (1993).

A few words about the 2D 1/2 perspective

The main idea underlying the 2.5D perspective is very simple: the viewer is assumed to be a 2D observer (a point) located at a given position p=(x, y), moving and seeing the planar domain D as a (simulated) 3D scene along a given direction d (the direction is given by a small red arrow in the picture below). The main strategy consists in computing the objects (and their distances) seen from the observer by performing a circular scan of the 2D domain: we simply compute all the rays having the p=(x, y) as origin and whose direction is defined by a given range (defined by a minimal a maximal angle). For each ray r (one for each orientation) we have to compute the first intersection point q between r and closest obstacle (which is thus visible). This planar point q will be associated with a vertical line segment in 3D scene seen by the observer. In order to simulated a 3D perspective projection, the length (more precisely the height) of such a segment is inversely proportional to the distance bewteen p and the intersection point q. See figure 2 for an illustration.

Principe de la 2D 1/2

Fig. 2 - Illustration of the 2.5D: from each ray originating from the observer location (red point, on the left image), we have to compute the closest intersection point q with one the constraint edges of the domains (bleu edges on the planar map). This point is associated to a vertical line segment (purple segment) in the 3D scene on the right. The length of such vertical segment is decreasing with respect to the distance of q from the observer.

Computing ray intersections

The naive way of computing ray intersections with the obstacles consists in checking, for all possible constraint (blue) edges in the triangulation of the 2D domain, whether such an edge cross the given ray. This method has linear time complexity, since we have to check all edges which defines the boundaries of the obstacles: this is by far too expensive, since we have repeat this operation for each ray emanating from the observer (and there is one ray for each pixel column in the image).

In order to improve the runtime performances, we will construct a partition of the planar input domain into input cells that respects the boundaries of the obstacle. More precisely, we are going to use a variant of the 2D Delaunay triangulation called constraint triangulation. The principle of this construction consists in satisying a local Delaunay criterion on all edges, at the exception of those edges that are marked as constraints (blue segments on the picture). So a vertex and a face located on the opposite sides with respect to an edge are allowed to violate the standard local Delaunay criterion. This is an easy way to force the triangulation to contain any constraint edge, while keeping good a good aspect ratio of triangle faces, which is an important property for performing ray tracing.

The Jcg already provides an implementation of 2D Delaunay constraints triangulations. More precisely (see for example the package triangulations2D) you are provided with the following methods

public HalfedgeHandle<Point_2> insert(Point_2 p, Point_2 q) that performs the insertion of a new constraint edge [p,q] into the triangulation.
GeometricOperations_2.doIntersect(s, r) that checks whether a segment s is intersected by a given ray r.
GeometricOperations_2.intersect(s, r) that return the intersection point between s and a given ray r.
del2D.locate(p) that locates a given input point p in the triangulation del2D (teh result is the containing face).

What you are asked to do: first task

Complete the code of the class RayCast: more precisely, provide an implementation of the method public HalfedgeHandle<Point_2> castRay (Ray_2 r, HalfedgeHandle<Point_2> e) that returns the first contraint edge (blue edge in the picture) that is intersected by a given input ray r; you can assume that the origin of the ray is located in the triangle face containing the half-edge e.
Then complete the method public void castRays() that performs the ray tracing for all rays (for a given range of orientations), in order to generate the 3D scene seen by the observer: the results (one distance for each ray) must stored in the array double[] distancesToObstacles.

Une fois ce travail realise vous pourrez vous amuser a ameliorer le moteur en ajoutant par exemple la gestion des collisions, l'utilisation de portes et de teleporteurs, l'afficchage de sprites representant les ennemis, etc. Le potentiel d'amelioration est infini, et vous vous rendrez vite compte qu'ecrire un bon moteur 3D necessite enormement de temps... pas etonnant que les moteurs de Id Software, la compagnie qui a cree Doom et Quake, se soient retrouves dans des dizaines de jeux Doom-like de l'epoque !

Installing the required Java libraries

Do not forget to integrate the Jcg.jar file into your Eclipse project (add it to the build path of your TD2 project, as done for the TD1).

1. Implementing the ray tracer

First download the following files

RayCast.java containing the skeleton of the class RayCast to be completed.
Map.java that provides the graphic representation of the planar domain
the file labyrinthe.edg that encodes the planar map of the domain. Please observe that the input format is very simple: each line contains the 2D coordinates of the two vertices that are extremities of a constraint edge (blue edge).

Remark (create your own labyrinth): you can easily create your own favourite labyrinth by editing the .edg file according to the input format described above. Please observe that, in our case, the constraint edges must satisfy an important criterion: the constraint edges can cross only at their extremities. Actually the current version of the Jcg library does not support the insertion of edge constraints that have intersections (in their interior): as a consequence, the method public HalfedgeHandle<Point_2> insert (Point_2 p, Point_2 q) could probably leads to an infinite loop and thus generate a Stack Overflow exception.

Running your code For running your program just execute the class RayCast using as argument the file labyrinthe.edg: as result your should see a 2D window showing the layout of the map representing the planar 2D domain (as illustrated in Fig.2): the constraint edges are drawn as thick blue segments, while the remaining black segments represent the (finite) edges of the Delaunay triangulation.
Observe that the computation of the constrained Delaunay triangulations is already provided by the Jcg library.

Question 1.1 (walking in the triangulation)

Complete the method

public HalfedgeHandle<Point_2> castRay(Ray_2 r, HalfedgeHandle<Point_2> e) of the class RayCast.
This method takes as input a ray r and an half-edge e: the half-edge is assumed to be located in the triangle face containing the origin of the ray r.
The method should return the HalfedgeHandle<Point_2> representing the first edge intersected by r. The method must return null if there is no intersection.

Two important remarks:
1) we may assume that the origin of the ray r is already known (we know the triangle face containing it): actually, we will need to compute many ray intersections (one for each ray orientation) that originate from the same point (the location of the observer); so will locate this origin point once for all before computing all ray intersections. The input argument HalfedgeHandle<Point_2> e represents an edge of the triangle face containing the origin of the ray.
2) in order to check whether an edge

HalfedgeHandle<Point_2>
e

is a constraint, it suffices to call the method e.isMarked(), that returns true if this is the case (and false otherwise).

Question 1.2 (perform raycasting for all rays)

Complete the method

public void castRays() that first computes the location of the observer in the triangulation and then perform the raycasting for all rays. For each ray, this method computes the distance from the observer corresponding to the closest intersection with a constraint edge. If there is no such intersection (no obstacle in this direction), the method must compute the value -1 (i.e. this occurs when castRay returns null).
The distances computed by castRays() will be stored in an array having viewSize entries, one for each ray emanating from the observer: this array is called distanceToObstacle and is defined in the class RayCast.

Important remark: for the computation of the distances please Do Not Use the method distanceToSegment that, by definition, is computing a different value: the distance from the observer to the constraint edge crossed by the ray. You fill find in the class RayCast a number of useful fields that you will need to implement the method castRays, more precisely:

the 2D location of the observer is stored in the field position. The ray orientation is given by the angle (expressed in degrees) with respect to the x-axis oriented toward the right. This value (the angle) is stored in the field orientation;
the width of the screen (defining the 3D scene) is given by the number of pixels, stored in the field viewSize. The total angle of the camera view (from the observer, including the two sides of the camera axis), is stored in the field viewAngle. So the camera view ranges from the angle orientation-viewAngle/2 to the angle orientation+viewAngle/2.

The two fields above (viewAngle and viewSize) are already initialized (in principle you do not need to update them): by default viewSize=600 (width of the 2D frame) and viewAngle=45 (such a small value guarantees a small distortion, which is a desirable requirement for players). The observer is located at the beginning at the point (-1.5, 1.2), and its view is oriented toward the direction defined by -45 with respect to the x-axis (i.e. the ray has slope -1, being oriented to the right-bottom of the 2D domain).

Important remark (avoiding distortion): in the rendering of the 3D scene we assume that the raycasting involves parallel rays. As a consequence, when looking at an obstacle (a wall) from the front, the height of the obstacle does not decrease when moving away from the view axis. But this way we introduce a perspective distortion due to the fact that raycasting is performed in a circular way around the observer. This distortions is measured by the cosinus of the angle between the ray direction and the view axis.
Thus, in order to avoid distortion, you will have to multiply the computed distance by a term defined as the cosinus of such an angle.

2. Rendering of the 3D scene

First download the file RayCastWindow.java, containing the skeleton of a class dealing with 3D layout of the scene seen from the observer location: the rendering is performed by the method public void paint(Graphics graphics) that you will have to complete.

Question 2.1

Complete the method

public void paint(Graphics graphics) that draws the visible walls (the obstacles) on the screen. Observe that we will use a double buffer in order to avoid flickering effects: thus you will "draw" the walls first using the field bufferGraphics instead of the field graphics. The method paint(Graphics graphics) already performs the drawing of the ground and of the sky using the double buffer: you will have to draw only the vertical walls. It will suffice to perform a linear scan of the array distancesToObstacles[] (already computed): for each entry you will generate a vertical segment having as x-coordinate the index of the entry in the array, and whose length is the inverse of the distance from the observer. The scale factor to be applied to the length is given by the field sceneZoom of the class RayCastWindow. By default we decide to draw the walls by setting relative position of the corresponding vertical segment to be from 1/3 below the horizon to 2/3 above the horizon (the height of the horizon is stored in the field horizon).

In order to test your solution, comment the lines below in the main function of the class RayCast:

Map map = new Map(r);
Collection<TriangulationDSFace_2<Point_2>> facesDel = r.del.finiteFaces();
LinkedList<Point_2[]> trianglesDel = new LinkedList<Point_2[]>();
for (TriangulationDSFace_2<Point_2> f : facesDel)
	trianglesDel.add(new Point_2[]{f.vertex(0).getPoint(), f.vertex(1).getPoint(), f.vertex(2).getPoint()});
Collection<HalfedgeHandle<Point_2>> cEdgesDel = r.del.constraintEdges();
LinkedList<Point_2[]> cSegmentsDel = new LinkedList<Point_2[]> ();
for (HalfedgeHandle<Point_2> e : cEdgesDel)
	cSegmentsDel.add(new Point_2[]{e.getVertex(0).getPoint(), e.getVertex(1).getPoint()});
map.addTriangles(trianglesDel);
map.addFatSegments(cSegmentsDel);

and uncomment the line below:

RayCastWindow f = new RayCastWindow (r);

If everything works fine you should get the rendering of the 3D scene as seen from the player: the rendering should be similar to the one shown in figure 2 (right picture).

3. Texture mapping

In order to improve the rendering of the 3D scene we can apply texture mapping to the walls. First download the texture file stone_wall.jpg, then uncomment the line below

textureImg = ImageIO.read(new File(textureFileName));

in the constructor of the class RayCastWindow. Your code will load the texture image in the field textureImg of the class RayCastWindow; you will get an exception if the file is not found in the folder of the project.

To perform texture mapping it suffices to update in the method paint of the class RayCastWindow the rendering of vertical segments: instead of drawing a connected segment (with uniform color), you will have to draw the segment pixel by pixel, using the texture image.
Please take into account the two following remarks:

the width of the texture does not match the width of the 3D view: you will have to perform some computations on the x-coordinates, modulo the width of the texture;
each texture segment must be rescaled in order to fit the correct height of the corresponding segment in the 3d scene (which depends, as already said, on the distance from the observer).

At the end should get a resulting 3D scene similar to one illustrated below:

Rendu avec texture

3.2 Improving the rendering (bonus)

The result obtaine so far has some not desirable effects:

the texture is more or less stretched along the vertical direction, depending on the distance from the observer;
when the observer is moving in the planar domain also the texture is moving with him;
the texture is mapped in a continuous way between two adjacent walls: it is hard to see the change point between the two walls.

These phenomena have the same origin: the shift in the texture correspoing to a given segment is always computed with respect to the left boundary of the 2D frame, while it should be computed with respect to the left boundary of the wall where the segment is located. To avoid this problem you have to update the method castRays of the class RayCast, and you will have to complete the array distancesToObstaclesBound that stored, for each ray, the distance between the intersection point and the (closest) vertex of the intersected constraint edge Then in the method paint of the class RayCastWindow, you have to compute for each x-coordinate the shift in the texture corresponding to the distance to the left boundary of the wall containing the segment. You have to perform a rescale multiplying the distance from the left boundary by the value textureScale stored in the class RayCastWindow.

The result is illustrated below: there is no vertical distortion anymore, and the change between adjacent walls appears in a more natural way.

Plaquage de texture reussi

A possible solution of this TD is available for download: solution.zip.