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
$102.50
Apple Inc.
+0.25
MSFT
$45.43
Microsoft Corpora
+0.55
GOOG
$571.60
Google Inc.
+2.40

MacTech Search:
Community Search:

Software Updates via MacUpdate

VueScan 9.4.41 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
Cloud 3.0.0 - File sharing from your men...
Cloud is simple file sharing for the Mac. Drag a file from your Mac to the CloudApp icon in the menubar and we take care of the rest. A link to the file will automatically be copied to your clipboard... Read more
LibreOffice 4.3.1.2 - 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
SlingPlayer Plugin 3.3.20.505 - Browser...
SlingPlayer is the screen interface software that works hand-in-hand with the hardware inside the Slingbox to make your TV viewing experience just like that at home. It features an array of... Read more
Get Lyrical 3.8 - Auto-magically adds ly...
Get Lyrical auto-magically add lyrics to songs in iTunes. You can choose either a selection of tracks, or the current track. Or turn on "Active Tagging" to get lyrics for songs as you play them.... Read more
Viber 4.2.2 - Send messages and make cal...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device,... Read more
Cocktail 7.6 - General maintenance and o...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
LaunchBar 6.1 - Powerful file/URL/email...
LaunchBar is an award-winning productivity utility that offers an amazingly intuitive and efficient way to search and access any kind of information stored on your computer or on the Web. It provides... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
BBEdit 10.5.12 - Powerful text and HTML...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more

Latest Forum Discussions

See All

Rhonna Designs Magic (Photography)
Rhonna Designs Magic 1.0 Device: iOS Universal Category: Photography Price: $1.99, Version: 1.0 (iTunes) Description: Want to sprinkle *magic* on your photos? With RD Magic, you can add colors, filters, light leaks, bokeh, edges,... | Read more »
This Week at 148Apps: August 25-29, 2014
Shiny Happy App Reviews   | Read more »
Qube Kingdom – Tips, Tricks, Strategies,...
Qube Kingdom is a tower defense game from DeNA. You rally your troops – magicians, archers, knights, barbarians, and others – and fight against an evil menace looking to dominate your kingdom of tiny squares. Planning a war isn’t easy, so here are a... | Read more »
Qube Kingdom Review
Qube Kingdom Review By Nadia Oxford on August 29th, 2014 Our Rating: :: KIND OF A SQUARE KINGDOMUniversal App - Designed for iPhone and iPad Qube Kingdom has cute visuals, but it’s a pretty basic tower defense game at heart.   | Read more »
Fire in the Hole Review
Fire in the Hole Review By Rob Thomas on August 29th, 2014 Our Rating: :: WALK THE PLANKUniversal App - Designed for iPhone and iPad Seafoam’s Fire in the Hole looks like a bright, 8-bit throwback, but there’s not enough booty to... | Read more »
Alien Creeps TD is Now Available Worldwi...
Alien Creeps TD is Now Available Worldwide Posted by Ellis Spice on August 29th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Dodo Master Review
Dodo Master Review By Jordan Minor on August 29th, 2014 Our Rating: :: NEST EGGiPad Only App - Designed for the iPad Dodo Master is tough but fair, and that’s what makes it a joy to play.   | Read more »
Motorsport Manager Review
Motorsport Manager Review By Lee Hamlet on August 29th, 2014 Our Rating: :: MARVELOUS MANAGEMENTUniversal App - Designed for iPhone and iPad Despite its depth and sense of tactical freedom, Motorsport Manager is one of the most... | Read more »
Motorsport Manager – Beginner Tips, Tric...
The world of Motorsport management can be an unforgiving and merciless one, so to help with some of the stress that comes with running a successful race team, here are a few hints and tips to leave your opponents in the dust. | Read more »
CalPal Update Brings the App to 2.0, Add...
CalPal Update Brings the App to 2.0, Adds Lots of New Stuff Posted by Ellis Spice on August 29th, 2014 [ permalink ] | Read more »

Price Scanner via MacPrices.net

The Rise of Phablets
Carlisle & Gallagher Consulting Group, a businesses and technology consulting firm focused solely on the financial services industry, has released an infographic depicting the convergence of... Read more
Eddy – Cloud Music Player for iPhone/iPad Fre...
Ukraine based CapableBits announces the release of Eddy, its tiny, but smart and powerful cloud music player for iPhone and iPad that allows users to stream or download music directly from cloud... Read more
A&D Medical Launches Its WellnessConnecte...
For consumers and the healthcare providers and loved ones who care for them, A&D Medical, a leader in connected health and biometric measurement devices and services, has launched its... Read more
Anand Lal Shimpi Retires From AnandTech
Anand Lal Shimpi, whose AnandTech Website is famous for its meticulously detailed and thoroughgoing reviews and analysis, is packing it in. Lal Shimpi, who founded the tech site at age 14 in 1997,... Read more
2.5GHz Mac mini, Apple refurbished, in stock...
The Apple Store has Apple Certified Refurbished 2.5GHz Mac minis available for $509, $90 off MSRP. Apple’s one-year warranty is included, and shipping is free. Read more
13-inch 2.5GHz MacBook Pro on sale for $999,...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $999.99 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more
Labor Day Weekend MacBook Pro sale; 15-inch m...
B&H Photo has the new 2014 15″ Retina MacBook Pros on sale for up to $125 off MSRP. Shipping is free, and B&H charges NY sales tax only. They’ll also include free copies of Parallels Desktop... Read more
Labor Day Weekend iPad mini sale; $50 to $100...
Best Buy has the iPad mini with Retina Display (WiFi models) on sale for $50 off MSRP on their online store for Labor Day Weekend. Choose free shipping or free local store pick up. Price is for... Read more
13-inch 1.4GHz MacBook Air on sale for $899,...
Adorama has the new 2014 13″ 1.4GHz/128GB MacBook Air on sale for $899.99 including free shipping plus NY & NJ tax only. Their price is $100 off MSRP. Read more
It’s Official: Apple Issues Invitations To Se...
Apple has issued one of its characteristically cryptic press invitations for a special event to be held at the Flint Center for the Performing Arts in hometown Cupertino on Sept. 9, 2014 at 10:00 am... 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
*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
*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
*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
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.