Celebrate National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# 3D math to calculate position

Posted on 2003-12-10
Medium Priority
892 Views
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.
0
Question by:medjan
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 3
• 3
• 2
• +5

LVL 84

Expert Comment

ID: 9934666
Wouldn't
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?
0

LVL 1

Expert Comment

ID: 10021331
What a strange algorithm! Why are you wanting to do this?
0

LVL 1

Assisted Solution

Maroy earned 200 total points
ID: 10098291
I think ozo has the right idea but not quite the right numbers. But even if his number were correct it would be only 1 solution out 4  equally correct solutions. If you had three objects the number of solutions goes up even higher but there is only one solution if you have 4 objects (all the same size).  My point being that there you wont find a single math formula which can give you all the solutions.

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.

0

LVL 1

Assisted Solution

RageDBL earned 200 total points
ID: 10110028
Well, this is a question that is quite on my level of knowledge.

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
0

LVL 1

Expert Comment

ID: 10112647
Hi 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!
0

LVL 1

Expert Comment

ID: 10136695
True, very true. My solution doesn't necessarily maximize distances between objects. I was trying to make a simple method. The method I came up with may not be completely solid, though. It may have problems for higher numbers of objects, and numbers such as 4, where you have two patterns that the objects could be arranged in. I don't think I made myself entirely clear in the solution either, but it could inspire some ideas that would lead to the solution.
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
0

LVL 1

Expert Comment

ID: 10188562
this problem cannot be (analytically) solved directly
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.
0

LVL 84

Accepted Solution

ozo earned 280 total points
ID: 10188700
Speaking of relaxation, that may not be a bad way to solve your problem.
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?
0

LVL 1

Expert Comment

ID: 10204542
namnoops, if you konw about 'centroidal voronoi diagram' s You ought to dish it out. I'd also very much like to know about it, too.

Oh, 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.

0

LVL 2

Assisted Solution

SWortham earned 120 total points
ID: 10337505
Does this have to happen quickly?  Because I think I could write a program that does this by working with forces in a particle engine.  Every object & wall would have to exert a force or a backwards elasticity effect.  If you write it correctly, each object would eventually come to a resting point where they're spaced out evenly.  And when it's all finally come to rest, you stop the loop and draw your results.

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.
0

LVL 2

Expert Comment

ID: 10337775
Now I'm interested in this too.  I used an old project I have to implement this in a single pass.  No particle engine movement or manipulation was required.

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++;
}
}
}
0

LVL 2

Expert Comment

ID: 10337821
0

Author Comment

ID: 10411911
Thanks everybody for your interesting approaches, ideas and solutions. As I now understand a precise solution in three dimensional space to this problem becomes problematic as the number of objects increase (also varying radii).

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
0

LVL 1

Expert Comment

ID: 10427925
I couldn't begin to suggest the code that is needed to do this, but I do have an observation that I do not see mentioned here. It would seem to me that the code would need to find the largest prime factor of the number of points. The prime number would determine the number of rays leaving the origin and therefore their realtion to each other. Then the other factor of the number of points would determine the number of points on that ray and thier placement. What I am not certain of is how to divide a cube in say 13 sections that all meet at the origin.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of â€¦
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompaâ€¦
Weâ€™ve all felt that sense of false security beforeâ€”locking down external access to a database or component and feeling like weâ€™ve done all we need to do to secure company data. But that feeling is fleeting. Attacks these days can happen in many wâ€¦
###### Suggested Courses
Course of the Month11 days, 14 hours left to enroll