I've implemented a Minimum Distance algorithm that estimates the minimum
distance from any point and the surface of an object.

The reason I implemented it is so that I could use it inside an "internal"
function that I can then use in the definition of (for example) and isosurface.

The algorithm does a really short "brute force", checking vectors in a bunch of
directions from the point, and finding the shortest distance in any of those
directions (if there is actually a "hit" in any of those directions), in order
to get an initial estimate, then uses simulated annealing to improve the
estimate.

I have a few questions that are really specific to the development team:

Is there already functionality implementing a minimum distance to an arbitrary
object that I missed? I looked for one, but haven't actually asked directly.

Is this something that could work its way back into the povray code? I was
thinking that I would add a class to implement the simulated annealing in a
general way, a minimum distance implementation, and "internal" function to call
it from POV STL, and then probably a minimum distance pattern that would work
similar to the existing object pattern, except it wouldn't have sharp edges at
the object boundary. Where would be the preferred place to stick the simulated
annealing class? Is that the kind of thing that would go under Core/Math?

I am still playing with it a bit, but am thinking that if it might be useful for
other folks, I should do it "right" so I can submit it over on github.

I've included an attachment showing some of the testing I have been doing while
using the function to define an isosurface. In the two images, the object in the
center is just an object rendered directly, on the left is the object rendered
as an isosurface using a pigment pattern as the defining function (of course it
is terrible, due to the infinite gradient at the object surface), and on the
right the the object rendered as an isosurface using the minimum distance
function with a very short annealing period (BTW, the function flips the sign to
negative for points inside the object, so you have a clean 0.0 threshold at the
surface of the object).

Post a reply to this message

Attachments:
Download 'test_both.png' (118 KB)

Preview of image 'test_both.png'

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

> Is there already functionality implementing a minimum distance to an arbitrary
> object that I missed? I looked for one, but haven't actually asked directly.

I don't believe there is - accessible from the SDL, anyway.  I know that in the
past, people have asked about ways to make pigment patterns based on the
distance of an object from the camera.
Can't find those threads at the moment...

> I am still playing with it a bit, but am thinking that if it might be useful for
> other folks, I should do it "right" so I can submit it over on github.

You are correct - it would be a useful thing to have.

>on the
> right the the object rendered as an isosurface using the minimum distance
> function with a very short annealing period (BTW, the function flips the sign to
> negative for points inside the object, so you have a clean 0.0 threshold at the
> surface of the object).

So, I'm curious, and confused.
This sounds a lot like ray-marching, mixed with signed distance functions.
And how are you taking an algorithm and having that work with a function {} ?


I don't know what you're exactly doing, or the details of how simulated
annealing work, but I'd likely approach this (naively, wrongly) by using the
bounding box and trace (), and only scanning a grid of points corresponding to
the resolution of the render, arranged on a plane just behind the bounding box
and perpendicular to the camera to look_at vector.

And that sounds like a macro more than a proper function...


- Bill

Post a reply to this message

"Bald Eagle" <cre### [at] netscapenet> wrote:
> "jceddy" <jce### [at] gmailcom> wrote:
>
> > Is there already functionality implementing a minimum distance to an arbitrary
> > object that I missed? I looked for one, but haven't actually asked directly.
>
> I don't believe there is - accessible from the SDL, anyway.  I know that in the
> past, people have asked about ways to make pigment patterns based on the
> distance of an object from the camera.
> Can't find those threads at the moment...
>
> > I am still playing with it a bit, but am thinking that if it might be useful for
> > other folks, I should do it "right" so I can submit it over on github.
>
> You are correct - it would be a useful thing to have.
>
> >on the
> > right the the object rendered as an isosurface using the minimum distance
> > function with a very short annealing period (BTW, the function flips the sign to
> > negative for points inside the object, so you have a clean 0.0 threshold at the
> > surface of the object).
>
> So, I'm curious, and confused.
> This sounds a lot like ray-marching, mixed with signed distance functions.
> And how are you taking an algorithm and having that work with a function {} ?
>
>
> I don't know what you're exactly doing, or the details of how simulated
> annealing work, but I'd likely approach this (naively, wrongly) by using the
> bounding box and trace (), and only scanning a grid of points corresponding to
> the resolution of the render, arranged on a plane just behind the bounding box
> and perpendicular to the camera to look_at vector.
>
> And that sounds like a macro more than a proper function...
>
>
> - Bill

