| The reference in .1 refers to a different brand of computational
geometry (albiet a very interesting one). The book referred to
is probably the one by Preperata and Shamos, though Edelsbrunner
has been a prolific contributer to the field.
I'm pretty familiar with the current techniques; the problem while not
"trivial" is not extremely hard either. To the best of my knowledge,
no canned routines exist at present, because such code would depend
heavily on the data structures used elsewhere in the modeller.
The level of potential complexity in the intersection curve of even
a pair of bicubic patches is such that all known approaches are
basically heuristic. One has to make a tradeoff between reliability
and efficiency.
The approach which is commonly used, and that I recommend, is to
rely on the subdivision properties of surfaces represented in the
B-spline and Bezier bases. The surface is guaranteed to lie within
the convex hull of the control polygon that effects it, so a divide
and conquer technique can be used to identify overlapping bounding
boxes, down to a reasonable level of tolerance. Then, a curve marching
algorithm can be run to trace each branch of the intersection curve
in detail.
This technique is quite safe, in that the subdivision approach is
guaranteed not to miss any intersections, but it converges slowly;
hence the switch to a faster curve follower at some point. The curve
follower should employ some safeguards to avoid accidentally jumping to
any nearby curve branches. That's usually done by estimating the
rate of convergence of local power series expansions of the curve
(which are generated via simple recurrance relations), and altering the
stepsize accordingly.
The tolerance on the bounding box subdivision phase can be made fairly
robust by adapting it to how nearly parallel the intersecting surface
normals are, though this can miss some potential cases with very high
order surfaces.
For the simpler cases of plane/surface and curve/surface intersection
the same techniques apply but can be special cased for more efficiency.
Do you need general surface intersection or just planar cross-sections?
- Jim
|
|
Thanks for the information so far but,
I am not sure if general surface or planar cross section is required.
I am also not sure of the difference and would appreciate an explanation.
Let me describe the problem. We are trying to convert a 3D modeling
system over to a VAX platform. One of the functions the current
system has is the capability of performing a cut through a surface.
So if I have a cone displayed, I would have the capability of
generating 'x' surfaces cuts through the cone at a specified angle.
The problem comes in since they have used the CATIA 3D math libraries
to generate the surface cuts. They pass the data to the CATIA routines
in the proper format and then convert it back to their own format.
They have implemented it by creating a job and then submitting the
job as a background task. When the job completes the data is
transferred back to their system.
My understanding is that CATIA is 15th degree which they are then
converting to 3rd degree. What problems do you see in the reduced
degrees of equations?
Unfortunately CATIA is not available on our platforms. Therefore
I am in search of a set of equivalent routines or information about
the degree of difficulty of creating these routines, and the expertise
required to do them.
George Zenzerovich
Software Specialist
LIO
|