// Unity C# reference source

// Copyright (c) Unity Technologies. For terms of use, see

// https://unity3d.com/legal/licenses/Unity_Reference_Only_License

using System.Collections.Generic;

using UnityEngine;

using UnityEngine.Profiling;

using UnityEditor;

using System.IO;

namespace TreeEditor

{

public class TreeData : ScriptableObject

{

[SerializeField]

private int _uniqueID;

public string materialHash;

public TreeGroupRoot root;

public TreeGroupBranch[] branchGroups;

public TreeGroupLeaf[] leafGroups;

public TreeNode[] nodes;

public Mesh mesh;

public Material optimizedSolidMaterial;

public Material optimizedCutoutMaterial;

public bool isInPreviewMode;

//

// resolve references..

//

public TreeGroup GetGroup(int id)

{

if (id == root.uniqueID)

{

return root;

}

for (int i = 0; i < branchGroups.Length; i++)

{

if (branchGroups[i].uniqueID == id)

{

return branchGroups[i];

}

}

for (int i = 0; i < leafGroups.Length; i++)

{

if (leafGroups[i].uniqueID == id)

{

return leafGroups[i];

}

}

return null;

}

public TreeNode GetNode(int id)

{

for (int i = 0; i < nodes.Length; i++)

{

if (nodes[i].uniqueID == id)

{

return nodes[i];

}

}

return null;

}

//

// Get at index

//

private int GetNodeCount()

{

return nodes.Length;

}

private TreeNode GetNodeAt(int i)

{

if (i >= 0 && i < nodes.Length)

{

return nodes[i];

}

return null;

}

private int GetGroupCount()

{

return 1 + branchGroups.Length + leafGroups.Length;

}

private TreeGroup GetGroupAt(int i)

{

if (i == 0)

{

return root;

}

i--;

if (i >= 0 && i < branchGroups.Length)

{

return branchGroups[i];

}

i -= branchGroups.Length;

if (i >= 0 && i < leafGroups.Length)

{

return leafGroups[i];

}

return null;

}

//

// Validate references

//

public void ValidateReferences()

{

Profiler.BeginSample("ValidateReferences");

//

// Fill direct references

//

int groupCount = GetGroupCount();

for (int i = 0; i < groupCount; i++)

{

TreeGroup g = GetGroupAt(i);

g.parentGroup = GetGroup(g.parentGroupID);

g.childGroups.Clear();

g.nodes.Clear();

for (int j = 0; j < g.childGroupIDs.Length; j++)

{

TreeGroup child = GetGroup(g.childGroupIDs[j]);

g.childGroups.Add(child);

}

for (int j = 0; j < g.nodeIDs.Length; j++)

{

TreeNode node = GetNode(g.nodeIDs[j]);

g.nodes.Add(node);

}

}

int nodeCount = GetNodeCount();

for (int i = 0; i < nodeCount; i++)

{

TreeNode n = GetNodeAt(i);

n.parent = GetNode(n.parentID);

n.group = GetGroup(n.groupID);

}

Profiler.EndSample(); // ValidateReferences

}

//

// Clear all direct references

//

public void ClearReferences()

{

for (int i = 0; i < branchGroups.Length; i++)

{

branchGroups[i].parentGroup = null;

branchGroups[i].childGroups.Clear();

branchGroups[i].nodes.Clear();

}

for (int i = 0; i < leafGroups.Length; i++)

{

leafGroups[i].parentGroup = null;

leafGroups[i].childGroups.Clear();

leafGroups[i].nodes.Clear();

}

for (int i = 0; i < nodes.Length; i++)

{

nodes[i].parent = null;

nodes[i].group = null;

}

}

//

// Group management

//

public TreeGroup AddGroup(TreeGroup parent, System.Type type)

{

TreeGroup g = null;

if (type == typeof(TreeGroupBranch))

{

g = new TreeGroupBranch();

branchGroups = ArrayAdd(branchGroups, g as TreeGroupBranch);

}

else if (type == typeof(TreeGroupLeaf))

{

g = new TreeGroupLeaf();

leafGroups = ArrayAdd(leafGroups, g as TreeGroupLeaf);

}

else

{

return null;

}

// set unique ID

g.uniqueID = _uniqueID;

_uniqueID++;

// set initial properties

g.parentGroupID = 0;

g.distributionFrequency = 1;

// set parent

SetGroupParent(g, parent);

// validate hierachy // already done in setgroupparent

//ValidateReferences();

return g;

}

// Copies public fields from n to n2, deep copy where needed...

private void CopyFields(object n, object n2)

{

if (n.GetType() != n2.GetType())

{

return;

}

System.Reflection.FieldInfo[] fields = n.GetType().GetFields();

for (int i = 0; i < fields.Length; i++)

{

if (fields[i].IsPublic)

{

if (fields[i].FieldType == typeof(TreeSpline))

{

// Tree Spline

TreeSpline origSpline = fields[i].GetValue(n) as TreeSpline;

fields[i].SetValue(n2, new TreeSpline(origSpline));

}

else if (fields[i].FieldType == typeof(AnimationCurve))

{

// Animation curve

AnimationCurve origCurve = fields[i].GetValue(n) as AnimationCurve;

AnimationCurve newCurve = new AnimationCurve(origCurve.keys);

newCurve.postWrapMode = origCurve.postWrapMode;

newCurve.preWrapMode = origCurve.preWrapMode;

fields[i].SetValue(n2, newCurve);

}

else

{

fields[i].SetValue(n2, fields[i].GetValue(n));

}

}

}

}

public TreeGroup DuplicateGroup(TreeGroup g)

{

TreeGroup g2 = AddGroup(GetGroup(g.parentGroupID), g.GetType());

CopyFields(g, g2);

// Don't do stuff with kids

g2.childGroupIDs = new int[0];

g2.nodeIDs = new int[0];

// Create nodes and clone stuff

for (int i = 0; i < g.nodeIDs.Length; i++)

{

TreeNode n = GetNode(g.nodeIDs[i]);

TreeNode n2 = AddNode(g2, GetNode(n.parentID));

CopyFields(n, n2);

n2.groupID = g2.uniqueID;

}

return g2;

}

public void DeleteGroup(TreeGroup g)

{

// remove nodes

for (int i = g.nodes.Count - 1; i >= 0; i--)

{

DeleteNode(g.nodes[i], false);

}

if (g.GetType() == typeof(TreeGroupBranch))

{

branchGroups = ArrayRemove(branchGroups, g as TreeGroupBranch);

}

else if (g.GetType() == typeof(TreeGroupLeaf))

{

leafGroups = ArrayRemove(leafGroups, g as TreeGroupLeaf);

}

// unlink..

SetGroupParent(g, null);

}

public void SetGroupParent(TreeGroup g, TreeGroup parent)

{

TreeGroup origParent = GetGroup(g.parentGroupID);

if (origParent != null)

{

origParent.childGroupIDs = ArrayRemove(origParent.childGroupIDs, g.uniqueID);

origParent.childGroups.Remove(g);

}

if (parent != null)

{

g.parentGroup = parent;

g.parentGroupID = parent.uniqueID;

parent.childGroups.Add(g);

parent.childGroupIDs = ArrayAdd(parent.childGroupIDs, g.uniqueID);

}

else

{

g.parentGroup = null;

g.parentGroupID = 0;

}

ValidateReferences();

// update frequency!

UpdateFrequency(g.uniqueID);

}

public void LockGroup(TreeGroup g)

{

g.Lock();

}

public void UnlockGroup(TreeGroup g)

{

g.Unlock();

UpdateFrequency(g.uniqueID);

}

public bool IsAncestor(TreeGroup ancestor, TreeGroup g)

{

if (g == null)

{

return false;

}

TreeGroup parent = GetGroup(g.parentGroupID);

while (parent != null)

{

if (parent == ancestor)

{

return true;

}

parent = GetGroup(parent.parentGroupID);

}

return false;

}

//

// Node management

//

public TreeNode AddNode(TreeGroup g, TreeNode parent)

{

return AddNode(g, parent, true);

}

public TreeNode AddNode(TreeGroup g, TreeNode parent, bool validate)

{

if (g == null)

{

return null;

}

TreeNode n = new TreeNode();

n.uniqueID = _uniqueID;

_uniqueID++;

// set node parent

SetNodeParent(n, parent);

// set group (both ID and temporary direct reference)

n.groupID = g.uniqueID;

n.group = g;

// add to group (both ID and temporary direct reference)

g.nodeIDs = ArrayAdd(g.nodeIDs, n.uniqueID);

g.nodes.Add(n);

nodes = ArrayAdd(nodes, n);

// validate references

if (validate)

{

ValidateReferences();

}

return n;

}

public void SetNodeParent(TreeNode n, TreeNode parent)

{

if (parent != null)

{

n.parentID = parent.uniqueID;

n.parent = parent;

}

else

{

n.parentID = 0;

n.parent = null;

}

}

public void DeleteNode(TreeNode n)

{

DeleteNode(n, true);

}

public void DeleteNode(TreeNode n, bool validate)

{

TreeGroup group = GetGroup(n.groupID);

if (group != null)

{

// remove from this group

group.nodeIDs = ArrayRemove(group.nodeIDs, n.uniqueID);

group.nodes.Remove(n);

// remove attached nodes

for (int i = 0; i < group.childGroups.Count; i++)

{

TreeGroup kidGroup = group.childGroups[i];

// go backwards through list to make deletion a little cleaner. (would require stepping j back on deletion otherwise)

for (int j = kidGroup.nodes.Count - 1; j >= 0; j--)

{

if ((kidGroup.nodes[j] != null) && (kidGroup.nodes[j].parentID == n.uniqueID))

{

DeleteNode(kidGroup.nodes[j], false);

}

}

}

}

n.group = null;

n.groupID = 0;

n.parent = null;

n.parentID = 0;

nodes = ArrayRemove(nodes, n);

if (validate)

{

ValidateReferences();

}

}

public TreeNode DuplicateNode(TreeNode n)

{

TreeGroup group = GetGroup(n.groupID);

if (group == null)

{

return null;

}

TreeNode n2 = AddNode(group, GetNode(n.parentID));

CopyFields(n, n2);

return n2;

}

//

// Initializes data..

//

public void Initialize()

{

if (root == null)

{

branchGroups = new TreeGroupBranch[0];

leafGroups = new TreeGroupLeaf[0];

nodes = new TreeNode[0];

// set unique id counter...

_uniqueID = 1;

root = new TreeGroupRoot();

root.uniqueID = _uniqueID;

root.distributionFrequency = 1;

_uniqueID++;

UpdateFrequency(root.uniqueID);

AddGroup(root, typeof(TreeGroupBranch));

}

}

// Update seed

public void UpdateSeed(int id)

{

TreeGroup g = GetGroup(id);

if (g == null)

{

return;

}

var origState = Random.state;

ClearReferences();

ValidateReferences();

g.UpdateSeed();

g.UpdateDistribution(true, true);

ClearReferences();

Random.state = origState;

}

// Update frequency

public void UpdateFrequency(int id)

{

TreeGroup g = GetGroup(id);

if (g == null)

{

return;

}

var origState = Random.state;

ClearReferences();

ValidateReferences();

g.UpdateFrequency(this);

ClearReferences();

Random.state = origState;

}

// Complete update of distribution properties..

public void UpdateDistribution(int id)

{

TreeGroup g = GetGroup(id);

if (g == null)

{

return;

}

var origState = Random.state;

ClearReferences();

ValidateReferences();

g.UpdateDistribution(true, true);

ClearReferences();

Random.state = origState;

}

static public int GetAdaptiveHeightSegments(float h, float adaptiveQuality)

{

return (int)Mathf.Max(h * adaptiveQuality, 2);

}

static public int GetAdaptiveRadialSegments(float r, float adaptiveQuality)

{

int segs = ((int)(r * 24 * adaptiveQuality)) / 2 * 2;

return (int)Mathf.Clamp(segs, 4, 32);

}

static public List<float> GetAdaptiveSamples(TreeGroup group, TreeNode node, float adaptiveQuality)

{

List<float> samplePoints = new List<float>();

if (node.spline == null) return samplePoints;

// starting point for cap smoothing

float capStartPoint = 1.0f - node.capRange;

// set initial sample points

// one at each spline node

SplineNode[] nodes = node.spline.GetNodes();

for (int i = 0; i < nodes.Length; i++)

{

// break..

if (nodes[i].time >= node.breakOffset)

{

samplePoints.Add(node.breakOffset);

break;

}

else if (nodes[i].time > capStartPoint)

{

samplePoints.Add(capStartPoint);

break;

}

else

{

samplePoints.Add(nodes[i].time);

}

}

// make sure they are in the correct order

samplePoints.Sort();

if (samplePoints.Count < 2)

{

return samplePoints;

}

//

// subdivide according to rotation

// as direction is not precise enough

// to adjust for small details

//

float rr = 1.0f;

if (group.GetType() == typeof(TreeGroupBranch))

{

rr = ((TreeGroupBranch)group).radius;

}

// subdivide as nescessary

float thresholdA = Mathf.Lerp(0.999f, 0.99999f, adaptiveQuality); // for optimize

float thresholdB = Mathf.Lerp(0.5f, 0.985f, adaptiveQuality); // for subdivision

float thresholdR = Mathf.Lerp(0.3f * rr, 0.1f * rr, adaptiveQuality); // for radius (un-affected by actual radius, only curve)

// Maximal number of subdivisions

int maxDivisions = 200;

//

// Sub-Divide:

// Sub-divide where nescessary

//

int first = 0;

while (first < samplePoints.Count - 1)

{

for (int i = first; i < samplePoints.Count - 1; i++)

{

// end rotations for segment

Quaternion a = node.spline.GetRotationAtTime(samplePoints[i]);

Quaternion b = node.spline.GetRotationAtTime(samplePoints[i + 1]);

// rotated up vectors

Vector3 upA = a * Vector3.up;

Vector3 upB = b * Vector3.up;

// rotated right vectors

Vector3 rightA = a * Vector3.right;

Vector3 rightB = b * Vector3.right;

// rotated front vectors

Vector3 frontA = a * Vector3.forward;

Vector3 frontB = b * Vector3.forward;

// radius

float radiusA = group.GetRadiusAtTime(node, samplePoints[i], true);

float radiusB = group.GetRadiusAtTime(node, samplePoints[i + 1], true);

bool needSubDivision = false;

// check end rotations against each other

if (Vector3.Dot(upA, upB) < thresholdB) needSubDivision = true;

if (Vector3.Dot(rightA, rightB) < thresholdB) needSubDivision = true;

if (Vector3.Dot(frontA, frontB) < thresholdB) needSubDivision = true;

// Check radius difference

if (Mathf.Abs(radiusA - radiusB) > thresholdR) needSubDivision = true;

if (needSubDivision)

{

maxDivisions--;

if (maxDivisions > 0)

{

// too much change so insert point in the middle

float mid = (samplePoints[i] + samplePoints[i + 1]) * 0.5f;

samplePoints.Insert(i + 1, mid);

// exit for-loop

break;

}

}

// set next as entry point if a sub-division occurs in the next segment

first = i + 1;

}

}

//

// Optimize:

// Remove unneeded sample points

//

for (int i = 0; i < samplePoints.Count - 2; i++)

{

// positions

Vector3 a = node.spline.GetPositionAtTime(samplePoints[i]);

Vector3 b = node.spline.GetPositionAtTime(samplePoints[i + 1]);

Vector3 c = node.spline.GetPositionAtTime(samplePoints[i + 2]);

// radius

float radiusA = group.GetRadiusAtTime(node, samplePoints[i], true);

float radiusB = group.GetRadiusAtTime(node, samplePoints[i + 1], true);

float radiusC = group.GetRadiusAtTime(node, samplePoints[i + 2], true);

// rotated up vectors

Vector3 dirAB = (b - a).normalized;

Vector3 dirAC = (c - a).normalized;

bool removeMidPoint = false;

// check directions against each other

if (Vector3.Dot(dirAB, dirAC) >= thresholdA)

{

removeMidPoint = true;

}

if (Mathf.Abs(radiusA - radiusB) > thresholdR) removeMidPoint = false;

if (Mathf.Abs(radiusB - radiusC) > thresholdR) removeMidPoint = false;

// remove point inbetween a and b..

if (removeMidPoint)

{

samplePoints.RemoveAt(i + 1);

i--;

}

}

//

// Smooth capping, requires extra points..

//

if (node.capRange > 0.0f)

{

int capLoops = 1 + Mathf.CeilToInt(node.capRange * 16.0f * adaptiveQuality);

for (int i = 0; i < capLoops; i++)

{

float angle = ((float)(i + 1) / (capLoops)) * Mathf.PI * 0.5f;

float smooth = Mathf.Sin(angle);

float capPoint = capStartPoint + node.capRange * smooth;

if (capPoint < node.breakOffset)

{

samplePoints.Add(capPoint);

}

}

// make sure they are in the correct order

samplePoints.Sort();

}

//

// Add end point.. or make sure it is at 1.0, unless spline is broken..

//

if (1.0f <= node.breakOffset)

{

if (samplePoints[samplePoints.Count - 1] < 1.0f)

{

samplePoints.Add(1.0f);

}

else

{

samplePoints[samplePoints.Count - 1] = 1.0f;

}

}

return samplePoints;

}

//

// Generates fast preview

public void PreviewMesh(Matrix4x4 worldToLocalMatrix, out Material[] outMaterials)

{

outMaterials = null;

if (!mesh)

{

Debug.LogError("TreeData must have mesh assigned");

return;

}

bool origAmbOcc = root.enableAmbientOcclusion;

float origLOD = root.adaptiveLODQuality;

root.enableMaterialOptimize = false;

root.enableWelding = false;

root.enableAmbientOcclusion = false;

root.adaptiveLODQuality = 0.0f;

UpdateMesh(worldToLocalMatrix, out outMaterials);

// re-enable welding..

root.enableWelding = true;

root.enableMaterialOptimize = true;

root.enableAmbientOcclusion = origAmbOcc;

root.adaptiveLODQuality = origLOD;

isInPreviewMode = true;

}

public void UpdateMesh(Matrix4x4 worldToLocalMatrix, out Material[] outMaterials)

{

outMaterials = null;

if (!mesh)

{

Debug.LogError("TreeData must have mesh assigned");

return;

}

isInPreviewMode = false;

// lists to hold materials, vertices and triangles and aospheres

List<TreeMaterial> materials = new List<TreeMaterial>();

List<TreeVertex> verts = new List<TreeVertex>();

List<TreeTriangle> tris = new List<TreeTriangle>();

List<TreeAOSphere> aoSpheres = new List<TreeAOSphere>();

// Set build flags..

int buildFlags = 0;

if (root.enableAmbientOcclusion)

{

buildFlags |= (int)TreeGroup.BuildFlag.BuildAmbientOcclusion;

}

if (root.enableWelding)

{

buildFlags |= (int)TreeGroup.BuildFlag.BuildWeldParts;

}

// Update TreeData...

UpdateMesh(worldToLocalMatrix, materials, verts, tris, aoSpheres, buildFlags, root.adaptiveLODQuality, root.aoDensity);

// clear previous mesh data

if (verts.Count > 65000)

{

// Too much to build

Debug.LogWarning("Tree mesh would exceed maximum vertex limit .. aborting");

return;

}

mesh.Clear();

if (verts.Count == 0 || tris.Count == 0)

{

// Nothing to build

return;

}

// Optimize to use a single material

OptimizeMaterial(materials, verts, tris);

Profiler.BeginSample("CopyMeshData");

// Copy mesh data to static arrays.. surely there must be a faster way to do this

Vector3[] tmpPos = new Vector3[verts.Count];

Vector3[] tmpNor = new Vector3[verts.Count];

Vector2[] tmpUV0 = new Vector2[verts.Count];

Vector2[] tmpUV1 = new Vector2[verts.Count];

Vector4[] tmpTan = new Vector4[verts.Count];

Color[] tmpCol = new Color[verts.Count];

for (int i = 0; i < verts.Count; i++)

{

tmpPos[i] = verts[i].pos;

tmpNor[i] = verts[i].nor;

tmpUV0[i] = verts[i].uv0;

tmpUV1[i] = verts[i].uv1;

tmpTan[i] = verts[i].tangent;

tmpCol[i] = verts[i].color;

}

// assign vertex properties

mesh.vertices = tmpPos;

mesh.normals = tmpNor;

mesh.uv = tmpUV0;

mesh.uv2 = tmpUV1;

mesh.tangents = tmpTan;

mesh.colors = tmpCol;

// assign triangles

int[] tmpTris = new int[tris.Count * 3];

const int kMaxOptimizedMaterials = 2;

List<Material> usedOptimizedMaterials = new List<Material>(kMaxOptimizedMaterials);

mesh.subMeshCount = kMaxOptimizedMaterials;

for (int mat = 0; mat < kMaxOptimizedMaterials; mat++)

{

int triCount = 0;

for (int i = 0; i < tris.Count; i++)

{

if (tris[i].materialIndex == mat)

{

tmpTris[triCount + 0] = tris[i].v[0];

tmpTris[triCount + 1] = tris[i].v[1];

tmpTris[triCount + 2] = tris[i].v[2];

triCount += 3;

}

}

if (triCount > 0)

{

int[] tmpTrisMat = new int[triCount];

for (int i = 0; i < triCount; i++)

{

tmpTrisMat[i] = tmpTris[i];

}

mesh.SetTriangles(tmpTrisMat, usedOptimizedMaterials.Count);

if (mat == 0)

usedOptimizedMaterials.Add(optimizedSolidMaterial);

else

usedOptimizedMaterials.Add(optimizedCutoutMaterial);

}

}

outMaterials = usedOptimizedMaterials.ToArray();

mesh.subMeshCount = usedOptimizedMaterials.Count;

Profiler.EndSample(); // CopyMeshData

// Recompute Bounds

mesh.RecalculateBounds();

}

private static void ExtractOptimizedShaders(List<TreeMaterial> materials, out Shader optimizedSolidShader, out Shader optimizedCutoutShader)

{

List<Shader> barkShaders = new List<Shader>();

List<Shader> leafShaders = new List<Shader>();

foreach (TreeMaterial treeMaterial in materials)

{

Material material = treeMaterial.material;

if (material && material.shader)

{

if (TreeEditorHelper.IsTreeBarkShader(material.shader))

barkShaders.Add(material.shader);

else if (TreeEditorHelper.IsTreeLeafShader(material.shader))

leafShaders.Add(material.shader);

}

}

optimizedSolidShader = null;

optimizedCutoutShader = null;

// Always use Shader.Find() to be able to override the shaders used in

// the optimized materials, even if the new shaders have the same

// names as the defaults.

if (barkShaders.Count > 0)

optimizedSolidShader = Shader.Find(TreeEditorHelper.GetOptimizedShaderName(barkShaders[0]));

if (leafShaders.Count > 0)

optimizedCutoutShader = Shader.Find(TreeEditorHelper.GetOptimizedShaderName(leafShaders[0]));

// fallback to default shaders

if (!optimizedSolidShader)

optimizedSolidShader = TreeEditorHelper.DefaultOptimizedBarkShader;

if (!optimizedCutoutShader)

optimizedCutoutShader = TreeEditorHelper.DefaultOptimizedLeafShader;

}

public bool OptimizeMaterial(List<TreeMaterial> materials, List<TreeVertex> vertices, List<TreeTriangle> triangles)

{

if (!optimizedSolidMaterial || !optimizedCutoutMaterial)

{

Debug.LogError("Optimized materials haven't been assigned");

return false;

}

Shader optimizedSolidShader;

Shader optimizedCutoutShader;

ExtractOptimizedShaders(materials, out optimizedSolidShader, out optimizedCutoutShader);

optimizedSolidMaterial.shader = optimizedSolidShader;

optimizedCutoutMaterial.shader = optimizedCutoutShader;

//

// Settings

//

int texWidth = 1024;

int texHeight = 1024;

int texPadding = 32;

Profiler.BeginSample("OptimizeMaterial");

//

// Compute surface area of each material

//

float[] materialArea = new float[materials.Count];

float totalTileV = 0.0f;

float totalNonTileV = 0.0f;

for (int i = 0; i < materials.Count; i++)

{

if (!materials[i].tileV)

{

totalNonTileV += 1.0f;

}

else

{

totalTileV += 1.0f;

}

}

//totalArea = totalTileV + Mathf.Clamp01(totalNonTileV);

// Normalize

for (int i = 0; i < materials.Count; i++)

{

if (materials[i].tileV)

{

materialArea[i] = 1.0f;

}

else

{

materialArea[i] = 1.0f / totalNonTileV;

}

// materialArea[i] /= totalArea;

// Debug.Log("material " + i + " area = " + materialArea[i] + " tileV = " + materialTileV[i]);

}