Triangle

Triangles in 3D space

PhilipRBrenan@yahoo.com, 2004, Perl License

Synopsis

Example t/triangle.t

#_ Triangle ___________________________________________________________
# Test 3d triangles    
# philiprbrenan@yahoo.com, 2004, Perl License    
#______________________________________________________________________

use Math::Zap::Vector;
use Math::Zap::Vector2;
use Math::Zap::Triangle;
use Test::Simple tests=>25;
 
$t = triangle
 (vector( 0,  0,  0), 
  vector( 0,  0,  4), 
  vector( 4,  0,  0),
 );
 
$u = triangle
 (vector( 0,  0,  0), 
  vector( 0,  1,  4), 
  vector( 4,  1,  0),
 );

$T = triangle
 (vector( 0,  1,  0), 
  vector( 0,  1,  1), 
  vector( 1,  1,  0),
 );

$c = vector(1, 1, 1);

#_ Triangle ___________________________________________________________
# Distance to plane
#______________________________________________________________________

ok($t->distance($c)   == 1, 'Distance to plane');
ok($T->distance($c)   == 0, 'Distance to plane');
ok($t->distance(2*$c) == 2, 'Distance to plane');
ok($t->distanceToPlaneAlongLine(vector(0,-1,0), vector(0,1,0)) == 1, 'Distance to plane towards a point');
ok($T->distanceToPlaneAlongLine(vector(0,-1,0), vector(0,1,0)) == 2, 'Distance to plane towards a point');

#_ Triangle ___________________________________________________________
# Permute the points of a triangle
#______________________________________________________________________

ok($t->permute                   == $t, 'Permute 1');
ok($t->permute->permute          == $t, 'Permute 2');
ok($t->permute->permute->permute == $t, 'Permute 3');

#_ Triangle ___________________________________________________________
# Intersection of a line with a plane defined by a triangle
#______________________________________________________________________

#ok($t->intersection($c, vector(1,  -1,  1)) == vector(1, 0, 1), 'Intersection of line with plane');
#ok($t->intersection($c, vector(-1, -1, -1)) == vector(0, 0, 0), 'Intersection of line with plane');

#_ Triangle ___________________________________________________________
# Test whether a point is in front or behind a plane relative to another
# point
#______________________________________________________________________
 
ok($t->frontInBehind($c, vector(1,  0.5,  1)) == +1, 'Front');
ok($t->frontInBehind($c, vector(1,    0,  1)) ==  0, 'In');
ok($t->frontInBehind($c, vector(1, -0.5,  1)) == -1, 'Behind');

#_ Triangle ___________________________________________________________
# Parallel
#______________________________________________________________________
 
ok($t->parallel($T) == 1, 'Parallel');
ok($t->parallel($u) == 0, 'Not Parallel');

#_ Triangle ___________________________________________________________
# Coplanar
#______________________________________________________________________
 
#ok($t->coplanar($t) == 1, 'Coplanar');
#ok($t->coplanar($u) == 0, 'Not coplanar');
#ok($t->coplanar($T) == 0, 'Not coplanar');

#_ Triangle ___________________________________________________________
# Project one triangle onto another
#______________________________________________________________________

$p = vector(0, 2, 0);
$s = $t->project($T, $p);

ok($s == triangle
 (vector(0,   0,   2),
  vector(0.5, 0,   2),
  vector(0,   0.5, 2),
 ), 'Projection of corner 3');

#_ Triangle ___________________________________________________________
# Convert space to plane coordinates and vice versa
#______________________________________________________________________

ok($t->convertSpaceToPlane(vector(2, 2, 2))   == vector(0.5,0.5,2), 'Space to Plane');
ok($t->convertPlaneToSpace(vector2(0.5, 0.5)) == vector(2, 0, 2),   'Plane to Space');

#_ Triangle ___________________________________________________________
# Divide 
#______________________________________________________________________

$it = triangle          # Intersects t
 (vector(  0, -1,  2), 
  vector(  0,  2,  2), 
  vector(  3,  2,  2),
 );

