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

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

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.

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

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);
   this->AddChild(aView);
}

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++)
      aView->AddItem(list[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:

Software Updates via MacUpdate

Tunnelblick 3.8.2a - GUI for OpenVPN.
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
calibre 4.17.0 - Complete e-book library...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital librarian... Read more
MacPilot 11.1.4 - $15.96
MacPilot gives you the power of UNIX and the simplicity of Macintosh, which means a phenomenal amount of untapped power in your hands! Use MacPilot to unlock over 1,200 features, and access them all... Read more
Transmission 3.00 - Popular BitTorrent c...
Transmission is a fast, easy, and free multi-platform BitTorrent client. Transmission sets initial preferences so things "just work", while advanced features like watch directories, bad peer blocking... Read more
Doom 3 1.3.1 - First-person shooter acti...
A massive demonic invasion has overwhelmed the Union Aerospace Corporation's (UAC) Mars Research Facility, leaving only chaos and horror in its wake. As one of only a few survivors, you must fight... Read more
Box Sync 4.0.8004 - Online synchronizati...
Box Sync gives you a hard-drive in the Cloud for online storage. Note: You must first sign up to use Box. What if the files you need are on your laptop -- but you're on the road with your iPhone? No... Read more
LibreOffice 6.4.4.2 - Free, open-source...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
Day One 4.14 - Maintain a daily journal.
Day One is an easy, great-looking way to use a journal / diary / text-logging application. Day One is well designed and extremely focused to encourage you to write more through quick Menu Bar entry,... Read more
MenuMeters 2.0.7 - CPU, memory, disk, an...
MenuMeters is a set of CPU, memory, disk, and network monitoring tools for Mac OS X. Although there are numerous other programs which do the same thing, none had quite the feature set I was looking... Read more
War Thunder 1.97.2.19 - Multiplayer war...
In War Thunder, aircraft, attack helicopters, ground forces and naval ships collaborate in realistic competitive battles. You can choose from over 1,500 vehicles and an extensive variety of combat... Read more

Latest Forum Discussions

See All

SINoALICE, Yoko Taro and Pokelabo's...
Yoko Taro and developer Pokelabo's SINoALICE has now opened for pre-registration over on the App Store. It's already amassed 1.5 million Android pre-registrations, and it's currently slated to launch on July 1st. [Read more] | Read more »
Masketeers: Idle Has Fallen's lates...
Masketeers: Idle Has Fallen is the latest endeavour from Appxplore, the folks behind Crab War, Thor: War of Tapnarok and Light A Way. It's an idle RPG that's currently available for Android in Early Access and will head to iOS at a later date. [... | Read more »
Evil Hunter Tycoon celebrates 2 million...
Evil Hunter Tycoon has proved to be quite the hit since launching back in March, with its most recent milestone being 2 million downloads. To celebrate the achievement, developer Super Planet has released a new updated called Darkness' Front Yard... | Read more »
Peak's Edge is an intriguing roguel...
Peak's Edge is an upcoming roguelike puzzle game from developer Kenny Sun that's heading for both iOS and Android on June 4th as a free-to-play title. It will see players rolling a pyramid shape through a variety of different levels. [Read more] | Read more »
Clash Royale: The Road to Legendary Aren...
Supercell recently celebrated its 10th anniversary and their best title, Clash Royale, is as good as it's ever been. Even for lapsed players, returning to the game is as easy as can be. If you want to join us in picking the game back up, we've put... | Read more »
The Magic Gladiator class arrives in MU...
The Magic Gladiator class is now available in MU Origin 2 following the most recent patch. It also marks the start of Abyss Season 11 and the introduction of Couple Skills and Couple Dungeons. [Read more] | Read more »
The 5 Best Racing Games
With KartRider Rush+ making a splash this past week, we figured it was high time we updated our list of the best mobile racing games out there. From realistic racing sims to futuristic arcade racers (and even racing management games!), check out... | Read more »
KartRider Rush+ Guide - Tips for new rac...
KartRider Rush+ continues to be a surprisingly refreshing and fun kart racer that's entirely free-to-play. The main reason for this is just how high its skill ceiling is. Check out the video above if you're curious to know what top level play looks... | Read more »
KartRider Rush+ might be good, actually?
It's hard to find good racing games on mobile. Most of them are free-to-play, and free-to-play racers generally suck. Even Nintendo couldn't put together a competent Mario Kart game, opting instead for a weird score chaser that resembles--but feels... | Read more »
LifeAfter, NetEase's popular surviv...
A new map will be making its way into NetEase's popular survival game LifeAfter. The map is set to arrive on May 28th and will introduce a volcano that's teetering on the verge of eruption, bringing a host of added challenges to the game. [Read... | Read more »

Price Scanner via MacPrices.net

Apple restocks 2019 MacBook Airs starting at...
Apple has clearance, Certified Refurbished, 2019 13″ MacBook Airs available again starting at $779. Each MacBook features a new outer case, comes with a standard Apple one-year warranty, and is... Read more
Apple restocks clearance Mac minis for only $...
Apple has restocked Certified Refurbished 2018 4-Core Mac minis for only $599. Each mini comes with a new outer case plus a standard Apple one-year warranty. Shipping is free: – 3.6GHz Quad-Core... Read more
Apple’s new 2020 13″ MacBook Airs on sale for...
B&H Photo has Apple’s new 2020 13″ 4-Core and 6-Core MacBook Airs on sale today for $50-$100 off Apple’s MSRP, starting at $949. Expedited shipping is free to many addresses in the US. The... Read more
B&H continues to offer clearance 2019 13″...
B&H Photo has clearance 2019 13″ 4-Core MacBook Pros available for up to $300 off Apple’s original MSRP, with prices starting at $1149. Expedited shipping is free to many addresses in the US. B... Read more
Memorial Day Weekend Sale: Take $300 off thes...
Apple resellers are offering $300 discounts on select 16″ MacBook Pros as part of their Memorial Day Weekend 2020 sales. Prices start at $2099: – 16″ 2.6GHz 6-Core Space Gray MacBook Pro: $2099 at... Read more
Best Memorial Day Weekend 2020 Apple AirPods...
Apple resellers are offering discounts ranging up to $50 off MSRP on AirPods as part of their Memorial Day Weekend 2020 sales. These are the best deals today on various AirPods models. See our... Read more
Memorial Day Weekend Sale: 10″ Apple iPads fo...
Amazon is offering new 10.2″ iPads for $80-$100 off Apple’s MSRP as part of their Memorial Day Weekend 2020 sale, with prices starting at only $249. These are the same iPads sold by Apple in their... Read more
Memorial Day Weekend Sale: 2020 Apple iPhone...
Sprint is offering Apple’s new 2020 64GB iPhone SE for $0 per month for 18 months as part of their Memorial Day Weekend 2020 sale. New line of service and trade-in required. Offer is valid from 5/22/... Read more
Amazon’s popular $100 Apple Watch Series 5 di...
Amazon has Apple Watch Series 5 GPS + Cellular models on sale for up to $100 off Apple’s MSRP today. Shipping is free. These are the same Apple Watch models sold by Apple in their retail and online... Read more
2020 13″ 4-Core MacBook Air on sale for $949,...
Apple reseller Adorama has the new 2020 13″ 1.1GHz 4-Core Space Gray MacBook Air on sale today for $949 shipped. Their price is $50 off Apple’s MSRP, and it’s the lowest price currently available for... Read more

Jobs Board

Essbase Developer - *Apple* - Theorem, LLC...
Job Summary Apple is seeking an experienced, detail-minded Essbase developer to join our worldwide business development and strategy team. If you are someone who Read more
Senior Software Engineer @ *Apple* - Theore...
Job Summary Apple is looking for a seasoned senior software engineer to join our worldwide business development and strategy team. This is an opportunity to lead a Read more
Cub Foods - *Apple* Valley - Now Hiring Par...
Cub Foods - Apple Valley - Now Hiring Part Time! United States of America, Minnesota, Apple Valley Retail Operations Post Date May 18, 2020 Requisition # 119230 Read more
Senior Practice Manager - *Apple* Hill Eye...
Senior Practice Manager - Apple Hill Eye Center Tracking Code 61713 Job Description Schedule & Location: Full Time Days Apple Hill Medical Center General Read more
Retail Sales Consultant - *Apple* Valley -...
Retail Sales Consultant - Apple Valley - $500 Hiring Bonus Apply Now...12-30-2019 Address : 7875 150th St W Location : Apple Valley, MN US Req # : 272753BR Job Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.