Polygons don't sufficiently clear circular items

[Lilith Bryant]

The correction factor POLY_CIRC_RADIUS_ADJ is not applied to the first and last points in all circular sections.

The results in inadequate clearance to the right of vias & pins. Line and arc clearances are similarly inadequate.

Attached is a simple example. To repeat:

1) Move the mark the centre of the via
2) Turn off the grid
3) Go to the polygon edge to the right of the via
4) Zoom in LOTS
5) Inspect the distance to the polygon at just above and below the "3 o'clock" position

Clearance in this example is supposed to be 0.35mm (0.25mm via radius + 0.1mm clearance). However 0.3494mm is observable.

[Lilith Bryant (dark141)]

Attached is a fix for pins/vias only.

The patch also rotates the approximation "40-polygon" by half a segment, so as to make the left/right/top/bottom edges of it orthogonal (rather than being "points up"). This allows full width webbing between pins/vias that are arranged a line.

( All of this is way more obvious if you set POLY_CIRC_SEGS to 8 )

Fixing lines and arc clearances seems rather more difficult. Patch pending...

[Lilith Bryant (dark141)]

It seems these changes are not enough. The definition of POLY_CIRC_RADIUS_ADJ (in polygon.h) is also incorrect. The correct definition is:

#define POLY_CIRC_RADIUS_ADJ (1.0/cos(M_PI / POLY_CIRC_SEGS_F))

[Lilith Bryant (dark141)]

Thought about the problem for a bit, and here's a different patch which fixes all the issues very simply. Please ignore the previous patches.

It does add one more point per circular segment, so I've also compensated by reducing the subdivisions to 36 (from 40). So as to not adversely affect performance.

[Peter Clifton (pcjc2)]

We have to be careful changing the number of segments. The majority of PCB lines are angled at a multiple of 45 degrees, with the normal case of adjoining lines being 45 degrees apart. 36 is not evenly divisible by 8, so that is not a good choice.

40 segments was chosen deliberately to ensure that the intersection between the clearances of these two lines share as many common points as possible. If not, each line intersections creates more complex geometry than necessary.

[Lilith Bryant (dark141)]

OK, that's fair enough, but perhaps lowering this subdivision would be a good idea anyway? At least to 32? Maybe even 24? I personally use 12 on my local build to get acceptable performance with my polygon-on-every-layer 8-layer boards . (I would use 8, but that triggers a polygon subdivider bug). Making this a configurable setting would be very nice.

[Peter Clifton (pcjc2)]

Have you tried any of my OpenGL branches?

git clone git://repo.or.cz/geda-gaf/pcjc2.git

Take a prod at the the "pcb+gl_experimental" branch.

That should be faster than git HEAD, as it uses a much more efficient way of rendering the polygons...

It uses rasteriser code borrowed from Cairo for complex shapes, and has a few other little tricks to keep things fast. It short-cuts rendering circular holes in polygons by using a pixel shader.

[Lilith Bryant (dark141)]

Trying it now. It looks good. A noticeable performance improvement even with Intel 945 integrated graphics. I did have to bump TRIANGLE_ARRAY_SIZE up to 40000 though for my current big design. Cheers.

[Peter Clifton (pcjc2)]

The reason I developed those faster code-paths was my laptop with 945 graphics... ;)

(And the GM45 graphics in the laptop I use now).

Although.. regarding TRIANGLE_ARRAY_SIZE, what particular problem were you seeing which caused you to bump its size?

Did you hit

      fprintf (stderr, "Not enough space in vertex buffer\n");
      fprintf (stderr, "Requested %i vertices, %i available\n",
                       count, 3 * TRIANGLE_ARRAY_SIZE);

I'd be really curious to see the polygon (or other geometry) which triggered that - it might be a bug somewhere.

Normally the code should just flush the triangles out and start again with a clear buffer.

[Lilith Bryant (dark141)]

The exact message is:

Not enough space in vertex buffer
Requested 94613 vertices, 90000 available

(Should these numbers be shown divided by 3?)

It's not a trivial PCB. Sorry, it's a design for a client, so I can't post it here.

The polygon are "simple" rectangles. But there is one per layer. 8 Layer board. It has 6 BGA devices, the biggest being 624 pads, 1400 rats, 1300 vias. And the flooding goes between all the BGA's escape vias, so I can see where all the vertices are going with 40 subdivs per circle. Going down to subdivision=12 makes it fit with 30000 though.

I don't think it's a bug, the board really is that complex.

[Peter Clifton (pcjc2)]

Could you let me know the SHA1 of the commit you are running from please.

I think this is as a bug, as the polygon should be broken down into triangles for rendering... and we don't need a huge buffer to render those, we just flush when it gets full.

I don't remember the exact behaviour of each version of the renderer, but I'd be surprised to see it genuinely fall-over, even for extremely complex boards.