@d = $t->divide($it);

ok($d[0] == triangle(vector(0, -1, 2), vector(0, 0, 2), vector(1, 0, 2)));
ok($d[1] == triangle(vector(0,  2, 2), vector(0, 0, 2), vector(1, 0, 2)));
ok($d[2] == triangle(vector(0,  2, 2), vector(1, 0, 2), vector(3, 2, 2)));

$it = triangle          # Intersects t
 (vector(  3,  2,  2),
  vector(  0,  2,  2), 
  vector(  0, -1,  2), 
 );

@d = $t->divide($it);

ok($d[0] == triangle(vector(0, -1, 2), vector(0, 0, 2), vector(1, 0, 2)));
ok($d[1] == triangle(vector(3,  2, 2), vector(1, 0, 2), vector(0, 0, 2)));
ok($d[2] == triangle(vector(3,  2, 2), vector(0, 0, 2), vector(0, 2, 2)));

$it = triangle          # Intersects t
 (vector(  3,  2,  2),
  vector(  0, -1,  2), 
  vector(  0,  2,  2), 
 );

@d = $t->divide($it);

ok($d[0] == triangle(vector(0, -1, 2), vector(1, 0, 2), vector(0, 0, 2)));
ok($d[1] == triangle(vector(3,  2, 2), vector(1, 0, 2), vector(0, 0, 2)));
ok($d[2] == triangle(vector(3,  2, 2), vector(0, 0, 2), vector(0, 2, 2)));

Description

Triangles in 3D space

Definitions:

Space coordinates = 3d space

Plane coordinates = a triangle in 3d space defines a 2d plane with a natural coordinate system: the origin is the first point of the triangle, the (x,y) units of this plane are the sides from the triangles first point to its other points.

package Math::Zap::Triangle;
$VERSION=1.07;
use Math::Zap::Line2;
use Math::Zap::Unique;
use Math::Zap::Vector2 check=>'vector2Check';
use Math::Zap::Vector  check=>'vectorCheck';
use Math::Zap::Matrix  new3v=>'matrixNew3v';
use Carp qw(cluck confess);
use constant debug => 0; # Debugging level

Constructors

new

Create a triangle from 3 vectors specifying the coordinates of each corner in space coordinates.

sub new($$$)
 {my ($a, $b, $c) = vectorCheck(@_);
  my $t = bless {a=>$a, b=>$b, c=>$c};
  narrow($t, 1);
  $t; 
 }

triangle

Create a triangle from 3 vectors specifying the coordinates of each corner in space coordinates - synonym for "new".

sub triangle($$$) {new($_[0],$_[1],$_[2])};

Methods

narrow

Narrow (colinear) triangle?

sub narrow($$)
 {my $t = shift;  # Triangle
  my $a = 1e-2;   # Accuracy
  my $A = shift;  # Action 0: return indicator, 1: confess 
  
  my $n = (($t->b-$t->a) x ($t->c-$t->a))->length < $a;
  
  confess "Narrow triangle" if $n and $A;
  $n;      
 }

check

Check its a triangle

sub check(@)
 {if (debug)
   {for my $t(@_)
     {confess "$t is not a triangle" unless ref($t) eq __PACKAGE__;
     }
   } 
  return (@_)
 }

is

Test its a triangle

sub is(@)
 {for my $t(@_)
   {return 0 unless ref($t) eq __PACKAGE__;
   }
  'triangle';
 }

components

Components of a triangle

sub a($)   {check(@_) if debug; $_[0]->{a}}
sub b($)   {check(@_) if debug; $_[0]->{b}}
sub c($)   {check(@_) if debug; $_[0]->{c}}

