Prepare for the CompTIA Network+ exam by learning how to troubleshoot, configure, and manage both wired and wireless networks.

I don't know much about 3d engines and related math so this might be a simple problem. I need to calculate the position of an object (x,y,z) in a 3D environment depending on the dimensions of the environment and the number of other object already occupying said environment.

I want the objects placed into the environment to have the largest distance between other objects and the edges of the environment. For example, we have an "empty" 3D cube 300 pixels by 300px by 300px. When I place 1 object into the environment it needs to find the position that is furthest away from the edges and other objects. In this case it would be at x=0,y=0,z=0 (assuming the origin is in the center of the cube). If I now place a second object into the environment it should let me know what the position of the 2 object present are. I assume this will be:

object1 x=0,y=0,z=-75

object2 x=0,y=0,z=75

What kind of math do I need to achieve this? Assuming the environment is square or rectangular & objects do not occupy any space.

I would also further be interested to know how this calculation changes when object have a preset size (i.e. two balls, one r=30px the other r=60px). Thank you.

I want the objects placed into the environment to have the largest distance between other objects and the edges of the environment. For example, we have an "empty" 3D cube 300 pixels by 300px by 300px. When I place 1 object into the environment it needs to find the position that is furthest away from the edges and other objects. In this case it would be at x=0,y=0,z=0 (assuming the origin is in the center of the cube). If I now place a second object into the environment it should let me know what the position of the 2 object present are. I assume this will be:

object1 x=0,y=0,z=-75

object2 x=0,y=0,z=75

What kind of math do I need to achieve this? Assuming the environment is square or rectangular & objects do not occupy any space.

I would also further be interested to know how this calculation changes when object have a preset size (i.e. two balls, one r=30px the other r=60px). Thank you.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

As for math try Pythagoras' theorem (in three space) the distance between two points is

sqrt(x^2 + y^2 + z^2). The longest line in your cube is between two of the opposite corners e.g. (-150,-150,-150) to (150,150,150) the length of this line is sqrt(300^2 + 300^2 + 300^2) = approx 520. Now divide the line into 3 segments = approx 173. now reverse Pythagoras' theorem eg sqrt((173^2)/3)) = 100. Use this value to move your starting points in the direction of the origin such that (-50,-50,-50) is one object and (50,50,50) is the other.

It's a good thing that this is a cube. The parameters for your problem were worded for the impossible (because anything in a cube that is farthest from the eight corners, would be the center, and anywhere else would not fit your practical solution.). I'm assuming that what you're trying to do is evenly space all the objects inside the cube. Well, I'll try to explain the concept.

What you need to do, is divide the volume of the cube into equal sections, depending on how many objects are in the cube. The simplest to visualize is for two objects, shown here in figure one, a side view of your cube:

The two objects are in the exact center of each of the sections. The position of a section's object will ALWAYS be the center, for every number of objects.

+---------|---------+

| | |

| | |

| O | O |

| | |

| | |

+---------|---------+

figure one.

This is just one view (front and top). The depth position (z coordinate) of the objects is aligned with the middle of the cube (the same as your first situation of one object). Then, here comes the hard part. If you have 3, your life just got a heck of alot more difficult. You have to somehow divide the cube into 3 equal sections. I recommend splitting it in a 'Y' pattern from the side. Now we seem to think that splitting one side is the way to go, NOT! When you reach 4, it gets more complicated. You need to split the cube from the center into four interlocking pyramids. This seems simple, but the 5 is even harder. But we know that 2 plus 3 is 5, so just divide it in 2, place objects, then divide the cube by 3 ('Y' pattern), then place objects. I'm not sure, but I think you might be able to do this by just splitting things by '|' ( divide by 2 ) and 'Y' ( divide by 3 ). This might work, but I made it up on the fly, so you'll have to try it yourself. You may find more patterns to divide it by. You might also have the problem of some objects haveing the same coordinates. Beware of this. This is where my idea might find fault.

If you get this, but don't know the math, well, you could try something with sin (angle) *radius for y and cos (angle) *radius for x. But I have the feeling you're gonna need to do some line intersection, which isn't too hard. Just remember, to find the center between any given points, just get their mean (I mean average, surely you know what that is).

I hope this helps. I made it up on the fly, but I've been doing 3D programming long enough for you to be right in giving it a try.

