# Circle Collision

 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.
Forum Jump
 Please select one User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home -------------------- Gallery     Latest Entries     Featured 2D     Featured 3D     CG Awards     Community Awards Main     News     General Discussion     Off Topic     Recruitment         Temp Job Board Challenges     Rival Crimson X Chaos     Education     Demo Reel     Portfolio Review GROUPS WIP ADVICE     Pro Select     Art Direction and Interviews     New 2D/3D Sketchbooks 2018     WIP 2D/3D & Animation         WIP/Critique: 3D         WIP/Critique: 2D             Speedpaints & Sketchbooks         WIP/Critique: Animation     Partners and Groups         Kitbash 3D Thunderdome         Collaborative Projects Autodesk     Autodesk Maya         Maya Dynamics         Maya Rendering         Maya Character Setup         Maya Programming     Autodesk Miscellaneous         Autodesk MotionBuilder         Autodesk Mudbox         Autodesk Softimage             XSI: Programming             ICE: Interactive Creative Environment     Autodesk 3ds max         3dsMax Tutorials & Tips         3dsMax Resources         3dsMax SDK and MaxScript         Plugins & Add-ons         Particle Flow     Mudbox Featured Gallery ZBrush     Featured Zbrush Gallery     Pixologic ZBrush     Keyshot     Marvelous Designer Texturing     Allegorithmic Substance         Substance Designer         Substance Painter         Substance Featured Gallery     Texturing XYZ     Mari     Marmoset Toolbag Software     Maxon Cinema 4D         Cinema 4D Resources     Side Effects Houdini     Compositing Software         The Foundry Nuke         Adobe After Effects         Autodesk Effects and Compositing         Eyeon Software Digital Fusion     Additional Software         Lightwave 3D             LW Resources             LW Tutorials         The Foundry Modo             The Foundry Time Travel Challenge         E-on Software Vue         Photoshop / Painter         Blender         3DCoat Techniques     Art Techniques and Theories     Digital Matte Painting         Digital Matte Painting Mini-Challenge     Modeling         Modeling Challenge             Member Model Collection     Texturing and Surfacing     Character Rigging     Animation     Lighting and Shaders         Lighting Challenges     Compositing and Editing     Anatomy and Figurative Art         SPOTLIGHT: Best of the Artistic Anatomy and Figurative Art Forum         Tutorials and Workshops         Personal Anatomy & Sketchbook Threads         References, Resources, and Supplies Technical     VR/AR     Master Virtual Reality with BrioVR     Workstation Builds     Game Engine     Graphics Programming     Technical and Hardware CGS Labs     Sketchbooks     Hardcore Crit     Discussions and Meet Ups
Miscellaneous

All times are GMT. The time now is 06:42 AM.