sub ab($)  {check(@_) if debug; ($_[0]->{b}-$_[0]->{a})}
sub ac($)  {check(@_) if debug; ($_[0]->{c}-$_[0]->{a})}
sub ba($)  {check(@_) if debug; ($_[0]->{a}-$_[0]->{b})}
sub bc($)  {check(@_) if debug; ($_[0]->{c}-$_[0]->{b})}
sub ca($)  {check(@_) if debug; ($_[0]->{a}-$_[0]->{c})}
sub cb($)  {check(@_) if debug; ($_[0]->{b}-$_[0]->{c})}

sub abc($) {check(@_) if debug; ($_[0]->{a}, $_[0]->{b}, $_[0]->{c})}
sub area($){check(@_) if debug; ($_[0]->ab x $_[0]->ac)->length}

clone

Create a triangle from another triangle

sub clone($)
 {my ($t) = check(@_); # Triangle   
  bless {a=>$t->a, b=>$t->b, c=>$t->c};
 }

permute

Cyclically permute the points of a triangle

sub permute($)
 {my ($t) = check(@_); # Triangle   
  bless {a=>$t->b, b=>$t->c, c=>$t->a};
 }

center

Center

sub center($)
 {my ($t) = check(@_); # Triangle   
  ($t->a + $t->b + $t->c) / 3;
 }

add

Add a vector to a triangle

sub add($$)
 {my ($t) =         check(@_[0..0]); # Triangle   
  my ($v) = vectorCheck(@_[1..1]); # Vector     
  new($t->a+$v, $t->b+$v, $t->c+$v);                         
 }

subtract

Subtract a vector from a triangle

sub subtract($$)
 {my ($t) =         check(@_[0..0]); # Triangle   
  my ($v) = vectorCheck(@_[1..1]); # Vector     
  new($t->a-$v, $t->b-$v, $t->c-$v);                         
 }

print

Print triangle

sub print($)
 {my ($t) = check(@_); # Triangle   
  my ($a, $b, $c) = ($t->a, $t->b, $t->c);
  "triangle($a, $b, $c)";
 }

accuracy

# Get/Set accuracy for comparisons

my $accuracy = 1e-10;

sub accuracy
 {return $accuracy unless scalar(@_);
  $accuracy = shift();
 }

distance

Shortest distance from plane defined by triangle t to point p

sub distance($$)
 {my ($t) =         check(@_[0..0]); # Triangle  
  my ($p) = vectorCheck(@_[1..1]); # Vector
  my  $n  = $t->ab x $t->ac;         # Plane normal
  my ($a, $b) = ($p, $p+$n);
   
  my $s = matrixNew3v($t->ab, $t->ac, $a-$b)/($a-$t->a);

  ($n*$s->z)->length;
 }

intersectionInPlane

Intersect line between two points with plane defined by triangle and return the intersection in plane coordinates. Identical logic as per intersection(). Note: no checks (yet) for line parallel to plane.

sub intersectionInPlane($$$)
 {my ($t)     =         check(@_[0..0]); # Triangle  
  my ($a, $b) = vectorCheck(@_[1..2]); # Vectors
   
  matrixNew3v($t->ab, $t->ac, $a-$b)/($a-$t->a);
 }

distanceToPlaneAlongLine

Distance to plane defined by triangle t going from a to b, or undef if the line is parallel to the plane

sub distanceToPlaneAlongLine($$$)
 {my ($t)     =         check(@_[0..0]); # Triangle  
  my ($a, $b) = vectorCheck(@_[1..2]); # Vectors

  return undef if abs(($t->ab x $t->ac) * ($b - $a)) < $accuracy;
   
  my $i = matrixNew3v($t->ab, $t->ac, $a-$b)/($a-$t->a);
  $i->z * ($a-$b)->length;
 }

convertSpaceToPlane

Convert space to plane coordinates

sub convertSpaceToPlane($$)
 {my ($t) =         check(@_[0..0]); # Triangle  
  my ($p) = vectorCheck(@_[1..1]); # Vector
   
  my $q = $p-$t->a;

  vector
   ($q * $t->ab / ($t->ab * $t->ab),
    $q * $t->ac / ($t->ac * $t->ac),
    $q * ($t->ab x $t->ac)->norm
   );
 }