Thanx

RageDBL

If you look at your diagram, would'nt you agree that if you increased the radius of the O (without changing their position) untill they touched a wall, then the left and right walls would be touched before the top and

bottom walls? If fact using your solution would'nt the maximum radius be 75 units?

My solution allows for a maximum radius of 86.6 units, which is the distance to origin from (50,50,50) Note that my solution does not maximize the distances either, the nearest wall from (50,50,50) is 100 units away. That means the real solution is closer to (55,55,55) but who wants to solve the differential equation 8-(

Three points define a plane, hence the solution for 3 objects would be to first finding the largest plane that would fit in the cube and then position the thee objects on that plane The plane in question here would not be a simple bisecting plane (e.g. it would not be orthogonal to any axis). This is the same logic I used for two point - two point form a line, Once you fine the longest line that can be made in the cube then the two object must be positioned on that line. If you position the two objects any other way then the length of the line (from a wall through the two objects and on to the next wall) will be shorter and hence the solution will not be maximized.

In any case your solution provides a method to approximate positioning using a programmatically simple methodology. If it were me I would change the problem to make the object fit inside a sphere!

When I formulated this solution, I intentionally did not consider object radius because the questioner wanted to know how to position the objects before considering radius. Either way the radius of each object would be proportional to the number of objects in the cube.

I think that if we combined our methods, we could very well have the solution. You just need to be a little more clear in your expainations; I didn't exactly follow every word.

I didn't mention another method that would make the problem simpler to solve. It doesn't work for numbers like 3 objects, though. It only works for multiples of 4. You just divide the volume into 4 smaller cubes for each step. This would give you numbers like 1 object, 4 objects, 16 objects, then 256 objects. This is a very simple method to follow, but it doesn't exactly fit the desired solution. If it isn't significant whether you can have numbers other than multiples of 4, it would be a good idea to use this method.

RageDBL

from what i understand, youre looking for the solution to a 3D centroidal voronoi diagram.

it means that you want a minimum energy solution.

in 2D its relatively simple, but in 3D, its a whole different story.

i would try to relax your demands a little.

If you simulate particles in a box that repel their closest neighbors and the sides of the box,

and shake the box until they settle in a stable solution, would that meet your requirements?

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialOh, yess, ozo!! Relaxed demands would be good right now, but your solution is quite interesting. You repel the walls from each other, then you repel objects?, interesting, but it only might work for concave arrangements (no objects are closer to the center). Which leaves us right back where we started. Still, look into it. That solution might not be as dead as I thought it was. It actually might be it!!

It might not line up with what was said before about the maximum effect.

Still, I'm VERY interested in this 'centroidal voronoi diagram' thing. Please, tell us more!!

RageDBL --- yes, math does intrigue me.

Check out my tutorial here...

http://www.gldomain.com/tutorials/Gravity-Momentum.htm

It'll show you how elasticity, gravity, & momentum can be simulated in a program. Hopefully this will give you some ideas.

This isn't exactly what you wanted, but I'm sure you could improve upon it...

int loop = 0;

float cube = 5; // 5x5x5 cube

float dist = sqrt(cube*cube + cube*cube + cube*cube) / pow(MAX_PARTICLES, .33333333333);

int loopx, loopy, loopz;

int maxLoop = pow(MAX_PARTICLES, .33333333333);

for (loopx=0; loopx < maxLoop; loopx++)

{

for (loopy=0; loopy < maxLoop; loopy++)

{

for (loopz=0; loopz < maxLoop; loopz++)

{

particle[loop].x = (loopx - maxLoop*.5) * dist; // Set X position

particle[loop].y = (loopy - maxLoop*.5) * dist; // Set Y position

particle[loop].z = (loopz - maxLoop*.5) * dist; // Set Z position

loop++;

}

}

}

http://www.gldomain.com/pics/Various/EvenlySpacedParticleCube.jpg

As I needed this problem solved for a visualization project, I believe the idea of relaxation will provide the best solution. My next step will be to write sample code but with that I have some experience.

I’m splitting the points as there could be multiple solutions. Not fully understanding the problem prohibited me from formulating a narrower question.

medjan

Game Programming

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

object1 x=33.6,y=33.6,z=33.6

object2 x=-33.6,y=-33.6,z=-33.6

be furthur away from the walls and each other?