[Algorithms] Sphere to rectangle

[Diogo de A. <dio...@ne...>]

Hi all.

 

I've been wrestling with a problem for some days now, and I honestly can't
seem to figure an elegant solution.

 

I want to find the rectangle that bounds a omni light source, so the problem
is: given a sphere with center C=(x0,y0,z0) and radius RADIUS, what is the
bounding rectangle rect=(rx1,ry1,rx2,ry2) on screen? 

 

My first guess was to find the extents of the sphere from the camera point
of view:

 

0)      Given a camera with position O=(x2,y2,z3) and view vectors
V=(v1,v2,v3), U=(u1,u2,u3) and R=(r1,r2,r3)

1)      Compute E1=C+R*RADIUS and E2=C+U*RADIUS

2)      E1'=proj(E1)

3)      E2'=proj(E2)

4)      O'=proj(O)

5)      rect=(O'.x-E1.x,O'.y+E2.y,O'.x+E1.x,O'.y+E2.y)

 

This almost works (specially at larger distances), but it is wrong, because
the points I find aren't the real bounds of the sphere from the camera
(after projection, the rectangle is smaller than needed), because I'm using
a perspective projection and not a orthogonal projection (took me alots of
diagrams to understand why).

 

After some more thinking, I arrived to the conclusion that what I want is to
find out the point E  that fulfill these two conditions:

 

||E-C||=r -> The point belongs to the sphere

dot(E-O,E-C)=0 -> The line defined by O and E is tangent to the sphere at
point E.

 

I started crushing the equations, but then I found that I was looking at
this problem really in 2d, and not 3d, and I have no idea on how to convert
this to 3d, to be honest.

 

My first guess is that I project all the relevant points (C and O) first
onto the plane with normal U (to extract the "horizontal" extents) and then
onto the plane with normal R (to extract the "vertical" extents) and then
treat the problem as a 2d problem, and combine the solutions to obtain a
point E1 and E2, which then are projected onto the screen (following from
point 2 on the algorithm above). But I'm not sure if this is the right
answer.

 

I'm not even sure if there isn't a better solution, to be honest. Saw
somewhere that I could find the intersection between the sphere and an
"imaginary" sphere with center C'=mid(O,C) and radius RADIUS'=||C'||/2, and
that seems like it can be easier to manage, but again, I'm not sure.

 

To compound the problem, afterwards I want to do the same for a spotlight,
which complicates matters (I need to find the bounding rectangle of a cone,
which seems like a bigger nightmare!).

 

So, can someone lend me a hand on this? Just being pointed in the right
direction (book, site, mathematical direction, etc), would be appreciated.
Even more, would be code to do both of these, but that might be a bit much
to ask. ;)

 

Thanks in advance

Diogo de Andrade