> FractRacer:
> Here's a visualization of the goal & problem.
>
> I'm sure I must simply be doing something slightly wrong when I compute a vector
> to rotate around, or a normal value, or something.
> It all looks fine on paper - so it should work!   :D
>
> If the red torus is the rim of an ice cream cone, then the green sphere should
> sit in it perfectly, in full contact, like a scoop of ice cream.
>

>

I will take some times to see your code.
If I understand, the point D is not in the same plane as the triangle, 
the torus is - but I may be wrong - the equator of the sphere on which D 
is.

Lionel

-- 
Do not judge my words, judge my actions.

---

http://www.avast.com

Post a reply to this message

> I will take some times to see your code.
> If I understand, the point D is not in the same plane as the triangle,
> the torus is - but I may be wrong - the equator of the sphere on which D
> is.

Correct - D is NOT in the same plane of the triangle.  It is a point H units
away from the triangular plane.
#declare PointD  =  vtransform (Middle, transform {translate Normal*Height});

The center you are using, the "centroid"
#local TMC = Triangle_Mass_Center(Corner_A_1, Corner_A_2, Corner_A_3);
is not the center used for finding the tangent circle.

The "circumcenter"
#declare Middle =  Triangle_M_out (Corner_A_1, Corner_A_2, Corner_A_3);
is the one to use - it also happens to lie on the midpoint between Corner_A_1
and Corner_A_3, because it is is a right triangle, and so it bisects the
hypotenuse.

I think maybe the rotation vectors I'm using are incorrect, or the trigonometry
is off, but I cannot see how.   Hopefully I can do more to understand what is
wrong tonight.

Post a reply to this message

I've gotten this far - the only thing unknown or in error at this point is the
radius of the sphere.
A nice discussion with good diagrams, in any event.

http://www.verniana.org/volumes/02/HTML/SphericalGeometry.html

Post a reply to this message

http://www.answers.com/topic/tetrahedron

"If OABC forms a general tetrahedron with a vertex O as the origin and vectors
a, b and c represent the positions of the vertices A, B, and C with respect to
O, then ... the radius of the circumsphere is given by:

R = |pow(a,2) * |bxc| + pow(b,2) * |cxa| + pow(c,2) |axb| | / 12V
where:
6V = |a.(bxc)|

Circumcenter O = |pow(a,2) * |bxc| + pow(b,2) * |cxa| + pow(c,2) |axb| | / 2a *
(bxc)

If I knew more about Delaunay triangulation or Voronoi cells, this might help me
out:
http://wias-berlin.de/software/tetgen/1.5/doc/manual/manual002.html
"In ℝ3, the vertices of the Voronoi diagram are the circumcenters of the
tetrahedra of the Delaunay tetrahedralization."

Post a reply to this message

If I got your problem correctly:
1. you have 4 points: A,B,C,D, not coplanar, and not even aligned by
group of 3. (A,B,C,D define a non-degenerated tetrahedron)
2. you want to find the sphere whose surface includes all the points.

You need additional constraint on D, or the sphere does not exist.

Notice that A,B,C & D are exchangeable. The sphere hold the ABC circle,
but also the ABD, ACD and BCD circles.

The normal going through the centre of all circles meets at the center
of the sphere.

So, one possible solution to check if there is a solution is:
 1. compute the circle for ABC: Center K, normal N.
 2. compute the circle for ABD (or any of the two others): Center L,
normal M.
 3. compute the smallest distance W between (K,K+N) line and (L,L+M) line
 4. if W is not null, there is no intersection, hence no solution.
 5. if W is null, the intersection I is the center of the sphere, and
the radius is IA, IB, IC or ID.


-- 
IQ of crossposters with FU: 100 / (number of groups)
IQ of crossposters without FU: 100 / (1 + number of groups)
IQ of multiposters: 100 / ( (number of groups) * (number of groups))

Post a reply to this message

