Random Points to mesh?

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?

Thank you so much for ideas!!


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.


very impressive! I will look into that! Thanks

Another option is to use Dynamic Terrain | Babylon.js Documentation

sounds also good, but as far as i understand i need to know exactly rows / colums to go with this option?


You can populate Data Map with noise, for example - Dynamic Terrain | Babylon.js Documentation

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:

  1. 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 |

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.

  1. 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 :wink: )

if you have any suggestion how to move from here please let me know! Thanks a lot!!


Look at this Mesh-Painter Example

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

I hope this helps to code your first meshes.

Edit: There is a bug in my pseudo code. This is a running example: Marching Cubes with random numbers

I still need to try this for my myself but it sure looks like the way to go @CodingCrusader & @pcace …
Here’s that video:

and there are more if search for Marching cubes

Hi there, thank you so much for your help! I played around with the algorithm, and found your example @CodingCrusader very very helpful: https://www.babylonjs-playground.com/#YLMG8N#10

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?

THanks a lot!

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.

Delaunay Trangulation

Me: What is the relation between “Delaunay-Triangulation” and “marching cubes”?

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.

1 Like

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:
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.

Funny how your chatGPT code renders a beautiful grey screen :thinking:
And it is pretty different from what i got.

Do not believe everything the ChatBot puts out and claims to be true. The code is missing some things and has some errors.

On the other hand, roughly evaluated, the code looks pretty optimized. I’ll have a closer look if I can find some time somewhere.

Sorry for the confusion, I’ll create a visual output for you…

don’t worry about it too much
that’s what chatGPT says way too often: “Sorry for the confusion” :wink:
And then render some new code with errors.

Here we are… but I am not sure if the result is correct…

Delaunay Trangulation | Babylon.js Playground (babylonjs-playground.com)


it looks plausible but is it right?

Compared with some pictures from google, I would strongly say “no, it’s far away from beeing right!”.

Here is a js-lib where you can pick up the code you need: mapbox/delaunator: An incredibly fast JavaScript library for Delaunay triangulation of 2D points (github.com)

My plan is now to use exactly this library to triangulate. i will then inject the z value after trianulation to get my terrain mesh ind 2.5D.

Thanks a lot for all your help! I will try to make a playground link when finished