[prev in list] [next in list] [prev in thread] [next in thread]
List: openjdk-2d-dev
Subject: Re: [OpenJDK 2D-Dev] sun.java2D.Pisces renderer Performance and Memory enhancements
From: Laurent_Bourgès <bourges.laurent () gmail ! com>
Date: 2013-06-17 15:18:06
Message-ID: CAKjRUT7LfwZT0hb__Q=C8_CjgBhC7y3WbrSF_HhmKL-uKjgVdA () mail ! gmail ! com
[Download RAW message or body]
Jim,
I think I found the source of the 'poor' quality of line rendering:
the alpha coverage is only computed for the 2 sub pixels (x0, x1) at the
current x-coordinate of an edge ie it does not take into account the span
of a line having a very flat slope:
for (i = 0, sum = 0, prev = bboxx0; i < numCrossings; i++) {
curxo = _crossings[i];
curx = curxo >> 1;
// LBO: TODO: explain alpha computation: Jim, please ?
...
if ((sum & mask) != 0) {
x0 = (prev > bboxx0) ? prev : bboxx0; //
Math.max(prev, bboxx0);
x1 = (curx < bboxx1) ? curx : bboxx1; //
Math.min(curx, bboxx1);
if (x0 < x1) {
x0 -= bboxx0; // turn x0, x1 from coords to
indices
x1 -= bboxx0; // in the alpha array.
pix_x = x0 >> _SUBPIXEL_LG_POSITIONS_X;
pix_xmaxm1 = (x1 - 1) >>
_SUBPIXEL_LG_POSITIONS_X;
if (pix_x == pix_xmaxm1) {
// Start and end in same pixel
tmp = (x1 - x0); // number of subpixels
_alpha[pix_x] += tmp;
_alpha[pix_x + 1] -= tmp;
} else {
tmp = (x0 & _SUBPIXEL_MASK_X);
* _alpha[pix_x] += _SUBPIXEL_POSITIONS_X -
tmp;
* * _alpha[pix_x + 1] += tmp;
*
pix_xmax = x1 >> _SUBPIXEL_LG_POSITIONS_X;
tmp = (x1 & _SUBPIXEL_MASK_X);
* _alpha[pix_xmax] -= _SUBPIXEL_POSITIONS_X
- tmp;
_alpha[pix_xmax + 1] -= tmp;
* }
}
}
// to turn {0, 1} into {-1, 1}, multiply by 2 and
subtract 1.
// int crorientation = ((curxo & 0x1) << 1) - 1;
sum += ((curxo & 0x1) << 1) - 1; // crorientation;
prev = curx;
}
}
Here is a line test using GeneralPath(Line2D.float) to use pisces instead
of FillParallelogram renderer:
- pisces (8x8):
http://jmmc.fr/~bourgesl/share/java2d-pisces/linetest/LineTest_3.png
- pisces (256x256):
http://jmmc.fr/~bourgesl/share/java2d-pisces/linetest/LineTest_8.png
The artefacts comes from the fact that the line spans over several
subpixels and the slope and the span width is not used at all !
I think it is possible to compute a better coverage for all alpha pixels
implied in a span (trapezoid):
for each edge at scanline y: it only needs to have curx and previous curx
(to know how many subpixel the span crosses)
http://upload.wikimedia.org/wikipedia/commons/3/38/PolygonFillTrapezoidExample.png
Comments are welcome ...
Two more comments:
> - coordinate conversions: float or integer computations (DDA) related to
> subpixel coordinates: ceil(), floor() ...
> Pisces uses 3x3 subpixels but it provides poor quality: many
> research papers are using 4x4 (1/16 error) or 8x8 (1/64 error) subpixel
> masks to increase the coverage precision (ratio of the pixel covered by the
> polygon)
> Moreover, Pisces does not take into account the distance / error
> between the mathematical edge position and the pixel grid.
> Ideally the subpixel mask should be 16x16 => 1/256 coverage error
> but it will lead to higher processing time.
>
I misunderstood the code: pisces uses 8x8 subpixel grid (1 << 3) so every
coordinate has a 1/8 precision (low) far from 1/256 (like AGG) which is the
ultimate precision => many rasterizer uses 24.8 (24 bits for integer
coordinates, 8 bits for 1/256 precision) => DDA (32 bits integer
computations)
I will try soon to use 24.8 fixed point DDA to compute x-coordinates of
edge segments.
Laurent
[Attachment #3 (text/html)]
Jim,<br><br>I think I found the source of the 'poor' quality of line \
rendering: <br>the alpha coverage is only computed for the 2 sub pixels (x0, x1) at \
the current x-coordinate of an edge ie it does not take into account the span of a \
line having a very flat slope:<br> <br><span style="font-family:courier \
new,monospace"> for (i = 0, sum = 0, prev = bboxx0; i < \
numCrossings; i++) {</span><br style="font-family:courier new,monospace"> <span \
style="font-family:courier new,monospace"> curxo = \
_crossings[i];</span><br style="font-family:courier new,monospace"><span \
style="font-family:courier new,monospace"> curx = curxo >> \
1;</span><br style="font-family:courier new,monospace">
<br style="font-family:courier new,monospace"><span style="font-family:courier \
new,monospace"> // LBO: TODO: explain alpha computation: Jim, \
please ? ...</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> if ((sum & \
mask) != 0) {</span><br style="font-family:courier new,monospace"><span \
style="font-family:courier new,monospace"> x0 = (prev > \
bboxx0) ? prev : bboxx0; // Math.max(prev, bboxx0);</span><br \
style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> x1 = (curx \
< bboxx1) ? curx : bboxx1; // Math.min(curx, bboxx1);</span><br \
style="font-family:courier new,monospace"><span style="font-family:courier \
new,monospace"> </span><br style="font-family:courier \
new,monospace">
<span style="font-family:courier new,monospace"> if (x0 < \
x1) {</span><br style="font-family:courier new,monospace"><span \
style="font-family:courier new,monospace"> x0 -= bboxx0; \
// turn x0, x1 from coords to indices</span><br style="font-family:courier \
new,monospace">
<span style="font-family:courier new,monospace"> x1 -= \
bboxx0; // in the alpha array.</span><br style="font-family:courier \
new,monospace"><br style="font-family:courier new,monospace"><span \
style="font-family:courier new,monospace"> pix_x = x0 \
>> _SUBPIXEL_LG_POSITIONS_X;</span><br style="font-family:courier \
new,monospace">
<span style="font-family:courier new,monospace"> \
pix_xmaxm1 = (x1 - 1) >> _SUBPIXEL_LG_POSITIONS_X;</span><br \
style="font-family:courier new,monospace"><span style="font-family:courier \
new,monospace"> </span><br style="font-family:courier \
new,monospace">
<span style="font-family:courier new,monospace"> if (pix_x \
== pix_xmaxm1) {</span><br style="font-family:courier new,monospace"><span \
style="font-family:courier new,monospace"> // Start \
and end in same pixel</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> tmp = \
(x1 - x0); // number of subpixels</span><br style="font-family:courier \
new,monospace"><span style="font-family:courier new,monospace"> \
_alpha[pix_x] += tmp;</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> \
_alpha[pix_x + 1] -= tmp;</span><br style="font-family:courier new,monospace"><span \
style="font-family:courier new,monospace"> } else \
{</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> tmp = \
(x0 & _SUBPIXEL_MASK_X);</span><br style="font-family:courier \
new,monospace"><b><span style="font-family:courier new,monospace"> \
_alpha[pix_x] += _SUBPIXEL_POSITIONS_X - tmp;</span><br style="font-family:courier \
new,monospace"> </b>
<b><span style="font-family:courier new,monospace"> \
_alpha[pix_x + 1] += tmp;</span><br style="font-family:courier \
new,monospace"></b><span style="font-family:courier new,monospace"> \
</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> \
pix_xmax = x1 >> _SUBPIXEL_LG_POSITIONS_X;</span><br style="font-family:courier \
new,monospace"><span style="font-family:courier new,monospace"> \
tmp = (x1 & _SUBPIXEL_MASK_X);</span><br style="font-family:courier \
new,monospace">
<b><span style="font-family:courier new,monospace"> \
_alpha[pix_xmax] -= _SUBPIXEL_POSITIONS_X - tmp;</span><br style="font-family:courier \
new,monospace"><span style="font-family:courier new,monospace"> \
_alpha[pix_xmax + 1] -= tmp;</span><br style="font-family:courier new,monospace"> \
</b> <span style="font-family:courier new,monospace"> \
}</span><br style="font-family:courier new,monospace"><span \
style="font-family:courier new,monospace"> }</span><br \
style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> }</span><br \
style="font-family:courier new,monospace"><span style="font-family:courier \
new,monospace"> </span><br style="font-family:courier \
new,monospace">
<span style="font-family:courier new,monospace"> // to turn {0, 1} \
into {-1, 1}, multiply by 2 and subtract 1.</span><br style="font-family:courier \
new,monospace"><span style="font-family:courier new,monospace">// \
int crorientation = ((curxo & 0x1) << 1) - 1;</span><br \
style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> sum += ((curxo \
& 0x1) << 1) - 1; // crorientation;</span><br style="font-family:courier \
new,monospace"><span style="font-family:courier new,monospace"> \
prev = curx;</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> }</span><br \
style="font-family:courier new,monospace"><span style="font-family:courier \
new,monospace"> }</span><br style="font-family:courier new,monospace">
<br>Here is a line test using GeneralPath(Line2D.float) to use pisces instead of \
FillParallelogram renderer:<br>- pisces (8x8): <br><a \
href="http://jmmc.fr/%7Ebourgesl/share/java2d-pisces/linetest/LineTest_3.png" \
target="_blank">http://jmmc.fr/~bourgesl/share/java2d-pisces/linetest/LineTest_3.png</a><br>
- pisces (256x256):<br><a \
href="http://jmmc.fr/%7Ebourgesl/share/java2d-pisces/linetest/LineTest_8.png" \
target="_blank">http://jmmc.fr/~bourgesl/share/java2d-pisces/linetest/LineTest_8.png</a><br><br>The \
artefacts comes from the fact that the line spans over several subpixels and the \
slope and the span width is not used at all !<br> <br>I think it is possible to \
compute a better coverage for all alpha pixels implied in a span (trapezoid):<br>for \
each edge at scanline y: it only needs to have curx and previous curx (to know how \
many subpixel the span crosses)<br> <br><a \
href="http://upload.wikimedia.org/wikipedia/commons/3/38/PolygonFillTrapezoidExample.p \
ng">http://upload.wikimedia.org/wikipedia/commons/3/38/PolygonFillTrapezoidExample.png</a><br><br>Comments \
are welcome ...<br><br> <div class="gmail_quote"><blockquote class="gmail_quote" \
style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid \
rgb(204,204,204);padding-left:1ex"> Two more comments:<br>
- coordinate conversions: float or integer computations (DDA) related to subpixel \
coordinates: ceil(), floor() ...<br> Pisces uses 3x3 subpixels but it provides \
poor quality: many research papers are using 4x4 (1/16 error) or 8x8 (1/64 error) \
subpixel masks to increase the coverage precision (ratio of the pixel covered by the \
polygon)<br>
Moreover, Pisces does not take into account the distance / error between the \
mathematical edge position and the pixel grid.<br> Ideally the subpixel mask \
should be 16x16 => 1/256 coverage error but it will lead to higher processing \
time.<br>
</blockquote><div><br>I misunderstood the code: pisces uses 8x8 subpixel grid (1 \
<< 3) so every coordinate has a 1/8 precision (low) far from 1/256 (like AGG) \
which is the ultimate precision => many rasterizer uses 24.8 (24 bits for integer \
coordinates, 8 bits for 1/256 precision) => DDA (32 bits integer computations)<br>
<br>I will try soon to use 24.8 fixed point DDA to compute x-coordinates of edge \
segments.<br><br>Laurent<br></div></div>
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic