Bounding sphere for spheres

#1

I know the thread name could sound strange, so I try to explain my problem. I have some number of spheres and would like to calculate an optimized bounding sphere containig al that spheres.

#2

Ritterâ€™s algorithm is a simple and fast algorithm thatâ€™s usually what is used for a non-optimal points enclosing sphere, you can use your spheres vertices as those points.

Someone wrote a script, not sure how it works though:

#3

But I would like to have an optimized bounding sphere and for spheres this algorithm retuns a bad aproximation. For meshes and boxes it worcks fine.

#4

Thesis:

CGAL doc:

https://doc.cgal.org/latest/Bounding_volumes/classCGAL_1_1Min__sphere__of__spheres__d.html

CGAL implantation:

#5

Thanks, have already seen that CGAL APi, but have not found the sorces and even if I do porting that C/C++ code to maxscript will defently go over my maxscript abilities.
I think to have a solution for my problem, but after reading that other thread here, not shure if center of bounding box is also center of bounding sphere.

#6

So I am going to try something like this

rMax=0
for s in spheres do (
if r>rMax then rMax=r
)
return rMax
)

center is the center of the bounding box and used as center of the bounding sphere to. Can this worck?

#7

Not at all.

#8

OK, thanks for the example. However the reason the bounding sphere in your example is not optimized, seems to be because the center of bounding box and bounding sphere is not the same. The other algorithm, that uses distances between center of bounding box and every single vertex would give at least the same result or even worth. Unfortunatelly I have not found any way to get the real center of the bounding sphere.

#9

!!??
Do what you want. Itâ€™s always the same with you.

P.S.: @KaaF has shown you a 183 pages PDF with a solution from a mathematician. Do you really think you can solve this problem by yourself in a such simple way?
Have you think in such a simple thing that the bounding box means absolutely nothing because it depends on the ortonormal axis [XYZ]?
Have you ever heard about the Problem of Apollonius?https://en.wikipedia.org/wiki/Problem_of_Apollonius
Itâ€™s basic geometry, just for three circles, and itâ€™s not easy at all, and has nothing to do with rectangular bounding box.
In any case, silly me by answering you again. Never more.

Edit: by the way, you say you havenâ€™t found any way to get the center of the bounding sphereâ€¦ Of course!!! This is the problem to solve! Once you have the center, the radius is a childrenâ€™s game!!!

#10

Man, really not understanding why you always geting it wrong? I ageed with you, just wanted to know if there is posibly a way to improove my solution. I saw that 183 pages PDF with a solution from a mathematician, but such huge text in english, which is the most dificult language I know, is a problem for me. Really hope you understanding me right his time, if not I am really sory. Also apologize for the previous misunderstanding.

#11

Iâ€™m going to explain it to you, although with little hope that you understand.
When I answer to you, I take my time to:

• Understand what your problem is
• Read and understand what your code does (you havenâ€™t explained it).
• Think about your solution to see if it can be valid using all my mathematic-engineering background.
• Realize that it canâ€™t and find a good example to show you that it canâ€™t.
• Draw the example, capture the screen, upload the image to a server and post the answer.

After all that, the answer I recieve from you is that my example doesnâ€™t fit what you are proposing. And that is not true. So, the only explanations I see are:

• You have taken a lot less time to read my post than me to try to give you a good answer. That is not very polite
• You donâ€™t mind at all and you are going to use your method yes or yes. That is not very polite either.

By the way, you are lucky if your problem with the 183 pages PDF is just the English language. You have incredible Maths skill! Who could have said itâ€¦

#12

Like I said, really apologize for the misunderstanding. I know itÂ´s hard to believe, but english is really a much biger problem for me than math. I am defenetly not a Dr. of math, but the formula stuff, was the only thing, I more or less understood there.
But the biger problem then english language itself for me is its mentality (posiblly not the right word, but have no idea how to call it). When I write thanks for the answer, I meanI really greatfull and it shouldnÂ´t be taken ironicaly, or donÂ´t know how it called. ItÂ´s really hard for me to know how youÂ´ll understand my answer.
So if I understood you right now, you think I wrote something like this: â€śyour answer is sh*t, I donÂ´t care about, going to use my solution aniwayâ€ť. I defenetly didnÂ´t said something like that.

#13

here is a little toy to play with â€śbounding sphereâ€ť idea:

``````(
/************* METHODS and STRUCTS **************/
fn pairGenerator count =
(
pairs = #()
for k=1 to count do for n = (k+1) to count do append pairs [k,n]
pairs
)
fn sphereDistance s0 s1 &center: =
(
p = s1.pos - s0.pos
d = length p
v = normalize p
p0 = s0.pos - s0.radius * v
p1 = s1.pos + s1.radius * v
if defined center do center = (p0 + p1)/2

--point pos:p0
--point pos:p1
--point pos:center

)

/*************** RANDOM SCENE SETUP ******************/
with redraw off
(
delete objects

count = 50
max_offset = 200

for k=1 to count do
(
pos = random -[max_offset,max_offset,max_offset] [max_offset,max_offset,max_offset]
)
gc light:on
)

/**************** MAKE BOUNDING SPHERE **************/
(
bounds = #()
iter = 0

best_bound = -1
curr_bound = 0

act = on
while act do
(
sps = for obj in objects where iskindof obj geosphere collect obj
ss = pairGenerator sps.count
global _xx = for s in ss collect
(
x = s[1]
y = s[2]
r = sphereDistance sps[x] sps[y] center:&c

)
p = _xx[1]
if (best_bound + 0.01 < curr_bound) then
(
iter += 1
best_bound = curr_bound

append bounds best_bound
format "% >> radius:%\n" iter best_bound
)
else act = off
)

format "% = difference:%\n" [bounds[1],bounds[iter]] (bounds[1]/bounds[iter])
best_bound
)
)``````

you can try to run whole script above.

it will make a scene of yellow target spheres and generate red bounding spheres for them.

in the listener you will see some log output which tells number of iterations, min and max bounding radius, and difference.

as you can see the difference is usually not greater than 10% depending on number of target spheres, their scattering size, and radius.

the algorithm idea is:
â€“ find two the most distant spheres
â€“ make a bounding sphere around these two
â€“ add new bounding sphere to the target list
â€“ repeat above stepsâ€¦

the â€śidealâ€ť bounding sphere is in-between first and last bounding spheres.
how to find it will be your homework

#14

this is the worst possible difference (easy to calculate)

the red circle is the result of my algorithm, the green one is the â€śidealâ€ť boundingâ€¦
the picture should give you a hint about how to find the â€śidealâ€ť.

#15

Thanks, that looks very interesting, let see what I can do with it using my very limited maxscript knowledge, but sincerely grateful.
Just 1 question, what is that other sphere is, I mean not the green and not the red one? No idea what that color is in english.