xracer-tools 0.96.9.1-6 / usr / games / xracer-mktrack

#!/usr/bin/perl -w
# XRACER (C) 1999-2000 Richard W.M. Jones <rich@annexia.org> and other AUTHORS
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
#
# $Id: xracer-mktrack.pl,v 1.9 2000/01/01 15:51:41 rich Exp $

# You have created the basic track shape in Blender and saved it
# as a VideoScape file. This file defines the basic shape of the
# track. This basic shape defines the surfaces which exert their
# levitation effect on the craft. At this stage, we are NOT talking
# about what the track actually looks like, or any textures, etc.
# (Although in the common case, these two things can be the same).
# This script takes this information and builds the C file necessary
# for XRacer to work out what forces are exerted on the craft at
# each point on the track.

use strict;

use Getopt::Long;

use lib '../../XRacer/blib/lib'; # So you can run this without installing it.
use XRacer::Math;

# Read command line arguments.
my $nr_steps;
my $tubefilename;
my $coutputfilename;
my $verbose;
my $help;

GetOptions ("steps=i" => \$nr_steps,
	    "tubefile=s" => \$tubefilename,
	    "outputc=s" => \$coutputfilename,
	    "verbose" => \$verbose,
	    "help|?" => \$help);

if ($help)
  {
    print STDERR "$0 --steps STEPS [--outputc OUTPUTFILE] [--verbose] --tubefile TUBEFILE [INPUTFILE]\n";
    print STDERR "where: STEPS is the number of vertices in each segment\n";
    print STDERR "       OUTPUTFILE is the C file to write\n";
    print STDERR "       TUBEFILE is the tube file generated by mktube prog\n";
    print STDERR "       INPUTFILE is the input VideoScape file\n";
    exit 1;
  }

die "--steps argument is required" if !$nr_steps;
die "--tubefile argument is required" if !$tubefilename;

# Read the segments from the tubefile.
my $segmentsref = do $tubefilename
  or die "$tubefilename: $!";
my @segments = @$segmentsref;

print "number of segments in tube file: ", scalar (@segments), "\n"
  if $verbose;

# Read input lines.
my $state = "expect 3DG1";
my $vcount;
my $nr_segments;
my @vertices = ();
my @faces = ();

while (<>)
  {
    s/[\n\r]+$//g;		# Removes trailing CR, LF.

    if ($state eq "expect 3DG1")
      {
	die "expecting first line to be 3DG1" if $_ ne "3DG1";
	$state = "expect vcount";
      }
    elsif ($state eq "expect vcount")
      {
	die "expecting vertex count" if $_ !~ m/^[1-9][0-9]*$/;

	$vcount = $_;

	# Check that steps divides number of vertices.
	die "number of steps must divide number of vertices ($vcount)"
	  if ($vcount / $nr_steps != int ($vcount / $nr_steps));

	$nr_segments = $vcount / $nr_steps;

	die "number of segments found does not match tube file"
	  if $nr_segments != @segments;

	$state = "reading vertices";
      }
    elsif ($state eq "reading vertices")
      {
	my @vs = split /[ \t]+/, $_;
	push @vertices, \@vs;
	$vcount--;

	$state = "reading faces" if $vcount == 0;
      }
    elsif ($state eq "reading faces")
      {
	my @fs = split /[ \t]+/, $_;
	die "oops - expecting only four-sided faces"
	  if $fs[0] != 4;
	push @faces, { 'vertices' => [ $fs[1], $fs[2], $fs[3], $fs[4] ] };
      }
  }

# Print a summary of the file.
print "number of vertices: ", scalar (@vertices), "\n" if $verbose;
print "number of segments: $nr_segments\n" if $verbose;
print "number of faces: ", scalar (@faces), "\n" if $verbose;

