CODEWITHSUNDEEP
c++algorithm
ulak blade
ulak blade

Reputation: 2665

Could someone explain this algorithm that uses raycasting?

http://www.redblobgames.com/articles/visibility/

It's the first part:

Calculate the angles where walls begin or end.

Cast a ray from the center along each angle.

Fill in the triangles generated by those rays.

I'm doing something like this:

    vector<float> angles;

    for(int i = 0; i < polygonCoordinates.size(); i++)
    {
        for(int j = 0; i < polygonCoordinates[i].size(); j++)
        {
            angles.push_back(AngleBetweenPoints(LIGHT_POSITION, polygonCoordinates[i][j]));
        }
    }

Where polygonCoordinates is a 2D vector, basically each polygon is a vector of Point2D structs and all polygons are inside a bigger vector.So after I find the angles, how do I proceed?Why do I need raycasting?How will that help me generate the "light polygon"?

Upvotes: 1

Views: 2164

Answers (1)

BWG
BWG

Reputation: 2288

First things first: Sort your angles and their corresponding vertices from least to greatest.

Start with your viewer 'aiming' to the left, and store the nearest visible point (which happens to be on the wall) in tmpPoint or something like that.

enter image description here

Then, you go through your list of angles you calculated. You are going to sweep out the whole area of the screen, clockwise (do this by iterating through your list of sorted angles). The first ray you are testing is the bottom left of the little rectangle (it has the lowest angle that you calculated). The nearest visible point is on the left wall somewhere. Your visible triangle list, add the triangle formed by the viewer, tmpPoint, and the point you just found. (see picture) Finally, store that point in tmpPoint.

enter image description here

The next point we check is the upper left of the little rectangle. Here is where we really need to check for visibility. The nearest point is the visible one. (see picture) Then, add your triangle (composed again of the point you just found, the viewer, and tmpPoint). Just repeat this process over and over, and you will eventually fill your whole screen with triangles representing visibility.

enter image description here

I hope this helps. I made some nice pseudocode, but I was doing it wrong, so here are just the graphics. :P

Edit:
So you have your verticy array all calculated out, and by calculated I mean visibility of the rays. What you do is something almost like this:

for(int i = 0; i < calculatedVertices.size()-1; i++) {
    triangle t = triangle(
        calculatedVertices[i],
        calculatedVertices[i+1],
        centerViewer);
    triangleArray.add(t);
}
//the loop above misses one triangle, so just add the last one
triangle final = triangle(
    calculatedVertices[0]
    calculatedVertices[calculatedVertices.size()-1],
    centerViewer);
triangleArray.add(final);

This nearly fully works, except for one terrible issue:

enter image description here

You see, when you have your far-wall cast triangle, the intersection should occur on the wall, but when you have your triangle cast to the rectangle, the intersection should occur on the rectangle itself. If the intersections don't occur in this manner, this will happen:

enter image description here

I'm not entirely sure if this is an actual problem, or if its just something i'm thinking of, but a way you can solve it is by adding a slight bias (of your intersection detection) towards your other vertex, if you know what I mean. That should fix this problem.

Upvotes: 6

Related Questions