foreach(ArgVert aV in aMD_IcosaSphere.icoPointCloud)
{
vN_In = aV.vPos.normalized;
q = Quaternion.LookRotation(vN_In);
int lev0, lev1, lev2, lev3;
GameObject gO;
GO_Tracker gT;
if (aV.itn.sector == 5)
{
gO = (GameObject)Instantiate(hexPreFab, aV.vPos, q);
gT = new GO_Tracker();
gT.go = gO;
gT.aVNode = aV;
lstHex_GO.Add(gT);
lev3 = aV.itn.nodePath;
lev0 = lev3 >> 6;
lev1 = lev3 >> 4 & 3;
lev2 = lev3 >> 2 & 3;
lev3 = lev3 & 3;
lstHex_GO[lstHex_GO.Count - 1].go.GetComponentInChildren<Text>().text = lev0.ToString() + lev1.ToString() + lev2.ToString() + lev3.ToString();
}
}
Spatial culling
Spatial culling might help you out here. There are many ways of doing this, but one of the more popular ones is probably the Octree. The idea is to store information in the tree about which triangles belong to which nodes. This obviously has a setup phase, but once the Octree is populated, getting the actual nearby triangles is much easier. Say you have triangle #379, and you want to find triangles that are close to it; you’d check which nodes that #379 is overlapping and you’ll find all potential matches. So you’ll get a subset of the triangles to work with, probably a few orders of magnitude less, which should quicken up your neighbor tests considerably.
Well if the triangles move around too much, then the cost of building the Octree might weigh out the benefits of fast lookup. But look at it this way. Say you have 1000 triangles and need to check them against each other in your current solution. That’s 1000*999 tests. Almost a million tests. With an octree, you’d probably do 2-3 tests per triangle to build the tree. That’s 1000*3, 3000 tests. Then during the lookup, you’d have to access nodes, so that’s another 3000 tests, and maybe inside each node there are 15-20 triangles so that’s another 20000 tests. From a rough guesstimate, you’re down from 1000k to 26k tests. But it’s also a lot of memory management since you have to move around elements…
Sorted Point Cloud by dist v = (-0.053, 1.498, -0.017) sector = 17 NodePath = 0 sector = 17 dist = 3.50284 v = (0.033, 1.498, 0.045) sector = 19 NodePath = 0 sector = 19 dist = 3.50284 v = (0.000, 1.498, -0.056) sector = 16 NodePath = 0 sector = 16 dist = 3.50284 v = (-0.033, 1.498, 0.045) sector = 18 NodePath = 0 sector = 18 dist = 3.50284 v = (0.053, 1.498, -0.017) sector = 15 NodePath = 0 sector = 15 dist = 3.50284 v = (-0.066, 1.494, 0.091) sector = 18 NodePath = 3 sector = 18 dist = 3.507324 v = (0.106, 1.494, -0.035) sector = 15 NodePath = 3 sector = 15 dist = 3.507324 v = (-0.106, 1.494, -0.035) sector = 17 NodePath = 3 sector = 17 dist = 3.507324 v = (0.066, 1.494, 0.091) sector = 19 NodePath = 3 sector = 19 dist = 3.507324 v = (0.000, 1.494, -0.112) sector = 16 NodePath = 3 sector = 16 dist = 3.507324 v = (0.152, 1.491, 0.015) sector = 15 NodePath = 1 sector = 15 dist = 3.512431 ... v = (-0.152, -1.491, -0.015) sector = 1 NodePath = 2 sector = 1 dist = 6.492669 v = (0.131, -1.491, -0.077) sector = 3 NodePath = 2 sector = 3 dist = 6.492669 v = (0.114, -1.491, 0.101) sector = 4 NodePath = 2 sector = 4 dist = 6.492669 v = (-0.114, -1.491, 0.101) sector = 1 NodePath = 1 sector = 1 dist = 6.492669 v = (-0.066, -1.494, -0.091) sector = 2 NodePath = 3 sector = 2 dist = 6.495427 v = (0.000, -1.494, 0.112) sector = 0 NodePath = 3 sector = 0 dist = 6.495427 v = (-0.106, -1.494, 0.035) sector = 1 NodePath = 3 sector = 1 dist = 6.495427 v = (0.066, -1.494, -0.091) sector = 3 NodePath = 3 sector = 3 dist = 6.495427 v = (0.106, -1.494, 0.035) sector = 4 NodePath = 3 sector = 4 dist = 6.495427 v = (0.000, -1.498, 0.056) sector = 0 NodePath = 0 sector = 0 dist = 6.497848 v = (0.053, -1.498, 0.017) sector = 4 NodePath = 0 sector = 4 dist = 6.497848 v = (-0.053, -1.498, 0.017) sector = 1 NodePath = 0 sector = 1 dist = 6.497848 v = (-0.033, -1.498, -0.045) sector = 2 NodePath = 0 sector = 2 dist = 6.497848 total verts = 5119
public class ICO_Tree_Node_ID
{
public int sector; // 20 sectors to ICO
public int nodePath; // 2 bits per depth level
}
public class ArgVert
{
public Vector3 vPos;
public ICO_Tree_Node_ID itn = new ICO_Tree_Node_ID();
public float dist;
}
public void SetSortDist(Vector3 Apex)
{
foreach(ArgVert aV in icoPointCloud)
{
aV.dist = (aV.vPos - Apex).magnitude;
}
}
public void sortPointCloud()
{
icoPointCloud.Sort((x, y) => x.dist.CompareTo(y.dist));
}
Initial Generation using ICO_TREE_GENERATOR
List Generated v = (0.000, -1.498, 0.056) sector = 0 NodePath = 0 v = (0.061, -1.491, 0.140) sector = 0 NodePath = 1 v = (-0.061, -1.491, 0.140) sector = 0 NodePath = 2 v = (0.000, -1.494, 0.112) sector = 0 NodePath = 3 v = (0.121, -1.477, 0.223) sector = 0 NodePath = 4 v = (0.181, -1.456, 0.306) sector = 0 NodePath = 5 v = (0.061, -1.465, 0.308) sector = 0 NodePath = 6 v = (0.121, -1.467, 0.279) sector = 0 NodePath = 7 v = (-0.121, -1.477, 0.223) sector = 0 NodePath = 8 v = (-0.061, -1.465, 0.308) sector = 0 NodePath = 9 v = (-0.181, -1.456, 0.306) sector = 0 NodePath = 10 v = (-0.121, -1.467, 0.279) sector = 0 NodePath = 11 v = (0.000, -1.472, 0.280) sector = 0 NodePath = 12 ...
public class ICO_Tree_Node_ID
{
public int sector; // 20 sectors to ICO
public int nodePath; // 2 bits per depth level
}
public class ArgVert
{
public Vector3 vPos;
public ICO_Tree_Node_ID itn = new ICO_Tree_Node_ID();
}
public class ArgosMeshDraft : MeshDraft
{
public List<Vector3> vTriCenter = new List<Vector3>();
public List<int> vQual = new List<int>();
public List<ArgVert> icoPointCloud = new List<ArgVert>();
public ArgosMeshDraft() :base()
{
}
public void Add_ITN_Node(MeshDraft tri,int sector,int nodePath)
{
Vector3 vC = (tri.vertices[0] + tri.vertices[1] + tri.vertices[2] )/ 3f;
ArgVert aV = new ArgVert();
aV.vPos = vC;
aV.itn.sector = sector;
aV.itn.nodePath = nodePath;
icoPointCloud.Add(aV);
}
void Create_GP(int depth)
{
for(int i = 0; i<20; i++)
{
Vector3 v0 = aMD.vertices[aMD.triangles[i*3]];
Vector3 v1 = aMD.vertices[aMD.triangles[i*3 +1]];
Vector3 v2 = aMD.vertices[aMD.triangles[i*3 + 2]];
Color col = getWhite();
subdivide(v0, v1, v2, depth, col,i,0);
}
}
void subdivide(Vector3 v1, Vector3 v2, Vector3 v3, int depth, Color col,int sector, int nID)
{
Vector3 v12, v23, v31;
Vector3 v12_n, v23_n, v31_n;
int i;
if (depth == 0)
{
if (icoType == ICO_Type.HEX)
{
addHex(v1, v2, v3, col);
}
else if(icoType == ICO_Type.TRIANGLE)
{
addTriangle(v1, v2, v3, col);
}
else if(icoType == ICO_Type.ICO_TREE_GENERATOR)
{
addITG_Node(v1, v2, v3, sector, nID);
}
return;
}
v12 = (v1 + v2) / 2.0f;
v23 = (v2 + v3) / 2.0f;
v31 = (v3 + v1) / 2.0f;
/* extrude midpoints to lie on unit sphere */
v12_n = v12.normalized * radius;
v23_n = v23.normalized * radius;
v31_n = v31.normalized * radius;
int shifter = nID;
shifter = shifter << 2;
/* recursively subdivide new triangles */
subdivide(v1, v12_n, v31_n, depth - 1, col, sector, shifter | 0);
subdivide(v12_n, v2, v23_n, depth - 1, col, sector, shifter | 1);
subdivide(v31_n, v23_n, v3, depth - 1, col, sector, shifter | 2);
subdivide(v23_n, v31_n, v12_n, depth - 1, col, sector, shifter | 3);
}