convertPlaneToSpace

Convert splane to space coordinates

sub convertPlaneToSpace($$)
 {my ($t, $p) = @_;
         check(@_[0..0]) if debug; # Triangle  
  vector2Check(@_[1..1]) if debug; # Vector in plane
   
  $t->a + ($p->x * $t->ab) + ($p->y * $t->ac);
 }

frontInBehind

Determine whether a test point b as viewed from a view point a is in front of(1), in(0), or behind(-1) a plane defined by a triangle t. Identical logic as per intersection(), except this time we use the z component to determine the relative position of the point b. Note: no checks (yet) for line parallel to plane.

sub frontInBehind($$$)
 {my ($t, $a, $b) = @_;
          check(@_[0..0]) if debug; # Triangle  
  vectorCheck(@_[1..2]) if debug; # Vectors
  return 1 if abs(($t->ab x $t->ac) * ($a-$b)) < $accuracy; # Parallel
  $s = matrixNew3v($t->ab, $t->ac, $a-$b)/($a-$t->a);
  $s->z <=> 1;
 }

frontInBehindZ

sub frontInBehindZ($$$)
 {my ($t, $a, $b) = @_;
          check(@_[0..0]) if debug; # Triangle  
  vectorCheck(@_[1..2]) if debug; # Vectors
  return undef if abs(($t->ab x $t->ac) * ($a-$b)) < $accuracy;  # Parallel
  $s = matrixNew3v($t->ab, $t->ac, $a-$b)/($a-$t->a);
  $s->z;
 }

parallel

Are two triangle parallel? I.e. do they define planes that are parallel? If they are parallel, their normals will have zero cross product

sub parallel($$)
 {my ($a, $b) = check(@_); # Triangles
  !(($a->ab x $a->ac) x ($b->ab x $b->ac))->length;
 }

divide

Divide triangle b by a: split b into triangles each of which is not intersected by a. Triangles are easy to draw in 3d except when they intersect: If they do not intersect, we can always draw one on top of the other and obtain the correct result; If they do intersect, they have to be split along the line of intersection into a sub triangle and a quadralateral: which can be be split again to obtain a result consisting of only triangles. The splitting can be done once: Each new view point only requires the correct ordering of the non intersecting triangles.

