# Calculating Intersections of Lines and Algebraic Surfaces

For context I am developing a ray-tracer for a computer science class, and want to implement some more advanced shapes than just spheres. So while this is related to schoolwork, I'm not asking you to do my work for me, the work is implementing the programming, and it's the math I don't understand, so I'm just looking for help understanding how the math works.

I am trying to understand how to calculate the intersection point, and the normal vector from that point, of several algebraic surfaces. I am at the very frustrating point of knowing what I need to do, and how it is theoretically done, but not really grasping how to actually do it.

I know that I need to take the equation for the line and substitute the x, y, and z variables in the surface equation for the equivalent portions of the line equation, but as soon as I sit down to do that, I immediately hit a mental brick wall. As for the normal calculations, I'm really lost, I'm not even sure there is a general case way to calculate the normals.

So, I'd love some help on how to calculate the intersection and normal of some of these shapes, and any sort of general case rules for these calculations would be fantastic.

Update While real general case solutions would be super awesome, it's ok to assume the shapes are in their standard orientation, not rotated or transformed at all - just positioned and (maybe) scaled. This make the problem much simpler, I believe. If there are other limitations you can use to make the problem even simpler, that's likely fine.

-
 In general, analytic solutions can only be found for certain special cases. You may want to try this link: ads.tuwien.ac.at/research/ssi for a survey of algorithms to approximate intersections. – WWright Sep 19 '10 at 4:37

Perhaps this more elementary description could help. Let $e$ be the eye/camera, and $v$ a line-of-sight vector. You want to solve simultaneously $e + t v$ with the surface you want to view, solving for $t$. If you have two or more surfaces, don't try to intersect them with one another, which can be algebraically complex, but rather let the ray tracing (effectively) do it for you.

Suppose you have a surface patch $S$ (perhaps a Bezier surface) parametrized by $a$ and $b$. So now you want to solve simultaneously for $(t, a, b)$. If $S$ is a sphere or cylinder, this amounts to quadratic equations. If $S$ is a cubic patch, it will reduce to solving cubic equations. If $S$ is a torus, degree-4 equations. Once you have $(a,b)$, you can get the normal vector at that point from your parametric equations, as J.M. describes.

-

The "normal vector" to a surface is easy enough: compute the partial derivatives with respect to both dependent variables (with respect to $x$ and $y$ if you have $z=f(x,y)$; with respect to parameters $u$ and $v$ if you have a parametric representation $(x\;\;y\;\;z)=(f(u,v)\;\;g(u,v)\;\;h(u,v))$), and then take the cross product of the vectors obtained, (with the option of normalizing it to have unit length).

In any event, I think you're better off trying to do surfaces with "easy" parametric representations: the manipulations are much easier than if you have them in implicit Cartesian form.

For polyhedra, finding normals to the faces is an even easier task: take the barycenter/centroid of the face under consideration, subtract the components of that from the components of any two selected vertices in the face, and take the cross product of the two resulting vectors (with again the option to normalize to unit length afterward).

-
 As for doing the intersection of two algebraic surfaces, the highbrow way of going about it relies on Gröbner basis computations, but that's too much I think for a simple class project. – J. M. Sep 19 '10 at 4:48 Well I know for a fact the sphere, cone, and cylinder can be calculated, as can the dingdong. is there a simpler algorithm if we don't need to rotate or transform the shape at all? – dimo414 Sep 19 '10 at 8:47 @dimo: Exactly what other shapes did you have in mind that you say are giving you trouble? As I said, dealing with arbitrary algebraic surfaces is a tough one; the examples you gave are so-called "quadric surfaces", and these are relatively easier to handle/parametrize/manipulate. – J. M. Sep 19 '10 at 9:25 I've said I'd try to do the cube, but that's not quadratic, and maybe would be too hard. The zylinder seems pretty straightforward, and like I said, I'm really struggling with the conceptual part of all of this, so even simple examples would be really helpful. – dimo414 Sep 19 '10 at 9:33 The cube is nothing more than six planes; just treat the six planes as a group. What sort of examples would you want to see? – J. M. Sep 19 '10 at 9:57
show 1 more comment