 • entries
3
10
• views
2313

N-vector data structure to store and query for scatter points

Introduction

The impetus for this research topic is concerned with a data structure that efficiently stores and queries scatter point data. These points may originally be neatly arranged on a grid, or randomly scattered across the surface of a sphere (e.g. the earth), but it makes no assumption in that regard. The data structure could have member functions such as add(point) or add(points, amount). The points themselves contain three scalar values: the longitude, the latitude, and the data value itself. This data value could be geographical data such as land height or weather data such as air temperature, but again, the data structure is agnostic about the data itself other than as a scalar value.

Data Structure

The purpose of the data structure is ultimately to efficiently and accurately query for point(s) that is(are) nearby another point, the reason being to compute the average value at that point. Suppose a requirement is to create an image representing the air temperature (or rainfall, cloud cover, whatever the scalar value of each point represents) - this data structure could be queried for each point (i.e. pixel) in the image. Once nearby points are queried, the algorithm to average the scalar values of each point is outside the scope of this, but a good candidate is the inverse distance weighed algorithm.

Within the data structure, the data points will not be stored in spherical coordinates, but as n-vectors. The reason for this is that the sampling algorithm - finding N closest data points - is more efficient and accurate using vector algebra. While it is outside the scope of this, to summarize: it is easier to determine how close two points are on a sphere if these points are represented by unit vectors than by latitude and longitude. For example, two points sharing the same longitude are farther apart at the equator than above or below the equator. Even if we are just concerned with relative distances, and do not need to compute the square root of the distance formula, for this reason it is still not as accurate. Also the international date line, where longitude "resets", presents a problem that would have to be dealt with. Also either pole. But you get the idea - vectors are more stable, accurate, and efficient.

I've always been a fan of Binary Space Partitions - each branch node of a BSP has two areas, one below and one above (or one left and one right, or one in and one out, however you like to think of it). To go along with storing points as vectors, branch nodes within the structure partitions their space also using a vector, which in this case forms the normal of a plane that bisects the unit sphere. All data points in a node (or children of the node) will either be above or below this plane (points that are on the plane can be allocated to either side as is appropriate). Points that are below the plane are placed in the first child of the node, and points that are above placed in the second child. We call this plane normal the split axis of the node.

Querying the structure for the closest N points then becomes trivial. For any branch node, compute the dot product of the point in question and the split axis of the node. If it is negative (the point is below the split plane), recursively query with the first child node, and if positive (the point is above the split plane), with the second child node. For a leaf node, compute the dot product of the point in question with each data point contained in the node, keeping a sorted list of the closest N points. The one caveat is that in branch nodes, after recursing into one child node, it may be necessary to recurse into the other child if the farthest point found so far is farther than the other child node, since there may be closer points in the other child node. But this is trivial as we are comparing dot products. No expensive computations are necessary to compute the N closest points - just a bunch of dot products. As dot products of unit vectors range from -1 to 1 (-1 being farthest apart and 1 being equal), two points are closer if their dot product is higher.

Once complete, and the list of N points found, the actual distances can be calculated if necessary, which in this case is done by calculating the angles using the already-calculated dot products. This angle can then be multiplied by the radius of the earth to get an exact distance, again only if necessary. But for averaging, these extra calculations are not necessary.

As a final note, the data structure lends itself well to graphics hardware. In my particular case, rendering an image using such a data structure on the CPU may take several minutes, but on the GPU takes a fraction of a second.

Problem

The problem - common to any space partitioning tree - is how to initially create the data structure. Again, the points are not assumed to be arranged in any specific way, and as far as we are concerned, are a "point soup". They can be specified one at a time - addPoint(point) - or all at once - addPoints(points) - or both. Specifically, how can the determination of the split axis of any branch be efficient and provide an even split (the same or similar number of points on either side). The problem is unique here because the points are not arranged on a two-dimensional surface or in three-dimensional space, but lie on a unit sphere.

My current solution to the problem is not terribly elegant. For each two data points, compute the axis that splits them evenly. This is done by computing the point between the two (subtract one from the other) and normalizing it, then crossing this with the cross product of the two points. This cross product comprises the normal of the plane that evenly splits the two points. This normal is then tested against each other point in the node to get 1) the number of points on either side of the plane and 2) the distances of the points to the plane. A good split plane is one that 1) splits points evenly, 2) has the same/similar distances on other side, and 3) has large distances on other side. As this test is performed for each two data points, some big-O notation shows that determination of the split plane for nodes containing a large number of points will become prohibitive.  However, I have not been able to determine a better solution.

But the advantages of such a data structure still outweigh this expense. In my particular case, the time spent initially creating the tree is worth the time saved during queries. I should mention that if the data points are known ahead of time, it is faster to specify them all at once, so the tree can re-build itself once, rather than one at a time which may cause the tree to re-build itself multiple times.

I'm guessing this is just for a general scheme for nearest neighbour search on a sphere, but the kind of questions I would be asking are:

