Thanks, Matt -- this is very helpful info. The brilliant kid developer we have working on this (a few years out of Stanford CS) went ahead and just built it in several hours night before last. It seems to work really well on splines; he's working on generalizing to surfaces next. Performance is pretty amazing on a fairly high-end GeForce GPU. 1M particles, all *inside* the cutoff distance, getting closest location on a curve, and pulling tangency and position data from there, runs at > 60fps.
On Mon, Mar 30, 2020 at 7:05 PM Matt Lind <speye...@hotmail.com> wrote: > 'Get closest Locations' is patent protected, so you won't be able to do > anything commercial from the algorithm as implemented (but you may be able > to find it's description at the patent office). > > I spoke with the author of that tool at great length a few years ago as I > had questions about certain behaviors (bugs). He said the patented part > of > importance is the acceleration structures, which is a tree to store > results > of the searches. The benefits come from making certain assumptions about > when the tree needs to be updated in order to avoid unnecessary > computation. > > Location finding on meshes is basic linear algebra. You can derive it > yourself using the following: > > - distance equation (Pythagorean) > - the plane equation > - point inside a triangle > - projections > - vector dot product (aka inner scalar product) > - vector cross product > - determinant > - linear transformations > - fundamental understanding of barycentric coordinates. > > For example, finding closest vertex is no more complicated than iterating > through all the vertices of the mesh and computing the Pythagorean > distance > (d = sqrt( x^2 + y^2 + z^2) ), then choosing the vertex with the smallest > value of d. If you want closest location, the computation is a bit more > involved, but same general principle. In either case, you need to make > sure > the origin of your search is in the same coordinate space as your mesh. > That's where linear transformations and projections come into play. > > Brute force techniques are accurate and easy to implement, but perform > slowly. That may be adequate for situations where performance is not > critical such as a pick session. However, If you want speed, you'll need > a > more intelligent method to search only the parts of the mesh which are > likely to produce the desired result. That can get complex really fast > depending on your situation. > > I can't speak too much about implementation on a GPU other than to say you > have to organize your data and algorithm to consider race conditions and > other usual issues of multi-threaded environments. > > Matt > > > > Date: Sun, 29 Mar 2020 21:41:31 -0400 > From: Ed Manning <etmth...@gmail.com> > Subject: anyone know how ICE "get closest location" actually works > under the hood? > To: "Softimage Users Mailing List." <softimage@listproc.autodesk.com> > > need to reverse-engineer it in c++ > > thanks! > > > > ------ > Softimage Mailing List. > To unsubscribe, send a mail to softimage-requ...@listproc.autodesk.com > with "unsubscribe" in the subject, and reply to confirm. >
------ Softimage Mailing List. To unsubscribe, send a mail to softimage-requ...@listproc.autodesk.com with "unsubscribe" in the subject, and reply to confirm.
