Exporting and Importing Blender Models

Models created in Blender can be imported into l3d programs. The Blender file format is very complex and not documented for external users. For this reason, we need to export the Blender models in a different file format in order to import them into l3d programs. The simplest export format offered by Blender is the Videoscape format. This file format is simple and straightforward it contains vertices and polygons defined in terms of indices into a common vertex list. Conveniently, this is...

Summary of l3d Classes

Figure 1-11 illustrates the major l3d classes covered up to this point. Study the previously presented drawdot program to keep a practical perspective on the use of the l3d classes, and remember the five-step process for creating l3d applications. Also, remember that the CD-ROM contains complete source code listings for all of these classes, and the introductory companion book Linux 3D Graphics Programming develops the classes in detail, with several example programs. Figure 1-11 Class diagram...

Data Flow within the World Editing System

Figure 6-10 shows the flow of data which takes place when creating a world file from a series of Blender meshes. The data flow diagram does not show control flow it makes no statement about any execution order. The purpose of the diagram is to show how Blender meshes get transformed into the world file. Figure 6-10 shows the flow of data which takes place when creating a world file from a series of Blender meshes. The data flow diagram does not show control flow it makes no statement about any...

The RPlay Server

RPlay is a flexible network sound server which allows sounds to be played to and from local and remote Unix systems. It can play multiple simultaneous sounds with differing volumes, understands common formats (au, wav, voc, raw, and many others), can be extended to play arbitrary sound formats through helper applications, supports audio CD tracks, has an event notification mechanism, and runs parallel to the application program. Since RPlay is a separate server program, which incidentally can...

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...

Step 4 Create a Pipeline

The fourth step in creating an l3d application is to create your pipeline object. This step is easy. Having already declared and defined an l3d_pipeline subclass, which fulfills the three pipeline responsibilities (creating screen-access objects, declaring world data, and overriding event-handling functions), we simply create the pipeline directly with the C++ new operator. This, in turn, invokes the pipeline's constructor, which creates the screen, rasterizer implementation, and rasterizer...

Fixed and Floating Point Math

In 3D graphics, we generally need to be able to store and manipulate fractional values. For this, we introduce the type l3d_real. The purpose of the l3d_real type is to allow all computations using real values to be performed using either floating-point or fixed-point arithmetic. Floating-point arithmetic is done by using the C type float, and for good real-time performance requires a hardware floating-point unit. Fixed-point arithmetic requires no floating-point unit in hardware, and simulates...

Graphics Fundamentals

3D graphics is the creation of a two-dimensional image or series of images on a flat computer screen such that the visual interpretation of the image or series of images is that of a three-dimensional image or series of images. Figure 1-2 Definition of 3D graphics. Figure 1-2 Definition of 3D graphics. The visual interpretation of an image depends on the optics of light rays striking the retina. Points emit light radially in all directions along straight lines, called light rays. Some subset of...

Bump Mapping

Bump mapping is a technique used to give a flat surface the appearance of having small surface perturbations, or bumps and pits. Bump mapping is similar to texture mapping in that it uses a 2D image map, the bump map, whose contents are used to vary the surface normal of a polygon during rasterization on a per-pixel basis. The modified surface normal is then used to compute lighting. Because the lighting computation depends on the surface normal, the modified surface normal gives the appearance...

Edge Collapse

An algorithmic means of simplifying a triangular mesh relies on edge collapse operations HOPP96 . The algorithm starts with amesh consisting exclusively of triangles if other arbitrary polygons are in the mesh, they should first be tessellated to triangles. Then, we make the mesh simpler by moving two separate vertices to one location. By doing this on a closed model, we eliminate one vertex, three edges, and two triangles. We can apply a series of edge collapse operations to reduce a...

Sample Program particle

With the preceding explanation, understanding the source code listing for the sample program particle should be easy. The structure of this program is based on that of the dots program presented in the introductory companion book Linux 3D Graphics Programming (and included on the CD-ROM). We have mercilessly slashed out the code for the runway lights, stars, and snow examples, and focused the program on the particle system simulation. The abstract class mydot has been extended to include a...

The Division Operation and Texture Mapping

Notice that regardless of whether we use the pixel-level or vertex-level approach to texture mapping, we must perform a divide to arrive at the u and v values. With the pixel-level approach, we must divide the numerator by the denominator for the u and v terms with the vertex-level approach, we must divide u z and v z by 1 z. Thus, the pixel-level and the vertex-level approach are mathematically equivalent it is just that with the vertex-level approach, we have made the relationship between u,...

Relevant Screen Attributes l3dscreeninfo

The class l3d_screen_info (file scrinfo.h) is an abstract interface to screen information. We define screen information as follows any information which an external class needs to know about a screen object in order to be able to work with that screen. Class l3d_screen_info encapsulates the vital statistics about a screen and makes them available through a clean, easy interface. In particular, when dealing with colors and Xlmages, the bytes making up a pixel and their interpretation depend on...

Graphics Programming

