3D Convex Hull edges

Everything about development and the OpenMW source code.
User avatar
AnyOldName3
Posts: 2666
Joined: 26 Nov 2015, 03:25

3D Convex Hull edges

Post by AnyOldName3 »

I have a problem to solve which will help with shadows, but it doesn't seem to be something either Google or my brain can readily provide.

I start with:
  • A list of edges (pairs of 3D vectors) which together form the boundary of a convex volume. (Basically it's a convex hull, but not as a vertex list or a plane list, which means Google isn't helping.)
  • A list of extra edges I want to add in order to expand the volume.
  • (Optionally - I know how to compute this, but it might be unnecessary) a collection of points which are now inside the hull instead of on its boundary, so need removing from edges.
I need:
  • A list of edges forming the boundary of the volume now it's bigger, but with no edges which pass through the inside of the volume.
It's really easy to get rid of the edges which are connected to points that have ended up inside the new volume - when you know which those points are, you just delete any edges with those points. However, there can be edges between points that are still on the boundary, but pass through the volume. For example, in the case of this tetrahedron Image if the volume contained by the orange lines is added, the bottom edge of the tetrahedron is no longer needed as it's completely enclosed by the new volume. The problem is detecting this without also deleting the top edge of the tetrahedron - both are edges between a pair of vertices which are still in the hull that make up non-adjacent points of the loop of vertices connected to new edges.

With a normal convex hull system represented by either vertices or planes, there are published solutions as it's a common thing to do. All of the mathematically simple approaches I can think of which work in theory will fail due to floating point error with edges, though, and the range of the input to the algorithm is too big to pick an epsilon value that should always work.

I tried using a convex hull implementation from Bullet, but it isn't reliable enough, sometimes producing garbage data, and looking at the implementation, it looks like I'm just feeding it worst-case data rather than hitting any bugs. It's only designed to be good enough to produce approximate collision shapes rather than be mathematically sound.

There's potentially a solution which involves considering all of the edges connected to a vertex, working out which of those form an open-ended convex hull, and discarding things in the middle, but I've failed to convince myself that any of the things I've thought of to achieve that would be free from edge cases.

So basically I'm asking if anyone has any ideas or is willing to do some thinking with me.
User avatar
raevol
Posts: 3093
Joined: 07 Aug 2011, 01:12
Location: Caldera

Re: 3D Convex Hull edges

Post by raevol »

I'm not a 3d graphics programmer, so please ignore me if this is not helpful:

Why do you need to delete the line?

Why do you need to add the second shape to the first?

Can you calculate if a point is inside the whole shape?

Can you form triangles from sets of points and calculate their norm? Can you calculate if a point on that norm (that is infinitely close to the triangle but not in the plane of the triangle itself) is inside the shape?

If you could, if a triangle had norm points contained within the shape on both norms going in opposite directions, then one of the edges of the triangle is inside the shape, isn't it? And if another triangle was also inside the shape and shared an edge with the first bad triangle, then that shared edge would be the one to be deleted?
PatDaRat
Posts: 8
Joined: 03 Aug 2017, 09:45

Re: 3D Convex Hull edges

Post by PatDaRat »

I am not a 3D graphics programmer either, but here are my thoughts:

This is challenging to describe but here goes. Imagine you were holding this wireframe shape in your hands. Now you can look at it from all different directions. Now pick an edge, E, and look directly along it so that it becomes a point. In other words, project the wireframe onto a plane where the edge E is orthogonal to that plane.

If you're still with me and can picture this, then I think you might see a point in the middle, which is E, and number of connecting edges going off in different directions. What I think is relevant are the angles between these connecting edges. If you cannot find an angle greater than or equal to 180, then I would imagine that this edge must travel through the interior of the convex hull.

I hope this helps!
Last edited by PatDaRat on 16 Aug 2018, 12:13, edited 1 time in total.
Horrowind
Posts: 6
Joined: 07 Aug 2011, 16:34

Re: 3D Convex Hull edges

Post by Horrowind »

I have some theoretical background on 3D (actually n-D) geometry, but not so much algorithmic background. Here are my ideas:

A line segment is not an edge of a polyhedron/volume, if its midpoint (or any other point besides the end points) is inside the polyhedron, or conversely, it is an edge of the polyhedron, if its midpoint is on the boundary of the polyhedron.

From this, it looks to me, that an unoptimized algorithm for you problem seems to be:
1. Ignore the edge data you are given and just take all vertices of all edges and create from this a data structure from which you can easily deside (strict) containment in the convex hull.
2. Test for each edge, if the midpoint is inside the convex hull and not on the boundary.

Another idea is to find at each vertex the set of line segments which form edges in the polyhedron. This is probably slower than the previous approach, but might be more in line of what you were thinking about.
For each vertex v:
1. Generate the list of all edges, which are incident to v
2. Find a plane through v which does not contain any of the edges and move it inside the polytope. (You can take the average of the directions of all edges to find a normal vector for such a plane)
3. Intersect all rays starting in v and formed by the edge directions with the plane. Now find the intersections, which form the convex hull. All other come from edges, which are inside the polyhedron.
PatDaRat
Posts: 8
Joined: 03 Aug 2017, 09:45

Re: 3D Convex Hull edges

Post by PatDaRat »

I guess after thinking about it a little further, what i'm essentially saying is that an edge can only be a valid edge of the convex hull if there exists a plane that can rest against this edge without intersecting any of the other edges. By analysing the angles I put forward in my previous post, you can show whether such a plane exists or not.
User avatar
AnyOldName3
Posts: 2666
Joined: 26 Nov 2015, 03:25

