On Tue, Jul 10, 2012 at 9:52 AM, phoenix <284281...@qq.com> wrote: > I look a litter deeper into the marching algorithm on how to implement it, > and meet some difficulties. Even after reading several papers to find the > answer I want, I still cannot come out with a complete solution of the first > step, which is to calculate the starting point on the intersection curve > using curve-surface intersection!
Does this paper offer any possibilities for starting point detection? http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.2788 We would probably use bounding box tree intersection rather than bezier patch approximations, but the ideas may be useful. 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 > So this method may be really HARD, although it seems to have good results. > > Could someone please give your opinion on this two approaches? Or other good > suggestions? 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). 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. > And I looked into the openNURBS API used by BRL-CAD. It does have some > interfaces (functions), which is designed to use for calculating > curve-curve/curve-surface or even surface/surface intersections, but it does > not have an implementation, and says: "The working function is part of the > Rhino SDK." It means that we must implement it by ourselves? Yes. OpenNURBS is not fully functional, so those pieces that are specific to Rhino are stubbed in in OpenNURBS. 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, http://tom.cs.byu.edu/~tom/papers/bezclip.pdf http://tom.cs.byu.edu/~tom/papers/C3CIC.pdf http://tom.cs.byu.edu/~tom/papers/ibc.pdf > Besides, I found that there is some code in brep.cpp dealing with the ray > trace of NURBS objects. There are functions related to intersections, which > are used to intersect a ray with a NURBS object, so I think they can offer > some help in this surface-surface intersection project. But there isn't any > documentation nor comment explaining these functions, so could someone > please tell me briefly what they really do and how to use it? Thanks a lot. The functionality that exists has mostly to do with building 3D surface and 2D curve trees, which are used to obtain initial guesses for an iterative solving solution that "walks in" to find exact ray/surface intersection points. That code needs a fair bit of clean-up, optimization, etc. It is mostly "driven" by the rt_brep_shot routine, if I recall correctly, so that will give you an idea of how to do things like build a surface tree. Cheers, CY ------------------------------------------------------------------------------ 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
