TweetFollow Us on Twitter

Apr 97 Challenge

Volume Number: 13 (1997)
Issue Number: 4
Column Tag: Programmer's Challenge

Programmer's Challenge

By Bob Boonstra, Westford, MA


For the Challenge this month, we return to the topic of computer graphics - you'll be solving a simplified rendering problem. Your Challenge is to create the image formed by a set of polygons on a specified projection plane, as viewed from a specific viewpoint, and as illuminated from a point light source. You will need to perform hidden surface elimination, create shadows caused by the light source, and project the image as it would be seen by someone at the viewpoint. You will be performing multiple projections from a given viewpoint, so this Challenge includes an initialization routine as well as a calculation routine, both of which are included for timing purposes in determining the winner.

The prototype for the code you should write is:

#define kMAXPOINTS 10

typedef struct My2DPoint {/* point in z==0 plane */
 float x2D; /* x coordinate */
 float y2D; /* y coordinate */
} My2DPoint;

typedef struct My3DPoint {
 float x3D; /* x coordinate */
 float y3D; /* y coordinate */
 float z3D; /* z coordinate */
} My3DPoint;

typedef struct My3DDirection {
 float thetaX;   /* angle in radians */
 float thetaY;   /* angle in radians */
 float thetaZ;   /* angle in radians */
} My3DDirection;

typedef struct MyPlane {
 My3DDirection planeNormal; /* normal vector to plane */
 My3DPointplaneOrigin;  /* origin of plane in 3D space */
} MyPlane;

typedef struct MyPolygon {
 long   numPoints; /* number of points in polygon */
 My2DPointthePoint[kMAXPOINTS];  /* polygon in z==0 plane */
 MyPlanepolyPlane; /* rotate/translate z==0 plane to this plane */
 RGBColor polyColor/* the color to draw this polygon */
} MyPolygon;

