The magazine of the Melbourne PC User Group Build a Bezier boat (Part 1): Smooth 3D surfaces Ken Holmes kholmes@melbpc.org.au

Fiddling with the Bezier method of constructing a smooth curve to round off a corner in two dimensions suggested extending to three dimensions and using the mirror method to view this stereoscopically. Further, it was natural to go on to use a mesh of Beziers to generate smooth surfaces.

Who or what is a Bezier?

I don't know who, but had assumed he was a French gentleman who devised the technique, of which I believe I have been aware since school days, and which is used by manual draughtsmen and CAD programs. Perhaps some member will enlighten me! Figure 1 illustrates the trick; three- or four-point Beziers are commonly used but you can devise five- or more-point types if you insist. If you have played with the Paintbrush program, in Windows 3.x Accessories, or Paint, in Windows 95 Accessories, you may have already used Beziers. Choosing the "curved line" tool, then clicking and dragging the mouse will draw a line, the ends of which become the "anchors". Clicking again will pull the centre of the line half way towards the mouse and you can move the mouse (as a "handle"), until the curve suits your taste, then release it. This is a three-point Bezier. Click again and you have another "handle" available which will drag that part of the line, between the second anchor and the first handle, towards the mouse. Release and you have a four-point Bezier. The latter curve can be simple or S-shaped or, if the two anchors are coincident (no initial drag), you will get a very credible aerofoil shape.

In Figure 1, the anchors for the three- point are "1" and "3", and the handle is "2". Level 0 of the method puts "4" midway between "1" and "2" and "5" midway between "2" and "3"; then "6" is midway between "4" and "5" and is the first calculated point on the curve. In level 1 we repeat the same algorithm using "1" and "6" as anchors and "4" as handle to provide another point, "7", on the curve. This is called a recursive" program since the same piece of code, or process, recurs by being called up within itself as many times as you wish. After we have pursued the first half of level 1 to further levels, we return and call the second half of level 1. Thus, level 1 gives us (eventually) two points on the curve. Similarly, level 2 gives four points, level 3 gives eight points and level n gives 2^n (2 to power n) points in a sort of binary tree. If we stop at, say, level 3 with eight points, we get them in neat sequence from the first anchor end with the first in the middle of the first one-eighth of the curve. To draw the continuous curve, we allow further levels to be called until the distance between adjacent points is less than one pixel; for example, level 7 would give 128 points and levels 0 to 6 would have already given 127 points for a total of 255.

Dealing now with the four-point, the anchors are "1" and "4", and the handles are "2" and "3". Level 0 of the method puts "5" midway between "1" and "2", "6" midway between "2" and "3" and "7" midway between "3" and "4"; then "8" is midway between "5" and "6" and "9" is midway between "6" and "7"; now "10" is midway between "8" and "9" and is the first calculated point on the curve. In level 1 we repeat the same algorithm using "1" and "10" as anchors with "5" and "8" as handles to provide a further point--and (eventually) "10" and "4" as anchors with "9" and "7" as handles to provide another. This is somewhat more complicated than the three-point procedure but note that we still get one point from level 0, two from level 1, and so on, just as with the three-point. Importantly, more useful shapes may be generated.

Notice that, with either type, the tangent to the curve at an anchor (end) is in fact the line joining that anchor to the nearest handle. So, if we want to link Beziers in a string, with the second anchor of the first being also the first anchor of the second, we may ensure there is no kink by lining up the two tangents. In other words, the common anchor must lie on the line joining the adjacent handles; if one handle is moved, we recalculate the position of the anchor to maintain this. Of course we may want a kink, and we can have it, as we will in the second part of this article when we design a keeled yacht. Note also that we are not using esoteric maths here. We can find a midpoint simply by averaging, respectively, the "x" and "y" co-ordinates of the end points, and we can go to three dimensions by doing the same for "z" co-ordinates.

The listing of BEZ.BAS is included as a bare-bones illustration of the power and economy of the recursion technique. For more ambitious projects, you would use a container for a point's co-ordinates, such as a user-defined TYPE in QBasic or a CLASS in C++. In the latter case you could use a Class Function to find midpoints. The recursions are counted here and the figure printed is 1023, i.e. up to level 9; as the curve spans 600 pixels horizontally, level 8 (511) would not eliminate all gaps.

Let's do something with them

For the moment, we will use a simple mesh to create a half-hull of a boat, and mirror it for the other half, see Figure 2. We use four-point Beziers along the gunwale, bilge and keel and, at stations along these, three-point Beziers from gunwale to keel, providing cross sections. Point "0" is the bow and point "3" is the top corner of the transom, acting as anchors, with points "1" and "2" as handles to control the beam and the position of maximum beam. Point "0" and point "9" anchor the keel with "7" and "8" to control shape and depth. Points "0", "4", "5" and "6" create an intermediate Bezier along the bilge, but outside the hull. At a cross- section, the gunwale and keel are already anchored but the bilge Bezier provides a handle to pull out the bilge. If you use a mirror vertically between the two views, it will be in stereo and the position of each point and the shape may be clearly seen. Note that the lengthwise Bezier entered 511 recursions (level 8), mainly to get near-solid lines for the gunwale, keel and longitudinal sections in the side view. The crosswise Bezier entered over 30,000 recursions or an average of 60 points (level 5) at each cross section--and is still a little dotty. Only 32 cross sections are actually plotted on the stereos and eight on the top diagram. This is a bit of overkill and slows the calculation to a whole two seconds (on a 486)!

The C++ program producing this will be on the BBS as BEZBOATS.LZH. Any of the points may be selected and moved using the cursor keys, producing many shapes, from canoes to planing hulls, from just 10 control points. Less bland boats, say, hard chined or tunnel hulls, or trimarans can be readily designed using more Beziers strung together across the hull. Anchors provide the option of soft or smooth blending and, even, the one line of anchors can change from a smooth junction near the bow to a sharp corner at the transom. The program can be written to record the exact position of any number of points on the surface and print them to the screen or write a file for use in construction. All sorts of characteristics may be calculated, such as cross section area, segment volumes, buoyancy distribution for different waterlines, pitching and rolling moments, and stability. Changes may be made and the whole output will be instantly revised, so there is no inhibition to trying many combinations to optimise some characteristic, assuming you know what you are trying to achieve as regards actual performance on the water. I don't know any boat designers but assume something along these lines is used in the computerised yachting world.

In Part 2, we will design a yacht using a four-point Bezier from bow to keel, joined to a three-point for the mid-section, joined to a four-point to the transom. This allows us to have a smooth line along the gunwale and bilge but kinks at the front and rear of the keel. Four point Beziers down the side (gunwale, bilge, bottom and centreline) enable us to use an S-shape near the keel but simpler curves towards bow and stern. Points will be recorded at bow (one point) and 19 stations along the yacht with 18 points down the side, i.e. 343 points. These will define 17 triangles between bow and the first X-section and 306 rectangles that we chop into 612 triangles and write into a file, in the exact format required by the raytracing program, POV-Ray. Naturally, you will see a ray-tracing produced from this.

Reprinted from the April 1999 issue of PC Update, the magazine of Melbourne PC User Group, Australia

[About Melbourne PC User Group]