Jump to content
  • Advertisement
Sign in to follow this  
  • entries
    2
  • comments
    4
  • views
    1599

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

Sign in to follow this  
jorgander

632 views

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.

Sign in to follow this  


2 Comments


Recommended Comments

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.

Share this comment


Link to comment

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[3] = ...; // unit vector (nvector) of pixel

	// [0] = distance, [1] = value
	float distance_and_value[N][2] = ...; // 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.

Share this comment


Link to comment

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

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
  • Advertisement
  • Blog Entries

  • Similar Content

    • By Scouting Ninja
      So I have hundreds of moving objects that need to check there speed. One of the reasons they need to check there speed is so they don't accelerate into oblivion, as more and more force is added to each object.
      At first I was just using the Unity vector3.magnitude. However this is actually very slow; when used hundreds of times.
      Next I tried the dot-product check:  vector3.dot(this.transform.foward, ShipBody.velocity) The performance boost was fantastic. However this only measures speed in the forward direction. Resulting in bouncing objects accelerating way past the allowed limit.
       
      I am hoping someone else knows a good way for me to check the speed with accuracy, that is fast on the CPU. Or just any magnitude calculations that I can test when I get home later.
       
      What if I used  vector3.dot(ShipBody.velocity.normalized, ShipBody.velocity)?
      How slow is it to normalize a vector, compared to asking it's magnitude?
    • By Prometheus73
      I control the camera in my program by changing the transformation matrix (which alters the other underlying matrices). Not this is all in 2D.
      The transformation matrix is pretty standard. It is a 4x4 matrix with the diagonal acting as the scale factor (x, y, z) and the right side acting as the offset coordinates (this is ignoring shear and rotation which aren't that important to me though I would like the method to still work with rotation).
      So essentially I am currently zooming by altering the x and y scale in the transformation matrix. This seems to act from the top left corner (which is the origin in my coordinate space). I would like the zoom to act towards the mouse. So knowing the x and y position of the mouse when I apply my transformation (every frame)  how should I alter the zoom so that it zooms towards whatever the mouse position was?
      I can share code if you would like but I am writing this in Rust. Also let me know if you need more information I am happy to provide I just didn't want to over share.
    • By Hampus Siversson
      Hello,
      I am trying to recreate a feature that exists in Unity which is called Stretched Billboarding. However I am having a hard time figuring out how to use a particle velocity to rotate and stretch the particle-quad accordingly.
      Here's a screenie of unity's example:

       
      Depending on the velocity of the particle, the quad rotates and stretches, but it is still always facing the camera.
      In my current solution I have normal billboarding and velocities and particle-local rotations are working fine.
      I generate my quads in a geometry-shader, if that makes any difference.
      So does anyone have any thoughts of how to achieve this?
      Best regards
      Hampus
    • By 51mon
      Hey
      I'm dealing with ribbons following the shape of multiple spline segments. It's straightforward to compute the direction at any point along the spline. However the ribbon also got a flat shape and I'm struggling with finding a way to compute the angle of the ribbon in the plane perpendicular to the direction.
      To illustrate what I mean here's a piece of code that almost worked:
      float3x3 rotMtxFromSpline; rotMtxFromSpline[1] = normalize(splineDir); rotMtxFromSpline[0] = normalize(cross(float3(1, 0, 0), rotMtxFromSpline[1])); rotMtxFromSpline[2] = cross(rotMtxFromSpline[0], rotMtxFromSpline[1]); // Rotate rotMtxFromSpline[0] in the rotMtxFromSpline[0]-rotMtxFromSpline[2]-plane to align with float3(0, 0, 1) dir rotMtxFromSpline[0] = normalize(dot(rotMtxFromSpline[0], float3(0, 0, 1)) * rotMtxFromSpline[0] + dot(rotMtxFromSpline[2], float3(0, 0, 1)) * rotMtxFromSpline[2]); rotMtxFromSpline[2] = cross(rotMtxFromSpline[0], rotMtxFromSpline[1]); The problem with this code is when the spline segment becomes perpendicular to (0,0,1)-dir as the orientation switch from one side to the other very easily.
      The approach above is kind of a global approach and I'm thinking if there's a way to append some info to each spline segment to remedy the issue.
      Anyhow I wanted to post this question in case anyone had a similar problem that they solved or maybe anyone know some web resource dealing with this issue?
       
      Thanks!
    • By Agustin Andreucci
      Hi everyone,

      I got stuck with my approach to aiming down sights. I've set up my first person arms mesh to be a child of the camera. Added a socket on the right hand of the skeleton to which I attach my weapon and there is a socket in the weapon used to signal the point at which the camera should sit during aiming down sight. When the players aims holding left click what I'm trying to do is to calculate the offset of the sight socket to the root of the FPP Mesh while on the aiming down sights pose and move the camera based on that.

      I'm using the code attached below.
      It's Unreal Engine but the problem seemed generic enough to qualify as an algebra one. What I'm doing is obtaining the transformations from the camera to the sight bone. That gives me the sight transform relative to the camera. After that I just negate the translation vector and add it to the first child of the camera. I was expecting to have the sight bone sit at the exact same point as the camera.
      What happens is that it is almost there but it's not correctly aligned. I believe my math and the general idea is right.
      Any ideas why this could be failing?
      Here is how I apply the resulting transform and below how I obtain it.
      Thank you very much for reading.
      FVector Translation = DeltaTransform.GetTranslation(); Translation.Z = 165.0f; /*Translation.X += Translation.Y; Translation.Y = Translation.X - Translation.Y; Translation.X = Translation.X - Translation.Y;*/ DeltaTransform *= DefaultMesh1PTransform; DeltaTransform.SetTranslation(Translation); Mesh1PCamOffsetLocationDelta = DeltaTransform.GetTranslation(); Mesh1PCamOffsetRotationDelta = DeltaTransform.GetRotation(); bInterpMesh1PCamOffset = bInterp; UE_LOG(LogTemp, Warning, TEXT("DeltaInverse Location x: %f, y: %f, z: %f"), (DeltaTransform).GetLocation().X, (DeltaTransform).GetLocation().Y, (DeltaTransform).GetLocation().Z); Mesh1P->SetRelativeLocation(DeltaTransform.GetLocation() * -1); UE_LOG(LogTemp, Warning, TEXT("Rotation yaw: %f, pitch: %f, roll: %f"), DeltaTransform.GetRotation().Rotator().Yaw, DeltaTransform.GetRotation().Rotator().Pitch, DeltaTransform.GetRotation().Rotator().Roll); FTransform HandToComponent; HandToComponent.SetIdentity(); FTransform BoneTransform; USkeletalMeshComponent* Mesh1P = CarryingPlayer->Mesh1P; // Get transform to weapon attach socket space HandToComponent *= FirearmMesh->GetSocketTransform(FName("sight_point_socket"), RTS_ParentBoneSpace); HandToComponent *= Mesh1P->GetSocketTransform(Firearm->GetCarrySocket(), RTS_ParentBoneSpace); // Get transform from the right hand bone relative to component (root bone) FName CurrentBoneName = FName("hand_r"); while (CurrentBoneName != NAME_None) { ArmsADSIdleAnimSequence->GetBoneTransform(BoneTransform, Mesh1P->GetBoneIndex(CurrentBoneName), 0.0f, true); HandToComponent *= BoneTransform; CurrentBoneName = Mesh1P->GetParentBone(CurrentBoneName); } return HandToComponent;
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!