Log In  

I am aware there is already code available by various authors for trifill, plus benchmarks and all that jazz.
However I have a particular use case which:

  • can leverage known properties (rotated rect) to halve draw calls needed (no triangulation)
  • requires compatibility with line() for drawing outlines (otherwise I'd need custom line code to match the fill)

So I've been cooking my own. (Use case aside, it's also a good learning experience.)

The basic idea is vertical slices drawn using rectfill, endpoints based on principles of Bresenham's algol. The goal is to match line() output exactly -- the endpoints should get overwritten if line() calls are subsequently made to draw outlines for the shape -- and it should work for both upper and lower edges.

Have managed to get pretty close but still getting a few isolated cases that don't match, e.g. stray pixels of fill color outside the outline. Here's what I've got so far:

Cart #linecompat-0 | 2020-01-01 | Code ▽ | Embed ▽ | No License
1

display

Given coordinates (x1,y1) and (x2,y2):
White line is ground truth and is drawn last using line().
Red fill uses the coordinates as one edge of fill -- want this to match white line -- uses top/bottom of screen as other edge
Gray fill is same as red but offset by 2 pixels -- helpful for spotting some mismatches: red "line" too thick in places => coloring outside the lines if toggle between top/bottom edge

controls

direction keys p2(sfed) and p1(arrows) -> move left and right coordinates respectively
p1 O(z) -> randomize coordinates
p1 X(x) -> toggle between line as upper/lower edge of fill

implementations + results thus far

The menu options allow switching between three slightly different implementations.
All start by flr() the x,y coords to match stock graphics behavior.

The "round 0.5 up" option performs full interpolation calculation, plugging in x to get y coords. If the fractional part of y is greater than or equal to 0.5, it gets rounded up (else is left as-is and gets truncated (floor) by rectfill)

The "round 0.5 down" option is very similar, but will only round the y coordinate up if the fractional part is strictly greater than 0.5

"Cumulative err" is a partial implementation of typical Bresenham's: does not interpolate but instead precomputes the slope and then increments a cumulative error by that much for each x-increment. This is working only for the baseline case of x2>x1, y2>y1, x2-x1>y2-y1 (other cases can derive from this)

Since the current focus is on getting the desired behavior, none of the code is particularly optimized / cleaned up. (e.g. "round up" can be done with no rounding logic, just +0.5 and let truncate take care of the rest)

Two other menu options provide a couple of known example failure cases:

  • "round 0.5 up" fails example A
  • "round 0.5 down" fails example B

These two approaches give about as good a match as I was able to get, but it's a bit puzzling that neither nails it exactly. I did "cumulative err" just in case it was something in the fixed point rounding behavior, but it turned out to be a disappointment.

Is there something obvious I've missed? Or is it just due to rounding and a perfect match just isn't possible? Any insight is appreciated.

P#71635 2020-01-01 18:44

2

Given you don’t know the rounding of the pico8 line, I'd suggest to roll your own line routine to match your polygons.
This is the standard yet tricky problem of sub-pixel rendering (e.g. pixel grid vs. polygon positions).
See: https://www.flipcode.com/archives/3D_Graphics_on_Mobile_Devices-Part_4_Polygon_Rasterization.shtml
(and many other old papers)

Note that bresenham was useful for older computer without a floating point unit.
pico comes with built-in fixed point ‘float’.

Or do it GPU shader style (e.g. draw an inflated 'outline' polygon behind), a bit more crude but bulletproof!
(note: could be made a lot faster if polygons are convex)

Cart #tekuyupozo-0 | 2020-01-01 | Code ▽ | Embed ▽ | No License
2

P#71638 2020-01-01 19:33 ( Edited 2020-01-01 22:04)
1

Thanks for the pointers and for the impressive demo code -- seriously overkill for my purposes though!

I actually suspect (but have not formally tested) that stock line() doesn't use the sub-pixel positions of endpoints -- I was getting worse match when calculating the interpolation with the sub-pixel coords (i.e. no flr() beforehand).

Other niggling suspicion is that while the computations I do are 16:16 fixed point, line() internally might not be subject to the same constraints and that tiny difference in rounding could be the source of the minor discrepancy.

Currently thought/hope is that "round up" for upper edges and "round down" for lower edges might be "good enough" to not color outside the lines -- will need to do some more thorough testing on that though. If not, you're probably right that rolling my own would be the way to go.

P#71683 2020-01-02 05:40

interested by what you are trying to achieve btw;)
‘can leverage known properties (rotated rect) to halve draw calls needed (no triangulation)’ is very much the same I did for my 3d game, see: https://twitter.com/fsouchu/status/1207025883191623681?s=21

P#71685 2020-01-02 07:32

Nothing that quite spectacular for me yet.
The task at hand is actually embarrassingly simple: draw a little rectangular tank body and add black lines on either side for the caterpillar tracks.

Other thing I have in mind for later is drawing walls from a top-down perspective 3d view.

P#71690 2020-01-02 15:35

then do use the convex polygon rendering code I posted.
for the tracks, I would use a series of circles drawn ‘under’ the main polygon - I suspect a simple line will be underwhelming.

P#71693 2020-01-02 16:06

Good idea if tank were larger, but that level of detail would be wasted on the tiny li'l 5×5px bugger I've got presently.

P#71701 2020-01-02 18:08

hehe :]
(left/right to turn - x/c to accelerate/brake)

Cart #juteromaki-0 | 2020-01-02 | Code ▽ | Embed ▽ | No License

tbh - at this size, a rotated sprite might be more appropriate (unless you need a polygon look for the whole game)

P#71712 2020-01-02 20:51 ( Edited 2020-01-02 20:53)

Yeah, that's similar to the behavior I already have. Going to resist looking at your code for now though, want to tinker and experiment with different approaches by myself for a bit to get a better hands-on understanding of things. Thanks for the help!

P#71723 2020-01-03 04:32

[Please log in to post a comment]

Follow Lexaloffle:          
Generated 2024-03-28 20:47:53 | 0.012s | Q:30