POV-Ray : Newsgroups : povray.advanced-users : Solve edge case: is point inside/on object Server Time
28 Mar 2024 05:40:09 EDT (-0400)
  Solve edge case: is point inside/on object (Message 1 to 6 of 6)  
From: ingo
Subject: Solve edge case: is point inside/on object
Date: 26 Dec 2018 07:52:54
Message: <XnsA9C48D36120BCseed7@news.povray.org>
While trying to add movement constraints to the FABRIK IK solvers I ran 
into trouble, best described by the scene with comments below (at least I 
hope so).

I'm looking for a solution that is 100% safe in detecting whether a point 
is outside an object. I want to count exactly on the surface as inside.

ingo

---%<------%<-------%<---

#version 3.7;
#include "rand.inc"

#global_settings{assumed_gamma 1.0 }
#default{pigment{rgb 1} finish{ ambient 0.2 diffuse 0.9 }} 
light_source{<1000,1000,-1000>, rgb 1}
camera{location <0,1.5,-2> look_at <0,0.5,0>}

// Create an ObjectOfConstraint. A bone should stay within this object
// The object is always enclosed within a unit sphere.
#declare C = object{
  intersection {
    sphere {0,1}
    cone{<0,0,0>,0,<0,1,0>,0.5}
  }
};


// To create the edge case:
// Creat a point A (green) somewhere on a unit sphere.

// inside but not seen as such, needs the oject to scaled up a bit
//#declare A = vrotate(<0,1,0>,<0,0,1>); 

//fails on all tries
// #declare A = vrotate(<0,1,0>,<0,0,-90>);
//ok on last trial
 #declare A = vrotate(<0,1,0>,<0,0,-90.01>);

//#declare Stream = seed(7);
//#declare A = VRand_On_Sphere(Stream);

// Create a TraceTarget (red), the 'centre piece' of our 
ObjectOfConstraint.
#declare TT = <0,1,0>;
// Now trace from A to TT. Normalise the found intersection point (yellow)
// so it will end up exactly on the rim of the sphere-cone intersection
// (cyan sphere). 
#declare Norm = <0,0,0>;
#declare Inter1 = trace(C, A, TT-A, Norm);
#debug "Trace A\n"
#debug concat("Norm : ", vstr(3,Norm,",",3,3),"\n")
#debug concat("Inter: ", vstr(3,Inter1,",",3,3),"\n")
#declare Np = vnormalize(Inter1);
#debug concat("NP : ", vstr(3,Np,",",3,3),"\n")

// Now we can't check whether NP is inside the ObjectOfConstraint,
// it is exactly on the surface, so neither in or out. Yet I'd like
// to count it as 'inside', so more testing.
#declare Inside = inside(C,Np);
#debug concat("\n===>> Inside : ",str(Inside,3,3),"\n\n")

#if(!Inside)
  // Lets scale the cone
  #declare C_s = object{C scale 1.0001} //object{C scale 2}
  #declare Inside = inside(C_s,Np);
  #debug concat("\n===>> Inside C_s: ",str(Inside,3,3),"\n\n")
  // No result as Np stays exactly on the surface, uncomment C_s below.
  // Cannot change te radius of the cone a bit as the ObjectOfConstraint
  // can be something else than a cone.
  
  // What can be done with trace?
  #declare Norm = <0,0,0>;
  #declare C = object{C}; //object{C scale 1.0001}; //object{C scale 
