Hi there, i am trying to find a good way to generate a mesh Plane from random points. The Mesh i am expecting is more or less a terain. So one rectangular area with high and low points.
In total there are around 60000 points in the original point cloud.
My goal would be to find a performant way to generate a mesh from these points. Preferably optimized where possible (if there are 10 points next to each other with the same height, they should be treated as one for example)
Are there already functions in babylonjs wich would help with this task? or is there something strategy to be used for something like that?
You can use the Marching Cubes Method! I found the function in the playground and optimized it as much as possible. You can find an example here: https://www.babylonjs-playground.com/#YLMG8N#2
Since you have a lot of points to process, I would suggest that you divide the entire area into smaller sections and work through them one by one.
Hi,
maybe my question was not quite correct. the problem i am facing is, that i have a bunch of xzy points in a more or less good grid. the data comes from laserscans and is around 160000 points big. and from this data i need to make a mesh.
there is two issues with the points:
it is not always a perfect grid. meaning that there are not always the same number of colums and rows (although they are very close together). so it can look like this:
X X
+------------+
| X X X X |
| |
| X X X X | X
| |
X | X X X X |
+------------+
X
one row can be 400pt long (in the example above 4 pt) the next one 399. so i cannot make a custom mesh, because i never really know wich point is on what row.
i dont know but i guess (because its just too many points) there could be points missing in the middle.
so my first idea was to check for the largest rectangle in the middle of all points somehow like this:
but for hundredthousands of points… idk if this is not way to expensive to calculate.
I tried to understand the marching cube algorithm, but tbh struggle to understand it. is it correct that i would run into problems when my grid is not complete?
or would this still be a good way to go (then i really would need to make some efford to understand the marching cubes )
if you have any suggestion how to move from here please let me know! Thanks a lot!!
The important places you have to consider are the this.max value which will be used from -this.max until this.max as a space where the marching cubes act.
class Chunk {
constructor() {
this.max = 10;
Second, you need a chunked loop over your points which have to be transformed into the marching cubes space:
let chunk = new Chunk();
let xmin = 0;
let xmax = 2*chunk.max;
let ymin = 0;
let ymax = 2*chunk.max;
let zmin = 0;
let zmax = 2*chunk.max;
let step = 1000; // you don't have to consider each point so vary this value to get a good enough result
for (let i=0;i<points.length;i+=step) {
let x = points[i].x;
let y = points[i].y;
let z = points[i].z;
if (x < xmin || x > xmax) continue;
if (y < ymin || y > ymax) continue;
if (z < zmin || z > zmax) continue;
// Transform the coordinates to fit into the dimensions of the chunk space
let cx = BABYLON.Scalar.RangeToPercent(x, -this.MAX, this.MAX);
let cy = BABYLON.Scalar.RangeToPercent(y, -this.MAX, this.MAX);
let cz = BABYLON.Scalar.RangeToPercent(z, -this.MAX, this.MAX);
chunk.cells[cx][cy][cz] = 1;
}
chunk.generate(); // your first cube of points are handled!
Now what you really need is a loop over all other chunked cubes of your points.
i.g. for the first line:
for (let xmin=0; xmin<max_x_point;xmin += 2*chunk.max) {
// insert the code above
}
the Problem i am having is that i find it very hard to control the mesh. i guess it seems to be not really the right approach i guess. id rather find a way to directly create a custommesh from the points. then i would have a direct control over the exact mesh.
i am currently thinking about delaunay triangulation. might that not be a better solution?
does anyone know of a good example in the playground?
With the help of chatGPT: Here is the Delaunay Trangulation Algorithm. Triangle Points are displayed in the console. I didn’t verify the result visualy.
Me: What is the relation between “Delaunay-Triangulation” and “marching cubes”?
ChatGPT:
Delaunay triangulation and Marching Cubes are both algorithms used in computer graphics and computational geometry, but they serve different purposes and operate on different types of data.
Delaunay triangulation is a geometric algorithm used to divide a set of points into a triangular mesh, where the resulting triangles satisfy the Delaunay criterion. The Delaunay criterion states that for every triangle in the mesh, no point lies within the circumcircle of that triangle. Delaunay triangulation is widely used in various applications, such as mesh generation, interpolation, and surface reconstruction.
On the other hand, Marching Cubes is an algorithm used to create a polygonal representation (usually triangles) of an isosurface from a three-dimensional scalar field. It operates on volumetric data, typically obtained from medical imaging or scientific simulations, where each voxel (3D pixel) contains a scalar value. The algorithm works by examining the scalar values of the voxels and constructing triangles to approximate the isosurface that represents a specific scalar value.
Although they have different purposes, there can be some connection between Delaunay triangulation and Marching Cubes in certain contexts. For example, in some applications involving surface reconstruction from point clouds, one might use Delaunay triangulation to create an initial mesh and then apply the Marching Cubes algorithm to refine and generate a more detailed mesh representation of the isosurface.
In summary, Delaunay triangulation is primarily used for dividing a set of points into triangles, while Marching Cubes is used for generating a polygonal representation of an isosurface from volumetric data. While they can be used together in some scenarios, they are distinct algorithms with different purposes.
I have tried to get chatGTP to write me a function as well. The little effer is pretty confused about format of the data you should feed it. Here’s the result: Marching_Cubes_ChatGPT.txt
Point is you have to feed it a 3 dimensional array. Just the points won’t do.
Will keep you posted but am looking into other things as well.
)
