PDA

View Full Version : Create Random Spheres without intersection


BrVB
04-05-2008, 09:43 AM
Can anyone help me with this issue? The only solution I found right now is to use a grid but that's something I don't want to use for this specific problem, I tried to make an array with all sphere's and everytime he draws a new one he calculates distance to the whole array but that doesn't work, I think it's because I'm quite new to scripting

BrVB
04-05-2008, 03:10 PM
Ok I did make something that solves the problem but it's probably a strange piece of scripting but it works, or sometimes it works, it's very slow and it can get into a loop
ArrPoints=#()
ArrDistance=#()
rollout rolCreaterandom "Create Random" width:164 height:220
(
GroupBox grp1 "Area" pos:[10,10] width:144 height:71
spinner InpSide01 "Side 01" pos:[23,33] width:120 height:16 range:[0,10000,100]
spinner InpSide02 "Side 02" pos:[23,55] width:120 height:16 range:[0,10000,200]
GroupBox grp7 "Points" pos:[10,90] width:144 height:72
spinner InpPoints "Number" pos:[23,110] width:120 height:16 range:[0,10000,10] type:#integer scale:1
spinner InpDistance "Distance" pos:[23,133] width:120 height:16 range:[0,10000,1]
button btn1 "Create" pos:[41,174] width:82 height:18
button btn2 "Hide" pos:[41,195] width:82 height:18
on btn1 pressed do
(
local
HlpPlane = plane length:InpSide01.value width:InpSide02.value wirecolor:blue
while ArrPoints.count != InpPoints.value do
(
FnPoints InpSide01.value InpSide02.value InpDistance.value
)
)
on btn2 pressed do

FnHideIt(HlpPlane)

)

CreateDialog RolCreateRandom

HlpV01 = 1

HlpV02 = 1

fn FnHideIt n = (hide n)

fn FnPoints l m n =

(

R01 = (random (m/-2) (m/2))

R02 = (random (l/-2) (l/2))

HlpPoint = sphere radius:n pos:[R01,R02,0] wirecolor:white

if arrPoints.count != 0 then

(

FnCollision HlpPoint.pos n

if ArrDistance[1] == 0 then

(

delete HlpPoint

print ("delete")

)

else

(

append ArrPoints HlpPoint.pos

HlpPoint.name = uniqueName "HlpPoint"

)

)

else

(

append ArrPoints HlpPoint.pos

HlpPoint.name = uniqueName "HlpPoint"

)

)

fn FnCollision m n =

(for j = 1 to j = ArrPoints.count do

(

FnDistance ArrPoints[j] m n

print (FnDistance ArrPoints[j] m n)

append ArrDistance (FnDistance ArrPoints[j] m n)

sort ArrDistance

)

)

fn FnDistance l m n =

(

if

(

(distance l m)/2 < n

)



then 0 else

(

1

print (Distance l m)

)

)

ZeBoxx2
04-07-2008, 01:07 PM
I wrote a script once that does this sort of thing based on surfaces, volumes, etc.... for thousands of spheres, it can be slow; you'd probably want to build some manner of acceleration grid yourself - or see if you can find somebody to write you an octree or kd-tree acceleration grid to store the points in; finding the nearest point in those is extremely fast.


The process is essentially just two steps, though...
1. Generate a position

