Xref: utzoo comp.graphics:13873 comp.sys.sgi:6276
Path: utzoo!attcan!uunet!wuarchive!cs.utexas.edu!sun-barr!lll-winken!unixhub!shelby!helens!baroque!jim
From: jim@baroque.Stanford.EDU (James Helman)
Newsgroups: comp.graphics,comp.sys.sgi
Subject: ALGORITHM References Wanted: tri mesh clipping
Message-ID: <JIM.90Oct14172452@baroque.Stanford.EDU>
Date: 15 Oct 90 00:24:52 GMT
Sender: news@helens.Stanford.EDU
Distribution: comp
Organization: Stanford University
Lines: 47

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