Procedural Buildings PART III: R0.2

R0.2 Design (draft)

The second release will perform shape or mesh manipulation, and will result in having complex shapes from primitive shapes. You may see at the next and at the end of this post, the current design and implementation results.

I start with the initial concept of generating random primitive 2D shapes, merging them into one that follows the outside perimeter of all, and then extruding vertically in the y axis as in R0.1. The following 2 figures represent these simple steps.
step1: generate simple primitive 2D shapes on the floor level, here 3 shapes overlapping one another

step2: extrude edges vertically into walls (again the outline here is offset down the y axis for visibility purposes)
Generating primitive shapes and placing them on a plane can be done in a lot of different ways. I will describe a really simple randomisation algorithm and you can play with the current implementation prototype below:

Unity Web Player | Final Results for release R02

First, I will define a vocabulary of primitive shapes, that is a mapping from a character to a shape, as follows:
  • "R": Rectangle
  • "T": Triangle
  • "C": Circle
Let S be the set of the shapes.

I will add to this soup some operations as well, part of the Operations set O:
  • "t": Translate
  • "r": Rotate
  • "s": Scale
  • "w": Skew
  • "c": Create new
  • "d": Delete

Operations are parametric, meaning that they require some parameter in order to be valid. For 2D transformations as is the case with this step, we will need the following parameters for each one:
  • For translation: One 2d vector to define the distance between the initial and final position
  • For rotation: One float, the (Euler) angle of the rotation between initial and final rotation
  • For scaling: One float, to represent the scaling factor between initial and final scale
  • For skewness: One 2D vector to represent the skewing distance between initial and final transformation
  • For shape creation: One 2D vector for position
So, now we need to mathematically represent the command: move the 24th rectangle ( and not the other ones in the scene) by 2 in the X axis and 4 in the Z axis. Let the notation of applying the translation operator on the shape R24 (remember, this is for the rectangle) by a 2D vector of (2,4) be like:
t{R24}(2.0,4.0) Similarly the notation s{C12}(3.5) means that the 12th circle should be scaled up by 3.5 times.
A string T will be appended at each iteration with the transformation(s) that were selected to be applied.

Initially, we start with the creation of a random shape. Its rotation will be 0 degrees and its scale will be 1 in all axis, just like creating a new 3D primitive shape in a Unity scene.
T(t) = T(t-1) + "c{R1}(0, 0)"
+ here stands for string concatenation.
Each time a shape is created, it is added to the pool of shapes, let this set be H. H collects instances of shapes and not types of shapes, so it is not to be confused with S. Initially H would be empty.

Then at each iteration we may randomly pick up an operation from O and apply it to a random shape in H (or in S if we are creating a new shape), like the following pseudocode presents for iteration k:

operation =  Random(operation from O)

if (operation == "c") then
  shape = Random(shape from S)
else
  shape = Random(shape from H)

if (operation == "t" OR operation == "w") then
  S(k) = operation{shape}(Random(float), Random(float))
else if (operation == "r" OR operation =="s") then
  S(k) = operation{shape}(Random(float))


Randomness is a good thing, but in order to achieve manageable results, one has to bound randomisation of continuous variables such as the 2D and 1D float parameters. I will try to implement such a bounded randomisation so that:
  • translation vector magnitude does not surpass 30% of the shape's perimeter
  • rotation angle should stay in the [-30, +30] degrees range
  • scaling vector is within the [0.7, 1.3] range for each axis X and Z
 Now the question remains: When to end iterations so that we may go on with the merging of the shapes and the extrusion of the walls? I will test in practice some numbers for different iteration thresholds, but I think a number between 5 and 9 would be ok.

The implementation of R0.2 will follow the Factory pattern method for the creation of different shapes, building on top of the design of release R0.1. This is a popular software pattern for constructing different kinds of objects. ShapeFactory is an abstract class that is inherited by a set of other classes that help with the instantiation of objects of different shapes. I am hereafter including a UML class diagram depicting the dependencies of the main classes:
Note: The diagram is made with WhiteStarUML, an open source CASE tool for software design with the UML graphical modelling language.


You may have observed that new classes inherit from ShapeFactory in comparison to the class diagram of R0.1, being able to construct new primitive shape types, namely  TriangularShapeFactory and CircularShapeFactory. Same is true for commands as well, and the new classes ShapeTranslate, ShapeRotate, ShapeScale inherit from the abstract ShapeCommand, and are in a generalisation relationship with it.

Merging however several 2D shapes into one common outline is not so simple task as you might think. The operation is called Boolean Addition (of 2 or more solids) in many 3D modelling tools, and now that I am writing these lines, I am having second thoughts about this. I may go for extruding each shape separately, we will see.

