« previous next »
Pages: [1]   Go Down

Author Topic: Scan Line Filled Polygon  (Read 3990 times)

0 Members and 1 Guest are viewing this topic.

Offline AndyA

  • Newbie
  • Posts: 73
    • View Profile
Scan Line Filled Polygon
« on: December 02, 2019, 01:35:56 am »
This a fast scan line filled polygon SUB.

In the past I've used it to mask sprites for a jigsaw puzzle game. It's also ALPHA friendly as the lines are only drawn once to fill the polygon.

A bit of preparation is required to use in your own programs.
1)  A list of vertex coordinate pairs that define the polygon. Could be DATA or file on disk.
2) DIM enough array space to hold all of the vertex coordinates and the nodes list.
3) Find or include the bounding box of the polygon.

That's it!

Maybe someone can think of other applications for this SUB.

Code: QB64: [Select]
  1. 'http://alienryderflex.com/polygon_fill/
  2. 'public-domain code by Darel Rex Finley, 2007
  3.  
  4. 'QB64 version by Andy Amaya
  5.  
  6. _TITLE "Scan Line Filled Polygon"
  7.  
  8. DIM SHARED polyX#(500), polyY#(500), nodeX%(500)
  12. COLOR 15, 1
  13. LINE (0, 0)-(639, 479), 1, BF
  14.  
  15. 'Initialize maxima and minima then, find the bounding box of the polygon
  16. minX# = 9999
  17. maxX# = -9999
  18. minY# = 9999
  19. maxY# = -9999
  20.  
  21. scaleX# = 5.2 'X scaling factor
  22. scaleY# = 4.2 'Y scaling factor
  23. offsetX# = 40 'X and Y offsets to place polygon on screen
  24. offsetY# = 18
  25. numVerts% = 62
  26.  
  27. 'Read the polygon vertices into polyX() and poly() arrays
  28. 'Use scaling and offsets before placing into the two arrays
  29. RESTORE jigsawPiece
  30. FOR i% = 0 TO numVerts% - 1 'polygon has 62 sides (zero based counting)
  31.     READ zx%
  32.     READ zy%
  33.     polyX#(i%) = zx% * scaleX# + offsetX#
  34.     polyY#(i%) = zy% * scaleY# + offsetY#
  35.     minX# = min(minX#, polyX#(i%))
  36.     maxX# = max(maxX#, polyX#(i%))
  37.     minY# = min(minY#, polyY#(i%))
  38.     maxY# = max(maxY#, polyY#(i%))
  40.  
  41. st = TIMER(.001)
  42. polyFill numVerts% - 1, minX#, maxX#, minY#, maxY#
  43. et = TIMER(.001) - st
  44.  
  45. PRINT "Polygon with 62 vertices filled in: "; USING "###"; (et * 1000);
  46. PRINT " milliseconds"
  49.  
  50. jigsawPiece:
  51. DATA 4,4,7,2,27,0,36,1,35,6,32,13,32,20,36,24,45,27,61,31
  52. DATA 61,26,57,22,57,19,60,18,75,17,89,21,87,43,85,48,88,53,97,48
  53. DATA 99,47,106,48,107,51,109,58,106,76,103,78,99,75,95,73,93,74,92,82
  54. DATA 93,92,95,104,76,108,69,108,67,104,67,99,70,91,70,85,59,80,47,80
  55. DATA 45,81,46,86,48,92,42,93,22,88,20,87,16,73,15,65,14,58,15,55
  56. DATA 20,55,25,56,30,59,30,56,27,47,25,39,22,35,15,31,9,31,3,35
  57. DATA 0,34,0,27
  58.  
  59. SUB polyFill (numSides%, minX#, maxX#, minY#, maxY#)
  60.     FOR pixelY% = minY# TO maxY#
  61.         nodes% = 0
  62.         j% = numSides% - 1
  63.         fpixY# = pixelY%
  64.         'build node list
  65.         FOR i% = 0 TO numSides% - 1
  66.             b1% = ABS(polyY#(i%) < fpixY#)
  67.             b2% = ABS(polyY#(j%) >= fpixY#)
  68.             b3% = ABS(polyY#(j%) < fpixY#)
  69.             b4% = ABS(polyY#(i%) >= fpixY#)
  70.             IF ((ABS(b1% AND b2%)) OR (ABS(b3% AND b4%))) THEN
  71.                 f1# = fpixY# - polyY#(i%)
  72.                 f2# = polyY#(j%) - polyY#(i%)
  73.                 f3# = polyX#(j%) - polyX#(i%)
  74.                 nodeX%(nodes%) = INT(f1# / f2# * f3# + polyX#(i%))
  75.                 nodes% = nodes% + 1
  76.             END IF
  77.             j% = i%
  78.         NEXT
  79.         'sort nodes
  80.         i% = 0
  81.         WHILE i% < nodes% - 1
  82.             IF (nodeX%(i%) > nodeX%(i% + 1)) THEN
  83.                 SWAP nodeX%(i%), nodeX%(i% + 1)
  84.                 IF (i% > 0) THEN i% = i% - 1
  85.             ELSE
  86.                 i% = i% + 1
  87.             END IF
  88.         WEND
  89.         'draw scanlines
  90.         FOR i% = 0 TO nodes% - 1 STEP 2
  91.             IF (nodeX%(i%) <= maxX#) THEN
  92.                 IF (nodeX%(i% + 1) > minX#) THEN
  93.                     IF (nodeX%(i%) < minX#) THEN nodeX%(i%) = minX#
  94.                     IF (nodeX%(i% + 1) > maxX#) THEN nodeX%(i% + 1) = maxX#
  95.                     LINE (nodeX%(i%), pixelY%)-(nodeX%(i% + 1), pixelY%)
  96.                 END IF
  97.             END IF
  98.         NEXT
  99.     NEXT
  101.  
  102. FUNCTION min# (flt1#, flt2#)
  103.     IF flt1# < flt2# THEN min# = flt1# ELSE min# = flt2#
  105.  
  106. FUNCTION max# (flt1#, flt2#)
  107.     IF flt1# > flt2# THEN max# = flt1# ELSE max# = flt2#
Logged

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Scan Line Filled Polygon
« Reply #1 on: December 02, 2019, 10:01:33 am »
Oh this is interesting, I will give it some study, Thanks Andy!
Logged

Offline RhoSigma

  • QB64 Developer
  • Forum Resident
  • Posts: 565
    • View Profile
Re: Scan Line Filled Polygon
« Reply #2 on: December 02, 2019, 11:03:11 am »
Same here, look into my DRF-Polygons library, I even enhanced the function to draw the surrounding border as well in a different color and made filling/border independently optional.
Logged
My Projects:   https://qb64forum.alephc.xyz/index.php?topic=809
GuiTools - A graphic UI framework (can do multiple UI forms/windows in one program)
Libraries - ImageProcess, StringBuffers (virt. files), MD5/SHA2-Hash, LZW etc.
Bonus - Blankers, QB64/Notepad++ setup pack

Offline AndyA

  • Newbie
  • Posts: 73
    • View Profile
Re: Scan Line Filled Polygon
« Reply #3 on: December 04, 2019, 11:24:20 pm »
Quote
Same here, look into my DRF-Polygons library, I even enhanced the function to draw the surrounding border as well in a different color and made filling/border independently optional.

That's a nice library but for simplicity, I like to use cut and paste-able functions instead of libraries. It's easier for me to follow the dependencies of a single function and make changes when it's not embedded in a library.

Yes drawing the border is a nice touch. I use pretty much the same method in the 'Point in Polygon' function.
https://www.qb64.org/forum/index.php?topic=1945.0

I just decided to omit the Sub for this demo.

Code: QB64: [Select]
  1. 'Code to draw a polygon border
  2. SUB drawPoly (verts AS INTEGER, colr AS INTEGER)
  3.     j% = verts - 1
  4.     FOR i% = 0 TO verts - 1
  5.         'Point in polygon array variables for line drawing
  6.         'LINE (xp(j%), yp(j%))-(xp(i%), yp(i%)), colr%
  7.         'polyFill array variables for line drawing
  8.         LINE (polyX#(j%), polyY#(j%)-(polyX#(i%),polyY#(i%)), colr%
  9.         j% = i%
  10.     NEXT
« Last Edit: December 04, 2019, 11:42:55 pm by AndyA »
Logged

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Scan Line Filled Polygon
« Reply #4 on: December 05, 2019, 01:23:13 pm »
OK I finally got around to conducting some experiments. Alas, I am getting wildly different results comparing Andy's polyFill method with normal PAINT method but I am guessing Andy's polyFill better because it doesn't need the outline needed for PAINT. If I change order Andy's polyFill then PAINT, polyFill is clearly better usually.

Anyway, then I wanted to try paintImage versus polyFillImage and for that Andy's polyFill method is clearly faster though I slowed it down considerably to "paint" the Brick image.

Here are tests I tried:
Code: QB64: [Select]
  1. _TITLE "Scan Line Filled Polygon Test" 'b+ copy Andy Amaya's post 2019-12-05
  2. ' and compare to naive poly fill that b+ would do from Paint Image Brick pattern test
  3. '_TITLE "Brick Pattern Tile, click a spot to spray paint a brick image."
  4.  
  5. 'Andy's notes
  6. 'http://alienryderflex.com/polygon_fill/
  7. 'public-domain code by Darel Rex Finley, 2007
  8. 'QB64 version by Andy Amaya
  9. '_TITLE "Scan Line Filled Polygon"
  10.  
  11. 'B+ notes of mods after adding Brick Pattern Tile code test
  12. ' change to 32 bit color graphis screen, so change Andy's colors
  13.  
  14. CONST xmax = 800, ymax = 600
  15. SCREEN _NEWIMAGE(xmax, ymax, 32)
  16. _SCREENMOVE 300, 40
  17.  
  18. DIM SHARED polyX#(500), polyY#(500), nodeX%(500)
  21.  
  22. 'Initialize maxima and minima then, find the bounding box of the polygon
  23. minX# = 9999
  24. maxX# = -9999
  25. minY# = 9999
  26. maxY# = -9999
  27.  
  28. scaleX# = 5.2 'X scaling factor
  29. scaleY# = 4.2 'Y scaling factor
  30. offsetX# = 80 'X and Y offsets to place polygon on screen
  31. offsetY# = 70
  32. numVerts% = 62
  33.  
  34. 'Read the polygon vertices into polyX() and poly() arrays
  35. 'Use scaling and offsets before placing into the two arrays
  36. RESTORE jigsawPiece
  37. FOR i% = 0 TO numVerts% - 1 'polygon has 62 sides (zero based counting)
  38.     READ zx%
  39.     READ zy%
  40.     polyX#(i%) = zx% * scaleX# + offsetX#
  41.     polyY#(i%) = zy% * scaleY# + offsetY#
  42.     minX# = min(minX#, polyX#(i%))
  43.     maxX# = max(maxX#, polyX#(i%))
  44.     minY# = min(minY#, polyY#(i%))
  45.     maxY# = max(maxY#, polyY#(i%))
  47.  
  48. 'make brick pattern   B+ test for compare
  49. brickpat& = _NEWIMAGE(16, 16, 32)
  50. _DEST brickpat&
  51. LINE (0, 0)-(_WIDTH(brickpat&) - 1, _HEIGHT(brickpat&) - 1), _RGB32(128, 0, 0), BF
  52. LINE (0, 0)-(_WIDTH(brickpat&) - 1, 0), _RGB32(200, 200, 200), BF
  53. LINE (0, 7)-(_WIDTH(brickpat&) - 1, 8), _RGB32(200, 200, 200), BF
  54. LINE (0, 15)-(_WIDTH(brickpat&) - 1, 15), _RGB32(200, 200, 200), BF
  55. LINE (0, 0)-(1, 8), _RGB32(200, 200, 200), BF
  56. LINE (7, 8)-(8, 15), _RGB32(200, 200, 200), BF
  57. DIM SHARED BC AS _UNSIGNED LONG 'requires a unique border color for Paint Porder 1 of 16 million + colors you can find one!
  58. BC = _RGB32(119, 17, 2) 'for PAINT fill to BC
  59. BC = &HFFFFFFFF
  61.  
  62. COLOR &HFFFFFFFF, &HFF000088
  63. PAINT (10, 10), &HFF000088 ' <<<<<<<<< for some reason what ever goes first is really fast either Andy's polyFill or PAINT
  64. '                            <<<<<<<<<<<<<< so I am making this call to PAINT first!
  65.  
  66. st = TIMER(.001)
  67. 'draw polygon, use Andy's fixed code, missing ), and 32 bit color
  68. drawPoly numVerts%, BC
  69. PAINT (10 * scaleX# + offsetX#, 10 * scaleY# + offsetY#), BC, BC
  70. et = TIMER(.001) - st
  71. PRINT "Polygon with 62 vertices Andy's drawPoly and PAINT filled in: "; USING "###"; (et * 1000);
  72. PRINT " milliseconds, press key for Andy's, Scan Line Fill Poly test..."
  75.  
  76. st = TIMER(.001)
  77. polyFill numVerts% - 1, minX#, maxX#, minY#, maxY#
  78. et = TIMER(.001) - st
  79. PRINT "Polygon with 62 vertices using Andy's polyFill, filled in: "; USING "###"; (et * 1000);
  80. PRINT " milliseconds, press key for bplus paintImage fill... "
  83.  
  84. st = TIMER(.001)
  85. 'draw polygon, use Andy's fixed code, missing ), and 32 bit color
  86. drawPoly numVerts%, BC
  87. paintImage 10 * scaleX# + offsetX#, 10 * scaleY# + offsetY#, BC, 0, brickpat&
  88. et = TIMER(.001) - st
  89. PRINT "Polygon with 62 vertices Andy's drawPoly and bplus paintImage filled in: "; USING "###"; (et * 1000);
  90. PRINT " milliseconds, press key for NEW polyFillImage, bplus mod of Andy's polyFill... "
  92.  
  94. st = TIMER(.001)
  95. ' combine Andy's polyFill with my paintImage for polyFillImage
  96. 'SUB    polyFillImage (numSides%, minX#, maxX#, minY#, maxY#, imageH&)
  97. polyFillImage numVerts% - 1, minX#, maxX#, minY#, maxY#, brickpat&
  98. et = TIMER(.001) - st
  99. PRINT "Polygon with 62 vertices NEW polyFillImage filled in: "; USING "###"; (et * 1000);
  100. PRINT " milliseconds, beats the old paintImage! End of tests...  "
  103.  
  104. jigsawPiece:
  105. DATA 4,4,7,2,27,0,36,1,35,6,32,13,32,20,36,24,45,27,61,31
  106. DATA 61,26,57,22,57,19,60,18,75,17,89,21,87,43,85,48,88,53,97,48
  107. DATA 99,47,106,48,107,51,109,58,106,76,103,78,99,75,95,73,93,74,92,82
  108. DATA 93,92,95,104,76,108,69,108,67,104,67,99,70,91,70,85,59,80,47,80
  109. DATA 45,81,46,86,48,92,42,93,22,88,20,87,16,73,15,65,14,58,15,55
  110. DATA 20,55,25,56,30,59,30,56,27,47,25,39,22,35,15,31,9,31,3,35
  111. DATA 0,34,0,27
  112.  
  113. SUB polyFill (numSides%, minX#, maxX#, minY#, maxY#)
  114.     FOR pixelY% = minY# TO maxY#
  115.         nodes% = 0
  116.         j% = numSides% - 1
  117.         fpixY# = pixelY%
  118.         'build node list
  119.         FOR i% = 0 TO numSides% - 1
  120.             b1% = ABS(polyY#(i%) < fpixY#)
  121.             b2% = ABS(polyY#(j%) >= fpixY#)
  122.             b3% = ABS(polyY#(j%) < fpixY#)
  123.             b4% = ABS(polyY#(i%) >= fpixY#)
  124.             IF ((ABS(b1% AND b2%)) OR (ABS(b3% AND b4%))) THEN
  125.                 f1# = fpixY# - polyY#(i%)
  126.                 f2# = polyY#(j%) - polyY#(i%)
  127.                 f3# = polyX#(j%) - polyX#(i%)
  128.                 nodeX%(nodes%) = INT(f1# / f2# * f3# + polyX#(i%))
  129.                 nodes% = nodes% + 1
  130.             END IF
  131.             j% = i%
  132.         NEXT
  133.         'sort nodes
  134.         i% = 0
  135.         WHILE i% < nodes% - 1
  136.             IF (nodeX%(i%) > nodeX%(i% + 1)) THEN
  137.                 SWAP nodeX%(i%), nodeX%(i% + 1)
  138.                 IF (i% > 0) THEN i% = i% - 1
  139.             ELSE
  140.                 i% = i% + 1
  141.             END IF
  142.         WEND
  143.         'draw scanlines
  144.         FOR i% = 0 TO nodes% - 1 STEP 2
  145.             IF (nodeX%(i%) <= maxX#) THEN
  146.                 IF (nodeX%(i% + 1) > minX#) THEN
  147.                     IF (nodeX%(i%) < minX#) THEN nodeX%(i%) = minX#
  148.                     IF (nodeX%(i% + 1) > maxX#) THEN nodeX%(i% + 1) = maxX#
  149.                     LINE (nodeX%(i%), pixelY%)-(nodeX%(i% + 1), pixelY%)
  150.                 END IF
  151.             END IF
  152.         NEXT
  153.     NEXT
  155.  
  156. SUB polyFillImage (numSides%, minX#, maxX#, minY#, maxY#, imageH&)
  157.     s = _SOURCE ' <<<<<<<<<<<<<< save Source for this routine
  158.     _SOURCE imageH&
  159.     FOR pixelY% = minY# TO maxY#
  160.         nodes% = 0
  161.         j% = numSides% - 1
  162.         fpixY# = pixelY%
  163.         'build node list
  164.         FOR i% = 0 TO numSides% - 1
  165.             b1% = ABS(polyY#(i%) < fpixY#)
  166.             b2% = ABS(polyY#(j%) >= fpixY#)
  167.             b3% = ABS(polyY#(j%) < fpixY#)
  168.             b4% = ABS(polyY#(i%) >= fpixY#)
  169.             IF ((ABS(b1% AND b2%)) OR (ABS(b3% AND b4%))) THEN
  170.                 f1# = fpixY# - polyY#(i%)
  171.                 f2# = polyY#(j%) - polyY#(i%)
  172.                 f3# = polyX#(j%) - polyX#(i%)
  173.                 nodeX%(nodes%) = INT(f1# / f2# * f3# + polyX#(i%))
  174.                 nodes% = nodes% + 1
  175.             END IF
  176.             j% = i%
  177.         NEXT
  178.         'sort nodes
  179.         i% = 0
  180.         WHILE i% < nodes% - 1
  181.             IF (nodeX%(i%) > nodeX%(i% + 1)) THEN
  182.                 SWAP nodeX%(i%), nodeX%(i% + 1)
  183.                 IF (i% > 0) THEN i% = i% - 1
  184.             ELSE
  185.                 i% = i% + 1
  186.             END IF
  187.         WEND
  188.         'draw scanlines
  189.         FOR i% = 0 TO nodes% - 1 STEP 2
  190.             IF (nodeX%(i%) <= maxX#) THEN
  191.                 IF (nodeX%(i% + 1) > minX#) THEN
  192.                     IF (nodeX%(i%) < minX#) THEN nodeX%(i%) = minX#
  193.                     IF (nodeX%(i% + 1) > maxX#) THEN nodeX%(i% + 1) = maxX#
  194.  
  195.                     'LINE (nodeX%(i%), pixelY%)-(nodeX%(i% + 1), pixelY%)   '                              <<<<<<<<<<
  196.                     FOR ii% = nodeX%(i%) TO nodeX%(i% + 1) '                                               <<<<<<<<<<
  197.                         ' _SOURCE imageH&
  198.                         PSET (ii%, pixelY%), POINT(ii% MOD _WIDTH(imageH&), pixelY% MOD _HEIGHT(imageH&)) '<<<<<<<<<<
  199.                     NEXT '                                                                                 <<<<<<<<<<
  200.  
  201.                 END IF
  202.             END IF
  203.         NEXT
  204.     NEXT
  205.     _SOURCE s '<<<<<<<<<<<<< restore source
  207.  
  208. FUNCTION min# (flt1#, flt2#)
  209.     IF flt1# < flt2# THEN min# = flt1# ELSE min# = flt2#
  211.  
  212. FUNCTION max# (flt1#, flt2#)
  213.     IF flt1# > flt2# THEN max# = flt1# ELSE max# = flt2#
  215.  
  216. SUB paintImage (x, y, Border~&, destHandle&, imageHandle&)
  217.     d = _DEST: s = _SOURCE
  218.     _DEST destHandle&
  219.     PAINT (x, y), BC, Border~&
  220.     FOR y = 0 TO _HEIGHT(destHandle&)
  221.         FOR x = 0 TO _WIDTH(destHandle&)
  222.             _SOURCE destHandle&
  223.             IF POINT(x, y) = BC THEN
  224.                 _SOURCE imageHandle&
  225.                 PSET (x, y), POINT(x MOD _WIDTH(imageHandle&), y MOD _HEIGHT(imageHandle&))
  226.             END IF
  227.         NEXT
  228.     NEXT
  229.     _DEST d: _SOURCE s
  231.  
  232. 'Code to draw a polygon border
  233. SUB drawPoly (verts AS INTEGER, colr AS _UNSIGNED LONG) 'change color
  234.     j% = verts - 1
  235.     FOR i% = 0 TO verts - 1
  236.         'Point in polygon array variables for line drawing
  237.         'LINE (xp(j%), yp(j%))-(xp(i%), yp(i%)), colr%
  238.         'polyFill array variables for line drawing
  239.         LINE (polyX#(j%), polyY#(j%))-(polyX#(i%), polyY#(i%)), colr
  240.         j% = i%
  241.     NEXT
  243.  
  244.  
« Last Edit: December 05, 2019, 01:36:44 pm by bplus »
Logged
Pages: [1]   Go Up
« previous next »