• ### Popular Now

• 12
• 27
• 9
• 9
• 20

#### Archived

This topic is now archived and is closed to further replies.

# line trace and bsp

This topic is 5135 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

hi all, i'm kinda lost with this, though i suspect it's not too hard. i'm working on a renderengine and i have the following situation: - i have my worldspace divided using a bsp tree (split using the worldfaces) - i have a point A - i have a point B what's the algorithm to determine whether or not there's any faces between point A and point B? i've tried searching for it on google, but i found nothing suitable (only college PDF files, nothing too usable). can anyone give me an example in pseudo code? i'm currently checking for all of my faces whether or not it's in between point A and B, but this is extremely slow. any help would be greatly appreciated! marc [edited by - Marc aka Foddex on February 21, 2004 8:25:34 PM]

##### Share on other sites
I believe that what you do is to start with the whole line, at the root node of the tree, and then walk the endpoints down through it until you reach leaf nodes.

When a line is at any given node:
(a) both ends of it are on the same side of this node''s plane - in which case, pass the line down the the appropriate child node for this side of the plane
(b) the ends are on different sides of the plane - first you check to see whether it actually collides with the face (not just the plane), and if you''ve not bombed out from that, split the line into two (one for each side of the plane) and push them down to the appropriate children.

I''m not sure though.

##### Share on other sites
You could use your BSP tree to determine this. First, you would do a recurssive(sp) walk down your BSP tree to determine where points A and B are. You you find a visible surface on that walk, then there is a visible surface

Starting at point B...function FindPointsToA()       if(A and B are both in left node)       {            Left->FindPointsToA();       }       if(A and B are both in right node)       {            Right->FindPointsToA();       }       if(A and B are in different nodes)       {       wall stored in the parent node        might be between them.       }end

Remember, a BSP tree is just a specialized Binary Tree. Execpt instead of using numbers to split up the data, you are using geometry. So if you can determine that A and B are in two different nodes of the tree, then you know which walls (parent node walls) to test aginst.

[edited by - Onemind on February 21, 2004 11:44:56 PM]