Category: Master’s Log

NOTE currently scatter and place rules use different discreet selectors.

Most basic discrete selection is just a list of parameter values on the range [0, 1]:

[pos1, pos2, ... posn]

One can also specify the interval between the items:

[item_offset]

It is possible to specify start offset

[offset_start : item_offset]

Or end offset:

[item_offset : offset_start]

Or  both:

[offset_start : item_offset : offset_end]

• offset_start, offset_end (double), the distance between the start of the edge and the first item, or respectively end of the edge and the last item. double values
• item_offset – either:
  • ninterval_count (int) – number of intervals between items; e.g. to place n items interval count is n-1
  • linterval_length (double) – desired interval length, could be less or more, depending on how many items fit in the area.

Problems with Numerical Indexing

Idea of numerical indexing is favourable because one can have precise control over the boundaries of shapes and intuitively is independent of angles of geometry – in contrast to geometrical selection (based angles of edges and similar constructions). In practice it has turned out to be very hard to track numeric indexing, for instance even peel range parameter is altered to extend to one more LE (Logical Edge). Moreover as operations are stacked up geometric complexity rises and numeric indexing becomes increasingly chaotic. As a results a simpler indexing system was devised.

01-Indexing

The idea is to still have number-based indexing, but to reduce number of labels to just two: “0” and “1”. The reason for two labels is that they naturally map to park layout where “0” corresponds to boundary edges and “1” marks the inner edges – with respect to the parent shape (see picture below).Though it is possible to have yet even simpler ‘unary’ indexing in range [0, 1) however in park designs it is important to distinguish between inner and outer boundaries, so arguably “01” indexing is ‘sufficiently minimal’ indexing in context.

Options

In some cases, for instance peel rule, there are two variants in what is labelled “1”:

1. Edges spanned by inner vertices, or
2. Edges where one of the vertices is inner and one outer, as in the shaped part of the image above.

Decision was to use the second approach where “0” indexing requires edges to be spanned by the boundary vertices only. Later a rule flags can be added to target exclusively inner edges.

Propagation

The shape boundary can not only be partitioned but modified for instance in place rule – in such case newly inserted vertices has to be relabelled (see picture). The following cases are handled:

1. Completely inner – trivial, labelled the same way regardless of direction.
2. Between two ranges with different labels – currently a simple solution is used where an unlabelled range are covered by the whichever label occurs first (“0” as shown on the picture above).
3. Data boundary (first index) occurring within the unlabelled range. This problem is handled by first rotating the whole polygon to start at the first zero-labelled edge.

Problems

Peel rule can result in splitting of the substrate part (image1 below) in two (or more) subparts when extruded part is large enough. Similar fragmentation can be caused by insertion of a placement shape (image2 below).

.

 

A similar technique has already been implemented in the early versions, but due to completely changed design we come back to it in this post.

Peel rule produces and extruded shape along the normal of each segment. It means this shape starts and ends at right angle to the appropriate segment. This is find when for instance when extruding a small section in the middle of the edge, however for peel ranges at the edge boundary this may produce substrate shape with sharp angles:

For sharp-enough angles (e.g. under 60 degrees) it makes sense to merge the extruded shapes with the neighbouring edges. Epsilon areas are added at the merge boundary regions to avoid erroneous shapes resulting from numerical errors:

In fact we just take two corners at the boundaries and unite them together with the extruded shape:

Given two geometrically consecutive edges e1 and e2 where e1.second == e2.first, we have two options for creating a boundary corner. For the front or start of the range e2 is used for extrusion and other way round for the back. The corner is simply triangle spanned by vector a – normal direction, and b – projection of a to the adjacent edge.

Projection of a to b

Let us consider the front case. Since a and e1 is known we compute b:

• from definition of dot product
  (|a||e1|cos),cos = dot(a,e1)/(|a||e1|),
