Robert Grzeszczuk (rg)
Tue, 1 Jun 1999 12:50:51 -0700 (PDT)
polygonize() takes a set of tetrahedra, a set of bricks, and a set of sampling
planes to produce a set of sampling triangles. In the general case, the tetras
can span multiple bricks (e.g., typically, the whole cubic volume will be
represented by 5 tetras). So the basic algorithm will take each plane
equation, intersect it with one of the tetras (producing a triangle or
quadrangle), which is then clipped to each of the brick's boundaries (or
brick's clip box, to be exact). The intersection step can be done in variety
of ways (e.g., marching tetrahedra), or the two steps can be combined: the two
operations can be viewed as clipping against a convex intersection of ten (four
that define the tetrahedron and 6 that define the box) planes. The results are
placed in a voFaceSet[brickNumber][planeNumber] and are assumed to be a convex
polygon (10-gon at the most).
>From the above, you can draw several conclusions. For example, the polygonize
effort is proportional to the product of planesNumber*tetraNumber*brickNumber.
Several operations need to be repeated on per-frame basis.
A major improvement in this basic approach can be introduced if the tetraSet
satisfies some simple conditions. Namely, if we know (or can easily determine)
that the current tetrahedron is wholly contained within the clip box of a
single brick, we only have to do the first part (i.e., slicing a tetrahedron
with a plane). Not only, this is small portion of the work we had to do before
(clipping against 4 planes not 10), but also, we can adopt simpler, much more
efficient algorithms. For example, notice that when we sweep a plane through a
tetrahedron, in a non-degenerate case, there will be three spans created as the
planes crosses one of the four vertices: in the first and last span the polygon
of intersection is a triangle, in the middle a quad (see attached figure). All
polygons within a span are similar and can be obtained via interpolation. This
approach is ~25 times faster than the basic apporach.
In order to take advantage of the above apporach, voGeometryActions::optimize()
was provided in release 1.1. It will clip the input tetra set to brick
boundaries and simplify the result. This operation can be done as a
pre-processing stage for static models (i.e, models that do not move wrt to
brick boundaries). The version provided with 1.1 is not a general purpose
routine, but rather it uses a simple heuristic to detect the single most common
case (i.e, a set of tetras that cover the whole BrickSet) and tesselate each
brick into TetraSets that are fully contained. Future releases will extend
this functionality to cover the general case as well. So now, if you had a
cubic (i.e, 5 tetra) volume with four bricks, the new volume will have 4*5=20
tetras. Since there are 4 times tetras to process, and the routine is 25 times
faster, you're likely to see a speedup of 6x for your polygonization stage.
Hope that clears some of the things up a bit. Let me know.
-rg
On Jun 1, 2:46pm, Manfred Weiler wrote:
> Subject: How does polygonize work
>
> Can anyone give me some details about how
> the voGeometryActions::polygonize method works ?
>
> Manfred.
>-- End of excerpt from Manfred Weiler
This archive was generated by hypermail 2.0b2 on Mon Nov 01 1999 - 14:02:50 PST