Just so I can learn some conversion of standard vector math notation, I turned
that all into (Corner_A_1 is already at the origin):

 #declare Vo = Corner_A_1;
 #declare Va = Corner_A_2;
 #declare Vb = Corner_A_3;
 #declare Vc = PointD;

 //  6V = |a.(bxc)|
 #declare V = vdot (Va, vcross (Vb, Vc) ) / 6;
 #debug concat ( "V = ", str (V, 3, 1), "\n")

 //  R = |pow(a,2) * |bxc| + pow(b,2) * |cxa| + pow(c,2) |axb| | / 12V

 #declare CircumRadius = vlength (
  pow(vlength (Va),2) * vcross (Vb, Vc) +
  pow(vlength (Vb),2) * vcross (Vc, Va) +
  pow(vlength (Vc),2) * vcross (Va, Vb)
  ) / (12 * V);
 #debug concat ( "CircumRadius = ", str (CircumRadius, 3, 1), "\n")

 //  O = |pow(a,2) * |bxc| + pow(b,2) * |cxa| + pow(c,2) |axb| | / 2a * (bxc)

 #declare PointO = vlength (
  pow(vlength (Va),2) * vcross (Vb, Vc) +
  pow(vlength (Vb),2) * vcross (Vc, Va) +
  pow(vlength (Vc),2) * vcross (Va, Vb)
  ) / (2 * vlength (Va) * vcross (Vb, Vc) );
 #debug concat("PointO = <", vstr(3, PointO, ", ", 0, 1), "> \n")

V and CircumRadius look plausible, PointO is somewhere under the plane at z =
AlphaCentauri.   :(


Le_Forgeron <jgr### [at] freefr> wrote:
> If I got your problem correctly:
> 1. you have 4 points: A,B,C,D, not coplanar, and not even aligned by
> group of 3. (A,B,C,D define a non-degenerated tetrahedron)
> 2. you want to find the sphere whose surface includes all the points.

Correct.

> You need additional constraint on D, or the sphere does not exist.

Right.  I define H, which is the height above the centroid of the triangle where
D exists.  (Within reason:) When H is small, D sits close to the triangle, and
the sphere is large.  When H gets larger, the radius of the sphere becomes
smaller.

> Notice that A,B,C & D are exchangeable. The sphere hold the ABC circle,
> but also the ABD, ACD and BCD circles.

Correct.

> The normal going through the centre of all circles meets at the center
> of the sphere.

I thought that might be true, but hadn't gotten around to a way of implementing
it.

> So, one possible solution to check if there is a solution is:
>  1. compute the circle for ABC: Center K, normal N.
>  2. compute the circle for ABD (or any of the two others): Center L,
> normal M.
>  3. compute the smallest distance W between (K,K+N) line and (L,L+M) line
>  4. if W is not null, there is no intersection, hence no solution.
>  5. if W is null, the intersection I is the center of the sphere, and
> the radius is IA, IB, IC or ID.

I see that 3 is the key.
I'm fuzzy on exactly how to do that.  I don't mind the exercise - I'm just not
that alert of a reader at the moment...   ;)
Can I define a plane that contains the original triangle's center and PointD and
then use trace along one of the lines to find the intersection?
I'm assuming that there's no "line" object to use for testing an intersection,
and rounding errors might cause a miss anyway....

I'll try the plane and then a tiny cylinder.

Thanks my friend.

Post a reply to this message

Am 08.08.2014 18:15, schrieb Le_Forgeron:
> If I got your problem correctly:
> 1. you have 4 points: A,B,C,D, not coplanar, and not even aligned by
> group of 3. (A,B,C,D define a non-degenerated tetrahedron)
> 2. you want to find the sphere whose surface includes all the points.
>
> You need additional constraint on D, or the sphere does not exist.

I don't think that's true: Constraint 1. is sufficient.

Every non-degenerate triangle has exactly one circumscribed circle, so 
obviously there exists exactly one circle touching ABC. Let O be that 
circle.

