Autoindexing of the Input Region

Input Shape Autoindexing

Since physical edge indexing is being abandoned, we introduce logical edges – groupings of the input region edges into geometrically (or otherwise) meaningful sets. Selection indexes shall correspond to that of these sets. Applied rules should preserve/propagate these edge sets.

Following shape classes could result in the following actions:

1. Rectangular quad – trivial case.
2. Quad, not axis-aligned, we can try:
• simple: determine index for the first edge, increment successive edges
• harder: compute Oriented Bounding Box; translate longest edge of that to x-axis; edge to the left (W-edge) has index 0.
3. |e| > 4, but roughly looks like a quad:
• Cardinal Directions selection will create 4 groups of edges
• …?
4. |e| > 4, looks like a multi-polygon
• length/angle threshold.

Grid-based Parks

Grid rule requires for input region to be a quad and ideally rectangular or close to rectangular or it will look strange. In other words we need to provide the following guarantee to Grid rule:

1. |Vi| == 4, Vi are vertices of the input region – a quad
2. All angles >= threshold1 (e.g. 70 degrees) – close to rectangular
3. Min Area >= threshold2 – minimum area required to build a park, otherwise fail (no derivation or a alternative rule)
4. Input region convex – otherwise results make no sense.

The following fixes apply to the appropriate points

• Oriented Rectangle (Box): 1, 2, 4
• Bounding Box
• Inscribed Box
• Linear Combination
• Optimised Box that occupies area sufficient for a park (harder problem)
• Axis-aligned box: certain design constraints
• Autoindexing: 1
• Cardinal directions when looks like a quad; Grid still requires a ‘corner shape’ which can be a quad with vertices corresponding to the meething points
• Autoindexing + Oriented Box,
• which vertices are at proximity (using a certain function) to the meeting points

Possible solutions for Selection v3

The selection problem is plagued by edge explosion and increasingly complex and dubious grammar results. New selection strategies are to be considered. Furthermore a layer of abstraction is to be placed between the physical and logical geometry elements:

• Corners or logical vertices – corresponding to selected vertices on the actual geometry that have a special importance
• Logical edges – should be enclosed between two corners and may contain a number of physical edges within – a polyline, or a curve. It should be used as a unit of selection (an integer range).

Selection Modes v3

Abandoning the physical based selection the new methods keep numeric indexing, but pointing to logical edges instead of the physical ones, as we see later.

Selection Propagation

Each rule should be capable of propagation of default input selection  to derived shapes the best way possible, for instance as seen below for the Peel rule.

For partitioning rules such selection will be based on closeness to the boundary:

• Whether or not it is located on the boundary
• Edge set touches the boundary

Optional: specify level within the hierarchy to as closely as possible to match to the current geometry of the shape. For instance one before last Peel rule or first Grid rule (could use negative indices to count from the ‘front’ of history).

Grid rule auto-reindexing is straightforward except for question of what to do with 45 degree edge – it can belong to the lower or higher index or split between both, as seen below – in this case it is crucial that edge assignment is symmetrically consistent.

For Voronoi regions there is a little more ambiguity so one selection method has to be chosen.

Custom Shape Selection

In addition of edge set index based selection, rule can perform a custom selection on any part of the input shape boundary.

Edge Angle Selection

Select edges which orientation is within a given angle range, e.g. [85, 95] degrees are roughly perpendicular edges.

Angle Range Selection

Select edges that lay within or partially within the radial region surrounded by two rays cast from the centre.

Direction Grow Selection

A number of directions are given. May result in inconsistent selection for non-convex shapes!

• Cast rays from the shape centre along these directions until an edge is hit.
• Grow selection for each edge. Attach successive neighbours to the existing selection.
• Stop when threshold of subsequent edge is too high
• Question: What to do with unattached regions?
• Keep growing until all edges are attached
• That containing more divergent (from threshold) value continues
• Optimisation problem…
Cardinal Directions Selection

Based on W, N, E, S directions. Every polygon with |e| >= 4 should be capable of accepting a cardinal selection.