After cruising around the forums a bit, I realize that I probably should have
posted this in programming instead of general.

I actually changed the povray source code to add a new built-in function type,
and patter type to call directly. The implementation is in the C++ source and
just exposed to SDL via a couple of new parser directives.

On my phone ATM, so will probably put something over in programming later
(unless there is a way for a forum admin to just move this thread or something).

I'm currently experimenting with some other options besides simulated annealing
for improving the initial estimate...simulated annealing is good for general
purpose because it helps avoid finding locally optimal solutions when it is not
the globally optimal one. For a lot of purposes though, a quick simple march of
rays could be good and fast enough, or even doing what I am doing now and then
just a simple gradient descent around the initial estimate to find the nearest
locally optimal solution.

It could be that a minimum_distance implementation could come with a few options
to allow the user to choose between different methods to balance
quality/performance and pick what works best with what they are doing.

Post a reply to this message

On 7/6/22 21:32, jceddy wrote:
> I actually changed the povray source code to add a new built-in function type,
> and patter type to call directly. The implementation is in the C++ source and
> just exposed to SDL via a couple of new parser directives.
> 
> On my phone ATM, so will probably put something over in programming later
> (unless there is a way for a forum admin to just move this thread or something).

So... I think you are saying you've added a new f_mindist() function 
with the appropriate hook in functions.inc - or a stand alone hook in 
the SDL? And also a new pattern calling the same mindist code?

I have an interest in the former work more than the latter as have on my 
wish list to expose an f_trace() capability in my povr branch play which 
is roughly equivalent to the SDL's trace() function. I'd like to see how 
you handled the internal code hooks for tracing, inside tests (surface 
handling?) and pointers to the objects to trace.

Official development is stalled again since mid 2021, so while a pull 
request would be one handy way I could look at your code, it's unlikely 
to be acted on any time soon - in any 'official' capacity.

---

Random thoughts
---------------

Over the years there has been a fair bit of play with "proximity 
patterns." The work breaking into two approaches. One sampling by 
tracing rays and the other by sampling density via inside/out shape 
sampling(a) at various distances.

(a) - Inside testing gets slow for complex SDL built shapes because the 
inside test bypasses all the bounding search mechanisms used while 
tracing. I have an open question in my head as to whether trace() 
bypasses the bounding mechanisms too?

There is a proximity pattern in Jerome's hgpovray38 branch IIRC. Long on 
my list to look over his implementation, but, I've never gotten to it...

There is in all v3.8 branches a potential pattern hook for all shapes. 
Today it's implemented only for blobs(b) and the isosurface(b1) itself. 
Extending it to other simple shapes like spheres would be easy, but it's 
not been done. I think because it's hard to see the benefit when you can 
represent simpler shapes directly with functions for isosurfaces and 
these simpler functions can be used as patterns already. Using 
'patterns' in isosurface functions comes with significant overhead - and 
in the official POV-Ray releases there are bugs and usage issues too.

(b) - There are continuity issues with the blob implementation itself 
which handicaps blob potential pattern use (blob use itself in fact).

(b1) I removed the capability to use this potential pattern with 
isosurfaces in my povr branch because working with the incoming 
isosurface functions directly will always be better. Further, supporting 
the isosurface potential pattern introduced new keywords and overhead 
for all isosurfaces. I felt it not worth the added complexity or run 
time cost.

Truly knowing 'the' mindist for all 3D shapes is likely impossible to 
any reasonable cost(c). This of course says nothing about whether a 
mindist functionality is useful - a somewhat fuzzy one would be.