Computer Graphics, Principles and Practice by James Foley, Andries van Dam, Steven Feiner, and John Hughes. Regarded by many as a classic in the field, this book covers an extremely broad range of topics relevant to 2D and 3D graphics programmers. Practically every important topic is covered, even if briefly. This book has a somewhat mathematical slant to it. OpenGL Programming Guide by Mason Woo, Jackie Neider, and Tom Davis. This is the definitive guide to programming with OpenGL. Real-Time...

Portals and Other Rendering Methods

Portal rendering can be combined easily with other methods of rendering. If we allow each cell to be responsible for rendering itself, then when we encounter a portal, we ask the connected cell to render itself through a virtual function call. This is in contrast to an approach where one main controlling routine tries to render each sector manually by explicitly drawing polygons and traversing the portals. Allowing each sector to render itself implies that each sector can use a different (even...

Rendering and LOD Techniques for Landscapes

LOD algorithms can be of considerable advantage with landscapes because of the large number of polygons needed to draw an entire landscape. The lack of natural partitioning boundaries for landscape meshes makes it difficult to use other LOD or culling techniques which are based on small, separate objects. An extreme example of this is the portal approach described in Chapter 5, which is poorly suited for landscape rendering because of the lack of obvious cell or sector structure in an arbitrary...

World Foundry

World Foundry is an open source (GPL) package that enables non-programmers to create 3D environments and games. It combines a powerful 3D engine with an external level editing system and an internal scripting system. NOTE The World Foundry project (http www.worldfoundry.org) currently needs interested 3D programmers to assist in porting and extending the engine and tools. You yes, you can help in this process. World Foundry is an extremely powerful system I have not seen any other open source...

Blender Interface and Commands

The Blender interface consists of a number of non-overlapping windows. Each window has a header and a type. You may choose to display the window header either at the top or the bottom of a window by right-clicking on the header. Change the type of the window by clicking and dragging the button on the left side of the window header. You can change the type of a window at any time. The types of windows are InfoWindow Contains global settings for the entire program, such as directory names....

Animating the Ika Chains

Blender offers a number of ways of animating the Ika chains. We can specify key frames with certain positions of the effectors, we can draw the movement curves explicitly, or we can even record the motion of the mouse to allow us to move the limb in real time. Here, we use the first method, key frame animation. Animating the Ika chains with key frame animation is almost identical to animating the vertices for 3D morphing as we did earlier. The procedure is as follows. 1. Choose a frame with the...

Combining BSP Trees and Bounding Volumes

We've now seen how to use the BSP tree to produce a correct polygon ordering for an arbitrary camera position. But with very large scenes, it becomes impractical to draw all of the polygons in all of the nodes of the BSP tree. It turns out that the technique of hierarchical view volume culling works well with BSP trees. The idea is that each node of a BSP tree represents a convex volume of space. So, all we need to do is compute a bounding sphere for each node in the BSP tree. This is the...

Deforming the Mesh

The second one is selected, because it was the last one inserted (or because you right-clicked it in the IpoWindow). With a vertex key selected, any changes to the mesh apply to that vertex key only. This means that if we go into EditMode now and change the mesh, it changes the mesh just for the second vertex key, but the first vertex key still retains the original shape of the mesh. This means that we now need to enter EditMode and deform the mesh into a...

Portalization Generating Portal Connectivity

Now, let's look at how to generate a simple world file based on the sector meshes we created in the last tutorial. The most significant thing that this process achieves is the automatic generation of the portal connectivity among the sectors and the creation of the appropriate PORTALPOLY lines in the world file. We call this process portalization. This is significant because this connectivity information was only implicitly specified in Blender through portal alignment after executing the...

Shadows and Light Maps

The lighting computation in the last sample program does not take into account the fact that some objects obstruct other objects. Light does not travel through opaque objects, creating areas of shadow on objects behind the obstructing object. Shadow computation can be done by performing an additional test before lighting each lumel. We check to see if any polygon from any object lies between the light source and the camera space (or world space) coordinates of the lumel. If there is such a...

Clipping Against the View Frustum

After culling objects against the view frustum, we know all objects whose bounding spheres lie at least partially within the frustum. We can then process these objects as normal performing back-face culling, perspective projection, clipping to the 2D view window, and rasterization. However, with the addition of the 3D view frustum, we now can make a change to one step the clip against the 2D view window. Recall that projection of a polygon from 3D into 2D can lead to vertices which lie outside...

Physics and Particle Systems

The idea behind our particle system is amazingly simple, yet it produces quite satisfying results. The next sample program particle simulates an explosion of a few thousand particles. We start all particles out at a certain position, and then impart each particle with a random 3D velocity away from the starting point, to simulate the tremendous and practically instantaneous outward force generated by an explosion. From classical Newtonian physics, we know that velocity is a change in position...

Game Blender Blender

Blender 2.0, also called Game Blender, is a version of Blender that includes some support for creating interactive content. We don't have the space in this book to go over the complete details of the entire system. What we can do is go over a quick example of how to create a simple game in Blender, so that you can see how the system works and experiment further on your own. NOTE To execute the following tutorial, you must download the Game Blender system (version 2.0 or higher) from the Blender...

Hardware Acceleration

In general, l3d programs can all take advantage of hardware acceleration by using OpenGL as the rasterization layer. This means that OpenGL must be configured to use hardware acceleration in order for l3d programs to use hardware acceleration. There are two ways for you to use hardware acceleration. The first way requires a 3DFX graphics card, the Glide library, and a Mesa distribution compiled with Glide support. This means that you need to manually install Glide and compile Mesa see the Mesa...

Sample Program lightmap

The last sample program in this chapter illustrates the use of light mapping and texture mapping combined. We also see an implementation of the actual computation of light intensities for the light maps, by using the diffuse reflection equations discussed earlier. The program lightmap displays a number of static pyramid objects, all initially dark. You can fly around the scene with the standard navigation keys provided by class l3d_pipe-line_world. Press p to place a point light at the current...

Curved Surfaces

The focus of this book has been on polygonal 3D graphics. We stored our models as polygons, and rendered these polygons to the screen. An alternative is to represent the geometry in terms of curved surfaces, then to tessellate the geometry dynamically to generate a polygonal representation. While it would theoretically be possible to render the curved surface directly by using a z buffer (remember, the z buffer only requires us to be able to compute a z value for the surface for every pixel),...

L3dGenpm

Module l3dGen.pm is a generator class, which generates a portal world file based on the information stored in a World object. Member variable _world stores the world object, which must have already been filled by a parser object. Method _generate is a method which simply traverses the world structure in memory and prints the appropriate lines, conforming to the world file format of Chapter 5, to the standard output stream. The data in memory is already organized similarly to the format needed...

Sample Program collide

As is usual with l3d programs, once the supporting lower-level classes are in place, the actual application program is simple. Program collide creates an instance of the new world class with collision detection, then asks it to load itself from disk. This causes creation of the appropriate collidable polygons and a collidable camera. Furthermore, the world file contains references to plug-in objects of type seeker, which also know how to collide themselves with the environment. The main program...

BSP Tree and Octree

BSP trees and octrees are similar to the regular spatial partitioning scheme, only hierarchical. Creating a world editor for such a system is also similar. You do not specify any partitioning of space yourself, instead letting the BSP tree or the octree divide the geometry for you. The geometry in the world editor is stored in any convenient manner, divided in any way across an arbitrary number of meshes then, all geometry is exported at once and is automatically partitioned by the BSP tree or...

Creating an Ika Chain in Blender

Let's begin modeling our human-like figure by creating four Ika chains two for the arms and two for the legs. (The file ika.blend, located in the source code directory for the next sample program ika, contains the finished Ika model we create in the next few sections.) Begin with an empty Blender configuration (Ctrl+x). Then create the Ika chain for one leg as follows 1. Position the 3D cursor as follows. Switch to front view (press 1 on the numeric keypad), and move the 3D cursor one unit to...

Backto Front Rendering Painters Algorithm Revisited

Let's now see how we can use the BSP tree, once constructed. It should be noted that there are many uses of BSP trees we can only cover a few here. One interesting property of a BSP tree as constructed above (choose splitting planes based on polygons) is that a traversal of the tree by using the camera position produces a perfect back-to-front or front-to-back ordering of the polygons, just as needed for the painter's algorithm, but without sorting. The traversal, which is recursive, works as...

Classes for Loading Textures from Disk

Now we know how to store texture data in memory, but what about creating the texture image data in the first place Typically, textures are created with a bitmap paint program, such as the GIMP program under Linux. The textures should be created with dimensions that are powers of two, for instance, 64 by 64 pixels. The textures need to be saved to disk in a file format which we can then read in and place into our l3d_texture_data class. The l3d classes for loading textures support the portable...

Back Face Culling

One of the simplest VSD algorithms is the back-face culling algorithm. This algorithm mainly addresses the efficiency issue of VSD. In 3D graphics, to cull an object means to remove it from further consideration. Thus, back-face culling refers to the removal from further consideration of faces (polygons) which are back-facing. Let's explore this idea more closely. Principally, we use polygons to model the surface of our 3D objects. If all of our objects are closed so that the interior may never...

Program Listings for blendat

Now that we've seen all of the details of how blend_at works, we can look at the code listings for this tool. blend_at was written using the GUI builder environment Glade. The terms builder environment are used to indicate that Glade is more than a one-way GUI builder tool, but not as completely integrated as a true Rapid Application Development environment. Glade is based upon the GTK toolkit of user interface widgets, and allows you to graphically place widgets within windows and attach code...

Tutorial Using Inverse Kinematics and Rotoscoping to Model a Walking Human Figure

This tutorial illustrates two very powerful features of Blender inverse kinematics and rotoscoping. These techniques allow us to animate a human-like jointed figure, which we then import into a program. This tutorial is a small introduction to the field of character animation. Character animation is a special branch of animation dealing with animating characters living entities such as humans, dogs, or imaginary creatures such as aliens. Even ordinarily inanimate objects, such as a sack of...

Collision Detection

The topic of collision detection is a non-graphical technique which nonetheless is very important for 3D graphics applications. Collision detection refers to the determination of whether two objects in the 3D virtual world overlap, or not. Collision detection generally also requires some sort of collision response if we detect a collision, such as moving the objects apart again. Collision detection algorithms are important for 3D graphics applications for two reasons They allow us to impart a...

Practical Issues in Dealing with Texture Image Files

You may have some existing image data that you wish to convert into a PPM file for use as a texture. The PPM utilities, available for many operating systems and included on the CD-ROM, offer several command-line utilities for converting to and from various file formats. You can find these by typing man -k ppm and man -k pnm. (PNM stands for portable anymap, meaning either a bitmap with two colors or a pixmap with arbitrary colors.) Some of the more important utilities are giftopnm and djpeg...

Intersection Testing and Bounding Volumes

Figure 8-1 Checking for collisions can be done by checking every polygon of one object against every polygon of the other object, but this is slow. polygon overlap between objeets a collision bounding sphere collision < 1 1 ycluyl collision bounding sphere collision although no actual collision bounding sphere collision < 1 1 ycluyl collision bounding sphere collision although no actual collision Figure 8-2 Enclosing the object in a bounding volume allows us to first check for overlap of...

Multiple Simultaneous Collisions and Collision Response

This section deals with the two topics together multiple simultaneous collisions and collision response. We treat these topics together because they influence one another to some degree. Once we detect that a collision occurred, we should do something about it. In general, this is completely application-specific. For instance, if we are modeling a game where the player runs around collecting coins to earn points, then when the player collides with a coin, we probably simply cause the coin to...

Parsing of Attributes by Vidsc Parserpm and vidinfo

We have now seen how we use blend_at to associate attribute information with meshes, and what specific attributes have a meaning for the generation of the world file. This is all the write side ofthe attribute system, where we essentially insert information into the attributes database. The read side ofthe attribute system takes place in module VidscParser.pm, where the attribute information is extracted and evaluated. With an understanding ofthe operation ofthe attribute system, we now can...

The Goals of VSD

VSD algorithms have two main goals to ensure a correct display and to efficiently reduce the amount of computation which must be done. Let's discuss each separately. First, the correctness issue addressed by VSD algorithms aims to ensure that farther polygons do not obscure nearer polygons, since this is a physical impossibility due to the properties of light. Drawing polygons to the screen in no particular order often leads to an incorrect display where farther polygons sometimes obscure...

Rayto Sphere

Ray-to-sphere intersection testing tests whether a ray intersects a sphere. We're going to look at a special case of this, which simply checks to see if a particular line segment (part of a ray) intersects the sphere. One way to do this is as follows. Call the center of the sphere c, and the endpoints of the line segment being tested a and b. Then, compute the vector c-a, which is the vector from the start point of the segment to the sphere center. Next, compute the normalized vector v b-a,...

The Five Step Process of l3d Programs

The drawdot program can be broken up into five steps, which are representative of programming with l3d. In fact, these steps are representative of event-based programming in general, on a variety of platforms, as evidenced by the fact that the following scheme also can be applied to event-driven programs under various operating systems. The five steps are as follows. 1. Choose the proper factories for three classes the screen, the rasterizer implementation, and the event dispatcher. 2. Declare...

Solving the Texture Mapping Equations with Calc

Now, at long last, we have enough information to solve the texture mapping equations in Calc. We solve the system with the procedure described in the previous section duplicate, solve with one variable as the last variable, repeat for other variables. Simplify each solution piece by piece by using selections. Immediately after entering the system of equations from Equation 2-20 into Calc, the Calc window appears as in Figure 2-32. Figure 2-32 The texture space to world space equations in Calc....

Tunneling and Sweep Tests

We implicitly addressed the problem of tunneling with the last collision test, sphere-to-polygon, but it is important enough that we should explicitly mention it. The term tunneling refers to the problem that objects moving with a high speed in a discrete computer simulation move from one location to a spatially distant location instantaneously, without ever occupying any of the space in between the old and the new positions. When the distance traveled by an object per frame remains small...

Sample Program backface

The sample program backface implements back-face culling. Its structure is simple and typical of an l3d program. We derive the custom world class for program backface from the new class l3d_world_backface. If you have read the introductory companion book Linux 3D Graphics Programming, you can see that this program is nearly identical to the fltsim program. Run the program and notice the display in the upper left of the screen, showing the number of polygons sent to the rasterizer. Only the...

Rayto Polygon

Ray-to-polygon intersection testing is the next intersection test of interest, and is also used by another test, the sphere-to-polygon test. A ray is a directed half-line starting at one point and moving infinitely in the direction of, through, and past a second point. With ray-to-polygon collision detection, the ray goes from the old position of the object to the new position of the object. We want to determine if this ray or line of movement intersects a particular polygon. This consists of...

Billboards

A billboard is a single texture mapped polygon which always rotates itself so that it directly faces the viewer. Billboards are also often called sprites. The texture image on the billboard is typically a 2D image of a more complicated 3D object. For instance, a 2D billboard could contain a pre-rendered image of a complex tree model containing hundreds of polygons. Then, we can approximate the visual appearance of the tree by rendering just one polygon. Thus, the purpose of using billboards is...

Surfaces

A surface is a pre-tiled, pre-lit texture. A texture and a light map combine to form a surface the surface can then be treated as a normal texture. With this approach, light mapping becomes simply a sort of preprocessing step before drawing the texture mapped polygons. In theory, this sounds easy enough for each texel in the texture map, simply light it according to the corresponding lumel in the light map, and we're done, right In practice, several problems prevent such a straightforward...

Eneral Technique

We have seen many facets of Linux 3D graphics programming operating system issues, the X Window System, 2D graphics, 3D geometry and mathematics, classes for orga-T y nizing 3D world data, 3D modeling and texturing, import and export of polygonal models, and animation. Starting with this chapter, we begin to put all of this information together, to create larger, interactive 3D environments. In this and the coming chapters we'll look at techniques for handling larger datasets, tools for...

Storing Landscapes as Height Fields

Landscape data is typically stored as a height field, or elevation grid. A height field is simply an evenly spaced 2D array of values, where each value represents the height of the landscape at that point on the ground. Height fields are a natural and easy way of storing elevation data, and many natural landscapes can be represented with height fields. Those landscapes that cannot be represented with height fields have cliffs or overhangs, where there would be multiple heights for a particular...

L3d Directory Structure

The library classes and the applications using the library classes are split into separate source and binary directory trees. The reason we split the source files and binary files into two separate trees is that the same source code can be compiled on a number of different platforms. Keeping the binary files, which vary from platform to platform, in the same directory as the source files, which remain the same, leads to a rather chaotic organization. While chaos theory is a rich and fascinating...

Nonconvex Sectorbased Partitioning

A sort of middle ground between completely manual partitioning and completely automatic partitioning is possible with the use of non-convex sectors. With this scheme, the world editor allows you to divide the world into logical sectors of space, which do not have to be convex. In this case, the partitioning serves to reduce complexity, but not to control explicit visibility information as is the case with convex sectors. For instance, with convex sectors, one logical room might have to be split...

Parent

The PARENT attribute specifies the name of the parent sector, < SECTOR> , in which this object is initially located. The object is initially inserted into the objects list of the parent sector, so that it is drawn along with the sector. Note that the parent sector does not own the object and is not responsible for its destruction the object is merely located within the sector. Indeed, the object can move from sector to sector, in which case it must remove itself from the objects list of the...

Step 2 Define a Texture Space

Having defined a 2D texture image, we need to somehow position this texture image in our 3D world. This is because the 2D texture image is supposed to affect the colors of the 3D polygons comprising our virtual world it only makes sense, then, that the texture image must also be positioned within the 3D world. Positioning the texture image in our 3D world first requires us to define a texture space containing the texture image. Texture space is simply a normal coordinate system with three axes...

Special Effects

In previous chapters we have seen all of the basic elements needed to create a reasonably good-looking interactive 3D environment. Let's briefly recapitulate the main techniques we have seen up to this point. Perspective creates a sense of depth and the parallax effect. Arbitrary camera orientation allows for realistic viewpoints. Texture mapping and lighting create engaging surface detail. A 3D modeling program allows us to create believable, complex geometry. VSD schemes combined with a world...

Using the Frustum Planes

Once we have the frustum planes, we then can test each polygon for containment within the frustum. A polygon is within the frustum if all of its vertices are in the frustum. A vertex is in the frustum if it is on the inside side of every frustum plane, which we can evaluate simply by evaluating the plane equation using the vertex. If a polygon is outside of the view frustum, it is removed from further processing by removing it from the nonculled_polygon_nodes list, just as we did for back-face...

Class l3dWorld Frustum

The new class l3d_world_frustum incorporates view frustum culling into the world's drawing behavior. It only overrides method draw_all. Listing 4-11 w_vfrust.h include tool_os memman.h include tool_os dispatch.h include view camera.h include tool_2d screen.h include object object3d.hM include world.h class l3d_world_frustum public l3d_world l3d_world_frustum(int xsize, int ysize) l3d_world(xsize,ysize) virtual l3d_world_frustum(void) include w_vfrust.h include < stdlib.h> include <...

View Frustum Culling

View frustum culling is another VSD algorithm which, like back-face culling, focuses on the efficiency side of VSD. With view frustum culling, we cull polygons or groups of polygons which are completely outside of the view frustum. The view frustum, also called the view volume, is the area in 3D space visible to the virtual viewer. The viewer does not see everything in the world the horizontal and vertical field of view terms, which involve the size of the display window, limit the amount of...

Using a BSP Tree to Partially Presort Polygons

Let's now look more closely at how we can construct a BSP tree, then look at an example of how to use a BSP tree for rendering polygons in front-to-back or back-to-front order. The key idea of the BSP tree is to divide space hierarchically using planes. The question is, which planes do we choose to divide space The answer depends on the fact that the spatial regions the BSP tree partitions are not empty. Instead, these regions contain polygons. We typically choose one of the polygons within the...

Exporting the Texture Information

The Videoscape file format does not store texture coordinates, so by exporting the morph target meshes to Videoscape, we lose the texture information. One simple solution is to export the file in VRML format, which is also an ASCII file format but is slightly more complicated to parse than Videoscape. With VRML export, Blender does save the texture coordinates in the VRML file. Fortunately, the ordering of the vertices and faces is the same in the Videoscape and the VRML files. This means that...

Creating Sectors and Portals

Sectors and portals in the world editing system are closely related. As we have said, a portal is not explicitly defined instead, it is a hole in the geometry of a sector. Let's formalize this notion of a hole in a sector. A hole in a sector is a continuous loop offree edges. A free edge is an edge in a sector which is used by only one polygon within the sector. Such free edges have a polygon on just one side, and empty space in other words, a hole on the other side. This definition assumes...

The Rasterizer l3drasterizer2d

The class l3d_rasterizer_2d (file rasteriz.cc) represents a 2D, double-buffered rasterizer a subsystem capable of drawing 2D geometric primitives on a double-buffered raster output device. The class does not do any of the rasterization work itself, but instead relies on a rasterizer implementation (covered in the next section) to provide a toolkit of functions that the rasterizer calls. Class l3d_rasterizer_2d is a recognition of the general concept of a rasterizer interface, which allows...

Programming IK and FK

Until now, we've looked at IK from the point of view of a 3D modeling program we manually pose our character in the 3D modeler with the help of IK, then export the results to meshes which we then animate in our program. A more comprehensive approach, and one which has started to become more common in recent years, is actually to do the IK calculations in real time in the 3D program itself. Essentially, you need to create a hierarchical data structure to store the limbs in an IK chain, and a...

Inverse Kinematics Definition

Inverse kinematics, abbreviated IK, is best thought of as a way of automatically positioning a series of joints by specifying the position of just one point the endpoint. An example will make this clear. Let's say we have modeled an arm object as a series of two segments the top segment and the bottom segment. Figure 3-15 An arm modeled as a chain (or Ika) consisting of two bones (or limbs). In Blender terminology, each of these segments is called a limb in other literature, these segments are...

Sample Program leafybsp

The sample program leafybsp reads in a Videoscape file as input, creates a leafy BSP tree based from the mesh, then writes out a series of Videoscape files, where each file contains the polygons in one leaf node of the leafy BSP tree. You can then load these files, all at once, into Blender, and see how the leafy BSP tree automatically divides arbitrary geometry into convex subsets. The main program file is very similar to that of program bsp. The only difference is that after loading the...

Mesa OpenGL 3D Rasterizer Implementation l3drasterizer3dmesaimp

Mesa can also draw texture mapped polygons for us. For a computer without hardware acceleration, there is no speed benefit to be gained by using Mesa instead of a custom software texture mapper, because Mesa must do exactly the same math. The picture looks quite different, though, with a 3D graphics card. In this case, Mesa simply forwards the request to draw a texture mapped polygon on to the hardware, which then draws the polygon at speeds impossible to achieve via software alone. Therefore,...

Hierarchical View Frustum Culling

Individually checking every polygon for containment within the view frustum is very inefficient. We can be more efficient by introducing a hierarchy into our checks. Instead of checking each polygon, we can first perform a coarse check at the object level. If an entire object is found to be outside of the view frustum, then all of its polygons must also lie outside of the frustum, so we don't need to waste time checking every polygon in the object. If the object is entirely inside the view...

Importing the Textured Ika Meshes

Having exported the textured meshes from Blender, we can then import them into a program by using the Videoscape plug-in from the previous program. The next program, ika, does just this. The fact that the meshes were created with IK does not matter to the Videoscape plug-in we just read them in as meshes and can then morph between them. For this program, I just chose to morph back and forth between two key frames, which are saved in file ikal.obj and ika7.obj. These correspond to animation...

Environment Mapping

The term environment mapping refers to a special form of dynamic texture mapping used to simulate the reflection of the environment off of a surface. Let's first talk about the general idea, then see how the idea can be applied in real time. Figure 7-1 A cylinder modeled with environment mapping. The cylinder appears to reflect its environment. Environment mapping simulates the appearance of a reflective surface by coloring each pixel of the surface's rasterized image with a color coming from a...

Goals of This Text

Analyze and use other 3D graphics texts and programs. In the open source world of Linux, understanding fundamental concepts is indeed important so that you can understand and possibly contribute to the common pool of knowledge and code. Furthermore, learning fundamental 3D graphics concepts also enables you to understand and effectively use sophisticated 3D applications and libraries such as 3D modelers and OpenGL. A second goal of this text is to give you plenty of hands-on experience...

Step 3 Map Between Texture Space and World Space

Defining a texture space in terms of a texture coordinate system actually has the effect of positioning, orienting, and scaling the texture within 3D space. Recall that texture space is a colored space. Our colored 2D texture image is located in the uv plane of texture space, in the unit square going from 0,0,0 to 1,1,0 . By positioning the origin point of the texture coordinate system, we are also effectively positioning the first pixel of the texture image. By orienting the axes of the...

Choosing a Splitting Plane

The question still remains as to which polygon's plane, at any given point, is the best plane to choose for splitting the space. The answer depends on how we use the BSP tree. But generally, it is best to try to choose the splitting planes such that, after splitting, larger sub-spaces contain few polygons and smaller sub-spaces contain many polygons NAYL98 . Striving for a balanced tree is usually not desirable, because the underlying geometry is usually not evenly distributed NAYL98 . Remember...

Store an ID Location and Orientation in Overlapping Edges

The first goal is to be able to uniquely identify each mesh before and after export. The design of this system was dictated by the limitations of the Videoscape export system supported by Blender. As mentioned earlier, two major properties of this system make a solution difficult only mesh geometry is exported, and we lose name information when exporting multiple meshes simultaneously. This means that if we can somehow encode the mesh's identity within the geometry itself, then this information...

Binary Space Partitioning Trees Octrees and Regular Spatial Partitioning

We mentioned in Chapter 4 the correctness and visibility aspects of VSD algorithms. The binary space partitioning BSP tree and octree algorithms are VSD algorithms which address both the correctness and efficiency issues of VSD. First, let's cover BSP trees later, we'll look at octrees. The two algorithms are quite similar. The BSP tree divides space hierarchically into regions in a time-consuming, one-time preprocessing step, then later allows determination of a correct back-to-front or...

Sample Program textest

Congratulations, you now understand basic texture mapping Let's now take a look at a sample program using texture mapping, so that all of this mind-boggling math actually produces a visual result. With an understanding of the basic concepts of texture mapping, using the texture mapping classes is comparatively easy. The next sample program, textest, creates a navigable scene with two texture mapped pyramids. One of the pyramids rotates, to provide some animation in the scene. You can fly...

Rotoscoping and Inverse Kinematics

Blender offers an interesting feature which can make creating IK animations easier. This feature is called rotoscoping. Rotoscoping is the use of live video material to assist in creating computer animations. Blender's support for rotoscoping allows individual frames of a movie file to be synchronized with the Blender animation frame. The movie image is superimposed on top of the 3DWindow. Changing the Blender animation frame with the arrow keys also changes the displayed frame of the movie....

The Painters Algorithm

Depth Sort Painter Algorithm

The painter's algorithm is a VSD algorithm, relying on polygon sorting, which addresses the correctness issue but neglects the efficiency issue. We know that drawing polygons in random order to the screen sometimes results in an incorrect display because farther polygons obscure nearer ones. The solution adopted in the original l3d_world class was the so-called painter's algorithm, where we draw polygons from back-to-front order into the frame buffer. By drawing the nearest polygons last, the...

Class l3dcollidablesphere

Class l3d_collidable_sphere is a sphere that can test itself for collision against other objects. Member variable collision_sphere_radius is the radius of the sphere. Overridden method detect_collision_with detects the collision of the sphere with various types of other objects. Implemented are the sphere-plane, sphere-polygon, and sphere-sphere tests described earlier. If member variable prevent_collision is true, then the sphere's position is corrected after a collision so that it no longer...

Mesa OpenGL Z Buffering

Mesa OpenGL provide built-in support for z buffering. 3D acceleration hardware often provides a z buffer in the hardware, meaning that applications can reap the benefits of the z buffer draw polygons in any order, the display will always be correct without worrying too much about the per-pixel performance hit in hardware, the calculations are fast enough so as not to be the bottleneck. This does not mean, however, that higher-level culling such as hierarchical view frustum culling can be...

Portals and the Near Z Plane

Clipping polygons against the near z plane is a necessity, as discussed in the introductory companion book Linux 3D Graphics Programming. However, it causes problems with portals. In particular, as we are approaching a portal, right as soon as we are about to cross it to move into the adjoining cell, the portal gets briefly but completely clipped away by the near z plane. This causes a very distracting jump in the image just as we cross the portal. If we are clearing the frame buffer after...

Defining a View Frustum

Bottom Frustum

The view frustum can be represented by six planes. The frustum itself is then the area inside of the intersection of all six planes. Figure 4-7 The view frustum can be defined by six planes near, far, left, right, top, and bottom. The corner points are computed via reverse projection of the screen space corner points, and are used to compute the equations for the left, right, top, and bottom planes. Figure 4-7 The view frustum can be defined by six planes near, far, left, right, top, and...

The Z Buffer Algorithm

The z buffer algorithm is accurate to the pixel. It correctly handles polygons that pierce one another, as well as cyclic overlap. It can even be used for non-polygonal objects all that is needed is some way of determining the z value of the object for a given pixel position. Figure 4-18 The z buffer. At first, it is initialized to the maximum depth value left . Then we insert one polygon, drawing each pixel and storing its depth values into the z buffer only if the polygon's z value is less...

Other VSD Algorithms

Recently, there has been a bit of interest in occlusion-based algorithms. The main idea behind such algorithms is that if we can find large polygons near the camera, they will obscure or occlude polygons behind them. Assuming, as is usually the case, that the polygons are opaque and not transparent, then finding large occluder polygons early on means that we do not need to draw or process anything behind the occluder. It should be noted that while the z...

Sample l3d Program

Before looking at the l3d classes themselves, let's first look at a sample program which uses l3d. This will give you a practical perspective on l3d before looking at the following sections, which go into more detail on the specific l3d classes. The following sample program is called drawdot and illustrates usage of the l3d library classes in order to move a green dot around the screen, thereby forming a simple drawing program. This program works with visuals of any color depth and in both...

Creating a Leafy BSP Tree

We can create a leafy BSP tree from a non-leafy BSP tree by using a recursive routine to push polygons down into their child nodes. The algorithm works as follows. Create a BSP tree as normal, with polygons stored in the internal nodes. Then, push each polygon down to a leaf node recursively as follows. Begin at the root of the entire tree with an empty convex clump. 1. Split the current convex clump against the current node's splitting plane. This yields two convex clumps one in front of the...

The l3d Library Classes

This book relies on the use of a series of C library classes implementing all of the 2D and 3D graphics concepts described in the previous sections. This library is called the l3d library. It is developed incrementally in the introductory companion book, Linux 3D Graphics Programming. In this book, we use the classes presented in the first book, and continue to build on these classes to illustrate newer and more advanced concepts. The l3d classes are on the CD-ROM and are also available for...

Leafy BSP Trees Automatic Convex Partitioning of Space

The BSP tree structure as described so far stores polygons in both the internal and leaf nodes of the tree. By traversing the tree in a particular order using the camera position relative to the current node's splitting plane, we determine an ordering among the BSP tree nodes. We draw each single polygon in each node as we traverse the tree to determine a viewpoint-dependent polygon ordering without sorting. Another form of BSP tree stores polygons exclusively in the leaf nodes of the tree, not...

Light Mapping Revisited

The difference between texture mapping and light mapping is that with texture mapping, the color in the texture map defines the final color to be displayed on-screen with light mapping, the light intensity in the light map does not define the color to be displayed, but instead affects an existing color, making it either brighter or darker via a lighting table. There are a few ways to implement light mapping. One way would be to modify the inner loop of the rasterizer to perform a double texture...

General Observations about the Z Buffer

Let's now look at some important aspects of the z buffer algorithm. Sorting. We do not need to sort objects before sending them to the z buffer. Eventually, after all objects are rasterized, the nearest pixels will correctly obscure the farthest pixels. However, if we do perform a rough front-to-back sort, this can save time. This is because drawing polygons in back-to-front order into the z buffer means that many painstakingly computed pixels will be wastefully overwritten, just as with the...

Texture LOD Techniques MIP Mapping

Mip Mapping

A final type of LOD that deserves mention deals with simplification not of the geometry of an object, but instead of its texture. The reason we wish to do this is to improve the appearance of texture mapped polygons which are viewed from a great distance. In contrast to geometry LOD techniques, which are intended to speed up processing by rendering fewer polygons, this texture LOD scheme mainly aims to improve visual quality. In some cases this texture LOD scheme can also cause more coherent...

BSP Tree as a Multiresolution Solid Modeling Representation

As we mentioned at the beginning of our discussion on BSP trees, we unfortunately cannot cover all the uses of BSP tree here see the references in the Appendix for more information. But one last topic concerning BSP trees deserves mention the use of the BSP tree as a representation of a polyhedral solid. Instead of storing a set of polygons defining the boundary of a polyhedral object, we can view the BSP tree as being a representation of the volume and not the boundary of the same polyhedral...

Generating Fractal Landscapes

Landscape Blender

Height field data for landscapes can also be generated algorithmically. Perhaps the best known class of algorithms for generating such data are the fractal algorithms. Fractal landscape algorithms fundamentally work by starting with a single, undivided polygon. The polygon is then divided into smaller polygons, which adds new vertices. The new vertices are first positioned at the average height of their neighboring vertices, then are additionally randomly displaced up or down. We recursively...

Step 4 Reverse Project from Screen Coordinates into Texture Coordinates

The practical goal of texture mapping is to determine, for each pixel of a polygon being drawn, which pixel from the texture image should be drawn. We can see this goal as being a conversion from screen coordinates to texture coordinates. We know the screen coordinates of each pixel we are drawing on-screen what we need to know are the texture coordinates in texture space, which then give us the precise pixel coordinates within the texture image we need to display. Given the previous section's...

Sample Program morph3d

Sample program morph3d displays a number of morphing pyramid objects in an interactive scene. Each pyramid slowly changes shape from a compact pyramid to a more elongated shape, then back again. You can interactively fly though the scene with the standard keyboard controls used in l3d library j Rotate left rotates around the VUP axis l Rotate right rotates around the VUP axis i Thrust forward translates along the VFW axis k Thrust backward translates along the VFW axis J Roll left rotates...

Software Z Buffer Class l3drasterizer3dzbufswimp

Class l3d_rasterizer_3d_zbuf_sw_imp is the l3d software rasterizer implementing z buffering. It draws textured polygons into a z buffer. The implementation is a fairly simple extension of the textured polygon drawing routine. Since we already need to interpolate the 1 z values across the polygon for texture mapping, all we need to do for z buffering is to store these values in a z buffer, and to compare each pixel's 1 z value against the 1 z value in the z buffer to see if the current pixel...

Software 3D Rasterizer Implementation l3drasterizer3dswimp

The class l3d_rasterizer_3d_sw_imp is a software implementation of the rasterization services required by class l3d_rasterizer_3d. The main function of interest is the new function draw_polygon_textured. Fundamentally, it draws a polygon in much the same manner as we draw flat-shaded polygons we proceed from top to bottom, rasterizing each edge on the left and right sides of the polygon simultaneously. Between the left edge and the right edge we draw a horizontal span of pixels. Figure 2-39...