• how many points are we talking about
• what is the distance (relative to the sphere) over which to make a query for nearest neighbours
• what are the access patterns (are the queries random, or are you, for instance looking for the closest points to a moving object, where you can reuse the results of a previous search)?
• The best scheme may depend on how fast adding a point to the data structure needs to be, versus the speed of the queries.

As well as spatial partitioning schemes, you may also be able to simply store a list of nearest neighbours on each point (you could prestore the angular 'distance' too). Then you search becomes a case of find the nearest point, and recurse outward (with a bitmask for points already visited) until you have found all the nearest points of interest.

Another data structure which might be useful is a 2d grid of all the point combinations, with the angular distance between each point pre-calculated. Also consider that knowing the exact distance to neighbours may not be as important as finding the 'rough' neighbourhood, depending on the application, so you may be able to avoid most of those calculations.

Thanks for your comment!

The actual use case is a bit more involved than I describe, but not much different than what I use as examples; it will be for rasterizing averaged values of weather data over a geographic area. The weather data comes in pre-defined grids, where each point of the grid is defined by latitude/longitude and a data value, and the grid may or may not be the same format as what is rendered (i.e. the weather data grid may be Polar Stereographic, while the rendered grid may be Lambert Conformal). As such, the internal structure should be agnostic.

Another layer of complication is that the weather data also comes in one or more forecasts, where there is a grid for each forecasted unit of time X number of times. For example, 72 grids spaced out an hour apart from each other, containing wave height data for the Caribbean Sea.

To keep the implementation simplified, each BSP only contains one type of weather data, at one point in time. Since the time is the same for all points in a BSP, it is not stored for every point, but once for the whole BSP. I mention it because even though it is not stored with each point, it is taken into consideration as another "dimension" when finding nearby points. The end result looks something like this:

float target_time = ...; // render time
float max_distance = ...; // points outside this distance are not considered
int N = ...; // number of nearby points to consider

foreach (pixel) {
float target_geo = ...; // unit vector (nvector) of pixel

//  = distance,  = value
float distance_and_value[N] = ...; // initialize to max_distance

// check BSPs
foreach (BSP close enough to target_time) {
// modifies distance_and_value parameter as smaller distances are found; keeps the array sorted based on distance
BSP.findClosest(target_geo, target_time, &distance_and_value);
}

float average = ...; // calculate using distance_and_value, stopping when >= max_distance
pixel = ...; // calculate using average
}

But I didn't mention all of this because it is tangential to the problem of selecting a partition for each BSP tree branch.

• how many points are we talking about - it varies from grid to grid. Some are as small as 350x150, and others as large as 4400x2200. It could be larger as more meteorological data is added. For now I'm only using freely available data from NOAA, but could eventually use proprietary data from other sources.
• what is the distance (relative to the sphere) over which to make a query for nearest neighbours - this is a parameter passed to the query function, and may differ based on application. For most cases, the end result should look "pretty" and show smooth gradients, whereas accuracy is preferred for "serious" uses such as maritime navigation.

• what are the access patterns (are the queries random, or are you, for instance looking for the closest points to a moving object, where you can reuse the results of a previous search)? - (see above code snippet)
• The best scheme may depend on how fast adding a point to the data structure needs to be, versus the speed of the queries. - you are right, it may be, although not for my current use case. Regardless of which is best, I would certainly implement faster BSP insertion if I knew how.
2 hours ago, lawnjelly said:

As well as spatial partitioning schemes, you may also be able to simply store a list of nearest neighbours on each point (you could prestore the angular 'distance' too). Then you search becomes a case of find the nearest point, and recurse outward (with a bitmask for points already visited) until you have found all the nearest points of interest.

That makes sense for rendering multiple images of the same geographic area, but not for the case where the area may be panned or zoomed, as the list would have to be re-built. Also how would the list of nearby neighbors be efficiently built without some partitioning scheme to begin with?

2 hours ago, lawnjelly said:

Another data structure which might be useful is a 2d grid of all the point combinations, with the angular distance between each point pre-calculated. Also consider that knowing the exact distance to neighbours may not be as important as finding the 'rough' neighbourhood, depending on the application, so you may be able to avoid most of those calculations.

I think this is also not effective for the same reasons. Pre-calculating the angular distance between data points is not necessary, as that is never needed (only need to determine distance between data points and another arbitrary point), and as in the previous paragraph, pre-calculating angular distance between data points and another point is only used once.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

• Similar Content

• Hey there,
I recently came across this: https://github.com/ssloy/tinyraytracer
It's a raytracer implemented in a very minimal way.
This person uses a method to find intersections between a ray and a sphere that I can't understand. His implementation is as follows:
bool ray_intersect(const Vec3f &orig, const Vec3f &dir, float &t0) const { Vec3f L = center - orig; float tca = L*dir; float d2 = L*L - tca*tca; if (d2 > radius*radius) return false; float thc = sqrtf(radius*radius - d2); t0 = tca - thc; float t1 = tca + thc; if (t0 < 0) t0 = t1; if (t0 < 0) return false; return true; } This code confuses me, because I've always used the quadratic formula to get the discriminant of the ray-sphere function. It looks like he is doing the same thing, but perhaps using a different formula to begin with?
If someone has the time I'd appreciate an explanation or a breakdown of this method.

