# Circle Collision

 Thread Tools Display Modes
 03 March 2013 spaw Veteran TD/Visual Effects Circle Collision Even though Ive used max since before its initial release I never really spent the time to learn script. I'm ashamed to say it but I'm a newbie if there ever was one. I ve had the good fortune to work with people very adept at creating tools or lived off the good graces of friends when Ive needed something script wise. Anyway, Now im trying to get my head wrapped around it and subsequently, Im trying any number of little tests to learn the simple stuff or get things working that would be hard to do through the normal UI. This circle collision script was a more dynamic version of circle packing. Normally this would be done with dart throwing or something a bit less brute force. In this case its very brute force and hence ugly and slow, but fun all the same. Take a look. https://vimeo.com/60926441 -Michael `````` ---------------------------------------------------------------------------------------- -- Circle Collision -- -- Dynamic Circle packing -- Circles are placed in a domain and then push their neighbors till there are no overlaps -- -- Michael Spaw -- Morphographic.com -- Started 02/05/13 -- ver 0.01 02/08/13 -- -- Here are the steps for the algorithm -- 1. N# of circles are placed randomly within the bounding shape -- and the wirecolor is set to yellow -- 2. For each circle its closest neighbor is found -- 3. Based on the vector between the circle and its closest neighbor the circle -- is moved just a bit in the oposite dirrection -- 4. The neighbor and repulsion setp is looped through till there are no overlaps -- -- Also of note you can see the wirecole change based on if the circle has been moved or is stationary ---------------------------------------------------------------------------------------- -- Setup aqua = (color 87 224 198)--Create a color to be used for the bounding shape drawRad = 3 --the radius of the circles radvary = 0.7 --The amount of variation in the radius of the circles numcircles =200 --Total number of circles created within the test Iterations = 5000 --Total attemps to move the cicrcles so they no longer collide initxpos = 50.0-drawrad --Inital x position for the circle minus some to keep it in the bounding rectangle initypos = 50.0-drawrad --same for the y delete objects--Lets clearout all the objects before we start Rectangle length:100 width:100 pos:[0,0,0] wirecolor:aqua --a nice bounding rectangle for neatness fn blendcolor a b x = ( return ((a) * (1 - (x)) + (b) * (x)) ) blendTime = 10 startColor = red endColor = yellow fn setColor startColor endColor obj blendTime = ( StartColorV = [startColor.r,startColor.g,startColor.b] endColorV = [endColor.r,endColor.g,endColor.b] colorDelta = (StartColorV - endColorV)*(1.0/blendTime) *-1 currentColor = [obj.wirecolor.r,obj.wirecolor.g,obj.wirecolor.b] L = (length (endColorV - currentColor)) if (L > (length colorDelta)) then ( newColor = currentColor + colorDelta obj.wirecolor = (color newColor.x newColor.y newColor.z) ) else ( obj.wirecolor = endColor ) ) --Make some circles in the bounding area Circles= #() for i = 1 to numcircles do ( p = (random [-initxpos,-initypos ,0.0] [initxpos,initypos,0.0]) randRad = drawRad + (random (drawRad*-radvary) (drawRad*radvary)) myCircle = circle pos:p radius:randRad wirecolor:startColor append circles myCircle ) circlescolor= #() for i = 1 to numcircles do ( circleColorVal = 0.0 append circlescolor circleColorVal ) fn findClosestNodes circles obj = ( closestNodes = #() for i=1 to circles.count do ( -- loop through the circles to find any that are within the radius of the circle in question (obj) if obj!=circles[i] do ( --check to make sure we aren't comparing against ourself ( currDist = distance obj.pos circles[i].pos -- get the dist between comparison pairs if (currDist < (obj.radius+circles[i].radius)) do ( -- if the circles overlap, add to the return array append closestNodes circles[i] ) ) ) ) return closestNodes ) --Time for some collision testing and movement for j=1 to iterations do ( noChange = true for i = 1 to circles.count do ( closestCircles = findClosestNodes circles circles[i] if closestCircles.count == 0 do (setColor startColor endColor circles[i] blendTime) for k=1 to closestCircles.count do ( ra = circles[i].radius rb = closestCircles[k].radius rad = ra+rb d = distance closestCircles[k].pos circles[i].pos if (d < rad) do ( noChange = false currentpos = circles[i].pos v = (closestCircles[k].pos - circles[i].pos) * -0.05 circles[i].pos += v newpos = circles[i].pos if (newPos != currentpos) do (circles[i].wirecolor = red) ) ) ) if noChange do ( circles.wirecolor = yellow format "Number of iterations: %\n" j exit ) forceCompleteRedraw() windows.processPostedMessages() )`````` Last edited by spaw : 03 March 2013 at 08:50 AM. share quote
 03 March 2013 lo the frequentest! portfolio Rotem Shiffman Tel Aviv, Israel Welcome to scripting and to the forum! Please use CODE tags when posting to make your code readable. __________________ VFB+ : Advanced Frame Buffer for 3dsmax share quote
 03 March 2013 Swordslayer isKindOf Artist   portfolio Vojtech Cada 3D generalist Czech Republic Had to do a similar thing long long time ago, although I picked the other approach; there were circles the new circles had to avoid colliding with, which as a side-effect allows you to continue running a script on a partially filled area (with or without changing the parameters). It was just one-off thing, no clever solutions to fill all the gaps nor any GUI, everything is set in the first two groups of locals. ``````( --------------------------------------------------------------------------------- -- Private Globals --------------------------------------------------------------------------------- -- nodes local boundary = \$boundary_circle local centerPoint = boundary.pos local boundaryRadius = boundary.radius local innerBounds = selection as array -- existing circles inside the bounding circle clearSelection() -- node settings local max_nodes = 250 + innerBounds.count -- limit of newly created circles local max_size = 2750 -- maximum circle size local min_size = 700 -- initial inserted circle size local min_gap = 150 local min_growth = 10 local max_growth = 50 local min_pos = boundary.min local max_pos = boundary.max -- 2D grid variables local gridData = #() local gridAddress = #() local gridUnit = 2 * (max_size + min_gap) -- collections local list = #() list[max_nodes] = undefined local nodesCount = 0 local liveNodes = #{} --------------------------------------------------------------------------------- -- Structs --------------------------------------------------------------------------------- -- existing circles, their size doesn't change struct staticNode ( index, pos, radius, obj, alive = false, fn updateNode = () ) -- inserted circles struct circleNode ( index, pos, radius = min_size, obj = circle pos:pos radius:radius wirecolor:yellow, alive = true, growth = random min_growth max_growth, fn updateNode = ( if alive do alive = (radius = (obj.radius += growth)) < max_size AND ((distance centerPoint pos) + min_gap + radius) < boundaryRadius liveNodes[index] = alive ) ) --------------------------------------------------------------------------------- -- Functions --------------------------------------------------------------------------------- fn build2DGrid = ( local start = [int(min_pos/gridUnit).x, int(min_pos/gridUnit).y] local end = [int(max_pos/gridUnit).x, int(max_pos/gridUnit).y] for x = start.x to end.x do for y = start.y to end.y do ( append gridAddress (getHashValue [x,y]) append gridData #() ) ) fn get2DGridAddress pos = ( pos /= gridUnit [int(pos.x), int(pos.y)] ) fn getItemsNearPos pos tolerance:1 = ( local items = #() local posAddress = get2DGridAddress pos for x = posAddress.x - tolerance to posAddress.x + tolerance do for y = posAddress.y - tolerance to posAddress.y + tolerance do join items gridData[findItem gridAddress (getHashValue [x,y])] items ) fn circlesCollide pos1 pos2 radius1 radius2 = distance pos1 pos2 < radius1 + radius2 + min_gap fn addNode pos = ( if ((distance centerPoint pos) + min_gap + min_size) < boundaryRadius then ( nodesCount += 1 list[nodesCount] = circleNode index:nodesCount pos:pos true ) else false ) fn addPoints = ( if addNode (random min_pos max_pos) do ( local addedPoint = list[nodesCount] local pointPos = addedPoint.pos local gridPos = get2DGridAddress pointPos local neighbors = getItemsNearPos gridPos -- first get the neighbors -- only after that add the node so we don't test it against itself append gridData[findItem gridAddress (gridPos as string)] addedPoint for item in neighbors while addedPoint.alive where circlesCollide pointPos item.pos min_size item.radius do ( delete addedPoint.obj list[nodesCount] = undefined liveNodes[nodesCount] = false nodesCount -= 1 ) ) ) fn killPoints = for i = 1 to nodesCount do for j = i+1 to nodesCount where (list[i].alive OR list[j].alive) AND circlesCollide list[i].pos list[j].pos list[i].radius (list[j].radius + min_gap) do ( list[i].alive = false list[j].alive = false ) fn updateList = for item in list where item != undefined do item.updateNode() --------------------------------------------------------------------------------- -- Main --------------------------------------------------------------------------------- build2DGrid() clearListener() for bound = 1 to innerBounds.count do ( local obj = innerBounds[bound] local pos = obj.pos local radius = obj.radius local addedNode = staticNode index:bound pos:pos radius:radius obj:obj list[bound] = addedNode local extra_size = if radius > max_size then radius - max_size else 0 local start = get2DGridAddress (pos - extra_size) local end = get2DGridAddress (pos + extra_size) for x = start.x to end.x do for y = start.y to end.y where (local gridIndex = findItem gridAddress ([x,y] as string)) > 0 do append gridData[gridIndex] addedNode nodesCount += 1 ) with undo off, redraw off ( -- continue adding circles till we reach the limit while nodesCount < max_nodes AND NOT keyboard.ESCpressed do ( addPoints() killPoints() updateList() windows.processPostedMessages() pushPrompt ("Remaining to add: " + (max_nodes - nodesCount) as string) ) -- continue growing circles till all are dead while liveNodes.numberSet > 0 AND NOT keyboard.ESCpressed do ( killPoints() updateList() windows.processPostedMessages() pushPrompt ("Remaining to grow: " + (liveNodes.numberSet) as string) ) ) )`````` __________________ Scripts :: linkedin Last edited by Swordslayer : 03 March 2013 at 07:31 AM. share quote
 03 March 2013 spaw Veteran TD/Visual Effects Cool! nice to see another approach. Ill need to dive into it and see what you have going on. Id like to see what could be done about getting collision going with bounding boxes with rotation. https://vimeo.com/39588710 Clovis has a snazzy script here but he has yet to make it public. Id love to hear whats going on under the hood. -Michael Originally Posted by Swordslayer: Had to do a similar thing long long time ago, although I picked the other approach; there were circles the new circles had to avoid colliding with, which as a side-effect allows you to continue running a script on a partially filled area (with or without changing the parameters). It was just one-off thing, no clever solutions to fill all the gaps nor any GUI, everything is set in the first two groups of locals. share quote
 03 March 2013 denisT MAX Doctor   portfolio Denis Trofimov CA, USA you have to understand that yours and Clovis's algorithms are very slow. it might work for ~100 nodes, but not for ~1000. it's much faster generate 'non-intersected' nodes, and find and delete 'intersected' after all. and more... the theory says that is faster to randomly generate nodes wherever than search for 'non-intersected' place for every new one. share quote
 03 March 2013 spaw Veteran TD/Visual Effects Random Points On A Sphere Originally Posted by denisT: you have to understand that yours and Clovis's algorithms are very slow. it might work for ~100 nodes, but not for ~1000. it's much faster generate 'non-intersected' nodes, and find and delete 'intersected' after all. and more... the theory says that is faster to randomly generate nodes wherever than search for 'non-intersected' place for every new one. For sure. Its more for fun than general use though I like the interactivity that clovis has and to be able to save keys. Denis how might I go about adding velocity buffer and actually dampen the jiggle? what other ways could it be made less sloppy? Thanks -Michael share quote
 03 March 2013 denisT MAX Doctor   portfolio Denis Trofimov CA, USA spaw, have you seen this my post? http://forums.cgsociety.org/showpos...76&postcount=23 share quote
 03 March 2013 spaw Veteran TD/Visual Effects Circle Collision Originally Posted by denisT: spaw, have you seen this my post? http://forums.cgsociety.org/showpos...76&postcount=23 Denis- Nifty! but im a bit thick, would you be willing to walk me through what all is going on? Thanks! -Michael share quote
 03 March 2013 denisT MAX Doctor   portfolio Denis Trofimov CA, USA Originally Posted by spaw: Nifty! but im a bit thick, would you be willing to walk me through what all is going on? I'm using 3D grid for fast searching of intersected bboxes (nodes). after I put all my bboxes in 3D grid I exactly know what cells every bbox occupies. and I know all neighbor cells of every cell. So I can search only in the occupied by bbox cells and their neighbors. When I know which bboxes intersect I can do with them whatever I want (delete, move, etc.) as you see in my snippet it takes only 150 ms to find all intersection in 10000 bboxes. using SDK the same algorithm does do the same for less than 30 ms. share quote
 03 March 2013 spaw Veteran TD/Visual Effects circle collision Very fast and cool for a 2d and 3d case but im wondering if you need to specify the number of points as in the sphere question (i.e. a surface ) I have going or even points on a plane. Do you think there is a way to get just the number of points you want if you are using a uniform grid? Thanks -Michael share quote
 03 March 2013 CGTalk Moderation Expert Thread automatically closed This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum. __________________ CGTalk Policy/Legalities Note that as CGTalk Members, you agree to the terms and conditions of using this website. share quote

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts vB code is On Smilies are On [IMG] code is On HTML code is Off CGSociety Society of Digital Artists www.cgsociety.org Powered by vBulletinCopyright ©2000 - 2006, Jelsoft Enterprises Ltd.