home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / sdk / graphics / gdi / mandel / bndscan.c next >
C/C++ Source or Header  |  1997-10-05  |  13KB  |  476 lines

  1. /******************************Module*Header*******************************\
  2. * Module Name: bndscan.c
  3. *
  4. * Contains the boundary scaning functions
  5. *
  6. * Created: 14-Apr-1992 10:59:52
  7. *
  8. * Copyright (C) 1993-1997 Microsoft Corporation
  9. *
  10. \**************************************************************************/
  11. #include <windows.h>
  12. #include <stdio.h>
  13. #include "jtypes.h"
  14. #include "bndscan.h"
  15.  
  16. BOOL    bBoundaryScanFix(PINFO);
  17. LPPOINT pptTrace(LONG, LONG, PINFO, INT *, HDC);
  18. DWORD    dwGetNextBoundaryPoint(DWORD, POINT, LPPOINT, PINFO);
  19. BOOL    bEscape(POINT, LONG, LONG, LONG, LONG, int, RECT);
  20. BOOL    bDirToPt(DWORD, POINT, LPPOINT);
  21. DWORD   dwShift(DWORD, int, int);
  22.  
  23. /******************************Public*Routine******************************\
  24. *
  25. * bBoundaryScanFix
  26. *
  27. * Effects:  Traces the outline of the mandelbrot set.  Currently,
  28. *           1. Uses the old method to set the color of each pixel
  29. *           2. Remember the first pixel from top that doesn't escape
  30. *              st we can do boundary trace later.
  31. *           3. When the whole set is done, do boundary trace.
  32. *           4. Store the boundary points in an array. Then build a path.
  33. *           5. Converts the path to region and then select the region as
  34. *              current clip region.
  35. *
  36. * Warnings: Only traces the first non-singular pixel island from top.
  37. \**************************************************************************/
  38.  
  39. BOOL bBoundaryScanFix(PINFO pInfo)
  40. {
  41.     DWORD       dwTick1;
  42.     int         m, n, o, p;
  43.     HDC         hDC;
  44.     RECT        rc;
  45.     LONG        c1, c2;
  46.     LONG        x0, y0;
  47.     int         iIteration;
  48.     LPPOINT     lpPt;
  49.     int     iCount;
  50.     POINT    Pt;
  51.     BOOL        bFirstPtSet;
  52.  
  53.     pInfo->bMandel = TRUE;
  54.     pInfo->bDrawing = TRUE;
  55.     bFirstPtSet = FALSE;
  56.     iIteration = pInfo->iIteration;
  57.     hDC = GetDC(pInfo->hwnd);
  58.     GetClientRect(pInfo->hwnd, &rc);
  59.  
  60.     dwTick1 = GetTickCount();
  61.     for (n=rc.bottom/2; n<=rc.bottom; n++) {
  62.     c2 = y0 = XformFix(n, rc.top, rc.bottom, pInfo->lyFrom, pInfo->lyTo);
  63.  
  64.         for (m=rc.left; m<=rc.right; m++) {
  65.         c1 = x0 = XformFix(m, rc.left, rc.right, pInfo->lxFrom, pInfo->lxTo);
  66.         Pt.x = m;
  67.         Pt.y = n;
  68.         if (bEscape(Pt, x0, y0, c1, c2, iIteration, rc)) {
  69.                 //SetPixel(hDC, m, n, 0x000000ff);
  70.             } else {
  71.  
  72.                 if (!bFirstPtSet)
  73.                 {
  74.                     o = m;
  75.                     p = n;
  76.                     bFirstPtSet = TRUE;
  77.                 }
  78.                 goto BOUNDTRACE;
  79.             }
  80.         }
  81.     }
  82.  
  83. BOUNDTRACE:
  84.  
  85.     SelectObject(hDC, hpnBlack);
  86.     if ((lpPt = pptTrace(o, p, pInfo, &iCount, hDC)) == NULL)
  87.     {
  88.         m = o+1;
  89.  
  90.         for (n=p; n<=rc.bottom; n++) {
  91.         c2 = y0 = XformFix(n, rc.top, rc.bottom, pInfo->lyFrom, pInfo->lyTo);
  92.  
  93.             while (m <= rc.right)
  94.             {
  95.             c1 = x0 = XformFix(m, rc.left, rc.right, pInfo->lxFrom, pInfo->lxTo);
  96.             Pt.x = m;
  97.             Pt.y = n;
  98.  
  99.             if (!bEscape(Pt, x0, y0, c1, c2, iIteration, rc))
  100.                 {
  101.                     o = m;
  102.                     p = n;
  103.                     goto BOUNDTRACE;
  104.                 }
  105.  
  106.                 m++;
  107.             }
  108.             m = rc.left;
  109.         }
  110.     }
  111.  
  112.     if (!BeginPath(hDC)) {
  113.         sprintf( gtext,"Failing in BeginPath!\n");
  114.         OutputDebugString( gtext );
  115.     }
  116.  
  117.     MoveToEx(hDC, m, n, NULL);
  118.     Polyline(hDC, lpPt, iCount);
  119.  
  120.     if (EndPath(hDC)) {
  121.         StrokePath(hDC);
  122.     }
  123.  
  124.     //
  125.     // Stroking discards the path
  126.     //
  127.     if (!BeginPath(hDC)) {
  128.         sprintf( gtext,"Failing in BeginPath!\n");
  129.         OutputDebugString( gtext );
  130.     }
  131.  
  132.     MoveToEx(hDC, m, n, NULL);
  133.     Polyline(hDC, lpPt, iCount);
  134.  
  135.     if (EndPath(hDC)) {
  136.         //
  137.         // Convert the path to region
  138.         //
  139.         pInfo->hRgnPath = PathToRegion(hDC);
  140.  
  141. #if 0
  142.         //
  143.         // Can't use SelectClipPath to set the clipping region here
  144.         // because we are on a different thread.  This is only a cached DC.
  145.         //
  146.         if (SelectClipPath(hDC, RGN_COPY)) {
  147.  
  148.             // Testing if the clip region is effective or not
  149.             //
  150.             //MoveToEx(hDC, 0, 0, NULL);
  151.             //GetClientRect(pInfo->hwnd, &rc);
  152.             //LineTo(hDC, rc.right, rc.bottom);
  153.         }
  154. #endif
  155.     }
  156.  
  157.     if (pInfo->hRgnPath != (HRGN) NULL) {
  158.         //
  159.         // let the main thread who owns the DC to set the clipping region.
  160.         //
  161.         SendMessage(ghwndMain, WM_COMMAND, MM_SELCLIPRGN, 0L);
  162.     }
  163.  
  164.     pInfo->dwElapsed = GetTickCount() - dwTick1;
  165.     pInfo->hBmpSaved = SaveBitmap(pInfo->hwnd, pInfo->hPal);
  166.     pInfo->bDrawing = FALSE;
  167.  
  168.     ReleaseDC(pInfo->hwnd, hDC);
  169.     //
  170.     // GlobalAlloc was called in pptTrace for storing the boundary points
  171.     //
  172.     GlobalFree((HANDLE) lpPt);
  173.     ExitThread(0);
  174.     return TRUE;
  175. }
  176.  
  177. /******************************Public*Routine******************************\
  178. *
  179. * pptTrace
  180. *
  181. * Effects:  Given a boundary point, traces the whole boundary of the
  182. *           set by calling dwGetNextBoundaryPoint() repeatedly.  Returns
  183. *           a pointer to an array of boundary points and also the count
  184. *           of boundary points in the array, if successful.  Otherwise,
  185. *           returns null.
  186. *           m, n is the x, y coordinates of the pixel of the initial
  187. *           boundary point.
  188. *
  189. * Warnings:
  190. *
  191. * History:
  192. *  20-Feb-1992 -by- Petrus Wong
  193. * Wrote it.
  194. \**************************************************************************/
  195.  
  196. LPPOINT pptTrace(LONG m, LONG n, PINFO pInfo, INT * piCount, HDC hDC)
  197. {
  198.     DWORD        dwFace;
  199.     LPPOINT      lpPt, lpTmpPt;
  200.     POINT        Init;
  201.     int          iNumPt;
  202.  
  203.     //
  204.     // MAXPOINT points should be enough for storing the boundary for now.  If
  205.     // it's not enough, it is more likely that it is an error.
  206.     //
  207.     if ((lpPt = (PPOINT) GlobalAlloc(GMEM_FIXED, MAXPOINT * sizeof(POINT))) == NULL) 
  208.     {
  209.         return (LPPOINT) NULL;
  210.     }
  211.     lpTmpPt = lpPt;
  212.     lpPt->x = Init.x = m;
  213.     lpPt->y = Init.y = n;
  214.     lpPt++;
  215.     iNumPt = 1;
  216.     dwFace = dwGetNextBoundaryPoint(EAST, Init, lpPt, pInfo);
  217.     //
  218.     // If can't find next boundary point, return null
  219.     //
  220.     if (dwFace == 0)
  221.         return((LPPOINT)NULL);
  222. //#if 0
  223.     //
  224.     // remove the ifdef if we wanted to see the boundary as we trace
  225.     //
  226.     MoveToEx(hDC, Init.x, Init.y, NULL);
  227.     LineTo(hDC, lpPt->x, lpPt->y);
  228. //#endif
  229.     //
  230.     // Keep looking for next boundary point until I get back to where I
  231.     // started or exceeding MAXPOINT points
  232.     //
  233.     while ((iNumPt < MAXPOINT) &&
  234.            ((lpPt->x != lpTmpPt->x) || (lpPt->y != lpTmpPt->y))) {
  235.         Init.x = lpPt->x;
  236.         Init.y = lpPt->y;
  237.         lpPt++;
  238.         iNumPt++;
  239.     dwFace = dwGetNextBoundaryPoint(dwFace, Init, lpPt, pInfo);
  240.         //
  241.         // If can't find next boundary point, return null
  242.         //
  243.         if (dwFace == 0)
  244.             return((LPPOINT)NULL);
  245. //#if 0
  246.         //
  247.         // remove the ifdef if we wanted to see the boundary as we trace
  248.         //
  249.         MoveToEx(hDC, Init.x, Init.y, NULL);
  250.         LineTo(hDC, lpPt->x, lpPt->y);
  251. //#endif
  252.  
  253.     }
  254.     //
  255.     // It is more likely that it is an error of the algorithm, if ever happens.
  256.     //
  257.     if (iNumPt >= MAXPOINT) 
  258.     {
  259.         OutputDebugString ("Not enough memory!!");
  260.     }
  261.     *piCount = iNumPt;
  262.     return (LPPOINT) lpTmpPt;
  263. }
  264.  
  265.  
  266. /******************************Public*Routine******************************\
  267. *
  268. * dwGetNextBoundaryPoint
  269. *
  270. * Effects:  Start checking the 8 neighbors in clockwise direction.  Returns
  271. *           the first neighbor that does not escape.
  272. *           dwFace      where we face
  273. *           InitPt      where we are right now in pixel coordinates
  274. *
  275. * Warnings: assumes that we start at a boundary point.  Does not trace into
  276. *           a bay if the entrance closed. Ie, it cuts cycle.
  277. *
  278. * History:
  279. *  12-Feb-1992 -by- Petrus Wong
  280. * Wrote it.
  281. \**************************************************************************/
  282.  
  283. DWORD dwGetNextBoundaryPoint(DWORD dwFace, POINT InitPt, LPPOINT lpPt, PINFO pInfo)
  284. {
  285.     BOOL    bEsc;
  286.     DWORD   dwExplore;
  287.     DWORD   dwEnd;
  288.     int     i;
  289.     NODE    arg[8];
  290.     POINT   BndPt;
  291.     LONG    lx, c1, ly, c2;
  292.     RECT    rc;
  293.  
  294.     GetClientRect(pInfo->hwnd, &rc);
  295.     //
  296.     // Start exploring clockwise, ending at where we came from
  297.     //
  298.     dwExplore = dwShift(dwFace, RIGHT, 3);
  299.     dwEnd = dwShift(dwFace, LEFT, 4);
  300.     i = 0;
  301.     bDirToPt(dwExplore, InitPt, &BndPt);
  302.     c1 = lx = XformFix(BndPt.x, rc.left, rc.right, pInfo->lxFrom, pInfo->lxTo);
  303.     c2 = ly = XformFix(BndPt.y, rc.top, rc.bottom, pInfo->lyFrom, pInfo->lyTo);
  304.  
  305.     while (bEsc = bEscape(BndPt, lx, ly, c1, c2, pInfo->iIteration, rc)) {
  306.         arg[i].dwDirection = dwExplore;
  307.         arg[i].bEscape     = TRUE;
  308.  
  309.         i++;
  310.  
  311.         if (dwExplore == dwEnd)
  312.             break;
  313.  
  314.         dwExplore = dwShift(dwExplore, LEFT, 1);
  315.     bDirToPt(dwExplore, InitPt, &BndPt);
  316.     c1 = lx = XformFix(BndPt.x, rc.left, rc.right, pInfo->lxFrom, pInfo->lxTo);
  317.     c2 = ly = XformFix(BndPt.y, rc.top, rc.bottom, pInfo->lyFrom, pInfo->lyTo);
  318.  
  319.     }
  320.  
  321.     if (bEsc) {
  322.         return 0L;
  323.     }
  324.  
  325.     arg[i].dwDirection = dwExplore;
  326.     arg[i].bEscape     = FALSE;
  327.  
  328.     bDirToPt(arg[i].dwDirection, InitPt, lpPt);
  329.  
  330.     return arg[i].dwDirection;
  331. }
  332.  
  333.  
  334.  
  335. /******************************Public*Routine******************************\
  336. *
  337. * bEscape
  338. *
  339. * Effects: Test if the point excapes based on the number of iterations
  340. *
  341. * Warnings:
  342. *
  343. * History:
  344. *  16-Feb-1993      Petrus Wong     9.23 fix
  345. *  20-Feb-1992 -by- Petrus Wong
  346. * Wrote it.
  347. \**************************************************************************/
  348.  
  349. BOOL bEscape(POINT Pt, LONG x, LONG y, LONG c1, LONG c2, int iIteration, RECT rc)
  350. {
  351.     LONG x1, y1, z;
  352.     BOOL bEscape;
  353.     int i;
  354.  
  355.     bEscape = FALSE;
  356.  
  357.     //
  358.     // Treat points outside of client rect as escaping
  359.     //
  360.     if ((Pt.x < rc.left)   || (Pt.x > rc.right-1) ||
  361.         (Pt.y > rc.bottom-1) || (Pt.y < rc.top))     {
  362.         return TRUE;
  363.     }
  364.     for (i=1; i<=iIteration; i++) {
  365.         x1 = lMul(x - y, x + y) + c1;
  366.         y1 = (lMul(x, y) * 2) + c2;
  367.         x = x1;
  368.         y = y1;                             //    2       2     2 1/2     2
  369.         z = lMul(x, x) + lMul(y, y);        // |Z|  = ((x1  + x2 )   ) > 2
  370.  
  371.         if (z > 33554432) {
  372.             bEscape = TRUE;
  373.             break;
  374.         }
  375.     }
  376.     return bEscape;
  377. }
  378.  
  379. /******************************Public*Routine******************************\
  380. *
  381. * bDirToPt
  382. *
  383. * Effects: Returns the pixel coordinates based the direction we are facing
  384. *          and our current position
  385. *
  386. * Warnings:
  387. *
  388. * History:
  389. *  20-Feb-1992
  390. * Wrote it.
  391. \**************************************************************************/
  392.  
  393. BOOL bDirToPt(DWORD dwDirection, POINT InitPt, LPPOINT lpPt)
  394. {
  395.     BOOL bSuccess;
  396.  
  397.     bSuccess = TRUE;
  398.     switch ((LONG)dwDirection) {
  399.         case EAST:
  400.             lpPt->x = InitPt.x+1;
  401.             lpPt->y = InitPt.y;
  402.             break;
  403.         case SOUTHEAST:
  404.             lpPt->x = InitPt.x+1;
  405.             lpPt->y = InitPt.y+1;
  406.             break;
  407.         case SOUTH:
  408.             lpPt->x = InitPt.x;
  409.             lpPt->y = InitPt.y+1;
  410.             break;
  411.         case SOUTHWEST:
  412.             lpPt->x = InitPt.x-1;
  413.             lpPt->y = InitPt.y+1;
  414.             break;
  415.         case WEST:
  416.             lpPt->x = InitPt.x-1;
  417.             lpPt->y = InitPt.y;
  418.             break;
  419.         case NORTHWEST:
  420.             lpPt->x = InitPt.x-1;
  421.             lpPt->y = InitPt.y-1;
  422.             break;
  423.         case NORTH:
  424.             lpPt->x = InitPt.x;
  425.             lpPt->y = InitPt.y-1;
  426.             break;
  427.         case NORTHEAST:
  428.             lpPt->x = InitPt.x+1;
  429.             lpPt->y = InitPt.y-1;
  430.             break;
  431.         default:
  432.             bSuccess = FALSE;
  433.             break;
  434.     }
  435.     return bSuccess;
  436. }
  437.  
  438. /******************************Public*Routine******************************\
  439. *
  440. * dwShift
  441. *                                     NORTH
  442. *                           NW        0x0040        NE
  443. *                               0x0020      0x0080
  444. * Effects:      WEST    0x0010          *           0x0001  EAST
  445. *                               0x0008      0x0002
  446. *                           SW        0x0004        SE
  447. *                                     SOUTH
  448. *
  449. *               Shift dwOpnd left or right by iNum.
  450. *               dwOpnd contains the above values. The shift operation is
  451. *               closed.
  452. *
  453. \**************************************************************************/
  454.  
  455. DWORD dwShift(DWORD dwOpnd, int iDir, int iNum)
  456. {
  457.     DWORD dwTmp;
  458.  
  459.     dwTmp = ((dwOpnd << 8) | dwOpnd);
  460.     switch ((LONG)iDir) {
  461.     case LEFT:
  462.             dwTmp = dwTmp << iNum;
  463.         dwTmp = dwTmp & 0x0ff00;
  464.             dwTmp = dwTmp >> 8;
  465.             break;
  466.     case RIGHT:
  467.             dwTmp = dwTmp >> iNum;
  468.             dwTmp = dwTmp & 0x0ff;
  469.             break;
  470.     default:
  471.             dwTmp = 0L;
  472.         break;
  473.     }
  474.     return dwTmp;
  475. }
  476.