Jump to content
• Advertisement

# Get convex hull from 3D point cloud?

This topic is 2844 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

## Recommended Posts

Okay I've been doing research on collision detection, I'm trying to use the minkowski sum to see if 2 objects are touching, I've got everything set up bar eliminating the points inside the shape.
Here is what I have so far:
 public override bool Intersects(BoundingConvex Other) { List<Vector3> Sum = new List<Vector3>(); Vector3 SumCenter = Position - Other.Position; foreach (Vector3 Vec in Vecs) { foreach (Vector3 OthVec in Other.Vecs) { Sum.Add((Vec) + (OthVec)); } } Vector3 SumOrigin = Vector3.Zero; foreach (Vector3 Vec in Sum) { SumOrigin += Vec; } SumOrigin /= Sum.Count; foreach (Vector3 Vec in Sum) { Vector3 Temp = Vec + SumOrigin; if (Vector3.Dot(Temp, SumCenter - Temp) > 0) { return false; } } return true; } 
Naturally I want to eliminate unwanted points before the origin is calculated, if anyone asks, I calculate an origin to make sure the origin of the shape is inside the shape itself.

I had been looking into the gift wrap method but I could only find a pseudo implementation with poor description and a java implementation which was messy as hell, so I tried splicing and it just went to hell and back.

So if anyone can help me find a fast way to get rid of vertices that are not on the surface of the hull, that would be great.

Any and all help is appreciated,
Thanks in advanced,
Bombshell

#### Share this post

##### Share on other sites
Advertisement
would it make sense to get the points furthest to the front, back left, right, up and down create normals for the faces they create, then check for the point furthest in that normal, repeating this until no more points are found?
the first part would be simple, and creating faces from that should be fairly straight forwards too.
But I'd imagine checking how far it is in the normals direction would take a little more.
I think I could get all points using a half space in direction of the normal, re-align them temporarily to treat the normal as an axis and get the furthest away.
Re-skin the hull and repeat until all half space checks return no points?

#### Share this post

