Board index » delphi » 3d programming

3d programming

Hi,

I have a problem with a program I am trying to write:

Does anyone know how to find the intersection of a line and plane
in simple x,y and z cartesian coordinates.  I have a model made
up of facets, each facet being defined by 4 points.  The working
envelope that this model is in, is then scanned from the bottom
to the top.  However I can't work out how to calculate the z
coordinate along the scan line that may intersect with a facet.

The scanning line is always horizontal and is defined with the
x and y coordinates remaining the same, with one end of the line
minus z and the other end positive z. As an example at what point
does the line whose start point is (54,46,-100) and whose end
point is (54,46,100) intersect with a plane facet defined by 4
points in a anti-clockwise direction point 1 (40,20,-70),
point 2 (40,60,-40), point 3 (120,60,-40) and point 4 (120,20,-70).

--
I must get round to writing myself a decent signature

 

Re:3d programming


In article <4f3od9$...@zeus.tcp.co.uk>, ag...@agale.tcp.co.uk (Aaron Gale)
wrote:

Quote
> Does anyone know how to find the intersection of a line and plane
> in simple x,y and z cartesian coordinates.  I have a model made
> up of facets, each facet being defined by 4 points.  The working
> envelope that this model is in, is then scanned from the bottom
> to the top.  However I can't work out how to calculate the z
> coordinate along the scan line that may intersect with a facet.

> The scanning line is always horizontal and is defined with the
> x and y coordinates remaining the same, with one end of the line
> minus z and the other end positive z. As an example at what point
> does the line whose start point is (54,46,-100) and whose end
> point is (54,46,100) intersect with a plane facet defined by 4
> points in a anti-clockwise direction point 1 (40,20,-70),
> point 2 (40,60,-40), point 3 (120,60,-40) and point 4 (120,20,-70).

You only need 3 points to define a plane.  Using these three points you
can calculate the equation for the plane by simulaneous equations.
ie using the first 3 points the equation using a form of z=mx+ny+b would be:

1.  -70 = 40m + 20n + b
2.  -40 = 40m + 60n + b
3.  -40 = 120m + 60n + b

Solving these gives m=0,n=0.75,b=-85.
If you had a more complicated line you could solve the intersection also
by the same method, however as all x & y values are the same, you can just
substitute the x & y in, which gives you the intersection at (54,46,-50.5)

--
James Derrick

Re:3d programming


Quote
ag...@agale.tcp.co.uk (Aaron Gale) wrote:
>Hi,
>I have a problem with a program I am trying to write:
>Does anyone know how to find the intersection of a line and plane
>in simple x,y and z cartesian coordinates.  I have a model made
>up of facets, each facet being defined by 4 points.  The working
>envelope that this model is in, is then scanned from the bottom
>to the top.  However I can't work out how to calculate the z
>coordinate along the scan line that may intersect with a facet.
>The scanning line is always horizontal and is defined with the
>x and y coordinates remaining the same, with one end of the line
>minus z and the other end positive z. As an example at what point
>does the line whose start point is (54,46,-100) and whose end
>point is (54,46,100) intersect with a plane facet defined by 4
>points in a anti-clockwise direction point 1 (40,20,-70),
>point 2 (40,60,-40), point 3 (120,60,-40) and point 4 (120,20,-70).
>--
>I must get round to writing myself a decent signature

A line can be described in 2 eq, in your case it's simple like
X=54; Y=46

A plane can be describet using one eq like  A*X+B*Y+C*Z=D
If (0,0,0) is part of the plane you will have to set D=0 in all other
cases you can those a constant value like 1.
Then you will need tre points from the plane that must not be in one
line. (You have a point more than you need to calculate this).

Then you must solve the tree eq to find A,B and C
A*X1+B*Y1+C*Z1=D
A*X2+B*Y2+C*Z2=D
A*X3+B*Y3+C*Z3=D

     D*Y2*Z3+ D*Y3*Z1+ D*Y1*Z2 - D*Y3*Z2- D*Y1*Z3- D*Y2*Z1    
A= -----------------------------------------------------------
    X1*Y2*Z3+X2*Y3*Z1+X3*Y1*Z2 -X1*Y3*Z2-X2*Y1*Z3-X3*Y2*Z1

    X1* D*Z3+X2* D*Z1+X3* D*Z2 -X1* D*Z2-X2* D*Z3-X3* D*Z1