Let N be the rotational axis of O. If D is on N, Let P be an arbitrary 
plane trough N; otherwise, let P be the plane through D and N. Note that 
in either case both D and N are on P.

Note that P intersects O in two points; let these be E and F. Also note 
that D is not on the line EF, otherwise ABCD would be coplanar. Thus, 
DEF is a non-degenerate triangle, and itself has a circumscribed circle. 
Let Q be that circle.

Note that E and F have equal distance to N, thus N runs through the 
center of Q, so rotating Q about N defines a sphere. Let S be that 
sphere. Note that D lies on Q and hence on S; also note that E and F 
both lie on Q, and their rotation about N yields O, thus O lies on S. 
Note that ABC all lie on O, and therefore also on S.

=> ABCD all lie on S.

Finally note that if P if ambiguous, the case is entirely rotationally 
symmetric except for the positions of ABC, and thus S is the same for 
all possible choices of P.

=> S is unambiguous.

=> For any non-degenerate tetrahedron ABCD, there exists exactly one 
circumscribed sphere.

Post a reply to this message

> I don't think that's true: Constraint 1. is sufficient.

True in general, But the way I define what D _IS_, is that it is the
circumcenter of ABC offest in the normal direction by some distance H.
That way the whole system is parameterized so that for any triangle ABC, I can
vary how much of sphere S "pokes through" circle O.


> Every non-degenerate triangle has exactly one circumscribed circle, so
> obviously there exists exactly one circle touching ABC. Let O be that
> circle.
>
> Let N be the rotational axis of O. If D is on N, Let P be an arbitrary
> plane trough N; otherwise, let P be the plane through D and N. Note that
> in either case both D and N are on P.
>
> Note that P intersects O in two points; let these be E and F. Also note
> that D is not on the line EF, otherwise ABCD would be coplanar. Thus,
> DEF is a non-degenerate triangle, and itself has a circumscribed circle.
> Let Q be that circle.
>
> Note that E and F have equal distance to N, thus N runs through the
> center of Q, so rotating Q about N defines a sphere. Let S be that
> sphere. Note that D lies on Q and hence on S; also note that E and F
> both lie on Q, and their rotation about N yields O, thus O lies on S.
> Note that ABC all lie on O, and therefore also on S.
>
> => ABCD all lie on S.
>
> Finally note that if P if ambiguous, the case is entirely rotationally
> symmetric except for the positions of ABC, and thus S is the same for
> all possible choices of P.
>
> => S is unambiguous.
>
> => For any non-degenerate tetrahedron ABCD, there exists exactly one
> circumscribed sphere.

I did manage to follow all of that after 3 or 4 tries, and you are of course,
correct.   Oh, if only my mind still worked as clearly as yours.

After a few false starts, I got it all to work out and am cleaning up all of the
accumulated dross in the code.

I must say I was rather surprised how little information is readily available
(internet-wise) on practically accomplish this otherwise-simple task.

Post a reply to this message

OK,  Here's the rough draft.
I use a normal line for my trace function - a haven't implemented the plane yet
- I need to figure out a check for coincidence with the trace line.

It also doesn't calculate / plot the correct normal for triangle A-B-D, which is
weird (and p------ me off) because it uses the same F. Lohmueller macro as all
the other faces of the tetrahedron.   What.  The.  Heck.

--------------------------------------------------

#declare Corner_A_1 = <0, 4, -2>;
#declare Corner_A_2 = <4, 4, -2>;
#declare Corner_A_3 = <2, 8, -2>;
#declare H = 0.5;


//
##############################################################################################################
//  Circumscribe a sphere around a triangle and a 4th "tetrahedral point"
determined by Height
 #macro Circumscribed_Sphere (Corner_1, Corner_2, Corner_3, Height)
  #local MacroName = "Circumscribed_Sphere"
  #if (verbose = true)
   #debug concat("macro '", MacroName, "' called with arguments: ")
   #debug concat("<", vstr(3, Corner_1, ", ", 0, 1), ">, <", vstr(3, Corner_2,