void InitProjection(
 My3DPoint*viewPoint,/* viewpoint from which to project */
 My3DPoint*illumPoint,  /* viewpoint from which to draw shadow */
 void   *storage,/* auxiliary storage preallocated for your use */
 long   storageSize/* number of bytes of storage */

void CalcProjection(
 GWorldPtroffScreen, /* GWorld to draw projection */
 MyPolygonthePolys[],/* polygons to project */
 long   numPolys,/* number of polygons to project */
 My3DPoint*viewPoint,/* viewpoint from which to project */
 My3DPoint*illumPoint,  /* illumination point from which to draw
        shadow */
 void   *storage,/* auxiliary storage preallocated for your use */
 long   storageSize/* number of bytes of storage */

Your InitProjection routine will be provided with a pointer to auxiliary storage (storageSize bytes, at least 1MB) preallocated for your use, along with the viewPoint from which projections are to be made and the illumPoint location of an illumination source from which shadows are to be created. InitProjection may perform any calculations that may be useful for multiple CalcProjection calls that follow. CalcProjection will be provided the same parameters given to InitProjection, along with the number (numPolys) and location of the polygons to be projected, and the offScreen GWorld in which the projection is to be drawn. CalcProjection should calculate the way thePolys would look from viewPoint, projected onto a projection plane normal to the viewPoint vector and passing through the origin. Hidden surface elimination must be performed so that obscured polygons or parts of polygons are not seen. The image of the projection is to be rendered in the GWorld pointed to by offScreen, with the projection plane mapped to the z==0 plane in the GWorld. Polygons must be rendered in the appropriate polyColor, subject to the limitations of the GWorld. Polygons are the same color on both sides. Parts of the projection plane not filled by projections of polygons should be black.

In addition to projecting the polygon image as seen from viewPoint, you must also project the shadow of thePolys created by an illumination source at illumPoint, onto the projection plane and onto the image of other polygons, as seen from viewPoint. Shadows should be rendered in the color of the surface in shadow, using a 50% gray pattern. All polygons have a flat matte surface, creating no specular reflections of the illumination source. The illumPoint will be on the same side of the projection plane as the viewPoint.

Polygons are specified in 2-dimensional coordinates in the z==0 plane, to ensure that all points are coplanar, along with a planeNormal vector that specifies the orientation of the polygon plane and a planeOrigin that specifies the plane origin. The last vertex of a polygon is connected to the first vertex to close the polygon (i.e., a square would have four vertices, not a fifth that is the same as the first.) The true polygon coordinates to be projected are calculated by first rotating counterclockwise about the positive z axis by thetaZ (i.e., the positive x axis rotated 90 degrees maps to the positive y axis), then counterclockwise about the positive x axis by thetaX (i.e., positive y rotates to positive z), then counterclockwise about the positive y axis by thetaY (i.e., positive z rotates to positive x), and finally by translating the origin to the planeOrigin point. In matrix form, the transformation is:

 | X |   | x3D |            | x2D |
 | Y | = | y3D | + Ry Rx Rz | y2D |, where
 | Z |   | z3D |            |  0  |

      | cos(thetaZ) -sin(thetaZ)        0     | 
 Rz = | sin(thetaZ)  cos(thetaZ)        0     |
      |       0            0            1     |

      |       1            0            0     |
 Rx = |       0      cos(thetaX) -sin(thetaX) |
      |       0      sin(thetaX)  cos(thetaX) |

      | cos(thetaY)        0      sin(thetaY) | 
 Ry = |       0            1            0     |
      |-sin(thetaY)        0      cos(thetaY) |

The offScreen GWorld will have a pixelDepth of 32. The viewPoint and illumPoint will have z coordinates greater than zero, but thePolys may have coordinates with arbitrary values (after rotating and translating the polyPlane). The projection plane is opaque, meaning that any part of a polygon behind the projection plane is invisible, creating no projection and no shadow.

On average, CalcProjection will be called approximately 10 times with the same viewpoint and illumPoint, but different polygons, for each call to InitProjection. The code producing the fastest projection, including both the InitProjection and CalcProjection times, will be the winner.

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

Perhaps it was the short amount of time to work with the BeOS CD-ROM bundled in the January issue of the magazine, or the fact that the BeOS required a 604 PowerMac, or some minor installation anomalies with the BeOS, or to migration of interest to a prospective NeXT-OS - whatever the reason, only two people entered the BeSort Challenge. Congratulations to Charles Higgins for submitting the fastest solution to the BeSort Challenge. The problem itself was fairly simple: write a SortWindow class that would sort a list of character strings by one of three methods, two specified by the problem statement and one of your own choosing.

Both Charles and the second contestant, Kenneth Slezak, implemented the required bubble sort and exchange sort methods, and both used the quicksort algorithm for the third method. The main difference in efficiency was in the technique used to swap list elements. Charles exchanged the pointers in the list and invalidated the list view to cause the list to be redrawn. Kenneth deleted the items to be exchanged from the list and added the items back into the list in the reverse order. On my 8500, the former was faster by 10+%. Interestingly enough, when run on a BeBox, the latter was ~5% faster. Since the problem statement called for evaluation on the Macintosh, Charles' solution is the winner.

One other interesting observation - in the winning solution, execution time was dominated by display time. I verified this by repeating the timing tests with the windows hidden. In the winning solution, this reduced execution time by almost 80%. In Ken Slezak's solution, execution time was dominated by the list additions/deletions used to swap list elements, so the difference in results is much smaller.

A straightforward optimization to the winning solution improved execution time significantly. Instead of invalidating the ListView each time two elements were exchanged, one need only invalidate the rectangles for the two items being exchanged. This change reduced execution time by some 30% when the windows were visible. (It actually hurt performance when the windows were not visible.)

The table below provides the execution times and code sizes for each two solutions submitted, plus the optimized version of the winning solution. It shows the time, in seconds, required to sort a list of 500 strings by each of the three sort methods, with either visible windows or invisible windows.


Here are the Top Contestants for the Programmer's Challenge. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

1.Munter, Ernst18211.Nicolle, Ludovic21
2.Gregg, Xan11412.Picao, Miguel Cruz21
3.Larsson, Gustav6713.Brown, Jorg20
4.Lengyel, Eric4014.Gundrum, Eric20
5.Lewis, Peter3215.Higgins, Charles20
6.Boring, Randy2716.Kasparian, Raffi20
7.Cooper, Greg2717.Slezak, Ken20
8.Antoniewicz, Andy2418.Studer, Thomas20
9.Beith, Gary2419.Karsh, Bill19
10.Cutts, Kevin2120.Nevard, John17

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place   20 points    5th place              2 points
2nd place   10 points    finding bug            2 points
3rd place    7 points    suggesting Challenge   2 points
4th place    4 points

Here is Charles Higgins' winning solution:


Charles Higgins

#include "SortWindow.h"

void swap(BWindow *aWindow, char **s1, char **s2);
char **addlist( BWindow *aWindow, char **list, int numberOfThings);
SortWindow::SortWindow(BRect frame)
         : BWindow(frame, "Sort", B_TITLED_WINDOW, 0)
   BRect            aRect = frame;
   BListView       *aView;
   aView = new BListView(aRect, "SortView", 
                          B_FOLLOW_ALL, B_WILL_DRAW);

void swap(BWindow *aWindow, char **s1, char **s2)
   BView   *aView;
   char    *temp;
   aView = aWindow->FindView("SortView");
   temp = *s1;
   *s1 = *s2;
   *s2 = temp;

char **addlist( BWindow *aWindow, char **list, int numberOfThings)
   BListView       *aView;
   int              i;
   aView = (BListView*)aWindow->FindView("SortView");
   for(i=0;i< numberOfThings;i++)

void SortWindow::DoSort(
   char *thingsToSort[], int numberOfThings, SortType sortMethod)
   short            i,
                    sorted = FALSE;
   char           **myList;
   myList = addlist( this, thingsToSort, numberOfThings);
      case kBubbleSort:
         i = numberOfThings-1;
               if (0 < strcmp(myList[k],myList[j]))
                  j = k;
            swap( this, &myList[i], &myList[j]);
      case kExchange:
            sorted = TRUE;
               if(0 < strcmp(myList[i],myList[i+1]))
                  sorted = FALSE;
                  swap( this, &myList[i], &myList[i+1]);
      case kMySort:
         QuickSort( myList, 0, numberOfThings);

void SortWindow::QuickSort( char **list, int first, int last)
   int              j,i;

   while(last - first > 1)
      i = first;
      j = last;
         while(++i < last && strcmp(list[i],list[first]) < 0)
         while(-j > first && strcmp(list[j],list[first]) > 0)
         if (i >= j)
         swap( this, &list[i], &list[j]);         
      if( j == first)
      swap( this, &list[first], &list[j]);      
      if(j - first < last - (j+1))
         QuickSort( list,first,j);
         first = j + 1;
         QuickSort( list,j+1,last);
         last = j;


typedef enum SortType {
 kBubbleSort = 1,
 kExchange = 2,
 kExchangeSort = 2,
 kMySort = 3
 } SortType;

class SortWindow : public BWindow {

 SortWindow(BRect frame);

virtual void DoSort( char *thingsToSort[],
     int numberOfThings,
     SortType sortMethod);
virtual void QuickSort( char **list, int first, int last);



Community Search:
MacTech Search:

Software Updates via MacUpdate

Warhammer 40,000: Freeblade guide - How...
Warhammer 40,000: Freebladejust launched in the App Store and it lets you live your childhood dream of blowing up and slashing a bunch of enemies as a massive, hulking Space Marine. It's not easy being a Space Marine though - and particularly if... | Read more »
Gopogo guide - How to bounce like the be...
Nitrome just launched a new game and, as to be expected, it's a lot of addictive fun. It's called Gopogo, and it challenges you to hoparound a bunch of platforms, avoiding enemies and picking up shiny stuff. It's not easy though - just like the... | Read more »
Sago Mini Superhero (Education)
Sago Mini Superhero 1.0 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0 (iTunes) Description: KAPOW! Jack the rabbit bursts into the sky as the Sago Mini Superhero! Fly with Jack as he lifts impossible weights,... | Read more »
Star Wars: Galaxy of Heroes guide - How...
Star Wars: Galaxy of Heroes is all about collecting heroes, powering them up, and using them together to defeat your foes. It's pretty straightforward stuff for the most part, but increasing your characters' stats can be a bit confusing because it... | Read more »
The best cooking apps (just in time for...
It’s that time of year again, where you’ll be gathering around the dinner table with your family and a huge feast in front of you. [Read more] | Read more »
Square Rave guide - How to grab those te...
Square Rave is an awesome little music-oriented puzzle game that smacks of games like Lumines, but with its own unique sense of gameplay. To help wrap your head around the game, keep the following tips and tricks in mind. [Read more] | Read more »
Snowboard Party 2 (Games)
Snowboard Party 2 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Crowned the best snowboarding game available on the market, Snowboard Party is back to fulfill all your adrenaline needs in... | Read more »
One Button Travel (Games)
One Button Travel 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: “To cut a long story short, If you like interactive fiction, just go buy this one.” - “Oozes the polish that... | Read more »
Light Apprentice Volume 1 (Games)
Light Apprentice Volume 1 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Light Apprentice Volume 1 includes Chapters 1 to 4, all gathered in a new exclusive game. When life in the world of... | Read more »
The best games like Animal Crossing on m...
Animal Crossing amiibo Festival is out right now for the Wii U, reminding us of just how much fun that world can be. Or at least to go back and check in on our villages once in a while. [Read more] | Read more »

Price Scanner via

iMobie Releases its Ace iOS Cleaner PhoneClea...
iMobie Inc. has announced the new update of PhoneClean 4, its iOS cleaner designed to reclaim wasted space on iPhone/iPad for use and keep the device fast. Alongside, iMobie hosts a 3-day giveaway of... Read more
U.S. Cellular Offering iPad Pro
U.S. Cellular today announced that it is offering the new iPad Pro with Wi-Fi + Cellular, featuring a 12.9-inch Retina display with 5.6 million pixels — the most ever in an iOS device. U.S. Cellular... Read more
Newegg Canada Unveils Black Friday Deals for...
Newegg Canada is offering more than 1,000 deep discounts to Canadian customers this Black Friday, available now through Cyber Monday, with new deals posted throughout the week. “Black Friday is... Read more
Black Friday: Macs on sale for up to $500 off...
BLACK FRIDAY B&H Photo has all new Macs on sale for up to $500 off MSRP as part of their early Black Friday sale including free shipping plus NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $... Read more
Black Friday: Up to $125 off iPad Air 2s at B...
BLACK FRIDAY Walmart has the 16GB iPad Air 2 WiFi on sale for $100 off MSRP on their online store. Choose free shipping or free local store pickup (if available): - 16GB iPad Air 2 WiFi: $399, save $... Read more
Black Friday: iPad mini 4s on sale for $100 o...
BLACK FRIDAY Best Buy has iPad mini 4s on sale for $100 off MSRP on their online store for Black Friday. Choose free shipping or free local store pickup (if available): - 16GB iPad mini 4 WiFi: $299.... Read more
Black Friday: Apple Watch for up to $100 off...
BLACK FRIDAY Apple resellers are offering discounts and bundles with the purchase of an Apple Watch this Black Friday. Below is a roundup of the deals being offered by authorized Watch resellers:... Read more
Black Friday: Target offers 6th Generation iP...
BLACK FRIDAY Save $40 to $60 on a 6th generation iPod touch at Target with free shipping or free local store pickup (if available). Sale prices for online orders only, in-store prices may vary: -... Read more
Black Friday: Walmart and Target offer iPod n...
BLACK FRIDAY Walmart has the 16GB iPod nano (various colors) on sale for $119.20 on their online store for a limited time. That’s $30 off MSRP. Choose free shipping or free local store pickup (if... Read more
Black Friday deals on the Apple Watch and App...
Apple resellers are offering discounts and bundles with the purchase of an Apple Watch this Black Friday weekend. Below is a roundup of the deals being offered by authorized Watch resellers: Apple... Read more

Jobs Board

Storefront Operations Coordinator, *Apple* -...
# Storefront Operations Coordinator, Apple -Latin America Job Number: 43587750 Miami, Florida, United States Posted: Oct. 16, 2015 Weekly Hours: 40.00 **Job Summary** The Read more
*Apple* Enterprise / Government Professional...
# Apple Enterprise / Gove ment Professional Services Engineer Job Number: 42292976 Reston, Virginia, United States Posted: Aug. 18, 2015 Weekly Hours: 40.00 **Job Read more
iOS Wallet & *Apple* Pay Engineer - App...
# iOS Wallet & Apple Pay Engineer Job Number: 40586801 Santa Clara Valley, Califo ia, United States Posted: Nov. 16, 2015 Weekly Hours: 40.00 **Job Summary** The iOS Read more
Software Engineer, *Apple* Watch - Clock Fa...
# Software Engineer, Apple Watch - Clock Face Team Job Number: 44368761 Santa Clara Valley, Califo ia, United States Posted: Nov. 14, 2015 Weekly Hours: 40.00 **Job Read more
Administrative Assistant, *Apple* Online St...
# Administrative Assistant, Apple Online Store Job Number: 43992352 Santa Clara Valley, Califo ia, United States Posted: Nov. 9, 2015 Weekly Hours: 40.00 **Job Summary** Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.