More on this soon...

R0.2 Enough said, where is the code, dude?

 I will release the scripting code progressively, so that I will be able to properly comment on it and explain things.

Public and Private Variables

In view of the simple initialisation of R0.1, I have introduced here some public variables that control the generation of shapes. These are explained below:
  • useTriangles: enables (if true) or disables (if false) the generation of triangle primitives
  • useRectangles: enables (if true) or disables (if false) the generation of rectangle primitives
  • useCircles: enables (if true) or disables (if false) the generation of triangle primitives
  • useTranslation: enables (if true) or disables (if false) the translation of existing 2D shapes in the scene
  • useRotation: enables (if true) or disables (if false) the rotation of existing 2D shapes in the scene
  • useScaling: enables (if true) or disables (if false) the scaling (re-sizing) of existing 2D shapes in the scene
  • useSkewing: enables (if true) or disables (if false) the skewing of existing 2D shapes in the scene. This option is ignored since I have not implemented skewing yet
  • maximumIterations: the number of iterations where the shape generation algorithm will be running. After this threshold the algorithm terminates.
The private variables declared are of use explicitly for this script only, and are not exposed to the user. These include:
  • currentIteration: holds the current number of iterations, used to compare with maximumIterations in order to know when to stop the shape generation algorithm
  • triangularFactory, rectangularFactory, circularFactory:  instances of the respective shape factories, one per class. These instances will be used throughout the script to instantiate (spawn) the different shapes on the XZ plane in the scene.
  • acceptableShapes: an array of shapes that the randomisation algorithm will choose from. It actually implements a user-based shape filter and is based on the user input of the public variables useTriangles, useRactangles, useCircles
  • acceptableCommands: an array of commands that the randomisation algorithm will choose from to apply on existing shapes. It implements a user-based filter and is based on the user input of the public variables useTranslation, useRotation, useScaling.
