Created attachment 6294 [details] trap.ps The customer has hardware to perform trapezoid filling and would like to use this as efficiently as possible. Since there is overhead in our library as well as in their device to create trapezoids, we want to generate the fewest number of total 'fill_trapezoid' and 'fill_rectangle' calls. The current code seems to be painting some areas multiple times (this would also be a problem with some painting methods, but is not relevant here). The attached simple example 'trap.ps' at 600 dpi generated the following calls into 'fill_rectangle' and 'fill_trapezoid' (all numbers are hex -- values with a '.' are 'fixed' 24.8) 1) fill_rectangle( 682, 34, 22, 1) called from spot_into_trapezoids__aj_fd:87 2) fill_trapezoid(yb=34.2c, yt=35.2b, lstart=(682.2c, 34.2c), lend=(682.2c,44.d6), rstart=(6a4.80, 34.2c), rend=(6a4.80, 35.2b) this is effectively a rectangle: (682, 34, 22, 1) WHICH REPAINTS THE RECTANGLE OF (1). 3) fill_trapezoid(yb=35.2b, yt=44.d6, lstart=(682.2c, 34.2c), lend=(682.2c,44.d6), rstart=(6a4.80, 35.2b), rend=(693.d5, 45.d5) 4) fill_trapezoid(yb=44.d6, yt=45.d5, lstart=(682.2c,44.d6),lend=(682.2c,44.d5), rstart=(6a4.80, 35.2b), rend=(693.d5, 45.d5) this is effectively a rectangle: (682, 45, 12, 1) 5) fill_rectangle(682, 45, 12, 1) called from spot_into_trapezoids__aj_fd:87 WHICH REPAINTS THE RECTANGLE OF (4)
sure would be nice to be able to set the Priority on the initial screen :-(
I forgot to mention that it would be nice, where possible to avoid the first and last trapezoid calls for the fill_adjust area generated by fill_slant_adjust when it is possible to combine with the 'central' trapezoid and count on that to paint the same pixels. In the example, this could be done for the last trapezoid, but not for the first (if my math is correct). Thus this example would boil down to painting a rectangular top line (height 1) and a single trapezoid.
Created attachment 6300 [details] trap2.ps Modified example that shows a 'dumbell' shape. The central section of the dumbell shape is formed of 2 horizontal lines in exactly the same place. Acrobat renders this central line. GS renders this central line too, due to the special case at line 87 of gxfilltr.h. Any modifications we do in this area need to carefully ensure that this case is not broken.
Revision 11282 contains a partial fix for this, in that it reduces the number of shapes plotted to 4 rather than 5. (The commit message incorrectly says 3). The first and last things plotted are the "hack" rectangles (from the dropout prevention code). These are not actually required in this particular instance as the shapes plotted by the slant_into_trapezoids code are sufficient (1 rectangle, followed by 1 trapezoid). Various ideas present themselves as things to try: 1) Remove the "hack" code that does drop out prevention: This causes the dumbell case to go wrong. This is to be expected as not all horizontal lines will have a trapezoid shape abutting them. 2) Change the code in slant_into_trapezoids to generate smaller traps: If we are sure that all horizontal lines are going to be plotted because of the drop out code, can we perhaps make use of this in slant_into_trapezoids by generating smaller traps? I think the answer here is no, because not all traps are going to come from shapes that genuinely have horizontal lines along their top and bottom edges. There is no easy way inside this routine to know that some (or all) of the top/bottom edges may already have been drawn. 3) Can we replace the "hack" with smarter dropout prevention, such that it only draws rectangles for horizontal lines if they weren't going to be rendered as part of a shape anyway? I cannot currently see a way to do this. Doing this would be complicated by the fact that some of a horizontal line might need drop out prevention, and some might not. I suspect any time saved by not having to generate a trap would be more than lost in the additional checks required. 4) Can we (as Ray suggests in comment 2) roll some generated traps together? Given that the important thing for the customer appears to be the number of traps generated, this may be worth pursuing.
Created attachment 6305 [details] patch There are 4 cases in the trapezoid output now; 1) rectangle, 2) trapezoid where top range is a subset of bottom range, 3) trapezoid where bottom range is a subset of top range, and 4) general slanted trapezoid case. 1) needs no optimisation. This patch adds the option for an optimisation in cases 2 and 3. If TRY_TO_EXTEND_TRAP is set then we extend the trap vertically to cover the same extent as the rectangle would, and then test to see if the X range of touched pixels is the same as the rectangle. If it is, then we emit the new trap instead. This doesn't make any difference with the existing test file as the extended trap covers an extra pixel and therefore the combined trap cannot be used. 4) may be looked at in a later patch if this proves worthwhile. I am currently testing this patch in the localcluster - all being well, it should cause no rendering differences.
There are rendering differences given by that patch due to the nature of working in limited precision; when we extend the trapezoids the inevitable rounding can cause differences in the edges of the trapezoids. I think this is unavoidable. I'll try a new version tomorrow tweaked to round outwards so that we always guarantee to plot at least as many pixels as before, but it's still not ideal.
One additional thought; why in fill_slant_adjust do we decompose to 3 trapezoids when we know that at least 2 of the trapezoids are representable as rectangles?
I have just committed revision 11350 to partially address this. If "ENABLE_TRAP_AMALGAMATION" is defined during build, then the code will attempt to amalgamate the trapezoid/rectangle pairs currently produced into a single trapezoid if it considers that the combined trapezoid should cover the same pixels. This process is not perfect due to differences in rounding between the scan conversion code and the trapezium drawing code, but it appears to only differ on very borderline cases. Because of this, (and because there is an overhead to performing the test which probably outweighs the benefits given on many platforms) I have therefore put the code in disabled by default. Thus no differences in rendering should be seen. This code only addresses 2 out of the 5 possible trapezoid cases - the case of 'slant' trapezoids can maybe be addressed similarly.
Revision 11497 extends the ENABLE_TRAP_AMALGAMATION code to the other cases. When enabled, no additional differences in rendering are seen.
The enhancements in here seem to satisfy the customer. We're leaving them disabled by default for now. So closing the bug.
Changing customer bugs that have been resolved more than a year ago to closed.