[Closed] Random position on surface

I’ve been kind of curious about this as well, and it looks like I was on target with the approach I had in mind (though haven’t tried yet). Looking forward to an example.

A similar one I’d be interested in is closest point on surface (like in box3) but I can start a new thread for that!

Here is one possible implementation (there might be better / faster ones):

fn GenerateRandomPointsOnSurface theObj PointCount =
 (
 	local st = timestamp() --get the start time
 	seed 12345 --set the random seed to a static number to get the same distribution each run
 	local theMesh = snapshotasMesh theObj --snapshot the TriMesh of the object
 	local theCount = theMesh.numfaces --get the number of faces in the TriMesh
 
 	local theArea = 0 --init. a variable to hold the count.
 
 	for f = 1 to theCount do theArea += meshop.getFaceArea theMesh f --collect the area of the mesh
 	local ObjectsPerArea = PointCount / theArea  --calculate the objects per square unit
 
 	local theIndices = for f = 1 to theCount collect f --collect the indices of the faces
 	local theRandomIndices = #() --init. an array to collect them randomly
 	while theIndices.count > 0 do --repeat until there are no indices left
 	(
 		theIndex = random 1 theIndices.count --pick a random face from the list
 		append theRandomIndices theIndices[theIndex] --add to the random list
 		deleteItem theIndices theIndex --and delete from the original list
 	)
 	 
 	local thePositions = #() --init. an array for the positions to return
 	thePositions[PointCount] = undefined --set the size of the array
 	local cnt = 0 --initialize a counter of the created points
 	for f in theRandomIndices while cnt < PointCount do --loop through the random faces until the count is reached
 	( 
 		local theFace = getFace theMesh f --get the face def. of the random face
 		local theFactor = ceil ((meshop.getFaceArea theMesh f)*ObjectsPerArea) --calculate the points for the face, at least one.
 		for i = 1 to theFactor while cnt < PointCount do --loop from 1 to the number of points on the face
 		(
 			cnt += 1 --increase the index
 			local theX = random 0.0 1.0 --get a random X
 			local theY = random 0.0 1.0 --get a random Y
 			if theX+theY > 1.0 do  --if the sum is greater than 1, subtract them from 1.0
 			(
 				theX = 1.0 - theX
 				theY = 1.0 - theY						
 			)
 			local theZ = 1.0 - theX - theY --the third bary coord is 1.0 minus the other two
 			--store the position in the array
 			thePositions[cnt] = ((getVert theMesh theFace.x)*theX + (getVert theMesh theFace.y)*theY + (getVert theMesh theFace.z)*theZ)
 		)--end i loop
 	)--end f loop
 	delete theMesh --free the memory from the TriMesh
 	format "Time: % ms
" (timestamp()-st) --report the time
 	thePositions --return the array
 )
 
 GenerateRandomPointsOnSurface $Plane01 1000000

When using a plane that has more faces than the number of points requested, one would have to make sure the faces used will be picked randomly. There are several approaches to solving this, the way I approached was randomizing the list of faces and creating points until the desired number was reached. Not using random faces could cause just a portion of the plane to be covered while the rest of the faces remaining empty.

If the number of faces is less than the desired number of objects, since we calculate the points per face and round up using Ceil(), we get at least one point per processed face, and if 1.2 points are requested for the face, 2 points will be generated, thus generally exceeding the number of requested points before we run out of faces.

I had another test where I sorted the faces by size and started with the largest one, but in a plane with noise, this leads to objects on the slopes where the faces are stretched, while leaving large areas empty.

On my machine, creating 1,000 points on a plane with 20×20 segments took 34 ms, 10,000 took 618 ms, 100,000 took 640 ms, 1,000,000 took 6957 ms.

Using a plane with 100×100 segments, 1M points took 25908 ms.

Note that I had to optimize the array growing by pre-initializing the size to the desired number and assign by index instead of just appending to it. When I was appending 1 million times, growing the array in memory via append() caused severe slowdowns due to the HeapSize being increased automatically.

That is powerfull … now i think i got it better… but still lots of fog in my mind ))

But it’s posible to get normal direction of faces and set them to random_objects… like it does testIntersectRay.dir …?

And how will be more accurate and fast to display only 10% of objects distributed on surface? what i’m thinking it’s to cut down 90% of obj_count.value but when rendering starts to switch back and recalculate the full amount of random_objects.
Or just to replace objects with some dummy that use object boundingbox size as his size to correctly preview scale amount, and when it comes the render time just to replace dummy with original objects…?

My first version of this script actually created teapots aligned to the surface normals, but then I read you wanted an array of points, so I changed it

