Moving a 3D camera to perfectly fit entire scene

Intro

I had a simple task to perfectly fit entire 3D scene onto a viewport. There is only one limitation — I’m allowed to only change camera position, meaning that its rotation and fov are locked.

How hard can it be? Most probably for a seasoned game developer this is a trivial task but for a beginner it is quite an interesting challenge.

More over most solutions out there cover only simplified case with a single AABB or a sphere. But what to do if I have multiple objects or a cloud of vertices and single AABB is not precise enough?

Quick note

At first I probably need to describe what “perfect” means in this case. It means that the scene must touch top/bottom or left/right part of the viewport at any given time with any aspect ratio. I can allow myself to do some minimal shortcuts in the name of performance but algorithm should be able to make a real perfect fit in case precision is more important.

I will also be using GoDot with Rust binding for this arcticle but it can be easily translated to the language of your choice.

Inspiration / Mentions

First of all I need to be honest — this algorithm is not entirely my idea. It contains some optimizations like changing O(N²) to O(N) but the most interesting parts come from a single StackOverflow answer I found that fits my requirements.

Well… I’m sure this question was answered many times in other places and I’m just bad at searching. Anyways.

Lets start

Before doing anything interesting lets create a simple scene:

And here is our beautiful render:

Algorithm

General idea is pretty simple — we take camera frustum planes and find vertices on the edges of each plane. For our case we don’t care about near and far plane, we care only about left, top, right and bottom planes. Than we reposition our planes to the edge vertices and find their intersection point.

That’s it. Simple.

Now lets implement it. This is the result we want to achieve:

Here red vertex is the leftmost vertex and green one is the rightmost vertex. Here is how it looks in the code:

let frustum = camera.get_frustum();

// get frustum planes
let left_plane = frustum.get(2);
let right_plane = frustum.get(4);
let top_plane = frustum.get(3);
let bottom_plane = frustum.get(5);

// get edge vertices for each plane
let left_vertex = vertices.iter().max_by_key(|vertex| {
    OrderedFloat(left_plane.normal.dot(**vertex))
})?;
let right_vertex = vertices.iter().max_by_key(|vertex| {
    OrderedFloat(right_plane.normal.dot(**vertex))
})?;
let top_vertex = vertices.iter().max_by_key(|vertex| {
    OrderedFloat(top_plane.normal.dot(**vertex))
})?;
let bottom_vertex = vertices.iter().max_by_key(|vertex| {
    OrderedFloat(bottom_plane.normal.dot(**vertex))
})?;

Now we have edge left, top, right and bottom vertices for our frustum planes. This is how it looks:

Dots are the actual vertices selected (left = red, top = blue, right = green, bottom = magenta) and lines are the normal vectors for each plane.

Now we need to construct new frustum planes with the points we just discovered:

let left_plane_new = Plane::from_point_normal(
    *left_vertex,
    left_plane.normal,
);
let right_plane_new = Plane::from_point_normal(
    *right_vertex,
    right_plane.normal,
);
let top_plane_new = Plane::from_point_normal(
    *top_vertex,
    top_plane.normal,
);
let bottom_plane_new = Plane::from_point_normal(
    *bottom_vertex,
    bottom_plane.normal,
);

Next part is to find where these planes intersect. Unfortunately, we can’t have a single point with four planes… If it was that easy. Instead we’ll have two lines — one for left and right planes, second for top and bottom planes. Here is an example for horizontal planes:

In short this means that no vertex will ever be cropped horizontally if camera is placed anywhere on this line.

And this is intersection line for the vertical planes:

Same goes here — no vertex will ever be cropped vertically if camera is placed anywhere on this line.

Here is the code to find these lines:

fn get_planes_intersection(p1: Plane, p2: Plane) -> Option<Ray> {
    let p3normal = p2.normal.cross(p1.normal);
    let p3d = p3normal.length_squared();

    if p3normal.is_zero_approx() {
        return None;
    }

    Some(Ray {
        origin: ((p3normal.cross(p2.normal) * p1.d) + (p1.normal.cross(p3normal) * p2.d)) / p3d,
        direction: p3normal,
    })
}

let horizontal_intersection = get_planes_intersection(
    left_plane_new,
    right_plane_new,
)?;
let vertical_intersection = get_planes_intersection(
    top_plane_new,
    bottom_plane_new,
)?;

Now we have two separate lines that most of the time will not overlap, what now? Well, we need to reduce this problem to finding two closest points between these lines:

let a = line1.direction.dot(line1.direction);
let b = line1.direction.dot(line2.direction);
let e = line2.direction.dot(line2.direction);