B= -----------------------------------------------------------
    X1*Y2*Z3+X2*Y3*Z1+X3*Y1*Z2 -X1*Y3*Z2-X2*Y1*Z3-X3*Y2*Z1

    X1*Y2* D+X2*Y3* D+X3*Y1* D -X1*Y3* D-X2*Y1* D-X3*Y2* D
C= -----------------------------------------------------------
    X1*Y2*Z3+X2*Y3*Z1+X3*Y1*Z2 -X1*Y3*Z2-X2*Y1*Z3-X3*Y2*Z1

Last you insert the known x and y into the eq: A*X+B*Y+C*Z=D
and solving for the only unknown: Z

If the (0,0,0) is part of the plane this will not work as
X1*Y2*Z3+X2*Y3*Z1+X3*Y1*Z2 -X1*Y3*Z2-X2*Y1*Z3-X3*Y2*Z1=0

One way to solve this will be to move the cordinate-system.
I hope this will help you.

-Bjarne Laursen, Pyramide Data , Denmark

Re:3d programming


Quote
James Derrick wrote:

> In article <4f3od9$...@zeus.tcp.co.uk>, ag...@agale.tcp.co.uk (Aaron Gale)
> wrote:

> > Does anyone know how to find the intersection of a line and plane
> > in simple x,y and z cartesian coordinates.  I have a model made
> > up of facets, each facet being defined by 4 points.  The working
> > envelope that this model is in, is then scanned from the bottom
> > to the top.  However I can't work out how to calculate the z
> > coordinate along the scan line that may intersect with a facet.

> > The scanning line is always horizontal and is defined with the
> > x and y coordinates remaining the same, with one end of the line
> > minus z and the other end positive z. As an example at what point
> > does the line whose start point is (54,46,-100) and whose end
> > point is (54,46,100) intersect with a plane facet defined by 4
> > points in a anti-clockwise direction point 1 (40,20,-70),
> > point 2 (40,60,-40), point 3 (120,60,-40) and point 4 (120,20,-70).

> You only need 3 points to define a plane.  Using these three points you
> can calculate the equation for the plane by simulaneous equations.
> ie using the first 3 points the equation using a form of z=mx+ny+b would be:

> 1.  -70 = 40m + 20n + b
> 2.  -40 = 40m + 60n + b
> 3.  -40 = 120m + 60n + b

> Solving these gives m=0,n=0.75,b=-85.
> If you had a more complicated line you could solve the intersection also
> by the same method, however as all x & y values are the same, you can just
> substitute the x & y in, which gives you the intersection at (54,46,-50.5)

Actually, you only need 2 points to define a plane: a point on the plane and
a normal vector. If your line goes from P0 to P1, and Pt is a point on the
line, then the following equations hold:

    Pt = P0 + t(P1 - P0)    [NOTE: Pt, P1, and P0 are vectors, t is a scalar]

    t < 0 or t > 1 --> no intersection

If Pe is a point on the plane and N is the inside normal to the plane, then
the following equations hold:

    dot_product( (Pe - Pt), N ) = 0 --> Pt is at the intersection point
                                > 0 --> Pt is inside the plane
                                < 0 --> Pt is outside the plane

        dot_product( N, (Pe - P0) )
    t = ---------------------------
        dot_product( N, (P1 - P0) )

Once you find t, you can find Pt, which is your intersection point. Note that
the equation for t fails if ||N|| = 0 (the 0 vector is usually a bad choice
for a normal vector :-), if P1 = P0 (no line), or if the line between P1 and P0
is parallel to the plane to which you're clipping (no intersection).

Hope this helps
-Chris
--
        \\ || //
        \ .  . /
___.oo0_(__()__)__0oo.___

 www.cse.psu.edu/~cclark

Re:3d programming


I have a more difficult problem: How to find the rays connecting
two points, satisfying Snell's law at the interface(s) between the
points. Any hints? I could figure it out for a plane or a sphere,
but in the general case of say a tessellated triangularized
surface between the points?

Re:3d programming


Quote
sch...@sdp13dj.der.edf.fr (andreas schumm) wrote:

