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”:

Edges spanned by inner vertices, or

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:

Completely inner – trivial, labelled the same way regardless of direction.

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).

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:

Swap e1 and e2, because geometrically e2 preceeds e1, and

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:

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> }

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.

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 }

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:

Complete – isomorphic mapping, where all of the indices are propagated to the derived shapes

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

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.

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:

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).

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.

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.

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.

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.

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:

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.

Paths overlap – vertices are ‘smoothed’ inside too much.

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

Discard expanded clipping region, use iregion as clipping region (less work too).

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.

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)

Go through every edge and offset it by a certain a given amount t along the (inner) normal.

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 anglesvertex 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.

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.

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.

Merge neighbour and non-neighbour intersections,
storing their edge id pairs.

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.

Create vertex and edge mappings.
A client should be ignorant to which edges were removed (vertices merged), or whether the direction is clockwise.

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.

Download and unpack the archive. README.txt found within describes how to install the Generator.

Start SketchUp. Open Generator dialogue by going to menu Extensions -> Park Generator.

Select a rule file which describes the park generation. An example rule file can be used initially.

Set any optional parameters. Please note that rulefule will override any parameters by “parameter_name = parameter_value” line in it (though it is a matter of discussion whether it stays that way).

Select the faces (could be just one, of course) in the SketchUp Drawing are where the parks should be generated into. For instance:

Press ‘r’ to select Rectangle tool and to draw a rectangular polygon.

Press Space to deselect a tool.

Click on the middle of the new polygon to select its face.

Click on Generate button.

Depending on the rule parameters it might be instant or take some time, if for example the number of subdivisions and placements is great. Please not that scatter distribution radius (Scatter rule) can affect the performance – for a smaller radius will result in more samples generated.

The whole generation is recorded as one SketchUp procedure and undo can be used to revert the state of the original polygon (iregion).

Example Rulefiles

The generator comes with two sample rule files in “example_rules” folder. First one generates a Grid-like park and places trees in the middle of square regions and scatters some grass around it. The other generates a park with radial paths/junctions, places trees along the boundary and bushes in the centre regions.

Version 0.0.3 Notes

Plugin currently works with rectangular shapes best. If an input polygons contains more than 4 vertices it will try to detect a quad and use it. If nothing is produced – the shape was not accepted. Weird input shapes may crash the plugin (this will be fixed in the next releases).

Only two partitioning rules are supported currently (Grid and RayCast). FFregions rule currently fails for almost half of the input of rectangles of various sizes (a bug in the partitioning algorithms which is triggered when one of the edges of a partitioned polygon is small enough).

Peel rule may result in bad shapes when applied after RayCast rule – for some inputs.

To compute FF layout fist we create park ‘quarters’ which are non-walkable. Because paths are computed from quarters, simply subtracting them from the polygon will result in a polygon with holes (see middle image below). To break loops we have to partition paths. There are few ways to acomplish this, for instance just one edge splitting the polygon loop would be sufficient, or the method described earlier that works better with the boost geometry library. However to be consistent it was decided to adopt similar structure to that of Grid rule where all paths are split into separate path centres from path sections.

First Methods

The centres were generated from a list of shifted vertices around each voronoi cell vertex. Shifted vertices were collected from each cell and stored in a map under a key of unshifted or voronoi vertex (for instance stored in std::map<point, std::vector<point>>). Cells are could be accessed in no particular order, for instance simply iterating over the cell container, and eventually each vertex would have received all shifted vertices within the neighbouring cells. Because search for the cell vertex is logarithmic the operation is expected to be of nlog(n) complexity.

In theory it would be only sufficient to compute centres and (picture 4) and subtract them from the paths with holes (or what is left after subtracting quarters, picture 3) from the iregion (picture 1) to create separate path sections. Alternatively we could subtract a union of centres and quarters:

iregion – (centres + cells)

However neither methods yield correct results with boost geometry, for instance as we can see of the second method in the last picture (the three paths sections in the lower left corner were generated).

Second Method

The previous process has failed because perhaps the algorithm was forced to work on non-manifold data (punctures). Instead trying point-edge operations (non-manifold) we separately create path sections which result in edge-edge operations with both centre and cell/quarter polygons.

Boost polygon provides half-edge data structures which was taken advantage of. Procedure as follows:

Shrink each quarter of the cell

Each shifted edge (of the shrunk quarter) is paired with the twin edge to create a path section.

For each original vertex – shifted vertices are also stored as well which are used to create a path centre.

It is important to note that come cells were open, e.g. with infinite edges. However we have already used an existing solution described in boost polygon documentation.

Shifted edges were created using normal-direction offset and subsequent intersection. To make certain intersection occurs edge was extended at both ends. It was also made sure only adjacent edges (those that share a vertex) were intersected – without such test intersections of the infinite edges which are adjacent in the data structures but not adjacent geometrically have been occurring at the other end. Shifted edges were computed per cell. To create a path section each a shifted edge had to be paired up with the twin variant and only once. To obtain the shifted twin we get list of shifted edges for appropriate neighbour and then the index of the twin within that list. The index is obtained from edge_id – > local_edge_id hash which was implemented as an array.

Shifted vertices were collected from the first vertex of each edge. Unlike the previous methods an array is used instead of the map to group around the ‘unshifted’ vertex.

The whole operation should be of n complexity (linear) because a linear access for all adjacent elements within half-edge based data structures. Boost polygon does allow to store a colour with each element – it was used to store container indices of each element.

In the Peel rule substrate shape is partially altered. In the best case corners are left intact only LE internals are changed when extruded occurs within a single integer range, e.g. [0.1, 0.9].