let d = a * e - b * b;

let r = line1.origin - line2.origin;
let c = line1.direction.dot(r);
let f = line2.direction.dot(r);

let s = (b * f - c * e) / d;
let t = (a * f - c * b) / d;

let closest_point_line1 = line1.origin + line1.direction * s;
let closest_point_line2 = line2.origin + line2.direction * t;

Only thing remaining is to choose which point to use for the camera position. Solution is simple — just choose the furthest point because it will cover more screen space:

let camera_transform = camera.get_global_transform();
let camera_forward = camera_transform.basis * Vector3::FORWARD;

match (closest_point1 - closest_point2).dot(camera_forward) < 0.0 {
    true => closest_point1,
    false => closest_point2,
}

And voila, we can now perfectly fit entire scene on the viewport only by moving the camera:

Full code

///
/// https://stackoverflow.com/a/66113254/855884
///
pub fn get_fit_to_viewport_position(camera: &Camera3D, vertices: &[Vector3]) -> Option<Vector3> {
    let frustum = camera.get_frustum();

    // get frustum planes
    let left_plane = frustum.get(2);
    let right_plane = frustum.get(4);
    let top_plane = frustum.get(3);
    let bottom_plane = frustum.get(5);

    // get edge vertices for each plane
    let left_vertex = vertices.iter().max_by_key(|vertex| {
        OrderedFloat(left_plane.normal.dot(**vertex))
    })?;
    let right_vertex = vertices.iter().max_by_key(|vertex| {
        OrderedFloat(right_plane.normal.dot(**vertex))
    })?;
    let top_vertex = vertices.iter().max_by_key(|vertex| {
        OrderedFloat(top_plane.normal.dot(**vertex))
    })?;
    let bottom_vertex = vertices.iter().max_by_key(|vertex| {
        OrderedFloat(bottom_plane.normal.dot(**vertex))
    })?;

    // create new planes centered in the edge vertices
    let left_plane_new = Plane::from_point_normal(
        *left_vertex,
        left_plane.normal,
    );
    let right_plane_new = Plane::from_point_normal(
        *right_vertex,
        right_plane.normal,
    );
    let top_plane_new = Plane::from_point_normal(
        *top_vertex,
        top_plane.normal,
    );
    let bottom_plane_new = Plane::from_point_normal(
        *bottom_vertex,
        bottom_plane.normal,
    );
    
    // find lines of plane intersections
    let horizontal_intersection = get_planes_intersection(
        left_plane_new,
        right_plane_new,
    )?;
    let vertical_intersection = get_planes_intersection(
        top_plane_new,
        bottom_plane_new,
    )?;
    
    // find nearest point on the intersection lines
    let (closest_point1, closest_point2) = find_closest_points_on_two_lines(
        horizontal_intersection,
        vertical_intersection,
    );

    // find the closest point that is furthest from the scene
    let camera_transform = camera.get_global_transform();
    let camera_forward = camera_transform.basis * Vector3::FORWARD;

    Some(match (closest_point1 - closest_point2).dot(camera_forward) < 0.0 {
        true => closest_point1,
        false => closest_point2,
    })
}

///
/// https://stackoverflow.com/a/32410473/2373034
/// Returns the intersection line of the 2 planes
///
fn get_planes_intersection(p1: Plane, p2: Plane) -> Option<Ray> {
    let p3normal = p2.normal.cross(p1.normal);
    let p3d = p3normal.length_squared();

    if p3normal.is_zero_approx() {
        return None;
    }

    Some(Ray {
        origin: ((p3normal.cross(p2.normal) * p1.d) + (p1.normal.cross(p3normal) * p2.d)) / p3d,
        direction: p3normal,
    })
}

///
/// Returns the edge points of the closest line segment between 2 lines
///
fn find_closest_points_on_two_lines(line1: Ray, line2: Ray) -> (Vector3, Vector3) {
    let a = line1.direction.dot(line1.direction);
    let b = line1.direction.dot(line2.direction);
    let e = line2.direction.dot(line2.direction);

    let d = a * e - b * b;

    let r = line1.origin - line2.origin;
    let c = line1.direction.dot(r);
    let f = line2.direction.dot(r);

    let s = (b * f - c * e) / d;
    let t = (a * f - c * b) / d;

    let closest_point_line1 = line1.origin + line1.direction * s;
    let closest_point_line2 = line2.origin + line2.direction * t;
    (closest_point_line1, closest_point_line2)
}

Hope you liked it or even better — found it useful!