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


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

Posted on 2006-04-28
Medium Priority
Last Modified: 2010-04-17
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?

Thanks in advance,

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.
LVL 85

Assisted Solution

ozo earned 664 total points
ID: 16561880
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++:
LVL 11

Assisted Solution

WelkinMaze earned 664 total points
ID: 16561884
Hi, you can look at this link:

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.

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

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?
Starting up a Project

580 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question