Apr 97 Challenge

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

# Programmer's Challenge

By Bob Boonstra, Westford, MA

## Projection

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
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.

## TOP 20 CONTESTANTS

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.

 Rank Name Points Rank Name Points 1. Munter, Ernst 182 11. Nicolle, Ludovic 21 2. Gregg, Xan 114 12. Picao, Miguel Cruz 21 3. Larsson, Gustav 67 13. Brown, Jorg 20 4. Lengyel, Eric 40 14. Gundrum, Eric 20 5. Lewis, Peter 32 15. Higgins, Charles 20 6. Boring, Randy 27 16. Kasparian, Raffi 20 7. Cooper, Greg 27 17. Slezak, Ken 20 8. Antoniewicz, Andy 24 18. Studer, Thomas 20 9. Beith, Gary 24 19. Karsh, Bill 19 10. Cutts, Kevin 21 20. Nevard, John 17

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:

## SortWindow.cpp

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;

aRect.OffsetTo(B_ORIGIN);
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");
aWindow->Lock();
temp = *s1;
*s1 = *s2;
*s2 = temp;
aView->Invalidate();
aWindow->Unlock();
}

char **addlist( BWindow *aWindow, char **list, int numberOfThings)
{
BListView       *aView;
int              i;

aView = (BListView*)aWindow->FindView("SortView");
aWindow->Lock();
for(i=0;i< numberOfThings;i++)
aWindow->Unlock();
return((char**)aView->Items());
}

void SortWindow::DoSort(
char *thingsToSort[], int numberOfThings, SortType sortMethod)
{
short            i,
j,
k,
sorted = FALSE;
char           **myList;

myList = addlist( this, thingsToSort, numberOfThings);
switch(sortMethod)
{
case kBubbleSort:
i = numberOfThings-1;
while(i>0)
{
j=i;
for(k=0;k<i;++k)
{
if (0 < strcmp(myList[k],myList[j]))
j = k;
}
swap( this, &myList[i], &myList[j]);
i-;
}
break;
case kExchange:
while(!sorted)
{
sorted = TRUE;
for(i=0;i<numberOfThings-1;i++)
{
if(0 < strcmp(myList[i],myList[i+1]))
{
sorted = FALSE;
swap( this, &myList[i], &myList[i+1]);
}
}
}
break;
case kMySort:
QuickSort( myList, 0, numberOfThings);
break;
}
memcpy(thingsToSort,myList,numberOfThings*sizeof(char*));
be_app->PostMessage(B_QUIT_REQUESTED);
}

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

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

SortWindow.h

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

