Solved

3D math to calculate position

Posted on 2003-12-10
15
835 Views
Last Modified: 2013-12-26
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
Comment
Question by:medjan
  • 3
  • 3
  • 2
  • +5
15 Comments
 
LVL 84

Expert Comment

by:ozo
Comment Utility
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

by:TimDSmith
Comment Utility
What a strange algorithm! Why are you wanting to do this?
0
 
LVL 1

Assisted Solution

by:Maroy
Maroy earned 50 total points
Comment Utility
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

by:RageDBL
RageDBL earned 50 total points
Comment Utility
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

by:Maroy
Comment Utility
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

by:RageDBL
Comment Utility
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

by:namnoops
Comment Utility
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
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 
LVL 84

Accepted Solution

by:
ozo earned 70 total points
Comment Utility
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

by:RageDBL
Comment Utility
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

by:SWortham
SWortham earned 30 total points
Comment Utility
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

by:SWortham
Comment Utility
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

by:SWortham
Comment Utility
0
 

Author Comment

by:medjan
Comment Utility
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

by:wjcott
Comment Utility
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

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

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 …
Artificial Intelligence comes in many forms, and for game developers, Path-Finding is an important ability for making an NPC (Non-Playable Character) maneuver through terrain.  A* is a particularly easy way to approach it.  I’ll start with the algor…
Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…
Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now