# Create triangles out of any set of points

This topic is 988 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have a set of points (i think i won't have more than 10 each iteration)

now i must somehow connect them together so they will form some shape, triangles can't overlap. :/

reason i need this is: look at the picture:

theres a ships hull where that yellow thing in center shows the center of gravity, now theres a full blue background and light blue water, we are viewing that hull from underwater. now whenever water plane slices  some set of triangles that make hull, and water plane is above center of mass of the ship i need to create additional set of triangles that close, the shape that is below water (i mean i need to produce set of points that lie on waterplane, so when connected to center of mass will produce additional tetrahedrons) - this is needed to properly calculate submerged volume of an object.

so i could be left with that:

i need somehow to grou that to get

or maybe theres a better solution for this?

for now im cutting set of points of a convex solid by set of waterplanes, and store only triangles that are below these waterplanes, then produce tetrahedrons where apex of all is at center of mass point, then i additionally cut each tetrahedron by corresponding waterplane to get actual submerged volume and here comes my acutal problem i need additional set of triangles that close the shape whenever waterplane is above center of mass i need to use these points that are a result of cut to calculate remaining submerged volume.

i rather expect something that is quite fast, coz i am planning to do this  more than 50 times per frame.

Edited by WiredCat

##### Share on other sites

Look up 'convex hull'.

This is like puting a rubber band around all points and excluding interior points.

It would return a point / edge sequence like 5,3,4,2 excluding point 1.

Finaly you can triangulate this to a surface simply by connecting all edges with center of mass.

For 2D case this is quite easy to implement e.g. by sorting points by angle.

For 3D i'd use a library like https://code.google.com/archive/p/juliohull/

Could bu used to easily precalculate a low polygon aprroximization of the ship for faster processing.

##### Share on other sites

Although a convex hull would not solve the problem you specifically mentioned. It does a damn good job at collecting all the external points. You can then use a trinagalization algorithm to compute triangles, which you  can then create an area from for your buoyancy problem.

##### Share on other sites

When calculating volume of a triangle mesh a good way is to sum tetrahedron volumes given a reference point. This reference point does *not* need to be inside of the volume itself, as long as you sum *signed* volumes. For an explanation I recommend 2013 GDC lecture "Interacting with 3D Geometry" by Stan Melax. He explains signed volume summing quite well.

We can place the reference point on the water plane so that all triangles on the water plane contribute no volume to the summation. This lets you ignore these triangles when summing volume. I also have slides about the zero-volume triangle trick (which I learned from Catto's Game Programming Gems chapter, I think it was Gems 6?), be sure to check out slide 15 in particular: http://www.randygaul.net/wp-content/uploads/2014/02/RigidBodies_WaterSurface.pdf

Edited by Randy Gaul

##### Share on other sites
So how i am supposed to find boundary points?

##### Share on other sites

Although a convex hull would not solve the problem you specifically mentioned. It does a damn good job at collecting all the external points. You can then use a trinagalization algorithm to compute triangles, which you  can then create an area from for your buoyancy problem.

I don't think that's right. The convex hull problem is typically understood to require not just selecting the points, but actually giving you a triangle list.

However, I don't think there is any need to compute this at all. The OP says the problem he really needs to solve is computing the submerged volume of an object. I suspect what he really needs is to compute buoyancy, which I haven't done before, but I am sure can be done by adding the pressure at each face of the object, and that would be much easier to do.

##### Share on other sites

Yeah alvaro thats the fact but, i am not quite sure how to find a pressure of a submerged triangle at all,

anyway i found algorithm for that.

and i am really curious if anyone could find a formula for for pressure, pressure = Force/Area that means pressure is a vector, then it should somehow sum together so it will always point up (for still water, and steady body), that could make my calculations faster for about 100 times ;x

Edited by WiredCat

##### Share on other sites

Yeah alvaro thats the fact but, i am not quite sure how to find a pressure of a submerged triangle at all,

The force on a triangle due to pressure is a vector orthogonal to the triangle whose magnitude is the area of the triangle times the average of the depth of the vertices times a couple other things (gravity and density, I think). Of course, if you have a triangle that straddles the surface of the water, you need to clip it before you do this computation.

##### Share on other sites

So how i am supposed to find boundary points?

Not sure what you mean, but i assume you finaly only need to know the volume under the water plane?

An easy, fast enough solution would be this:

Use the convex hull lib i suggested to precompute a hull of maximum 30 vertices, should be accurate enough.

At runtime, build a list of vertices from this hull that are below the water plane.

Test all edges of the hull with the waterplane and add intersecting points to the list to handle points exactly at the water plane.

Use the lib again th create another convex hull and its volume from the list.

I know it's a big waste to compute a hull every frame when most of this data is already known,

but for a single ship it's surely fast enough, and you can continue to develop simulation, see how it works and optimize later.

Note: The convex hull algorithm comes from the Newton Game Dynamics engine, which also handles buoyancy out of the box.

##### Share on other sites

The only 3rd party lib i could use is for initializing a sound for my engine.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633736
• Total Posts
3013599
×