Architecture of the Perl Portalization System

The Perl portalization system consists of a number of scripts which can be divided into three categories: structural modules, parsing and generator modules, and controlling scripts. The next sections cover each of these categories individually.

We unfortunately don't have the space here to provide a tutorial on the Perl language. Check the manual page for Perl (type man perl) for extensive information on the various reference material and tutorials available online. We'll go over the major concepts of each Perl script at a high level so you can understand how they work, and also comment briefly on any particularly unusual Perl constructs used to achieve the goals.

The operation of the entire system can be understood as follows. Also, refer back to the data flow diagram of the system, Figure 6-10.

1. Parse all Videoscape files. Store all of the geometry in internal Perl data structures, organized by sector.

2. For each sector, scan the mesh for free edges. Link all free edges into continuous loops. Add each continuous loop as a portal polygon belonging to the sector.

3. For each sector and portal, scan all other sectors for an overlapping portal. If such an overlapping portal is found, link the original portal to the target sector containing the overlapping portal. If no such portal is found, the portal has no target sector, which is a modeling error; thus, delete the portal.

4. Print each sector's vertex, polygon, and portal definitions to the world file.

Keep the high-level operation of the system in mind as you read the following sections on the specific Perl modules used.

Structural Modules

The structural Perl modules in the portalization system store the geometrical data extracted from the Videoscape files in a structured manner, so that this information may be easily queried and changed. Each Perl module is essentially a class, in the object-oriented sense of the word. The organization of the structural classes is similar to that of the l3d classes. At the lowest level, we have 3D vertices (represented by module Vertex.pm). Based on lists of these vertices, we can build facets (polygons) and portals (modules Facet.pm and Portal.pm). A facet can contain a reference to a texture (Texture.pm). Facets and polygons are grouped into sectors (Sec-tor.pm). A sector can also contain any number of actors (Actor.pm), which are plug-in objects. All sectors and actors belong to the world (World.pm). A description of each of the structural modules follows.

Vertex.pm

Module Vertex.pm represents a vertex in 3D space.

Method new is the object constructor. It creates a new Perl hash object—which, remember, is just a list with members indexed by string—and inserts several items into the hash. These items are essentially the member variables of the class, and we will refer to them as such. In other words, we are using a Perl hash as an instance of a class, and are using elements of the hash object to represent member variables for that instance. This idea is identical for all of the Perl modules used in the portalization system.

Member variables _x, _y, and _z are the spatial coordinates of the vertex. External users of this class do not access the variables directly, but instead go through the member functions x, y, and z. Without an argument, these functions return the corresponding value; with an argument, they set the value to the given value. Another programming idiom, also used in the Perl portalization modules, is to have separate get and set routines, for instance get_x and set_x. All of the Perl portalization modules use this scheme of private hash members being accessed through member functions (either separate get/set methods or a unified get-set method), so we won't explicitly mention it again.

Method dot takes a second vertex as a parameter, and takes the dot product of itself and the given vertex. Both vertices are interpreted as the tips of vectors starting at the origin. This implies that the Perl Vertex class as defined here does not distinguish between vectors and points—a small sin, but if you've made it this far in the book, you hopefully know well the difference between vectors and points so as to understand which is meant within the context of a particular usage.

Method dif takes a second vertex as a parameter, and returns the vector difference between the location of the current vertex and the location of the second vertex—in other words, the vector from the second vertex to the current vertex.

Listing 6-1: Vertex.pm package Vertex;

use strict;

## the object constructor ##

return $self;

## methods to access per-object data ##

return $self->x * $v2->x + $self->y * $v2->y + $self->z * $v2->z ;

return $vnew;

1; # so the require or use succeeds

Facet.pm

Module Facet.pm represents a polygonal facet. It stores the geometrical definition of the facet in terms of indices into a vertex list. It also provides methods which we need for the portalization process: accessing the facet's edge list, checking for polygon overlap, and using the facet as a texture space.

Method new is the object constructor. As a parameter, it expects a sector object, which is the parent of the facet object. In other words, facets cannot exist in isolation; they belong to a sector.

Member variable _is_invisible is an integer flag indicating if the facet is invisible (1) or visible (0). As we see later, we can use invisible facets to help define texture spaces to map textures to the walls of our sectors.

Member variable _tex_id is a string indicating which texture should be applied to this facet. Again, we cover texturing later in this chapter; also see module Texture.pm.

Member variable _parent_sector is a reference to the sector containing this facet, and is set in the constructor.

Member variable _vertex_indices is an array of integers which are indices into the parent sector's vertex list. These vertex indices define the polygon.

Method get_edge_list constructs a list of edges for the facet and returns it to the caller. An edge is simply a consecutive pair of vertex indices. The purpose of this method is to explicitly store all such pairs in a list, and to return this list. For instance, if a polygon is defined by the three vertex indices 0 7 2, then the edge list would be [ [0,7], [7,2], [2,0] ]. Accessing the edges plays an important role in finding the free edges, which form the boundaries of portals.

Method contains_edge tells the caller whether or not the facet contains a particular edge, as specified by its two vertex indices. We use this method when scanning for free edges; if an edge is contained only by one facet, then it is a free edge; otherwise, it is not.

Method coincident_with_facet tells the caller whether or not the facet overlaps exactly with another facet, passed as a parameter. This is used in scanning for overlapping portals to link them together. It works by seeing if for each vertex in the original facet, a corresponding vertex at the same spatial location can be found in the other facet. If so, then the facets are coincident; otherwise, they are not. During comparison, we introduce an epsilon parameter to allow nearby points also to count as overlapping, to compensate for slight numerical or modeling errors.