I have a test-case here someone sent me with 8 layers, and 9x Spartan FPGAs on a PCI card! (And it renders just fine).

Can you get the bug to reproduce with a cut-down board? I'd like to confirm exactly which geometry is causing it.

I'll be busy for a bit, but if I can send you a patch to PCB to get some debug info out - I'd appreciate the info.

Perhaps you could run PCB inside gdb, and set a breakpoint on the exit function, and attach a backtrace from when it dies.

gdb --args pcb [designfile]
(gdb) break exit
(gdb) run

....

Breakpoint 1, __GI_exit (status=status@entry=0) at exit.c:99
99 exit.c: No such file or directory.
(gdb) bt

.... (Paste this into a file and attach here).

[Peter Clifton (pcjc2)]

(The back-trace would at least tell me what code-path the render is taking when it falls over. That would identify exactly what type of geometry it is processing at the time).

[Peter Clifton (pcjc2)]

Just eyeballing the code, it could possibly be the cached polygon geometry causing the problem.

I forgot that I introduced a (crude) cache, and it is expecting to be be able to emit the entire trip-strip set for a given polygon contour in one go.

This will be confirmed if you get an exit backtrace which is something like:

exit
hidgl_ensure_vertex_space
fill_contour (hidgl.c, Approx line 840)
....

This _is_ a bug (probably ought to be filed separately), thanks for catching it!

The solution will be to chunk up the triangle-strip a little when it gets too large. That isn't difficult, as it consists of individual trapezoids and triangles from the polygon rasterisation anyway. These are jointed together with repeated
start and end vertices to form a single tri-strip. (The joints between triangles and/or traps don't render, as the repeated vertices cause them to be zero-width slivers).

[Lilith Bryant (dark141)]

Version is: 3ca5275f5a4bfee0c399d0aea83567ee6f5639f4

And indeed, break exit/bt 10 gives:

#0 0x47abdcd6 in exit () from /lib/libc.so.6
#1 0x080ffb15 in hidgl_ensure_vertex_space (buffer=0x81cd4f0, count=94613) at hid/common/hidgl.c:258
#2 0x080ffe08 in fill_contour (contour=0x924f918) at hid/common/hidgl.c:840
#3 0x081005e9 in fill_polyarea (pa=0x8740090, clip_box=0xbfffca04, use_new_stencil=<value optimized out>)
    at hid/common/hidgl.c:958
#0 0x47abdcd6 in exit () from /lib/libc.so.6
#1 0x080ffb15 in hidgl_ensure_vertex_space (buffer=0x81cd4f0, count=94613) at hid/common/hidgl.c:258
#2 0x080ffe08 in fill_contour (contour=0x924f918) at hid/common/hidgl.c:840
#3 0x081005e9 in fill_polyarea (pa=0x8740090, clip_box=0xbfffca04, use_new_stencil=<value optimized out>)
    at hid/common/hidgl.c:958
#4 0x08100679 in hidgl_fill_pcb_polygon (poly=0x84200c8, clip_box=0xbfffca04) at hid/common/hidgl.c:979
#5 0x0812a227 in ghid_thindraw_pcb_polygon (gc=0x82d8f38, poly=0x84200c8, clip_box=0xbfffca04) at hid/gtk/gtkhid-gl.c:764
#6 0x080e902c in common_gui_draw_pcb_polygon (gc=0x82d8f38, polygon=0x84200c8, clip_box=0xbfffca04)
    at hid/common/draw_helpers.c:266
#7 0x08124040 in poly_callback_clearing (b=0x84200c8, cl=0xbfffc890) at hid/gtk/gtkhid-gl.c:1400
#8 0x080d74c0 in __r_search (node=0x84d9cd0, query=0xbfffca04, arg=0xbfffc764) at rtree.c:485
#9 0x080d756c in r_search (rtree=0x84ca7e0, query=0xbfffbcb8, check_region=0,
    found_rectangle=0x8123fe0 <poly_callback_clearing>, cl=0xbfffc890) at rtree.c:570
#10 0x08127996 in GhidDrawLayerGroup (screen=<value optimized out>, group=<value optimized out>) at hid/gtk/gtkhid-gl.c:1586

Will see if I can put together a simple .pcb that causes it.

[Peter Clifton (pcjc2)]

Ok,

If you don't consider the silhuette polygon confidential, I could patch up a debug snippet which will spit out the offending polygon.

(Or you could send me something in confidence privately).

FWIW, I can probably just debug what I suspect to be the root cause, and send you updated code to test against. (Altough I'd like to check the polygon to ensure that it isn't otherwise degenerate).

Regarding the patches attached to this bug, I'll have a review of them when I get a moment. I think I'd prefer like to push the numerical fix and the half-segment rotation as two separate changes though.. We should test both separately.