linking points to create mesh

[Kairu]

hi,

i have a problem, let's say i have a number of scattered points in 3D space, in which i want to create mesh with. is there any irrlicht function that can do this automatically by knowing the location of the points only?

note : i know i can create mesh by combining 'triangular list/fan' , but is there a way to do this automatically since the points is scattered randomly?

thanks

[hybrid]

No, that's not possible in Irrlicht automatically. Basically because it's a very difficult task, which requires lots of advanced algorithms to do it nice.

[bitplane]

Sounds like an interesting problem though! There are lots of different ways to solve it too, but it depends on what you need.
Do you need to support concave shapes? Does it need to be fast? Do you need a solid mathematical approach or something simple and hacky?

[Kairu]

the idea is user enter position manually( the point is on the top of the line), and it will not have any order(depend on user), and i want to create mesh to cover all the point,
anyway, i m trying to manually create and arrange each triangle to fill it(dont know what is the term for this)
so if anyone have any idea or even the algorithm idea , please help

thanks

[bitplane]

So the algorithm really works in 2D, you're tessellating a surface rather than a volume. The back of the surface is always on the negative Y.
This is pretty easy, just flatten the points on the XZ plane (remove Y coord). Pick a point, find the next closest point to form an edge (line2d<f32>), then find the next closest to make your first triangle.

You now have a list of 3 edges, each has an inside (right) and outside (left), you can work from the inside.

Now do something like this:

Code: Select all

for edge in AllEdges:
  if not edge.complete:
    p = find closest outside point
    if p:
      create new triangle (from edge.start, edge.end and p)
      addEdge(edge.start, p)
      addEdge(p, edge.end)
  
    edge.complete = true

addEdge would have to make sure the same edge isn't added twice-

Code: Select all

addEdge( start, end ):
  e = AllEdges.find(start, end)
  if e:
    e.complete = true
  else:
    AllEdges.add(start, end)

Keep in mind that .find would have to assume that edge(start, end) == edge(end, start)

[wITTus]

Never played these line connecting games for kids?
Using the closest point is a very vague approach.

Looking forward to see the result of Bitplane's algo.