adjacent meshes
#1
Hi,

can you help me to solve the trouble?
I need to know how to check if a 3dpoint is adjacent to a mesh (without check every point of the mesh).
and i need to calculate the distance of  a 3dpoint to a mesh (not to the bounting box).

Sombody can help me?

Thanks!
#2
The easiest way is to brute force it: For each triangle compute it's distance to the point and then take the minimum. If the mesh is not large and you don't need to run this every frame, then it should suffice. 

I have yet to see a function in Ab3d that would do this, but that doesn't mean it does not exist.
#3
(11-20-2020, 01:24 PM)janovrom Wrote: The easiest way is to brute force it: For each triangle compute it's distance to the point and then take the minimum. If the mesh is not large and you don't need to run this every frame, then it should suffice. 

I have yet to see a function in Ab3d that would do this, but that doesn't mean it does not exist.

I tried, but the mesh is very large and i have to test too many points..... It needs to much time!

Really there is not a fast way to do it?
#4
If you a lot of models than you can first check the distance from the point to the model's Bounds - after that check only the models that are the closest to the position.

To optimize calculations with meshes that have a lot of positions, the easiest thing to do is to optimize access to positions. You need to know, then when accessing MeshGeometry3D.Position[index] on each call there is also a call to VerifyAccess method that checks if you are on the correct thread - this significantly slows down the access to positions. So if you copy the positions into an array of Point3D structs, you will be able to access that array significantly faster. Event better is to use float-based structs instead of double based Point3D - for example SharpDX.Vector3 or System.Numerics.Vector3 - this will reduce the memory traffic by half. 

You can also use Pallalel.For for very large position arrays (but test this as it takes some initialization time to use multiple threads).


Also, try to manually inline functions and use distance square instead of distance - for example, the easiest approach is to use:

var distance = (vector1 - vector2).Length;

But this is much slower then if you have vector1 written as x1, y1 and z1 and instead of using Length (that uses sqrt functions) just get the distance squared value:

var dx = x1 - vector2.X;
var dy = y1 - vector2.Y;
var dz = z1 - vector2.Z;
var distanceSquared = dx * dx + dy * dy + dz * dz;

Then you can find the minimum distanceSquared.

This is significantly faster - it does not require any call and no branches (I think that the previous method required at least 3 calls - one is Math.Sqrt and a few branches).

If you need an actual distance you can call Math.Sqrt(distanceSquared) when you have the minimum distanceSquared.


I think that this should be at least 10 times faster (more with using multi-threading).

If this will be still to slow, then you can significantly reduce the number of positions that needed to be checked by using OctTree or some other structure that divides the 3D space into smaller areas - then you fist check which areas of the OctTree or some other structure are closest to the 3D point and then calculate the distance only for the positions in that areas. See internet for more information about using that. You may also use the OctTree from Ab3d.DXEngine - there it is used for hit-testing.
Andrej Benedik
#5
Quote:...but the mesh is very large and i have to test too many points...
How many? If you can measure allocations/garbage collection then it might be good to try it as well. If you pass around structures like Point3D/Vector3 or anything larger then one integer, it might be worth to pass it either using ref or in argument modifier. Passing structs around causes by value duplicates them and it can result in large slow downs.

Code:
void PassedByValue(SharpDX.Vector3 vertex, SharpDX.Plane plane)
{
  // Do some stuff
}

void PassedByReference(ref SharpDX.Vector3 vertex, ref SharpDX.Plane plane)
{
  // Do some stuff
}

void Main()
{
  var v = new Vector3();
  var p = new Plane();
  // This will result in two copies of vector and plane
  PassedByValue(v, p);
   // This operation will be faster and no copies are created
   PassedByReference(ref v, ref p);
}

If you try to use SharpDX you will find out that most of functions come in pair and I would recommend to use the first one:
Code:
public static void DotNormal(ref Plane left, ref Vector3 right, out float result);
public static float DotNormal(Plane left, Vector3 right);

If you don't need the results immediately (like per frame basis, the user can wait) but you only don't want to block the rendering thread you could use async task and await, where you would just run all the checks in separate task (not necessarily on new thread) and await on the result to resume your code flow.
  


Forum Jump:


Users browsing this thread:
1 Guest(s)