• Edge Angle selection should with appropriate angles (for instance [-45, 45] for East) will work only for convex shapes.
• Angle Range selection will also work on concave shapes but will not work so well when lengths of the sides (or edge sets) differ a lot (high variance of edge set lengths).
• Direction Grow along the axes.
• Dominant-direction symmetrical selection.
• In the picture above (Reindexing for Grid rule) the dominance (say set by the user or selected to one value by default) is symmetrically consistent for the mirrored regions.

Rule History Selection

Such selection has already been discussed for Peel rule. However is it possible to create generic selection that all rules could adhere to?

Recursive Peel and Edge Indices

Selection

The problem with selection arises when we have a non-quad shape in a rule production.

Indexing of regions, for instance in the context of the grid rule works well as long as we have [0-3] indexes for W(est), N, E, S directions.

Instead of one type of index based on orientation, or distance from the boundary, we need other types of indexing methods, for instance those that are semantically-aware.

It would be nice to have the following selection modes

• Edge interval that was result of the peel operation
• when placing something between the peeled regions
• Outer iregion edges
• when placing something on the boundary
• Direction based (W N E S) edge selection. If we have multiple edges facing West, parametrisation, by length, will be of the combined edge length – those facing west
• we want to place trees on the south-facing borders
• Direction continuity selection. Selection for West-dc edges will also include edges NOT facing west, IF they are resulted from operation from west facing edge OR (!) when they are enclosed by west facing edge.
• we want to place trees on the west side of the park but not all edges may face west

Index operators v2.1

Peel based selection

Shapes that result from the peel operation allow edge selection based on what was peeled. For instance a is the selection passed to the peel operation; b and c were extruded.

• PEELED_BASE, short version – PB, the ‘a‘ segment in the image
• PEELED_INNER, PI, ‘b’
• PEELED_SEGMENT, PS, ‘cbc’
Implementation Details

During peel operation a and b are recorded by storing copies of the points. Another operations on the derived shapes can make selection based on these edges, for instance  for PEELED_INNER selector if an edge endpoints are in b, then it is selected.

Boundary Indexing

Two options for such:

• Edges incident to iregion (corners). The problem is that there may be more vertices between two corners – we need to consider an ‘edge’ between two corners NOT vertices.
• All edges resulted of splitting or modifying iregion edge. Edge implementation does not need to be changed however more operations – intersections – are required; extra problems might arise from the intersections.

Enumerated Indexing for Grid

We are returning to enumerated indexing.

Lets consider the 1×1 path (2×2 regions) case again.

Indexing shall start at the iregion corners. The direction will be determined where the second index is.

Since iregion indexing starts at SW – the lower left corner, it shall be mirrored to the remaining elements (in 2×2 regions it is simple!).

Polygons are ALWAYS oriented one way, in our case clockwise. The indexing system allows us to avoid re-ordering vertices after each operation!

Non-symmetric partitioning – first indexing ideas

Symmetric design apply to grid-constructed park, but not to beam and grow-based (Voronoi) region partitioning.

We still require some a form of addressing when placing the elements within these regions. We need to find a way to index the edges and corners.

Common functionality

The non-symmetric methods accept a list of points as a parameter, which are the centres of the circles completely within the boundary (or just to say that the centres are of a certain distance from the boundary).

Beam Partitioning (RayCast)

Edge Indexing

• Edge 0 will be the first edge from the centre (that does not lay on the centre)
• Which one of the two will be determined by the orientation (default is clockwise).
• Corner 0 will be the vertex that coincides with the centre region and the  Edge 0.
• if Centre is non-zero, there will be an Edge that represents the centre boundary

POSSIBLE ALTERNATIVE:

Because symmetry can still be preserved but WITHIN a single region of consideration.

• Edge indexing starts with 1, and -1 in the other direction (counter-clockwise).
• Edge 0 exists in case Centre is non-zero (except for the widths of the paths)
• Similar indexing strategy for vertices.

Further partitioning needs to consider the boundary of the region. Two options are possible:

• Match the the sides that are not parallel to the boundary/edge that is uses as a reference.
• Keep the shape, e.g. preserve the angles and scale the are to match the available space.
• NEW IDEA have a new rule that would fit in the rectangular shape into the available space
Multiple Centres

It should (may?) be possible to have multiple centres in the rule. The problem arises of how to connect the centres with paths, building a walk-graph.

Centres Connection

