flipcode - Method for Curved Surfaces

Method for Curved Surfaces
by (13 January 1999)

Introduction

For the last few days I spend some time on implementing the extremely popular 'curved surfaces' in Focus. Before I started coding, I did some thinking: How can curves be used in the static geometry, does it add anything, could it be fast, and very important: Can it easily be integrated in the current engine. This document describes what I finally implemented, and why.

Curved Surfaces

For static geometry, it really doesn't make much sense to have arbitrary curved surfaces, like beziers or NURBS. You will not make walls that bend inwards in a smooth curve, that just doesn't look good. You could however want to add a curved door somewhere, or a perfectly round window. Or maybe you like the old DOOM barrels, and those would of course look very cool if they where perfectly round. A good compromise would therefore be to allow the curve to be a part of a circle: A curved surface will thus have at least two straight edges. This kind of curves is both easy to implement, and useful.

Curves become really usefull when you add 'level of detail', LOD. That means that the number of subdivisions that you use for the curve approximation depends on the distance and size of the curved polygons. A polygon that is only a single pixel on screen doesn't need to be curved at all, you won't notice it anyway. But if you look at a barrel real close, it might be a good idea to use lots of polygons, otherwise you will still see separate polygons. So, ideally the number of polygons should be adaptive.

This introduces another problem: How do you add a round window to a straight wall? If you subdivide the polygons for the window, it will probably leave nasty gaps where it touches the wall. That is where my structure comes in.

Imagine three polygons: The first is a rectangle, and on both sides (call them left and right) there is a triangle. The edges that are shared by the rectangle and the triangles will get curved, causing the rectangle to be subdivided in a strip of smaller rectangles. The triangles get split in just as many smaller triangles, this is called a 'triangle fan'. Have a look at this piece of ASCII art: (looks cool with courier)

A x----------x B
   \         |
    \        |
     \       |
      \      |
       D     |
        \    |
         \   |
          \  |
           \ |
            \x C

Let's say that this triangle shares edge A-C with the rectangle. If we subdivide A-C in 10 pieces, we could make it a nice arc by making sure that each calculated 3D coordinate is at the same distance from B as A and C are. Since A and C are probably not at the same distance from C, the distance can be interpolated. So, if the distance from A to B is 10, and the distance from C to B is 14, the distance of the fifth calculated coordinate ('D') should be 12. If we linearly interpolate from A to C we get a good approximation of the desired coordinate, and if we adjust the position of 'D' by moving it away from B, it is perfect. This way we can determine all extra vertices for the triangle fan, and for the rectangle strip. Of course, the right triangle can now be totally different. That way we can do various cool things: Cylinders are possible, but also flattened cylinders (when A and C are not at the same distance from B) and cylinders that are bigger at one side.

With a single structure like I just described, you can only do accurate curves that go from zero to 90 degrees. Larger arcs need multiple structures like this.

Imagine the barrel again: Split it in four (with four triangles making up the top, and four for the bottom). Now you have effectively a square barrel, until you subdivide the outer edges of the 8 triangles and move them away from the centre of the top and the bottom of the barrel. See what I mean?

Now arcs for doors are easy too: Define two triangles where the door should come, like this:

+----------------------+
|        ________      |
|        |1 /\ 2|      |
|        | /  \ |      |
|        |/  . \|      |
|        |      |      |
|        |      |      |
|        |      |      |
|        |      |      |
|________|      |______|

The ceiling of the passage behind the door consists of two 'rectangle strips'. In this case, the arcs of the triangles need to be moved the other way, towards the top left and top right vertices of the triangles. You can achieve this by defining extra vertices, around wich you curve the arc (for example, the dot in the image).

Closing

Other possible structures are: Round windows, pipes, round ceilings (though no half spheres), round car tires, round ropes, and so on. And you don't need beziers for it. :)

Enjoy,
Jacco Bikker - a.k.a. "THE PHANTOM"