5
\$\begingroup\$

I have a large list of points (millions) in 2d. Let's say it's a star map. Each star has a radius and position in space.

I want to render this map at different level of details. From a single star to entire star system, galaxy or even universe. I also want it to be fast.

So I started with a quad tree approach: loaded every point into the tree. At any moment of time I can query a tree with a simple question: Give me top N points in this region

But what is a top? I thought to myself that quads can be compared based on total radius of points that they host. So, this gives me sorting order to work with, and the algorithm boils down to a mix of quad tree and a priority queue:

priorityQueue.push(rootQuad)

while priorityQueue.size < N {
  let node = priorityQueue.pop() // take the largest node
  for each child of node {
    if child.intersects(region) {
       priorityQueue.push(child)
    }
  }
}

After this algorithm is done, I can render each point either at its location (if it's a leaf), or at the node's center of mass (if it's intermediate node). It works very fast, and gives decent results.

However there is a problem with this approach. Let's consider a simple grid of points:

grid of points

If I render each intermediate quad tree node at node's center of mass, then I get these artifacts, where two nodes are collapsed into one:

artifact example

It almost feels like I should start from leaves, combine individual points into single cluster, until I get N clusters, but this would kill performance.

What would you recommend to do to avoid such artifacts?

\$\endgroup\$
3
\$\begingroup\$

One obvious error in your current implementation is that you should combine nodes based on their total area, and not total radius. Otherwise you're overstating the visual effect by a squared factor - remember the area formula, pi*r^2. But you'll still run into other artifacts.

An obvious one is that when you are zooming or refining your detail, there will be popping artifacts as one level of detail is abruptly replaced with the next. Most LOD algorithms deal with this by fading between levels of detail - i.e. when you are at the threshold between levels, alpha blend between the two instead of having a hard threshold.

In my experience level of detail for point clouds where you replace small points with big points only works for continuous surfaces (and even then you get artifacts from the loss of surface texture, which is somewhat improved by texture mapping techniques like bump mapping). When you're dealing with discontinuous data, like your starfield, replacing multiple points with a single point is going to cause jarring effects like points shifting abruptly. You can also try one of two techniques:

  • Replace with a single quad that approximates the total luminance of the underlying stars. This is a much better approximation than a single large star.
  • Replace with a textured quad, where the texture is of a generic starfield. This is kind of related to the 3D impostors technique.

Experiment and see what works best. One thing you could try: the brightest stars are always visible; emulate that effect by having a priority queue of stars by brightness, always rendering the brightest N, and the rest in simplified form.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks, aggregating nodes by area was spot on. I also assigned center of each quad to the largest star it holds, and that gave smooth transition: i.imgur.com/azKQXbE.gif \$\endgroup\$ – Anvaka Jul 24 '16 at 0:48
  • \$\begingroup\$ Nice effect! You should edit it in your question to help future readers \$\endgroup\$ – congusbongus Jul 24 '16 at 1:48
0
\$\begingroup\$

Try rendering the stars at full resolution, and building a mipmap.

A mipmap is a "pyramid" of images, each at a different scale. At the "top" of the (upside down) pyramid is the original image. The next level is the same image at half-scale. And so on.

GPU can produce mipmaps (opengl, directx I'd imagine too), though such a map is prolly too large to do it in one shot on the GPU (too large for a texture), but if you are doing quadtrees you should be able to figure out how to break it down to feed it to the GPU piecemeal. The lowest level of a mipmap would look like that section from far away. Precompute the entire mipmap if you can.

It should look decent, but if it doesn't look good, you'll want to do the same thing yourself; use a vision library like opencv (prolly to precompute them) and basically you do {1. blur, 2. subsample at half resolution} over and over until you have a 1x1 mipmap level. And you have produced the mipmap yourself. The choice of "blur" and associated parameter choices for each blur will affect how it looks at the end. Some examples are "gaussian filter" or "bilateral filter". There are lots of others.

Another thing to try would be to use opencv (or another lib) to directly do the rescaling; see if you can produce a mipmap this way, it might produce good results.

Fade between the two levels of the mipmap that are at the scale you want to draw on the screen (this is called trilinear interpolation).

Just to note, if you don't want to do the entire thing precomputed, you can take a section that you want to draw and only do that section. Keep in mind you might need to add some border to this section to take into account things that would normally be blurred in.

\$\endgroup\$
  • \$\begingroup\$ While these are good suggestions, they might be a bit too costly for his soft-real-time requirements and may be taking a too complex approach rather than a good approximation that keeps simplicity as a priority. \$\endgroup\$ – user5665 Jul 22 '16 at 8:02
  • \$\begingroup\$ @MattJensJensen only one way to find out :) \$\endgroup\$ – Realz Slaw Jul 22 '16 at 8:10
  • \$\begingroup\$ Perhaps so, but I think from the perspective here in GameDev, it's more important for him to have a suitable solution that has minimal development time and considerable flexibility. Integrating OpenCV to manipulate computer generated graphics seems a fundamental misstep. OpenCV is intended to be used for converting images into a model a computer can work with and process, he is already starting with a model a computer can process to begin with, the introduction of OpenCV would unnecessarily complicate and slow down this process, even if it were done before run-time. \$\endgroup\$ – user5665 Jul 22 '16 at 8:14
  • \$\begingroup\$ @MattJensJensen are you suggesting that my answer is inappropriate for this stackexchange site? Should I remove it? \$\endgroup\$ – Realz Slaw Jul 22 '16 at 8:18
  • \$\begingroup\$ No, I'm not suggesting your answer is off-topic or invalid, I'm just suggesting that you keep in mind that this SE site is for game development and solutions that are perfectly valid academic answers may mislead or complicate the lives of people trying to implement real-time applications. \$\endgroup\$ – user5665 Jul 22 '16 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.