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

Posted on 2006-04-28
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

    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 84

    Assisted Solution

    LVL 25

    Expert Comment

    Here's a great article on BSP tree's from GameDev, which demonstrate how to implement BSP trees in C++:
    LVL 11

    Assisted Solution

    Hi, you can look at this link:

    Author Comment

    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

    How your wiki can always stay up-to-date

    Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
    - Increase transparency
    - Onboard new hires faster
    - Access from mobile/offline

    Join & Write a Comment

    Suggested Solutions

    RIA (Rich Internet Application) tools are interactive internet applications which have many of the characteristics of desktop applications. The RIA tools typically deliver output either by the way of a site-specific browser or via browser plug-in. T…
    Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
    In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
    In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

    733 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

    Need Help in Real-Time?

    Connect with top rated Experts

    25 Experts available now in Live!

    Get 1:1 Help Now