> We would probably use bounding box tree intersection rather than
> bezier patch approximations, but the ideas may be useful.
Today I go on reading papers on marching algorithms as well as using bounding
boxes, and read the existing code in BRL-CAD. Algorithms have been implemented
to create surface trees already (which contains a tree hierarchy of bounding
boxes), so I think it would be much easier to implement surface-surface
intersection in this way (compared to the marching algorithm). The first step
is to generate two surface trees and calculate the intersections of bounding
boxes with existing APIs, and then fitting an intersection curve using the
method describe in the paper below (Section 6.1):
http://kingkong.me.berkeley.edu/~adarsh/Papers/TVCG09.pdf
> One concern with the subdividsion approach alone is apparently
> performance - this paper offers a hybrid approach but unfortunately I
> don't see a copy online:
> http://www.sciencedirect.com/science/article/pii/0167839687900203
> Abstractly, the idea of some sort of "hybrid" approach appeals to me,
> since that's essentially what we do with our raytracing (use the
> bounding boxes to quickly narrow down to the regions of interest, then
> do the harder calculations).
Sorry I cannot find these paper on the Internet any way, so could you please
tell me briefly about this "hybrid" approach? Or send me a copy of this paper
(if you have an electronic version)?
> If we can narrow down potential intersection curves to a set of
> bounding boxes that bound near-planar sub-regions of the NURBS
> surface, we may be able to identify searching techniques within those
> local, well-behaved regions that would characterize them for us. If
> we go that route, the first step is to build routines that will
> "intelligently" identify that set of bounding boxes. Our existing
> surface trees probably have enough information, and you might be able
> to build two surface trees for the candidate surfaces and find the
> intersecting leaf bbox sets as a first step. Our surface tree design
> needs a re-think though, so feel free to implement your own version
> that suits the needs of this problem if the existing one isn't good
> enough.
The existing surface tree is really very useful after some tests on it. Thanks
a lot for the information you gave me. But I don't really understand what you
mean by "intelligently identify the bboxes". Do you mean using smart algorithms
to speed up the calculation of the intersections? (Do not use brute force
O(N^2) calculations, using the information in the hierarchy to reduce
calculation). I think getting the intersections of bounding boxes would not be
much a problem (but performance still needs to be cared about), and the next
step is to fitting an intersection NURBS curve, as discussed in the paper
above. Any suggestions?
> One possibility is to "build up" the missing functionality, starting
> from curve/curve - most of the papers seem to deal with Bezier curves,
> but perhaps those techniques would be adaptable to NURBS curves - for
> example,
Curve-curve intersections (as well as curve-surface intersections) can also be
calculated using sub-division algorithms (provided the curve-tree and
surface-tree). So my idea is to focus on the surface-surface intersections, but
once I need curve-curve or curve-surface intersections, I can add functions to
implement them, and call these functions.
Cheers!
Wu
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
BRL-CAD Developer mailing list
brlcad-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/brlcad-devel