2. Check if this random position is one of:
A. Too close to another sphere (i.e. if you did create a new sphere, its minimum radius would intersect with another sphere) -> don't create a new sphere
B. Too far away from another sphere (i.e. if you did create a new sphere, even its maximum radius would not 'touch' another sphere) -> creating the sphere here depends on your desires (if you don't, it will 'grow' a model of spheres based on the first sphere, every new sphere always touching a previously created one)
C. The closest other sphere is in the sweet spot of being at a distance between your spheres' mimimum and maximum radius -> create the new sphere

The best way to check for these distances is to first record the position of every sphere you create in an array, then get the distance between your randomly generated position and every position in the array, and perform the above tests. Note that if you have 1,000 positions recorded and the 7th position already falls into category A (too close), you don't have to loop over the remaining 993.. that already speeds things up a slight bit.

Another few small bits that will speed things up are:
1. Always name the objects you create explcitly.. i.e.
sphere pos:myPos radius:myRadius name:"pre-generated name"
That way MaxScript won't have to try and find a new unique name each time you create a node.

2. Consider using points instead of spheres. If you use points, you can set the .size parameter as a substitute for the spheres' radius. Points take up way less memory, and viewport redraw time, than spheres. You can easily replace all points with spheres later by looping over them and creating new spheres with their radius set to the point's size values.

3. Use a mimimum and a maximum radius instead of a fixed radius. This isn't so much a speed-up tip as a "your code will loop nearly forever if you don't...". Imagine a sphere at [0,0,0] with radius 10. Now let's say you generate a bunch of random positions... the odds that such a random position is always -exactly- 10 units away from [0,0,0] are extremely small; the only reason it sometimes works is because of max's relatively low accuracy. So if you have a new position [0,0,10.001], that wouldn't generate a new sphere. So you may wish to have, say, a minimum radius 9 and a maximum radius 11.

4. If you do need a fixed radius, consider generating positions not at random, but based on previous sphere's positions. I.e. per the previous example, take the position [0,0,0], and generate a new position that's 10 units away from that in a random direction. Then all you have to test for is situation A; whether or not that new position intersects with another sphere. You already know it'll be at the correct distance, so situations B and C can be ignored.

My scripts couldn't use option 4 because things like mesh topolgy and particles' positions drove the position generation, any new position I'd generate myself would have to be tested against such topology/the particle system which would be much slower than brute forcing it (until a later stage, at which point nearly all positions generated would hit scenario A, but at that point the generated spheres tend to be aplenty anyway).

I hope this helps a little

davestewart
04-08-2008, 09:58 AM
Cool thread!
I don't know if shrinking new sphere until they no-longer intersect would be an efficient option, but I thought it worth suggesting.

Here's another interesting take on the problem in 2D: http://levitated.net/daily/levEmotionFractal.html

ZeBoxx2
04-08-2008, 12:21 PM
Cool thread!
I don't know if shrinking new sphere until they no-longer intersect would be an efficient option, but I thought it worth suggesting.
That's actually where the minimum Radius and maximum Radius come in.

Rather than taking a Radius and checking if it fits - and if it doesn't, shrink it by 1 and testing again, just check if the distance from 'Point A' (generated 'random' position) to Point B (a position with a sphere) minus the radius of the sphere at Point B is in the interval minRadius < (distance - existingRadius) < maxRadius.

If you set minRadius to a very small value, then the space you're trying to fill with spheres will very quickly end up having tiny little spheres throughout. A 'better' strategy is to have a minRadius and a maxRadius close to eachother and only decrease minRadius if you've failed to place a new sphere (due to intersections/etc.) N number of times. That way you always place larger spheres first and then work down to smaller spheres.
That is, if that's what you want at all :)

BrVB
04-08-2008, 04:06 PM
With the very good help from the replys I rewrote the script, made it a lot faster too
but I just needed sphere's with same radius and no intersection.

(
HlpPlane = plane length:InpSide01.value width:InpSide02.value wirecolor:blue
for k=1 to k = InpPoints.value do
(
l = InpSide01.value
m = InpSide02.value
n = InpDistance.value
R01 = (random (m/-2) (m/2))
R02 = (random (l/-2) (l/2))
HlpPos = [R01,R02,0]
if ArrPoints.count != 0 then
(
for j = 1 to j = ArrPoints.count do
(
if (Distance ArrPoints[j] HlpPos/2) < n then
(exit())
else
(if j == arrpoints.count then append ArrPoints HlpPos)
)
)
else append ArrPoints HlpPos
)
for i = 1 to i = ArrPoints.count do
HlpPoint = sphere radius:InpDistance.value pos:Arrpoints[i] wirecolor:white Name:"HlpPoint"

)

CGTalk Moderation
04-08-2008, 04:06 PM
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.