Method get_tex_ouv interprets a triangular facet as a texture space specification and returns a hash with three elements representing the origin of the texture space, the tip of the u axis, and the tip of the v axis. Methods get_tex_origin, get_tex_u_vec, and get_tex_ v_vec call method get_tex_ouv and just return the appropriate single element requested (the origin, u tip, or v tip, respectively). The idea behind these methods is that a single triangular facet can be interpreted as a texture space; we call such a triangle a texture definition triangle. In order for this to work, the facet must be a right triangle—in other words, one of the angles must be exactly 90 degrees. The polygon vertex ordering determines the front/back orientation of the polygon; the left-handed convention we have been using throughout this book is that the front side is the side from which the polygon vertices appear clockwise. Then, we can define the triangle texture space as follows: when looking at the front side of the right triangle, the vertex on the 90 degree angle is the origin, the next vertex in the clockwise direction is the tip of the u axis, and the remaining vertex is the tip of the v axis. By appropriately scaling and positioning a triangle, we can then specify any texture space with a single polygon; we later see exactly how to do this in Blender, and how to flag a triangle so that it is recognized by the portalization system as being a texture definition triangle. Assuming a triangle has been found to have been marked as a texture definition triangle, the method get_tex_ouv then scans the triangle to find the vertex on the 90 degree angle, using the dot product between the two adjoining edges. This point is the origin of texture space; the next clockwise point is the u tip, and the other point is the v tip.

Figure 6-39: A texture space defined in world coordinates.

Figure 6-40: The texture space represented by a right triangle. Point 0 is on a 90 degree angle between two edges, and is thus the origin of the texture space. Point 1 is the next clockwise vertex (we are looking at the back side of the triangle), and is thus the tip of the u axis. Point 2 is the tip of the v axis. The w axis is not explicitly defined and is not needed for 2D textures.

^y NOTE Note that a texture space defined by means of a right triangle only specifies the loca-^^ tion of the origin, the u axis tip, and the v axis tip. It does not allow for specification of a w axis. Specification of a w axis is only important if we use 3D volumetric textures (see Chapter 3), which we do not in this book.

Listing 6-2: Facet.pm package Facet; use strict;

## the object constructor ##

my $class = ref($proto) || $proto; my $self = {}; $self->{_is_invisible} = 0; $self->{_tex_id} = ""; $self->{_vertex_indices} = []; $self->{_parent_sector} = $parent; bless ($self, $class); return $self;

## methods to access per-object data ##

