'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 <[email protected]>
Subject: anyone know how ICE "get closest location" actually works
under the hood?
To: "Softimage Users Mailing List." <[email protected]>
need to reverse-engineer it in c++
thanks!
------
Softimage Mailing List.
To unsubscribe, send a mail to [email protected] with
"unsubscribe" in the subject, and reply to confirm.