##### Share on other sites
If memory serves, Quickhull is still gold standard (but I'm not up to date).
Alternatively, Bullet can do this for you in btConvexHullShape.

#### Share this post

##### Share on other sites
I'm not using any libraries bar xna, just so I can get experience in all parts of game development, however little it may be.
I'm planning on writing a C++ engine after a few projects, so its good to know a bit of everything before I try.

at the moment I'm creating a base shape using the top, bottom, right, left, front and back points.

Then checking against the face normals vertices inside or on the surface of the shape are removed from the vertex list.
Vertices in front of a certain face are found then the vertex furthest in the normals direction found.
This is repeated until no vertices are in the list. At which point the list of vertices used for the faces of the shape are returned (or the faces, normals, whatever is needed for the situation)

I'm not sure how fast it will go but its implementation is easy enough, only thing I'm stuck on is finding the vertex furthest in the normal direction.

#### Share this post

##### Share on other sites
Here is my current implementation. Unsure if it works completely correct, I'm whipping up a quick visualization of it now.
This is the Method for getting the hulls vertices
 public List<Vector3> GetHullVerts(List<Vector3> Vecs) { List<Vector3> Hull = new List<Vector3>(); List<HalfSpace> HSpace = new List<HalfSpace>(); Vector3 Top, Bottom, Left, Right, Front, Back; Top = Bottom = Left = Right = Front = Back = Vecs[0]; foreach (Vector3 Vec in Vecs) { if (Vec.Z > Top.Z) { Top = Vec; } if (Vec.Z < Bottom.Z) { Bottom = Vec; } if (Vec.X > Right.X) { Right = Vec; } if (Vec.X < Left.X) { Left = Vec; } if (Vec.Y > Front.Y) { Front = Vec; } if (Vec.Y < Back.Y) { Back = Vec; } } if (Top != Back && Top != Right && Back != Right) { HSpace.Add(new HalfSpace(Top, Back, Right)); } if (Top != Right && Top != Front && Right != Front) { HSpace.Add(new HalfSpace(Top, Right, Front)); } if (Top != Front && Top != Left && Left != Front) { HSpace.Add(new HalfSpace(Top, Front, Left)); } if (Top != Left && Top != Back && Left != Back) { HSpace.Add(new HalfSpace(Top, Left, Back)); } if (Bottom != Back && Bottom != Right && Back != Right) { HSpace.Add(new HalfSpace(Bottom, Right, Back)); } if (Bottom != Right && Bottom != Front && Right != Front) { HSpace.Add(new HalfSpace(Bottom, Front, Right)); } if (Bottom != Front && Bottom != Left && Left != Front) { HSpace.Add(new HalfSpace(Bottom, Left, Front)); } if (Bottom != Left && Bottom != Back && Left != Back) { HSpace.Add(new HalfSpace(Bottom, Back, Left)); } List<Vector3> Temp = new List<Vector3>(); List<HalfSpace> TempSpace = new List<HalfSpace>(); List<Vector3> TempVecs = new List<Vector3>(); while (Vecs.Count > 0) { TempVecs.Clear(); TempVecs.AddRange(Vecs); foreach (Vector3 Vec in TempVecs) { int i; for (i = 0; i < HSpace.Count; i++) { if (HSpace.ix(Vec)) { break; } } if (i == HSpace.Count) { Vecs.Remove(Vec); } } TempSpace.Clear(); TempSpace.AddRange(HSpace); foreach (HalfSpace HS in TempSpace) { Temp.Clear(); foreach (Vector3 Vec in Vecs) { if (HS.ix(Vec)) { Temp.Add(Vec); } } if (Temp.Count != 0) { Vector3 i = Temp[0]; float x = Vector3.Dot(Temp[0], HS.Normal) / HS.Normal.Length(); foreach (Vector3 Vec in Temp) { float y = Vector3.Dot(Vec, HS.Normal) / HS.Normal.Length(); if (y > x) { x = y; i = Vec; } } HSpace.Remove(HS); HSpace.Add(new HalfSpace(HS.A, HS.B, i)); HSpace.Add(new HalfSpace(HS.B, HS.C, i)); HSpace.Add(new HalfSpace(HS.C, HS.A, i)); } } } foreach (HalfSpace HS in HSpace) { if (!Hull.Contains(HS.A)) { Hull.Add(HS.A); } if (!Hull.Contains(HS.B)) { Hull.Add(HS.B); } if (!Hull.Contains(HS.C)) { Hull.Add(HS.C); } } return Hull; } 
This is the HalfSpace class, to explain the vague names of functions
 public class HalfSpace { public Vector3 A, B, C; public Vector3 Position, Normal; public float Radius; public HalfSpace(Vector3 A, Vector3 B, Vector3 C) { this.A = A; this.B = B; this.C = C; Position = (A + B + C)/3; Normal = Vector3.Normalize(Vector3.Cross(B - A, C - A)); Radius = Vector3.Distance(A, B) + Vector3.Distance(A, C); } public bool i(Vector3 X) { if (Vector3.Dot(Normal, Vector3.Normalize(Position - X)) <= 0) { return true; } return false; } public bool ix(Vector3 X) { if (Vector3.Dot(Normal, Vector3.Normalize(Position - X)) < 0) { return true; } return false; } public bool Inside(Vector3 X) { if (Vector3.Dot(Normal, Vector3.Normalize(Position - X)) <= 0 && Vector3.Distance(Position, X) <= Radius) { return true; } return false; } } 

All my previous tries failed so I named things quick to prototype this faster.

#### Share this post

##### Share on other sites

If memory serves, Quickhull is still gold standard (but I'm not up to date).

Quick Hull has complexity O(n log(n)) and may in the worst case fall back to O(n²). By now, there are optimal (!) output-sensitive approaches. For instance the approach of Timothy M. Chan runs always in O(n log h), where h is the number of points on the hull.

#### Share this post

##### Share on other sites
I'm pretty sure its nothing impressive, but where would my implementation come closest to?

#### Share this post

##### Share on other sites

• Advertisement
• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• Advertisement

• ### Popular Now

• 11
• 15
• 21
• 26
• 11
• Advertisement
×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!