sub get_is_invisible { my $self = shift; return $self->{_is_invisible};

sub set_is_invisible { my $self = shift; my $val = shift; $self->{_is_invisible}= $val;

sub get_tex_id { my $self = shift; return $self->{_tex_id};

sub set_tex_id { my $self = shift; my $id = shift; $self->{_tex_id}= $id;

sub get_parent_sector {

return $self->{_parent_sector};

sub set_parent_sector { my $self = shift; my $parent = shift; $self->{_parent_sector}= $parent;

sub get_vertex_index { my $self = shift; my $position = shift;

return $self->{_vertex_indices}[$position];

sub get_vertex_index_count { my $self = shift;

sub add_vertex_index { my $self = shift; my $index = shift;

#sub get_vertex_index_list {

my @edge_list;

for($i=0; $i <= $self->get_vertex_index_count(); $i++) { my $j;

$edge_list[$i] = [ $self->get_vertex_index($i) ]; $j = $i + 1;

if($j > $self->get_vertex_index_count()) { $j = 0;

push @{$edge_list[$i]}, $self->get_vertex_index($j);

return @edge_list;

sub contains_edge { my $self = shift; my $idx0 = shift; my $idx1 = shift;

for( my $i=0; ( $i <= $#edge_list ) && ( !$found ); $i++ ) { if ( ( ( $edge_list[$i][0] == $idx0 ) && ( $edge_list[$i][1] == $idx1 ) ) ||( ( $edge_list[$i][o] == $idx1 ) && ( $edge_list[$i][l] == $idx0 ) ) )

return $found;

sub coincident_with_facet { my $self = shift; my $epsilon = 1.001;

for ( my $i = 0; ($i <= $self->get_vertex_index_count()) && $result; $i++ ) { my $vertex_found_in_other = undef; for ( my $other_i = 0;

($other_i <= $other_facet->get_vertex_index_count())

my $parent = $self->get_parent_sector(); my $other_parent = $other_facet->get_parent_sector(); if(

(abs($parent->get_vertex($self->get_vertex_index($i)) -> x() -$other_parent->get_vertex

($other_facet->get_vertex_index($other_i))->x())

&&(abs($parent->get_vertex($self->get_vertex_index($i)) -> y() -$other_parent->get_vertex

($other_facet->get_vertex_index($other_i))->y())

&&(abs($parent->get_vertex($self->get_vertex_index($i)) -> z() -$other_parent->get_vertex

($other_facet->get_vertex_index($other_i))->z())

$vertex_found_in_other = 1;

return $result;

$v1->x ( $self->get_parent_sector()->get_vertex ($self->get_vertex_index(0)) -> x ); $v1->y ( $self->get_parent_sector()->get_vertex

($self->get_vertex_index(0)) -> y() ); $v1->z ( $self->get_parent_sector()->get_vertex

($self->get_vertex_index(0)) -> z() ); $v2->x ( $self->get_parent_sector()->get_vertex

($self->get_vertex_index(1)) -> x() ); $v2->y ( $self->get_parent_sector()->get_vertex

($self->get_vertex_index(1)) -> y() ); $v2->z ( $self->get_parent_sector()->get_vertex

($self->get_vertex_index(1)) -> z() ); $v3->x ( $self->get_parent_sector()->get_vertex

($self->get_vertex_index(2)) -> x() ); $v3->y ( $self->get_parent_sector()->get_vertex

($self->get_vertex_index(2)) -> y() ); $v3->z ( $self->get_parent_sector()->get_vertex ($self->get_vertex_index(2)) -> z() );

# try origin at v1

if ( $v2->dif($v1)->dot($v3->dif($v1)) < $epsilon) { if ($debug) {print "origin v1"; ) return {o => $v1, v => $v3, u => $v2 };

# try origin at v2

if ( $v1->dif($v2)->dot($v3->dif($v2)) < $epsilon) { if ( $debug ) {print "origin v2"; ) return {o => $v2, v => $v1, u => $v3 };

# try origin at v3

if ( $v1->dif($v3)->dot($v2->dif($v3)) < $epsilon) { if ( $debug ) {print "origin v3"; ) return {o => $v3, v => $v2, u => $v1 };

if ( $debug ) { print "Hm... no origin found!" };

print "WARNING: Invalid texture definition triangle found";

print " (orientation could not be determined).";

1; # so the require or use succeeds

Texture.pm

Module Texture.pm represents a texture image and orientation. It stores a texture space, the name of a texture image file, and a unique string which identifies the texture object itself. Textures can be assigned to facets, as we mentioned earlier. Importantly, notice that assigning a Texture to a Facet not only assigns the image to the facet, but also the orientation defined in the Texture.

Member variable _tex_id is a string identifying this object. Its purpose is to allow us to define a single texture image and orientation, and assign a name to it, such as stony_ceiling. This way, we can set all polygons located in the ceiling of a room to use the texture stony_ceiling, which means that they all share the same texture image and the same texture space. This allows all polygons forming the ceiling, no matter how oddly shaped they are, to line up seamlessly on the edges, since they all share the same texture space.

Member variables _u_vec, _v_vec, and _origin define the texture space in terms of the tip of the u axis, the tip of the v axis, and the texture space origin.

Member variable _image is a string containing the filename of the texture image associated with this texture object.

Listing 6-3: Texture.pm package Texture; use strict;

use Portals::Vertex;

## the object constructor ##

my $class = ref($proto) || $proto; my $self = {}; $self->{_tex_id) = ""; $self->{_u_vec} = Vertex->new();

$self->{_v_vec} = Vertex->new(); $self->{_origin} = Vertex->new(); $self->{_image} = ""; bless ($self, $class); return $self;

## methods to access per-object data ##

sub get_tex_id { my $self = shift; return $self->{_tex_id};

sub set_tex_id { my $self = shift; my $id = shift; $self->{_tex_id}= $id;

sub get_u_vec { my $self = shift; return $self->{_u_vec};

sub set_u_vec { my $self = shift; my $vec = shift; $self->{_u_vec}= $vec;

sub get_v_vec { my $self = shift; return $self->{_v_vec};

sub set_v_vec { my $self = shift; my $vec = shift; $self->{_v_vec}= $vec;

sub get_origin { my $self = shift; return $self->{_origin};

sub set_origin { my $self = shift; my $o = shift; $self->{_origin}= $o;

sub set_image { my $self = shift; my $i = shift; $self->{_image}= $i;

1; # so the require or use succeeds

Portal.pm

Module Portal.pm represents a portal polygon. It inherits from the Facet class.

Member variable _target_sector (which, incidentally, is not explicitly created in the constructor, but is instead dynamically created upon assignment via method set_target_ sector) is a reference to a sector object, to which the portal polygon leads. Listing 6-4: Portal.pm package Portal;

sub get_target_sector { my $self = shift; return $self->{_target_sector};

sub set_target_sector { my $self = shift; my $target = shift; $self->{_target_sector}= $target;

Sector.pm

Module Sector.pm represents a sector containing both geometric polygons and portal polygons leading to other sectors. It contains the logic for generating portals based on the holes in the sector geometry.

Member variable _name is a unique string identifier for this sector.

Member variable _vertices is a list of vertices of type Vertex. The vertices are accessible by an integer index indicating their position in the list.

Member variable _facets is alist of geometric polygons in the sectormesh. The polygons are of type Facet.

Member variable _portals is a list of portal polygons in the sector mesh and are of type Portal.

Member variable _nonlooped_portals is a list of incomplete portal polygons which could not be completely formed because the free edges did not form a closed loop, which is necessary for a valid portal polygon. This list can be printed for error checking purposes.

Member variable _nonlinked_portals is a list of invalid portal polygons for which no corresponding overlapping portal could be found, meaning that the portal could not be linked to any other sector.

Member variable _free_edges is a list of all free edges among all polygons in the sector mesh. It is filled through private method _find_free_edges.

Member variable _actors is a list of all actor objects (plug-in objects) which have been initially assigned to this sector. We see later how to use Blender to specify the location of actors.

Member variables _node_min_{x,y,z} and _node_max_{x,y,z} store an axially aligned bounding box for the sector, in terms of the minimum and maximum corner points.

Member variable _has_geometry indicates whether or not the sector contains any geometry. Normally it will return a true value; however, certain automatic sector generation schemes (discussed at the end of this chapter) can result in the creation of empty sectors containing no geometry, in which case this variable returns a false value.

Private method _find_free_edges is the first part of the portal generation process. It scans for free edges among all polygons within the sector. The logic is as follows. For each polygon, we loop through all of its edges. For each edge, we see if any other polygon edge in the sector contains the same edge. If so, the edge is used by more than one polygon, and cannot be a free edge. If not, the edge is only used by one polygon, and is thus a free edge. After execution of this method, member variable _free_edges contains the free edge list.

Private method _merge_free_edges_into_portals is the second part of the portal generation process. Given the list of free edges, we then proceed to find continuous loops of free edges. Each such loop is a portal. We proceed simply by starting with one free edge, which is a pair of vertices. Then, we try to daisy chain to the next free edge, by finding another free edge whose starting vertex is the same as the ending vertex of the current free edge. In this manner, we build up a loop, free edge by free edge. If we finally arrive at the starting free edge again, we have completed the loop, and can add it to the sector's list of portals. If any free edge loop can be started but not completed (i.e., if we do not finally arrive back at the starting free edge), then the input data was partially erroneous, and we have a non-looped portal.

Public method make_portals_from_holes simply calls _find_free_edges and _merge_free_edges_into_portals in sequence, and is the interface for external users to create portal polygons for this sector.

Listing 6-5: Sector.pm package Sector; use strict; use Portals::Facet; use Portals::Portal;

use Portals::Vertex;

## the object constructor ##

my $proto = shift; my $class = ref($proto) || $proto; my $self = {}; $self->{_name} = undef;

vertices}= {}; facets} = {}; portals} = {}; actors}= {}; nonlooped_portals}= {}; nonlinked_portals}= {}; free_edges} = []; has_geometry}= undef; node_min_x}=999999; node_min_y}=999999; node_min_z}=999999; node_max_x}=-999999; node_max_y}=-999999; node_max_z}=-999999;

## methods to access per-object data ##

if (@_) {$self->{_node_min_x}= shift } return $self->{_node_min_x};

if (@_) {$self->{_node_min_y}= shift } return $self->{_node_min_y};

if (@_) {$self->{_node_min_z}= shift } return $self->{_node_min_z};

if (@_) {$self->{_node_max_x}= shift } return $self->{_node_max_x};

if (@_) {$self->{_node_max_y}= shift } return $self->{_node_max_y};

$se

f

>

$se

f

>

$se

f

>

$se

f

>

$se

f

>

$se

f

>

$se

f

>

$se

f

>

$se

f

>

$se

f

>

$se

f

>

$se

f

>

$se

f

>

$se

f

>

if (@_) {$self->{_node_max_z}= shift } return $self->{_node_max_z};

if (@_) {$self->{_has_geometry}= shift } return $self->{_has_geometry};

sub name {

sub get_all_vertices { my $self = shift;

if (@_) {$self->{_vertices}= shift } return $self->{_vertices};

sub get_vertex {

sub add_vertex {

my $self = shift; my $vertex_index = shift; my $vertex = shift;

$self->{_vertices}->{$vertex_index}= $vertex;

#if (@_) {@{$self->{_facets}}= @_ } #return @{$self->{_facets}};

sub get_facet { my $self= shift; my $facet_index = shift; return $self->{_facets}->{$facet_index};

sub add_facet {

my $self = shift; my $facet_index = shift; my $facet = shift;

if (@_) {$self->{_actors}= shift } return $self->{_actors};

sub add_actor {

$self->{_actors}->{$actor->name()}= $actor;

sub get_actor {

if (@_) {$self->{_portals}= shift } return $self->{_portals};

sub get_portal { my $self= shift; my $portal_index = shift; return $self->{_portals}->{$portal_index};

sub add_portal { my $self = shift; my $portal_index = shift; my $portal = shift;

sub delete_portal { my $self = shift; my $portal = shift;

for my $a_index ( keys %{$self->get_all_portals()}) { if ($self->get_portal($a_index) == $portal) { print STDERR "Portal deleted."; delete $self->{_portals}->{$a_index};

sub make_portals_from_holes { my $self = shift;

printf(STDERR "Making portals $self->_find_free_edges(); $self->_merge_free_edges_into

sub add_nonlooped_portal { my $self = shift; my $portal_index = shift; my $portal = shift;

$self->{_nonlooped_portals}{$portal_index}= $portal;

sub get_nonlooped_portal { my $self= shift; my $portal_index = shift;

return $self->{_nonlooped_portals}->{$portal_index};

sub get_all_nonlooped_portals { my $self = shift;

return $self->{_nonlooped_portals};

sub add_nonlinked_portal { my $self = shift; my $portal_index = shift; my $portal = shift;

$self->{_nonlinked_portals}{$portal_index}= $portal;

sub get_all_nonlinked_portals { my $self = shift;

return $self->{_nonlinked_portals};

sub get_nonlinked_portal { my $self= shift; my $portal_index = shift;

return $self->{_nonlinked_portals}->{$portal_index};

###################### PRIVATE #######################

my $aFacet_key; my $aFacet; my $aOtherFacet_key; my $aOtherFacet; my @edge_list;

print STDERR "Scanning for free edges, Sector ", $aSector->name(), ""; for $aFacet_key ( keys % {$aSector->get_all_facets() }) { $aFacet = $aSector->get_facet($aFacet_key); print STDERR " Facet ", $aFacet_key, ""; @edge_list = $aFacet->get_edge_list(); for ( my $i=0; $i<=$#edge_list; $i++) { my $edge_taken = undef;

for $aOtherFacet_key ( keys % {$aSector->get_all_facets() }) { if($aOtherFacet_key != $aFacet_key) { # for all OTHER facets $aOtherFacet = $aSector->get_facet($aOtherFacet_key);

if($aOtherFacet ->contains_edge($edge_list[$i][0],$edge_list[$i][1])) {

" FREE EDGE ", $edge_list[$i][0]," ", $edge_list[$i][1], ""; push @{$self->get_free_edges()}, $edge_list[$i] ;

print STDERR " Summary of found free edges:"; for ( my $i=0; $i<=$#{$self->get_free_edges()b $i++) { print STDERR " ";

print STDERR ${@{$self->get_free_edgesO}[$i]}[0]," "; print STDERR ${@{$self->get_free_edges()}[$i]}[1],"";

sub _merge_free_edges_into_portals { my $self = shift; my $portal;

# note that we must link the edges from pt1 to pt0 instead of pt0 to pt1

# because we must reverse the orientation of the edges to make the portal

# normal point the same direction as the neighboring facets' normals.

my $unlooped_portal_num = 0;

while ( ( $#{$self->get_free_edges()}>= 0 ) ) {

print STDERR " Creating new portal."; $portal = Portal->new($self);

$self->add_portal(sprintf("%d",$portal_num), $portal); my $e_idx = 0;

my $idx1 = ${@{$self->get_free_edges()}[$e_idx]}[1]; my $idx0 = ${@{$self->get_free_edges()}[$e_idx]}[0];

# add current vertex to vertex list

splice ( @{$self->get_free_edges()}, $e_idx, 1 ); # remove current edge print STDERR " Starting vertex $idx1.";

while ( ( $idx0 != $first_idx ) && !$error ) {

# keep going through vertex pairs until you hit the starting vertex again

# find daisy-chained edge my $i;

for ( $i=0; ($i<=$#{$self->get_free_edges()}) && (!$done); $i++) { my $candidate_idx1 = ${@{$self->get_free_edges()}[$i]}[1]; my $candidate_idx0 = ${@{$self->get_free_edges()}[$i]}[o];

if ( $candidate_idx1 == $idx0 ) { $idx1 = $candidate_idx1; $idx0 = $candidate_idx0;

# add current vertex to vertex list $portal->add_vertex_index( $idx1 );

print STDERR " Daisy-chaining vertex $idx1.";

# remove current edge splice ( @{$self->get_free_edges()}, $e_idx, 1 ); $done = 1;

# the videoscape format appears to arbitrarily reverse

# the order of vertices in two-vertex "faces" (probably since

# no normal vector orientation can be computed based on two

# vertices), so we have to also check for a matching edge in

# the other direction, i.e. edge 0-1 and 1-3 daisy chains to 0-1-3,

# but so does 0-1 and 3-1 (since 3-1 is the same as 1-3) elsif ( $candidate_idx0 == $idx0 ) {

# add current vertex to vertex list $portal->add_vertex_index( $idx1 );

print STDERR " Daisy-chaining vertex $idx1.";

# remove current edge splice ( @{$self->get_free_edges()}, $e_idx, 1 ); $done = 1;

"Uh oh, free edges couldn't be joined into a loop; skipping..."; $self->delete_portal($portal);

$self->add_nonlooped_portal(sprintf("%d",$unlooped_portal_num++), $portal);

if ( ! $error ) { print STDERR " Portal complete."; $portal_num++;

1; # so the require or use succeeds

Actor.pm

Module Actor.pm represents a plug-in object, or actor. Later in this chapter, we see how to specify actors in Blender.

Member variable _name is a string uniquely identifying the actor.

Member variable _parent is the sector object in which this actor initially resides; member variable _parent_name is the name of this sector object.

Member variable _orientation is a string containing the nine elements of the object's rotation matrix. A more flexible approach would store the rotation matrix as an array where each element is individually accessible, but in this case, we don't actually use the rotation matrix; we simply read it from the mesh, and rewrite it to the world file. This is why the orientation is stored as a simple string.

Member variable _position is a string containing the coordinates of the object's position. As with the orientation, the string storage format is used because we do not do any manipulation of the position.

Member variable _is_camera reflects whether or not the current plug-in object under consideration is the main camera in the scene. According to the world file format in Chapter 5, the camera is specified by a CAMERA line in the world file, whereas other plug-in objects are specified with an ACTOR line; thus, we need to differentiate between the two.

Member variable _meshfile is the name of the Videoscape file containing the geometry for this plug-in object. As we touched upon earlier and as we see later in more detail, we use simple cubes in Blender as placeholders for plug-in objects; the actual plug-in geometry is defined by this separate mesh file.

Member variable _uvfile is the name of the file containing the texture coordinates for the mesh.

Member variable _texturefile is the name of the file containing the texture image for the mesh.

Member variable _pluginfile is the name of the dynamic library file controlling the behavior of this plug-in object. Listing 6-6: Actor.pm package Actor;

use strict;

use Portals::Facet;

use Portals::Portal;

use Portals::Vertex;

## the object constructor ##

$sel

f

>{

name} = undef;

$sel

f

>{

parent}= undef;

$sel

f

>{

parent name}= undef;

$sel

f

>{

orientation}= undef;

$sel

f

>{

position} = undef;

$sel

f

>{

is camera} = undef;

$sel

f

>{

meshfile} = undef;

$sel

f

>{

uvfile}= undef;

$sel

f

>{

texturefile}= undef;

$sel

f

>{

pluginfile} = undef;

## methods to access per-object data ##

sub name {

if (@_) {$self->{_parent_name}= shift ) return $self->{_parent_name};

sub parent {

if (@_) {$self->{_parent}= shift } return $self->{_parent};

sub is_camera {

if (@_) {$self->{_is_camera}= shift } return $self->{_is_camera};

sub meshfile {

sub uvfile {

if (@_) {$self->{_uvfile} = shift } return $self->{_uvfile};

sub texturefile { my $self = shift;

if (@_) {$self->{_texturefile}= shift } return $self->{_texturefile};

sub pluginfile {

if (@_) {$self->{_pluginfile} = shift } return $self->{_pluginfile};

sub orientation { my $self = shift;

if (@_) {$self->{_orientation}= shift } return $self->{_orientation};

sub position {

if (@_) {$self->{_position}= shift } return $self->{_position};

1; # so the require or use succeeds

World.pm

Module World.pm is the highest-level structural module, which represents a portal world consisting of sectors and actors. Essentially, we parse all exported Videoscape files and store them into a World object, which we then traverse to print out the final portal world file.

Member variable _sectors is a list of sector objects, of type Sector, belonging to this world. For each Videoscape file, there is one sector object.

Member variable _textures is a list of all textures, of type Texture, available in the world. Remember that a Texture specifies both an image and an orientation.

Member variable _texture_imagenums is a unique, numbered list of all texture images referenced by all Texture objects in the _textures list. The idea is that if several Texture objects use the same texture image (but with different orientations), the texture image should not be loaded more than once. By collecting all texture images into a unique list, we prevent unnecessary duplication of texture images. We can reference each image in the unique texture image list by a numerical identifier, which, not coincidentally, is also how the world file format refers to textures (by number).

Member variables _min{x,y,z} and _max{x,y,z} store the bounding box of all geometry in the world, in terms of minimum and maximum corner points. Member variables _nodesize{x,y,z} store predefined dimensions of a box. If we were using a regular spatial partitioning scheme (see the end of this chapter), we could divide the bounding box of all geometry into smaller boxes with dimensions specified by _nodesize{x,y,z}.

Method link_portals is the last part of automatic portal generation. Within the Sector class, we first found all free edges, then linked free edges into portals belonging to the sector. After doing this for all sectors, the last step is to find overlapping portals. For all sectors, for all portals, we must link each portal to the sector containing its overlapping counterpart. In other words, given a portal A in one sector, we scan for a portal B in another sector which exactly overlaps A. If we find such a portal B, then we link A to the sector containing B. If we find no such corresponding portal B, then this is an error, and A is a non-linked portal which should be deleted from its containing sector. Listing 6-7: World.pm package World;

use strict;

use Portals::Sector;

use Portals::Texture;

## the object constructor ##

$se

f

>{ sectors} = {};

$se

f

>{ textures} = {};

$se

f

>{ texture imagenums} = {};

$se

f

>{_minx} = 500000;

$se

f

>{ maxx} = -500000;

$se

f

>{_miny} = 500000;

$se

f

>{_maxy} = -500000;

$se

f

>{_minz} = 500000;

$se

f

>{_maxz} = -500000;

$se

f

>{ nodesizex} = 200;

$se

f

>{ nodesizey} = 200;

$se

f

>{ nodesizez} = 200;

## methods to access per-object data ##

sub get_nodesizex {

return $self->{_nodesizex};

sub get_nodesizey { my $self = shift; return $self->{_nodesizey};

sub get_nodesizez { my $self = shift; return $self->{_nodesizez};

sub get_minx {

sub get_miny {

sub get_minz {

sub get_maxx {

sub get_maxy {

sub get_maxz {

sub set_minx {

my $self = shift; my $v = shift; $self->{_minx}= $v;

sub set_miny {

my $self = shift; my $v = shift; $self->{_miny}= $v;

sub set_minz {

my $self = shift; my $v = shift; $self->{_minz}= $v;

sub set_maxx {

my $self = shift; my $v = shift; $self->{_maxx)= $v;

sub set_maxy {

my $self = shift; my $v = shift; $self->{_maxy)= $v;

sub set_maxz {

my $self = shift; my $v = shift; $self->{_maxz)= $v;

sub get_nodesizex { my $self = shift; return $self->{_nodesizex);

sub get_nodesizey { my $self = shift; return $self->{_nodesizey);

sub get_nodesizez { my $self = shift; return $self->{_nodesizez);

sub get_sector {

sub add_sector {

my $self = shift; my $sector_name = shift; my $sector = shift;

sub get_all_textures { my $self = shift;

sub get_texture { my $self = shift; my $tex_id = shift;

sub add_texture { my $self = shift; my $tex_id = shift; my $tex = shift;

sub get_all_texture_imagenums { my $self = shift;

return $self->{_texture_imagenums);

sub get_texture_imagenum { my $self = shift; my $texi_id = shift;

return $self->{_texture_imagenums)->{$texi_id);

sub set_texture_imagenum { my $self = shift; my $texi_id = shift; my $texi = shift;

$self->{_texture_imagenums)->{$texi_id)= $texi;

my $aSector_key; my $aSector; my $aPortal_key; my $aPortal; my $aOtherSector_key; my $aOtherSector; my $aOtherPortal_key; my $aOtherPortal;

for $aSector_key ( keys % {$self->get_all_sectors() )) { my $unlinked_portal_num = 0; $aSector = $self->get_sector($aSector_key);

print STDERR "Linking portals from Sector $aSector_key."; for $aPortal_key ( keys % {$aSector->get_all_portals() )) { $aPortal = $aSector->get_portal($aPortal_key); if ($aPortal->get_target_sector()) { print STDERR " Already assigned other side of portal $aPortal_key"; print STDERR "(Sector ", $aPortal->get_target_sector()->name(), ")."; )else {

print STDERR " Searching for other side of portal $aPortal_key."; my $portal_linked = undef;

for $aOtherSector_key ( keys % {$self->get_all_sectors() }) { if ($aOtherSector_key ne $aSector_key) { $aOtherSector = $self->get_sector($aOtherSector_key); for $aOtherPortal_key (keys %{$aOtherSector->get_all_portals()}) { $aOtherPortal = $aOtherSector->get_portal($aOtherPortal_key); if ( $aPortal->coincident_with_facet($aOtherPortal) ) { $portal_linked = 1;

print STDERR " Coincides with Sector $aOtherSector_key,"; print STDERR " Portal $aOtherPortal_key"; $aPortal->set_target_sector($aOtherSector); $aOtherPortal->set_target_sector($aSector); #reverse link

if ( ! $portal_linked) { print STDERR " No link found!"; $aSector->delete_portal($aPortal);

$aSector->add_nonlinked_portal(sprintf("%d",$unlinked_portal_num++),

$aPortal);

1; # so the require or use succeeds

Parsing and Generator Modules

We've now seen the Perl modules which store the structure of the entire portal world in memory. These structures form the middle stage of a pipeline. The input to the pipeline comes from a parser, which parses the Videoscape files and fills the world structures accordingly. On the output side, the world data is then fed through a generator, which traverses the world structure in memory and writes as output a valid portal world file to disk, conforming to the format specified in Chapter 5.

The next sections look at the input (parser) and output (generator) classes of the Perl portalization system.

VidscParser.pm

Module VidscParser.pm is a parser for the Videoscape file format. It only has one member variable, _world, which is the World object that will be filled by the parser.

Method parse reads all input files specified on the command line (which should be all Videoscape files forming the world), parses them to find the definitions of the geometric polygons, and stores these polygons in the world object. For now, you can ignore most of the parse routine, because most of it deals with the extraction of attribute information from the mesh, which we cover later in this chapter. The code which now interests us begins at the block marked "all untagged meshes are treated as sectors." Here, we create and fill a new sector object. We simply read in the facet definitions from the Videoscape file, change the coordinates from a right-handed to a left-handed system, and store these facets in the current sector object. We do this for all

Videoscape files, since one Videoscape file represents one sector. The next code block of interest then begins at the line marked "link portals together." At this point in the code, we have already read in and parsed all facet definitions for all sectors, and have stored these in memory. So, we call make_portals_from_holes for each sector, then call link_portals for the world to link all portals among all sectors. At this point, the sector objects in memory now contain both the geometry polygons and the portals, which are linked to their connected sectors. The data is ready to be written to disk by one of the generator classes, which we cover next.

Listing 6-8: VidscParser.pm package VidscParser;

# defines variable $Bin, which is dir from which script was invoked use FindBin;

use lib "$FindBin::Bin";

use strict; use Portals::World; use Portals::Actor; use FileHandle;

my $id_extraction_program = "$FindBin::Bin/../vidinfo/vidinfo"; my $attrib_filename_format_str = "attrib%d.dat";

## the object constructor ##

$self->{_world} = World->new(); bless ($self, $class); return $self;

## methods to access per-object data ##

sub get_world {

for (my $file_idx=0; $file_idx <= $#files; $file_idx++) { my @mesh_properties; my $mesh_type; my $mesh_name;

my $cmd = join(" ", $id_extraction_program, $files[$file_idx]); my @extracted_info = ~$cmd~; my $extracted_id = $extracted_info[0]; if($extracted_id) { my $attrib_file = sprintf($attrib_filename_format_str, $extracted_id);

my @attrib_dir_tokens = split('/', $files[$file_idx]); pop @attrib_dir_tokens; # get path of current videoscape file $attrib_dir = join("/", @attrib_dir_tokens); if( length($attrib_dir) ) {

$attrib_file = join("/",$attrib_dir, $attrib_file); }else {

$attrib_file = $attrib_file;

my $fh = FileHandle->new(); $fh->open($attrib_file); while(<$fh>) { push @mesh_properties, $_;

my @mesh_types = grep( /^TYPE / , @mesh_properties); $mesh_type = $mesh_types[0]; my @mesh_tokens = split(' ', $mesh_type); $mesh_type = $mesh_tokens[1];

my @mesh_names = grep( /^NAME / , @mesh_properties); $mesh_name = $mesh_names[0]; my @meshname_tokens = split(' ', $mesh_name); $mesh_name= $meshname_tokens[1]; }else { $mesh_type = undef; $mesh_name = undef;

if (lc($mesh_type) eq "actor") { my $actor = Actor->new(); if(length($mesh_name)) {

$actor->name(sprintf("ACTOR%d",$file_idx));

my @mesh_matches; my $mesh_match; my @tokens;

@mesh_matches = grep( /^PARENT / , @mesh_properties);

$actor->parent_name($mesh_match);

@mesh_matches = grep( /~IS_CAMERA / , @mesh_properties); $mesh_match = $mesh_matches[0]; @tokens = split(' ', $mesh_match); $mesh_match = $tokens[1]; if($mesh_match) { $actor->is_camera($mesh_match);

@mesh_matches = grep( /^MESH / , @mesh_properties); $mesh_match = $mesh_matches[0]; @tokens = split(' ', $mesh_match); $mesh_match = $tokens[1]; if($mesh_match) { $actor->meshfile($mesh_match);

@mesh_matches = grep( /^TEXCOORDS / , @mesh_properties); $mesh_match = $mesh_matches[0]; @tokens = split(' ', $mesh_match); $mesh_match = $tokens[1]; if($mesh_match) { $actor->uvfile($mesh_match);

@mesh_matches = grep( /^TEXTURE / , @mesh_properties); $mesh_match = $mesh_matches[0]; @tokens = split(' ', $mesh_match); $mesh_match = $tokens[1]; if($mesh_match) { $actor->texturefile($mesh_match);

@mesh_matches = grep( /^PLUGIN / , @mesh_properties); $mesh_match = $mesh_matches[0]; @tokens = split(' ', $mesh_match); $mesh_match = $tokens[1]; if($mesh_match) { $actor->pluginfile($mesh_match);

my $loc = $extracted_info[1]; my $or_row0 = $extracted_info[2]; my $or_row1 = $extracted_info[3]; my $or_row2 = $extracted_info[4]; $or_row0 =~ s/ $or_row1 =~ s/ $or_row2 =~ s/ $loc =~ s/

$loc = join(" $loc_parts[0], $loc_parts[2], $loc_parts[1]);

# to change orientation from rhs to lhs we must do two things:

# 1) swap the y and z columns in the matrix

# 2) swap the y and z rows in the matrix my @row_parts = split(' ', $or_row0);

$or_row0 = join(" ", $row_parts[0], $row_parts[2], $row_parts[1]);

$or_row1 = join(" ", $row_parts[0], $row_parts[2], $row_parts[1]); @row_parts = split(' ', $or_row2);

$or_row2 = join(" ", $row_parts[0], $row_parts[2], $row_parts[1]); $actor->position($loc);

$actor->orientation(join(" ", $or_row0, $or_row2, $or_row1)); push @actors, $actor;

else # elsif(lc($mesh_type) eq "sector")

########################################################################

# all untagged meshes are treated as sectors

########################################################################

$sector->name(sprintf("S%d",$file_idx));

$self->get_world()->add_sector($sector->name(), $sector);

my %sectors; undef %sectors;

if ($debug) {print "$debug_str $files[$file_idx] opened"; } my $id = <FILE>;

# read in vertex list from file for (my $i=0; $i<$vertex_count; $i++) { my $vertex = Vertex->new();

$sector->add_vertex( sprintf("%d",$i), $vertex ); my $line = <FILE>;

# blender/videoscape uses a +z-up RHS system; we use a +y-up LHS system.

# read in facet definitions from file my @face_properties = grep( /^FACE / , @mesh_properties);

print STDERR "Mesh properties:--";

print STDERR @mesh_properties;

print STDERR "Face properties:--";

print STDERR @face_properties;

i f( $list[0] < 3 ) { next; # this "polygon" has less than three edges: either it is

# a special ID flag, or it is a modeling error, but it

# certainly is not geometry we need to write to the final

# world file

pop @list; # pop color off list shift @list; # don't care about vertex index count my $facet = Facet->new($sector); $facet->set_is_invisible(0); # may be changed below

# we add the facet to the sector object LATER, after it is determined

# if it is visible or not (if not it is just there to define a

# texture orientation)

my @this_face_properties =

print STDERR @this_face_properties;

# we count the vertex indices in reverse because blender/videoscape

# normally store the vertices counterclockwise(rhs) whereas we use

# clockwise (rhs)

for(my $i=$#list; $i>=0; $i-) { $facet->add_vertex index( $list[$i] );

my $tex_image_name;

my @matching_texspace_lines =

grep( /_TEX_SPACE/ , @this_face_properties); if($#matching_texspace_lines > -1) {

# a polygon should EITHER use OR define a texture space, not both.

# also, a polygon can't use or define multiple textures. so, we

# just take the first matching line with _TEX_SPACE and extract the

# texture id from it.

my @matching_texspace_tokens =

# joining sector name with tex id name ensures uniqueness among

# reused texture space names among sectors. not joining it with sector

# name allows texture spaces to be reused across sectors, since

# the texture space list is global in the world, not local in the sector. $tex_id = join(".", $sector->name(), $matching_texspace_tokens[3]); $tex_image_name = $matching_texspace_tokens[4];

if ( grep( /IS_TEX_SPACE/ , @this_face_properties )

&& !grep( /IS_INVISIBLE/, @this_face_properties ) ) {

if ($facet->get_vertex_index_count() != 2) { printf(STDERR

"Non-triangle marked as geometry and tex-def-tri. ID: %s.", $tex_id);

printf(STDERR "Geometry and tex-def-tri found. ID: %s", $tex_id);

$self->get_world()->set_texture_imagenum($tex_image_name, "dummy");

# we just insert the image name as the hash KEY into the hash;

# the value, which is the numerical index, is assigned later

# in l3dGen after all tex images have been defined.

# using a hash ensures uniqueness among the keys.

$self->get_world()->add_texture(sprintf("%s",$tex_id), $tex);

}elsif ( grep( /IS_TEX_SPACE/ , @this_face_properties ) && grep( /IS_INVISIBLE/, @this_face_properties ) )

if ($facet->get_vertex_index_count() != 2) { printf(STDERR

"Non-triangle marked as pure tex-def-tri. ID: %s.", $tex_id);

}else { printf(STDERR

"Pure tex-def-tri found. ID: %s", $tex_id); $facet->set_is_invisible(1); # face not to be written to world file $facet->set_tex_id($tex_id);

$self->get_world()->set_texture_imagenum($tex_image_name, "dummy");

# we just insert the image name as the hash KEY into the hash;

# the value, which is the numerical index, is assigned later

# in l3dGen after all tex images have been defined.

# using a hash ensures uniqueness among the keys.

$self->get_world()->add_texture(sprintf("%s",$tex_id), $tex);

}elsif ( grep( /USES_TEX_SPACE/ , @this_face_properties ) ) { printf(STDERR "Geometry poly num %d linked to tex ID: %s",

$facet_number, $tex_id); $facet->set_tex_id($tex_id); }else {

printf(STDERR "Normal Geometry poly num %d", $facet_number);

# if facet was not invisible, add it to the world file if($facet->get_is_invisible() == 0) { $sector->add_facet( sprintf("%d",$facet_number), $facet );

# link portals together my $aSector_key;

my $aSector;

for $aSector_key ( keys % {$self->get_world()->get_all_sectors() }) { $aSector = $self->get_world()->get_sector($aSector_key); $aSector->make_portals_from_holes();

# assign actors to sectors print STDERR "Now assigning ", $#actors + 1, " actors to their sectors.";

my $i;<

Was this article helpful?

0 0

Post a comment