Bezier Surface-Surface Intersection

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: http://www.geocities.com/sandeep_pulla/cracking_problem/main.html

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.