TweetFollow Us on Twitter

Jul 97 Challenge

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

Jul 97 - Programmer's Challenge

by Bob Boonstra, Westford, MA

Disambiguator

The Challenge this month is to write a string completion routine loosely patterned after the keyword lookup facility in the QuickView utility. QuickView will suggest a completion of the keyword as you begin to type it, and update that suggested completion as you continue to type. In the Toolbox Assistant, for example, if you are looking for documentation on InitGraf and type "i", the suggested completion is "iconIDToRgn". As you continue by typing "n", the suggestion becomes "index2Color". Adding "i" yields "initAllPacks"; adding "t" leaves the suggestion intact; adding "g" changes it to "initGDevice". Finally, typing "r" gives the desired "initgraf".

For our disambiguator, you will be given an unsorted list of words and an opportunity to preprocess them. Then you will be given a string to match and asked to return a list of words matching findString. To make the problem more interesting, the match string can contain wild card characters, as described below.

The prototype for the code you should write is:

typedef unsigned long ulong;

void InitDisambiguator(
   const char *const wordList[],   /* words to match against */
   ulong numWords,                 /* number of words in wordList */
   void *privStorage,              /* private storage preinitialized to zero */
   ulong storageSize               /* number of bytes of privStorage */
);

ulong /*numMatch*/ Disambiguator(
   const char *const wordList[],   /* words to match against */
   ulong numWords,                 /* number of words in wordList */
   void *privStorage,              /* private storage */
   ulong storageSize,              /* number of bytes of privStorage */
   char *findString,               /* string to match, includes wild cards */
   char *matchList[]               /* return matched words here */
);

Your InitDisambiguator routine will be called with an unsorted list wordList of numWords null-terminated words to match. The wordList words will include alphanumeric characters, spaces, and underscores. You will also be provided with a pointer privStorage to storageSize bytes of preallocated memory initialized to zero. The amount of storage provided will be at least 20 bytes for each word in wordList, plus one byte for each character in the wordList (including the null byte, and rounded up to a multiple of 4). In other words, storageSize will be no smaller than minStorage, calculated as:

for (minStorage=0,i=0; i<numWords; i++)
   minStorage += 20 + 4*(1+strlen(wordList[i])/4);

