Previous Table of Contents Next


Chapter 65
3-D Clipping and Other Thoughts

Determining What’s Inside Your Field of View

Our part of the world is changing, and I’m concerned. By way of explanation, three anecdotes.

Anecdote the first: In the introduction to one of his books, Frank Herbert, author of Dune, told how he had once been approached by a friend who claimed he (the friend) had a killer idea for an SF story, and offered to tell it to Herbert. In return, Herbert had to agree that if he used the idea in a story, he’d split the money from the story with this fellow. Herbert’s response was that ideas were a dime a dozen; he had more story ideas than he could ever write in a lifetime. The hard part was the writing, not the ideas.

Anecdote the second: I’ve been programming micros for 15 years, and writing about them for more than a decade and, until about a year ago, I had never—not once!—had anyone offer to sell me a technical idea. In the last year, it’s happened multiple times, generally via unsolicited email along the lines of Herbert’s tale.

This trend toward selling ideas is one symptom of an attitude that I’ve noticed more and more among programmers over the past few years—an attitude of which software patents are the most obvious manifestation—a desire to think something up without breaking a sweat, then let someone else’s hard work make you money. It’s an attitude that says, “I’m so smart that my ideas alone set me apart.” Sorry, it doesn’t work that way in the real world. Ideas are a dime a dozen in programming, too; I have a lifetime’s worth of article and software ideas written neatly in a notebook, and I know several truly original thinkers who have far more yet. Folks, it’s not the ideas; it’s design, implementation, and especially hard work that make the difference.

Virtually every idea I’ve encountered in 3-D graphics was invented decades ago. You think you have a clever graphics idea? Sutherland, Sproull, Schumacker, Catmull, Smith, Blinn, Glassner, Kajiya, Heckbert, or Teller probably thought of your idea years ago. (I’m serious—spend a few weeks reading through the literature on 3-D graphics, and you’ll be amazed at what’s already been invented and published.) If they thought it was important enough, they wrote a paper about it, or tried to commercialize it, but what they didn’t do was try to charge people for the idea itself.

A closely related point is the astonishing lack of gratitude some programmers show for the hard work and sense of community that went into building the knowledge base with which they work. How about this? Anyone who thinks they have a unique idea that they want to “own” and milk for money can do so—but first they have to track down and appropriately compensate all the people who made possible the compilers, algorithms, programming courses, books, hardware, and so forth that put them in a position to have their brainstorm.

Put that way, it sounds like a silly idea, but the idea behind software patents is precisely that eventually everyone will own parts of our communal knowledge base, and that programming will become in large part a process of properly identifying and compensating each and every owner of the techniques you use. All I can say is that if we do go down that path, I guarantee that it will be a poorer profession for all of us—except the patent attorneys, I guess.

Anecdote the third: A while back, I had the good fortune to have lunch down by Seattle’s waterfront with Neal Stephenson, the author of Snow Crash and The Diamond Age (one of the best SF books I’ve come across in a long time). As he talked about the nature of networked technology and what he hoped to see emerge, he mentioned that a couple of blocks down the street was the pawn shop where Jimi Hendrix bought his first guitar. His point was that if a cheap guitar hadn’t been available, Hendrix’s unique talent would never have emerged. Similarly, he views the networking of society as a way to get affordable creative tools to many people, so as much talent as possible can be unearthed and developed.

Extend that to programming. The way it should work is that a steady flow of information circulates, so that everyone can do the best work they’re capable of. The idea is that I don’t gain by intellectually impoverishing you, and vice-versa; as we both compete and (intentionally or otherwise) share ideas, both our products become better, so the market grows larger and everyone benefits.

That’s the way things have worked with programming for a long time. So far as I can see it has worked remarkably well, and the recent signs of change make me concerned about the future of our profession.

Things aren’t changing everywhere, though; over the past year, I’ve circulated a good bit of info about 3-D graphics, and plan to keep on doing it as long as I can. Next, we’re going to take a look at 3-D clipping.

3-D Clipping Basics

Before I got deeply into 3-D, I kept hearing how difficult 3-D clipping was, so I was pleasantly surprised when I actually got around to doing it and found that it was quite straightforward, after all. At heart, 3-D clipping is nothing more than evaluating whether and where a line intersects a plane; in this context, the plane is considered to have an “inside” (a side on which points are to be kept) and an “outside” (a side on which points are to be removed or clipped). We can easily extend this single operation to polygon clipping, working with the line segments that form the edges of a polygon.

The most common application of 3-D clipping is as part of the process of hidden surface removal. In this application, the four planes that make up the view volume, or view frustum, are used to clip away parts of polygons that aren’t visible. Sometimes this process includes clipping to near and far plane, to restrict the depth of the scene. Other applications include clipping to splitting planes while building BSP trees, and clipping moving objects to convex sectors such as BSP leaves. The clipping principles I’ll cover apply to any sort of 3-D clipping task, but clipping to the frustum is the specific context in which I’ll discuss clipping below.

In a commercial application, you wouldn’t want to clip every single polygon in the scene database individually. As I mentioned in the last chapter, the use of bounding volumes to cull chunks of the scene database that fall entirely outside the frustum, without having to consider each polygon separately, is an important performance aspect of scene rendering. Once that’s done, however, you’re still left with a set of polygons that may be entirely inside, or partially or completely outside, the frustum. In this chapter, I’m going to talk about how to clip those remaining polygons. I’ll focus on the basics of 3-D clipping, the stuff I wish I’d known when I started doing 3-D. There are plenty of ways to speed up clipping under various circumstances, some of which I’ll mention, but the material covered below will give you the tools you need to implement functional 3-D clipping.


Previous Table of Contents Next

Graphics Programming Black Book © 2001 Michael Abrash