Just change the following line in the function and you will get the same as IntersectRay:

thePositions[cnt] = Ray ((getVert theMesh theFace.x)*theX + (getVert theMesh theFace.y)*theY + (getVert theMesh theFace.z)*theZ)  (getFaceNormal theMesh f)
 

This will give you an array of Rays with position and normal direction. But other than IntersectRay, it will use the FACE normal and not the smoothed one. To get the smoothed normal, you would have to get the face’s vertex normals and interpolate them via the barycentric coordinates just like I did with the positions, but that wouldn’t take into account smoothing groups. You could support smoothing groups, but it would get too complicated. If your mesh is dense enough, you will barely notice the difference.

As for every nth, keep in mind that 10K Helpers are WORSE for Max viewports performance than 10K meshes (strange, but true). One thing you could do is run a pre-render script that creates the full set of objects. For viewport display, you could make 1% or 10% and attach to a single mesh (which is much faster than 10K single objects) and uncheck the Renderable property of the node to use it in the viewports only. When the renderer is called, your function would be called to make the full renderable set, then in a post-render callback function, you could delete them again. See the example in the MAXScript Reference under “How To … Change Objects At Render Time”. Keep in mind you can create and delete geometry only in a #preRender callback and not #preRenderFrame callback, so you cannot add objects to a frame of a sequence, only before the whole sequence begins.

Thanks again BOBO, after lots of testing i see that to achieve full covered surface with 10k objects you will find by 4 or 5 objects in the same position, soo it’s any method to delete closest object from array by radius or something like simple collision… or best will be if before rays are traced to determine space between them?
for instance to use target object boundingbox size with some offset… the objects may be close to eachother but not in the same position… that will simplify the result a lot.

i’m just an novice in maxscript so sorry for my question and my english

Well, the object placement uses random points on the face, and random means “anywhere”. It is possible to do basic bounding box intersection tests (or more complex ones) while placing the object, but you will have to perform the creation inside the Ray generation code and keep on trying until you either find a place on the face where the object does not intersect with others or (after a number of attempts, like 100 or so) stop trying and move on to the next face.
MAXScript has a function called intersects() which takes two objects and checks whether their bounding boxes intersect. But you will have to perform that test with all already created objects, or keep some sort of acceleration structure to be able to find the closest ones to a point (which isn’t the simplest thing to do if you are novice in MAXScript). So it will get a lot slower.
Another method would be the “bounding sphere” approach which is simpler – just take the distance from the .center of the object to its .max property as the radius of the bounding sphere and then check whether the distance from .center to .center of two objects is greater than sum of their bounding sphere radii. But this approach will cause larger distances between objects than the bounding box approach.

A possible “simple” acceleration approach would be to collect an array of all distances from the current object’s center to all other objects’ centers, then perform an indexed qsort to get the closest objects in the beginning of the array. Then loop through the array until the distance value becomes higher than the sum of the two bounding spheres (any objects further in the array will be guaranteed to be farther than that and can be skipped).

If I can find a minute, I might write an example, but keep in mind this is getting into intermediate territory…

Ok, here is an example that performs intersects() check against all existing objects using brute-force loop without any acceleration.

