On Jul 10, 2012, at 2:31 PM, Clifford Yapp wrote: > 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! > > We would probably use bounding box tree intersection rather than > bezier patch approximations, but the ideas may be useful.
I'd strongly second that notion. Avoid converting to bezier patches or other similar translation forms at all costs. That was the old/original approach -- and one for which we have another failed implementation already, see the bspline primitive. The algorithms sound reasonable but they simply inject too much complexity and numerical instability with the translation (simply due to floating point). Moreover, research from 2006 paved the way demonstrating that you can directly evaluate NURBS surfaces (on modern hardware where cache coherency is king) just as fast or faster than you can chopping them up into bezier surfaces. Minimizing your quantity of data and data transfers on the CPU are simply more important. > 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. That sounds like a stellar approach. Would even be worth refactoring the existing bounding box subdivision code so that it's reused/reusable by both. >> 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? Fun eh? They ripped out some of the best parts. It's still a great framework and kudos to them for releasing what they did as open source. It saved us a couple years of development and we wouldn't have likely ended up with an API nearly as clean and organized. A good starting point would be to start by attempting to implement the guts for one of those empty functions, probably picking the lowest one first like curve/curve intersections. Then build up to the more complex cases using your lower routines where it makes sense. For example, once you find curve/curve, implementing curve/surface still involves a bunch of curve/curve tests along with the surface itself. >> 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. That is unfortunate that things aren't better documented, but most of the guys that worked on that code are on this mailing list so you can certainly ask questions here. I find it VERY helpful to clean up code and add comments when I go through understanding existing code. Feel free to do that to any code in BRL-CAD, especially the undocumented portions of the brep/nurbs code. Yet another publishable paper... Cheers! Sean ------------------------------------------------------------------------------ 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