The rule should be independent of the number of centres and number of corners. Instead we must have some guidance how to build the graph.

Some ideas:

• Cast the ray to the nearest corner only. OR
• cast the ray only if the corner is not connected (or inverse cast corner -> centre)
• cast ray to all corners, without intersecting other paths (HOW??)
• Have a sub-rule on how to join the centres some options
1. Leave as it is – completely disconnected
2. Join in a loop or closed path
3. A loop without a single edge – a tree; chosen at random
4. Join pairs of centres
5. Join opposites – intersections? What if there is an odd number of vertices? How to select two equally weighted opposites?
6. Completely random?

Grow Region Partitioning

Symmetrical placement is even less applicable to this method because it is much harder to predict the number of edges that the region is going to have.

Counting the index perhaps would not make much sense (why?) Instead the designs should be developed taking into the account the inner and outer edges and vertices.

Although the subregion may have more then four corners, it is often necessary to map a region to a quad.

Issues

• Non-convex beam paritioning – remove paths that are casted to the outside area
• More formal specifications for terms
• opposite centres in the sides
• delauney triangulation – connects into a graph
• planar graph – must be plannar

2D Local Parameters instead of Offsets

Edge and offset local space addressing as discussed in the previous post introduces is redundant whereby two operations from the opposite edges produce the same result. For example you could either take edge 0 or 2 and count parameter from the other end (1-p for edge 2) and use the same offset to locate the same position.

We introduce several local addressing modes based on x and y coordinates. This is intuitive and directly maps to the xz plane in 3D world.

We have the concept of a corner instead of a vertex, because vertex refers to the geometric rather than semantic element. For instance there could be an arbitrary number of vertices between some two corners – depending on the geometric detail.

2×2 Grid Case

Let us again return to the previous post where the symmetry is achieved by labelling edges. All operations including offset are mapped to achieve symmetry against x and y axes.

Instead we map the local coordinates to [0..1], based on the proximity to the corner of iregion.

Hence origin is the nearest iregion corner.

Above we see the 2×1 (or top of the 2×2) grid. The circles (tree ground areas) are placed at (0.8, 0.1), where the origin is top left corner for first cell and top right corner for the second cell.

This way we can easily place items symmetrically in all quadrants of the 2×2 grid. For now we will ignore the cases where park centres are larger the path junctions.

3xn Grid Case

In the case of the 3×2 grid the question is what to do with the subregions in the middle? Or even grids of the higher dimensions, or the odd ones?

We have two approaches:

1. To apply a different rule (number 2) to the middle row elements
(will deal in the next section of edge parametrisation)
2. Automatically adjust the erroneous coordinate – one of x axis in the case above.

Let us consider the second approach. Then there are four options:

1. No centre axis coordinates. In x axis case (picture above) x coordinates are mapped to the centre – the blue circle in the top middle cell.
2. Extended right. The coordinates are extended left to right as seen in the middle block below. Because the rules tells us to draw at (0.8, 0.1) and current cell coordinates are out of the range – nothing is drawn
3. Extend left. The opposite of the above case.
4. Local to right. Also left to right but the counter is reset. In this case the left most block duplicated. Here symmetry is broken so this technique is not favourable.

Auto-centering axis as in (1) may result in park like this:

However this is too of a simple example and with a few elements there maybe a conflict where they are nested together.

4xn Grid Case

Again we consider x axis, operations for y axis can be adapted appropriately.

1. Pair mirror. Simply repeat the 2-cell pairing.
2. Mirror against centre. Repeat the boundary elements to the centre.
3. Extended addressing. The rule that draws to (0.8, 0.1) will not draw anything, but another rule can be used to draw there.

Automatic symmetry is the most desired solution as it does not require different treatment of the cell depending on the position, however I anticipate that  it is hard to achieve it correctly, especially with a large number of elements.

Now we consider perhaps a more practical approach that takes into account symmetry, where each of the cells that are not symmetric to each other are considered  separately. Each cell type will have a different set of rules, perhaps using a case/switch statement.

In 3×3 grid as considered below there are 4 different types of cells. Type 2a and 2b may be different without violating symmetry constraints – both types have a single boundary edge, one lays on the x and the other on the y axes.

The number in the picture is used to count the boundary relations or a boundary metric distance.

