Sign in to follow this  
vic2005

Polyhedral Equation Exist?

Recommended Posts

vic2005    122
Do there exist some Polyhedral Equation? (Tetrahedron,Cube,Octahedron,Dodecahedron,Icosahedron equation) If i have the rotation of them, can i find the coordinate of their point(which is ROTATED)? That means if i provide the x and y coordinate and the 3 axis angles, can i get z coordinate back? If this equation do not exist, how can i do it? [Edited by - vic2005 on March 22, 2008 5:23:13 AM]

Share this post


Link to post
Share on other sites
Emergent    982
Let me make sure I understand what you're looking for correctly: You would like a function, which takes x and y screen/pixel coordinates and yaw/pitch/roll angles as arguments, and returns the z coordinate (distance from camera) to the polyhedron if it is "at" this pixel (and otherwise, returns something else; perhaps a negative number.)

A simple, closed-form expression for such a function does not exist.

I think you need to break your problem down into three parts:
1 - Generating the polyhedron geometry.
2 - Rotating the polyhedron geometry.
3 - Rendering the polyhedron geometry.

I will also assume that you are interested in convex, regular polyhedra.

There are two basic approaches I see, and which one you choose will affect how you do both #1 and #3 above (#2 will be roughly the same no matter what you do.)

Planes

The first approach is to represent the polyhedron by a number of planes -- specifically, by a BSP tree. The idea is this: If you have a polyhedron with n faces, consider the set of n oriented planes such that each plane contains one of the polyhedron's faces. (By "oriented," I mean that each plane has a front and a back; you can represent this by the direction of the plane's normal.) Then, a point is contained within the polyhedron if and only if it is behind each of these n planes. Thus, you can represent your polyhedron as a collection of planes in a BSP tree.

Then, to determine the "z coordinate" of your polyhedron at a given pixel point, what you really want to do is cast an "eye ray" out, and see if it intersects the polyhedron, and where. There exist fast ray-intersection tests for BSP trees.

Triangles

The second approach is to represent your polyhedron as a collection of triangles. This makes generating the polyhedron more difficult, I think, but rendering more compatible with modern hardware. I think the easiest way to deal with this is not very elegant: Just hard-code models of each of these shapes into your code, or load them from files.

I assume you want to evaluate your function on a fixed grid? Then just rasterize your triangles. Since these are convex polyhedra, the simple painter's algorithm will work fine. Or just use OpenGL/DirectX to do your work for you.

Rotation

This is the easiest part. If you represent your polyhedron by a collection of planes, just multiply each plane's normal and offset by a rotation matrix. (Or equivalently, cast your rays from a different point.) If you represent your polyhedron by a collection of triangles, just multiply each vertex by a rotation matrix.

You say you'd like to specify 3 Euler rotation angles. Well, your overall rotation matrix will then just be the product of three simpler rotation matrices -- one about the x axis, one about the y axis, and one about the z axis. The Wikipedia article will tell you everything you need to know about that: http://en.wikipedia.org/wiki/Euler_angles

Hope that helps.

Share this post


Link to post
Share on other sites
Emergent    982
Quote:
Original post by Emergent
The first approach is to represent the polyhedron by a number of planes -- specifically, by a BSP tree.


More on this:

For the case of convex polyhedra, your "BSP tree" isn't much of a tree at all -- more of list, really. In any event, let's keep referring to it as a tree -- because it is a tree, albeit a degenerate tree. :-)

Let's say that we do our rotations using the "move the camera" method. We are casting a ray from our camera in a direction given by x and y, as well as the Euler angles.

To start, figure out what region in space your camera is in. To do this, start at the root of your BSP tree and ask, "Is the camera on the 'inside' side of this plane?" If the answer is "yes," move to the next plane and ask, "is the camera 'inside' this plane?" Do this until you find a plane that the camera is on the "outside" side of.

Now, you intersect the ray against this plane to get a point. Is this point inside this plane's child plane? If so, continue; is it inside the child's child plane? Keep doing this until you find a plane that the point is not inside of, or you reach the leaves of the tree (in which case, (a) this point is the intersection, if it is inside the leaf plane, or (b) there is no intersection, if it is outside the leaf plane). If the point is not inside the current plane, then intersect the ray with the current plane; you are now testing this new point against all of the current plane's children. Again, when you get to the leaves of the tree, you've found your intersection, if it exists.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this