next »

[gimymblert]

Hello

I'm trying to implement a convex hull algorithm and I thought I could use support mapping to sweep through all the points and discard point that are in the interior of the shape (leaving only point on the surface of the hull). Basically I calculate a centroid (ie the average of all the point) that I use to define a direction to every point. For every points, I try to find if there is a better point (further) in the direction of that point, relative to the centroid, using a dot product.

But I have strange behavior, what did I missed?
Here is my current code

Code:

		foreach (Vector3 v in vertlist) 
		{
			centroid += v;
		}
		centroid /= vertlist.Length;


//		ArrayList discard = new ArrayList();

		Vector3 support = new Vector3();
		float max = float.Epsilon;

		foreach (Vector3 v in vert) 
		{

			//vector= end - start
			Vector3 direction = v - centroid;
			print ("------------------------");
			max = float.Epsilon;


			foreach (Vector3 t in vert) 
			{
				

				Vector3 compared= t - centroid;

				float dot = Vector3.Dot (compared,direction);

				if (dot > max) {
					max = dot;
					support = t;
					if (t == v)	print("ding!");
					print ("maxi!");
				}
				//print (dot +" :: "+ max);
				//print(direction.magnitude + "//" + compared.magnitude);


			}


			if (support != v) 
			{
				discard.Add (v);
				print ("discard:"+v);
			}

			if (support == v) 
			{
				print ("self");
			}


		}
		print ("discard count:"+discard.Count);

More about support mapping.

https://www.toptal.com/game/video-game-physics-part-ii-collision-detection-for-solid-objects

Support Functions

A support function sA(d) returns a point on the boundary of the shape A that has the highest projection on the vector d. Mathematically, it has the highest dot product with d. This is called a support point, and this operation is also known as support mapping. Geometrically, this point is the farthest point on the shape in the direction of d.

SupportMapping

Finding a support point on a polygon is relatively easy. For a support point for vector d, you just have to loop through its vertices and find the one which has the highest dot product with d, like this:

Code:

Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) {
    float highest = -FLT_MAX;
    Vector2 support = (Vector2){0, 0};

    for (int i = 0; i < count; ++i) {
        Vector2 v = vertices[i];
        float dot = v.x * d.x + v.y * d.y;

        if (dot > highest) {
            highest = dot;
            support = v;
        }
    }

    return support;
}

[qMopey]

I'm not aware of a convex hull algorithm that uses only support points. I suggest you lookup an already existing convex hull algorithm and implement that. Please note that convex hulls in 3D are difficult and you'll need to learn some new concepts in order to implement the algorithm correctly. The hard part is not implementing a support function, but the bookkeeping of all adjacency (connectivity) info. This gets difficult when you run into degenerate hull configurations (like flipped faces, duplicated vertices, face merging, etc).

I know you've already seen Dirk's GDC presentation, so just go with that and ask specific questions if you run into them. I've implemented 3D Quick Hull a couple times before and can probably answer questions if you have them.

[gimymblert]

I do, I started with valve's quickhull3D's recipe. That's why I'm using support mapping, it precisely allow to lower the bookkeeping.

There is another trick to limit effects of degenerate case such as precision issues, colinearity/coplanarity, and everything you mention, ie "inflating" the points using a centroid to avoid some of those bookeping hassle.

See this:
http://www.xbdev.net/misc_demos/demos/convexhull3d/paper.pdf
It expend on the quickhull3D

I'm also interested in support mapping for potential use in the future.

edit:
I have already coded the original algorithm up to the simplex (the easy part), I'm exploring the support mapping option.

[qMopey]

I see, well at this step you have 4 faces on the simplex, and each face has points that are *above* it. During a quick hull expansion you must choose *any* point above *any* face, and expand the hull to this point.

This leaves us freedom to choose whatever point we want. You can choose a random face and a random point that belongs to that face. You can choose the point farthest from all faces. Lastly, we can choose a random face and the farthest point that belongs to it. There's possibly more options, but these are the important ones. Which one you choose affects the run-time of the algorithm, and the number of iterations.