(c) - So long as 2D the internal point list representations are 
standardized/cleaned this can be done by various direct algorithms - as 
happens in VLSI design rule checking tooling. New distance functions to 
linear segments represented by point lists could be useful - especially 
if the point list can be pre-processed for fast mindist determinations 
after parsing. For small numbers of segments this can be done in any 
recent POV-Ray release. I've played too with DF3 based methods for large 
numbers of 'walls' (maze images from some years back) but it's a clunky 
approach.

Anyhow, I'll stop rambling.

I'm interested in what your trying for possible use/adaptation with 
stuff I'm trying. :-)

Bill P.

Post a reply to this message

> So... I think you are saying you've added a new f_mindist() function
> with the appropriate hook in functions.inc - or a stand alone hook in
> the SDL? And also a new pattern calling the same mindist code?

I actually implemented it as a "special" function, the way the pattern function
is implemented. So in the scene it looks like:

#declare fn = function { minimum_distance { ObjectIdentifier } };

> I have an interest in the former work more than the latter as have on my
> wish list to expose an f_trace() capability in my povr branch play which
> is roughly equivalent to the SDL's trace() function. I'd like to see how
> you handled the internal code hooks for tracing, inside tests (surface
> handling?) and pointers to the objects to trace.

I'm sure you could do a trace function similar to the way I did the
minimum_distance one. I am currently working on learning the parser a bit better
so I can more easily come up with a general set of arguments. I was thinking I'd
like to be able to do something like:

#declare fn = function {
  minimum_distance {
    ObjectIdentifier
    method brute_force
    quality 2
  }
}

or similar, and then possible implement brute_force, simulated_annealing, and
gradient_descent methods with appropriate arguments

> Official development is stalled again since mid 2021, so while a pull
> request would be one handy way I could look at your code, it's unlikely
> to be acted on any time soon - in any 'official' capacity.

I had seen that development had been done as recently as 2021, which gave me
hope that it was moving forward again! XD