A 4×4 grid can also have 4 different classes and 4 types as the four cells in the middle should be symmetric with each other.

For grids of higher degree the number elements is certainly higher. For example 5×5 grid may have 9 different regions and 6  boundary  metric distance classes (2, 3 and 5 may be doubled).

It is possible to have various scenarios where symmetry has to be complied with, but perhaps it would often be easier to use a recursive application of grid rule. In an example below complicated conditional testing for 4×4 grid – it is easier to just use 3×3 grid and nested grids 1×2 for A and 2×2 grid for B.

Boundary Metric

In addition to corner-based addressing we require indexing of the whole cell based on their type.

Elements of the same type are symmetrically identical – under {x, y} mirror and translate operations.

All elements of one type shall have the same boundary metric index which is a 2-vector value (or attribute) – least distance to the iregion boundary.

Index of the corner cells is (0, 0). Corner values also have two edges lying on (coinciding with?) the iregion boundary.

Index of the cells grows as they get further away from the iregion corners. For instance top left cell is at index (0, 0), cell (1, 0) is directly to the right and cell (0, 1) is directly downwards, as can be seen on the picture below. Type index is in fact Distance from Outer Edge (DOE).

The concept of symmetry is upheld, in that is the indexes only grow as high as the middle of the grid in terms of x and y axes and decrease as you go further away from the middle.

Rule interfaces

Region Partitioning Rules

All of the rules described below do not alter the area of the input region, but instead partition it into a set of subregions all entirely contained within the input region.

No holes are present in the resulting subregions – that is every subregion has boundary either shared with another region or with the outside world.

Partitioning results with a set of non-walkable regions, for example grassy areas of the park, path network and optionally centres at the path crossroads/junctions.

We should now the sizes of the resulting elements at the point of a partitioning rule evaluation, and unambiguously so – because each of the resulted subregions should know it’s size when they are evaluated further. For example we should specify the size of the path crossroads/centres because they affect how much space is subtracted from the neighbouring regions.

Note that the crossing centre region could be partitioned to contain another non-walkable region inside of it which could be used to construct an arbitrary sub-park. However because the size of the crossing is known during the partitioning rule, other regions are unaffected by what actually happens in the centre (it can be considered as a single node).

Grid rule

Partitions region into a regular x,y grid elements with paths in between.

Grid(dim_x, dim_y) { region_operations }
Grid(dim_x, dim_y) { region_operations } { path_operations }
Grid(dim_x, dim_y) { region_operations } { path_operations } { path_centre_operations }

• dim_{x, y} = range [ “a” range ]    // optionally angle values
range = num | “[” num, num “]” // either a number of a real range of numbers
• region_operations – to construct the non-walkable region, i.e. everything other then the path
• path_operation (optional) – rules that construct the path; defaults create standard paths
• path_centre_operations (optional) – rules for path crossings. If omitted normal regular crossroads are created. The following
Example:

```Region -> Grid(2, 2) { ParkQuarter } { ParkPath } { Romb(3) Fountain } ```

Alternative would be to have two symbolic region parameters for the ‘grid’ rule. For example:

```Region -> Grid(2, 2) { ParkQuarter } { ParkPathCentered } ParkPathCentered -> joined { RombCenter(..) ParkPath(..) } ```

However in this case the ParkQuarter does not have a region geometry fixed when it is mentioned in Grid rule.

Implicit Attributes

Each non-walkable region may differ based on the proximity of either of the region’s sides/boundaries/edges. The output attributes will be discussed in the later post in detail.

Alternative Notation

To stay in tune with CGA grammar of CityEngine, alternative notation may:

Grid(dim_x, dim_y) { region_operations | path_operations | path_centre_operations }

Questions remaining
• Variation of the crossing centres – should happen within the grid rule for non-walkable regions to know their sizes

VoronoiRegions Rule

Partitions a region using Voronoi algorithm and optionally smoothing algorithm/function.

VoronoiRegions(point_set, smooth_function) { region_operations}
VoronoiRegions(point_set, smooth_function) { region_operations} { path_operations }

• point_set – set of input points to grow from
• smooth_function -(optional) how to smooth the resulting regions; if unspecified, (2x) average function is applied
• region_operations – sequence of rules from the non-walkable regions
• path_operations – (optional) sequence of rules for the path; if unspecified