A new selection propagation mode uses corner vertices to propagate selection for peel.

Problem is still present when:

One or more of the (LE) corners are consumed for substrate shape

Propagation occurs on extruded shapes, or the newly created shapes, those that do not include the substrate.

Autoselection

Threshold based

Selection mode can no be altered with the auto-detection function. Besides basic angle or dot product thresholding both length and angle can be used.

For instance two lengths those to the previous and next vertices (l1 * l2) / (l1 +l2) or (l1+l2)/ 2 are compared against the mean length.

Angle Range based

For quarters are built

clockwise

starting from [pi*5/4, pi*7/4]

angles converted to direction vectors

cross product based detection

the cross(x, a) is negative if x comes before a clockwise and positive if after.

can easily determine if x is between a and b, where cross products must be positive and negative respectively.

Let vertex x_i be corner vertex when x_i is outside of range (a, b) and x_i+1 is inside of it.

Growth based

Cardinal direction rays leaving centroid

Rays should intersect one edge (segment) each

Shape is either too bad and non-convex when more intersections are found

..or when one segment is intersected by more than one ray we have malformed shape as well.

Weights based on dot product computed for the whole shape

As mentioned already, logical edges (or LEs) contain multiple physical (or geometrical) edges. A selection unit is now a logical edge instead of a physical vertex as it was previous to this moment. Indices and directions are still used but relate to LEs instead of vertices. LEs are implemented as integer values of a start vertex and the length of the path to the next corner vertex.

When length is zero selection is no longer contains edges could represent a single vertex.

Autoindexing Input Region

A polygon with |v| > 4 but that roughly looks like a quad is treated as a ‘quad’ by partitioning all edges using (currently only) angle thresholding into 4 LEs

Vertices of the detected LEs or corners are also used as a corner shape for the Grid rule, because for path partitioning Grid rules requires a quad as input.

Grid Changes

adapted LEs to be used as input

Subregions (may be non-quads) and Corner Shapes (quads) are spacially indexed the same way

Matrix indexing

Corner Shapes may contain vertices that do not add new geometric information. Such vertices are removed. Thresholds were increased to deal with increasingly large Epsilon values.

Almost identical vertices, that is with an Epsilon distance between them are removed.

Vertices that span an angle of close to 180 degrees with the adjacent edges are classified as middle of the edge vertices and are removed.

Matrix Indexing

Compute points of quarter centres (NOTE border quarters are slightly larger because path is subtracted only from one side; TODO fix that).

For each unsorted quarter intersect find intersection with the quarter centre and save at the matrix array index. Do the same for corner shapes.

Now it is possible to walk through matrix and access bothquarters and corner shapes (corner quarters).

Create labelled shape for each quarter

Remove duplicate and middle-of-edge vertices for each corner shape and set it to appropriate quarter.

Set indexing.

Peel Changes

Input remains the same

Iregion

Selection: list of non-overlapping intervals [a, b]

Extrusion size

Process separated

Linestrings created from selection list and input shape

Each linestring extruded into a single connected polygon

Boolean polygon cutting and labelled shape creation

Substrate shape created by differencing iregion with extruded shapes

Fixing of polygons

Indices are set

Linestring Creation

Given iregion and a selection extractBoundary computes a linestring around the boundary of the iregion.

Split one selection range into selection for reach LE and pair with index of that LE. Whole LEs of course will have range [0, 1]. For instance selection [0.6, 2.3] will result in the list:
[0:[0.6, 1], 1:[0, 1], 2:[0, 0.3]]

(optional) Ranges are reversed if selection direction is negative. Also each LE selection ranges are reversed [a, b] -> [1 – b, 1 – a]. Note that LE indexing is not changed, only the order of evaluation to closely match physical representation. For example the range above converted to:
[2:[0.7, 1], 1:[0, 1], 0:[0, 0.4]].
[TODO picture]

Ectually extract LE subedges.

Get LE, as linestring on the local range [0, 1]

Extract ‘substring’ or [0, 1] converted to [a, b] which could be[0.7, 1]. The algorithm also rather large in code is quite trivial nevertheless, important only to mention is that the edges are parametrised by length.

Joing LE subedges into one linestring, removing duplicates at joining points.

Extrusion

Initially only inner extrusion has been used. However as a result of floating point errors using Boolean operations – part of the boundary was not clipped appropriately. In the second iteration outer extrusion has been enabled and which amount controlled by an additional argument.

Extrusion algorithm as follows

Split polyline into individual edges or segments

Create pairs of inner and outer segments; Outer segment may either lie on the polyline or outside when outer extrusion parameter is positive.

Extrude polygons or blocks are created. At this point however we cannot join them unless angle between adjacent segments is180 degrees or lower.

Joining polygons are created connect adjacent blocks. To accommodate both inner and outer extrusion joining polygons are applied to the whatever side of the polyline that has a greater angle. For zero outer extrusion empty polygons are added.

Inner product algorithm joins sets of blocks and joining polygons where both * and + operation overloaded as a joining operation. Because number of joining polygons is one less, an extra one is added to match the number of blocks.

It is necessary to select a quarter (or subregion) resulting from the Grid rule. Instead of a single label, a list of expressions paired with labels are now allowed – when expression matches a given quarter – label is selected. At the end there should be a label without expression to guarantee a label for for a quarter that has not been matched by the other expressions.

Where index expression is either a number or a constant label which corresponds to multiple indexing of being either odd, on the boundary. We could also have a negation of an expression. However negation applies to individual axes, for instance “!x, !y, Label” negates both x and y.