I have been using POV long enough that I am used to the punctuated equilibrium
model of development. This is the second time I had tried to look into the
source, and the previous time was I believe before the C++ implementation (there
was a before C++ time, right? I'm not just imagining it?) and I had no idea what
was going on. I am having a lot more success navigating it now.

> There is in all v3.8 branches a potential pattern hook for all shapes.
> Today it's implemented only for blobs(b) and the isosurface(b1) itself.
> Extending it to other simple shapes like spheres would be easy, but it's
> not been done. I think because it's hard to see the benefit when you can
> represent simpler shapes directly with functions for isosurfaces and
> these simpler functions can be used as patterns already. Using
> 'patterns' in isosurface functions comes with significant overhead - and
> in the official POV-Ray releases there are bugs and usage issues too.

I actually did my first pass at this implementation by creating a
minumum_distance pattern, and then using that inside a function. As you allude
to here, that was not satisfactory...my code is still messy, though, and I have
"helper" functions in the pattern class that I am calling from the built-in
function. I need to clean all that up, but will probably work on that today and
push it up to my fork in github.

One thing I am curious about, that I haven't dug into yet, is if I can get more
information about the object being passed to the function and possible enable
performance improvements based on that. I started down this path because I have
a mesh object I am working with that I want this functionality for...in the case
where the "top level" object is a mesh, and I could get access to the mesh data,
I have a feeling I could improved this quite a bit for that specific use case.

> Truly knowing 'the' mindist for all 3D shapes is likely impossible to
> any reasonable cost(c). This of course says nothing about whether a
> mindist functionality is useful - a somewhat fuzzy one would be.

Yes, the performance of finding the minimum_distance with *very* good precision
slows things down tremendously. Been doing a lot of testing, though, and it
seems that in a lot of cases you can get a "good enough" solution without it
being *too* painful (of course that is subjective).

For a bunch of objects I've been testing on, just shooting rays out uniformly
45-degrees in polar coordinates (so like 26 ray samples) gets you nearly as good
a solution as a "smarter" method that might still end up taking longer to get
you like a .01% improvement in reality.

> I'm interested in what your trying for possible use/adaptation with
> stuff I'm trying. :-)

I'll work on this more today, and be back later with a link to my github fork.

Post a reply to this message

> I'll work on this more today, and be back later with a link to my github fork.

My fork is over here: https://github.com/jceddy/povray

If you search for "minimum" you are going to find most of my changes.

You can create a minimum distance function with:

#declare fn = function { minimum_distance { object } };

The minimum distance pattern allows a little more control over the simulated
annealing step, but I am currently working on additional changes to expose all
of the relevant tweakable parameters.

At any rate, if you take a look at how I ma using Find_Intersection in the
MinimumDistanceSolver class, that is basically the core trace() functionality
that you had mentioned you are interested in exposing via a function.

Post a reply to this message

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

> One thing I am curious about, that I haven't dug into yet, is if I can get more
> information about the object being passed to the function and possible enable
> performance improvements based on that. I started down this path because I have
> a mesh object I am working with that I want this functionality for...in the case
> where the "top level" object is a mesh, and I could get access to the mesh data,
> I have a feeling I could improved this quite a bit for that specific use case.

So, first off, this is very interesting, and exciting, that you have C++
development experience, and seem to understand enough to be able to write your
own source code function and plug it into POV-Ray.

I've been interested in doing that ever since I read about Leigh Orf's work on
weather data and super cells.

Several of us have bounced around the idea of having the ability to work with
convex hulls and point-clouds, and this seems to be very closely related to
that.

The idea I had was to have a POV-Ray object that would be simply a set of 3D
vectors, or points.  The advantage being that one could apply things like matrix
transforms to the data without having to loop through all the points in SDL,
which would be very slow in comparison to a source code subroutine.

So, I'm thinking that for your mesh, you would have a set of vertices - so why
not treat those as a point cloud?

Then you could have a tool to just find the minimum Euclidian distance between
the camera and all of the points in the cloud.  I ... feel ... there's some way
to optimize that so you don't have to check every single point. (?)

Then maybe there's a way to generate a true mesh object from the point cloud
object - which would be useful for folks who would like to take a bunch of
points and make a mesh out of its convex hull.

I'm light on details, and fast and loose with mostly everything, because I'm
pretty sure you already understand what I'm suggesting, and have your own ideas
about how best to approach all of this.


Finally, It would be great if you could provide a few posts detailing your
thought processes and some of the pertinent details about how to go about
writing on'es own function and getting POV-Ray to recognize and use it as a
built-in function.  That would greatly help anyone who has enough programming
experience to do so, but doesn't have the time to invest in tracking down all of
the details on the learning curve of doing that for POV-Ray - it's not like any
of that is really documented anywhere, and Dr. Orf's explanation, although good,
seemed like it was brief and geared to people who might already know how to do
so.


Thanks, and I hope you have a lot of success with your project!

- Bill

Post a reply to this message

> So, I'm thinking that for your mesh, you would have a set of vertices - so why
> not treat those as a point cloud?
>
> Then you could have a tool to just find the minimum Euclidian distance between
> the camera and all of the points in the cloud.  I ... feel ... there's some way
> to optimize that so you don't have to check every single point. (?)
>

In my case I already have a mesh. I'm the case of a simple mesh object there is
a straightforward way of computing minimum distance, but it would be slow unless
you do some fancy preprocessing to partition the vertices/faces.

Either way, in the case of an arbitrary object defined in SDL, I have not
figured out if there is a way in C++ to be able to go "hey, this is a mesh!" and
then get access to the underlying data.



>
> Finally, It would be great if you could provide a few posts detailing your
> thought processes and some of the pertinent details about how to go about
> writing on'es own function and getting POV-Ray to recognize and use it as a
> built-in function.  That would greatly help anyone who has enough programming
> experience to do so, but doesn't have the time to invest in tracking down all of
> the details on the learning curve of doing that for POV-Ray - it's not like any
> of that is really documented anywhere, and Dr. Orf's explanation, although good,
> seemed like it was brief and geared to people who might already know how to do
> so.
>

Yeah, a "developer's guide to patching povray" would be great. 😁

I could possible post some details about how to add keywords and get them
processed, but it would only really be useful to folks that have a compiler and
know how to use it.

Post a reply to this message

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

> In my case I already have a mesh. I'm the case of a simple mesh object there is
> a straightforward way of computing minimum distance,

To quote my research advisor, editing my thesis, "Which is...?"   ;)

