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:

## Latest Forum Discussions

Fresh From the Land Down Under – The Tou...
After a two week hiatus, we are back with another episode of The TouchArcade Show. Eli is fresh off his trip to Australia, which according to him is very similar to America but more upside down. Also kangaroos all over. Other topics this week... | Read more »
TouchArcade Game of the Week: ‘Dungeon T...
I’m a little conflicted on this week’s pick. Pretty much everyone knows the legend of Dungeon Raid, the match-3 RPG hybrid that took the world by storm way back in 2011. Everyone at the time was obsessed with it, but for whatever reason the... | Read more »
Hello gentle readers, and welcome to the SwitchArcade Round-Up for July 19th, 2024. In today’s article, we finish up the week with the unusual appearance of a review. I’ve spent my time with Hot Lap Racing, and I’m ready to give my verdict. After... | Read more »
Draknek Interview: Alan Hazelden on Thin...
Ever since I played my first release from Draknek & Friends years ago, I knew I wanted to sit down with Alan Hazelden and chat about the team, puzzle games, and much more. | Read more »
The Latest ‘Marvel Snap’ OTA Update Buff...
I don’t know about all of you, my fellow Marvel Snap (Free) players, but these days when I see a balance update I find myself clenching my… teeth and bracing for the impact to my decks. They’ve been pretty spicy of late, after all. How will the... | Read more »
‘Honkai Star Rail’ Version 2.4 “Finest D...
HoYoverse just announced the Honkai Star Rail (Free) version 2.4 “Finest Duel Under the Pristine Blue" update alongside a surprising collaboration. Honkai Star Rail 2.4 follows the 2.3 “Farewell, Penacony" update. Read about that here. | Read more »
‘Vampire Survivors+’ on Apple Arcade Wil...
Earlier this month, Apple revealed that poncle’s excellent Vampire Survivors+ () would be heading to Apple Arcade as a new App Store Great. I reached out to poncle to check in on the DLC for Vampire Survivors+ because only the first two DLCs were... | Read more »
Homerun Clash 2: Legends Derby opens for...
Since launching in 2018, Homerun Clash has performed admirably for HAEGIN, racking up 12 million players all eager to prove they could be the next baseball champions. Well, the title will soon be up for grabs again, as Homerun Clash 2: Legends... | Read more »
‘Neverness to Everness’ Is a Free To Pla...
Perfect World Games and Hotta Studio (Tower of Fantasy) announced a new free to play open world RPG in the form of Neverness to Everness a few days ago (via Gematsu). Neverness to Everness has an urban setting, and the two reveal trailers for it... | Read more »
Meditative Puzzler ‘Ouros’ Coming to iOS...
Ouros is a mediative puzzle game from developer Michael Kamm that launched on PC just a couple of months back, and today it has been revealed that the title is now heading to iOS and Android devices next month. Which is good news I say because this... | Read more »

## Price Scanner via MacPrices.net

Amazon is still selling 16-inch MacBook Pros...
Prime Day in July is over, but Amazon is still selling 16-inch Apple MacBook Pros for \$500-\$600 off MSRP. Shipping is free. These are the lowest prices available this weekend for new 16″ Apple... Read more
Walmart continues to sell clearance 13-inch M...
Walmart continues to offer clearance, but new, Apple 13″ M1 MacBook Airs (8GB RAM, 256GB SSD) online for \$699, \$300 off original MSRP, in Space Gray, Silver, and Gold colors. These are new MacBooks... Read more
Apple is offering steep discounts, up to \$600...
Apple has standard-configuration 16″ M3 Max MacBook Pros available, Certified Refurbished, starting at \$2969 and ranging up to \$600 off MSRP. Each model features a new outer case, shipping is free,... Read more
Save up to \$480 with these 14-inch M3 Pro/M3...
Apple has 14″ M3 Pro and M3 Max MacBook Pros in stock today and available, Certified Refurbished, starting at \$1699 and ranging up to \$480 off MSRP. Each model features a new outer case, shipping is... Read more
Amazon has clearance 9th-generation WiFi iPad...
Amazon has Apple’s 9th generation 10.2″ WiFi iPads on sale for \$80-\$100 off MSRP, starting only \$249. Their prices are the lowest available for new iPads anywhere: – 10″ 64GB WiFi iPad (Space Gray or... Read more
Apple is offering a \$50 discount on 2nd-gener...
Apple has Certified Refurbished White and Midnight HomePods available for \$249, Certified Refurbished. That’s \$50 off MSRP and the lowest price currently available for a full-size Apple HomePod today... Read more
The latest MacBook Pro sale at Amazon: 16-inc...
Amazon is offering instant discounts on 16″ M3 Pro and 16″ M3 Max MacBook Pros ranging up to \$400 off MSRP as part of their early July 4th sale. Shipping is free. These are the lowest prices... Read more
14-inch M3 Pro MacBook Pros with 36GB of RAM...
B&H Photo has 14″ M3 Pro MacBook Pros with 36GB of RAM and 512GB or 1TB SSDs in stock today and on sale for \$200 off Apple’s MSRP, each including free 1-2 day shipping: – 14″ M3 Pro MacBook Pro (... Read more
14-inch M3 MacBook Pros with 16GB of RAM on s...
B&H Photo has 14″ M3 MacBook Pros with 16GB of RAM and 512GB or 1TB SSDs in stock today and on sale for \$150-\$200 off Apple’s MSRP, each including free 1-2 day shipping: – 14″ M3 MacBook Pro (... Read more
Amazon is offering \$170-\$200 discounts on new...
Amazon is offering a \$170-\$200 discount on every configuration and color of Apple’s M3-powered 15″ MacBook Airs. Prices start at \$1129 for models with 8GB of RAM and 256GB of storage: – 15″ M3... Read more

## Jobs Board

*Apple* Systems Engineer - Chenega Corporati...
…LLC,** a **Chenega Professional Services** ' company, is looking for a ** Apple Systems Engineer** to support the Information Technology Operations and Maintenance Read more
Solutions Engineer - *Apple* - SHI (United...
**Job Summary** An Apple Solution Engineer's primary role is tosupport SHI customers in their efforts to select, deploy, and manage Apple operating systems and Read more
*Apple* / Mac Administrator - JAMF Pro - Ame...
Amentum is seeking an ** Apple / Mac Administrator - JAMF Pro** to provide support with the Apple Ecosystem to include hardware and software to join our team and Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall Read more