class SortWindow : public BWindow {

public:
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:

Microsoft Office 2016 16.11 - Popular pr...
Microsoft Office 2016 - Unmistakably Office, designed for Mac. The new versions of Word, Excel, PowerPoint, Outlook, and OneNote provide the best of both worlds for Mac users - the familiar Office... Read more
Adobe Photoshop CC 2018 19.1.2 - Profess...
Photoshop CC 2018 is available as part of Adobe Creative Cloud for as little as \$19.99/month (or \$9.99/month if you're a previous Photoshop customer). Adobe Photoshop CC 2018, the industry standard... Read more
Adobe Dreamweaver CC 2018 18.1.0.10155 -...
Dreamweaver CC 2018 is available as part of Adobe Creative Cloud for as little as \$19.99/month (or \$9.99/month if you're a previous Dreamweaver customer). Adobe Dreamweaver CC 2018 allows you to... Read more
Adobe Flash Player 29.0.0.113 - Plug-in...
Adobe Flash Player is a cross-platform, browser-based application runtime that provides uncompromised viewing of expressive applications, content, and videos across browsers and operating systems.... Read more
Drive Genius 5.2.0 - \$79.00
Drive Genius features a comprehensive Malware Scan. Automate your malware protection. Protect your investment from any threat. The Malware Scan is part of the automated DrivePulse utility. DrivePulse... Read more
MegaSeg 6.0.6 - Professional DJ and radi...
MegaSeg is a complete solution for pro audio/video DJ mixing, radio automation, and music scheduling with rock-solid performance and an easy-to-use design. Mix with visual waveforms and Magic... Read more
ffWorks 1.0.7 - Convert multimedia files...
ffWorks (was iFFmpeg), focused on simplicity, brings a fresh approach to the use of FFmpeg, allowing you to create ultra-high-quality movies without the need to write a single line of code on the... Read more
Dash 4.1.5 - Instant search and offline...
Dash is an API documentation browser and code snippet manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
Evernote 7.0.3 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
jAlbum Pro 15.3 - Organize your digital...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. You can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly... Read more

## Latest Forum Discussions

Around the Empire: What have you missed...
Oh hi nice reader, and thanks for popping in to check out our weekly round-up of all the stuff that you might have missed across the Steel Media network. Yeah, that's right, it's a big ol' network. Obviously 148Apps is the best, but there are some... | Read more »
All the best games on sale for iPhone an...
It might not have been the greatest week for new releases on the App Store, but don't let that get you down, because there are some truly incredible games on sale for iPhone and iPad right now. Seriously, you could buy anything on this list and I... | Read more »
Everything You Need to Know About The Fo...
In just over a week, Epic Games has made a flurry of announcements. First, they revealed that Fortnite—their ultra-popular PUBG competitor—is coming to mobile. This was followed by brief sign-up period for interested beta testers before sending out... | Read more »
The best games that came out for iPhone...
It's not been the best week for games on the App Store. There are a few decent ones here and there, but nothing that's really going to make you throw down what you're doing and run to the nearest WiFi hotspot in order to download it. That's not to... | Read more »
Death Coming (Games)
Death Coming 1.1.1.536 Device: iOS Universal Category: Games Price: \$1.99, Version: 1.1.1.536 (iTunes) Description: --- Background Story ---You Died. Pure and simple, but death was not the end. You have become an agent of Death: a... | Read more »
Hints, tips, and tricks for Empires and...
Empires and Puzzles is a slick match-stuff RPG that mixes in a bunch of city-building aspects to keep things fresh. And it's currently the Game of the Day over on the App Store. So, if you're picking it up for the first time today, we thought it'd... | Read more »
What You Need to Know About Sam Barlow’s...
Sam Barlow’s follow up to Her Story is #WarGames, an interactive video series that reimagines the 1983 film WarGames in a more present day context. It’s not exactly a game, but it’s definitely still interesting. Here are the top things you should... | Read more »
Pixel Plex Guide - How to Build Better T...
Pixel Plex is the latest city builder that has come to the App Store, and it takes a pretty different tact than the ones that came before it. Instead of being in charge of your own city by yourself, you have to work together with other players to... | Read more »
Fortnite Will Be Better Than PUBG on Mob...
Before last week, if you asked me which game I prefer between Fortnite Battle Royale and PlayerUnknown’s Battlegrounds (PUBG), I’d choose the latter just about 100% of the time. Now that we know that both games are primed to hit our mobile screens... | Read more »
Siege of Dragonspear (Games)
Siege of Dragonspear 2.5.12 Device: iOS Universal Category: Games Price: \$9.99, Version: 2.5.12 (iTunes) Description: Experience the Siege of Dragonspear, an epic Baldur’s Gate tale, filled with with intrigue, magic, and monsters.... | Read more »

## Price Scanner via MacPrices.net

Sunday Sales: \$200 off 13″ Touch Bar MacBook...
Amazon has new 2017 13″ 3.1GHz Touch Bar MacBook Pros on sale this weekend for \$200 off MSRP, each including free shipping: – 13″ 3.1GHz/256GB Space Gray MacBook Pro (MPXV2LL/A): \$1599.99 \$200 off... Read more
B&H drops prices on 15″ MacBook Pros up t...
B&H Photo has dropped prices on new 2017 15″ MacBook Pros, now up to \$300 off MSRP and matching Adorama’s price drop yesterday. Shipping is free, and B&H charges sales tax for NY & NJ... Read more
Apple restocks Certified Refurbished 2017 13″...
Apple has restocked Certified Refurbished 2017 13″ 2.3GHz MacBook Pros for \$200-\$230 off MSRP. A standard Apple one-year warranty is included with each MacBook, models receive new outer cases, and... Read more
13″ Space Gray Touch Bar MacBook Pros on sale...
Adorama has new 2017 13″ Space Gray Touch Bar MacBook Pros on sale for \$150 off MSRP. Shipping is free, and Adorama charges sales tax in NY & NJ only: – 13″ 3.1GHz/256GB Space Gray MacBook Pro (... Read more
Best deal of the year on 15″ Apple MacBook Pr...
Adorama has New 2017 15″ MacBook Pros on sale for up to \$300 off MSRP. Shipping is free, and Adorama charges sales tax in NJ and NY only: – 15″ 2.8GHz Touch Bar MacBook Pro Space Gray (MPTR2LL/A): \$... Read more
Save \$100-\$150+ on 13″ Touch Bar MacBook Pros...
B&H Photo has 13″ Touch Bar MacBook Pros on sale for \$100-\$150 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13″ 3.1GHz/256GB Space Gray MacBook Pro... Read more
Current deals on 27″ Apple iMacs, models up t...
B&H Photo has 27″ iMacs on sale for up to \$150 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 27″ 3.8GHz iMac (MNED2LL/A): \$2149 \$150 off MSRP – 27″ 3... Read more
Thursday Deal: 13″ 2.3GHz MacBook Pro for \$11...
B&H Photo has the 13″ 2.3GHz/128GB Space Gray MacBook Pro on sale for \$100 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13-inch 2.3GHz/128GB Space... Read more
How to save \$100-\$190 on 10″ & 12″ iPad P...
Apple is now offering Certified Refurbished 2017 10″ and 12″ iPad Pros for \$100-\$190 off MSRP, depending on the model. An Apple one-year warranty is included with each model, and shipping is free: –... Read more
Silver 12″ 1.3GHz MacBook on sale at B&H...
B&H Photo has the 2017 12″ 1.3GHz Silver MacBook on sale for \$1399.99 including free shipping plus sales tax for NY & NJ residents only. Their price is \$200 off MSRP, and it’s the lowest... Read more

## Jobs Board

Firmware Engineer - *Apple* Accessories - A...
# Firmware Engineer - Apple Accessories Job Number: 113452350 Santa Clara Valley, California, United States Posted: 28-Feb-2018 Weekly Hours: 40.00 **Job Summary** Read more
Automation and Performance Engineer, *Apple*...
# Automation and Performance Engineer, Apple Pay Job Number: 113557967 Santa Clara Valley, California, United States Posted: 09-Mar-2018 Weekly Hours: 40.00 **Job Read more
Hardware Systems Architect - *Apple* Watch...
# Hardware Systems Architect - Apple Watch Job Number: 113565323 Santa Clara Valley, California, United States Posted: 05-Mar-2018 Weekly Hours: 40.00 **Job Read more
Lead *Apple* Solution Consultant - Apple (U...
# Lead Apple Solution Consultant Chicago IL Job Number: 113560644 Chicago, Illinois, United States Posted: 10-Mar-2018 Weekly Hours: 40.00 **Job Summary** As a Lead Read more
Art Director, *Apple* Music + Beats1 Market...
# Art Director, Apple Music + Beats1 Marketing Design Job Number: 113258081 Culver City, California, United States Posted: 07-Mar-2018 Weekly Hours: 40.00 **Job Read more