Sparse Attributes

[sibarrick]

Hi all,

When creating sparse attributes, ie attributes that have a different number of elements per point/prim, how do you make sure the allocated range is the correct size.

Is the only way to do it to pre calculate the maximum possible size of an array and then use that, or can you make the size the maximum potential dimension and then run some method to trim it back. Or thirdly start with it zero sized and then grow it as you go. I see methods to deal with capture attributes this way, but I'm guessing they won't work with arbitary attributes?

For example. I'm capturing points for a deformer. Potential every point in the surface could be captured by every point in a second surface. Can I start by making the attribute N dimensions big, where N is the number of points in the second input, then when I have finished resize it to fit with the maximum number of dimensions actually needed. Or do I need to determine all this before creating the attribute? Ideally I'd use the add dimensions as I go route, since creating an attribute N big could have large memory overheads.

[edward]

There is no such thing as sparse attributes which is why we have the index pair attribute hack.

In the capture sops, we our own sparse form of the data and then when done, create the minimum size necessary and copy all the weights into the attribute data. Because the attributes for each point are currently stored in different memory chunks, memory coherency is an issue. Keeping your data in a memory-coherent data structure until all done improves performance.

There are functions to grow and shrink attributes but they're very inefficient. For each point, they reallocate the memory chunk. I wouldn't recommend it.

[sibarrick]

Thanks edward. Yes sorry I am using attribute pairs, what I meant was when using them you don't know when you start how many pairs you will need - hence they are sparse. But I think you follow what I'm after, you answered my question the way I suspected you would anyway.

the best answer is to stuff all the pairs into an array of the maximum possible size - ie N points (of second input) * 2 then run through them to see how many real pairs are needed create the attribute pairs of that number and copy the array into them. Right.

[edward]

Hmm ... let me rethink that previous post. I was actually thinking more along the lines of never allocating the maximum amount of memory if you know a priori that the data is sparse. That will actually use more reallocations that your method of allocating the maximum size in the attributes and then resizing them only once when done. Er, so scratch the memory coherency comment.

If you keep a non-sparse form of the data with the N points of the second input, then you don't need to * 2. You can just create a 2D array of M rows by N columns where M is the number of points in the first input. After you're all done, you can just go through and count the maximum number of pairs needed for each point. The "index" will be just the column number.

I'm not sure what the best way is. It's sort of a memory vs. speed trade-off.

PS. For the mean value coordinates, Jeff Lait suggested that one could specify a tolerance threshold and then just drop off the capture primitives whose weight are lower than the threshold.

[sibarrick]

With regard to the mean value thing, I'm not sure that will work. I thought about it, but never tried it mind you.

The thing is that you can have a point slap bang in the mddle of your control mesh and it will be weighted by a very small amount from every point in the mesh. This point would then fail to be in the right place if you zapped weights under a threshold. I guess it could be an option if you were only using it like a skin wrap deformer where the control mesh and the input mesh were always very close together. I'll do some experiments to see if it is feasible.

I've tended to use it where the above isn't the case so I haven't worried about it. Worth a try though.

With regard to the sparse data, are you saying that when you store the sparse data first that you use a reallocation method to keep enlarging it as you go? Do you use UT_PtrArray for this?

<later>

Ok had a look at UT_PtrArray looks like it has all the functionality required so going to try down this route first. Good idea to save memory rather than cook time I think.

[sibarrick]

With regard to the mean value thing again.

Just tried this really quickly and there might be some mileage in it. It would sure help reduce the amount of data stored for big meshes. Once I figure out a way to deal with sparse data I'll try and get around to updating it to make that an option. It's a payoff between accuracy and storage but I think in a lot of cases a small loss in accuracy for a big paid off in speed and memory would be well worth it.

Cheers Jeff, (i think, giving me more work.....)

Hey how about Sesi taking over this sop and making it part of the package? then you guys could deal with optimising it!

[sibarrick]

I've properly added the threshold idea into my mean value stuff, and Jeff is right in some cases it works a treat, reduces the storage overhead by a factor of 3 or easily more. And hence increases the performance by the same factor. The down side is a small loss in accuracy but easily liveable with in lots of cases. I'll do some proper tests and post up the code and results.

<later>

actually it's a bit of a cheeky one, it works ok if the driver surface is quite close to the control mesh, but as I suspected it doesn't work too well as the distance between the two increases. Also even when they are close it tend to make the deformed mesh pull towards the control cage, which may or may not be acceptable. In other cases it just doesn't work at all. I'll leave it in but it's definately a use at your own risk feature.

Edited August 19, 2005 by sibarrick