kicad-developers team mailing list archive

[Mário Luzeiro <mrluzeiro@xxxxx>]

Thank you for the explanation, I am starting to better understand it now.

Could that be done some other way?

I was trying to understand how GAL is rendering the zones and it first draws "the polygon it self" and then the beautiful rounded outlines. (The corner interpolation is visually implemented in shaders in openGL GAL case)

What about apply the remove holes only to that "10 000 to 20 000 corners" (I believe the remove holes will so create more corners..with the format of the hole..) and then render an outline with the approximation polygon.?

The other way I was trying to suggest / think is in some acceleration structure (tree) or to subdivide the board (in a grid) and then apply that remove holes. (so, not sure how can it be performed .. or if boost is already doing that)

Another technical question: How does the outline width/ polygon is properly rendered?
If we have a single point, that point will draw a circle with the radius = width ?

Maybe there are some other way that I am trying to think how this can be visually rendered with less processing (similar way as GAL).

One other possibility, but it could lack a bit from "technical precision" would be using image operation & textures. In that case the rendering could be performed as in GAL and the holes are removed by pixel operations... maybe then.. (as I suggested before) a proper outline can be rendered in 3D... In the end we want to have the best math / physical realistic & correctness rendering.. but it can be faked somehow.

What do you think?

Regards,
Mario Luzeiro
________________________________________
From: jp charras [jp.charras@xxxxxxxxxx]
Sent: 13 April 2015 16:14
To: Mário Luzeiro
Cc: kicad-developers@xxxxxxxxxxxxxxxxxxx
Subject: Re: Remove holes and bottleneck in 3d-viewer

Le 13/04/2015 15:27, Mário Luzeiro a écrit :
> Hi Jean-Pierre,
>
> As we know, one of the bottleneck in 3d-viewer is while exporting the pcbboard to polygons and then remove the holes from the fill zones.
> I was trying to understand the process of that and in the sources and see if we have room for improvement.
>
> "        // Draw copper zones. Note:
>         // * if the holes are removed from copper zones
>         // the polygons are stored in bufferPolys (which contains all other polygons)
>         // * if the holes are NOT removed from copper zones
>         // the polygons are stored in bufferZonesPolys"
>
> So, the only different while extracting the holes is to have the information form the filling zones? Why in that case it is causing so much more CPU effort?
>
> Then,
>
> "  // bufferPolys contains polygons to merge. Many overlaps ."
> " // Calculate merged polygons"
>
> "// Merge polygons, and remove holes
>         currLayerPolyset -= polysetHoles;""
>
> I was wondering if the polygons are really merged?
> I mean, if we add a fill zone in the copper, it should overlap tracks (ex GND / Power tracks of the zone) so, that track polygon information are not needed and can be merged .. some how?
> Can we gain any speed if we combine this overlap polygons?
>
> Also, what about if we perform the remove holes by split it somehow? ex: remove holes per zone, per track? ..
>
> I dont know how that (boost) algorithm works, I was thinking if it have less data to process it could be faster, so a hole will only remove polygons that we know (somehow) in advance that are hit by a hole?
>
> Do you have any other ideas and how this can be improved?
>
> Thanks!
> Regards,
> Mario Luzeiro
>

To understand why removing holes in copper zones is so time consuming,
remember how filled zones are made:
They combine 2 different things:
* the polygon itself.
* the outlines which have a thickness(which it is the minimal zone
width). they are rounded ends segments.

In 3D viewer, each zone is converted to an equivalent polygon:
the main polygon itself and its outline (each thick segment of the
outline is converted to a polygon, which overlaps the main polygon)

For large and complex zones, the number of polygon corners can be very
large (10 000 to 20 000 corners, and if each segment is approximated by
a 16 corners polygon, it gives 150 000 to 300 000 corners).

To remove holes from zones, you have to combine these polygons to others.
Therefore, combining these polygons to remove holes (this is what makes
the line: currLayerPolyset -= polysetHoles;) is very time consuming
because you can have hundred of thousand of corners to combine in a
power plane.

When the holes are not removed from zones, the number of corners to
combine is (by far) not so large, and calculations are faster.

You asked:
"Also, what about if we perform the remove holes by split it somehow?
ex: remove holes per zone, per track? .."

I already tried: the calculation time is higher, because you have to
make twice some calculations (for instance: remove the same holes from
tracks and zones) and this is equivalent to combine more polygon corners.


--
Jean-Pierre CHARRAS