So I am working with a 2D plane with N arbitrarily placed points and M obstacles which are just straight line segments (no two line segments cross each other). The goal is to determine which points are visible to other points in the plane, in the most efficient way possible.

The naive way to do it is compare every point with other points. That is N(N-1)/2 comparisons at least and for each two points, test intersection of its line of sight segment with all obstacles. This is just very computationally expensive.

Other approach i know of, is to determine area of visibility from each point, as it is done to determine which area of the scene are illuminated from a light source, I believe they use ray casting. We can use ray casting from the source to end points of line segments (obstacles) to determine which areas are visible in the scene. This is to be done for every point in the scene. I don't know if this approach is computationally any better or not.

I am not sure if using space partitioning such as BSPs will help with this problem or not.

But, I will appreciate any advice, help regarding this problem.

Thank you.

Yes, space partitioning will help (it's also the key for fast raytracing).

BSP would do well but because building is expensive it's used only for static data.

The first thing you should try is a simple grid:

Each grid cell has a list to all obstacels it contains or intersects.

Then you walk your line of sight along each grid cell it intersects and check the listed obstacles.

Tune your grid resolution for best performance / memory ratio.

If that's not fast enough, you can try further:

Nested grids to avoid having too much grid cells without content.

Quadtree ('loose' quadtree has advantage each obstacle links to only one node)

Tree of bounding rectangles (BVH)

BSP

k-d tree

... endless list of other tree based approaches

Thank you for the prompt reply.

This problem of determining visibility among N points is just to be used for programming AI.

With the simple grid approach. For one source point, I should raycast from this point to all other points and traverse each of them through the grids and as soon as the ray intersects a line segment occurring in the grid, I stop (no LoS), or, the ray never intersects anything and I reach the grid that contains the point in question, then we have LoS. This approach definitely decreases the amount of intersection tests against obstacle line segments, given that line segments are ideally equally divided among grids. But the issue is, this approach will not give us any other information other than true/false for LoS.

As I know, the raycasting approach as demonstrated here. This will also find the visible areas the AI can see (along with LoS to other points) which we can also use for AI movement for example. But for each point, we cast rays to all line segment obstacles. I am not sure if using any kind of space partitioning will help here with algorithm performance?

I am doing this as a course project, I have to analyse performance of different algorithms to solve this problem. I appreciate all comments/thoughts you guys can give me.

I looked at the article you have linked.

It's nice but not the fastest way.

If your goal is to get a list af all visible line segments and not just a single line of sight, you can do this much faster without rays but using polygon clipping instead.

Also BSP is perfect here.

I've learned about BSPs from Michael Abrashs book: http://www.drdobbs.com/parallel/graphics-programming-black-book/184404919

IIRC it covers the top down 2D case used in Doom which is what you need.

First you need to build a BSP compiler which turns your walls line segments to a binary tree of convex floor polygons.

Then you start with a big polygon that covers the entire scene and clip it through the BSP and also clip away regions invisible from the eye point.

You end up with a set of polygons that contains visible walls at their edges. The polygons themselves define the visible area.

The BSP can be used to implement a faster version of the algorithm from the link as well (it would speed up the raytracing - other things like sorting points by angle would work as described).

First you need to build a BSP compiler which turns your walls line segments to a binary tree of convex floor polygons. Then you start with a big polygon that covers the entire scene and clip it through the BSP and also clip away regions invisible from the eye point. You end up with a set of polygons that contains visible walls at their edges. The polygons themselves define the visible area.

Thank you for the explanation. But none of this makes sense to me right now, as I don't have any experience with video games mathematics and algorithms.

I understand the first sentence though, at the end BSP generation, you end up with subspaces each containing a wall on the edge (that was used to split spaces). But I am still not sure how exactly I will determine LoS between two points in the plane after I have the BSP. When you say that 'start with a big polygon that covers the entire scene and clip it through the BSP', Do you mean traverse through the BSP?

Even then I can't make sense of the last two senstences there.

You end up with a set of polygons that contains visible walls at their edges. The polygons themselves define the visible area.

I don't understand how exactly we end up with set of polygons that define the visible area? and how do they define the visible area?

In the end, When I have a BSP generated, and I want to determine LoS between two given points, do I just traverse through the BSP doing intersection tests with each line segment I encounter and stop if there is intersection or otherwise I end up traversing the whole tree to find out that we have LoS (in this case, number of intersection tests for two points are equal to number line segments, not so optimal i think).

I'll appreciate a bit more explanation or point me to it.

Thank you very much.

Ok, this stuff isn't that easy. For me the understanding came only with implementation.

Assume you already have routines to clip a convex polygon with a infinite line (described in the book i've linked above).

The math here is not hard, but you need to handle numerical precission issues well to make it robust.

The hard thing is understanding the BSP and its power.

I made this picture to explain the algorithm:

First, the BSP generation (1 & 2):

We begin with a bounding rectangle of the entire scene, link all walls to its interior list and now we want to pick our first split to bild the BSP.

We can choose any wall segment for the splitting plane (i use the term plane from 3D because it;s more common than 2D splitting line).

So we test them all and make our decission based on a heuristic: We want to avoid splitting many line segment, we want equal numbers of walls on each side, we want equal area of space on each side. (Thats the reason why building BSPs is slow)

Notice wall 1 and 2 share the same plane, and i have chosen that plane for the first split into blue and red 'floor polygons' or 'subspaces' or 'child nodes' - however we call it. We link both walls to the edge lists of each the red and blue polygons.

Also note the 3rd. wall gets split into two segments by doing so, so we link each segment to the corresponding polygons interior list and continue recursively.

In the next iteration each node has only one interior wall segment, so we use it for the plitting plane, divide space again and lik wall segments to edge lists.

All interior lists are empty now we're done building the BSP.

Second: Clip a arbitary convex polygon through the BSP and do additional visibility clipping from a given eye point (A & B)

We choose a white square to define maximum sight for the eye point (we could also use scene bounding rect for unlimited visiblity range). The process follows the same order we have build the tree.

So our first BSP split (red / blue) cuts the square into two pieces.

The red side is the same as the eye, so no further work necessary, just clip that piece with the red side child BSP recursively: No further intersection, done.

The blue side is other than the eye, so clip away the occluded regions by iterating wall segments from blue poly edge list - we get two polys we need to push down the red side child tree.

One of those new polys intersects the splitting plane (magenta / red) of the child tree, so continue recursively - we have the final result of visible areas.

So, you have an idea now i hope.

It's easier but similar to clip a line segment through the tree (determinate visibility between two points with out the need to calculate visible area first - so faster if you have not too many tests to do)

Or to find to which BSP leaf a point belongs (just determinate side of splitting plane to choose child node).

Also, by linking our white ploygons to the BSP leaves they ended up in, you can quickly determinate visibility for many points (you find BSP leave node for each boint and finally check visible area polys).

You also can temporarily add the visible area polys to the BSP itself if you want, ....

EDIT:

In this picture i've added a 4th wall to illustrate that the additional split only affects its parent polygon, not the entire scene. The other pictures did not make that clear but it's important for a good understanding.

I apologize for being away for about 3 weeks, busy with exams and just finished.

I was able to easily implement 2D BSP trees in python for quick demonstration, randomly generated line segments as obstacles and points to determine LoS between them.

for each two points, I traversed the BSP tree, if the two points lie across the partitioning line segment, then I do an intersection test of LoS and that obstacle at that node, if no intersection, then I move to left and right subtree, if there is intersection, we do not have LoS and we stop.

In case, the points lie on one side of the partitioning line segment, I do not have to do intersection test and move to either left or right subtree, depending on the side.

If we reached the end of BSP tree, then we will have LoS.

Runtime complexity of this would be log(m) <= O(m) <= m, where m are number of obstacles.

However, the tests I did with BSP tree, the average number of traversals remain close to log(m), given that our tree is balanced.

Anyways, I have new concern with BSP trees, since constructing BSP trees is a precalculation step, for example, we may construct trees while we load a level and then use this tree to render and answer geometric queries during we play.

what about moving obstacles, like moving doors, or rotating walls, this will change our BSP tree, how do we reconstruct our BSP tree in real-time?

If a wall segment moves along the partitioning line, then our BSP tree remains the same

if a wall segment moves away from the partitioning line and/or rotates, then our BSP tree will most likely change,

a) either it will partition existing line segments in its subtree

b) it could also now lie on other side of its parent node

Also, like a door opening or closing in a game, our line segments, will move little by little every frame, so in each frame, we will be checking if there is a change in BSP tree and if there is, we reconstruct it, it sounds very computationally expensive.

how do you approach this?