• 1/cos = |a||e1|/dot(a,e1)
• By looking at right-angled triangl, length of b is
  |b| = |a| (|a||e1|/dot(a,e1)
• So b is unit(b)*|b| and since unit(b) = unit(e1) as both point in the same direction
  b = unit(e1)|b| = unit(e1)|e1| (|a|^2) /dot(a, e1)
  b = e1 * (|a|^2) /dot(a, e1)

Epsilon Extension

In the context of triangles endpoints corresponding to a an be span a line segment s = (o + a, o + b), where o is local origin: e1.second (or e2.first). s is extended in both directions by epsilon: s’. Boundary corner is now (o, s’.first, s’.second) for front and (o, s’.second, s’.first) for back cases.

Determination of Angle Sharpness

An angle formed between two edges e1 and e2 determines the need for boundary corners. Dot and Cross products informing about cos and sin respectively allow us to determine the quadrant of the angle when we consider e2 as fixed and e1 resolving around it.

We want the forth quadrant, when cos > 0 and sin < 0. When

• cos <= 0, angle between adjacent edges is sharp already or a right one which means that an extruded shape at boundary will touch the adjacent edges anyway.
• sin >= 0, we have a concave (greater than 180 degrees) for flat (180 degrees) angle. If we want to limit sharpness to 60 degrees the cross product is expteded to be within the range [-1, -sin(60)]

Direction of Indexing

When indexing is negative we need to:

1. Swap e1 and e2, because geometrically e2 preceeds e1, and
2. Change front and back flag, since the edges are swapped we expect front where otherwise back would go.

 

Attributes or global parameters are accessible by all rules. Even if an attribute only used by one rule, all instances receive the same value; they can also be thought of as flags. An attribute consists of three items:

1. type – a string which cay be either can be “number“, “bool” or of type option. The first are self-explanatory, in case it is an option the syntax is:
   "option" ':' <option_1> { ',' <option_i> }
2. value – a double precision number which can store a value of any other type. In integer is obtained by casting, boolean is obtained by comparison to zero, and in case of an option the count of the selected option is stored. Initially a default value is stored.
3. percent flag – if true, the value is relative to some other measure – as if percent.

An example clipping mode parameter, which determines whether an inserted shape is clipped to iregion or not, or discarded (if touches), is:
{ "option:ignore,clip,discard", 0, false }
Whereas path width parameter is:
{ "double", 10, true }

Problems with A1

Problem arises at the indexing boundary, that is if a merged vertex which source set includes a first vertex (index 0).

Copying LE Indexing

In a smoothed shape it should it should be known which are the original vertices – or the logical vertices, in contrast to the newly created vertices who’s purpose is to approximate the curve in geometry. This mapping is facilitated with LEs. We want this to have a consistent behaviour in subsequent operations and visual similarity (preserved topology) – no matter if smoothing was performed or not.

Vertex mapping options:

1. Complete – isomorphic mapping, where all of the indices are propagated to the derived shapes
2. Partial, where some of the indices are propagated. In this case there are missing source shape vertices, and indexing has to be made whole somehow.

In addition Propagation can be

1. Exact – each indexed vertex in the derived shape exactly matches (has the same coordinates) that of the parent shape. In complete and exact propagation a rule may only insert or modify non-index vertices.
2. Inexact – either closely laying vertices are used as successors, or some sort of mapping is applied. If we consider the whole smoothing operation – the vertices would have moved – but we can still track and apply appropriate indices to them.

Smoothing has Complete Inexact index propagation, because all of the vertices are kept (except for special cases of concave geometry?), but (depending on the smoothing method) they change their positions.

Clipping index propagation is Partial Exact, because some indexed vertices are discarded, while the remaining ones retain at their position.

Counting Propagation (P1)

First implementation of indexing propagation does not work for a number of cases as the following:

The vertices 3 and 4 need to be found in the source polygon (unclipped) which looks like:

and closup:

Which means there are only 4 vertices in the source and we are trying to fill 3 vertices in the place of two, that is in addition of vertex 1 and 2 we need to need to fit addition vertex – which is impossible or we would have a sequence like 0 1 2 3 3, because the first and the last LE indices have to match that of the unclipped shape as show above. Below is an image of how the indices are stored – array indices correspond to actual geometry indices of the clipped shape and the values are LE indices of the source (unclipped) shape:

The algorithm should replace missing LE indices (represented by -1, NOTE this is a bug in the algorithm; a subsequent fix has been applied and -1 replaced by 0) for new vertices created by the clip operation.

It was decided to abandon this algorithm, however for completeness the description as follows:

1. Hash source LE corners in rtree. In the case of Voronoi Diagram source is the unclipped polygon and LE corners are vertices stored clockwise (Boost Geometry format).
2. Interate over target (clipped) polygon vertices and see if a match is found with the source. This results in the array as on the picture above.
3. Find unknown LEs for the new vertices created from clipping (or other operation). We find first vertex that is defined, e.g. vertex 3 in the picture, and feel all the other vertices up to that with one less e.g. 0, 1, 2. In this example however there would be two zeros at indices 0 and 4 (picture below), which make this approach unsuitable.

Geometric Propagation and Smoothing (P2)

Boundary shapes are clipped to the iregion. The polygon part that is outside of iregion that are clipped away are called outer part and the result of the clipping that remain are inner part.

When smoothing is applied, if the boundary shapes are smoothed after clipping we the whole park layout consists of ‘blobs’ as in the first picture above, whereas the layout on the second picture is more desirable.

If they are smoothed before clipping – the boundary shapes are either missing or, for a large cell – they become very small. The reason is simple – since the outer part is much larger than the inner part, smoothing affects the inner part considerably more in the local scale (that is within the iregion), than the outer part. For this reason it is important to reduce the outer part before smoothing. , but at the same time leave some area outside the iregion to avoid blobs. Rather than preserving geometric detail on the part that is clipped away it turns out it is sufficient to evenly arrange remaining vertices at some distance from the iregion boundary.

Let us take expand the iregion (inverse of grassfire shrink) to create a clipping region. Each shape is clipped as follows.

1. Find intersections of the cell with the clipping region. There should be two (2) of them or we throw an error (discard or do not smooth the polygon.
2. Each intersection would belong to a certain edge. One vertex of such edge would be inside the clipping region and the other – outside. The two immediate outside vertices are moved in the place of intersections.
3. Span a line with two vertices at the intersections. The vertices between these two vertices are evenly distributed along the line segment.

Extended Geometric Propagation (P3)

Two problems with P2:

1. Line may cut into a large chunk of iregion, even if clipping region is large, part of the smoothed polygon will crawl into the iregion creating a hole.
2. Paths overlap – vertices are ‘smoothed’ inside too much.

P3 solves these two issues, picture below shows a smoothed layout before clipping.

1. Discard expanded clipping region, use iregion as clipping region (less work too).
2. Instead of spawning lines at intersections, extend ‘rays’ from intersection points away from iregion with a reasonable length (currently perimeter / 12). Endpoints of ‘rays’ span the line segment described in above in P2.

 FFregions Reconsidered

Voronoi Cell Details.

Because Voronoi Diagram spans the whole plane, the outer cells are semi-open. In such cells one edge is missing and two edges are semi-infinite – they are actually rays. To visualise a VD semi-infinite ‘ray’ edges need to be clipped to a reasonable (but large!) length. In fact implementation does not store this ray edge – such needs to be constructed when discrete geometry is created. For such ray only one vertex is known, so to form a finite edge the other vertex needs to be computed. Boost Polygon Tutorial on Voronoi Diagram describes how this is done and the layout generator uses some of the code from voronoi_visualizer.cpp. In this code the second vertex for a ‘ray’ edge is chosen as the midpoint between the current and the adjacent cell centres – edge is shared between these two.

 

Cell polygon can be constructed by taking vertices of the edges. Ray edge one ‘virtual’ vertex does not have an adjacent edge, so instead of taking say the first vertex (or second) all vertices could be taken. This certainly results in duplicates for inner edges and duplicates are to be removed subsequently. This is the first method used. The second method simply takes the first vertex, virtual or not, everywhere except for a ray edge where the second vertex is also virtual – in such case both vertices are used as shown on the picture.Every second vertex is in grey square. Because there is no edge between two ray edges – where the cross is, first vertex of one of the ray edges is taken – the one within a red square.

Quarters

Voronoi cells are shrunk  to form park quarters. The remaining space taken by paths and junctions. VD data structures use Counter-Clockwise (CCW) orientation while where as most operations are performed on boost::geometry polygon data types where vertices are stored clockwise (CW). A mapping between the two is created.

Junctions

Before Cells are shrunk, a VD vertex is shared by neighbouring cells. The shrunk cells each have shifted version of the same vertex [TODO picture], which are kept track of by a vertex id. Implementation stores shifted vertices under the entry indexed by vertex id. Since VD vertex has three neighbour cells [NOTE is it possible a 4-junction in VD? maybe in an artificial case?] hence junctions are triangles , we do not need to even worry about the order, just clockwise orientation. If the vertex is merged vertex mapping looks up the vertex that is shared with other junctions. In such case path segment is missing and junctions will share an edge.

Path Segments

A path consists of two offset parts of the mirrored edges. Edge id is also know during iteration and hashed against the position within a cell/quarter polygon.

Two twin edges  that are shrunk form a path segment. When vertices are tracked it is possible to smooth quarters and still preserve topology of path segments. In this case segment still based on the same but shifted VD segments, but more vertices which approximate a curve may be inserted in between two VD vertices of the given edge.

 Shrinking

Naive Shrinking A0 (Algorithm 0)

1. Go through every edge and offset it by a certain a given amount t along the (inner) normal.
2. Intersect each pair of edges – intersections form the new polygon.

Our implementation also extends each edge – to handle concave polygon (with a reasonable angle of incidence).

Grassfire Transform

The problem with naive approach is that topology may change, where the an edge may collapse, or for concave angles vertex may split into two, also summerised by Cacciola. These are called edge event and split events respectively. We want for polygons collapse a if each edge were set on fire, hence the Grassfire Transform. The reduction method is called Mittered-offset.

In the case of VD cells all polygons are convex (because of the intersection of half-spaces) so only edge events need to be handled. After we shrink a polygon with distance t from the boundary a number of edges might have collapsed, meaning a number of vertices might have merged into one (see second picture below). It is necessary to track which edges have collapsed – means no path segments for them, and which vertices are merged – vertex sharing for junctions.

Shrinking A1

A1 is based on naive shrinking.

1. Shrink Polygon naively (A0).
   Since this may create spurious geometry outside of the actual Grassfire polygon there might be some intersections with non-neighbouring edges.
2. Find non-neighbour intersections per edge.
   Find any additional intersections that trigger and edge event. To avoid neighbour intersection we shrink an edge by a small amount (Epsilon value) from both sides. We manually discard self-intersections. boost::geometry r-tree is used which operates which only allow to intersect a segment with an edge, we manually weed out edges within the AABB by intersecting the with each potential segment individually.
3. Merge neighbour and non-neighbour intersections,
   storing their edge id pairs.
4. Filter out spurious geometry.
   Intersections or vertices that inside the ‘buffer’, a polygon with hole are discarded. Buffer polygon the result of the union of extruded edges.
5. Create vertex and edge mappings.
   A client should be ignorant to which edges were removed (vertices merged), or whether the direction is clockwise.
6. Use mappings to create correct junctions and path segments.

Smoothing

Smoothing based on Logical Edges have been added. LE topology is preserved as can be seen on the second picture under Junctions subsection. At the moment only for inner cells (and respective path segments that are affected), since outer cells are quite large before they are clipped to iregion. After smoothing a shape shrinks so much – relative to the much smaller inner cells, that they leave the iregion.