Park Generator (alpha)

Park Generator v0.0.3

generator_alpha_version_screenshot

Quick Start

  1. Download and unpack the archive. README.txt found within describes how to install the Generator.
  2. Start SketchUp. Open Generator dialogue by going to menu Extensions -> Park Generator.
  3. Select a rule file which describes the park generation. An example rule file can be used initially.
  4. 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).
  5. Select the faces (could be just one, of course) in the SketchUp Drawing are where the parks should be generated into. For instance:
    1. Press ‘r’ to select Rectangle tool and to draw a rectangular polygon.
    2. Press Space to deselect a tool.
    3. Click on the middle of the new polygon to select its face.
  6. 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.

FF regions polygons

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:

  1. Shrink each quarter of the cell
  2. Each shifted edge (of the shrunk quarter) is paired with the twin edge to create a path section.
  3. 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.

Corner-based Selection Propagation and Basic Autoselection

Selection Propagation v1

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

peel-reindexing-on-integer-range

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

Problem is still present when:

  1. One or more of the (LE) corners are consumed for substrate shape
  2. 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 (ab) 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
  • Enclosed segments are searched
    • weights are sorted
    • best weight is selected as a corner shape
  • Ensures that we have distinct 4 corners.

 

Indexing and Selecting using Logical Edges

Logical Edges Implementation

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

le-basic

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
  1. Compute points of quarter centres (NOTE border quarters are slightly larger because path is subtracted only from one side; TODO fix that).
  2. For each unsorted quarter intersect find intersection with the quarter centre and save at the matrix array index. Do the same for corner shapes.
  3. Now it is possible to walk through matrix and access both quarters and corner shapes (corner quarters).
    1. Create labelled shape for each quarter
    2. Remove duplicate and middle-of-edge vertices for each corner shape and set it to appropriate quarter.
    3. Set indexing.

Peel Changes

  • Input remains the same
    • Iregion
    • Selection: list of non-overlapping intervals [a, b]
    • Extrusion size
  • Process separated
    1. Linestrings created from selection list and input shape
    2. Each linestring extruded into a single connected polygon
    3. Boolean polygon cutting and labelled shape creation
      1. Substrate shape created by differencing iregion with extruded shapes
      2. Fixing of polygons
    4. Indices are set
Linestring Creation

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

  1. 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]]
  2. (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]
  3. Ectually extract LE subedges.
    1. Get LE, as linestring on the local range [0, 1]
    2. 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.
  4. 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.

peel-diagram


Extrusion algorithm as follows

  1. Split polyline into individual edges or segments
  2. Create pairs of inner and outer segments; Outer segment may either lie on the polyline or outside when outer extrusion parameter is positive.
  3.  Extrude polygons or blocks are created. At this point however we cannot join them unless angle between adjacent segments is180 degrees or lower.
    extrusion blocks
  4. 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.
  5. 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.

Grid Quarter Selection

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.

For instance instead of:

Park ->(…){ ParkQuarter }

It is possible to have:

Park ->(…){ ParkQuarter | 0, 1, Quarter2 | odd, 1, Quarter3 }

In other words we replace label with label_list:

label_list = label_expr ( ‘|’ label_expr )*
label_expr = label | x_idx_expr ‘,’ y_idx_expr ‘,’ label
x_idx_expr, y_idx_expr =  [‘!’] idx_expr
idx_expr = NUM | ‘odd’ | ‘border’

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.

Selection v2

Previously to this point actual vertices were used for selection. A new selection system was needed that would widen (or create) an abstraction gap between geometry and identifiable element used in grammar. Because edge to vertex relationship remains the same we discuss vertex indexing only.

Indexing

Index array is used to access polygon vertices instead of dereferencing actual geometry. For instance vertex 0 is not the first vertex in a container of the polygon representation, but the first element in the index array, value of of which points to the container element. This way any geometrical operation does not violate logical or spacial order of the elements.

Current Indexing Problem

Auto selection (for instance that of Peel rule) is still not stable because the rule stores a set of vertices, but the selecting rule manipulates on ranges, which are edge based. Vertex to edge conversion looses selection of single vertices. In addition edge to vertex selection mutilates selection where two intervals are separated by one edge – both vertices of that edge are contained in adjacent selections, so reverse conversion unites the two selections into one.

Symmetry

Grid operation now enforces symmetry based on vertex indexing. Because the direction for x or y-mirrored regions change the direction (for instance to counter clockwise from default clockwise) and the geometrical representation uses requires of the same implementation for all elements – indexed orientation may differ from the actual one. Hence we can save indexing with two items, start vertex and direction. Start vertex is computed based on the outgoing edge orientation of one of 4 types. This works well for nearly grid aligned (of course also for perfectly aligned) shapes, but near diagonal shapes, for instance rhombus centres this technique does not work.

Path Parametrisation

In a previous approach to specify positions of the objects along the polyline for Insert/Place rules one would write for instance [0.3, 0.5, 0.7] – three objects in the centre separated by 0.2 (20%) of the selected path length. However it is quite tedious to specify each individual positions and not very algorithmic. New parameter subrule allows a shortcut: 0.3:n3:0.3 – meaning there is distance of 30% from each sides and three objects in the middle; an alternative form 0.3:l0.2:0.3 also works. In fact we can omit the last number as well 0.3:n3.

