"jceddy" <jce### [at] gmailcom> wrote:

> When I inverse-transform the test point, do a minimum distance vector to the
> original mesh data, then transform that direction vector back to take the
> length, the result is slightly off from the version where I keep a parallel
> version of the mesh data around that I recalculate by transforming all the
> vertices whenever the mesh's Trans changes.

What if instead of re-transforming the mesh data, you transform the reference
point to measure the length?
Then it's only ever one transform in either direction.

I'm only guessing, based on what I'm envisioning you doing...

Post a reply to this message

> What if instead of re-transforming the mesh data, you transform the reference
> point to measure the length?
> Then it's only ever one transform in either direction.
>

That is exactly what I tried, if I am understanding you.

I want to find the distance from point P to mesh M (which contains
vertex/triangle data as well as a transformation).

So I tried basically this:


P_inv = InverseTransformPoint(P, M->Trans)
N = NearestPoint(P_inv, M->Data)
V = N - P_inv  // get the vector from P_inv to N
V_trans = TransformDirection(V, M->Trans)

If(Inside(P, M))
  distance = -Length(V_trans)
Else
  distance = Length(V_trans)


....and the result was much worse than finding the distance from point P to mesh
M (which contains transformed vertex/triangle data), but doing this:


N = NearestPoint(P, TransformAllVertices(M->Data, M->Trans))
V = N - P

If(Inside(P, M))
  distance = -Length(V)
Else
  distance = Length(V)



I mean, obviously the second one looks cleaner, as well, but it hides all the
code required to make sure M->TransformedData is there to use.

Post a reply to this message

On 7/11/22 17:25, jceddy wrote:
>> What if instead of re-transforming the mesh data, you transform the reference
>> point to measure the length?
>> Then it's only ever one transform in either direction.
>>
> That is exactly what I tried, if I am understanding you.
> 
> I want to find the distance from point P to mesh M (which contains
> vertex/triangle data as well as a transformation).
> 
> So I tried basically this:
> 
> 
> P_inv = InverseTransformPoint(P, M->Trans)
> N = NearestPoint(P_inv, M->Data)
> V = N - P_inv  // get the vector from P_inv to N
> V_trans = TransformDirection(V, M->Trans)
> 
> If(Inside(P, M))
>    distance = -Length(V_trans)
> Else
>    distance = Length(V_trans)

FYI. A chance the following inside_vector issue in play.

"Leaving mesh inside_vector untouched on transforms."
https://github.com/POV-Ray/povray/pull/361

IIRC this closed / not merged pull was last Christoph's version over my 
original suggested fix on the developer mailing list. For reasons 
unknown to me it never got merged into the official code base. I got 
tired of re-basing branches on code updates and eventually closed it.

There is too - and also still - the issue that our documentation 
suggests an axis aligned inside vector. This an unfortunate suggestion 
given things like buildings are often axis aligned and any time the 
inside vector is very close to perpendicular to a face's normal, the 
mesh inside test becomes noisy.

Bill P.

Post a reply to this message

> FYI. A chance the following inside_vector issue in play.
>
> "Leaving mesh inside_vector untouched on transforms."
> https://github.com/POV-Ray/povray/pull/361
>

That merge request changes the inside_vector test to use MInvTransPoint instead
of MInvTransRay followed by a Normalize, which makes sense to me.

In the version where I don't transform the mesh vertex data, I am doing
MInvTransPoint to tranform the test point, computing the minimum distance Vector
from the transformed test point to the original mesh data, then using
MInvTransDirection to transform that Vector using the mesh's Trans, then using
the length of the transformed vector as the distance.

The result obtained this way is a lot worse.

I wonder if there are cases where it would actually get a *wrong* answer, not
just loss of precision...such as the case where the object is scaled
non-uniformly. I think you can come up with an easy example where this is the
case where a "fat" ellipse that has a larger diameter in the x/y plane is scaled
such that it has a larger diameter in the x/z plane. Looking at the point at the
center of the ellipse, the minimum distance direction vector would switch from
<1, 0, 0> to <0, 1, 0> (for example).

Post a reply to this message

Well, I think I have decided that doing nearest-vertex calculation using a
kd-tree is *not* the best way to implement this for meshes.