Personally I just chose a random face and the farthest point from this face.

Choosing the farthest point from a face can be done with the support function, and does *not* require a centroid or any reference points. Simply compute the dot product along the support direction (the face normal) and keep track of the maximal point, this is the point that is farthest from your given face.

The code you had copy/pasted for 2D works perfectly for the 3D case if you expand the definition of the dot product (I modified the code slightly according to my preferences):

Code:

v3 Support( v3 *verts, int count, v3 d )
{
    v3 s = verts[ 0 ];
    float max = Dot( d, s );

    for ( int i = 1; i < count; ++i )
    {
        v3 v = verts[ i ];
        float dot = Dot( d, v );

        if ( dot > max )
        {
            max = dot;
            s = v;
        }
    }

    return s;
}

Also, it is possible to sort the points as they are allotted to each face, such that there is no need to compute support points upon each iteration. Instead the points can be sorted according to their dot products Dot( d, v ). This can make selecting the farthest point from a face a constant-time operation. In practice this may or may not improve efficiency (I myself have never bothered to try).

Hope this helps! If you already understand all of this feel free to ask a different question

[gimymblert]

I think there might be confusion here! I implemented qhull 3D up to the simplex!

It's not the support mapping version!

I have restarted to do the support mapping version, there I'm at the level where I visualized the discarded point to see if everything works correctly (it seems bogus).

I haven't inflated the vertex yet.

Now centroid is useful to avoid the bookkeeping by expanding into the "unit sphere". Avoiding the edge cases.



I think my support point implementation is very similar to the code you provided to find support point.

The problem is that iterating all vertices to have their support and stocking all discarded point (inner points) seems to have bogus data upon visualization!

Here the current visualization, red are supposedly discarded point, they clearly above the surface, so the surface mapping failed?



Or maybe I got something wrong?  

[qMopey]

Right I understand you implemented qhull up to the simplex. My last post I assumed you had the simplex ready to go, but didn't yet assign vertices onto the simplex faces. I was describing what the algorithm starts to look like once you get verts assigned to each simplex face.

So taking a look at your picture you are trying to assign vertices to each face of the simplex! Good, this is the next step for you.Your support function is probably implemented correctly, so assume it is OK.

To me it looks like a bug with distance of point to plane computation. To assign a vertex to a face, the vertex must be above the face. To do this we must construct a plane for each simplex face where a, b and c are simplex face vertices in CCW order:

Code:

Plane MakePlane( v3 a, v3 b, v3 c )
{
    Plane p;
    p.normal = Norm( Cross( b - a, c - a ) );
    p.distance = Dot( p.normal, a );
    return p;
}

Here is an algorithm (psuedo code) to assign all vertices onto the simplex:

Code:

struct Plane
{
    v3 normal;
    float distance;
};

float Distance( Plane p, v3 v )
{
    return Dot( p.normal, v ) - p.distance;
}

struct Vert
{
    v3 v;
    int mark;
};

void PlaceVertsOntoSimplexFaces( Vert* verts, int count, Face* simplex )
{
    for ( int iFace = 0; iFace < 4; ++iFace )
    {
        Face* face = simplex + iFace;
        Plane plane = face->plane;

        for ( int i = 0; i < count; ++i )
        {
            Vert vert = verts[ i ];
            if ( vert.mark ) continue;

            float distance = Distance( plane, vert.v );
            
            if ( distance > 0 )
            {
                face->Assign( i );
                verts[ i ].mark = 1;
            }
        }
    }
}

You can see it's important to be careful with computing distance of point to face (or in other words, point to plane) to assign a free vertex to a face.

Then when all vertices are assigned to each simplex face you can start writing the main qhull expand function. Make sure to debug draw the simplex and show all vertices assigned to each face (like in your above picture) to verify you have the simplex constructed properly before moving on!

Take a look at my video and pause at 0 or 1 seconds. I draw a blue line from each simplex face to each assigned vertex. The next vertex I will expand to I render a red square. Debug visualization like this becomes very important to implement the qhull algorithm so it's great you already started this.