", ", 0, 1), ">, <", vstr(3, Corner_3, ", ", 0, 1), ">, ", str(Height, 3, 3), "
\n")
  #end // end verbose debugging output
//  ################
  #local Markers = true; //  Display points and geometric construction lines

  #local SolidBlue    = texture {pigment {color rgb <0, 0, 1> } finish {ambient
0.6}};
  #local SolidRed     = texture {pigment {color rgb <1, 0, 0> } finish {ambient
0.6}};
  #local SolidYellow  = texture {pigment {color rgb <1, 1, 0> } finish {ambient
0.6}};
  #local SolidGreen  = texture {pigment {color rgb <0, 1, 0> } finish {ambient
0.6}};
  #local SolidGray  = texture {pigment {color rgb <0.5, 0.5, 0.5> } finish
{ambient 0.6}};

  #local Point_radius = 0.125;
  #local Line_radius  = 0.125/4;
  union{
   // POINT P / Middle
   #local Middle =  Triangle_M_out (Corner_1, Corner_2, Corner_3);
   #local Radius =  Triangle_R_out (Corner_1, Corner_2, Corner_3);
   #local Normal =  Triangle_Normal(Corner_1, Corner_2, Corner_3);
   #declare CC_Radius = vlength (Middle - Corner_1);
   #local PointD  =  vtransform (Middle, transform {translate Normal*Height});

   //  Tetrahedral faces
   #local Middle12D =  Triangle_M_out (Corner_1, Corner_2, PointD);
   #local Radius12D =  Triangle_R_out (Corner_1, Corner_2, PointD);
   #local Normal12D =  Triangle_Normal(Corner_1, Corner_2, PointD);

   #local Middle23D =  Triangle_M_out (PointD, Corner_2, Corner_3);
   #local Radius23D =  Triangle_R_out (PointD, Corner_2, Corner_3);
   #local Normal23D =  Triangle_Normal(PointD, Corner_2, Corner_3);
   #local Normal23DVector = vtransform (Middle23D, transform {translate
-Normal23D*10});

   #local Middle31D =  Triangle_M_out (Corner_1, PointD, Corner_3);
   #local Radius31D =  Triangle_R_out (Corner_1, PointD, Corner_3);
   #local Normal31D =  Triangle_Normal(Corner_1, PointD, Corner_3);

   #local Centerline  = vtransform (Middle, transform {translate -Normal*10});
   #local Centertrace = object {cylinder {PointD, Centerline, 0.01} }

   #declare CS_Center = trace (Centertrace, Middle23D, -Normal23D );
   #declare CS_Radius = vlength (PointD - CS_Center);

   #if (Markers = true)
    sphere {Corner_A_1, Point_radius    texture {SolidBlue} }
    object {LabelPoint (Corner_1, "A", 0.5)   texture {SolidRed}  }
    sphere {Corner_A_2, Point_radius    texture {SolidBlue} }
    object {LabelPoint (Corner_2, "B", 0.5)   texture {SolidRed}  }
    sphere {Corner_A_3, Point_radius    texture {SolidBlue} }
    object {LabelPoint (Corner_3, "C", 0.5)   texture {SolidRed}  }
    // circumcenter of triangle ABC
    sphere {Middle, Point_radius     texture {SolidBlue} }
    object {LabelPoint (Middle, "m", 0.5)    texture {SolidBlue} }
    //  Circumcircle of original triangle
    torus {  CC_Radius, Line_radius rotate x*90 translate Middle texture
{SolidBlue} no_shadow}
    // new tetrahedral point
    sphere {PointD, Point_radius texture {SolidGray} }
    object {LabelPoint (PointD, "D", 0.5) texture {SolidGray} translate
Normal*Height}

    object {Centertrace texture {SolidGreen} } // extended normal of original
