CGAL users discussion list

> Basically i have 100 silhouette from 2d images and want to build 3D
> Polyhydron using Visual Hull. I am trying demo which given nef_3 package.

Hi Naresh,

I've been experimenting with ways of optimizing my usage of Nef3 recently,
and one thing to bear in mind is that the algorithms involved seem to be
oriented towards optimizing asymptotic performance with respect to the
size of the geometry involved in one boolean operation.

If you are doing multiple operations (for instance, an nary_union), you
start paying polynomial prices.

As a test, I strung up a bunch of simple shapes S1..Sn in a chain, where
each shape has about 100 triangles, and each shape intersects only the
neighboring two shapes (except S1 and Sn, which intersect only one other
shape).

Performing an iterative union, where I add each Sj to the completed shape
via +=, the union time for each shape creeps upwards at
slightly-larger-than-linear rate, which I suppose is to be expected. Note
that this implies, at the very least, quadratic time in n. The total union
time for n==23 (under debug) was about 300 seconds.

If instead I construct only two Nefs, one containing all geometry for Sn
with even-numbered n, and the other containing all geometry for Sn with
odd-numbered n, then I only have one union operation to do. Note that by
this construction there is no self-intersect in either Nef (also note that
the chain doesn't loop around and intersect itself). The total time for
this union was only 30 seconds under the same settings. Total nef
construction time was approximately the same in both approaches and
negligeable compared to union time.

So in conclusion, if you're doing a large number of operations, I think
you'll find that your running time using with a naive iterative approach
will start being dominated by the number of operations rather than the
size of the geometry. In my case, I am considering putting together a
preprocessing step where I use bounding shapes to construct a "potentially
intersecting input shape" graph, and use that to organize my geometry into
maximal non-self-intersecting subsets. Each subset will be built into a
single nef, thereby minimizing the number of operations I need to do.

This begs a questions from the Nef3 team: is there anything in the
overlay-mark-simplify processing model that prevents Nef3 from offering
nary operations, thereby (presumably) avoiding the polynomial overhead of
iterative binary operations?

Fred