sub divide($$)
 {my ($a, $b) = check(@_);         # Triangles  

  return ($b) if $a->parallel($b); # Parallel: no need to split

  my $A = $a->permute; $a = $A if $b->distance($A->a) > $b->distance($a->a);
     $A = $A->permute; $a = $A if $b->distance($A->a) > $b->distance($a->a);
 
  my $na = $a->ab x $a->ac;        # Normal to a
  my $nb = $b->ab x $b->ac;        # Normal to b

  my $aa = $a->a;
  my $ab = $a->b;
  my $ac = $a->c;
  my $bc = $a->bc;

# Avoid using vectors in a that are parallel to b
  $ab += $bc/2 if ($a->ab->norm * $nb->norm) < 0.1;
  $ac += $bc/2 if ($a->ac->norm * $nb->norm) < 0.1;

# Two points in both planes in b plane coordinates
  my $i = $b->intersectionInPlane($aa, $ab);
  my $j = $b->intersectionInPlane($aa, $ac);


# Does the line between these points intersect the sides of triangle b?
  my $l = line2
   (vector2($i->x, $i->y), 
    vector2($j->x, $j->y),
   );
  return ($b) if ($l->b-$l->a)->length < $accuracy;

# Triangle b has very simple sides in b plane coordinates

  my $l1 = line2(vector2(0, 0), vector2(1, 0)); # ab
  my $l2 = line2(vector2(0, 0), vector2(0, 1)); # ac
  my $l3 = line2(vector2(1, 0), vector2(0, 1)); # bc 

  my $i1 = ((!$l->parallel($l1)) and ($l->intersectWithin($l1)));
  my $i2 = ((!$l->parallel($l2)) and ($l->intersectWithin($l2)));
  my $i3 = ((!$l->parallel($l3)) and ($l->intersectWithin($l3)));

# There should be either 0 or 2 intersections.
   {my $n = $i1+$i2+$i3;
    ($n == 1 or $n == 3) and  debug and warn "There should 0 or 2 intersections, not $n";
    return ($b) unless $n == 2; # No division required
   }

# There are two intersections.
# Make a copy of b called c, orientated so that the line of 
# intersection crosses sides c->ab, c->ac           
  my $c;
  $c = $b                                 if $i1 and $i2;   
  $c = triangle($b->b, $b->a, $b->c) if $i1 and $i3;   
  $c = triangle($b->c, $b->a, $b->b) if $i2 and $i3;

# Find intersection points in terms of reorientated triangle   

  unless ($i1 and $i2)
   {$i = $c->intersectionInPlane($aa, $ab);
    $j = $c->intersectionInPlane($aa, $ac);
    $l = line2
     (vector2($i->x, $i->y), 
      vector2($j->x, $j->y),
     );
   }

# this time in plane coordinates
  $i1 = $l->intersect($l1);
  $i2 = $l->intersect($l2);

# Convert to space coordinates
  my $s1 = $c->convertPlaneToSpace($i1);
  my $s2 = $c->convertPlaneToSpace($i2);

# Vertices close to intersection points 
  my $a1 = ($c->a - $s1)->length < 1e-3; 
  my $a2 = ($c->a - $s2)->length < 1e-3; 
  my $b1 = ($c->b - $s1)->length < 1e-3; 
  my $b2 = ($c->b - $s2)->length < 1e-3; 
  my $c1 = ($c->c - $s1)->length < 1e-3; 
  my $c2 = ($c->c - $s2)->length < 1e-3;

  return ($b) if ($a1 or $b1 or $c1) and ($a2 or $b2 or $c2);
  
# Divide b into 3 if the intersections points are far from the vertices
  return
   (triangle($c->a, $s1, $s2),
    triangle($c->b, $s1, $s2),
    triangle($c->b, $s2, $c->c),
   ) unless $a1 or $a2 or $b1 or $b2 or $c1 or $c2;

# If only one intersection point is close to a vertex, make it s1.
  ($s1, $s2, $a1, $b1, $c1, $a2, $b2, $c2) =
  ($s2, $s1, $a2, $b2, $c2, $a1, $b1, $c1) if !($a1 or $b1 or $c1) and ($a2 or $b2 or $c2);

# Divide b into 2 if one intersection point is close to a vertex
  return
   (triangle($c->a, $c->b, $s2),
    triangle($c->a, $c->c, $s2),
   ) if $a1;
  return
   (triangle($c->a, $c->b, $s2),
    triangle($c->c, $c->b, $s2),
   ) if $b1;
  return
   (triangle($c->a, $c->c, $s2),
    triangle($c->b, $c->c, $s2),
   ) if $c1;
  confess "Unable to divide triangle $a by $b\n"
 }

project

Project onto the plane defined by triangle t the image of a triangle triangle T as viewed from a view point p. Return the coordinates of the projection of T onto t using the plane coordinates induced by t. The projection coordinates are (of course) 2d in the projection plane, however they are returned as the x,y components of a 3d vector with the z component set to the multiple of the distance from the view point to the corresponding corner of T required to reach t. If z > 1, this corner of T is in front the plane of t, if z < 1 this corner of T is behind the plane of t. The logic is the same as intersection().

sub project($$$)
 {my ($t, $T, $p) = @_;
          check(@_[0..1]) if debug; # Triangles 
  vectorCheck(@_[2..2]) if debug; # Vector

  new
   (matrixNew3v($t->ab, $t->ac, $p-$T->a)/($p-$t->a),
    matrixNew3v($t->ab, $t->ac, $p-$T->b)/($p-$t->a),
    matrixNew3v($t->ab, $t->ac, $p-$T->c)/($p-$t->a),
   );
 }

