PHP Developers Network

A community of PHP developers offering assistance, advice, discussion, and friendship.
 
Loading
It is currently Mon Feb 24, 2020 10:07 pm

All times are UTC - 5 hours




Post new topic Reply to topic  [ 7 posts ] 
Author Message
PostPosted: Sun Aug 28, 2011 8:49 am 
Offline
Forum Commoner

Joined: Mon Jan 11, 2010 9:28 pm
Posts: 28
Hi, I'm working on a project that requires me to navigate a 3d cartesian coordinate system. Most of this stuff I learned back in high school, but it's been so long since I've taken a math class, I'm having to relearn a bunch of it.

Does anyone have any experience with this?

Here's what I'm currently trying to figure out.

Imagine the 3d graph (x,y,z). Grid lines are at each integer, though since the line uses real numbers, it can cross a grid line where it doesn't intersect with another. I'm calling each 1x1x1 square a sector such that if you're at (1.5,6.3,5.2), you're in sector (1,6,5)....basically, the adjacent point nearest the origin. I'm trying to identify where the line passes into the next sector. Or, more importantly, if I know two(2) points, I want to identify each sector the line passes through. I was thinking of identifying each integer between the two points for each of (x,y,z), and then solving for each (easy in 2 dimensions, but much tougher in 3). I was hoping there's a better method for doing this. Any ideas?

Thanks

Jason


Top
 Profile  
 
PostPosted: Mon Aug 29, 2011 4:58 pm 
Offline
DevNet Master
User avatar

Joined: Wed Jun 27, 2007 9:44 am
Posts: 4313
Location: Sofia, Bulgaria
By using the canonical formula (not sure that's the one in English) for a line with 2 points defined, you can calculate every point of the line.
After that you can "trace" the line by using integer numbers for one of the coordinates and round() for the other two.

_________________
There are 10 types of people in this world, those who understand binary and those who don't


Top
 Profile  
 
PostPosted: Tue Aug 30, 2011 2:31 am 
Offline
DevNet Master
User avatar

Joined: Wed Jun 27, 2007 9:44 am
Posts: 4313
Location: Sofia, Bulgaria
Syntax: [ Download ] [ Hide ]
<?php


class GridLine3D
{
        protected $pointA;
        protected $pointB;
       
        const X_AXIS    = 0;
        const Y_AXIS    = 1;
        const Z_AXIS    = 2;
       
        function __construct($pointA, $pointB)
        {
                $this->pointA = $pointA;
                $this->pointB = $pointB;
        }

        protected function calcCoefficient($value, $axis)
        {
                return ($value - $this->pointA[$axis]) / ($this->pointB[$axis] - $this->pointA[$axis]);
        }
       
        protected function calcAxisValue($axis, $coeff)
        {
                return $coeff * ( $this->pointB[$axis] - $this->pointA[$axis] ) + $this->pointA[$axis];
        }
       
        protected function getGridAlignedAxisValue($axis, $coeff)
        {
                return intval(round($this->calcAxisValue($axis, $coeff)));
        }
       
        /**
         *
         * @param int $value
         * @param int $axis GridLine3D::X_AXIS | GridLine3D::Y_AXIS | GridLine3D::Z_AXIS
         * @return array Point
         */

        public function calcGridAlignedPoint($value, $axis)
        {
                $coeff = $this->calcCoefficient($value, $axis);
               
                $x = $axis == self::X_AXIS ? $value : $this->getGridAlignedAxisValue(self::X_AXIS, $coeff);
                $y = $axis == self::Y_AXIS ? $value : $this->getGridAlignedAxisValue(self::Y_AXIS, $coeff);
                $z = $axis == self::Z_AXIS ? $value : $this->getGridAlignedAxisValue(self::Z_AXIS, $coeff);
               
                return array
                (
                        self::X_AXIS => $x,
                        self::Y_AXIS => $y,
                        self::Z_AXIS => $z,
                );
        }

}

$line3d = new GridLine3D(array(6, 9, 4), array(3, 7, 2));

for ($z = -10; $z < 11; $z++)
{
        echo implode(', ', $line3d->calcGridAlignedPoint($z, GridLine3D::Z_AXIS)) . "\n";
}

 

_________________
There are 10 types of people in this world, those who understand binary and those who don't


Top
 Profile  
 
PostPosted: Sat Sep 03, 2011 1:01 pm 
Offline
Forum Commoner

Joined: Mon Jan 11, 2010 9:28 pm
Posts: 28
VladSun,
Thanks for the response. I tried it out, but with the example you give, the x & y values remain constant while z progresses with the for loop. I've been trying this myself, using trigonometry. Unfortunately, it's been 20 years since I've taken trig, so I'm having to relearn all of this.

My thought, however is to handle it as follows:
1. Break into 2 planes (x,y & x,z).
2. Determine the next axis cross, and at what point that ocurrs.
To do this, I'd calculate the length of the hypotenuse of the triangle formed on the xy plane, calculating where it crosses x and where it crosses y. Then, the same for the xz plane, where it crosses z.
3. Once I know this, I'd pick the shortest of the 3, and use that to calculate the next coordinate set.
4. I'd repeat step 2 until I reach the destination coordinates.

Hopefully I'll have time to tackle this this weekend. If you, or anyone else have any thoughts on how to tackle this, feel free to help me out.

Thanks

Jason


Top
 Profile  
 
PostPosted: Sat Sep 03, 2011 3:53 pm 
Offline
DevNet Resident

Joined: Sun Jun 14, 2009 3:13 pm
Posts: 1146
Except for dividing the planes it sounds a bit like the 3d version of this algorithm used in graphic accelerators:
http://en.wikipedia.org/wiki/Bresenham% ... _algorithm

Maybe you could rewrite D to include the Z,Zo points and adjust the algorithm. Here's a C version of the 3D version of this algorithm:
http://www.luberth.com/plotter/line3d.c.txt.html

Or you might try rewriting the line in parametric form which allows to to sweep one variable.


Top
 Profile  
 
PostPosted: Sun Sep 04, 2011 2:55 pm 
Offline
DevNet Master
User avatar

Joined: Wed Jun 27, 2007 9:44 am
Posts: 4313
Location: Sofia, Bulgaria

_________________
There are 10 types of people in this world, those who understand binary and those who don't


Top
 Profile  
 
PostPosted: Sun Sep 04, 2011 6:44 pm 
Offline
Forum Commoner

Joined: Mon Jan 11, 2010 9:28 pm
Posts: 28


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: Google [Bot] and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Jump to:  
Powered by phpBB® Forum Software © phpBB Group