>I have a more difficult problem: How to find the rays connecting
>two points, satisfying Snell's law at the interface(s) between the
>points. Any hints? I could figure it out for a plane or a sphere,
>but in the general case of say a tessellated triangularized
>surface between the points?

This is a real pain - there's no quick and easy way.  As you say,
spheres are simple - hence you see them a lot in ray-traced drawings.
My suggestion is to consult a decent maths book.

Good luck,

ChrisR:

Re:3d programming


In article <3118310E....@psu.edu>, Christopher H. Clark <chc...@psu.edu> wrote:

Quote
>Actually, you only need 2 points to define a plane: a point on the plane and
>a normal vector.

Sorry to quibble, but...

   A VECTOR IS NOT A POINT!!!!

Now back to our regular program.

Jon

Re:3d programming


Quote
Jonathan Cohen wrote:

> In article <3118310E....@psu.edu>, Christopher H. Clark <chc...@psu.edu> wrote:
> >Actually, you only need 2 points to define a plane: a point on the plane and
> >a normal vector.

> Sorry to quibble, but...

>    A VECTOR IS NOT A POINT!!!!

> Now back to our regular program.

Points are vectors.

-Chris
--
        \\ || //
        \ .  . /
___.oo0_(__()__)__0oo.___

 www.cse.psu.edu/~cclark

Re:3d programming


In <311E38D7.7...@psu.edu> "Christopher H. Clark" <chc...@psu.edu>
writes:

Quote

>Jonathan Cohen wrote:

>> In article <3118310E....@psu.edu>, Christopher H. Clark
<chc...@psu.edu> wrote:
>> >Actually, you only need 2 points to define a plane: a point on the
plane and
>> >a normal vector.

>> Sorry to quibble, but...

>>    A VECTOR IS NOT A POINT!!!!

>> Now back to our regular program.

>Points are vectors.

But the reverse is not true.

    - John J. Karcher

Re:3d programming


Quote
Christopher H. Clark wrote:

> Jonathan Cohen wrote:

> > In article <3118310E....@psu.edu>, Christopher H. Clark <chc...@psu.edu> wrote:
> > >Actually, you only need 2 points to define a plane: a point on the plane and
> > >a normal vector.

> > Sorry to quibble, but...

> >    A VECTOR IS NOT A POINT!!!!

> > Now back to our regular program.

> Points are vectors.
> ^^^^^^^^^^^^^^^^^^

Sorry, but I must take offense here.  A point in Cartesian space has three
aspects [X,Y,Z].  A vector requires a direction, and depending on how sticky you
are, probably a length.  This implies 6 independent aspects.  Result;  A plane
requires 3 points.  Always.

Cheers

Re:3d programming


In article <311F9C84.3...@structure.chimie.usherb.ca>,
Paul Rowntree  <rownt...@structure.chimie.usherb.ca> wrote:

Quote
>Christopher H. Clark wrote:

>> Jonathan Cohen wrote:

>> > In article <3118310E....@psu.edu>, Christopher H. Clark <chc...@psu.edu> wrote:
>> > >Actually, you only need 2 points to define a plane: a point on the plane and
>> > >a normal vector.

>> > Sorry to quibble, but...

>> >    A VECTOR IS NOT A POINT!!!!

>> > Now back to our regular program.

>> Points are vectors.
>> ^^^^^^^^^^^^^^^^^^

>Sorry, but I must take offense here.  A point in Cartesian space has three
>aspects [X,Y,Z].  A vector requires a direction, and depending on how sticky you
>are, probably a length.  This implies 6 independent aspects.  Result;  A plane
>requires 3 points.  Always.

>Cheers

Note that while I objected to the original poster's terminology, the
fact remains that a six-tuple of numbers is enough to define a plane,
while three individual points require a nine-tuple of numbers to
represents.  Thus, the 3 points contain some information in addition to
what plane they define.

So... if you want to describe a plane using points, it requires 3
points, but a point on a plane plus a normal vector also define a plane,
using less information.

Jon

Re:3d programming


Quote
On Mon, 12 Feb 1996, Paul Rowntree wrote:
> Christopher H. Clark wrote:

> > Jonathan Cohen wrote:

> > > In article <3118310E....@psu.edu>, Christopher H. Clark <chc...@psu.edu> wrote:
> > > >Actually, you only need 2 points to define a plane: a point on the plane and
> > > >a normal vector.

