2
\$\begingroup\$

I have a polygon which is defined by a set of vertices and I need the smallest sphere encompassing the mesh.

The spheres are defined by a position vector (x,y,z) and a radius.

Is there an algorithm that given a solid collision mesh with no holes generates the smallest sphere that encompasses a solid collision mesh with no holes in all cases


This is not a duplicate of this question because the question is only about a sphere encompassing a polygon soup a. I'm asking if there is an algorithm that given any solid collision mesh with no holes generates the smallest sphere that encompasses a solid collision mesh in all cases.

\$\endgroup\$
  • 1
    \$\begingroup\$ What have you tried? How did the solutions/research you did before hand not suffice? \$\endgroup\$ – Tyyppi_77 Jun 6 '18 at 13:02
  • \$\begingroup\$ @Tyyppi_77 the solutions did not suffice because they were costly and didn't work in all cases and this. \$\endgroup\$ – user116458 Jun 7 '18 at 8:32
  • 1
    \$\begingroup\$ To improve your question, you should also list the solutions that did not suffice. Why is costly an issue? Does your game deform meshes rapidly at runtime, or is there another reason why you can't cache the result? \$\endgroup\$ – Tyyppi_77 Jun 7 '18 at 8:35
  • \$\begingroup\$ @Tyyppi_77 the main reason why the question is not a duplicate is because I am very specific about asking for the smallest sphere and he is not. Also, my meshes sometimes change at run time \$\endgroup\$ – user116458 Jun 7 '18 at 8:44
  • \$\begingroup\$ There is still a lot of room for improving this question. What cases did you have that the other did not? What did you try that did not work? \$\endgroup\$ – Alexandre Vaillancourt Jun 7 '18 at 13:29
6
\$\begingroup\$

Solving the bounding sphere problem

Computing the bounding sphere for a set of given vertices means solving the minimum covering circle problem in three dimensions. There're many algorithms out there to find such a bounding sphere, like Welzl's algorithm (at this page you can find an implementation in Java), and many others. You can also check out Fischer's exact solver the open source Miniball algorithm is based on.

The minimum enclosing sphere problem can be solved with an average algorithmic complexity of O(n4) for a naive algorithm working on free vertices, down to an easy O(nk) where k is the number of vertices of the equivalent convex hull of your starting mesh.

Edit: such linear-time solution is optimized for a convex set of vertices only, because further assumptions can be made due to geometric properties of convexity. A mesh with just no holes isn't necessarily convex; for example, a C-shaped mesh has no holes, but it isn't convex either – you can connect its two edges with a segment, and part of it will lie outside the shape. A solid mesh may have fewer vertices to compute compared to a "holed" counterpart (and the CPU will be happy about it), but solidity doesn't imply convexity. Thus such mesh isn't eligible for the optimized algorithm mentioned above.

Consideration: exact vs. approximate solutions

As developers, we should be aware of many aspects in our games. Highly-detailed simulations (e.g. physics) or rich graphics imply a greater workload on CPU/GPU; on the other hand, prioritizing performances excessively may lead to a poor game experience due to low quality of simulation.

As coders, we must not waste resources when possible; we can optimize some operations in order to spend spare resources elsewhere if needed. As designers, we must define the minimum requirements for our game without being too greedy: a side-scrolling platformer will never need the same precision of physics simulation we expect from a top-quality racing game.

We need tradeoffs between results expected and resources required; every CPU clock is precious. If we can sacrifice some little realism without having the player noticing it and gain overall performances, this is a good way to go in my opinion.

An approximate, efficient algorithm

Having already aswered your question, if you don't really need the smallest sphere possible and an approximation of it is good enough, you can go with this algorithm.

algorithm MiniBall
    input: set V of points in space
    output: enclosing sphere in the form [center, radius]

    B = AABB(V)                // AABB from vertices
    C = mean(B.max + B.min)    // centroid of box B
    for each v in V:
        r = max(r, dist(C, v))        // distance to furthest point
    return [C, r]

The main idea is:

  • Consider the axis-aligned bounding-box, and use its centroid as origin. This ensures the sphere center will be always amongst the vertices;

  • Find the distance from the centroid to the furthest vertex, and use such distance as radius. This ensures that no points will lie outside of the sphere, at most on the sphere surface.

The complexity of this algorithm is O(n) where n is the number of vertices: you first read all vertices to find the bounding box corners, then you compute n distances between centroid and individual vertices.

It's quite fast, and may be more suitable for a real-time application with average precision requirements, such as a videogame.

Bonus: you can tweak the code line computing distance, and use the criterion that better suits your needs:

  • Max distance: no points outside of the sphere, at least one on the surface;

  • Min distance: no points inside the sphere, at least one on the surface (not really recommended in most cases);

  • Average distance: compute both the larger and smaller radii, and use mean(minR, maxR) as sphere radius. On average the sphere will split the vertices set into two halves. Some points may be inside the sphere, others outside of it, some can lie on the surface.

\$\endgroup\$
  • \$\begingroup\$ I edited the question liggiorgio. Does your answer still work now or is there any thing you want to add to it? \$\endgroup\$ – user116458 Jun 10 '18 at 11:59
  • \$\begingroup\$ My answer still works, I updated it anyway to reflect the further details you included and expand my explanation. \$\endgroup\$ – liggiorgio Jun 10 '18 at 13:26
0
\$\begingroup\$

Here is what I came up with after some feedback from @nwp.

  • set the radius to 0

  • set the center to the first vertex.

  • add the radius incrementally to the absolute distance between the first point and each point on the mesh.

  • add the center incrementally to the radius halved.

  • add the entities position to the mesh.

For more info see this thread on chat.

\$\endgroup\$
  • \$\begingroup\$ @AlexandreVaillancourt it answers the question now \$\endgroup\$ – user116458 Jun 8 '18 at 14:55
  • \$\begingroup\$ This does not give the smallest sphere. A simple counter example is 3 equidistant vertices. The smallest encompassing sphere would be center on the midpoint between them. If this solution solved your problem, then you need to reword your question to indicate you are looking for an approximation. \$\endgroup\$ – Pikalek Jun 9 '18 at 15:10
  • \$\begingroup\$ @Pikalek reworded the question \$\endgroup\$ – user116458 Jun 9 '18 at 15:16
  • \$\begingroup\$ @Pikalek does the answer work with a solid collision mesh \$\endgroup\$ – user116458 Jun 10 '18 at 11:57
  • \$\begingroup\$ @Pikalek do you have another counter example \$\endgroup\$ – user116458 Jun 11 '18 at 17:21

Your Answer

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