/*
 * Project Name: Procedural Buildings
 * Scene Name: MainScene
 * Version: R0.3
 * Date: May 2013
 * Script Author: Elias Kalapanidas
 * 
 * Objective: Procedural Generation of as-much-as-possible realistic buildings, to be used in a procedurally generated city (a destractibe urban environment)
 */ 

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class buildingBaseLayoutGeneration : MonoBehaviour {
 public bool useTriangles = true;
 public bool useRectangles = true;
 public bool useCircles = true;
 public bool useTranslation = true;
 public bool useRotation = true;
 public bool useScaling = true;
 public bool useSkewing = false;
 public int maximumIterations = 6;
 
 private int currentIteration = 0;
 private TriangularShapeFactory triangleFactory = new TriangularShapeFactory();
 private RectangularShapeFactory rectangularFactory = new RectangularShapeFactory();
 private CircularShapeFactory circularFactory = new CircularShapeFactory();
 
 // acceptableShapes is the subset of shape primitives that the user has accepted to be included in generative modeling of 2D base layout shape, out of the available ones.
 private bool [] acceptableShapes;
 // acceptableCommands are the subset of operators/commands that the user has accepted to be applied on the set of acceptableShapes from the available ones
 private bool [] acceptableCommands;

Initialisation

 // Use this for initialization
 void Start () {
  acceptableShapes = new bool [3];
  acceptableShapes[(int)ShapeEnum.Triangle] = useTriangles;
  acceptableShapes[(int)ShapeEnum.Rectangle] = useRectangles;
  acceptableShapes[(int)ShapeEnum.Circle] = useCircles;
  // We cannot have all shape types de-activated. If this is the case, then automatically activate Rectangles and Log for the user to know
  if (!useTriangles && !useRectangles && !useCircles) {
   useRectangles = true;
   Debug.LogWarning("You have configured the Building Generator script to generate no shape types at all. Your choice is overriden with Rectangles activated.");
  }
  
  acceptableCommands = new bool [6];
  acceptableCommands[(int)CommandEnum.create] = true;
  acceptableCommands[(int)CommandEnum.translate] = useTranslation;
  acceptableCommands[(int)CommandEnum.rotate] = useRotation;
  acceptableCommands[(int)CommandEnum.scale] = useScaling;
  acceptableCommands[(int)CommandEnum.skew] = false; // ToDo: support skew in later versions/updates
  acceptableCommands[(int)CommandEnum.delete] = false; // ToDo: support shape deletion in later versions/updates
  
  //TriangularShape triangle = new TriangularShape();
  //CircularShape circle = new CircularShape(32);
 }

On update

I have inserted the code for each iteration in the Update method of the buildingBaseLayoutGeneration_R02 class. This means that each iteration, during which a new shape is created or an existing shape is transformed, will occur when a frame is refreshed.

About enum types in C#

A note on how random shapes and commands (operations on shapes) are selected: Shapes and command types are represented by 2 different enumerations: ShapeEnum and CommandEnum respectively.
Enumerators in an enum type are also assigned to integer variables, either explicitly by the user or implicitly by the order that they are defined. By default the first enumerator is assigned to 0, this is why I did not make that explicit. For example the enumeration enum ShapeEnum {Triangle, Rectangle, Circle} defaults to enum ShapeEnum {Triangle = 0, Rectangle = 1, Circle = 2};
Now if I declare 
     enum randomShape = ShapeEnum.Rectangle;
that would also mean that randomShape has also been assigned to 1. If I properly cast the variable such as (int)randomShape and print it in the Output, I will get 1. More interestingly so, the inverse also applies: If I declare:
     int randomShape = 1;
then I can cast it as (ShapeEnum)randomShape, print it, and get the string "Rectangle". This proves that effectively the integer value has been assigned the correct enumerator, and then was converted to string in order to printed.
The enum type in CSharp is a strange beast: While it should be, it is not IEnumerable. You cannot search through the enumerators with a foreach (ShapeEnum aShape in ... In .Net usually you can write Enum.GetValues(Typeof(ShapesEnum)), and this would return an array of all the enumerators. However this did not work for me. Perhaps it is a limitation of the Mono implementation of .Net that is used in Unity.

Anyway, randomShape and randomCommand are 2 variables that get a random integer value between the integer value of the first and last enumerator. I use them to get a random integer value within the range of the enumerators. If this value corresponds however to a shape or command that the user has deactivated (in the Inpector window), I am cycling through all enumerators until I find one that is active and valid (this is happening in lines 78-84 for commands and in lines 88-93 for shapes). After getting valid random values, then I convert them through casting to the enum type (in lines 102, 105, 108, 116).
 // Update is called once per frame
 void Update () {
  //Randomiser of acceptableCommands and acceptableShapes
  
  // First check if the maximumIteration number is met. If yes, stop the further shape generation
  if (currentIteration < maximumIterations) {
   // if this is the first iteration and there are no shapes generated yet, then
   // let the first command be "create"
   int randomCommand = 0;
   if (currentIteration == 0)
    randomCommand = (int)CommandEnum.create;
   else
    // else choose a random command
    randomCommand = Random.Range(0, acceptableCommands.Length);
   if (randomCommand >= acceptableCommands.Length) {
    Debug.LogError("random value selected for the command exceeds the number of available commands");
    randomCommand = 0;
   }
   // check if it is accepted, otherwise move on to the next in the list of acceptableCommands
   while (!acceptableCommands[randomCommand]) {
    // 6 below is the length of the CommandEnum enumeration variable
    if (randomCommand < acceptableCommands.Length -1) // for some mysterious reason Enum.GetNames().Length is not accepted by mono compiler
     randomCommand++;
    else
     randomCommand = 0; //cycle back to the beginning of the enum structure
   }
   // choose a random shape type
   int randomShape = Random.Range(0, acceptableShapes.Length);
   // check if it is accepted, otherwise move to the next in the list
   while (!acceptableShapes[randomShape]) {
    if (randomShape < acceptableShapes.Length -1) // Enum.GetNames().Length
     randomShape++;
    else
     randomShape = 0;
   }
   if (randomShape >= acceptableShapes.Length) {
    Debug.LogError("random value selected for the shape exceeds the number of available shapes");
    randomCommand = 0;
   }
 
   // declare a general ShapeFactory variable that will point to a given factory later on
   ShapeFactory abstractedFactory = null;
   // 
   if ((ShapeEnum)randomShape == ShapeEnum.Triangle) {
    abstractedFactory = triangleFactory;
   }
   if ((ShapeEnum)randomShape == ShapeEnum.Rectangle) {
    abstractedFactory = rectangularFactory;
   }
   if ((ShapeEnum)randomShape == ShapeEnum.Circle) {
    abstractedFactory = circularFactory;
   }
   
   // execute randomCommand, but first find out which one in the enum the command is
   if ((CommandEnum)randomCommand == CommandEnum.create) {
    // and now, create a new shape of the selected randomShape type
    ShapeCreate create = new ShapeCreate();
    create.setShapeType( (ShapeEnum)randomShape );
    create.setShapeFactory(abstractedFactory);
    create.execute();
   }
   else
   {
    // choose a random shape instance from existing ones of type randomShape
    int randomShapeInstance = Random.Range(0, abstractedFactory.getShapesCount() -1);
    // perform the operations below only if the selected factory includes at least one shape
    if ((CommandEnum)randomCommand == CommandEnum.translate && abstractedFactory.getShapesCount()>0) {
     ShapeTranslate translate = new ShapeTranslate();
     translate.setShapeToTransform (abstractedFactory.getShape (randomShapeInstance));
     translate.execute ();
    }
    if ((CommandEnum)randomCommand == CommandEnum.rotate && abstractedFactory.getShapesCount()>0) {
     ShapeRotate rotate = new ShapeRotate();
     rotate.setShapeToTransform(abstractedFactory.getShape (randomShapeInstance));
     rotate.execute();
    }
    if ((CommandEnum)randomCommand == CommandEnum.scale && abstractedFactory.getShapesCount()>0) {
     ShapeScale scale = new ShapeScale();
     scale.setShapeToTransform (abstractedFactory.getShape (randomShapeInstance));
     scale.execute();
    }
    
   }
   currentIteration++;
  }
 } // Update() ends here
 
}; // buildingBaseLayoutGeneration class ends here

Some randomisation results 

After making small amendments to the code above (e.g. adding a transparent material to the created shapes, automatically generating screen capture files and saving them in a folder), I have been able to get some results of different randomisation configurations. The image below displays a tile set of screen captures, each being the output of the algorithm set to run for 6 iterations, all shapes are on, the basic commands creation, translation, rotation and scaling are on as well.
results for 6 iterations, all 3 shapes, TRS transformations
First conclusions: 
  • The shapes are largely overlapping one another
  • Disproportional scaling seems nice (seen for example in R02_23)
  • The limitations that I have set for the transformation commands (e.g. to scale only upwards, by a rate between 0% and 100%) is restricting the visual variation of possible transformations
First corrective measures:
  • Apply all transformations at once on a given shape: first decide whether or not to apply a transformation (50% chance to apply), then proceed with it, otherwise proceed to the next one. This alteration will probably produce more interesting visual results, will reduce the concentration of shapes.
  • Add a mirror command, to mirror a given shape across any random 2D direction.
  • Loose the transformation boundaries 
A first result with extrusion on follows:
triple extrusion on a circle primitive
The image shows an unexpected artefact: when an extrusion is applied on a shape that has just been extruded, it creates another level. This is undesired, and I have to eliminate it. All extrusions are supposed to create just one level. More levels will be generated by the application of a procedural generation algorithm that will operate on whole levels (and will disposition them, rotate them, scale them etc.).
Another observation I have is that something fishy is going on with the normal vectors. I will need to take a closer look.

After some time working with the script, I made some changes:
  • The shape creation command also translates the shape, and dispositions it a bit away, to a random direction
  • No extrusion is occuring while the randomisation algorithm is running. After the last iteration, all shapes are extruded along the +Y axis
  • The boundaries of the 3 possible transformations are loosened a bit.
  • The user defines a probability of occurance for each shape type and command, instead of a boolean activation/deactivation. This is used in the new randomisation mechanism (see below)
  • A new randomisation mechanism is introduced, which is based on "Probability proportional to Size Sampling". I will explain this later on.
After extruding the randomisation results are more sensible. Some possible shape configurations are displayed in the following image.
I am still not satisfied with the results, but at least they are an improvement over the previous ones. A closer look to one of these follows:
On the top-left corner, you may see a GUI button that resets the algorithm, destroys all existing shapes and runs the algorithm again for a new set of iterations. The camera view is perspective looking down the Y axis.

Probability-proportional-to-size-based sampling

This is my implementation of a statistical sampling process that is used in this project as a randomisation mechanism. I did not want to have a truly random process from a normal distribution. I would like to give the user the ability to assign to the shape types different probabilities of selection, the sum of which would equal 1. Similarly, the user would set the probabilities of selection for the different commands as well.
Let me show this with the example of the shape selection:
There are three shape types in the ShapeEnum enumeration. Say that the probabilities of selection are as follows:
     P(Triangle) = 0.3
     P(Rectangle) = 0.5
     P(Circle) = 0.2

The sum of all probabilities is 1. Each shape contributes to the sum with its probability, and if we draw stacked the probabilities from 0 to 1, we can identify "zones" each corresponding to a different shape type:
I select a random float number in the range [0, 1]. This is what Random.Range(0, 1f) is doing. Say again that this random float equals 0.57. Now I would like to know the integer index that corresponds to the index of the selected zone. In the example above, this is 1 (remember that this is a 0-based index). This index is associated with the ShapeEnum enumeration, and it is assigned to the 2nd enumerator (Rectangle). The algorithm continues normally from that point on, after having selected the shape to be created or transformed by the commands.

 // Define Probability proportional to Size Sampling class
 public class PPSSampling {
  private ArrayList _probabilities;
  
  public void setProbability(float prob) {
   if (_probabilities == null)
    _probabilities = new ArrayList();
   _probabilities.Add(prob);
  }
  public int getRandomInt() {
   float greatSum = 0;
   for (int i=0; i<_probabilities data-blogger-escaped-.count="" data-blogger-escaped-float="" data-blogger-escaped-for="" data-blogger-escaped-greatsum="" data-blogger-escaped-i="" data-blogger-escaped-if="" data-blogger-escaped-int="" data-blogger-escaped-probabilities.count="" data-blogger-escaped-probabilities="" data-blogger-escaped-randomfloat="" data-blogger-escaped-randomprobzone="-1;" data-blogger-escaped-sumsofar="0;">= sumSoFar && randomFloat < (sumSoFar + (float)_probabilities[i]))
     randomProbZone = i;
    sumSoFar += (float)_probabilities[i];
   }
   return randomProbZone;
  }
 }

