Jump to content
  • Advertisement
Sign in to follow this  
_WeirdCat_

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.

If you intended to correct an error in the post then please contact us.

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.

shbt.png

 

 

so i could be left with that:

setofp.png

 

i need somehow to grou that to get

 

setofp2.png

 

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!