Circle Collision

Become a member of the CGSociety

Connect, Share, and Learn with our Large Growing CG Art Community. It's Free!

THREAD CLOSED
 
Thread Tools Search this Thread Display Modes
  03 March 2013
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.
 
  03 March 2013
Welcome to scripting and to the forum!
Please use CODE tags when posting to make your code readable.
 
  03 March 2013
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.
 
  03 March 2013
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.

 
  03 March 2013
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.
 
  03 March 2013
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
 
  03 March 2013
spaw,
have you seen this my post? http://forums.cgsociety.org/showpos...76&postcount=23
 
  03 March 2013
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
 
  03 March 2013
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.
 
  03 March 2013
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
 
  03 March 2013
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.
 
Thread Closed share thread



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 vBulletin
Copyright 2000 - 2006,
Jelsoft Enterprises Ltd.
Minimize Ads
Forum Jump
Miscellaneous

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


Powered by vBulletin
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.