Framing 3d objects
Today I ran into some code in Spore that has to do with framing pictures of creations. The problem is this: given some object created by the user, come up with a camera which takes a picture of that object.
The code worked by placing the object in front of a camera, then incrementally moving the camera around until the object fits. This is obviously inefficient. So today I set out to figure out how to frame objects efficiently.
In 3d games, a camera defines a view frustum; this is a three-dimensional trapezoid. You can imagine it as a four-sided pyramid with the camera at the top, pointing down. For technical reasons, the top of the pyramid is cut off at the "near plane". The bottom of the pyramid is the "far plane":
I am sure that there is code to solve this problem already, but I like to understand the code I write, so I set out to derive a solution from first principles.
What I figured out was this:
* Pretend the camera is at the origin pointing down the +Z axis. (It's easy to transform the points into this point of view)
* Project each vertex V onto the four angled planes of the view frustum and find the distance. This is easy to calculate; it's just the dot product of the plane normal and the vertex. This distance is negative if the point is outside the frustum. The minimum value found for each plane touches the furthest vertex. You can then find the intersection of the left/right and top/bottom planes to get the camera's X and Y; the camera's Z is the minimum of the two Z values found.
* Also, the Z value of the furthest and nearest vertices can be used for the far/near plane.
The trickiest part is the middle one. What I did was figure out how far along one frustum plane the intersection point moves for each unit the opposite plane moves. Then, calculating all these values was just simple trigonometry.
Solution:
Given: set of vertices v, field of view half-angle θ.
s = sin θ
c = cos θ
p+ = (0, -1/2c, 1/2s); p- = (0, 1/2c, 1/2s)
n+ = (0, -c, s); n- = (0, c, s)
d+ = min_v(v dot n+); d- = min_v(v dot n-)
Cy = (d+ * p+) + (d- * p-)
Cx is calculated in a similar way, but swapping the x and y coordinates and using the appropriate θ.
camera position = (Cx.x, Cy.y, min(Cx.z, Cy.z))
near = min_v(v.z - C.z); far = max_v(v.z - C.z)
The code worked by placing the object in front of a camera, then incrementally moving the camera around until the object fits. This is obviously inefficient. So today I set out to figure out how to frame objects efficiently.
In 3d games, a camera defines a view frustum; this is a three-dimensional trapezoid. You can imagine it as a four-sided pyramid with the camera at the top, pointing down. For technical reasons, the top of the pyramid is cut off at the "near plane". The bottom of the pyramid is the "far plane":
I am sure that there is code to solve this problem already, but I like to understand the code I write, so I set out to derive a solution from first principles.
What I figured out was this:
* Pretend the camera is at the origin pointing down the +Z axis. (It's easy to transform the points into this point of view)
* Project each vertex V onto the four angled planes of the view frustum and find the distance. This is easy to calculate; it's just the dot product of the plane normal and the vertex. This distance is negative if the point is outside the frustum. The minimum value found for each plane touches the furthest vertex. You can then find the intersection of the left/right and top/bottom planes to get the camera's X and Y; the camera's Z is the minimum of the two Z values found.
* Also, the Z value of the furthest and nearest vertices can be used for the far/near plane.
The trickiest part is the middle one. What I did was figure out how far along one frustum plane the intersection point moves for each unit the opposite plane moves. Then, calculating all these values was just simple trigonometry.
Solution:
Given: set of vertices v, field of view half-angle θ.
s = sin θ
c = cos θ
p+ = (0, -1/2c, 1/2s); p- = (0, 1/2c, 1/2s)
n+ = (0, -c, s); n- = (0, c, s)
d+ = min_v(v dot n+); d- = min_v(v dot n-)
Cy = (d+ * p+) + (d- * p-)
Cx is calculated in a similar way, but swapping the x and y coordinates and using the appropriate θ.
camera position = (Cx.x, Cy.y, min(Cx.z, Cy.z))
near = min_v(v.z - C.z); far = max_v(v.z - C.z)