> but it would be slow unless
> you do some fancy preprocessing to partition the vertices/faces.
>
> Either way, in the case of an arbitrary object defined in SDL, I have not
> figured out if there is a way in C++ to be able to go "hey, this is a mesh!" and
> then get access to the underlying data.

Indeed.  I haven't looked too much at the parser and the tokenizing of things,
but I would imagine that every object defined in SDL would have to have some
unique identifier of one sort or another.  It would be great to discover what
that is, and have an SDL-accessible table of numbered objects and associated
attributes.

I really have no top-down overview of how everything happens in order to go from
the simplest of scenes to defining the final rgb values of a pixel in a render.
It would be great to make a flowchart, perhaps with one of those automated
software-analyzing packages...

I guess just start by looking at:
povray/source/core/shape/mesh.cpp

and see if anything pops out at you.

> Yeah, a "developer's guide to patching povray" would be great. 😁
>
> I could possible post some details about how to add keywords and get them
> processed, but it would only really be useful to folks that have a compiler and
> know how to use it.

There are a few of us who have compilers, being on linux machines, but I usually
need a bit of hand-holding to build pov-ray from scratch and install it.  ;)

I think it also comes down to a sort of chicken-and-egg thing, where people have
reason to use their compiler, so they don't know how, and so they don't do
anything with them.

I can kinda read _most_ of the source code, but there are certain notations and
other things going on that I'm still ignorant of, and therefore remain cryptic.
I've dabbled, and spent quite a while programming several arduino boards for
various different purposes.   Which is "C++".

Post a reply to this message

>
> Indeed.  I haven't looked too much at the parser and the tokenizing of things,
> but I would imagine that every object defined in SDL would have to have some
> unique identifier of one sort or another.  It would be great to discover what
> that is, and have an SDL-accessible table of numbered objects and associated
> attributes.
>
> I really have no top-down overview of how everything happens in order to go from
> the simplest of scenes to defining the final rgb values of a pixel in a render.
> It would be great to make a flowchart, perhaps with one of those automated
> software-analyzing packages...
>
> I guess just start by looking at:
> povray/source/core/shape/mesh.cpp
>
> and see if anything pops out at you

You can specify objects and object identifiers in SDL...there are ways to hook
into the parser so that you can get an "object pointer" when an object
definition of object identifier shows up in the scene. It may be that it's
possible given the object pointer to figure out that the top level object is a
mesh, and get the mesh data. I will definitely be looking into that at some
point. (My priority at the moment is cleaning up the code and implementing an
easy way to tweak calls to the minimum distance function easily in SDL).

It is unclear whether that helps with performance of a minimum distance
function, but one thing it *would* be useful for is testing, to evaluate how
accurate various methods are. Of course, I can also evaluate that stuff using
other methods, as well, since I know the mesh definition "offline" already.

>
> > Yeah, a "developer's guide to patching povray" would be great. 😁
> >
> > I could possible post some details about how to add keywords and get them
> > processed, but it would only really be useful to folks that have a compiler and
> > know how to use it.
>
> There are a few of us who have compilers, being on linux machines, but I usually
> need a bit of hand-holding to build pov-ray from scratch and install it.  ;)
>
> I think it also comes down to a sort of chicken-and-egg thing, where people have
> reason to use their compiler, so they don't know how, and so they don't do
> anything with them.
>
> I can kinda read _most_ of the source code, but there are certain notations and
> other things going on that I'm still ignorant of, and therefore remain cryptic.
> I've dabbled, and spent quite a while programming several arduino boards for
> various different purposes.   Which is "C++".

I could probably help anyone trying to patch/build/run on windows using visual
studio 2015, I don't know what wrinkles might be involves in doing it in Linux,
Mac, etc.

Post a reply to this message