> > > Sorry to quibble, but...

> > >    A VECTOR IS NOT A POINT!!!!

> > > Now back to our regular program.

> > Points are vectors.
> > ^^^^^^^^^^^^^^^^^^

> Sorry, but I must take offense here.  A point in Cartesian space has three
> aspects [X,Y,Z].  A vector requires a direction, and depending on how sticky you
> are, probably a length.  This implies 6 independent aspects.  Result;  A plane
> requires 3 points.  Always.

> Cheers

A vector has a direction and magnitude. That is 4 parameters.
        YOu can consider a point to be a vector from (0,0,0) to (x,y,z).
However a vector (x,y,z) could be a vector from (x1,y1,z2) to (x2,y2,z3).
The point has a fixed location with respect to the coordinate axes while
the vector has no fixed location with respect to the coordinate axes.

David Matiskella
matis...@aa.washington.edu

Re:3d programming


Quote
John J. Karcher wrote:

[snip]

Quote
> >Points are vectors.

Possibly they are as far as implementaion goes, but not conceptualy
true.  The 'pure' definition of a point is that is has absolute position
(x,y & z), whilst a vector has magnitude and direction but no absolute
position

Quote
> But the reverse is not true.

Quite

Quote
>     - John J. Karcher

------------------------------------------------------------O----------------      
Out of the gloom came a voice, "Smile  and  be  happy things| EMail To:
could  be  worse",  it  said.  So I smiled and I was  happy,|
se...@dmu.ac.uk
and  behold  things  did  get worse.                        |
------------------------------------------------------------O----------------

Re:3d programming


Quote
David Matiskella wrote:

> On Mon, 12 Feb 1996, Paul Rowntree wrote:

> > Christopher H. Clark wrote:

> > > Jonathan Cohen wrote:

> > > > In article <3118310E....@psu.edu>, Christopher H. Clark <chc...@psu.edu> wrote:
> > > > >Actually, you only need 2 points to define a plane: a point on the plane and
> > > > >a normal vector.

> > > > Sorry to quibble, but...

> > > >    A VECTOR IS NOT A POINT!!!!

> > > > Now back to our regular program.

> > > Points are vectors.
> > > ^^^^^^^^^^^^^^^^^^

> > Sorry, but I must take offense here.  A point in Cartesian space has three
> > aspects [X,Y,Z].  A vector requires a direction, and depending on how sticky you
> > are, probably a length.  This implies 6 independent aspects.  Result;  A plane
> > requires 3 points.  Always.

> > Cheers

> A vector has a direction and magnitude. That is 4 parameters.
>         YOu can consider a point to be a vector from (0,0,0) to (x,y,z).
> However a vector (x,y,z) could be a vector from (x1,y1,z2) to (x2,y2,z3).
> The point has a fixed location with respect to the coordinate axes while
> the vector has no fixed location with respect to the coordinate axes.

OK, OK! I use the same data structure for points and vectors, and I've had
several calc and physics TA's (plus my computer graphics professor!) say that
a point (x, y, z) is really a vector from the origin to (x, y, z). It does
seem to have some merit, since x, y, and z are relative to the origin, and
therefore (x, y, z) indicates a displacement, which is a vector quantity.

-Chris
--
        \\ || //
        \ .  . /
___.oo0_(__()__)__0oo.___

 www.cse.psu.edu/~cclark

Re:3d programming


In article <311E38D7.7...@psu.edu> chc...@psu.edu "Christopher H. Clark" writes:

Quote
>Jonathan Cohen wrote:

>> Sorry to quibble, but...

>>    A VECTOR IS NOT A POINT!!!!

>> Now back to our regular program.

>Points are vectors.

No they aren't. A vector has a DIRECTION in space, not merely a POSITION.
It requires TWO points to define it.

Chris
--
--------------------------------------------------------------------------
 Chris Marriott, Warrington, UK      | Author of SkyMap v3 award-winning
 ch...@chrism.demon.co.uk            | shareware Win31/Win95 planetarium.
            For full info, see http://www.execpc.com/~skymap  
      Author member of Association of Shareware Professionals (ASP)
--------------------------------------------------------------------------

Go to page: [1] [2] [3] [4]

Other Threads