I've attached a file comparing my original simulated-annealing run (using a very
short simulated annealing period after a very short brute force), which does
simple ray sampling, to the version that does a nearest-neighbor vertex search
on the mesh data using a kd-tree, and then finds the nearest point on any
triangles using that vertex.

The upper image is the simulated annealing one, and the lower image is the
nearest-neighbor mesh one. You can see that the simulated annealing approach
results in better output.

*ALSO*, the simulated annealing approach runs more quickly...it completed in
less than 60% of the time of the other one.

I think I am going to put those code changes on the back-burner, after making
sure I store them away somewhere, and then go ahead with another option I was
thinking about: doing a simple gradient descent search from an initial candidate
guess.

Post a reply to this message

Attachments:
Download 'test_compare.png' (252 KB)

Preview of image 'test_compare.png'

> *ALSO*, the simulated annealing approach runs more quickly...it completed in
> less than 60% of the time of the other one.
>

So after some more testing, I think the issue might actually be that the nearest
point algorithm using the kd-tree approach might be yielding suboptimal results,
which is requiring the isosurface code to do more samples, which is what is
actually slowing it down.

Basically, each sample is faster, but it's doing a lot more samples.

Either there is a bug in my kd-tree implementation, or there is something
fundamentally incorrect with the approach. Will have to do some more testing to
narrow down which it is.

It also occurs to me that I should be able to *somehow* use the mesh's bounding
box tree to implement a fast closest point query. Or maybe a parallel bounding
sphere tree?

Post a reply to this message

> Either there is a bug in my kd-tree implementation, or there is something
> fundamentally incorrect with the approach. Will have to do some more testing to
> narrow down which it is.
>

Looks like the kd-tree is not always returning the nearest mesh vertex to the
test point. I create a test that compares the minimum distance found using
simulated annealing vs. the one found using the nearest-vertex test, and then
added some code to find the nearest vertex by using a brute-force check of *all*
the vertices in the mesh, which I run in the case the simulated-distance found a
better solution than the kd-tree nearest-vertex approach.

I fairly quickly ran into a case where kd-tree is not returning the correct
vertex, so now need to figure out why that is the case.

Post a reply to this message

hi,

"jceddy" <jce### [at] gmailcom> wrote:
> > Either there is a bug in my kd-tree implementation, ...
> ... using the nearest-vertex test, and then
> added some code to find the nearest vertex by using a brute-force check of *all*

thinking, re "nearest neighbour", perhaps the implementation that comes with the
GTS library "tools" may be of use?  written by Sunil Arya & David Mount, "ANN:
Approximate Nearest Neighbours" (though they spell it without the 'u' :-)), I
have a version from May 2005 installed; sorry, no ref link.


regards, jr.

Post a reply to this message

> thinking, re "nearest neighbour", perhaps the implementation that comes with the
> GTS library "tools" may be of use?  written by Sunil Arya & David Mount, "ANN:
> Approximate Nearest Neighbours" (though they spell it without the 'u' :-)), I
> have a version from May 2005 installed; sorry, no ref link.
>

I can compare their kd-tree implementation to the one I have and try to figure
out if I'm dealing with a bug there.

Or rather if it helps me track down the but that is definitely there.

For example, I have a test point:

<-0.35977653631284895, 1.2000000000000000, -0.31591251373961082>

My kd-tree is returning this point as the nearest vertex:

<-0.22430989146232605, 0.65443259477615356, -0.19062881171703339>

The distance from the test point is 0.575926

*BUT*, when I brute force it, I find this is the actual nearest vertex:

<0.34019410610198975, 0.44190537929534912, 0.36512014269828796>

And the distance to that one is only 0.350649

That kind of error can definitely throw everything off.

Post a reply to this message

hi,

"jceddy" <jce### [at] gmailcom> wrote:
> ...
> I can compare their kd-tree implementation to the one I have and try to figure
> out if I'm dealing with a bug there.
>
> Or rather if it helps me track down the but that is definitely there.
>
> For example, I have a test point:
>
> <-0.35977653631284895, 1.2000000000000000, -0.31591251373961082>

faces/triangles in GTS are made from edges, so, an extra "layer".  agree re bug
hunt, running your points through both implementations should provide useful
info.


regards, jr.

Post a reply to this message