split

Split a triangle into 4 sub triangles unless the sub triangles would be too small

sub split($$)
 {my ($t) = check(@_[0..0]); # Triangles 
  my ($s) =      (@_[1..1]); # Minimum size 

  return () unless
    $t->ab->length > $s and
    $t->ac->length > $s and
    $t->bc->length > $s;

   (new($t->a, ($t->a+$t->b)/2, ($t->a+$t->c)/2),
    new($t->b, ($t->b+$t->a)/2, ($t->b+$t->c)/2),
    new($t->c, ($t->c+$t->a)/2, ($t->c+$t->b)/2),
    new(($t->a+$t->b)/2, ($t->a+$t->b)/2, ($t->b+$t->c)/2)
   )
 }

triangulate

Triangulate

sub triangulate($$)
 {my ($t)    = check(@_[0..0]); # Triangle
  my  $color =       @_[1..1];  # Color           
  my  $plane = unique();        # Plane           
   
  {triangle=>$t, color=>$color, plane=>$plane};
 }

equals

Compare two triangles for equality

sub equals($$)
 {my ($a, $b) = check(@_); # Triangles
  my ($aa, $ab, $ac) = ($a->a, $a->b, $a->c);
  my ($ba, $bb, $bc) = ($b->a, $b->b, $b->c);
  my  $d             = $accuracy;  

  return 1 if 
abs(($aa-$ba)->length) < $d and abs(($ab-$bb)->length) < $d and abs(($ac-$bc)->length) < $d or
abs(($aa-$ba)->length) < $d and abs(($ab-$bc)->length) < $d and abs(($ac-$bb)->length) < $d or
abs(($aa-$bb)->length) < $d and abs(($ab-$bc)->length) < $d and abs(($ac-$ba)->length) < $d or
abs(($aa-$bb)->length) < $d and abs(($ab-$ba)->length) < $d and abs(($ac-$bc)->length) < $d or
abs(($aa-$bc)->length) < $d and abs(($ab-$ba)->length) < $d and abs(($ac-$bb)->length) < $d or
abs(($aa-$bc)->length) < $d and abs(($ab-$bb)->length) < $d and abs(($ac-$ba)->length) < $d;  
  0;
 }

Operators

Operator overloads

use overload
 '+',       => \&add3,      # Add a vector
 '-',       => \&sub3,      # Subtract a vector
 '=='       => \&equals3,   # Equals
 '""'       => \&print3,    # Print
 'fallback' => FALSE;

add

Add operator.

sub add3
 {my ($a, $b, $c) = @_;
  return $a->add($b);
 }

subtract

Subtract operator.

sub sub3
 {my ($a, $b, $c) = @_;
  return $a->subtract($b);
 }

equals

Equals operator.

sub equals3
 {my ($a, $b, $c) = @_;
  return $a->equals($b);
 }

print

Print a triangle

sub print3
 {my ($a) = @_;
  return $a->print;
 }

Exports

Export "triangle"

use Math::Zap::Exports qw(
  triangle ($$$)
 );

#_ Triangle ___________________________________________________________
# Package loaded successfully
#______________________________________________________________________

1;

Credits

Author

philiprbrenan@yahoo.com

Copyright

philiprbrenan@yahoo.com, 2004

License

Perl License.

To install Math::Zap::Draw, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Math::Zap::Draw

CPAN shell

perl -MCPAN -e shell
install Math::Zap::Draw

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

Triangle

Synopsis

Description

Constructors

new

triangle

Methods

narrow

check

is

components

clone

permute

center

add

subtract

print

accuracy

distance

intersectionInPlane

distanceToPlaneAlongLine

convertSpaceToPlane

convertPlaneToSpace

frontInBehind

frontInBehindZ

parallel

divide

project

split

triangulate

equals

Operators

add

subtract

equals

print

Exports

Credits

Author

Copyright

License

Module Install Instructions