Re: 3D Convex Hull edges

Post by AnyOldName3 »

All of these posts seem to be forgetting that if a point is on a plane, I can't find this out - depending on how the rounding happens to come out, there's a 50% chance of it being flagged as on one side of the plane and a 50% chance of it being flagged as on the other side, but a 0% chance of it being flagged as on the plane. I had thought about a system using the midpoints of edges, but the midpoints of all edges are on planes, and therefore have a good chance of being flagged as inside the volume.

I'll try and address things one point at a time:
Why do you need to delete the line?
Another function that needs to be run on the volume afterwards will fail if it is ill-formed.
Why do you need to add the second shape to the first?
The first shape represents a portion of the view frustum. The second represents the space between it and the sun. Together, they represent the volume which shadow casters can occupy.
Can you calculate if a point is inside the whole shape?
I can do this with a 50% false positive rate for things on the border, but all of the edges I want to keep are on the border, so half of those would be removed.
Can you form triangles from sets of points and calculate their norm? Can you calculate if a point on that norm (that is infinitely close to the triangle but not in the plane of the triangle itself) is inside the shape?
That's not terminology I recognise, but when I see the word close, my default response is going to be that the results will be wrong 50% of the time.
This is challenging to describe but here goes. Imagine you were holding this wireframe shape in your hands. Now you can look at it from all different directions. Now pick an edge, E, and look directly along it so that it becomes a point. In other words, project the wireframe onto a plane where the edge E is orthogonal to that plane.

If you're still with me and can picture this, then I think you might see a point in the middle, which is E, and number of connecting edges going off in different directions. What I think is relevant are the angles between these connecting edges. If you cannot find an angle greater than or equal to 180, then I would imagine that this edge must travel through the interior of the convex hull.
So I project everything into 2D, looking along an edge, work out the bearing of each of its neighbours, and check at least one of the gaps is above 180°? This actually seems like it might be viable. It's like a few other ideas I had, but I'm not seeing any of the pitfalls, and it passes my 'stab some cocktail sticks into an eraser and see if it works' test. I shall conduct further testing.
A line segment is not an edge of a polyhedron/volume, if its midpoint (or any other point besides the end points) is inside the polyhedron, or conversely, it is an edge of the polyhedron, if its midpoint is on the boundary of the polyhedron.

From this, it looks to me, that an unoptimized algorithm for you problem seems to be:
1. Ignore the edge data you are given and just take all vertices of all edges and create from this a data structure from which you can easily deside (strict) containment in the convex hull.
2. Test for each edge, if the midpoint is inside the convex hull and not on the boundary.
Due to rounding errors, I can't test if something is on the boundary - it's either on one side or the other, and things close to the boundary have a 50% chance of registering as on either side. That breaks this. It's something I've already tried.
Another idea is to find at each vertex the set of line segments which form edges in the polyhedron. This is probably slower than the previous approach, but might be more in line of what you were thinking about.
For each vertex v:
1. Generate the list of all edges, which are incident to v
2. Find a plane through v which does not contain any of the edges and move it inside the polytope. (You can take the average of the directions of all edges to find a normal vector for such a plane)
3. Intersect all rays starting in v and formed by the edge directions with the plane. Now find the intersections, which form the convex hull. All other come from edges, which are inside the polyhedron.
This is another thing I'd already thought of, but sliding the plane is where it fails - the scale of input the data can change by many orders of magnitude, even for one volume (parts of the added volume use -DBL_MAX and the original volume can sometimes range between 0.9998 and 0.9999). If the plane is slid far enough to soak up the rounding error for the big numbers, it also soaks up the whole range of the small numbers.

Picking a plane normal is also harder than just taking the average - if there are enough edges in one direction, the plane will face that direction, which is only acceptable if lines are constrained to 90°. A good normal is the average of just the minimum and maximum edges in an orthogonal plane, and then everything starts to get circular, with things requiring their own results to exist before they can be computed.

Final verdict:

I'm going to try a prototype of PatDaRat's solution as it's the only thing to pass both the 'stab some cocktail sticks into an eraser and see if it works' test and the 'doesn't require testing against planes' test.
User avatar
raevol
Posts: 3093
Joined: 07 Aug 2011, 01:12
Location: Caldera

Re: 3D Convex Hull edges

Post by raevol »

AnyOldName3 wrote: 16 Aug 2018, 14:09 The first shape represents a portion of the view frustum. The second represents the space between it and the sun. Together, they represent the volume which shadow casters can occupy.
Is it right to say that this shape will always be the same, just with different sizes and orientations? Is the "top" of the shape in the image always going to be closest to the viewer? Can you calculate the distance between the viewer and the endpoints of the lines?

If so, could you order the endpoints by distance to the viewer and then delete the line between endpoints 3 and 4 out of 8?
User avatar
AnyOldName3
Posts: 2666
Joined: 26 Nov 2015, 03:25

Re: 3D Convex Hull edges

Post by AnyOldName3 »

The answer to all of those is no. The prototype version of PatDaRat's idea seems to be working flawlessly, though, so I'm going to get it into C++ and hopefully it'll work.
User avatar
raevol
Posts: 3093
Joined: 07 Aug 2011, 01:12
Location: Caldera

Re: 3D Convex Hull edges

Post by raevol »

Haha, fair enough.
User avatar
Thunderforge
Posts: 503
Joined: 06 Jun 2017, 05:57

Re: 3D Convex Hull edges

Post by Thunderforge »

Would it be better to move this conversation to the Content Development Section? Or is it related somehow to OpenMW development?
Post Reply