# For convenience, number each face and also convert it to
# a set of plane coefficients.
for (my $i = 0; $i < @faces; ++$i)
  {
    $faces[$i]->{n} = $i;
    $faces[$i]->{faceplane}
    = plane_coefficients ($vertices[$faces[$i]->{vertices}->[0]],
			  $vertices[$faces[$i]->{vertices}->[1]],
			  $vertices[$faces[$i]->{vertices}->[2]]);
  }

# Map faces into segments.
foreach (@segments) { $_->{faces} = [] };

my $face;
foreach $face (@faces)
  {
    # Map vertex numbers to segment numbers.
    my @sns = map { int ($_ / $nr_steps) } @{$face->{vertices}};

    #print "segments: ", join (" ", @sns), "\n" if $verbose;

    # Take the minimum and maximum segment numbers.
    my $min_seg = $nr_segments+1;
    foreach (@sns) { $min_seg = $_ if $_ < $min_seg }
    my $max_seg = -1;
    foreach (@sns) { $max_seg = $_ if $_ > $max_seg }

    # The minimum segment number must be max segment number - 1 (but
    # take into account the wrap-around case ...)
    my $segnum;
    if ($min_seg == $max_seg)	# Equal is OK too.
      {
	$segnum = $min_seg;
      }
    elsif ($min_seg == $max_seg-1)
      {
	$segnum = $min_seg;
      }
    elsif ($min_seg == 0 && $max_seg == $nr_segments-1) # wraparound case
      {
	$segnum = $nr_segments-1;
      }
    else
      {
	die "oops - track face covers more than 1 segment";
      }

    #print "putting it into segment: $segnum\n" if $verbose;

    # Put the face into the segment.
    my $facesref = $segments[$segnum]->{faces};
    push @$facesref, $face;
  }

# Examine each face in turn and create the list of planes.
foreach $face (@faces)
  {
    # Get the four vertices from the face.
    my $v0 = $vertices[$face->{vertices}->[0]];
    my $v1 = $vertices[$face->{vertices}->[1]];
    my $v2 = $vertices[$face->{vertices}->[2]];
    my $v3 = $vertices[$face->{vertices}->[3]];

    # Construct the midpoint of the face (point MP in diagram).
    my $mp = midpoint ($v0, $v1, $v2, $v3);

    # Construct a plane from the face.
    my $faceplane = plane_coefficients ($v2, $v1, $v0);

    # Construct a unit normal vector to the face (vector MQ-MP in diagram).
    my $n = unit_normal ($faceplane);

    # Construct midpoint of plane one unit normal from face (point MQ).
    my $mq = sum_vectors ($mp, $n);

    # Construct points V4, ..., V7 (see diagram).
    my $v4 = sum_vectors ($v0, $n);
    my $v5 = sum_vectors ($v1, $n);
    my $v6 = sum_vectors ($v2, $n);
    my $v7 = sum_vectors ($v3, $n);

    # Points V8, ..., V11 are just points V4, ..., V7 extended
    # outwards by a small percentage. So, for example,
    # V8 = MQ + (V4 - MQ) * (expansion_percentage / 100)
    # where expansion_percentage is, perhaps, 110.

    # XXX Constant!
    my $expansion = 1.1;

    my $v8 = sum_vectors ($mq,
			  multiply_scalar_vector ($expansion,
			  subtract_vectors ($v4, $mq)));
    my $v9 = sum_vectors ($mq,
			  multiply_scalar_vector ($expansion,
                          subtract_vectors ($v5, $mq)));
    my $v10 = sum_vectors ($mq,
			   multiply_scalar_vector ($expansion,
			   subtract_vectors ($v6, $mq)));
    my $v11 = sum_vectors ($mq,
			   multiply_scalar_vector ($expansion,
                           subtract_vectors ($v7, $mq)));

    if ($verbose)
      {
	print "face:  ", cinitializer ($v0, $v1, $v2, $v3), "\n";
	print "inner: ", cinitializer ($v4, $v5, $v6, $v7), "\n";
	print "outer: ", cinitializer ($v8, $v9, $v10, $v11), "\n";
      }

    # Now we can construct the planes for real (see right
    # hand side of diagram). For example, one plane is
    # V0, V1, V9, V8
    my $plane0 = plane_coefficients ($v8, $v0, $v1);
    my $plane1 = plane_coefficients ($v9, $v1, $v2);
    my $plane2 = plane_coefficients ($v10, $v2, $v3);
    my $plane3 = plane_coefficients ($v11, $v3, $v0);

    # Assertion: Check that the midpoints $mp and $mq are both
    # inside all of the planes. This is just a sanity check
    # on the above calculations.
    die "assertion failed: midpoints not inside planes"
      if distance_point_to_plane ($plane0, $mp) < 0 ||
	distance_point_to_plane ($plane0, $mq) < 0 ||
	distance_point_to_plane ($plane1, $mp) < 0 ||
	distance_point_to_plane ($plane1, $mq) < 0 ||
	distance_point_to_plane ($plane2, $mp) < 0 ||
	distance_point_to_plane ($plane2, $mq) < 0 ||
	distance_point_to_plane ($plane3, $mp) < 0 ||
	distance_point_to_plane ($plane3, $mq) < 0;

    # Store these planes in the face description.
    $face->{planes} = [ $plane0, $plane1, $plane2, $plane3 ];
  }