Next Idea to develop:

While I was playing out in the sun with my son, I got hit by another idea that has even more potential in generating interesting outlines: Why generating different shapes and then try to unite them in one with a boolean addition, and not try to apply the operations at the vertex level of one main shape? The idea is based on one of the foundational and simpler randomisation techniques: midpoint displacement. This technique works by introducing a new vertex in between two adjacent (neighbouring) vertices, and then by displacing it a bit to a random direction and by a random distance.

By extending this idea, I could generate a simple rectangle, and then apply the following operations in a random fashion:
  1. Vertex displacement: translate a vertex
  2. Edge/ Nearest neighbours displacement: translate 2 or more neighbouring vertices
  3. Midpoint generation: generate a new vertex in the middle of 2 neighbouring vertices
  4. Primitive generation: select one edge (2 neighbouring vertices) and introduce a set of vertices that form a primitive shape. Possible subclasses:
    1. rectangle (2 vertices equally displaced)
    2. circle (a half-circle having its centre on the middle of the edge)
    3. triangle (3 vertices, 2 of which lie on the edge)
  5. select a subset of the vertices, mirror them across a random plane, and delete the remaining ones

Yet another change in plans: From vertex to edge-based manipulation

Well, before the ink of my vertex-based manipulation ideas dries, I am indulging into another angle to this problem:
Instead of going to the vertex level, stay at the edge level: manipulate edges in 2 dimensions. The following concepts depict this idea, which I have already started implementing it. I am very optimistic if not confident that the results will be much better than before.
  • The first figure depicts the result of extruding an edge, the extruded rectangle is stored as a submesh;
  • The second figure is both extrusion and scaling of an edge, again the extruded trapezoid is stored as a submesh;
  • The third figure is extrusion and midpoint merging of the extruded vertices, the extruded triangle is stored as a submesh.
