C++ Algorithm to Filter Irrelevant Coordinate Data

Question

I'm currently working on a hobby project in which I have several thousand stars in a 2D fictional universe. I need to render these stars to the screen, but clearly I don't want to have to operate on all of them -- only the ones that are visible at any given time.

For proof of concept, I wrote a brute force algorithm that would look at every star and test its coordinates against the bounds of the player's screen:

for (const std::shared_ptr<Star>& star : stars_) {
    if (moved_)
        star->MoveStar(starfield_offset_, level_);
            position = star->position();
    if (position.x >= bounds_[0] &&
        position.x <= bounds_[1] &&
        position.y >= bounds_[2] &&
        position.y <= bounds_[3])
        target.draw(*star);
}

While this clunky method does, indeed, draw only the visible stars to the screen, it clearly operates in linear time. Since stars are only part of the background and, frankly, aren't the most important thing for the processor to be spending time filtering through, I'd like to devise a faster algorithm to reduce some of the load.

So, my current train of thought is along the lines of using binary search to find the relevant stars. For this, I would clearly need to sort my data. However, I wasn't really sure how I could go about sorting my coordinate data -- I couldn't think of any absolute ordering that would allow me to properly sort my data in ascending order (with regards to both x and y coordinates).

So, I implemented two new containers -- one for the data sorted by x coordinate, and the other by y coordinate. My original thought was to take the intersection of these two sorted sets and draw the resulting stars to screen (stars whose x and y coordinates lie within the screen bounds):

struct SortedStars {
    std::vector<std::shared_ptr<Star>>::iterator begin, end;
    std::vector<std::shared_ptr<Star>> stars;
} stars_x_, stars_y_;

I then sorted these containers:

// comparison objects
static struct SortX {
    bool operator() (const std::shared_ptr<Star>& first, const std::shared_ptr<Star>& second)
        { return (first->position().x < second->position().x); }
    bool operator() (const std::shared_ptr<Star>& first, const float val)
        { return (first->position().x < val); }
    bool operator() (const float val, const std::shared_ptr<Star>& second)
        { return (val < second->position().x); }
} sort_x;

static struct SortY {
    bool operator() (const std::shared_ptr<Star>& first, const std::shared_ptr<Star>& second)
        { return (first->position().y < second->position().y); }
    bool operator() (const std::shared_ptr<Star>& first, const float val)
        { return (first->position().y < val); }
    bool operator() (const float val, const std::shared_ptr<Star>& second)
        { return (val < second->position().y); }
} sort_y;

void Starfield::Sort() {
    // clone original data (shared pointers)
    stars_x_.stars = stars_;
    stars_y_.stars = stars_;
    // sort as needed
    std::sort(stars_x_.stars.begin(), stars_x_.stars.end(), sort_x);
    std::sort(stars_y_.stars.begin(), stars_y_.stars.end(), sort_y);

    // set iterators to the outermost visible stars (defined by screen bounds)
    // these are updated every time the screen is moved
    stars_x_.begin = std::lower_bound(stars_x_.stars.begin(), stars_x_.stars.end(), bounds_[0], sort_x);
    stars_x_.end = std::upper_bound(stars_x_.stars.begin(), stars_x_.stars.end(), bounds_[1], sort_x);
    stars_y_.begin = std::lower_bound(stars_y_.stars.begin(), stars_y_.stars.end(), bounds_[2], sort_y);
    stars_y_.end = std::upper_bound(stars_y_.stars.begin(), stars_y_.stars.end(), bounds_[3], sort_y);

    return;
}

Unfortunately, I cannot seem to either come up with an appropriate comparison function for std::set_intersection or a method through which I could manually compare coordinates using my iterators.

Could you guys point me in the right direction? Feedback on my methodology or implementation is very welcome.

Thanks for your time!

Answer 1

There are a variety of spatial acceleration data structures that help to answer questions of 'what points are in this region'. Quadtrees are a popular solution for 2D but may be overkill for your problem. Probably the simplest approach is to have a 2D grid with points (stars) bucketed by the grid square they fall into. You then check to see which grid squares your view window overlaps and only need to look at the stars in the buckets for those squares. If you make your grid squares a bit larger than your view window size you'll only ever have to check a maximum of four buckets.

If you can zoom in and out a more complicated structure like a Quadtree might be appropriate.

Answer 2

I use real star data for rendering (psychosomatic style) for years and have no speed problems without any visibility ordering/selecting under OpenGL (VBO)

1. I usually used BSC star catalog in the past

   • stars up to +6.5mag
   • 9110 stars

2. few years back I convert my engines to hipparcos catalog

   • 118322 stars
   • 3D coordinates

So unless you use too much stars it should be faster to just render them all
- How many stars are you rendering? - How are you stars rendered? (I use blended Quad per star)

What platform/setup ...
- this worked well even on my old setup GeForce 4000 Ti, 1.3GHz single core AMD - also in stereo 3D

what is your desired FPS ? ... I am fine with 30fps for my simulations

If you have similar values and low speed may be there is something wrong with your rendering code (not with the amount of data)...

PS.

if you have a big space to cover you can select bright stars to viewer only

• after each hyperspace jump or what ever
• based on relative magnitude and distance

also you use too much ifs for star selection

• they are sometimes slower then the rendering
• try just dot product of viewing direction and star direction vectors instead
• and test the sign only (do not see what is behind)
• of course if you use quads then CULL_FACE make it for you

Also i see you are calling draw for each star

• that is heap trashing
• try to avoid calling functions when you can
• it will boost the speed a lot !!!
• for example you can add a flag to each star if it should be rendered or not
• and then render them with single for and no sub-calls to render function

Answer 3

You can try spatial R-tree which is now part of Boost Geometry library.

The application could work as follows:

You add your star's coordinate to the tree in some "absolute" coordinate system. If your stars have different sizes you probably want to add not a point but a bounding box of each star.

#include <boost/geometry/index/rtree.hpp>
#include <boost/geometry/geometries/box.hpp>
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

typedef bg::model::point<float, 2, bg::cs::cartesian> point;
typedef bg::model::box<point> box;
typedef std::pair<box, Star*> value; //here "second" can optionally give the star index in star's storage 
bgi::rtree<value> rtree;

As you build your universe, you populate the rtree:

for (auto star: stars)
{
    box b(star->position(), star->position()));
    bg::expand(b, point(star->radius(), star->radius());
    // insert new value
    rtree.insert(std::make_pair(b, star));   
}

When you need to render them, you compute your screen window into "absolute" coord system and query the tree about stars which overlap your window:

box query_box(point(0, 0), point(5, 5));
std::vector<value> result_s;
rtree.query(bgi::intersects(query_box), std::back_inserter(result_s));

Here result_s will list the relevant stars and their bounding boxes.

Good luck!