# Save what we have to the C output file.
if ($coutputfilename)
  {
    open C, ">$coutputfilename"
      or die "$coutputfilename: $!";

    print C "/* This file describes the shape of the track itself.\n * It is automatically generated.\n */\n\n#include \"common.h\"\n\n";

    # Save a list of vertices.
    print C "int nr_face_vertices = ", scalar (@vertices), ";\n";

    print C "GLfloat face_vertices[][3] = ",
    cinitializer (@vertices), ";\n";

    # Construct the list of faces.
    print C "int nr_faces = ", scalar (@faces), ";\n";

    print C "struct xrFace faces[] = {\n";

    print C join (",\n",
		  map ({
			my $faceplane = $_->{faceplane};
			my $planes = $_->{planes};
			my $vertices = $_->{vertices};

			"{ " . cinitializer (@$faceplane) . ", " .
			cinitializer (@$planes) . ", " .
			cinitializer (@$vertices) . " }"
		       } @faces));

    print C "};\n";

    # Construct the mapping of segments onto faces.
    for (my $i = 0; $i < @segments; ++$i)
      {
	print C "static int _faces$i [] = ",
	cinitializer (map { $_->{n} } @{$segments[$i]->{faces}}), ";\n";
      }

    print C "struct xrSegmentFaces segment_to_faces[] = {\n";

    my $i = 0;
    print C join (",\n",
		  map ({
			my $faces = $_->{faces};
			my $nr_faces = @$faces;

			"{ " . $nr_faces . ", _faces" . $i++ . " }"
		       } @segments));

    print C "};\n";

    print C "/* End of file. */\n";

    close C;
  }

exit 0;

#----------------------------------------------------------------------

# This small helper function takes a list of either numbers of
# array refs, and returns an equivalent C string for initializing
# a C multi-dimensional array or structure.
sub cinitializer
  {
    return "{ " . join (", ",
			map ({ ref ($_) eq 'ARRAY' ? cinitializer (@$_) : $_ }
			     @_)) . " }";
  }

#----------------------------------------------------------------------

sub is_cbc
  {
    my $plane0 = shift;
    my $plane1 = shift;
    my $cylinder = shift;

    # Calculate line of intersection of the two planes.
    my $intersection = intersection_of_two_planes ($plane0,
						   $plane1);

    return line_intersects_cylinder ($intersection, $cylinder);
  }

# Return true if $plane1 is inside $plane0. Both planes are
# CBC-related.
#
# Since the planes are CBC-related, we know that they do
# not intersect at any points within the cylinder. Therefore
# we can simply pick any point on $plane1 which is inside
# the cylinder and test that point for insidedness with
# respect to $plane0. The problem is to find a point inside
# the cylinder on $plane1. 
sub is_inside
  {
    my $plane0 = shift;
    my $plane1 = shift;
    my $cylinder = shift;

    # XXXXXXXXXXXXXXXXXXX



  }