fn GenerateRandomPointsOnSurface theObj PointCount useIntersection:true numAttempts:10 =
  (
  	delete $Teapot* --delete previous teapots (remove if you are not making teapots)
  	local st = timestamp() --get the start time
  	seed 12345 --set the random seed to a static number to get the same distribution each run
  	local theMesh = snapshotasMesh theObj --snapshot the TriMesh of the object
  	local theCount = theMesh.numfaces --get the number of faces in the TriMesh
  	local theNewObjectsArray = #() --init. an array for the objects to create
  	local theArea = 0 --init. a variable to hold the count.
  
  	for f = 1 to theCount do theArea += meshop.getFaceArea theMesh f --collect the area of the mesh
  	local ObjectsPerArea = PointCount / theArea  --calculate the objects per square unit
  
  	local theIndices = for f = 1 to theCount collect f --collect the indices of the faces
  	local theRandomIndices = #() --init. an array to collect them randomly
  	while theIndices.count > 0 do --repeat until there are no indices left
  	(
  		theIndex = random 1 theIndices.count --pick a random face from the list
  		append theRandomIndices theIndices[theIndex] --add to the random list
  		deleteItem theIndices theIndex --and delete from the original list
  	)
  	 
  	local cnt = 0 --initialize a counter of the created points
  	for f in theRandomIndices while cnt < PointCount do --loop through the random faces until the count is reached
  	( 
  		local theFace = getFace theMesh f --get the face def. of the random face
  		local theFactor = ceil ((meshop.getFaceArea theMesh f)*ObjectsPerArea) --calculate the points for the face, at least one.
  		local theVert1 = (getVert theMesh theFace.x) --get the first vertex' position
  		local theVert2 = (getVert theMesh theFace.y) --get the second vertex' position
  		local theVert3 = (getVert theMesh theFace.z) --get the third vertex' position
  		for i = 1 to theFactor while cnt < PointCount do --loop from 1 to the number of points on the face
  		(
  			local theNewObj = teapot radius:(random 2.0 5.0) wirecolor:red --create a teapot with random radius
  			theNewObj.transform = matrixFromNormal (getFaceNormal theMesh f) --set TM based on normal
  			local positionNotValid = true --raise a flag that the position is not valid yet
  			for attempts = 1 to numAttempts while positionNotValid do --repeat until position is valid or max. attempts have been made
  			(
  				local theX = random 0.0 1.0 --get a random X
  				local theY = random 0.0 1.0 --get a random Y
  				if theX+theY > 1.0 do  --if the sum is greater than 1, subtract them from 1.0
  				(
  					theX = 1.0 - theX
  					theY = 1.0 - theY						
  				)
  				local theZ = 1.0 - theX - theY --the third bary coord is 1.0 minus the other two
  				theNewObj.pos = (theVert1*theX + theVert2*theY + theVert3*theZ) --set position using barycentric coords.
  				--if no intersection is requested, or if there is no intersection with existing objects,
  				if not useIntersection or (for o in theNewObjectsArray where intersects  theNewObj o collect o).count == 0 do
  				(
  					append theNewObjectsArray theNewObj --add the new object to the array
  					cnt += 1 --increase the index
  					positionNotValid = false --lower the flag to stop iterating
  				)
  			)--end attempts loop
  			if positionNotValid do delete theNewObj --if all attempts failed due to intersections, delete the object
  		)--end i loop
  	)--end f loop
  	delete theMesh --free the memory from the TriMesh
  	format "Time: % ms
" (timestamp()-st) --report the time
  	cnt --returns number of created objects
  )
  
  GenerateRandomPointsOnSurface $Plane01 1000 useIntersection:true numAttempts:10
  

You can use the function for both kinds of placement.
When useIntersection:false, the specified number of objects will be created without checking for intersections.
When useIntersection:true, intersections with existing objects will be checked and numAttempts attempts will be made to find a position on the face where there is no intersection (usually if the first attempt failed, the next attempts will also fail so that number can be relatively low, unless the faces on the target mesh are very large and generating a new random position could create a vastly different result). Increasing numAttempts will affect performance a lot. Set it to 1 to perform only 1 attempt and skip if it was intersecting for fastest performance.

Here are some results:

Plane with 20×20 segments and Noise modifier.
1000 teapots with random radii between 2 and 5 without intersection test took 369 ms:

With intersection check on and 10 iterations, it took 3125 ms and created only 112 objects:

Using numAttempts:1, it took 1406 ms and created only 89 teapots:

The placement will change when changing the parameters because the number of random() calls will be different. Calling the function with the SAME parameters should produce the same distribution based on the seed() value.

You could change the code to also randomize or even reduce the radius (size) of the objects between attempts if that is an option.

EDIT: Putting the whole function code inside a WITH UNDO OFF() context reduces the time with 10 iterations to 2836 ms because the deleting of objects in the failed attempts won’t create undo records which is slow and memory consuming.

Here is a quick illustration of what happens when the target mesh has faces with varying area. I took a plane with 2×2 segments and tessellated some of its faces to created smaller and smaller faces in the one corner.

But when you distribute randomly on this surface, the whole plane is covered relatively uniformly due to the area calculations performed by the script:

I tested the Position Object operator in PFlow and it acts the same (more or less).
In fact, I would have used a PFlow system for object distribution instead of scripting my own solution. Not that I have anything against scripting…

i’m impressed to be true of maxscript power…
that is a very very nice result, mine test with intersect ray are extremly slow…

at least i have now a good example to learn of.

But strange how does Hair And Fur modifier calculate so many random points in 1 second, any chance to spread objects on surface with the same speed, almost in realtime? for example if i work in viewport with 100 instances that is ok, but when i need to render, have to run script again with lots of instances, 10k in boundingbox preview mode takes more then 10 minutes and sometimes process crash max, maybe its my machine, but anyway comapring with all scatters like FinalRenderScatteringSystem or VrayScatter the process is almost instantly, is it because SDK give more abilities or I just folow wrong rabbit?