123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200 |
-
- using System;
- using System.Collections.Generic;
- using System.Diagnostics;
- namespace OpenSim.Region.Physics.ConvexDecompositionDotNet
- {
- public delegate void ConvexDecompositionCallback(ConvexResult result);
- public class FaceTri
- {
- public float3 P1;
- public float3 P2;
- public float3 P3;
- public FaceTri() { }
- public FaceTri(List<float3> vertices, int i1, int i2, int i3)
- {
- P1 = new float3(vertices[i1]);
- P2 = new float3(vertices[i2]);
- P3 = new float3(vertices[i3]);
- }
- }
- public static class ConvexDecomposition
- {
- private static void addTri(VertexPool vl, List<int> list, float3 p1, float3 p2, float3 p3)
- {
- int i1 = vl.getIndex(p1);
- int i2 = vl.getIndex(p2);
- int i3 = vl.getIndex(p3);
-
- if ( i1 != i2 && i1 != i3 && i2 != i3 )
- {
- list.Add(i1);
- list.Add(i2);
- list.Add(i3);
- }
- }
- public static void calcConvexDecomposition(List<float3> vertices, List<int> indices, ConvexDecompositionCallback callback, float masterVolume, int depth,
- int maxDepth, float concavePercent, float mergePercent)
- {
- float4 plane = new float4();
- bool split = false;
- if (depth < maxDepth)
- {
- float volume = 0f;
- float c = Concavity.computeConcavity(vertices, indices, ref plane, ref volume);
- if (depth == 0)
- {
- masterVolume = volume;
- }
- float percent = (c * 100.0f) / masterVolume;
- if (percent > concavePercent)
- {
- split = true;
- }
- }
- if (depth >= maxDepth || !split)
- {
- HullResult result = new HullResult();
- HullDesc desc = new HullDesc();
- desc.SetHullFlag(HullFlag.QF_TRIANGLES);
- desc.Vertices = vertices;
- HullError ret = HullUtils.CreateConvexHull(desc, ref result);
- if (ret == HullError.QE_OK)
- {
- ConvexResult r = new ConvexResult(result.OutputVertices, result.Indices);
- callback(r);
- }
- return;
- }
- List<int> ifront = new List<int>();
- List<int> iback = new List<int>();
- VertexPool vfront = new VertexPool();
- VertexPool vback = new VertexPool();
-
- for (int i = 0; i < indices.Count / 3; i++)
- {
- int i1 = indices[i * 3 + 0];
- int i2 = indices[i * 3 + 1];
- int i3 = indices[i * 3 + 2];
- FaceTri t = new FaceTri(vertices, i1, i2, i3);
- float3[] front = new float3[4];
- float3[] back = new float3[4];
- int fcount = 0;
- int bcount = 0;
- PlaneTriResult result = PlaneTri.planeTriIntersection(plane, t, 0.00001f, ref front, out fcount, ref back, out bcount);
- if (fcount > 4 || bcount > 4)
- {
- result = PlaneTri.planeTriIntersection(plane, t, 0.00001f, ref front, out fcount, ref back, out bcount);
- }
- switch (result)
- {
- case PlaneTriResult.PTR_FRONT:
- Debug.Assert(fcount == 3);
- addTri(vfront, ifront, front[0], front[1], front[2]);
- break;
- case PlaneTriResult.PTR_BACK:
- Debug.Assert(bcount == 3);
- addTri(vback, iback, back[0], back[1], back[2]);
- break;
- case PlaneTriResult.PTR_SPLIT:
- Debug.Assert(fcount >= 3 && fcount <= 4);
- Debug.Assert(bcount >= 3 && bcount <= 4);
- addTri(vfront, ifront, front[0], front[1], front[2]);
- addTri(vback, iback, back[0], back[1], back[2]);
- if (fcount == 4)
- {
- addTri(vfront, ifront, front[0], front[2], front[3]);
- }
- if (bcount == 4)
- {
- addTri(vback, iback, back[0], back[2], back[3]);
- }
- break;
- }
- }
-
- if (ifront.Count > 0)
- {
- int vcount = vfront.GetSize();
- List<float3> vertices2 = vfront.GetVertices();
- for (int i = 0; i < vertices2.Count; i++)
- vertices2[i] = new float3(vertices2[i]);
- int tcount = ifront.Count / 3;
- calcConvexDecomposition(vertices2, ifront, callback, masterVolume, depth + 1, maxDepth, concavePercent, mergePercent);
- }
- ifront.Clear();
- vfront.Clear();
- if (iback.Count > 0)
- {
- int vcount = vback.GetSize();
- List<float3> vertices2 = vback.GetVertices();
- int tcount = iback.Count / 3;
- calcConvexDecomposition(vertices2, iback, callback, masterVolume, depth + 1, maxDepth, concavePercent, mergePercent);
- }
- iback.Clear();
- vback.Clear();
- }
- }
- }
|