Example:

```Region -> VoronoiRegions(CircleRegions) { SmoothRegions } { Path } CircleRegions -> ScatterCircles(5 {[5-10]})```

Regions are reduced by path_width/2 to give way to the paths. Path amalgamated region is what is left when the on-walkable regions are shrunk.

Questions remaining
• How to incorporate smoothing
• What kind of smoothing functions available
• no smoothing should also be possible
• It should also be possible to build something at the region centres.

CastRays Rule

Partitions the region using ray-cast principle taking centre the source and the destination into account.

CastRays(source_point, target_point_set) { region_operations }
CastRays(source_point, target_point_set) { region_operations } { path_operations }

• source_point – the origins of the rays, where the rays are cat from
• target_point_set – where to cast rays to, which could be directions where the roads will go to
• region_operations – non-walkable region rules
• path_operations – (optional) walkable region rules

Example

```Region -> VoronoiSmoothed(CircleRegions) { SmoothRegions } { Path } CircleRegions -> ScatterCircles(5 {[5-10]})```

Peel rule

Extrude the subset of the boundary inwards (normally) of the region.

Peel(boundary_selection, size1, Flags…) { region1_operations | region2_operations }

• boundary_selection – subset of iregion boundary
• subset of edge line segments
• whole edge selection OR
• parametric edge selection
• region1_operations, region2_operations – rules for the two regions, the first one being the newly created region and the second region taking the remaining space
• size1 – how much to peel; can be absolute (meters) or relative (0..1)
• flags
• CornersOrthogonal – when true the corners are moved perpendicular to the edge extruded. By default corners follow the adjacent edges

Output always produces two closed regions, with one shared boundary.

CGA grammar has a number of similar rules: setback, shapeL, shapeU, shapeO and offset.

Example

`ParkQuarter -> Peel(OuterEdgesSelection, 0.75, CornersOrthogonal) { TreeStrip | GrassRegion }`

Questions remaining
• Is it possible to apply smoothing to the pealed region?

Contract Rule

Contract(units)
Contract(units, centre)

• units – amount to contract by towards the centre
• centre – contract towards this point

Contracts the region towards the centre (of mass).  Centre can also be specified as a parameter

TODO find out if s rule would be sufficient.

Scatter and Place rules are responsible for distributing objects of non-zero volume along the surface of the park

Place and Rule

(Also includes Distribute functionality)

TODO determine how to use selectors

`Place( CENTRE) { TreeRegion }`

Scatter Rule

(also includes scatter circles functionality)

Sweep Rule

(Previously called SmoothDistribute)

Sweep(line_segments)  { Operations }

• line_segments – where to instantiate the operation

Creates a volume over the defined area or defined line segment when width is specified.

Non-mutating Rules

Parametrise Rule

Parametrises perimeter of the region by continuous edge segments

• Input – region who’s boundary should be parametrised
• alternatively a set of edges
• input2 – list of ranges
• each range subset of range [0..1], represents the subsegment of the current edge
• output – list of ranges mapped to the context of the input

Example:

Parametrise([0.1, 0.9] [] [0.1, 0.9], Square(10))
Results in two line segments…

Questions remaining
• Edge indexing determined by the partitioning algorithm
• symmetry is specified then – will be discussed in the latter post(s)

IO Functions

loads a static mesh from the file.

Ideas To develop (TODO)

Polygon Spit hints

We should delay splitting the polygon as much as possible.
Even more abstract would allow polygons with holes in the system. However that is unnecessarily complex and is potentially a problem. For instance non-trivial triangulation.

Selectors

Edge selectors, vertex selectors, indexed based on the symmetry relationships.

Operations for the Simple Square Park

1. Grid operation creates crossroads with custom centre and subtracts it from the square polygon resulting in a one path region and 4 non-walkable regions.
2. Extract the place holder for the fountain in at the centre of the crossroads. (Alternatively: just place the fountain in the centre)
3. We deal with each of the 4 non-walkable regions by applying the same operation, mirrored against the paths accordingly. We use Peel operation to split the outer edge into a L-shaped polygon. It is subsequently filled with trees
4. Ground area for the tree is inserted in the inner park polygon which represents a Grass Area. To avoid holes (see previous post) the Grass Area is split in two.
5. Finally bush volumes are added. This is done by parametrising the perimeter of the containing polygon and contracting it. Arbitrary subset of the perimeter can be used to create a path which is then extruded into a volume.
6. Placement of trees and fountains as external models is performed at the end (picture not shown).