0.9999};
  #declare Inter2 = trace(C, TT, TT-Np, Norm);
  #debug "Trace NP 2 : \n"
  #debug concat("Norm : ", vstr(3,Norm,",",3,3),"\n")
  #debug concat("Inter2: ", vstr(3,Inter2,",",3,3),"\n")
  // Just a trace form Np to TT results in nothing, no hit
  // scale up a bit results in the intersection point being TT
  // scale down a bit results in the intersection point being close to Np 
  //
  // Is this always the case?
  //
  // Fiddling with the position of A has shown there are situations where
  // it does not work. Coincident surface like problems? Scaling should 
  // not matter as Np is and stays exactly on the surface as seen with the
  // inside test.
  
  // Trace in opposite direction: nope
  #declare Inter3 = trace(C, Np, Np-TT, Norm);
  #debug "\nTrace NP 3 : \n"
  #debug concat("Norm : ", vstr(3,Norm,",",3,3),"\n")
  #debug concat("Inter3: ", vstr(3,Inter3,",",3,3),"\n")
  
  
  // Lets trace from a slightly different position. Extend TT to Np a bit.
  // The resulting intersection should be equal to Np
  
  #local NPn = Np+(vnormalize((Np-TT))*0.1);
  sphere {NPn 0.031}
  #declare Inter4 = trace(C, NPn, TT-NPn, Norm);
  #debug "\nTrace NPn : \n"
  #debug concat("Norm : ", vstr(3,Norm,",",3,3),"\n")
  #debug concat("Inter4: ", vstr(3,Inter4,",",3,3),"\n")
  // No result??? Because it exactly hits the rim???
  
  // Trace in opposite direction?
  #declare Inter5 = trace(C, TT, NPn-TT, Norm);
  #debug "\nTrace NPn : \n"
  #debug concat("Norm : ", vstr(3,Norm,",",3,3),"\n")
  #debug concat("Inter5: ", vstr(3,Inter5,",",3,3),"\n")
  // Seems to work ...? Not!
  
  object {C pigment {rgbf 0.6}}
  //object {C_s pigment {rgbf 0.9}}
  sphere {A 0.03 pigment{rgb y}}
  sphere {TT 0.03 pigment{rgb x}}
  sphere {Inter1 0.031 pigment{rgb x+y}}
  sphere {Inter2 0.031 pigment{rgb x+y}}
  sphere {Inter3 0.031 pigment{rgb x+y}}
  sphere {Inter4 0.031 pigment{rgb x+y}}
  sphere {Inter5 0.031 pigment{rgb x+y}}
  sphere {Np 0.03 pigment{rgb y+z}}
  cylinder {A, TT, 0.02}
  cylinder {Np, TT, 0.02}
#end


Post a reply to this message

From: jr
Subject: Re: Solve edge case: is point inside/on object
Date: 26 Dec 2018 09:00:01
Message: <web.5c23888fb6169bfa48892b50@news.povray.org>
hi,

ingo <ing### [at] tagpovrayorg> wrote:
> I'm looking for a solution that is 100% safe in detecting whether a point
> is outside an object. I want to count exactly on the surface as inside.

I probably completely misunderstood, or you will have have considered and
discarded the following already:

to see whether the red sphere is outside, when/where you get the NP on the
surface, slide the sphere along the perpendicular (to surface) by a small amount
and retest.  what have I overlooked?


regards, jr.


Post a reply to this message

From: ingo
Subject: Re: Solve edge case: is point inside/on object
Date: 26 Dec 2018 09:13:30
Message: <XnsA9C49AE1123ECseed7@news.povray.org>
in news:web.5c23888fb6169bfa48892b50@news.povray.org jr wrote:

Part of the solution to the problem is not creating part of the problem 
in the first place. 

While having my afternoon walk to the groceries I thought, what if I 
don't intersect with the sphere. All computations are done on or within 
the unit sphere, that automatically gives me an implicit intersection.

If I only deal with the cone I get rid of the "rim" problem and the 
method with tracing through the point to be tested will always work. 
Trace through the point and compare the intersection with the point, if 
they are equal the point is on the surface and I count it as in.

Also inside testing will be easier as points on the spherical part of 
the intersection are now inside the cone instead of on the surface.

> what have I overlooked?

The red sphere is not the problem, its the cyan one you don't see. To 
see it comment out the yellow 'Inter' spheres.

I guess I've not explained the problem well, it's rather complex and 
needs quite a few steps.

Thanks,

ingo


Post a reply to this message

From: ingo
Subject: Re: Solve edge case: is point inside/on object
Date: 26 Dec 2018 11:19:44
Message: <XnsA9C4B04878A0seed7@news.povray.org>
in news:XnsA9C49AE1123ECseed7@news.povray.org ingo wrote:

> don't intersect with the sphere

