Bezier Surface-Surface Intersection

I need an algorithm for computing the intersection points between two bicubic Bezier surfaces.  Specifically, I would like to use the Divide and Conquer approach.  However, the only thing I can think of so far is as follows:

1.  Test the bounding boxes of each surface patch for any possible intersection - if not, then exit.
2.  Test for planarity of each surface patch - if not, then increase order of Bezier patch.  Continue until sufficient planarity is acquired.  
3.  Determine intersections of plane segments.

With this algorithm, I am fairly comfortable performing steps one and two, but am unsure how to do step three.  However, I am not married to this particular algorithm - it simply is the only one that I can think of.  One potential problem that makes me hesitant is the ability to quickly overload the computer by increasing the order over and over again until each surface patch is sufficiently planar - something I foresee as requiring a very high order Bezier surface.  If you are aware of another algorithm, feel free to submit that.

I'm pretty generous with points and do not feel that this problem is particularly difficult for someone who is comfortable with 3D graphics (I, however, am not - so I could really use some help).  I would really appreciate a walkthrough of the logic that is need to carry this out.

One final note, I am attempting to do this in MATLab because I don't have any other programming language available to me.  I am comfortable with many other languages (Basic, Fortran, Pascal C (rusty) and LISP (rusty), so please keep that in mind.  

Many Thanks,
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
About increasing patches to gain planarity, don't see why, well, may be just because you pretedn to use 2 plane section intersection... but how do you know a plane intersection of patch A will not intersect two or three plane segments on path B? It can get tricky this way, I think.

If you do it to avoid "cracks" in the unions, have a look here first:

How would I do it: First step is clear, check for the boundaries to intersect before any other thing! Yuo can solve it quickly by comparing MaxX(Patch1)<MinX(Patch2) and MinX(Patch1)>MaxX(Pacth2), then repeat for Y and Z.

I woul go this way from here:

A) Test all the points in the 4 sides of patch 1 to find one were Z is the same as Z in the second patch: For each point in one side of the patch1, check that this (x,y) lies inside patch2 and then calculate DiffZ(x,y) = Patch1(x,y)-Patch2(x,y) [difference between Z coords), and continue moving on the side of the patch (adding a small (dx, dy) amount) until DiffZ changes in sign. If it doesn't happend, go with the next side of the patch.

B) Finally you have no such a point (no intersection occurs -at least in the boundaries-), so they don't intersect. Or, you find a point in the Patch1 border that is an intersection point with Patch2. Let's call it (P0x, P0x)

Now, the idea is to go, from this point (P0x, P0x), jumping to another DiffZ=0 (intersection) point in the interior of the surface until you reach the other border line where intersection line finish... but how?

C) Set a initial direction of the search to be normal to the side you were testing, and pointing to the patch1 interior. So if last point you checked in the A) step before you found this initial point (P0x, P0x) was (P'x, P'y), then initial search vector -call it (Sx, Sy)- can be (P'y-P0y, -(P'x-P0x)) or its negative... check they both to determine withch one makes (P0x + Sx, P0y + Sy) lie inside Patch1 domain. Normalize the winner to have it measure 1 unit, or even better, put it in 2D polar coordinates, and as length is useless here, just keep the angle if you wish.

D) So the second point in your path (the intersection of the 2 patch will be a 3D path), and the rest of the points in the serie, is calculated always the same way: Candidate is the prior point found -(P0x, P0y) in the beginning- adding search vector (Sx, Sy) * dv (like a little junp in that direction, chose dv to be something like 1/100 of the side length so your path will have about 100 points accurace).

E) Before admiting new candidate, check for DiffZ, and if it is "too big" (use some constant dz=1/100000 or similar), then move angle a little (+ or - it) and recheck, if it goes worst, use the other direction (- angle). Once the good direction is found, keep adding to the angle -remember, angle of the polar coords. of (Sx, Sy)- until Diff change form positive to negative (or oposite), change angle jump to the half and steep back angle until you manage to keep DiffZ lower than dz (standard way of searching for zeros in 2D usual functions).

F) Once you found a second point, dv -or less- units away from first, and using a given angle to jump from previous point, just repeat the process using this angle as the new search intial angle to find a third point.... and keep on doing this until the point found "walk back the path" meaning you can't go further so angle optimization gives you -last_angle, so you are "driving backwards".

You can check it (only in 2D x,y coordinates, as Z is the height in the patches) taking care that angle used in the last jump does not equals -initial_angle, as it should mena pn basically equals pn-2.
My best suggestion is to go to the POVRay website and download their source code. It includes these kind of test and is reasonably easy to follow.

Note this product is freeware and the source is freely available. There is also a large knowledgable community that could probably assist you. Search for MegaPov to get started.

It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Game Programming

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.