Trying to find a bounding sphere.. doing something wrong, but can't figure out what

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

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
real08121985's picture

Mhh.. this bounding sphere

Mhh.. this bounding sphere thing is a cool problem, nice thing to talk about. Currently I'm preparing for some exams, otherwise I would start some scripttests too :( So lets think about this:

You check if 1 vert is outside of the sphere by taking the spherecenter and the vertposition and compare the distance of these 2 points to the sphereradius.

Ok, your result is the vert is sticking outside of the sphere, so now you have to correct the position of your sphere to try to bring the vert inside of the sphere again.

You can move up, down, left, right, back, forth. Try each of these directions. While moving your sphere you have to check that caused by your moving no other vert will stick outside.

The whole movement and sphereshrinking should be done in those stepvalues: 10.0 , 1.0 , 0.1 , 0.01 to approximate the closest sphere and not wasting time with to low stepvalues.

Malkalypse's picture

What's your major? Is it a

What's your major? Is it a related field, or is this just something you do for fun? :)

real08121985's picture

So you want to have the

So you want to have the minimum enclosing sphere.

Maybe creating a sphere like I did before, with the help of the bounding box. Then shrinking the sphere step by step and check if its intersecting with the object and adjusting the position of the sphere. Would be an attempt to find a solution from outside of the object .. an approximation,  what do you think about this?

Malkalypse's picture

I'd considered that

I'd considered that actually, and it would certainly be a good enough solution for my needs. The only problem is, while shrinking the sphere step by step would be easy enough, I'm not sure what to do about adjusting the position.

Anubis's picture

Maybe using only 2 spheres

Maybe using only 2 spheres properties - center and radius, will give you more simple way to achieve bounding sphere calculations.

my recent MAXScripts RSS (archive here)

Malkalypse's picture

Those are the only

Those are the only properties I am using :O

real08121985's picture

I don't know if this is what

I don't know if this is what you're looking for :)

(
	try destroyDialog rlBoundingSphere catch()
	global rlBoundingSphere = rollout rlBoundingSphere "Bounding Sphere" (
		-- controls
			button butStart "Start"
		-- functions
			fn fnCreateBoundingSpheres = (
				for Obj in selection do (
					local fSphereRadius = distance Obj.center Obj.max
					local SphereObj = sphere pos:Obj.center radius:fSphereRadius
				)
			)
		-- events
			on butStart pressed do fnCreateBoundingSpheres()
	)
	createDialog rlBoundingSphere
)
Malkalypse's picture

Unfortunately, no. When I

Unfortunately, no. When I initially started I hoped there might be a solution that simple, but there is not. Trying to use and object's bounding box works fine as long as the object is, well, a box. Otherwise, well, you can see below:

This is apparently a problem that has been attacked in a lot of different ways, particularly in the game industry, but so far there don't seem to be any MaxScript solutions for it.

For more information, check here: http://www.gamedev.net/reference/articles/article2484.asp

 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.