• I am a beginner in computer graphics but i have solid understanding of linear algebra. I am trying to implement my own forward kinematics for a skeleton. I defined global and local translation vector in child-parent relationships but i am struggling with propagation of rotations from the node n to n+1, n+2 ...
I figured that motion builder uses XYZ rotation order. I created a matrix to transform child vector and "rotate it".
But if i have 3 joints where 1st is parent to 2nd and 2nd is parent to 3rd, if i rotate 1st joint say (10,20,0) locally, i get accurate global position for 2nd and 3rd joint but if i have a local rotation of 2nd joint say (20,0, 0) on top of (10, 20, 0) for the 1st, my 3rd joint's position is wrong. I notice there should be some stacking so that i should probably do (10+20, 20+0, 0+0) for the second rotation but i am not sure why is that the case.
If i could get some links or a book that will address this topic, i would appreciate it. Thanks!
• By M-Ody
My question is pretty straight to the point. I'm reading Real-Time Rendering right now, and while at the start I've done great understanding all the topics, I'm having a hard time once I entered rotations and stuff. I.e. the 4.2.2 chapter, where the function to extract parameters from an Euler Transform is presented, I've felt like the author just pulled a rabbit from a hat.
I know that most mathematicians could just derive those equations by themselves, but I absolutely can't do it right now.

So the question is: should I keep reading and I will eventually understand those things or should I stop and "start easier"?
I'm a little bit worried that I would not be able to follow along and waste my time, but then this could be only because I hate to not grasp the full concept right away and have a 'semi-knowledge' on something. Maybe I don't need to understand everything the first time?

I should mention that I'm a programmer and I know some decent linear algebra. I'm also planning to go hard on math on the next semesters.
• By Yann_A
Hi,
Say I have a square with the following vertices in world position.
topleft=100,100
bottomRight= 200,200
So the center is at 150,150
So my local to world matrix should be a translation T to 150,150 (if my for vertices where offset around the origin by 50 in local space)
Now, this is what I tried to build my rotation matrix.
Compute Tinv as the inverse of T to come back to local space. Compute R as the rotation matrix around 0,0,1 axis with pi/2 as the angle. So my plan to builld this matrix was to first come back to local space, then rotate, then go back to world space.
F = Tinv * R * T
And that doesn't work.
It does work when I apply those matrices independently though, so like:
rotatedTopLeft = topLeft * TInv
rotatedTopLeft = rotatedTopLeft * R
rotatedTopLeft = rotatedTopLeft * T
But what I want is combine TInv, R and T into a single matrix so I can just do
rotatedTopLeft = topLeft * F
So how exactly do I compute F?
Thanks 🙂

• hi, i´ve tried for a long time to get a skinning example code to work, without much success. does anyone know a website/tutorial where it is described step-by-step what happens to the vertices during key-frame animations? i want to point put that there isnt a more confusing way than wrapping essential pieces of code into class methods, as it is done here:
http://ogldev.atspace.co.uk/www/tutorial38/tutorial38.html
so this one is just not comprehendable, at least not to me ...
i´d like to reiterate what i already know: vertices are defined in "mesh space". to transform that mesh to its proper position in the world, several chained transformations have to be applied to those vertices ("world space"). first, a model is (or can be) a hierarchical organized scene, for example, to put the hand of a human to its correct place, the ellbow-transform and shoulder-transform have to be applied after the models transform itself (that is, where the model in the world is located).
absolute_hand_transform = model_transform x shoulder x ellbow x hand
... each defined relative to its parent, of course. this is all static, no skinning there ... thats what i´ve already implemented.
if you load a model using ASSIMP (for example), bones contain a "offset matrix", that transform the vertices of a mesh to "local space of the bone":
... then, an animation produces for each bone a relative transformation (relative to its parent, i guess) that i can use (draw) after all the previous or "parent" transforms are applied.
IS IT THEN CORRECT (?) that to draw a skinned mesh, the transformations i have to calculate and send to the vertexshader are calculated as following:
MeshSpace-To-WorldSpace = ModelToWorld-Transform x MeshSpace-To-BoneSpace_0 x AnimatedBone_0 x MeshSpace-To-BoneSpace_1 x AnimatedBone_1 x MeshSpace-To-BoneSpace_2 x AnimatedBone_2 x MeshSpace-To-BoneSpace_3 x AnimatedBone_3 where all those "MeshSpace-To-BoneSpace" transforms are these "bone offset matrices" AND each of those "AnimatedBone" are directly computed by interpolating the animation keys ... correct ???
(i assume its not because often i read about having to use some "inverse bone offset transform" in some way i dont get ... 😐)

thanks in advance for any answers/suggestions/clarifications !!