Aug 99 Challenge
Volume Number: 15
Issue Number: 8
Column Tag: Programmer's Challenge
Aug 99 Prgrammer's Challenge
by Bob Boonstra, Westford, MA
3D FlyBy
Some of the people who have recently written to suggest possible Challenge problems
have asked for Challenges that are more specific to the Macintosh. Well, not everyone
is actually that subtle about it. One writer lamented "yet another plain-vanilla
Challenge that could just as well have appeared in a Linux or Windows programming
magazine". Ouch!! Since this column is based on demonstrating efficient performance,
many of the problems naturally carry over to other platforms. But the writer has a
point, and this month's Challenge will have more to do with the Mac OS.
Back in April, readers were asked to find a path through three-dimensional terrain
that minimized elevation change. This month, you'll also be dealing with 3D terrain,
but you'll be flying over it, and displaying a perspective view of that terrain. In the
process, you'll have the opportunity to learn a little about QuickDraw3D.
The prototype for the code you should write is:
#include
#include
#include
#include
#if defined(__cplusplus)
extern "C" {
#endif
typedef struct MyTriangles {
long pointIndices[3];
TQ3ColorRGB triangleColor;
} MyTriangles;
void InitFlyBy(
CWindowPtr theWindow,
long numPoints,
const TQ3Point3D thePoints[],
long numTriangles,
const MyTriangles theTriangles[],
const TQ3ViewAngleAspectCameraData perspectiveData,
// perspectiveData.cameraData.range.hither = 0.0;
// perspectiveData.cameraData.range.yon = 1000.0
// perspectiveData.cameraData.viewPort.origin.x = -1.0
// perspectiveData.cameraData.viewPort.origin.y = 1.0
// perspectiveData.cameraData.viewPort.width = 2.0
// perspectiveData.cameraData.viewPort.height = 2.0
// perspectiveData.fov = 1.0
// perspectiveData.aspectRatioXToY =
// (float) (theWindow->portRect.right -
theWindow->portRect.left) /
// (float) (theWindow->portRect.bottom -
theWindow->portRect.top)
const TQ3ColorRGB backgroundColor
// color of background
);
void GenerateView(
TQ3CameraPlacement viewPoint
);
void TermFlyBy(void);
#if defined(__cplusplus)
}
#endif
Your code consists of three routines: InitFlyBy. called once for each terrain map;
GenerateView, called repeatedly with different view positions as you fly through the
terrain; and TermFlyBy, called at the end of each flight.
InitFlyBy is given everything needed to describe the scene to be generated except the
viewPoint. The terrain consists of numPoints terrain coordinates provided in
thePoints. The terrain is divided into numTriangles triangles, provided in
theTriangles, each of which is described by 3 pointIndices into thePoints array, plus a
color for the triangle.
Each time GenerateView is called, the terrain should be displayed in theWindow from
the viewPoint using the projection information provided in perspectiveData. The
projection will be a perspective, as opposed to an orthographic, projection, described
using the TQ3ViewAngleAspectCameraData structure. The range, viewPort, fov, and
aspectRationXToY elements of that structure are guaranteed to be defined using the
simplifying values shown in the prototype commentary above.
Triangles should be displayed in the triangleColor, and areas of the scene not included
in theTriangles should be displayed in the backgroundColor.
To optimize your code, you can rely on the fact that the viewPoint cameraLocation
provided on successive calls to GenerateView will not change very much, simulating an
actual flight. Similarly, the viewPoint pointOfInterest that determines the viewing
direction, and the viewPoint upVector that governs orientation will not change by large
amounts. They will change as the simulated flying machine banks and turns to avoid
terrain.
A more realistic FlyBy Challenge would include one or more light sources, an
illumination model, and the projection of shadows. For simplicity, we'll omit those
minor details. We'll also allow you to fly without worrying about intersecting the
terrain ("crashing") - the test code won't do that.
TermFlyBy should deallocate any dynamically allocated memory. Remember, your
solutions need to properly initialize and clean up after themselves so they can be
executed repeatedly.
Information on QuickDraw3D data structures can be found
at:http://developer.apple.com/techpubs/quicktime/qtdevdocs/QD3D/qd3d_book.htm
The winner will be the solution that accurately depicts multiple flights through
terrain using the least amount of execution time. This will be a native PowerPC
Challenge, using the latest CodeWarrior environment. Solutions may be coded in C,
C++, or Pascal.
Three Months Ago Winner
Congratulations to Ernst Munter (Kanata, Ontario) for submitting the winning
solution to the May "Piper" Challenge. The Challenge, based on a TidBITS column by
Rick Holzgrafe, was to map a string of characters into the smallest rectangle, placing
adjacent characters in the string into adjacent positions (horizontally, vertically, or
diagonally). The rules allowed (and encouraged) characters to be reused, so that a
string like "How much wood would a woodchuck chuck if a woodchuck could chuck
wood?" can be mapped into a compact 4x4 rectangle:
hwhu
oocm
udwk
lafi
Five people submitted entries to this Challenge, and I also evaluated a version of Rick
Holzgrafe's code, modified to work with the API specified by the problem statement.
Scoring was based on the area of the rectangle produced by the solution, with a 1%
penalty added for each second of execution time. I evaluated the entries using 5 test
cases with input strings ranging from 38 characters to 198 characters. Besides
chucking wood, the entries had the opportunity to pick pickled peppers, sell sea shells
by the sea shore, travel to St. Ives with the man with seven wives, and chow down on