For this example the grammar shall look like this:

Region -> Grid(2, 2) { ParkQuarter } { ParkPath } { Romb(3) Fountain }

ParkQuarter -> Peel(OUTER) { 0.75: TreeStrip | GrassRegion }

TreeStrip ->  BLUE_GRASS
Distribute (OUTER_EDGE: 0.375, 2) {TallTree}

GrassRegion -> GREEN_GRASS
Place( CENTRE) { TreeRegion }
DistributeSmooth( Boundary1(Perimeter))  { Bush }

fun Boundary1(area) ->
Parametrise([0.02,1], [0, 1], [0, 0.15], 0) { Contract(1, area) }

TreeRegion -> Circle (1)
Place (CENTRE) { Tree }

Rule Design – Circular Paths

Because of high rate of occurrence of the circular structures in the park, it is reasonable to introduce an operator that breaks the region of the park along the circle.

A simple example is where a circle is placed somewhere randomly within the park with the minimal radius between the circle and the park boundary. Rays are then cast towards the boundary of the Park.

Rays can be cast towards the corners of the park, as can be seen in the last (4th) picture.

Termination condition for the rays are when the region boundary are met.

The center can be extruded into a custom shape – which can be in turn another region as can be seen in the first picture.

Example rules:

• CentreRegionSize = 5
• Region -> CastRays(CentrePoint [CentreRegionSize], CastToList) { CentreRegion } { CutRegion }
• CentrePoint -> ScatterCircles(1 {15})
• CastToList -> Corners(Region)
• CentreRegion -> Fountain
• CutRegion -> Grass

Because the Free-Form Construction using Grammar is quite a complex topic, we limit ourselves to the simple techniques.

The picture above is of a park constructed between blocks of flats in Manhattan.

Construction process is proposed to proceed by first scattering circles within the region with the specified radius that should not come in contact with one another or the boundary.

Afterwards we grow the regions starting from the circle centre points, resulting in Voronoi regions.

The resulting boundary can be varied by offsetting it with random values along the averaged normal.

Individual regions are contracted and smoothed out. The space between the regions is the path. Separated regions are populated previously described techniques.

Rule Example:

• Region -> VoronoiSmoothed(CircleRegions) { SmoothRegions } { Path }
• CircleRegions -> ScatterCircles(5 {[5-10]})

Rule Design – More Complex Grid Parks

Recursion in Grid Parks

Grid rule can be used recursively to implement more elaborate results.

• PathWidth = 2
• Region -> Grid(3 {2, 6, 2} , 2 {6} ) { NestedRegion } { CementPath }
• NestedRegion -> Grid { TreeRegion } { StonePath }

First of all we set the path width to 2m. First of all we create a grid with 2/6/2 meter long along x axis and 6 meter long along y (or z) axis.

The path can be changed wen supplied as the second structure (second expression in the curly braces).

When the size of the grid is not given, it tries to automatically fit the elements within, pacing path areas in between.

Irregular Grids

There are a lot of examples of parks with non-rectangular grids. One of the park examples is give above.

The two pictures sow the same park from different perspective. This also quite an elaborate example with a building and a curved outer region.

We require to provide another parameter – angle. In addition we require to supply variance of the values.

Grid should also be able to work without the paths in between. For that we can specify empty braces.

An example park will work as follows:

• Region -> Grid (3 {[7,15]a[-15,15]}, 2) { NonWalkableRegion }
• NonWalkableRegion -> Grid (2 {a[-5,5]}, {[1.5,4]a[-25,25]}) { PlantedRegion } {}
• PlantedRegion -> Choose { GrassRegion, BushRegion, Plant1Region, Plant2Region /*, … */ }

In the second grid the size is omitted. Which is fine because the size parameters are given in curly braces – let the grammar decide how many regions it should split the park into. Empty second struct means no paths in between.