1
\$\begingroup\$

am working on an algorithm for procedural generation of 3D meshes for caves in a side-scroller game.

The algorithm nicely computes contours and also points inside the caves that are supposed to be anchor points for the mesh. A sample for this can be seen in the following image: enter image description here

The idea is that each of those anchor points has a distance to the view-pane depending on their distance to the contour. This way the caves have a roughly spherical shape in 3D.

This is also the reason I added those anchor points because having triangles from wall-to-wall would not enable me to have actual 3D caves.

However, the problem now is how to make the triangles. I found a nice implementation of the Delaunay triangulation algorithm. However that yields me the following mesh: enter image description here

Obviously this algorithm is not aware of what's inside my cave and what is not and thus forms triangles completely outside of the caves. Pruning those outliers does not yield good results because then the contours of the caves are interrupted.

I have heard of "ear cut" algorithms that can work with concave shapes like my outlines. However those are not compatible with the anchor points I require.

What I'd need is a triangulation algorithm that allows me either to add anchor points inside the figure, or that allows me to limit the maximal length of vertices thus computing anchor points on its own.

Is such an algorithm known?

Huge thanks!

\$\endgroup\$
3

2 Answers 2

Reset to default
1
\$\begingroup\$

You can compute the centroid of the triangles that make your mesh and cull them if they are outside your original boundary.

Reference

\$\endgroup\$
0
\$\begingroup\$

You have the solution in your last line "that allows me to limit the maximal length of vertices" If you have the code which is generating the good mesh, except for the outside zones, you can add a line to check triangle's size as it is written by the meshing code.

You can alternatively write a brief function which fetches your triangle point arrays, and checks every triangle size in the model. You can either rewrite a new mesh with new vertex indices, or you can go cheap, and resize triangles that are too big, so that all three points are the same point.

Triangles can occupy an infinitely small point in space, and it makes them invisible to the graphics card. you can rewrite the big ones small else erase and re-index them, either in the triangle checking stage of your meshing code, or in a mesh editing function afterwards. for a mesh of that size, it would take about 1 frame of time.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you for your response, but I'm not sure whether I understand yet. Fear you missed a word in "you can a line to every vertex". I cannot just remove the triangles that are partially outside of the desired area because some of their vertices form the outline of my cave! It would be great if I could remove just the wrong vertices, but how do I form a triangle from the remaining two vertices again? Have already thought to search for the nearest anchor point, but then I have triangles that overlap... \$\endgroup\$
    – DragonGamer
    Commented Oct 12, 2019 at 18:15
  • \$\begingroup\$ Sorry, i meant: you can add a some lines to check triangle's size as it is written by the meshing code.Every triangle is written in a loop of the meshing code. I edited that ages ago for a snap-MC version of marching cubes: it's the blue pics here: stackoverflow.com/questions/35112181/… you are doing the same thing, except for the large edges and not the small edges. \$\endgroup\$
    – bandybabboon
    Commented Oct 12, 2019 at 18:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .