Least expensive way to check each element of an struct array in tick?

Development Programming & Scripting C++
1

I’m working on a VR Gesture system. Ideally, this system regularly updates (probably won’t be in event tick, but rather fixed tick rate), and decides which struct out of an array of structs is the best choice.

I can’t imagine this not requiring a for loop, and I know in a majority of cases that using for loops in updates from blueprints is generally a bad idea. So I’m also wondering if doing it via a c++ function is viable with the amount of data being accessed.

Each struct roughly contains 4-6 3D vectors, floats, and booleans.

There may be anywhere from 5 to 70 of these structs to access at once for all I know. It’s intended to be usable in a multitude of projects.

Any thoughts, or even alternative solutions, would be greatly appreciated.

2

The words least-expensive, array and tick don’t go together :slight_smile:

How do you know which is the best?

3

I was thinking something simple like a tolerance value to compare. At least for most of the 3d vector values, since the two main values will simply be location and rotation (although now that I think about it, rotation will likely be rotator. Used to them being vector3’s from unity)

Then beyond that, just the closest value to the one changing in runtime

But I may yet include both velocity and angular velocity, which may change how I’ll want it to decide

1 Like
4

I’m thinking of something like the ‘hash’ that dictionary ( map ) data types use.

If you could implement something like that ( probably in CPP ), then you could do it every tick, because you would be able to jump straight to the relevant entry… :slight_smile:

1 Like
5

I was hoping there was something like that, but wasn’t sure what it would be called.

I’ll definitely be looking into it, thanks a ton for the help

1 Like
6

If you’re looking up exact values, then you could do it in BP. But if you want to be approximate, the CPP would be better. You could write your own hash :slight_smile:

7

Apologies for the long and wordy post, but I did a bit of reading on hashes and maps and was wondering if I could get a second opinion on a choosing which routes to explore
I’ve found a few options that may do what I want, but I’m definitely open to alternatives as well.

From what I’ve read, the main methods that I would think are my best options are:

Spatial hashing, which from my understanding, is a fixed grid in 3d space that is indexed, then each position within that grid space is stored in the array at said index

quadtrees (or octrees in 3d space?), which from what I’ve read are significantly more complicated to work with and possibly less performant (that part wasn’t entirely clear, but I’m gonna lean towards it being true, because my implementation probably will be).
It kind of sounds like spatial hash maps being nested inside of each other, but I didn’t read that far into it so I’m not exactly sure.

I also thought of a hash map that maps each base 10 digit onto its own array (probably from like 0.01m to 10m, since that’s likely all that’s needed) and mapping each 0-9 value to its own index position. Only thing is I’d have to do this for each axis in a vector, then for multiple vectors (although probably only 4-6 of them. But that of course means 12-18 iterations). But then I’d also need to retrieve base 10 digit values for at least 2 of these vectors consistently during runtime
Although now that i think about it, this kind of just sounds like quadtreeing, but each grid has 10x10x10 within it, and I’m just checking each axis individually

I’m not sure if any of these are what you had in mind, so if you had a better idea I’d love to hear it.
I figure if it comes to it, I’ll just make functions for all of these and test their performance impact

1 Like
8

It sounds like you’re on top of the research.

You could do it in stages.

If you do a very efficient short circuit algorithm in blueprint, that might actually work. You can’t leave anything to chance, just explicitly take the quickest route through the calculations, and see where there that gets you.

If the number of operations ( for any of these methods ) is of the order < 100 ( plucked from the air ), you’ll probably be ok. Give it a go.

If it’s too slow, the either change approach, or move to C++.

Does that makes sense?

9

I’ve decided to go the spatial hashing route, but there’s some things I wanted to know if you had an opinion on.

tldr: Filtering positions with spatial hashing works great! What about rotation and velocity?

My Current Solution

The main method I’ve explored is fast. I use spatial hashing to create a grid space around the player and find which grid cell the object, or hands in this case, are in.

Users can record these gestures in the editor. Then when loading the game, these recorded gestures can be scaled according to player sizes and other specifications, then stored in a hash table.

While I haven’t implemented it yet, I plan to be able to allow storage of a gesture in a neighboring cell if it’s within a radius tolerance of the recorded position.

This works quite fast. Even with a quickly thrown together Blueprint implementation, ticking on every frame, I didn’t notice more than an average of 5 fps drop (at around 140 fps). Keep in mind this was also drawing debug squares for the cell each hand is reading from. The grid size was 40 * 40 * 40 for a total of 64,000 grid squares.

Of course I am aware that this type of thing should be done on a timer rather than in a frame tick, but I want it to be a plausible option.

The Problem

The current solution works great for positions, but I’m uncertain as to how well it will work on rotation and velocity. At first I thought I would just make position a requirement, then once the best gesture has been decided, see if the other values work well enough.

But what if a user wants to capture purely a flicking motion in any arbitrary direction? Or a rotation and angular velocity at any arbitrary location?

I thought then, that velocity and rotation and everything are all just 3d vectors, so maybe they could be hashed the same way. The rotation may not be so troublesome. I just have to convert any rotations axis to be from 0 - 360 degrees. But velocity may be a little more troublesome if the player is capable of producing extreme values that are out of the range of the grid, since the grid is a fixed size.

Plus, the performance impact may actually start to be a problem if I’m calculating 3 or 4 different keys every frame. And of course I’d have to triple or quadruple the amount of for loops that check between each gesture stored in these cells.

Wrap up and big questions

Is there a better way of filtering these other values? Or a better way to compare all values including position quickly and efficiently every frame? Or is such a thing completely out of my scope?

Thank you for reading this far into the post, and any help or insight on the matter would be greatly appreciated

1 Like
10

I’m in uncharted territory here…

I’m thinking that some way of hashing everything all at once would be best, if possible. I don’t even know if that makes sense.

I think you’ll find that rotations are a pig, because it’s not just 0-360, something called gimble lock, will mean you’ll probably need to use quaternions.

Sounds like it’s going very well so far, but I don’t think I can be much help :thinking:

11

That almost makes sense. I figure you mean a hash table that maps all 4 values, and a key that takes the input of all 4 values. But I’m pretty sure this would end up being the same thing, as I would be having to do the same calculations, just with less modularity.

You know, I’m really glad you mentioned Gimbal Locking. I honestly didn’t even know it was a thing, and it now makes as to the limitations of Euler rotations. I guess for that one I’ll have to do more reading on quaternion rotations, which I’ve honestly been putting off for a long time.

So I suppose you did provide some help in the end. Thanks a ton

1 Like