Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# BSP tree for choosing closest point (from a selection of randomly distributed points) from current point?

Posted on 2006-04-28
Medium Priority
422 Views
Hello,
I have a large collection of randomly distributed points in 3D and I wish to repeatedly find the closest point to another arbitrary (moving) point. I am aware of BSP trees and but don't know how to go about impementing one in C++ and all the examples I find are for depth sorting polygons. Is a BSP tree the best way to approach this problem or is there another way of doing it? If a BSP Tree is a good solution can someone tell me how to implement one for this?

Philip
0
Question by:aardmancgi

LVL 25

Accepted Solution

InteractiveMind earned 672 total points
ID: 16561875
Yes Philip, BSP tree's would be my personal choice also.

Exactly how this is implemented would depend on roughly how many points there are in your collection, and also the speed that your dynamic point is moving. There may also require some level of trial and error to find the best performing configuration.

Generally, You could split the entire 3D scene up into a group of 'boxes'. The boxes should be modelled within some sort of 'Box' class; which either stores all of the sub-points in an array, or stores the first point within that box, which then references the next point, which then references the point after that, and so on (..nodes).

When you need to find the closest point to your dynamic point, you find which box it is in, then find the closest point within that box, to your dynamic point.
One way to do this, would be using a customized quick-sort.

You could also have each box consist of other boxes (sub-boxes). These boxes would then either contain more the points within that region, or even more sub-boxes!

But this part is dependent on things like how many points there are, how well they're distributed, et al.
0

LVL 85

Assisted Solution

ozo earned 664 total points
ID: 16561880
0

LVL 25

Expert Comment

ID: 16561883
Here's a great article on BSP tree's from GameDev, which demonstrate how to implement BSP trees in C++:
http://www.gamedev.net/reference/articles/article657.asp
0

LVL 11

Assisted Solution

WelkinMaze earned 664 total points
ID: 16561884
Hi, you can look at this link:
http://mindprod.com/jgloss/hangingmoss.html
0

Author Comment

ID: 16562426
Thanks for your replies, I see that the exact set-up of the tree would vary depending on the number of points in question and their distribution. In this case it varies but could well be 1 million+ so I cirtainly will need to use some sort of tree to speed things up. My main question would be more about  setting up BSP trees in for a beginner.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may he…
Today, the web development industry is booming, and many people consider it to be their vocation. The question you may be asking yourself is – how do I become a web developer?
Progress
Starting up a Project
###### Suggested Courses
Course of the Month14 days, 2 hours left to enroll