triangle

    object {PointMarker (Middle12D, Line_radius) texture {SolidGray} }
    torus  {Radius12D, Line_radius Reorient_Trans(y, Normal12D) translate
Middle12D texture {SolidGray} }
    object {Distance_Marker(Middle12D, vtransform (Middle12D, transform
{translate -Normal12D*CS_Radius}), Line_radius) texture {SolidGreen}}

    object {PointMarker (Middle23D, Line_radius) texture {SolidGray} }
    torus  {Radius23D, Line_radius Reorient_Trans(y, Normal23D) translate
Middle23D texture {SolidGray} }
    object {Distance_Marker(Middle23D, Normal23DVector, 0.025) texture
{SolidGreen}}

    object {PointMarker (Middle31D, Line_radius) texture {SolidGray} }
    torus  {Radius31D, Line_radius Reorient_Trans(y, Normal31D) translate
Middle31D texture {SolidGray} }
    object {Distance_Marker(Middle31D, vtransform (Middle31D, transform
{translate -Normal31D*CS_Radius}), Line_radius) texture {SolidGreen}}

    object {Distance_Marker(Corner_1, Corner_2, Line_radius)  texture
{SolidBlue}}
    object {Distance_Marker(Corner_2, Corner_3, Line_radius)  texture
{SolidBlue}}
    object {Distance_Marker(Corner_3, Corner_1, Line_radius)  texture
{SolidBlue}}
    object {Distance_Marker(Corner_1, PointD, Line_radius)   texture
{SolidGray}}
    object {Distance_Marker(Corner_2, PointD, Line_radius)   texture
{SolidGray}}
    object {Distance_Marker(Corner_3, PointD, Line_radius)   texture
{SolidGray}}

    object {PointMarker (CS_Center, Line_radius) texture {SolidRed} }  //
Circumcenter of sphere
    object {LabelPoint (CS_Center, "Circumcenter", 0.5) texture {SolidGreen} }

   #end // end diagram markers

   sphere {CS_Center, CS_Radius}  //  THE ACTUAL SPHERE

  }  // end union
//  ################
  #if (verbose = true)
   #debug concat ("Sphere Circumcenter = <", vstr(3, CS_Center, ", ", 0, 1), ">
\n")
   #debug concat ("Sphere Circumradius = ", str (CS_Radius, 3, 1), "\n")
   #debug concat ("macro '", MacroName, "' finished. \n")
  #end // end verbose debugging output
 #end  //  end of macro
//
##############################################################################################################


Macro for PointMarkers:
//
##############################################################################################################
//  Plot an x-y-z point marker.
 #macro PointMarker (Point, Radius)
  #local MacroName = "PointMarker"
  #if (verbose = true)
   #debug concat("macro '", MacroName, "' called with arguments: ")
   #debug concat("<", vstr(3, Point, ", ", 0, 1), ">, ", str(Radius, 3, 3), "
\n")
  #end // end verbose debugging output
//  ################
   #local MarkerHeight = 0.25;
   union {
   cylinder { <Point.x-MarkerHeight, Point.y, Point.z>, <Point.x+MarkerHeight,
Point.y, Point.z>, Radius}
   cylinder { <Point.x, Point.y-MarkerHeight, Point.z>, <Point.x,
Point.y+MarkerHeight, Point.z>, Radius}
   cylinder { <Point.x, Point.y, Point.z-MarkerHeight>, <Point.x, Point.y,
Point.z+MarkerHeight>, Radius}
   }
//  ################
  #if (verbose = true)
   #debug concat("macro '", MacroName, "' finished. \n")
  #end // end verbose debugging output
 #end  //  end of macro
//
##############################################################################################################

Post a reply to this message

Strangely, when I switched to using a plane for my trace object, which has
NOTHING to do with the triangle normal, it "fixed itself".
Crazy.

I animated it and it looks quite nice for a first look at the WIP.
posted in povray.binaries.animations.

Questions, comments, an suggestions welcome.

Thanks so much for all the helpful input in getting this to work.

Post a reply to this message