Implementation for Ray and Free Form Regions v1

Ray Cast Regions

As described already, the poisson scattered circles (2d disks) serve as locations for path centres, but certainly their radius is smaller than that of poisson disks – than to make room for the paths. Poisson circle radius as a rule parameter.

Paths are connected as follows. First each corner connects the nearest centre with a path. Second a single paths between all the centres is found – construction of a spanning tree. The algorithm walks through centres and tries to connect to each centre to one of the kNNs with the condition that such is not already connected. If all kNNs are connected, we simply do an exhaustive search for an unconnected one. Newly connected centre is selected as the next one. Only n-1 centres are processed this way, of course (|E| == |V| – 1).

The resulting tree may contain a crossing when embedded into the plane or a layout, so each path section is merged with the existing set of paths right after creation – otherwise when fusing (merging) the unconnected paths with the centres afterwards a boost geometry error will occur.

raycast-regions-v1

For next Iteration
  • Number of circles as a parameter (user would prefer that to the poisson radius)
  • More elaborate connections. Even if it is a spanning tree – perhaps try to create a graph that is embedded into a plane?
  • Region indexing

Free Form (Smooth) Regions

Poisson circles are scattered (the same way as above) and the centres are grown into Voronoi regions (or diagram), which are then shrunk (the same process as used for a straight skeleton creation), and smoothed by using subdivision. Subdivision weighting is another rule parameter.

freeformregions(voronoi)v1

For next Iteration
  • Better smoothing techniques – a polynomial curve perhaps?
  • Number of circles (same as above)

Spacial Indexing

Because centres produced in Grid v2 using intersection algorithm are not placed in meaningful order beyond 2 by 2 regions, we need to find a way to index them.

Rtree implementation of boost geometry was used. Rtree is basically b-tree with spacial indexing (n-dimentional rectangles), so insertions are automatically balanced. Alternatively it would be possible to individually intersect path strips, but for more complex algorithms or other patterns spacial indexing is much more beneficial (for instance in terms of search complexity).

Grid Indexing

To find region index we divide iregion into as many Indexing Regions (XRs), which would also take the space of the paths [NOTE will these XRs not overlaps with the negibouring regions?]. XR_i,j will obtain Non-walkable Region, NWR_i,j.

Each NWR will have x and y index from which symmetry can be obtained. From then we can choose how to compute a symmetry. We have SYMM_BOTTOM_LEFT and SYMM_BOTTOM_RIGHT which are self-explanatory with the same orientation for all blocks.
SYMM_RADIAL_2X2 we have orientations in 2×2 block set with the orientation = 3 * x + y*(int)(-1)^i, where i is x index, x = i%2, y = j%2.

For 3×2 (4 by 3 regions) and radial 2×2 symmetry result is as follows:grid-indexing-symmetry-3x2

Place Rule Development

Insert Rule

Insert rule takes as a parameter and selection of the input region – in form of points, or perimeter indices. It expects to have a shape in the body of the polygon. The shape is placed at the given positions around the perimeter or iregion.

NOTE: Second Insert rule can accept a set of iregions, instead of just one – apply function has been overloaded – to accomodate placement into a number of surrounding polygons. Also an index to the polygon that selection corresponds to is given.

Place Rule Implementation

Place rule has been implemented as a combination of Peel and a new Insert rules.

Both peeled polygons are forwarded to Insert rule.

The selection should only correspond to the edge of extrusion.

place rule

Peel Rule Development

Peel rule is inner extrusion.

First parameter is a selection – a subset of the perimeter. Perimeter is meant a closed set of edge line segments of the input region. Selection can be in either of the following formats:

  1. non-overlapping intervals (RangeSelection) [a_i, b_i] where 0 <= a_i, b_i  <= |E|,  for example [0, 1][2,2.5] selects the first and the first half of the third edges.
  2. list of edge indexes (EdgeSelection)
  3. Keyword based selection.
    • Operation affected selection.  Implemented – extrusion base and extrusion frontier of the peel rule.
    • Position-based selection. Yet to be implemented.
      • Border edges and n-neighbours
      • Border vertices and n-neighbours

Second parameter is the size we want to extrude or ‘peel’ by (of type Size1d_t) which accepts either absolute size or value in percent. The percent is relative to the average length of the edge.
In the next iteration it should be changed to the distance to the middle of the nearest edge.

Selection parameter of any type is converted into RangeSelection. Because we extrude separately for each edge, each range is split to integer (or edge) boundaries. For example [0.4,  2.9] is split into a list [0.4, 1.0][1.0,2.0][2.0, 2.9].

Each split segment is then extruded inwards, that is a new polygon constructed with the width given in the second parameter.  New polygons are intersected with the input polygon to cut away the corners that may protrude outside of the region.

The set of newly created polygon are subtracted from the input polygon to create effect of the extrusion.

Special Cases

  1. Extending inner corner at a concave junction in the middle of selection. When the junction inner angle is greater then 180 degrees.
    peel-concave-join
  2. Corners at the beginning and the end of the selection. When the inner angle at the junction is greater then 90 degrees.
    peel-corner-extension