The tough task here is to find a 'good' candidate edge to extrude, not to result in extruding into the 'interior' of the initial shape, nor having overlapping areas after the extrusion occurs. Once again I relied on using MeshExtrusion script from the example asset that Unity has freely shared in the asset store and which is focused on procedural generation demonstration.
Here is a nice result after 5 iterations (the first created the main shape, the 4 successive ones extruded a randomly selected outer edge).

Finally, after another implementation iteration (another sprint), the following results have come out, which I believe are more satisfying:
Randomisation with edge selection and extrusion (ShapeExtrudeRectangle class and operation), after 6 iterations
Some slight overlapping is still there, and I should check more thoroughly that the selected edge to be extruded is not to lie into another existing triangle.

After a simple check for overlaps with other existing triangles, and after implementing extrusion and midpoint merging, extrusion and scaling, I got the following results:

All horizontal extrusion operations applied randomly, after 6 iterations
I think that this is the final touch in R03 release. The code for the class that implements the functionality that I described above follows.

 public class ShapeExtrudeHorizontal : ShapeCommand {
  public enum ExtrusionType {rectangle, triangle, trapezoid};
  protected GameObject _shape;
  protected Vector3 _fromVertex, _toVertex;
  protected float _extrusionDistance;
  protected ExtrusionType _extrusionType;
  protected float _extrusionOffset;
  
  public ShapeExtrudeHorizontal () {
   _class = CommandEnum.extrudeHorizontal;
   _fromVertex = new Vector3(0,0,0);
   _toVertex = new Vector3(0,0,0);
   _extrusionDistance = 0f;
   _extrusionType = ExtrusionType.rectangle;
   _extrusionOffset = 0f;
  }
  
  public void setExtrusionDistance(float distance) {
   if (distance > 0)
    _extrusionDistance = distance;
  }
  public float getExtrusionDistance() { return _extrusionDistance; }
  
  public void setShapeToTransform (GameObject aShape) { _shape = aShape; }
  public GameObject getShapeToTransform () { return _shape; }
  
  public void setExtrusionType( ExtrusionType aType ) { _extrusionType = aType; }
  public ExtrusionType getExtrusionType() { return _extrusionType; }
  
  public void setShapeEdgeToExtrude (Vector3 fromPoint, Vector3 toPoint, float distance) {
   if (fromPoint.y == toPoint.y) {
    _fromVertex = fromPoint;
    _toVertex = toPoint;
   }
   if (distance > 0)
    _extrusionDistance = distance;
  }
  
  // Helper functions
  protected bool isOnSameSide(Vector3 p1, Vector3 p2, Vector3 a, Vector3 b) {
      Vector3 cp1 = Vector3.Cross(b-a, p1-a);
      Vector3 cp2 = Vector3.Cross(b-a, p2-a);
      if ( Vector3.Dot(cp1, cp2) >= 0 ) 
    return true;
      else 
    return false;
  }
 
  protected bool isInsideTriangle(Vector3 p, Vector3 a, Vector3 b, Vector3 c) {
      if ( isOnSameSide(p, a, b, c) && isOnSameSide(p, b, a, c) && isOnSameSide(p, c, a, b) )
    return true;
      else 
    return false;
  }

  /// <summary>
  /// Selects a random edge, and assigns values for the protected attributes _fromVertex and _toVertex.
  /// </summary>
  public bool selectRandomEdge() {
   // browse through the existing submeshes
   // and find 2 neighbouring vertices (present in the same triangle definition) that are not shared with other submeshes/ triangles
   if (_shape == null) {
    Debug.LogError("ShapeExtrudeHorizontalHorizontal.execute: The shape to act upon by ShapeTranslate.execute() is not set. Make sure that the setShapeToTransform method is called before this one.");
    return false;
   }
   Mesh myMesh = _shape.GetComponent<MeshFilter>().mesh;
   if (myMesh == null) {
    Debug.LogError ("ShapeExtrudeHorizontalHorizontal:execute: The shape to act upon has no valid MeshFilter.");
    return false;
   }
   
   // use MeshExtrusion script's BuildManifoldEdges method to store all outter edges in an array
   // Iterate for all submeshes, since each submesh is a manifold shape, while the mesh is not necessarily
   
   List <MeshExtrusion.Edge> outterEdges = new List <MeshExtrusion.Edge>();  
   MeshExtrusion.Edge [] edges= MeshExtrusion.BuildManifoldEdges(myMesh);
   outterEdges.AddRange (edges);
   // Remove completely edges that their 2 points are shared (those that have duplicates/ triples / ...)
   List <int> duplicateEdges = new List<int>(0);
   for (int i=0; i<outterEdges.Count; i++) {
    bool deleteme = false;
    for (int j=i+1; j<outterEdges.Count; j++) {
     if (
     ( myMesh.vertices[outterEdges[j].vertexIndex[0]] == myMesh.vertices[outterEdges[i].vertexIndex[0]] &&
     myMesh.vertices[outterEdges[j].vertexIndex[1]] == myMesh.vertices[outterEdges[i].vertexIndex[1]] ) ||
     ( myMesh.vertices[outterEdges[j].vertexIndex[0]] == myMesh.vertices[outterEdges[i].vertexIndex[1]] &&
     myMesh.vertices[outterEdges[j].vertexIndex[1]] == myMesh.vertices[outterEdges[i].vertexIndex[0]] ) ) {
      duplicateEdges.Add(j);
      deleteme = true;
     }
    }
    if (deleteme)
     duplicateEdges.Add (i);
   }
   // sort duplicate Edges descending order
   duplicateEdges.Sort ();
   for (int i=duplicateEdges.Count-1; i>=0 ; i--)
    if ( duplicateEdges[i] < outterEdges.Count )
     outterEdges.RemoveAt( duplicateEdges[i] );
      
      
   if (outterEdges.Count == 0)
    return false;
   // Randomly select an edge from the list
   int selectedEdgeIndex = Random.Range(0, outterEdges.Count);
   
   // Validate that the extruded vertice(s) will not lie into an existing triangle, otherwise select another edge
   bool extrusionOverlapsShape = true;
   while (extrusionOverlapsShape) {
    extrusionOverlapsShape = false;
    // Find the triangle they belong to, and check their order of appearance
    // which will determine the normal vector of the edge to be extruded
    // Note: we would like the edge to be extruded outwards, not inwards
    int triangleIndex = outterEdges[selectedEdgeIndex].faceIndex[0] * 3;
    if ( myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[0] ] == myMesh.vertices[myMesh.triangles[triangleIndex]] ) {
     if ( myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[1] ] == myMesh.vertices[myMesh.triangles[triangleIndex + 1]] ) {
      _fromVertex = myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[0] ];
      _toVertex = myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[1] ];
     }
     else {
      _fromVertex = myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[1] ];
      _toVertex = myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[0] ];
     }
    }
    else if ( myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[0] ] == myMesh.vertices[myMesh.triangles[triangleIndex + 1]] ) {
     if ( myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[1] ] == myMesh.vertices[myMesh.triangles[triangleIndex + 2]] ) {
      _fromVertex = myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[0] ];
      _toVertex = myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[1] ];
     }
     else {
      _fromVertex = myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[1] ];
      _toVertex = myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[0] ];
     }
    }
    else if ( myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[0] ] == myMesh.vertices[myMesh.triangles[triangleIndex + 2]] ) {
     if ( myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[1] ] == myMesh.vertices[myMesh.triangles[triangleIndex]] ) {
      _fromVertex = myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[0] ];
      _toVertex = myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[1] ];
     }
     else {
      _fromVertex = myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[1] ];
      _toVertex = myMesh.vertices[ outterEdges[selectedEdgeIndex].vertexIndex[0] ];
     }
    }
    if (getExtrusionType() == ExtrusionType.trapezoid) {
     // Validate random offset distance
     float _extrusionOffset = Random.Range(-0.5f, 0.5f);
     while ( Mathf.Abs(_extrusionOffset) > Vector3.Distance(_fromVertex, _toVertex)/2 )
      _extrusionOffset = Random.Range(-0.5f, 0.5f);
    }
    
    Vector3 extrudedFromPoint = Vector3.zero, extrudedToPoint = Vector3.zero;
    // Find the plane passing by _fromVertex and _toVertex
    Plane edgePlane = new Plane( _fromVertex, _toVertex, _fromVertex + Vector3.up );
    
    switch (getExtrusionType ()) {
    case ExtrusionType.triangle :
     extrudedFromPoint = (_fromVertex + _toVertex) /2 + edgePlane.normal*_extrusionDistance;
     extrudedToPoint = extrudedFromPoint;
     break;
    case ExtrusionType.rectangle :
     extrudedFromPoint = _fromVertex + edgePlane.normal*_extrusionDistance;
     extrudedToPoint = _toVertex + edgePlane.normal*_extrusionDistance;
     break;
    case ExtrusionType.trapezoid :
     extrudedFromPoint = _fromVertex + edgePlane.normal*_extrusionDistance + Quaternion.AngleAxis(-90, Vector3.up)*edgePlane.normal*_extrusionOffset;
     extrudedToPoint = _toVertex + edgePlane.normal*_extrusionDistance + Quaternion.AngleAxis(90, Vector3.up)*edgePlane.normal*_extrusionOffset;
     break;
    }
     
    // The core validation starts here: Browse through all triangles
    for (int i=0; i<myMesh.triangles.Length; i+=3) {
     // Do not check the triangle that includes the selected Edge
      // Check that neither extrudedFromPoint nor extrudedToPoint fall in an existing triangle
      if ( isInsideTriangle( extrudedFromPoint, myMesh.vertices[myMesh.triangles[i]], myMesh.vertices[myMesh.triangles[i+1]], myMesh.vertices[myMesh.triangles[i+2]]) )
       extrusionOverlapsShape = true;
      if ( getExtrusionType() != ExtrusionType.triangle )
       if ( isInsideTriangle( extrudedToPoint, myMesh.vertices[myMesh.triangles[i]], myMesh.vertices[myMesh.triangles[i+1]], myMesh.vertices[myMesh.triangles[i+2]]) )
        extrusionOverlapsShape = true;
    }
    for (int i=0; i<myMesh.vertexCount; i++) {
     if (i != (outterEdges[selectedEdgeIndex].faceIndex[0]*3)) {
      // Check that no existing vertex falls in the (future) triangles formed by extrudedFromPoint, extrudedToPoint and _fromVertex, _toVertex
      // but only for vertices different from _fromVertex and _toVertex
      if ( myMesh.vertices[i] != _fromVertex && myMesh.vertices[i] != _toVertex ) {
       if ( isInsideTriangle( myMesh.vertices[i], _fromVertex, extrudedFromPoint, _toVertex ) )
        extrusionOverlapsShape = true;
       if ( getExtrusionType() != ExtrusionType.triangle )
        if ( isInsideTriangle( myMesh.vertices[i], _toVertex, extrudedFromPoint, extrudedToPoint ) )
         extrusionOverlapsShape = true;
      }
     }
    }
   
    
    // Select another edge, if the previous one causes overlaps
    if (extrusionOverlapsShape)
     selectedEdgeIndex = Random.Range(0, outterEdges.Count);
   }

   return true;
  }
  
  override public GameObject execute() {
   if (_shape == null) {
    Debug.LogError("ShapeExtrudeHorizontalHorizontal.execute: The shape to act upon by ShapeTranslate.execute() is not set. Make sure that the setShapeToTransform method is called before this one.");
    return null;
   }
   if (_fromVertex == _toVertex ) {
    Debug.LogError ("ShapeExtrudeHorizontalHorizontal:execute: The 2 points that form the edge to be extruded are not correctly set, or are equal. Make sure that the setShapeEdgeToExtrude method is called before this one.");
    return null;
   }
   Mesh myMesh = _shape.GetComponent<MeshFilter>().mesh;
   if (myMesh == null) {
    Debug.LogError ("ShapeExtrudeHorizontalHorizontal:execute: The shape to act upon has no valid MeshFilter.");
    return null;
   }
   // Validation: Find an edge that has two of its three vertices equal to _fromPoint and _toPoint
   
   // Find the plane passing by _fromVertex and _toVertex
   Plane edgePlane = new Plane( _fromVertex, _toVertex, _fromVertex + Vector3.up );
   
   Vector3 [] newVertices = new Vector3 [myMesh.vertexCount + (getExtrusionType() == ExtrusionType.triangle?3:4)]; 
   Vector3 [] newNormals = new Vector3 [myMesh.vertexCount + (getExtrusionType() == ExtrusionType.triangle?3:4)];
   int [] newTriangles = new int [getExtrusionType() == ExtrusionType.triangle?3:6];
   for (int i=0; i<myMesh.vertexCount; i++) {
    newVertices[i] = myMesh.vertices[i];
    newNormals[i] = myMesh.normals[i];
   }
   newVertices[myMesh.vertexCount] = new Vector3(_fromVertex.x, _fromVertex.y, _fromVertex.z);
   if (getExtrusionType() == ExtrusionType.triangle) {
    newVertices[myMesh.vertexCount +1] = (_fromVertex + _toVertex) /2 + edgePlane.normal*_extrusionDistance;
    newVertices[myMesh.vertexCount +2] = new Vector3(_toVertex.x, _toVertex.y, _toVertex.z);
    
    newNormals[myMesh.vertexCount] = Vector3.up;
    newNormals[myMesh.vertexCount +1] = Vector3.up;
    newNormals[myMesh.vertexCount +2] = Vector3.up;
   
    newTriangles[0] = myMesh.vertexCount;
    newTriangles[1] = myMesh.vertexCount +1;
    newTriangles[2] = myMesh.vertexCount +2;
   }
   else {
    if (getExtrusionType() == ExtrusionType.trapezoid) {
     newVertices[myMesh.vertexCount +1] = _fromVertex + edgePlane.normal*_extrusionDistance + Quaternion.AngleAxis(-90, Vector3.up)*edgePlane.normal*_extrusionOffset;
     newVertices[myMesh.vertexCount +2] = _toVertex + edgePlane.normal*_extrusionDistance + Quaternion.AngleAxis(90, Vector3.up)*edgePlane.normal*_extrusionOffset;
    } else {
     newVertices[myMesh.vertexCount +1] = _fromVertex + edgePlane.normal*_extrusionDistance;
     newVertices[myMesh.vertexCount +2] = _toVertex + edgePlane.normal*_extrusionDistance;
    }
    newVertices[myMesh.vertexCount +3] = new Vector3(_toVertex.x, _toVertex.y, _toVertex.z);
    newNormals[myMesh.vertexCount] = Vector3.up;
    newNormals[myMesh.vertexCount +1] = Vector3.up;
    newNormals[myMesh.vertexCount +2] = Vector3.up;
    newNormals[myMesh.vertexCount +3] = Vector3.up;
   
    newTriangles[0] = myMesh.vertexCount;
    newTriangles[1] = myMesh.vertexCount +1;
    newTriangles[2] = myMesh.vertexCount +3;
    newTriangles[3] = myMesh.vertexCount +3; 
    newTriangles[4] = myMesh.vertexCount +1;
    newTriangles[5] = myMesh.vertexCount +2;
   }   
      myMesh.vertices = newVertices;
      myMesh.normals = newNormals;
   // Make a new submesh
   myMesh.subMeshCount += 1;
   myMesh.SetTriangles(newTriangles, myMesh.subMeshCount -1);
      //myMesh.uv = new Vector2[] {new Vector2(0,1), new Vector2(0,0), new Vector2(1,0)};
      //myMesh.colors = new Color[] {Color.white,Color.white,Color.white};
   myMesh.Optimize();
   myMesh.RecalculateBounds();
   //myMesh.RecalculateNormals();
   return _shape;
  }
 };
The experimentation goes on, stay tuned. If you have any good idea, please drop a comment below.

Comments

Post a Comment