SparseGrid

craouettecraouette Posts: 113

Hi,

I want to store the classify Points inside a grid with a defined cell size.
There is already SparseGrid.
I can use setExplicitCellSize to set the cell size.
Can it be used on Points?
How can I restrict the Points to be classified (with and index array)?
do I need to call updatePointObject with every active points? can it be done with PEX?
Can I use bSphereQuery to get all the points around a given position?

thanks,

pierre

Comments

  • jcgagnonjcgagnon Fabric Employee Posts: 122 Fabric Employee

    Hi Pierre,

    Yes, the bSphereQuery's goal is to get points around a given position & radius.

    The SparseGrid object is generic and you can add what you want in it, including points or subset of points; you decide what indices are mapped to. "updatePointObject" (or "updateBBoxObject" if your points have a size) needs to be called for every point that change, and it cannot be done with PEX, however it is already very optimized (less work if point doesn't change much). Once all points are updated, SparseGrid.updateGrid() must be called.

    The Points already provide a built-in method that allows to use a SparseGrid, but at that level there is no way to restrict the SparseGrid to a specific subset; to do that you would need to setup the SparseGrid yourself, but it is not very complex. To use it for a Points object, use the setup options similarly to the example in http://docs.fabric-engine.com/FabricEngine/2.0.1/HTML/KLExtensionsGuide/Geometry/spatialqueriesusage.html#spatialqueriesusage but with a Points object. And, you can see here how to use a bsphere query at the level of the Geometry services: http://docs.fabric-engine.com/FabricEngine/2.0.1/HTML/KLExtensionsGuide/Geometry/spatialqueriesusage.html#using-the-spatialquery-object

    For the Points, the Points.prepareForSpatialQueries implementation updates the spatial query structure (octree of sparse grid, using something that abstracts both) using a default point size or a size attribute. It looks complex but most of it is optimizations to avoid updating when not required.

    Jerome

  • craouettecraouette Posts: 113

    thanks @jcgagnon

    I had figured most of it.
    here is my code:

     this.sparseGrid = SparseGrid();
      this.sparseGrid.setExplicitCellSize(this.h);
    
      Vec3Attribute positionAttribute = particles.getOrCreateVec3Attribute("positions", false);
      Vec3 positions[] = positionAttribute.values;
      for(UInt32 i=0; i<particles.numActives; i++) {
        UInt32 index = particles.activeIndices[i];
        this.sparseGrid.updatePointObject(i, positions[index]);
      }
      this.sparseGrid.updateGrid();
    

    the only point I was not able to handle, is to update the grid... I just create an empty one on every simulation step.

  • jcgagnonjcgagnon Fabric Employee Posts: 122 Fabric Employee

    Yes, that looks good! As you probably know, the cell size can have a huge impact on performance, so choosing the right one is key. In some cases, if the density varies a lot, the Octree could be better, otherwise the SparseGrid has a lower overhead, particularly if you search radius is similar to your cell size.

    Jerome

  • jcgagnonjcgagnon Fabric Employee Posts: 122 Fabric Employee

    Sorry I missed your question about updating the grid. Reusing the grid by incrementally updating it can give major performance gains, and the support for incremental updates is at the center of the design of the SparseGrid (and Octree too). Normally, the loop above should work fine with an existing grid. However if some points are no longer part of the active indices, you will need to remove these from the grid by calling SparseGrid.removeObject(). What issues did you have?

  • craouettecraouette Posts: 113

    It is for SPH, so the search radius is always the same:

    this.h

    As it is particles, the number changes, but all particles are moving (and it is very difficult to track the ones not moving). so, I am not sure there is a lot to gain by not starting fresh on every simulation step.
    If I remove from the previous code

    this.sparseGrid = SparseGrid();
    this.sparseGrid.setExplicitCellSize(this.h);
    

    then , I got a lot of (even if no particles are deleted, only new one added):

    [FABRIC:MT] Error: SpatialQuery/SparseGrid/SparseGridInternal.kl:401:11: index (4294967292) out of range (2145)
    

    but the rest of the code is the same and working when starting fresh... so, there is no way this crazy index is used!

  • jcgagnonjcgagnon Fabric Employee Posts: 122 Fabric Employee

    There would certainly be gains; the SparseGrid knows the "previous" position and update is very fast if the particle is in the same cell, and it avoid a lot of memory allocation and structure initializations.

    As for the error you are getting, not sure what's happening, possibly a bug; could you dump the full stack trace if you have it?

  • craouettecraouette Posts: 113

    could you dump the full stack trace if you have it?

    I can do better... here is the full source code.
    Add the unzipped folder to the Ext path. open in canvas the file: Particles/tests/verlet_simulation-sph.canvas
    and press play.
    to do this with starting clean at each simulation step, uncomment lines 59 and 60 of the file SPH.kl and reload extension of one of the Particles nodes.

    hope this help!

  • craouettecraouette Posts: 113

    I forgot, you probably will have to update the path in the loadObj node!!!

  • jcgagnonjcgagnon Fabric Employee Posts: 122 Fabric Employee

    Great, I've logged an issue tp track this with your repro files. These issues can be hard to track down so I can't say right now when I'll have a closer look however. Thanks!

  • craouettecraouette Posts: 113
    edited March 2016

    It is not necessary to continue my developments... as the start fresh is working well. Nevertheless, a little speed increase is always welcome... ;)

  • jcgagnonjcgagnon Fabric Employee Posts: 122 Fabric Employee

    Fine, thanks. I confirm it reproes here when following your steps. If I disable mutltithreading to make it easier to reproduce, it freezes without a stack trace, which is either another bug or the consequence of that same bug. Anyway, thank you for taking the time to send these reproes, otherwise it would be very hard to investigate!

    Jerome

  • jcgagnonjcgagnon Fabric Employee Posts: 122 Fabric Employee

    FYI, I just fixed the issue, the fix should be available in the next daily builds. If you're interested in trying it yourself:

    In SparseGridInternal.kl, replace:
    UInt32 cellSubIndex = hashCellDataOffset / SparseGridCellDataOffset_NbFields;
    with
    UInt32 cellSubIndex = (hashCellDataOffset - hashDataOffset) / SparseGridCellDataOffset_NbFields;

  • borjaborja Administrator, Fabric Employee Posts: 480 admin

    @craouette note that we just merged in the change, so it will take until the next arbus daily for the fix to appear!

    Borja Morales
    Technical Product Manager
    Fabric Software Inc.

Sign In or Register to comment.