Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / General Programming / converting convex hulls to meshes Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
erkokite

May 11, 2005, 02:49 PM

Is there a simple way to convert convex hulls (like those used in quake 3 brushes) to a polygon mesh?

 
mentalcalculator

May 11, 2005, 03:30 PM

Voronoi Diagram + Delaunay Triangulation ? I'm not sure about this so don't take it too seriously :)

 
DonJuan

May 11, 2005, 03:57 PM

sure, for direct3d. if you know the vertices and faces, just use D3DXCreateMesh.

 
Wernaeh

May 11, 2005, 04:08 PM

Hi there =)

Depends on how you have got your convex hulls. If you just have some plane soup, build a large poly on each plane (large enough so that it spans the min/max of all plane intersection points). Then, test each of these polies against all planes they don't lie on. Cut off everything thats on the wrong side of these planes (usually the negative side).

This is similiar to automatically creating portal polygons from a non-leafy BSP tree.

Cheers,
- Wernaeh

 
goltrpoat

May 11, 2005, 04:38 PM

I had to do something similar at my last job, and ended up with the following. Note that this is not the simplest version, but at the time, I decided that it was the best combination of efficiency and numerical robustness I could come up with (the "make one huge poly for each plane and repeatedly clip it" version is prone to all sorts of numerical drift).

First of all, define the following data structure.

  1.  
  2. enum
  3. {
  4.    BACK = 1,
  5.    FRONT = 2
  6. };
  7.  
  8. struct Edge
  9. {
  10.    Vector3      O;              // line origin
  11.    Vector3      D;              // line direction
  12.  
  13.    int          iBounded;       // bitmask, see below
  14.    int          iPlane[2];      // generating plane indices
  15.    int          iPoly[2];       // adjacent polygons
  16.    int          iClipPlane[2];  // clipping plane indices
  17.    float        ClipDist[2];    // distance to last clipping plane
  18.    int          iVerts[2];      // vertex indices
  19.  
  20.    Edge() : iBounded(0) { }  
  21. };
  22.  


If the iBounded member is 0, then the edge is an infinite line. If it's BACK or FRONT, the edge is a ray (clipped either in front or in the back, respectively). If it's 3, the edge is a line segment. Edges start out unbounded (as intersections of planes). To ensure winding consistency, you have to maintain a winding convention, eg., "an edge is wound counterclockwise wrt first generating plane".

After that first step, you clip every edge to a plane. The inner loop is as follows:

  1.  
  2. if (edge has not been clipped)
  3. {
  4.    int whichSide = (edge_direction.Dot(plane_normal) < 0) ? FRONT : BACK;
  5.    iBounded |= whichSide
  6.    clip edge to plane
  7.    set the edge origin to the intersection point
  8.    set the clip distance to the plane's distance
  9.   set clip plane index to this plane
  10. }
  11. else if (edge has been clipped, but not from this side)
  12. {
  13.   clip this side, update edge structure, etc
  14. }
  15. else if (edge has been clipped from this side)
  16. {
  17.   if (this plane makes the edge smaller)
  18.   {
  19.       clip this side, update edge structure
  20.   }
  21. }
  22.  


At this point, it might be a good idea to add a verification step to catch malformed brushes (and bugs): every edge should be clipped from both sides, if not then something is broken.

The next step is to fill in the iVerts fields. An edge is defined by four planes: the two planes whose intersection defines the line, and the two planes which clip the line on both sides. Vertices are defined by three planes (both of the former, and one of the latter). We need to link together the edges which share vertices. To that end, create a vertex structure which holds a list of edges connected to it, and go through the edge list. If a given combination of three planes has a vertex entry, then use its index, otherwise create a new one.

At this point, we have a list of edges (with counterclockwise winding with respect to, say, the left hand face), and a way to get from one edge to the next. This makes it easy to reconstruct polys:

  1.  
  2. for_each (edge)
  3. {
  4.    if (edge->leftFace hasn't been created)
  5.   {
  6.      edge->leftFace = new Face
  7.      edge->leftFace->AddEdge(edge)
  8.      
  9.      for_each (adjacent edge that has the same left plane index as the
  10.                current one)
  11.      {
  12.         edge->leftFace->AddEdge(adjacent edge)
  13.         adjacent_edge->leftFace = edge->leftFace
  14.      }
  15.   }
  16.  
  17.   if (edge->rightFace hasn't been created)
  18.    {
  19.       ...
  20.    }
  21. }
  22.  


This results in a poly mesh. Triangulate using your favorite method.



-goltrpoat

EDIT: Forgot to mention this (writing from memory, haven't had to do this in a while). Obviously, not all edges generated in the first step are going to end up in the final mesh. In the second step, any edge that ends up with a negative length (i.e. the front cap is behind the back cap) is simply discarded.

 
goltrpoat

May 11, 2005, 05:27 PM

[doublepost deleted]

 
goltrpoat

May 11, 2005, 05:29 PM

Forgot another thing. If an edge is parallel to a plane, and its origin is in front of it, the edge should be discarded (a special case of the negative length edge test). This handles the case of, eg., an AABB with one edge moved slightly inwards (the edge generated by the non axis-aligned plane and the plane opposite to it won't get discarded without that test).

That should be it, I think.

-goltrpoat

 
This thread contains 7 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.