how to: a geometric 3d bevel

This tutorial covers basic 3d modeling and rendering. It demonstrates how to write a beveling algorithm, which takes a 2d polygon and extrudes it into a 3d shape, and also includes the basics of lighting 3d objects.

DOWNLOAD. Java project written for Android. If you want to run the app, you will need to install the Android emulator and development environment. Note that the code is very messy; it's a workshop to shake out any issues with the algorithm. Also, read legal.txt before using this code elsewhere.

update 2010.11.14. Rewrote the core algorithm and clipping to work on polygons instead of triangles, removing all the triangulization (until the very last output stage). This creates a lot loss final geometry and provides a big speed boost, although I also rewrote the polygon clipper to fix bugs, which slowed things down a bit.

update 2010.11.01. Fixed a bug generating gaps during the extrude process.

The basic algorithm consists of two main steps: First extrude the input into 3d, then clip away any overlapping shapes.

Input is provided as a list of points forming a 2d polygon. We'll run the example on a shape I call silo, a simple object that covers a number of properties we want to test against the algorithm.

The first step is to convert every two points on our initial polygon into a quadrilateral in 3d space. Each new point is created the same way: Feed the algorithm 2 points, treating each segment like a ray to determine the direction (flipping the direction will cause the new point to be extruded outside the polygon, instead of inside). With this direction info, find a new segment parallel to the existing segment, with the new endpoints as bevel distance away from the input points, and bevel up along the z axis. In between adding quads, check to see if any gaps have formed, and add a triangle to span the difference if necessary. The basic algorithm is implemented in Extrude.java: The loop is in on(), the new segment generation is in extrudePoints() and gap generation is handled in fillGaps().

Once finished, and depending on the depth of the bevel, we've generated what looks like a mess, with many overlapping polygons.

The next step is to clip away the overlapping geometry, which is the heart of the algorithm. Conceptually, the problem is fairly simple. Imagine our object rotated on its side, so that we see each polygon (the quadrilaterals and triangles generated during the extrude) as a plane rising from the ground, intersecting with other polygons. That line of intersection is the clip point, and we want to remove everything above it. The basic steps are these:

1. For each polygon a, find its area of intersection with polygon b. This is done by projecting each point of b onto the same plane as a, then determining which of the new points lie above or below their originals. The simple cases are: All points lie above, in which case no clipping can occur; or all points lie below, in which case all of b is clipped from a. The degenerate case is a mix of these conditions, in which case we need to find where the intersections against a occur, which then form the basis of the clipping polygon. In all success cases, the result is a polygon on the same plane as a.
2. Subtract the clipping polygon from polygon a. (Side note: Boolean subtraction of polygons is a fairly large topic; I've found numerous resources online, but when implemented, they all had a variety of flaws. The more robust solutions seem to only be available as licensed libraries, so I've spent some time on my own clipper, slowly increasing the quality. My current implementation (see Bool.java in the source) is edge-based, examining which edges are "good" and should be included, and which are "evil" and should be tossed, then generating new polygons from that info. No doubt there are many improvements that still need to be made.)
3. Repeat for each polygon b that overlaps polygon a.

The algorithm is simple, but the implementation is extensive enough that it's easier to look at the source rather then a series of excerpts. The main loop happens in Clip.java, which builds the clipping poly for each polygon in the input. The results are passed to Mask.java, which is responsible for running the boolean subtraction operation and triangulating the final, completely clipped, polygon (or polygons, as multiple polygons might be output by the boolean operation).

Now that we have a 3d model, let's take a couple extra minutes to light it. This is a huge topic, but the basics are very simple: To light a 3d object, all you need is the surface normal and a light source. The normal is the vector perpendicular to your surface. In the case of a triangle, the normal is found by taking the cross product of two edges, for example:

void setOn(final Tri t, final Surface s) {
mA.asVector(t.mPt[1], t.mPt[0]);
mB.asVector(t.mPt[2], t.mPt[1]);
s.mNormal.asCrossProduct(mA, mB);
s.mNormal.normalize();
}

and then measuring the distance to a light source:

private final double lightFrom(final Point3 normal, final Point3 light) {
return (normal.x*light.x + normal.y*light.y + normal.z*light.z) / (normal.length() * light.length());
}

Both methods are found in RenderTri in the source.

With the normals we can now light each surface of the model.

For fun, let's look at a couple other cases, this time with a little shading in place indicating the Z height of each pixel.

IMPROVEMENTS

Complex initial shapes can confuse the routine for determining the point order (clockwise, counterclockwise), found in Extrude.isClockWise().

Of course, performance is very poor. Two obvious issues jump to mind: There is a ton of temporary data being generated and tossed, so the garbage collector is constantly chugging. Creating reusable buffers for triangles and polygons would probably have a big performance impact. Also, finding the distance between points and lines is very common, but usually you just need a relative distance, so you can toss the sqrt() involved. This is already done in a number of places, but there are more that could be weeded out.

REFERENCES

Segment to segment intersection (2d)
http://alienryderflex.com/intersect/

Segment to segment intersection (3d)
http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm#dist3D_Segment_to_Segment()

Ray to triangle intersection (3d)
http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm

Distance from point to segment (3d)
http://www.softsurfer.com/Archive/algorithm_0102/#dist_Point_to_Segment()

General all-around good intersection info
http://www.realtimerendering.com/intersections.html