looks less complex now, works for simple objects


#version 3.7;
#include "rand.inc"
#include "transforms.inc"

#global_settings{assumed_gamma 1.0 }
#default{pigment{rgb 1} finish{ ambient 0.2 diffuse 0.9 }} 
light_source{<1000,1000,-1000>, rgb 1}
camera{orthographic location <0,0.5,-2> look_at <0,0.5,0>}


#macro WhereOnObj(Obj, Point, TraceTarget)
  #if(VEq(Point, TraceTarget))
    #local Where = "on";
  #else
    // Simple test first
    #declare Inside = inside(Obj, Point);
    #if (Inside)
      #local Where = "inside";
    #else
      // Not inside but maybe on the surface of Obj.
      // Trace from extended Point to TraceTarget. 
      // If intersection == Point we're on the surface
      #local Norm = <0,0,0>;
      #local NewPoint = Point+(vnormalize((Point-TraceTarget))*0.1);
      #local Inter = trace(Obj, NewPoint, TraceTarget-NewPoint, Norm);
      #local Miss = VEq(Norm, <0,0,0>);
      #local OnSurface = VEq(Inter, Point);
      #if (OnSurface)
        #local Where = "on";
      #else
        #local Where = "outside";
      #end
      #debug concat("Miss  : ",str(Miss,0,0),"\n")
      #debug concat("Norm  : ",vstr(3,Norm,","3,3),"\n")
      #debug concat("Inter : ",vstr(3,Inter,",",3,3),"\n")
      #debug concat("OnSurface : ",str(OnSurface,0,0),"\n")
    #end
    #debug concat("Where : ",Where,"\n")
  #end
  #local ReturnObject = array mixed[2]{Point, Where};
  ReturnObject
#end


// Create an ObjectOfConstraint. A bone should stay within this object
// The object is always enclosed within a unit sphere.
#declare C = object{
    cone{<0,0,0>,0,<0,1,0>,0.5}
};

// Creat a point A (green) somewhere on a unit sphere.
#declare A = vrotate(<0,1,0>,<55,0,30>);
//#declare Stream = seed(7);
//#declare A = VRand_On_Sphere(Stream);

// Test where the point lies with regard to object C
#declare TT = <0,1,0>;
#declare Loc = WhereOnObj(C, A, TT);
#debug concat("\nThe Point ",vstr(3,Loc[0],",",3,3)," lies ",Loc[1]," 
the surface of the Object\n") 

#if(Loc[1] = "outside")
  #debug "project the point on the surface\n"
  #declare Norm = <0,0,0>;
  #declare Inter1 = trace(C, A, TT-A, Norm);
  #debug concat("Norm : ", vstr(3,Norm,",",3,3),"\n")
  #debug concat("Inter: ", vstr(3,Inter1,",",3,3),"\n")
  #declare Np = vnormalize(Inter1);
  #debug concat("Np : ", vstr(3,Np,",",3,3),"\n\n")
  #declare Loc = WhereOnObj(C, Np, TT);
  #debug concat("\nThe Point ",vstr(3,Loc[0],",",3,3)," lies ",Loc[1]," 
the surface of the Object\n") 
#end


Post a reply to this message

From: jr
Subject: Re: Solve edge case: is point inside/on object
Date: 26 Dec 2018 12:25:03
Message: <web.5c23b923b6169bfa48892b50@news.povray.org>
hi,

ingo <ing### [at] tagpovrayorg> wrote:
> While having my afternoon walk to the groceries I thought ...
> looks less complex now, works for simple objects

fresh air + distraction.  nice.  :-)


regards, jr.


Post a reply to this message

From: ingo
Subject: Re: Solve edge case: is point inside/on object
Date: 26 Dec 2018 13:14:54
Message: <XnsA9C4C3CDF9FA6seed7@news.povray.org>
in news:web.5c23b923b6169bfa48892b50@news.povray.org jr wrote:

> fresh air + distraction.  nice.  :-)
> 

The rithm of walking ordends the messy brain. A big rocking horse in the 
garden would be ideal ;)

ingo


Post a reply to this message

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.