# Build a decision tree, recursively. This function takes the
# following arguments:
#   $current_depth
#   $max_depthref   (reference to $max_depth variable)
#   $nr_nodesref    (reference to $nr_nodes variable)
#   $planesref      (reference to list of planes left -- DO NOT CHANGE THIS!)
#   $insideref      (references to inside planes -- DO NOT CHANGE THIS!)
#   $cylinder       (bounding cylinder)
# It returns a tree.
sub build_decision_tree
  {
    my $current_depth = shift;
    my $max_depthref = shift;
    my $nr_nodesref = shift;
    my $planesref = shift;
    my $insideref = shift;
    my $cylinder = shift;

    # Update global $max_depth variable.
    $$max_depthref = $current_depth if $$max_depthref < $current_depth;

    # Update global $nr_nodes variable.
    $$nr_nodesref++;

    my %node = ();

    # Base case: no planes left: build the list of faces now.
    if (@$planesref == 0)
      {
	$node{type} = "base";

	# Find out which faces are fully inside (all four planes inside).
	my %inside_count = ();
	my @faces_inside = ();

	foreach (@$insideref)
	  {
	    if (exists $inside_count{$_->{face}})
	      {
		$inside_count{$_->{face}}++;
	      }
	    else
	      {
		$inside_count{$_->{face}} = 0;
	      }
	  }

	foreach (keys %inside_count)
	  {
	    if ($inside_count{$_} == 4)
	      {
		push @faces_inside, $_;
	      }
	    elsif ($inside_count{$_} > 4)
	      {
		die "oops: face $_ has inside_count == ",
		  $inside_count{$_};
	      }
	  }

	# Construct the base node.
	$node{faces} = \@faces_inside;

	print "constructing base node, faces == { ",
	  join (", ", @faces_inside), " }\n" if $verbose;
      }
    # Recursive case: pick a plane and build an interior node.
    else
      {
	$node{type} = "interior";

	# Pick a plane at random. Well, OK, pick the first plane.
	my $plane = $planesref->[0];

	# Here we build up:
	# (1) a list of CBC-related planes inside $plane.
	# (2) a list of CBC-related planes outside $plane.
	# (3) a list of non-CBC-related planes.
	my @cbc_related_inside = ();
	my @cbc_related_outside = ();
	my @not_cbc_related = ();

	for (my $i = 1; $i < @$planesref; $i++)
	  {
	    if (is_cbc ($plane->{plane}, $planesref->[$i]->{plane},
			$cylinder))
	      {
		if (is_inside ($plane->{plane}, $planesref->[$i]->{plane},
			       $cylinder))
		  {
		    push @cbc_related_inside, $planesref->[$i];
		  }
		else
		  {
		    push @cbc_related_outside, $planesref->[$i];
		  }
	      }
	    else
	      {
		push @not_cbc_related, $planesref->[$i];
	      }
	  }

	# Build the inside tree.
	my @remaining_planes = ();
	push @remaining_planes, @not_cbc_related;
	my @inside_planes = ();
	push @inside_planes, @$insideref, @cbc_related_inside;

	my $inside_tree = build_decision_tree ($current_depth+1,
					       $max_depthref,
					       \@remaining_planes,
					       \@inside_planes,
					       $cylinder);

	# Build the outside tree.
	@remaining_planes = ();
	push @remaining_planes, @not_cbc_related, @cbc_related_outside;
	@inside_planes = ();
	push @inside_planes, @$insideref;

	my $outside_tree = build_decision_tree ($current_depth+1,
						$max_depthref,
						\@remaining_planes,
						\@inside_planes,
						$cylinder);

	$node{inside} = $inside_tree;
	$node{outside} = $outside_tree;
      }

    return \%node;
  }