jim@baroque.Stanford.EDU (James Helman) (10/15/90)
I'm looking for algorithms for clipping triangular meshes "on the fly" against several "arbitrary" clipping planes. Definitions: triangular mesh: A sequence of vertices where each vertex and the previous two define a new triangle "on the fly": While drawing. Retaining minimal information about what has already been drawn. Requiring no information about subsequent vertices to draw the clipped triangle corresponding to the current vertex. Solutions: A) INDEPENDENT TRIANGLE CLIPPING: Recursively clipping and subdividing independent triangles is straightforward and can be done on the fly. This could be used by reverting to triangles when clipped, but I'd rather stay with a mesh. B) SINGLE CLIPPING: Clipping an entire triangular mesh against one clipping plane can be done with a simple algorithm. But I don't want to be making multiple passes and storing intermediate meshes. C) DIRECTLY CLIPPING THE MESH ON THE FLY: I'm looking for algorithms analogous to (A) for triangular meshes. It's a simple question, if you don't think about it too much. So it should have a simple answer ;-). I figured out a reasonably clean algorithm which does (C). But it is not optimal, at least not in triangle count. I'm looking for a better way, i.e. one which generates fewer triangles and/or needs less retained history and/or is more elegant. I don't have references on any of these topics. (A) should be dusty history. And I'm sure (B) and (C) are covered somewhere. I'd appreciate references on *any* of them, but especially on (C). Some graphics hardware (e.g. SGI's VGX) handles multiple clipping planes. (If we had one, I wouldn't be asking these questions!) Does anyone know how SGI does it? Thanks, Jim Helman Department of Applied Physics Durand 012 Stanford University FAX: (415) 725-3377 (jim@KAOS.stanford.edu) Work: (415) 723-9127
bruceh@sgi.com (Bruce R. Holloway) (10/16/90)
In article <JIM.90Oct14172452@baroque.Stanford.EDU> jim@baroque.Stanford.EDU (James Helman) writes: > >I'm looking for algorithms for clipping triangular meshes "on the fly" >against several "arbitrary" clipping planes. > >Some graphics hardware (e.g. SGI's VGX) handles multiple clipping >planes. (If we had one, I wouldn't be asking these questions!) Does >anyone know how SGI does it? The VGX clipper knows nothing of meshes, only triangles. It inputs a triangle and outputs a whole number of triangles. Clipping a mesh could result in multiple disjoint meshes. As for clipping against arbitrary planes, this is done at the same time and in the same way as against the six canonical clipping planes. Regards, bruceh
jroth@allvax.dec.com (Jim Roth) (10/16/90)
In article <JIM.90Oct14172452@baroque.Stanford.EDU>, jim@baroque.Stanford.EDU (James Helman) writes... >I'm looking for algorithms for clipping triangular meshes "on the fly" >against several "arbitrary" clipping planes. If your goal is good performance, then note that most triangles in a mesh are either trivially accepted (lying entirely in a view volume) or trivially rejected (lying entirely to one side of some clipping plane.) Statistially, fairly few actually require detailed clipping. If your mesh comes in where each triangle shares a side with the previous one (like PHIGS+), then check and save the status of each new vertex with respect to all clip planes and only do clipping if the triangle requires more work. This is easily checked with boolean operations on "outcode" bits saved with each vertex. To do clipping, use Sutherland-Hodgeman clipping, as it is very efficient and can even be inlined as a set of macro expansions if only a few clipping planes are in use (this is impractical if you have lots of planes.) This yields a convex polygon, which you can triangulate again if your renderer requires it. - Jim