2
\$\begingroup\$

I have reached some limits in my game experiments that seem to be solvable by working with content as 'point clouds'. My main concern now is how to convert the resulting point clouds into polygon meshes? I can't seem to find any algorithms anywhere, but I see people doing it in various programs, so it is clearly possible.

EDIT: Some elaboration. I am doing some simulation of, among other things, geological forces, and a polygon surface simply does not allow the needed detail. My goal is to create a landscape as a point cloud and use that to better simulate forces on it. But the changes are expected to be so complex that simply starting with a flat polygon surface and warping it will not be useful. So I need to taake the point cloud landscape and create a polygon surface for it, from the data it holds.

\$\endgroup\$
  • \$\begingroup\$ Do you want to ask about rasterization or triangulation? \$\endgroup\$ – Bálint Jun 5 '17 at 15:01
  • \$\begingroup\$ Probably triangulation, but I am open for both ideas! \$\endgroup\$ – Henry Stone Jun 5 '17 at 15:58
  • 1
    \$\begingroup\$ You probably need a hull-finding algorithm as well. \$\endgroup\$ – Draco18s no longer trusts SE Jun 5 '17 at 16:27
2
\$\begingroup\$

Usually you (or your artist) uses a modelling program and makes models. These already contain the information about the order they are in. This can be either done by indexing them (having an array, that basically says in which order they come, like 0, 1, 3, 3, 1, 2 for a quad) or by repeating them in the vertex list. The latter is usually only used when you want to have sharp edges, because you can't define a vertex and a normal vector separately.

There are however procedurally generated meshes. Those need to be triangulated using one of the algorithms, like Delauney triangulation.

GPUs always use triangles to draw things, because there are already a lot of optimized algorithms to draw them. Some APIs allow you to render quads or polygons, but those functions are deprecated, because GPUs have to triangulate them every frame, which is ineffiecient.

After you have a the vertices in order, you have to rasterize them. Rasterization is the process of converting points to triangles. This is also a pretty optimized. Most games don't do this part, they instead rely on an API such as OpenGL or DirectX, which can communicate with the GPU.

\$\endgroup\$
  • \$\begingroup\$ Sorry, I meant how to program your game to do it. \$\endgroup\$ – Henry Stone Jun 5 '17 at 19:50
  • \$\begingroup\$ @HenryStone This is a Q&A site designed to help fixing problems in already existing codebases or provide algorithms, we don't give tutorials, because there are already thousands of them \$\endgroup\$ – Bálint Jun 5 '17 at 20:04
  • \$\begingroup\$ I am not expecting tutorials, only an insight in a topic I do not yet fully understand. If this goes against policy, I will not object to the question being closed. \$\endgroup\$ – Henry Stone Jun 5 '17 at 21:30
  • \$\begingroup\$ "GPUs always use triangles". This is wrong. You can also use quads natively in some cards (which also has it advantages, it often has a nicer topology). Although its not that widely supported anymore. And, with geometry shaders, you can do certain isosurface extractions directly on the GPU. \$\endgroup\$ – Polygnome Jun 5 '17 at 21:43
  • \$\begingroup\$ @Polygnome This was either a long time ago (e.g. the Saturn distorted sprites to achieve polygonal effects, and those were quads) or you're speaking about the quads rendering mode in some APIs, in which case you should read my answer properly \$\endgroup\$ – Bálint Jun 6 '17 at 7:42
1
\$\begingroup\$

The process of converting data (for example, point clouds) into polygons is called meshing (since you produce a mesh) or Isosurface extraction. There are lots of techniques out there - marching cubes, marching tetrahedrons, surface nets, greedy meshing, dual conturing and many, many more. If you look for "Isosurface extraction", you'll find lots algorithms with different stenghts and weaknesses. Without knowing more, its hard to ecommend an approach.

For starters, marching cubes is a safe bet, though.

\$\endgroup\$
  • \$\begingroup\$ Thanks, that is a big help!! I use marching cubes already and love it, my problem is that the next version of my program does not limit points to a 3d grid, and I have never dealt with pount clouds as free floating clouds. It is very far from dealing with a rigid grid... \$\endgroup\$ – Henry Stone Jun 6 '17 at 10:05
  • \$\begingroup\$ You don't need a 3d grid for marching cubes. But as I said, without knowing more about your exact problem its hard to recommend any approach. \$\endgroup\$ – Polygnome Jun 6 '17 at 11:25
  • \$\begingroup\$ I have never seen Marching Cubes used in any other way than to represent a 3D point grid (heck, i used to do it myself for kicks). Do you have links to examples / explanations?? Also, I will explain my problem better in an edit in a moment... \$\endgroup\$ – Henry Stone Jun 12 '17 at 14:49
  • \$\begingroup\$ @HenryStone Sure, the end result with Marching cubes is an isosurface whose vertices only conincide with a 3D grid. But the point cloud can be arbitrary (it doesn't need to be a point cloud that conincides with a 3D grid, it can be of arbitrary density and distribution), you only need to have the proper weighing function, and it needs to be in a structure that can be efficiently queried (e.g. KD-tree). \$\endgroup\$ – Polygnome Jun 12 '17 at 14:56
  • \$\begingroup\$ Do you have examples? Thinking about this in the abstract is too much for my brain, I never saw MC as anything but a visual representation of grid values, and my brain can't let go of that... \$\endgroup\$ – Henry Stone Jun 12 '17 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.