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);

};

 
AAPL
$95.60
Apple Inc.
-2.55
MSFT
$43.16
Microsoft Corpora
-0.42
GOOG
$571.60
Google Inc.
-15.82

MacTech Search:
Community Search:

Software Updates via MacUpdate

OneNote 15.2 - Free digital notebook fro...
OneNote is your very own digital notebook. With OneNote, you can capture that flash of genius, that moment of inspiration, or that list of errands that’s too important to forget. Whether you’re at... Read more
iStat Menus 4.22 - Monitor your system r...
iStat Menus lets you monitor your system right from the menubar. Included are 8 menu extras that let you monitor every aspect of your system. Some features: CPU -- Monitor cpu usage. 7 display... Read more
Ember 1.8 - Versatile digital scrapbook....
Ember (formerly LittleSnapper) is your digital scrapbook of things that inspire you: websites, photos, apps or other things. Just drag in images that you want to keep, organize them into relevant... Read more
OmniPlan 2.3.6 - Robust project manageme...
With OmniPlan, you can create logical, manageable project plans with Gantt charts, schedules, summaries, milestones, and critical paths. Break down the tasks needed to make your project a success,... Read more
Command-C 1.1.1 - Clipboard sharing tool...
Command-C is a revolutionary app which makes easy to share your clipboard between iOS and OS X using your local WiFi network, even if the app is not currently opened. Copy anything (text, pictures,... Read more
Knock 1.1.7 - Unlock your Mac by knockin...
Knock is a faster, safer way to sign in. You keep your iPhone with you all the time. Now you can use it as a password. You never have to open the app -- just knock on your phone twice, even when it's... Read more
Mellel 3.3.6 - Powerful word processor w...
Mellel is the leading word processor for OS X and has been widely considered the industry standard since its inception. Mellel focuses on writers and scholars for technical writing and multilingual... Read more
LibreOffice 4.3.0.4 - Free Open Source o...
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
Freeway Pro 7.0 - Drag-and-drop Web desi...
Freeway Pro lets you build websites with speed and precision... without writing a line of code! With it's user-oriented drag-and-drop interface, Freeway Pro helps you piece together the website of... Read more
Drive Genius 3.2.4 - Powerful system uti...
Drive Genius is an OS X utility designed to provide unsurpassed storage management. Featuring an easy-to-use interface, Drive Genius is packed with powerful tools such as a drive optimizer, a... Read more

Latest Forum Discussions

See All

Dawn of the Immortals Review
Dawn of the Immortals Review By Jennifer Allen on July 31st, 2014 Our Rating: :: RESPECTABLE EXPLORATIONUniversal App - Designed for iPhone and iPad Dawn of the Immortals might not re-invent the wheel, but it does tweak it a little... | Read more »
80 Days Review
80 Days Review By Jennifer Allen on July 31st, 2014 Our Rating: :: EPIC ADVENTUREUniversal App - Designed for iPhone and iPad A fantastic and fascinating re-envisioning of the classic novel by Jules Verne, 80 Days is a delightful... | Read more »
Battleheart Legacy Guide
The world of Battleheart Legacy is fun and deep; full of wizards, warriors, and witches. Here are some tips and tactics to help you get the most enjoyment out of this great game. | Read more »
Puzzle Roo Review
Puzzle Roo Review By Jennifer Allen on July 31st, 2014 Our Rating: :: PUZZLE-BASED TWISTUniversal App - Designed for iPhone and iPad A different take on the usual block dropping puzzle game, Puzzle Roo is quite pleasant.   | Read more »
Super Crossfire Re-Release Super Crossfi...
Super Crossfire Re-Release Super Crossfighter Coming Soon, Other Radiangames Titles Go 50% Off Posted by Ellis Spice on July 31st, 2014 [ | Read more »
Hexiled Review
Hexiled Review By Rob Thomas on July 31st, 2014 Our Rating: :: HEX SELLSUniversal App - Designed for iPhone and iPad In space, no one can hear you… spell? Hexiled is a neat concept for a word scramble puzzle, but it doesn’t go too... | Read more »
Summoners War: Sky Arena Passes 10 Milli...
Summoners War: Sky Arena Passes 10 Million Installs! Posted by Jessica Fisher on July 31st, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Deep Loot Review
Deep Loot Review By Jennifer Allen on July 31st, 2014 Our Rating: :: DIVE DEEPUniversal App - Designed for iPhone and iPad Dive deep in this fun explore-em-up that’s a little grind heavy but ultimately quite entertaining.   | Read more »
Despicable Me: Minion Rush is One Year O...
Despicable Me: Minion Rush is One Year Old, Gets its Biggest Update Yet Posted by Jennifer Allen on July 31st, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Fish & Shark Review
Fish & Shark Review By Jordan Minor on July 31st, 2014 Our Rating: :: FLAPPY FISHUniversal App - Designed for iPhone and iPad Fish & Shark’s beauty is only scale deep.   | Read more »

Price Scanner via MacPrices.net

All Over For Tablets Or Just A Maturing, Evol...
CNN’s David Goldman weighs in on tablet sector doom and gloom, asking rhetorically: “Is this the beginning of the end for the tablet?” Answering that, he contends that hysteria and panic are... Read more
Letterspace 1.0.1 – New Free iOS Text Editor...
Bangkok, Thailand based independent developer Sittipon Simasanti has released Letterspace, a new text editor for iPhone, iPad, and iPod touch devices. Letterspace is a note taking app with an... Read more
Save up to $130 on an iPad mini with Apple re...
The Apple Store has Certified Refurbished 2nd generation iPad minis with Retina Displays available for up to $130 off the cost of new models, starting at $339. Apple’s one-year warranty is included... Read more
iPad Cannibalization Threat “Overblown”
Seeking Alpha’s Kevin Greenhalgh observes that while many commentators think Apple’s forthcoming 5.5-inch panel iPhone 6 will cannibalize iPad sales, in his estimation, these concerns are being... Read more
Primate Labs Releases July 2014 MacBook Pro P...
Primate Labs’ John Poole has posted Geekbench 3 results for most of the new MacBook Pro models that Apple released on Tuesday. Poole observes that overall performance improvements for the new MacBook... Read more
Apple Re-Releases Bugfixed MacBook Air EFI Fi...
Apple has posted a bugfixed version EFI Firmware Update 2.9 a for MacBook Air (Mid 2011) models. The update addresses an issue where systems may take longer to wake from sleep than expected, and... Read more
Save $50 on the 2.5GHz Mac mini, plus free sh...
B&H Photo has the 2.5GHz Mac mini on sale for $549.99 including free shipping. That’s $50 off MSRP, and B&H will also include a free copy of Parallels Desktop software. NY sales tax only. Read more
Save up to $140 on an iPad Air with Apple ref...
Apple is offering Certified Refurbished iPad Airs for up to $140 off MSRP. Apple’s one-year warranty is included with each model, and shipping is free. Stock tends to come and go with some of these... Read more
$250 price drop on leftover 15-inch Retina Ma...
B&H Photo has dropped prices on 2013 15″ Retina MacBook Pros by $250 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.3GHz Retina MacBook Pro: $2249, $250 off... Read more
More iPad Upgrade Musings – The ‘Book Mystiqu...
Much discussed recently, what with Apple reporting iPad sales shrinkage over two consecutive quarters, is that it had apparently been widely assumed that tablet users would follow a two-year hardware... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Sr. Product Leader, *Apple* Store Apps - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full Read more
Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.