getClosestFacetAtCoordinates returning null most of the time

All,

getClosestFacetAtCoordinates returns null most of the time, even though the points are relatively close:

closestFacetTo(point) {
    var index = this._partMesh.getClosestFacetAtCoordinates(point.x, point.y, point.z); // returns the index of the closest facet to (x, y, z)
    let pos = this._anchor.getAbsolutePosition();
    if (index != null) {
        pos = this._partMesh.getFacetPosition(index);   // the world position of this facet
        console.log("pos", pos)
    } else {
        console.log("returning old");
    }
    return pos;
}

I tried updating the partitioning bbox ration to 1.8:

mesh.partitioningBBoxRatio = 1.8;
mesh.updateFacetData();

Regarding a playground, I am providing a playground that somebody else created (and had the same issue), which they seemed to resolve, but they don’t specify how:

https://www.babylonjs-playground.com/#UZGNA#13

Their original post: Facet Index = null when using getClosestFacetAtCoordinates - Questions & Answers - HTML5 Game Devs Forum

The world matrix of the mesh must be recomputed as the position property is changed:

https://www.babylonjs-playground.com/#UZGNA#14

While that seems to solve the issue with the playground in question - it does not solve it in my local example - the mesh position is not being changed, and as you can see from the image below, the closest point that is being returned is far from the truly closest point. I will work on preparing a playground to illustrate this - in the meantime, if you have other suggestions, please let me know.

Thank you for your help

image

@Evgeni_Popov Here is a playground: https://playground.babylonjs.com/#TL1IIB#50

Drag plane with text “hose-5” - you will notice that most of the time it gives null - in which case I have the function closestFacetTo return new BABYLON.Vector3(0, 0, 0)

I think it is working as expected (albeit not how you would like it to work):

When using facets, the mesh bounding volume is subdivided into tiny cubes, depending on a number of parameters (partitioningBBoxRatio, partitioningSubdivisions, …).

When checking a point P for a closest facet, the function looks for the cube containing P and compute the distances between P and each facet of this cube and returns back the facet with the minimum distance to P.

So, there are two important things to note:

  1. P must be inside the bounding volume of the mesh (taking partitioningBBoxRatio into account - so you can inflate a bit the bounding volume used by the function by setting partitioningBBoxRatio greater than 1) for the function to (potentially) returns something other than null (see 2.)
  2. if the cube that holds P does not contain any facts, the function returns null

So, given that the center of the label plane you move stays inside the bounding volume, it’s 2. that explains that most of the time no facet is found.

You can circumvent 2. by lowering partitioningSubdivisions (even setting it to 1), but that defeats the purpose of the subdivision process, which is to quickly find a match by checking only a subset of the facets…

2 Likes

Thank you for the thorough explanation - finding the closest facet on a mesh is a critical function for what I am doing. I am trying to think of ways to make this more accurate (projecting to a plane within the bounding box etc.). If you know about something I can do, let me know.

It is currently replacing the following function, which as you may imagine is very slow:

/**
 * Finds the point that is closest to the part's mesh. 
 * @param {Vector3} point
 * @return {Vector3} Closest point on the Part Mesh
 */
closestPointOnPartMeshTo(point) {
    var positions = this._partMesh.getVerticesData(BABYLON.VertexBuffer.PositionKind);
    var minSquaredDistance = Math.pow(10, 9);
    var closestVertex = BABYLON.Vector3.Zero;
    var numberOfVertices = positions.length / 3;	

    for (var i = 0; i < numberOfVertices; i = i + 1) {
        var vertPosition = new BABYLON.Vector3(positions[i*3], positions[i*3+1], positions[i*3+2]);
        var dsq = BABYLON.Vector3.DistanceSquared(point, vertPosition);

        if (minSquaredDistance > dsq)  {
            minSquaredDistance = dsq;
            closestVertex = vertPosition;
        }
    }    
    return closestVertex;
}

Maybe you can have a look here: Nearest neighbor search - Wikipedia

It seems building a kd-treee or a bd-tree from the mesh vertices could be a solution.

Maybe this lib can help: GitHub - ubilabs/kd-tree-javascript: JavaScript k-d Tree Implementation

1 Like

There’s also this one: GitHub - mikolalysenko/static-kdtree: A static kdtree data structure

Its author says it’s faster than GitHub - ubilabs/kd-tree-javascript: JavaScript k-d Tree Implementation

@Evgeni_Popov So these libraries are server-side: I need to calculate the closest position on a mesh to 5000-10000 3D points. Just so I understand before delving into this - I am guessing I send the 10k point to nodejs together with the mesh points and do the calculations in nodejs and then return the resutls?

No, those are js libraries, you can simply get the .js file of the library (from the github repository) in your own project and reference it with a <script src="..."></script> tag.

Doesn’t look like they are javascript libraries: static-kdtree/kdtree.js at master · mikolalysenko/static-kdtree · GitHub

I think GitHub - ubilabs/kd-tree-javascript: JavaScript k-d Tree Implementation can be used “as is”, simply by referencing the .js file.

As for static-kdtree/kdtree.js at master · mikolalysenko/static-kdtree · GitHub, I guess each library dependency could be retrieved by hand, but I’m not very familiar with all those module import things…

1 Like

That’s correct. I was able to include the ubilabs kdtree library using direct .js file. There were improvements when vertex number over 1000.