Okay, I've been competely unable to find a Maxscript for finding an object's minumim enclosing sphere (bounding sphere), so I'm trying to write my own.
The basic concept is:
1) Start with the first few points of an object
2) Make spheres based on their positions (i.e. either from between 2 points, or at the circumcenter of a triangle formed by 3 points).
3) Keep the smallest sphere that still includes all of the checked points, delete the rest.
4) Ignore points that do not reach as far out as that smallest sphere (i.e. ones well within the boundaries), then add the next point to be checked
5) Repeat from step 2
Unfortunately, I seem to be having a hard time putting this into practice. My attempts so far have brought me up to the following. I have some code in there to output debugging data to the listener, and don't understand why the code is allowing certain things to happen.
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 #%...\n" 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 #%\n" 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 #%)\n\n" 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\n" 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 #%...\n" 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\n" 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 #%)\n" 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\n")
) -- 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
AndyOakley · 2009-07-02
Anubis · 2009-06-26
real08121985 · 2009-06-26