[gimymblert]

Thanks for the help, it's must be me who are miscommunicating.

I 'm not yet trying to assign point to the simplex. I don't think it's hard although I don't have yet assess "horizon" detection.

I'm really just trying to understand and test "support mapping" only. I'll move on once I have solve what's wrong (support vector seems fine just not the mapping part)

Before moving to the valuable help you have already provided

I'm not asking about quickhull, I'm asking for support mapping!

[qMopey]

Oh I see. Well I suggest you forget about that surface mapping convex hull paper. They were just experimenting and trying out something new. If you read the "Optimization" section they even plainly state they didn't even think about optimization when designing or implementing the algorithm -- they save "novel" but to me this reads as "complicated, inefficient, not useful" etc. It's going to result in a weird and complicated algorithm.

If you wanted to learn quickly by exploring an easier "surface mapping" paper that probably won't work out If you want to do it for learning purposes it will probably be harder than implementing qhull. Instead I recommend to just dive into qhull and ask questions as you go. This will probably be a better learning experience, and result in useful code.

Edit:
Also they called the title "surface mapping", not support mapping. Support mapping it usually means the support function we talked about already. The paper uses support mapping, but in the title they refer to surface mapping (as in mapping vertices onto a sphere).

[gimymblert]

Well I'll turn that into a qhull thread, will investigate support stuff a bit more before though. I'll come back to quickhull later when I'm stuck! lol

Though I don't care about optimization, just the discarding process.

Thanks.

[qMopey]

NP good luck

[gimymblert]

BTW support mapping is reference here too
http://www.cs.sjsu.edu/faculty/pollett/masters/Semesters/Spring12/josh/?mpr_report.html

[qMopey]

That's a support function, which maps to the surface of a convex hull in Minkowski space. Quite different from constructing a convex hull.

[gimymblert]

Anyway I was reading back all the docs I have to identify I there stuff I had missed

Support Mapping
Support mapping is often used in physics and
collision detection [Kim et al. 2002]. The support mapping for a
cloud of points given a direction is the point that is farthest in the
direction - which simply means finding the point with the maximum
dot product (i.e., dot(direction, point). The supporting point in any
direction is guaranteed to be on the surface of the convex hull cloud
of points. We exploit this concept in our algorithm to efficiently
determine the surface points.

We calculate the normal from the centroid to each
point and find the support vertex, and add it to a list. The list will
contain a set of points which sit on the convex hull surface. Using
the centroid, we project each surface point onto a sphere (i.e., with
the centroid the centre of the sphere).

Welp I hadn't normalize the direction and I tried to add the discarded points. I'll try to follow the recipe closer to see if that change anything.

Still don't work, moving on.

[gimymblert]

Hello!

I was wondering did you use half edge representation for the quickhull? It seems to advise using it, but porting the c++ code to c# isn't straightforward because "pointer", now I have cycle warning from the struct code

[gimymblert]

Oh well I should have slept more I would have stay classy

[gimymblert]

2 years later the support mapping works ...

[qMopey]

Congrats! And two years later: yes, I use half edge

[gimymblert]

STill has to use half edge, a year ago after that failure, I made a converter of normal mesh to half mesh that suture UV and sharp seam by detecting duplicate points.

Now I can move to full convex hull, lets see how that pans out, i'm stubborn.

[gimymblert]

Extra note, I'm looking to see if there is simplification to be had, I really want all my point to be part of the hull, and they lie roughly on a sphere (center of quad is on sphere).

I wasted time with support mapping (for this project, still useful to know how to make a convex hull) because it get rid of internal point, all my point NEED to be part of the hull

[gimymblert]

Okay I have no idea what's up with conflict list with quickhull, everything is written in awful math jargon too. And apparently giftwrap is easier but's it's in jargon too. Jargon suck man. I'm stuck because of verbose bulls**t.

How do I manage conflict list? it doesn't make much sense to me.

Help?