I want to write a script that will find an object’s optimized bounding sphere. In other words, the smallest possible sphere that the object can fit into. I don’t know if this is something that can be done mathematically, or if I will just have to have it run through some trial and error and correct itself incrementally.
I know that Max has some special ways of dealing with sphere intersections such as the RayMeshGridIntersect function, and that there is a bounding sphere option in Max’s Dynamics system, so I am hoping there is some kind of an elegant solution for this. Any thoughts?
You can get the objects center position, determin it’s max and min points and then you can work out the center point of your circle and the radius of the circle.
$.center
$.min
$.max
Those should be the commands you need and
Sphere()
to create your spheres.
Yeah, that’s what I’m using at my starting point…
global RO_KnuckleBall
try(destroyDialog RO_KnuckleBall)catch()
fn knuckleBall tgt =
(
centerPivot tgt
boundSize = (tgt.max - tgt.min) / 2
startSize = 0
for i = 1 to 3 do if boundSize[i] > startSize do (startSize = boundSize[i])
g = geosphere pos:tgt.pos
g.radius = startSize
)
rollout RO_knuckleBall "Knuckle Ball"
(
pickbutton pck_Tgt "Pick target"
on pck_Tgt picked obj do knuckleBall obj
)
createDialog RO_KnuckleBal
Unfortunately that doesn’t quite do it.
Working with a cube, for example, that would actually give you a sphere entirely INSIDE the cube. Also (for something with a roughly hemisphere shape, for example) the midpoint of the bounding box does not match the midpoint of the bounding sphere.
EDIT: Wait, I was wrong about the inside of the cube one. Scratch that. But anyway, it IS a bit more complicated than that for less regular shapes ^^;
You could find the distance between the individual vertices and $.center and use the bigger distance as the sphere’s radius. On very high poly items it could be very slow of course…
Finding the optimal bounding sphere of any given set of points is not as trivial as you might think. Using maxscript’s .min, .max properties (or nodeGetBoundingBox) will not result in a sphere that tightly fits the point cloud. If you Google for it you’ll find a couple of different approaches to this problem, here’s a couple them:
http://www.gamedev.net/reference/articles/article2484.asp
http://www.compgeom.com/meb/
http://www.inf.ethz.ch/personal/gaertner/miniball.html (2d implementation)
Martijn
I had a feeling SOMEONE must have looked into this problem before, and it seems I was right, just not in Maxscript. I’ll take a look the Welzl one, as some of the other stuff is over my head.
EDIT:
Okay, someone remind me… how do you get an enclosing circle for a triangle or quadrangle?
EDIT AGAIN:
Actually, I got the triangle… just need the quadrangle.
[left]Okay. I got a script working that will create a bounding sphere for the first 4 points of an object, now I just need help figuring out how to iterate it through the rest of the object’s points.
[/left]
global RO_KnuckleBall
try(destroyDialog RO_KnuckleBall)catch()
global s
-- special thanks to Joel Hewitt (a.k.a. Gravey)
fn circumcenter p1 p2 p3 =
(
BC = distance p2 p3
CA = distance p3 p1
AB = distance p1 p2
baryCoords = [ (BC^2 * (CA^2 + AB^2 - BC^2)), (CA^2 * (AB^2 + BC^2 - CA^2)), (AB^2 * (BC^2 + CA^2 - AB^2)) ]
triArea = baryCoords.x + baryCoords.y + baryCoords.z
baryCoords /= triArea -- normalize the barycentric coordinates
baryCoords.x * p1 + baryCoords.y * p2 + baryCoords.z * p3
)
-- get measurements and create spheres
fn defineSpheres p =
(
-- midpoints of lines
midAB = (p[1] + p[2]) / 2
midAC = (p[1] + p[3]) / 2
midAD = (p[1] + p[4]) / 2
midBC = (p[2] + p[4]) / 2
midBD = (p[2] + p[4]) / 2
midCD = (p[3] + p[4]) / 2
-- midpoints of triangles
centerABC = circumcenter p[1] p[2] p[3]
centerABD = circumcenter p[1] p[2] p[4]
centerACD = circumcenter p[1] p[3] p[4]
centerBCD = circumcenter p[2] p[3] p[4]
-- spheres defined by 2 points
s2_AB = geoSphere pos:midAB radius:(distance p[1] midAB)
s2_AC = geoSphere pos:midAC radius:(distance p[1] midAC)
s2_AD = geoSphere pos:midAD radius:(distance p[1] midAD)
s2_BC = geoSphere pos:midBC radius:(distance p[2] midBC)
s2_BD = geoSphere pos:midBD radius:(distance p[2] midBD)
s2_CD = geoSphere pos:midCD radius:(distance p[3] midCD)
-- spheres defined by 3 points
s3_ABC = geoSphere pos:centerABC radius:(distance p[1] centerABC)
s3_ABD = geoSphere pos:centerABD radius:(distance p[1] centerABD)
s3_ACD = geoSphere pos:centerACD radius:(distance p[1] centerACD)
s3_BCD = geoSphere pos:centerBCD radius:(distance p[1] centerBCD)
)
-- get position and radius of spheres
fn getSphereData =
(
s = #(#(), #())
for o in objects where classOf o == geoSphere and o != undefined do
(
append s[1] o.pos
append s[2] o.radius
)
)
fn knuckleBall tgt =
(
-- define initial points
p = #()
for i = 1 to 4 do p[i] = polyOp.getVert tgt i
defineSpheres p
getSphereData()
for a = 1 to s[1].count do -- for all spheres in the scene
(
for b in p where distance s[1][a] b > s[2][a] do -- for all points in array
(
-- delete spheres with points that fall outside
try(for o in objects where classOf o == geoSphere and o.pos == s[1][a] do delete o) catch()
) -- end b loop
) -- end a loop
getSphereData()
format "spheres: %
" s
for a = 1 to s[1].count do -- for all spheres in the scene (there -should- only be one)
(
-- remove redundant points from the array
for b = 1 to p.count do (try(if distance s[1][a] p[b] < s[2][a] do deleteItem p b) catch())
)
format "point array: %
" p
) -- end RO_KnuckleBall
rollout RO_knuckleBall "Knuckle Ball"
(
pickbutton pck_Tgt "Pick target"
on pck_Tgt picked obj do knuckleBall obj
)
Now I’ve reached the absolute limit of what I can do on my own. From looking at this, it seems to me like it SHOULD work, only it doesn’t. It’s clearly doing SOMETHING, but I can’t figure out where the script is going wrong. Is there anything glaringly obvious I’m doing wrong?
I’ve highlighted what I consider to be the problem area (the script at least -seems- to work up to that point).
global RO_KnuckleBall
try(destroyDialog RO_KnuckleBall)catch()
global s
-- special thanks to Joel Hewitt (a.k.a. Gravey)
fn circumcenter p1 p2 p3 =
(
BC = distance p2 p3
CA = distance p3 p1
AB = distance p1 p2
baryCoords = [ (BC^2 * (CA^2 + AB^2 - BC^2)), (CA^2 * (AB^2 + BC^2 - CA^2)), (AB^2 * (BC^2 + CA^2 - AB^2)) ]
triArea = baryCoords.x + baryCoords.y + baryCoords.z
baryCoords /= triArea -- normalize the barycentric coordinates
baryCoords.x * p1 + baryCoords.y * p2 + baryCoords.z * p3
)
-- get measurements and create spheres
fn defineSpheres p =
(
-- midpoints of lines
midAB = (p[1] + p[2]) / 2
try(midAC = (p[1] + p[3]) / 2) catch()
try(midAD = (p[1] + p[4]) / 2) catch()
try(midBC = (p[2] + p[4]) / 2) catch()
try(midBD = (p[2] + p[4]) / 2) catch()
try(midCD = (p[3] + p[4]) / 2) catch()
-- midpoints of triangles
try(centerABC = circumcenter p[1] p[2] p[3]) catch()
try(centerABD = circumcenter p[1] p[2] p[4]) catch()
try(centerACD = circumcenter p[1] p[3] p[4]) catch()
try(centerBCD = circumcenter p[2] p[3] p[4]) catch()
-- spheres defined by 2 points
try(s2_AB = geoSphere pos:midAB radius:(distance p[1] midAB)) catch()
try(s2_AC = geoSphere pos:midAC radius:(distance p[1] midAC)) catch()
try(s2_AD = geoSphere pos:midAD radius:(distance p[1] midAD)) catch()
try(s2_BC = geoSphere pos:midBC radius:(distance p[2] midBC)) catch()
try(s2_BD = geoSphere pos:midBD radius:(distance p[2] midBD)) catch()
try(s2_CD = geoSphere pos:midCD radius:(distance p[3] midCD)) catch()
-- spheres defined by 3 points
try(s3_ABC = geoSphere pos:centerABC radius:(distance p[1] centerABC)) catch()
try(s3_ABD = geoSphere pos:centerABD radius:(distance p[1] centerABD)) catch()
try(s3_ACD = geoSphere pos:centerACD radius:(distance p[1] centerACD)) catch()
try(s3_BCD = geoSphere pos:centerBCD radius:(distance p[1] centerBCD)) catch()
)
-- get position and radius of spheres
fn getSphereData =
(
s = #(#(), #())
for o in objects where classOf o == geoSphere and o != undefined do
(
append s[1] o.pos
append s[2] o.radius
)
)
fn knuckleBall tgt =
(
-- define initial points
p = #()
for i = 1 to 4 do p[i] = polyOp.getVert tgt i
defineSpheres p
getSphereData()
-- delete spheres with points that fall outside
for a = 1 to s[1].count do
(
for b in p where distance s[1][a] b > s[2][a] do
(
try(for o in objects where classOf o == geoSphere and o.pos == s[1][a] do delete o) catch()
) -- end b loop
) -- end a loop
-- delete all but the smallest bounding sphere
getSphereData()
for o = 1 to objects.count where classOf objects[o] == geoSphere do
(
if objects[o].radius != aMin s[2] do delete objects[o]
)
getSphereData()
-- remove redundant points from the array
for a = 1 to s[1].count do
(
for b = 1 to p.count do (try(if distance s[1][a] p[b] < s[2][a] do deleteItem p b) catch())
)
/* */
-- continue creating and checking spheres using the remainder of the object's points.
for i = 5 to (tgt.numVerts) do
(
append p (polyOp.getVert tgt i)
defineSpheres p
getSphereData()
-- delete spheres with points that fall outside
for a = 1 to s[1].count do
(
for b in p where (distance s[1][a] b - s[2][a]) > .0001 do
(
for o = 1 to objects.count where classOf objects[o] == geoSphere do
(
if objects[o].pos == s[1][a] do (delete objects[o])
)
)
) -- end a loop
-- delete all but the smallest bounding sphere
getSphereData()
for o = 1 to objects.count where classOf objects[o] == geoSphere do
(
if objects[o].radius != aMin s[2] do delete objects[o]
)
getSphereData()
-- remove redundant points from the array
for a = 1 to s[1].count do
(
for b = 1 to p.count do (try(if distance s[1][a] p[b] < s[2][a] do deleteItem p b) catch())
)
)
/* */[/b]
) -- end RO_KnuckleBall
rollout RO_knuckleBall "Knuckle Ball"
(
pickbutton pck_Tgt "Pick target"
on pck_Tgt picked obj do knuckleBall obj
)
createDialog RO_KnuckleBall
I’ve tried debugging this and I’ve made a couple changes. Apparently I have something set up wrong even in the first part, because the stuff I’m getting in the listener doesn’t make sense.
Could someone take a look at this and tell me what I’m doing wrong? I’m completely lost…
global RO_KnuckleBall
try(destroyDialog RO_KnuckleBall)catch()
global s
-- special thanks to Joel Hewitt (a.k.a. Gravey)
fn circumcenter p1 p2 p3 =
(
BC = distance p2 p3
CA = distance p3 p1
AB = distance p1 p2
baryCoords = [ (BC^2 * (CA^2 + AB^2 - BC^2)), (CA^2 * (AB^2 + BC^2 - CA^2)), (AB^2 * (BC^2 + CA^2 - AB^2)) ]
triArea = baryCoords.x + baryCoords.y + baryCoords.z
baryCoords /= triArea -- normalize the barycentric coordinates
baryCoords.x * p1 + baryCoords.y * p2 + baryCoords.z * p3
)
-- get measurements and create spheres
fn defineSpheres p =
(
-- midpoints of lines
midAB = (p[1] + p[2]) / 2
try(midAC = (p[1] + p[3]) / 2) catch()
try(midAD = (p[1] + p[4]) / 2) catch()
try(midBC = (p[2] + p[4]) / 2) catch()
try(midBD = (p[2] + p[4]) / 2) catch()
try(midCD = (p[3] + p[4]) / 2) catch()
-- midpoints of triangles
try(centerABC = circumcenter p[1] p[2] p[3]) catch()
try(centerABD = circumcenter p[1] p[2] p[4]) catch()
try(centerACD = circumcenter p[1] p[3] p[4]) catch()
try(centerBCD = circumcenter p[2] p[3] p[4]) catch()
-- spheres defined by 2 points
try(s2_AB = geoSphere pos:midAB radius:(distance p[1] midAB)) catch()
try(s2_AC = geoSphere pos:midAC radius:(distance p[1] midAC)) catch()
try(s2_AD = geoSphere pos:midAD radius:(distance p[1] midAD)) catch()
try(s2_BC = geoSphere pos:midBC radius:(distance p[2] midBC)) catch()
try(s2_BD = geoSphere pos:midBD radius:(distance p[2] midBD)) catch()
try(s2_CD = geoSphere pos:midCD radius:(distance p[3] midCD)) catch()
-- spheres defined by 3 points
try(s3_ABC = geoSphere pos:centerABC radius:(distance p[1] centerABC)) catch()
try(s3_ABD = geoSphere pos:centerABD radius:(distance p[1] centerABD)) catch()
try(s3_ACD = geoSphere pos:centerACD radius:(distance p[1] centerACD)) catch()
try(s3_BCD = geoSphere pos:centerBCD radius:(distance p[1] centerBCD)) catch()
)
-- get position and radius of spheres
fn getSphereData =
(
s = #(#(), #())
for o in objects where classOf o == geoSphere and o != undefined do
(
append s[1] o.pos
append s[2] o.radius
)
)
fn knuckleBall_Start tgt =
(
-- define initial points
p = #()
for i = 1 to 4 do p[i] = polyOp.getVert tgt i
defineSpheres p
getSphereData()
-- delete spheres with points that fall outside
for a = 1 to s[1].count do
(
format "looking at sphere #%...
" a
for b = 1 to p.count do
(
if distance s[1][a] p[b] - s[2][a] > .0001 do
(
format " point #% (%) falls outside sphere #%
" b p[b] a
isDeleted = false
for o = 1 to objects.count where classOf objects[o] == geoSphere while isDeleted == false do
(
if objects[o].pos == s[1][a] and objects[o].radius == s[2][a] do
(
format " deleting object % (matches sphere #%)
" objects[o] a
delete objects[o]
isDeleted = true
)
) -- end o loop
) -- end if (distance)
) -- end b loop
) -- end a loop
-- delete all but the smallest bounding sphere
getSphereData()
for o = 1 to objects.count where classOf objects[o] == geoSphere do
(
if objects[o].radius != aMin s[2] do delete objects[o]
)
getSphereData()
-- remove redundant points from the array
for a = 1 to s[1].count do
(
for b = 1 to p.count do
(
try
(
if distance s[1][a] p[b] < s[2][a] do deleteItem p b
)
catch(format "NOTE: array item % was NOT deleted
" b[p])
)
)
)
-- continue creating and checking spheres using the remainder of the object's points.
fn knuckleBall_Cont theTarget i =
(
tempPoint = point size:0.1 pos:(polyOp.getVert theTarget i)
append p (polyOp.getVert theTarget i)
defineSpheres p
getSphereData()
-- delete spheres with points that fall outside
for a = 1 to s[1].count do -- for all spheres
(
format "looking at sphere #%...
" a
for b = 1 to p.count do
(
if distance s[1][a] p[b] - s[2][a] > .0001
then
(
format " point #% (%) falls outside sphere
" b p[b]
for o = 1 to objects.count where classOf objects[o] == geoSphere do
(
if objects[o].pos == s[1][a] do
(
format " (deleting sphere #%)
" a
delete objects[o]
)
) -- end o loop
) -- end if/then/else (distance)
) -- end b loop
) -- end a loop
-- delete all but the smallest bounding sphere
getSphereData()
for o = 1 to objects.count where classOf objects[o] == geoSphere do
(
if objects[o].radius != aMin s[2] do delete objects[o]
)
getSphereData()
-- remove redundant points from the array
for a = 1 to s[1].count do
(
for b = 1 to p.count do
(
try
(
if distance s[1][a] p[b] < s[2][a] do deleteItem p b
)
catch (format "item was not deleted
")
) -- end b loop
) -- end a loop
) -- end fn knuckleBall_Cont
rollout RO_knuckleBall "Knuckle Ball"
(
pickbutton pck_Tgt "Pick target" width:100
button btn_Cont "Continue" width:100 enabled:false
global theTarget
global tempPoint
local theLoop = 1
local p
on pck_Tgt picked obj do
(
theTarget = obj
knuckleBall_Start theTarget
btn_Cont.enabled = true
)
on btn_Cont pressed do
(
if tempPoint != undefined and isValidNode tempPoint do
(
tempPoint.size = 0.01
)
knuckleBall_Cont theTarget theLoop
theLoop = theLoop + 1
)
)
createDialog RO_KnuckleBall
Okay, it’s not perfect, but it does a pretty good job, and it’s short and clean compared to my last script.
What I am doing is finding the largest sphere that still touches the object on either 2, or more likely 3, points. (I guess it should technically go up to 4 points, which is probably why I still miss a few vertices occasionally, but I don’t know how to do that).
I found that I was able to cut a lot of useless calculation out by starting with the 2 points furthest from each other as the defining points of the initial sphere, since any enclosing sphere will be at least that size. From there, if the sphere must be enlarged, it will need to
- touch at least one of the points outside the initial sphere, and
- be larger than the initial sphere
-- special thanks to Joel Hewitt (a.k.a. Gravey) for circumcenter function
fn circumcenter p1 p2 p3 =
(
BC = distance p2 p3
CA = distance p3 p1
AB = distance p1 p2
baryCoords = [ (BC^2 * (CA^2 + AB^2 - BC^2)), (CA^2 * (AB^2 + BC^2 - CA^2)), (AB^2 * (BC^2 + CA^2 - AB^2)) ]
triArea = baryCoords.x + baryCoords.y + baryCoords.z
baryCoords /= triArea -- normalize the barycentric coordinates
baryCoords.x * p1 + baryCoords.y * p2 + baryCoords.z * p3
)
struct pointData (id, pos) -- vertex number and position
struct pointPair (pointA, pointB, dist) -- 2 points and their distance from each other
allPoints = #() -- array for all object vertices
for i = 1 to $.numVerts do allPoints[i] = pointData id:i pos:(polyOp.getVert $ i)
-- find the two points that are furthest from each other
farPoints = pointPair dist:0
for i = 1 to allPoints.count do
(
a = allPoints[i]
for j = 1 to $.numVerts do
(
b = allPoints[j]
if distance (a.pos) (b.pos) > farPoints.dist do
(
farPoints.pointA = a
farPoints.pointB = b
farPoints.dist = distance (a.pos) (b.pos)
) -- end if (distance (a.pos) (b.pos))
) -- end j loop
) -- end i loop
-- starting position and radius
sPos = ((farPoints.pointA.pos + farPoints.pointB.pos) / 2)
sRadius = ((distance farPoints.pointA.pos farPoints.pointB.pos) / 2)
theCenter = sPos
theRadius = sRadius
-- find vertices that fall outside the initial hypothetical sphere
outPoints = #()
fn getOutPoints =
(
for i = 1 to allPoints.count do
(
if distance allPoints[i].pos theCenter > theRadius do append outPoints allPoints[i]
)
)
getOutPoints()
-- For every set of 3 points,
-- if the distance between each of the 3 points is larger than the radial hypotenuse of theRadius,
-- find the circumcenter and radius for the 3 points.
-- If the radius of the 3 points is larger than the existing value of theRadius,
-- update the value of theRadius and theCenter
for i = 1 to outPoints.count do
(
a = outPoints[i].pos
for j = 1 to allPoints.count do
(
b = allPoints[j].pos
if distance b a > (theRadius * sqrt 2) do
(
for k = 1 to allPoints.count do
(
c = allPoints[k].pos
if distance c a > (theRadius * sqrt 2) and distance c b > (theRadius * sqrt 2) do
(
circ = circumcenter a b c
r = distance circ a
if r > theRadius do
(
theRadius = r
theCenter = circ
) -- end if (r > theRadius)
) -- end if (distance c)
) -- end k loop
) -- end if (distance b)
) --end j loop
) -- end i loop
The script can be a bit slow on high poly objects. To make it run faster (with the tradeoff that it becomes less reliable), the lines
for i = 1 to outPoints.count do
(
a = outPoints[i].pos
for j = 1 to allPoints.count do
(
b = allPoints[j].pos
can be changed to
for i = 1 to outPoints.count do
(
a = outPoints[i].pos
for j = 1 to outPoints.count do
(
b = outPoints[j].pos
This will cause the script to check only for spheres that touch on at least TWO points outside the initial sphere.