InitDisambiguator is not allowed to modify the wordList, but you may store a sorted version of wordList, or pointers to the words in sorted order, in privStorage. The first four parameters provided to Disambiguator will be identical as those provided to InitDisambiguator. In addition, you will be provided with the null-terminated findString and a preallocated array matchList with numWords entries where you are to store pointers to the words that match findString. Your string matches should be case insensitive (i.e., "initgr" matches "InitGraf". The matchList should be returned with the strings ordered in case-insensitive ASCII order (i.e., space < [0..9] < [A-Za-z] < underscore).

The findString may also contain zero or more of the wildcard characters '?', '*', and '+'. The wildcard '?' matches any single character, '*' matches zero or more characters, and '+' matches one or more characters. So, for example, "*graf" matches any string ending in the (case-insensitive) string "graf", while "+1Ind+" matches any string containing "1Ind" between the first and last characters of a word.

For each call to InitDisambiguator, your Disambiguator routine will be called an average of 100 to 1000 times. The winner will be the solution that finds the correct matchList in the minimum amount of time, including the time taken by the initialization routine.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal. The problem is based on a suggestion by Charles Kefauver, who pointed me to an April, 1995, AppleDirections article discussing the user interface for a disambiguator. Charles wins 2 Challenge points for his suggestion.

Three Months Ago Winner

Congratulations to ACC Murphy (Perth, Australia), for submitting the faster (and smaller) of the two entries I received for the Projection Challenge. This problem required contestants to calculate the image of a set of input polygons, including the shadows cast by one polygon on another, given an observation viewpoint and an illumination point.

Both of the submitted solutions used a ray-tracing technique. The winning solution calculates, for each point on the projection plane, the nearest polygon to the viewpoint among those intersecting the ray from the plane to the viewpoint. It then does another ray-trace to determine if there are any other polygons between the illumination point and the projected polygon, identifying the point as being in shadow if an intervening polygon is found.

I ran three test cases, moving the polygons 10 times for a given viewpoint in each case, using a GWorld bounds rectangle slightly smaller than my 1024x768 monitor. As you can see from the execution times, considerable refinement would be needed before this code could be used for animation.

A good discussion of the projection and hidden surface removal algorithms applicable to this problem can be found in the Black Art of Macintosh Game Programming, by Kevin Tieskoetter. In addition to discussing the z-buffer ray-tracing algorithm, it describes another technique for hidden surface removal called the Painter's algorithm. This approach breaks the polygons to be displayed into pieces such that each piece is entirely in front of or entirely behind any other piece, as seen from the viewpoint. The polygons can then be sorted and displayed without looking at each pixel in the image. For our application, two polygon decompositions would be required, one for the image, and one for the shadows.

The table below lists, for each entry, the execution time for each case and the code size. The number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges to date prior to this one.

                      Case 1   Case 2   Case 3    Total       Code
Name                   Time     Time     Time   Time (secs)   Size
A.C.C. Murphy (10)    29.02    23.64    81.61     134.27      4196
Ernst Munter (232)    20.87    58.11    89.76     168.74      7192

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      194       11.   Beith, Gary         24
   2.   Gregg, Xan         114       12.   Cutts, Kevin        21
   3.   Cooper, Greg        54       13.   Nicolle, Ludovic    21
   4.   Larsson, Gustav     47       14.   Picao, Miguel Cruz  21
   5.   Lengyel, Eric       40       15.   Brown, Jorg         20
   6.   Boring, Randy       37       16.   Gundrum, Eric       20
   7.   Mallett, Jeff       37       17.   Higgins, Charles    20
   8.   Lewis, Peter        32       18.   Kasparian, Raffi    20
   9.   Murphy, ACC         30       19.   Slezak, Ken         20
   10.  Antoniewicz, Andy   24       20.   Studer, Thomas      20

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 A.C.C. Murphy's winning solution:
Challenge.p
A.C.C. Murphy

unit Challenge;

(*

Assumptions:
   Storage space must be big enough for 13 floats per polygon
   All points must be significantly smaller in magnitude than BIG_FLOAT = 
      1000000.0
   Polygons are translucent (their colour based uplon lighting is independent 
      of the side of the polygon that is lit)
   50% attenuation of colour is used
   50% attenuation of black is black
      
Method:
   InitProjection is not used
   
   First we precalculate a small bounding sphere for the polygon points.
   Next we get the information about the GWorld to allow direct pixel access.
   Then for each point on the GWorld, we trace the ray from the point to the 
      eye, intersecting it with each polygon and finding the one closes to 
      the eye (furthest forward, since the eye is infront of all polygons).  
      That determines the colour.  We then trace the ray from that intersection 
      point to the light source to determine whether the point is in shadow, 
      and if so we halve the intensity. We set the colour of the pixel and 
      move on.
   
   Optimizations:
      Direct pixel access to the GWorld (known to be 32 bit)
      Bounding sphere used to optimize the ray/polygon intersection test.
      Time is approximately 2 microseconds per pixel per polygon on an 8500.
*)

interface

   uses
      Types, Quickdraw, QDOffscreen;
      
   const
      kMAXPOINTS = 10;

   const
      BIG_FLOAT = 1000000.0;
         
   type
      float = real;
      
   type
      My2DPoint = record (* point in z==0 plane*)
         x2D: float; (* x coordinate*)
         y2D: float; (* y coordinate*)
      end;
      My3DPoint = record
         x3D: float;                 (* x coordinate*)
         y3D: float;                 (* y coordinate*)
         z3D: float;                 (* z coordinate*)
      end;
      My3DDirection = record
         thetaX:float;              (* angle in radians*)
         thetaY:float;              (* angle in radians*)
         thetaZ:float;              (* angle in radians*)
      end;
      MyPlane = record
         planeNormal: My3DDirection; (* normal vector to plane*)
         planeOrigin: My3DPoint;     (* origin of plane in 3D space*)
      end;
      MyPolygon = record
         numPoints: longint;      (* number of points in polygon*)
         thePoint: array[0..kMAXPOINTS-1] of My2DPoint;
                                  (* polygon in z==0 plane*)
         polyPlane: MyPlane;      (* rotate/translate z==0 plane to this plane*)
         polyColor: RGBColor;     (* the color to draw this polygon*)
      end;
      MyPolygonArray = array[0..0] of MyPolygon;
      
         
   procedure InitProjection(
      const viewPoint: My3DPoint;(* viewpoint from which to project*)
      const illumPoint:My3DPoint;(* viewpoint from which to draw shadow*)
      storage: univ Ptr;         (* auxiliary storage preallocated for your use*)
      storageSize: longint       (* number of bytes of storage*)
   );

   procedure CalcProjection(
      offScreen: GWorldPtr;          (* GWorld to draw projection *)
      const thePolys: MyPolygonArray;(* polygons to project *)
      numPolys: longint;             (* number of polygons to project *)
      const viewPoint: My3DPoint;    (* viewpoint from which to project *)
      const illumPoint: My3DPoint;
                               (* illumination point from which to draw shadow *)
      storage: univ Ptr;       (* auxiliary storage preallocated for your use*)
      storageSize: longint     (* number of bytes of storage*)
   );

implementation

   type
      Ray3D = record
         origin: My3DPoint;
         direction: My3DPoint;
      end;
      PolygonExtra = record
         normal, rotX, rotY, center: My3DPoint;
         radius2: float;
      end;
      PolygonExtraArray = array[0..0] of PolygonExtra;
      StorageRecord = record
         poly_extra: PolygonExtraArray;
                  { must be at the end, since it's an extensible array }
      end;
      StorageRecordPtr = ^StorageRecord;
      
   function DotProduct(const src1, src2 : My3DPoint) : float;
   begin
      DotProduct := src1.x3D*src2.x3D +  
                    src1.y3D*src2.y3D +  
                    src1.z3D*src2.z3D;
   end;
   
CrossProduct
   procedure CrossProduct(src1, src2 : My3DPoint; 
                    var dst : My3DPoint);
   begin
      dst.x3D := src1.y3D*src2.z3D - src1.z3D*src2.y3D;
      dst.y3D := src1.z3D*src2.x3D - src1.x3D*src2.z3D;
      dst.z3D := src1.x3D*src2.y3D - src1.y3D*src2.x3D;
   end;
   
AddVectors
   procedure AddVectors(const src1, src2 : My3DPoint; 
                     var dst : My3DPoint);
   begin
      dst.x3D := src1.x3D + src2.x3D;
      dst.y3D := src1.y3D + src2.y3D;
      dst.z3D := src1.z3D + src2.z3D;
   end;
      
SubtractVectors
   procedure SubtractVectors(const src1, src2 : My3DPoint; 
                      var dst : My3DPoint);
   begin
      dst.x3D := src1.x3D - src2.x3D;
      dst.y3D := src1.y3D - src2.y3D;
      dst.z3D := src1.z3D - src2.z3D;
   end;
   
MidPoint
   procedure MidPoint( const src1, src2 : My3DPoint; 
                      var dst : My3DPoint);
   begin
      dst.x3D := (src1.x3D + src2.x3D) / 2;
      dst.y3D := (src1.y3D + src2.y3D) / 2;
      dst.z3D := (src1.z3D + src2.z3D) / 2;
   end;
   
Distance2
   function Distance2( const src1, src2 : My3DPoint) : float;
   begin
      Distance2 := sqr(src1.x3D - src2.x3D) + 
                      sqr(src1.y3D - src2.y3D) + 
                      sqr(src1.z3D - src2.z3D);
   end;
   
ScaleVector
   procedure ScaleVector(const src : My3DPoint; scale : float; 
                      var dst : My3DPoint);
   begin
      dst.x3D := src.x3D * scale;
      dst.y3D := src.y3D * scale;
      dst.z3D := src.z3D * scale;
   end;
      
NormalizeVector
   procedure NormalizeVector(const src : My3DPoint;
                      var dst : My3DPoint);
      var
         length : float;
   begin
      length := sqrt(DotProduct(src,src));   
      dst.x3D := src.x3D / length;
      dst.y3D := src.y3D / length;
      dst.z3D := src.z3D / length;
   end;
   
MakeViewRay
   procedure MakeViewRay(const eye : My3DPoint;
                      x, y, z: float; var ray : Ray3D);
   begin
      ray.origin.x3D := x;
      ray.origin.y3D := y;
      ray.origin.z3D := z;
      ray.direction.x3D := eye.x3D - x;
      ray.direction.y3D := eye.y3D - y;
      ray.direction.z3D := eye.z3D - z;
      NormalizeVector(ray.direction, ray.direction);
   end;
   
RotateX
   procedure RotateX(src : My3DPoint; sinA, cosA : float; 
                      var dst : My3DPoint);
   begin
      dst.x3D := src.x3D;
      dst.y3D := cosA*src.y3D - sinA*src.z3D;
      dst.z3D := sinA*src.y3D + cosA*src.z3D;
   end;
   
RotateY
   procedure RotateY( src : My3DPoint; sinA, cosA : float; 
                      var dst : My3DPoint);
   begin
      dst.x3D := cosA*src.x3D + sinA*src.z3D;
      dst.y3D := src.y3D;
      dst.z3D := -sinA*src.x3D + cosA*src.z3D;
   end;
   
RotateZ
   procedure RotateZ( src : My3DPoint; sinA, cosA : float; 
                      var dst : My3DPoint);
   begin
      dst.x3D := cosA*src.x3D - sinA*src.y3D;
      dst.y3D := sinA*src.x3D + cosA*src.y3D;
      dst.z3D := src.z3D;
   end;
   
PointInPlaneInPolygon
   function PointInPlaneInPolygon( const pt: My2DPoint; const 
               poly: MyPolygon ): boolean;
      function Quadrant( const pt: My2DPoint; x, y: float ): 
                      longint;
      begin
         if pt.x2D > x then begin
            if pt.y2D > y then begin
               Quadrant := 0;
            end else begin
               Quadrant := 3;
            end;
         end else begin
            if pt.y2D > y then begin
               Quadrant := 1;
            end else begin
               Quadrant := 2;
            end;
         end;
      end;
      
      function x_intercept( const pt1, pt2: My2DPoint;
                      yy: float ): 
                      float;
      begin
         x_intercept := pt2.x2D - 
                     ( (pt2.y2D - yy) * 
                        ((pt1.x2D - pt2.x2D)/(pt1.y2D - pt2.y2D)) );
      end;
      
      var
         i, angle, quad, next_quad, delta: longint;
         last_vertex, next_vertex: My2DPoint;
   begin
      angle := 0;
      last_vertex := poly.thePoint[poly.numPoints-1];
      quad := Quadrant( last_vertex, pt.x2D, pt.y2D );
      for i := 1 to poly.numPoints do begin
         next_vertex := poly.thePoint[i-1];
         next_quad := Quadrant( next_vertex, pt.x2D, pt.y2D );
         delta := next_quad - quad;
         case delta of
            3: delta := -1;
            -3: delta := 1;
            2, -2: begin
               if x_intercept( last_vertex, next_vertex, pt.y2D ) > 
                           pt.x2D then begin
                  delta := -delta;
               end;
            end;
            otherwise begin
            end;
         end;
         angle := angle + delta;
         quad := next_quad;
         last_vertex := next_vertex;
      end;
      PointInPlaneInPolygon := (angle = 4) | (angle = -4);
   end;
   
Intersect
   function Intersect(const ray: Ray3D; const poly: MyPolygon; 
         const poly_extra: PolygonExtra; var distance : float; 
         var intersectionPt: My3DPoint) : boolean;
      var
         tempVector : My3DPoint;
         temp1, temp2 : float;
         intersectionPoint : My3DPoint;
         intersection2D : My2DPoint;
         Ib, Ic, Id: float;
   begin
      Intersect := false;

      { intersect ray with sphere }
      SubtractVectors( ray.origin, poly_extra.center,
                            tempVector );
      Ib := 2 * DotProduct( ray.direction, tempVector );
      Ic := DotProduct( tempVector, tempVector ) - 
                            poly_extra.radius2;
      Id := sqr(Ib) - 4.0*Ic;
      if Id >= 0 then begin { yes, ray intersects sphere }
         temp1 := DotProduct( poly.polyPlane.planeOrigin, 
                            poly_extra.normal ) - 
                     DotProduct( poly_extra.normal, ray.origin );
         temp2 := DotProduct(ray.direction, poly_extra.normal);
         if temp2 <> 0 then begin
            distance := temp1 / temp2;
            if distance > 0 then begin
               ScaleVector(ray.direction, distance, intersectionPoint);
               AddVectors(intersectionPoint, ray.origin, 
                           intersectionPoint);
               
               if Distance2(intersectionPoint, poly_extra.center)
                  <= 
                                          poly_extra.radius2 then begin 
                  { intersection point is whithin sphere.  
                     Find out if it is actually in the polygon }
                  intersectionPt := intersectionPoint;
                  { First translate back to the origin }
                  SubtractVectors(intersectionPoint, 
                     poly.polyPlane.planeOrigin,intersectionPoint);
                  intersection2D.x2D := DotProduct(
                     intersectionPoint,
                        poly_extra.rotX );
                  intersection2D.y2D := DotProduct( 
                     intersectionPoint, 
                        poly_extra.rotY );
                  { Then check if it is whithin the polygon }
                  Intersect := PointInPlaneInPolygon
                                                      (intersection2D,poly);
               end;
            end;
         end;
      end;
   end;

InitProjection
   procedure InitProjection(
      const viewPoint: My3DPoint;(* viewpoint from which to project *)
      const illumPoint:My3DPoint;
                                 (* viewpoint from which to draw shadow *)
      storage: univ Ptr;         (* auxiliary storage preallocated for your use *)
      storageSize: longint       (* number of bytes of storage *)
   );
   begin
{$unused( viewPoint, illumPoint, storage, storageSize )}
   end;

PreparsePolygons
   procedure PreparsePolygons( my_storage: StorageRecordPtr;
   numPolys: longint; const thePolys: MyPolygonArray );
      var
         i, j: longint;
         pt: My3DPoint;
         pts: array[1..kMAXPOINTS] of My3DPoint;
         min_x, min_y, min_z, max_x, max_y, max_z: My3DPoint;
         dist_x, dist_y, dist_z, new_radius2: float;
         radius, new_radius, old_to_new: float;
         sinX, cosX, sinY, cosY, sinZ, cosZ: float;
   begin
      for i := 0 to numPolys-1 do begin
         with my_storage^.poly_extra[i], thePolys[i],
         polyPlane.planeNormal do begin
            sinX := sin(thetaX);
            cosX := cos(thetaX);
            sinY := sin(thetaY);
            cosY := cos(thetaY);
            sinZ := sin(thetaZ);
            cosZ := cos(thetaZ);
            normal.x3d := sinY*cosX;
            normal.y3d := -sinX;
            normal.z3d := cosY*cosX;
            rotX.x3D := 1;
            rotX.y3D := 0;
            rotX.z3D := 0;
            RotateZ(rotX, sinZ, cosZ, rotX);
            RotateX(rotX, sinX, cosX, rotX);
            RotateY(rotX, sinY, cosY, rotX);
            rotY.x3D := 0;
            rotY.y3D := 1;
            rotY.z3D := 0;
            RotateZ(rotY, sinZ, cosZ, rotY);
            RotateX(rotY, sinX, cosX, rotY);
            RotateY(rotY, sinY, cosY, rotY);
            
            for j := 1 to numPoints do begin
               pt.x3D := thePoint[j-1].x2D;
               pt.y3D := thePoint[j-1].y2D;
               pt.z3D := 0;
               RotateZ(pt, sinZ, cosZ, pt);
               RotateX(pt, sinX, cosX, pt);
               RotateY(pt, sinY, cosY, pt);
               pts[j] := pt;
               if j = 1 then begin
                  min_x := pt; min_y := pt; min_z := pt;
                  max_x := pt; max_y := pt; max_z := pt;
               end else begin
                  if pt.x3D < min_x.x3D then begin
                     min_x := pt;
                  end;
                  if pt.y3D < min_y.y3D then begin
                     min_y := pt;
                  end;
                  if pt.z3D < min_z.z3D then begin
                     min_z := pt;
                  end;
                  if pt.x3D > max_x.x3D then begin
                     max_x := pt;
                  end;
                  if pt.y3D > max_y.y3D then begin
                     max_y := pt;
                  end;
                  if pt.z3D > max_z.z3D then begin
                     max_z := pt;
                  end;
               end;
            end;
            
            dist_x := Distance2( min_x, max_x );
            dist_y := Distance2( min_y, max_y );
            dist_z := Distance2( min_z, max_z );
            if dist_x > dist_y then begin
               if dist_x > dist_z then begin
                  radius2 := dist_x/4;
                  MidPoint( min_x, max_x, center );
               end else begin
                  radius2 := dist_z/4;
                  MidPoint( min_z, max_z, center );
               end;
            end else begin
               if dist_y > dist_z then begin
                  radius2 := dist_y/4;
                  MidPoint( min_y, max_y, center );
               end else begin
                  radius2 := dist_z/4;
                  MidPoint( min_z, max_z, center );
               end;
            end;
            
            for j := 1 to numPoints do begin
               new_radius2 := Distance2( center, pts[j] );
               if new_radius2 > radius2 then begin
                  radius := sqrt(radius2);
                  new_radius := sqrt(new_radius2);
                  radius2 := (radius + new_radius)/2;
                  old_to_new := radius2 - radius;
                  center.x3D := (radius2*center.x3D + 
                              old_to_new*pts[j].x3D)/radius;
                  center.y3D := (radius2*center.y3D + 
                              old_to_new*pts[j].y3D)/radius;
                  center.z3D := (radius2*center.z3D + 
                              old_to_new*pts[j].z3D)/radius;
                  radius2 := sqr(radius2);
               end;
            end;
         
            AddVectors( polyPlane.planeOrigin, center, center );

         end;
      end;
   end;
   
CalcProjection
   procedure CalcProjection(
      offScreen: GWorldPtr;          (* GWorld to draw projection *)
      const thePolys: MyPolygonArray;(* polygons to project *)
      numPolys: longint;             (* number of polygons to project *)
      const viewPoint: My3DPoint;    (* viewpoint from which to project *)
      const illumPoint: My3DPoint;   (* illumination point from which to draw shadow *)
      storage: univ Ptr;         (* auxiliary storage preallocated for your use *)
      storageSize: longint      (* number of bytes of storage *)
   );
      var
         bounds: Rect;
         x, y : integer;
         colour : RGBColor;
         viewRay : Ray3D;
         lightRay : Ray3D;
         i : integer;
         closestDistance : float;
         closestIntersectionPt: My3DPoint;
         thisDistance : float;
         intersectionPt: My3DPoint;
         intersect_polygon: longint;
         pm: PixMapHandle;
         junk_boolean: boolean;
         pixels: Ptr;
         rowbytes_add: longint;
         my_storage: StorageRecordPtr;
   begin
{$unused( storage, storageSize )}
      my_storage := StorageRecordPtr(storage);

      PreparsePolygons( my_storage, numPolys, thePolys );

      SetGWorld( offScreen, nil );
      bounds := offScreen^.PortRect;
      pm := GetGWorldPixMap( offScreen );
      junk_boolean := LockPixels( pm );
      pixels := GetPixBaseAddr( pm );
      rowbytes_add := band( pm^^.rowBytes, $3FFF ) - 
                                    4 * (bounds.right - bounds.left);

      for y := bounds.top to bounds.bottom-1 do begin
         for x := bounds.left to bounds.right-1 do begin
            MakeViewRay(viewPoint, x, y, 0, viewRay);
            closestDistance := 0.0;
            intersect_polygon := -1;
            for i:= 1 to numPolys do begin
               if Intersect(viewRay, thePolys[i-1], 
                           my_storage^.poly_extra[i-1], thisDistance, 
                           intersectionPt) then begin
                  if (thisDistance > closestDistance) then begin
                     intersect_polygon := i;
                     closestDistance := thisDistance;
                     closestIntersectionPt := intersectionPt;
                  end;
               end
            end;
            if intersect_polygon > 0 then begin
               colour := thePolys[intersect_polygon-1].polyColor;

               MakeViewRay(illumPoint, closestIntersectionPt.x3D, 
                                 closestIntersectionPt.y3D, 
                                 closestIntersectionPt.z3D, lightRay);

               for i:= 1 to numPolys do begin
                  if (intersect_polygon <> i) & 
                     Intersect(lightRay, thePolys[i-1], 
                     my_storage^.poly_extra[i-1], 
                     thisDistance, intersectionPt) then begin
               colour.red := band(colour.red, $0FFFF) div 2;
               colour.green := band(colour.green, $0FFFF) div 2;
               colour.blue := band(colour.blue, $0FFFF) div 2;
                     leave;
                  end
               end;
               
      LongintPtr(pixels)^ := bsl( band(colour.red, $0FF00), 8 ) 
                     + band(colour.green, $0FF00) + 
                        bsr( band(colour.blue, $0FF00), 8 );
            end else begin
               LongintPtr(pixels)^ := 0;
            end;
            longint(pixels) := longint(pixels) + 4;
         end;
         longint(pixels) := longint(pixels) + rowbytes_add;
      end;
   end;

end.

 
AAPL
$99.02
Apple Inc.
+1.35
MSFT
$43.97
Microsoft Corpora
-0.53
GOOG
$590.60
Google Inc.
+1.58

MacTech Search:
Community Search:

Software Updates via MacUpdate

OS X Yosemite Wallpaper 1.0 - Desktop im...
OS X Yosemite Wallpaper is the gorgeous new background image for Apple's upcoming OS X 10.10 Yosemite. This wallpaper is available for all screen resolutions with a source file that measures 5,418... Read more
Acorn 4.4 - Bitmap image editor. (Demo)
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Bartender 1.2.20 - Organize your menu ba...
Bartender lets you organize your menu bar apps. Features: Lets you tidy your menu bar apps how you want. See your menu bar apps when you want. Hide the apps you need to run, but do not need to... Read more
TotalFinder 1.6.2 - Adds tabs, hotkeys,...
TotalFinder is a universally acclaimed navigational companion for your Mac. Enhance your Mac's Finder with features so smart and convenient, you won't believe you ever lived without them. Tab-based... Read more
Vienna 3.0.0 RC 2 :be5265e: - RSS and At...
Vienna is a freeware and Open-Source RSS/Atom newsreader with article storage and management via a SQLite database, written in Objective-C and Cocoa, for the OS X operating system. It provides... Read more
VLC Media Player 2.1.5 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Default Folder X 4.6.7 - Enhances Open a...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click... Read more
TinkerTool 5.3 - Expanded preference set...
TinkerTool is an application that gives you access to additional preference settings Apple has built into Mac OS X. This allows to activate hidden features in the operating system and in some of the... Read more
Audio Hijack Pro 2.11.0 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more
Intermission 1.1.1 - Pause and rewind li...
Intermission allows you to pause and rewind live audio from any application on your Mac. Intermission will buffer up to 3 hours of audio, allowing users to skip through any assortment of audio... Read more

Latest Forum Discussions

See All

Traps n’ Gemstones Review
Traps n’ Gemstones Review By Campbell Bird on July 28th, 2014 Our Rating: :: CASTLEVANIA JONESUniversal App - Designed for iPhone and iPad Fight mummies, dig tunnels, and ride a runaway minecart to discover ancient secrets in this... | Read more »
The Phantom PI Mission Apparition Review
The Phantom PI Mission Apparition Review By Jordan Minor on July 28th, 2014 Our Rating: :: GHOSTS BUSTEDUniversal App - Designed for iPhone and iPad The Phantom PI is an exceedingly clever and well-crafted adventure game.   | Read more »
More Stubies Are Coming Your Way in a Ne...
More Stubies Are Coming Your Way in a New Update Posted by Jessica Fisher on July 28th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
The Great Prank War Review
The Great Prank War Review By Nadia Oxford on July 28th, 2014 Our Rating: :: PRANKING IS SERIOUS BUSINESSUniversal App - Designed for iPhone and iPad Though short, The Great Prank War offers an interesting and fun mix of action and... | Read more »
Marvel Contest of Champions Announced at...
Marvel Contest of Champions Announced at Comic-Con Posted by Jennifer Allen on July 28th, 2014 [ permalink ] Announced over the weekend at San Diego Comic-Con was the fairly exciting looking Marvel Contest of Champions. | Read more »
Teenage Mutant Ninja Turtles Review
Teenage Mutant Ninja Turtles Review By Jennifer Allen on July 28th, 2014 Our Rating: :: DULL SWIPINGUniversal App - Designed for iPhone and iPad The pizza power is weak when it comes to this Teenage Mutant Ninja Turtles game.   | Read more »
Exploration Focused Puzzle Game Beatbudd...
Exploration Focused Puzzle Game Beatbuddy Set to Make Transition from PC to iOS this September Posted by Jennifer Allen on July 28th, 2014 [ permalink ] | Read more »
PlanetHD
PlanetHD By Nadia Oxford on July 28th, 2014 Our Rating: :: SPACE MADNESSUniversal App - Designed for iPhone and iPad PlanetHD will keep players busy for a while, though its unpredictable physics are a handful to deal with.   | Read more »
This Week at 148Apps: July 21-25, 2014
Another Week of Expert App Reviews   At 148Apps, we help you sort through the great ocean of apps to find the ones we think you’ll like and the ones you’ll need. Our top picks become Editor’s Choice, our stamp of approval for apps with that little... | Read more »
Reddme for iPhone - The Reddit Client (...
Reddme for iPhone - The Reddit Client 1.0 Device: iOS iPhone Category: News Price: $.99, Version: 1.0 (iTunes) Description: Reddme for iPhone is an iOS 7-optimized Reddit client that offers a refreshing new way to experience Reddit... | Read more »

Price Scanner via MacPrices.net

13-inch 2.5GHz MacBook Pro on sale for $1099,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $1099.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $100 off MSRP. Price is... Read more
Roundup of Apple refurbished MacBook Pros, th...
The Apple Store has Apple Certified Refurbished 13″ and 15″ MacBook Pros available for up to $400 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. Their prices... Read more
Record Mac Shipments In Q2/14 Confound Analys...
A Seeking Alpha Trefis commentary notes that Apple’s fiscal Q3 2014 results released July 22, beat market predictions on earnings, although revenues were slightly lower than anticipated. Apple’s Mac’... Read more
Intel To Launch Core M Silicon For Use In Not...
Digitimes’ Monica Chen and Joseph Tsai, report that Intel will launch 14nm-based Core M series processors specifically for use in fanless notebook/tablet 2-in-1 models in Q4 2014, with many models to... Read more
Apple’s 2014 Back to School promotion: $100 g...
 Apple’s 2014 Back to School promotion includes a free $100 App Store Gift Card with the purchase of any new Mac (Mac mini excluded), or a $50 Gift Card with the purchase of an iPad or iPhone,... Read more
iMacs on sale for $150 off MSRP, $250 off for...
Best Buy has iMacs on sale for up to $160 off MSRP for a limited time. Choose free home shipping or free instant local store pickup (if available). Prices are valid for online orders only, in-store... Read more
Mac minis on sale for $100 off MSRP, starting...
Best Buy has Mac minis on sale for $100 off MSRP. Choose free shipping or free instant local store pickup. Prices are for online orders only, in-store prices may vary: 2.5GHz Mac mini: $499.99 2.3GHz... Read more
Global Tablet Market Grows 11% in Q2/14 Notwi...
Worldwide tablet sales grew 11.0 percent year over year in the second quarter of 2014, with shipments reaching 49.3 million units according to preliminary data from the International Data Corporation... Read more
New iPhone 6 Models to Have Staggered Release...
Digitimes’ Cage Chao and Steve Shen report that according to unnamed sources in Apple’s upstream iPhone supply chain, the new 5.5-inch iPhone will be released several months later than the new 4.7-... Read more
New iOS App Helps People Feel Good About thei...
Mobile shoppers looking for big savings at their favorite stores can turn to the Goodshop app, a new iOS app with the latest coupons and deals at more than 5,000 online stores. In addition to being a... Read more

Jobs Board

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