BOSP
Boolean Operation Sculpting Program
Innovations 2002/03 Project Report
Scott Griffiths (1352949)

Introduction
Over the past three years I have been very interested in the process of transferring a drawn or imagined idea into a full 3D geometric model.

There are many techniques that exist to achieve this goal, most notable are polygonal and NURBS creation methods, though it is useful to note that once a polygonal mesh is created, it can be refined and smoothed to create a more pleasing shape.

Looking at work by famous sculptors, such as Henry Moore and even Michelangelo, I noticed how very difficult it would be to produce authentic-looking objects in these styles, such as Moore’s reclining figure, a bronze sculpture depicting a rather abstract figure lying gracefully on a bronze plinth.

The organic shapes in this piece would be extremely difficult to reproduce capturing the same lazy sweep as the artists here has done – in fact the computer modeler would have to actually work to produce them, whereas it came naturally to the sculptor.

Even with more complicated and realistic sculptures such as Michelangelo’s Statue of Giuliano de' Medici, again it would be very difficult to produce these results in a standard computer environment, and may be more intuitive to a sculptor, even when using advanced tools such as Non-Uniform Rational B-Splines (NURBS) to create the curves.

Working with NURBS modeling techniques can be a very time-consuming and un-creative experience, and geometry created with said methods can sometimes result in an overly complicated and even unusable end-products if due care is not taken throughout the process.

Polygons, therefore, can be taken as one of the easiest and most intuitive modeling techniques, and most importantly, the easiest to correct and refine later. The unfortunate downside is that the user must exhibit a large knowledge of the underlying geometric techniques - e.g. vertices, edges and faces/polygons, and the structure in which they fit together - in order to work with a polygonal model. 

Polygonal surfaces also have no integral refinement techniques - unlike parametric surfaces such as NURBS - and the user must take this into account when creating realistic looking geometry is required, as the resulting model may look "blocky" and unrealistic. It is down to the user, therefore, to build refinement into their own model, which again requires knowledge of how flat planes combine to create the illusion of curvature.

Taking this into account, I have decided to attempt to create a modeling process based on polygonal geometric techniques, though one which will hopefully eradicate much of the knowledge needed of geometry in order to create workable meshes.

Just as a sculptor does not necessarily need to understand the physical components of the material he/she is working with, a computer sculptor should not need to either.

Sculpting
Tools
When looking at a sculptor work into a solid cube of stone, and create from it a complicated and pleasing final product, it is easy to note that the use of tools is prolific in the process.

A tool can be anything from some sandpaper to a chisel or planing device, and all of the tools have different properties and can achieve drastically different results when used correctly.

Tools, therefore, must play a large part in our finished product, though unlike in the real world, intricate knowledge of tool-using techniques should not be required - as well as the strength to use them, or the physical limitations imposed on tool shape and design. 

Indeed this last is an important point, as real-world tools have several restrictions: They must include some method for the user to manipulate the tool - and gain sufficient leverage to make the tool useful - a chisel must have a long enough handle. Tools must also be of a certain dimension (depending on the material the tool is created out of) in order to prevent snapping - you may not have a chisel which is only 1 mm wide, unless made from some extremely expensive material itself.

When simulating tools in a computer environment, however, we do not have any of these restrictions, and we may allow the user to define custom tools of arbitrary size and shape, without paying heed to material limitations.

Technique
Tools do play an important part of the sculpting process, though their main purpose is to remove material from the work-in-progress - which we shall call the "object". Therefore in any sculpting process, there are two main components: the tool and the object.

When a sculptor works, he/she will tend to move around the object a large amount, whilst only moving the tool a relatively small amount (enough to make the tool have the desired effect). In a computer environment, the movement around the object can be simulated by the simple rotation of the object itself around a central point - possibly the center of gravity of the object, or the object's geometric bounding center.

The tool therefore does not need to be rotated and manipulated in the same degree, but need only be moved across a certain range of motion. This motion can be restricted therefore to a simple plane across the field of vision of the user, usually facing the user directly.

Another direct problem that the conversion from reality to simulation brings about, is the intrinsic conversion from the two-dimensional "equipment space" i.e. the mouse and keyboard, into the three-dimensional "program-space". As we will already be using our mouse's two dimensions to position the tool across the object, we find that we need some way to simulate the tool's "power", in order to regulate the effect of the tool on the object.

Simulation
We can distill the usage of a simulated tool into two main categories - the orientation (which we have already covered), and the effect. The mouse buttons themselves are very one-dimensional, and not user-friendly, but can be used in conjunction with another control method to produce more pleasing and natural results of control. 

The options however, are limited - a mouse has no third dimensional control, and so we a forced to "double-up" on the two dimensional ability of the mouse system. We are currently not really taking any notice of the change of speed of the mouse position, and this can be used to our advantage, as speed and power are closely linked, making it intuitive to take the speed of the motion to be the power of the effect.

Combined with the usage of the mouse button itself, which we will use to "transform" the "mode" of the control system from orientation to effect, this may provide us with an intuitive and user-friendlier system for the sculpting program.

Display
With the control and tool system more or less defined, we can consider the actual display of the modeling system. A three-dimensional representation of the "scene" is obviously more suited to this application, as a two-dimensional view will restrict the user’s ability to visualize the scene and therefore create an accurate final product.

With any 3D scene, the user is still going to be confined to a single camera orientation, unless we enable the user to change the camera’s angle of view. This can be accomplished by the use of another mouse-button to switch camera-reorientation on, then the position data can be interpreted into camera rotation change.

One thing should be considered however – due to the intrinsic two-dimensional nature of a computer monitor, true three-dimensional representation cannot be achieved, only an approximation – making it extremely difficult for the user to interpret the scene, and therefore difficult to create the model required of the software.

We can improve the accuracy of the system by reducing the display motion to only a single plane across the object, with the display only oriented to the tool. This has the effect of providing the user with the most useful viewpoint in terms of sculpting, but also enables the user to accurately position the tool in respect to the object.

Software
An obvious choice for developing the software required to simulate this application is the Microsoft Visual C++ programming environment. This enables us to create windows-style GUI elements, and seamlessly integrate the three-dimensional portions to create a unified whole.

The application therefore will be best served by a reasonably large “observation viewport” – the actual 3D view of the modeling elements – with a useful toolbar on the right hand side. This enables a square viewport without compromising the rectangular fitted shape of the parent window, with a reasonably equal aspect ratio of the computer monitor it will be viewed on.

The toolbar will have to include the more obvious functions such as loading and saving a scene – using a simple proprietary format, organized into a reasonable extension such as “.scn” or “.blp”, simply so that a user can recognize files created with this program. In addition, functions to load and save the objects and reload them as tool shapes would also be desirable. Options to reset the shapes into one of several primitives (such as a cube, sphere etc.) to use as a new tool.

Some additional tool settings may be required, mostly as modifiers for the effects of the tool itself. The user can then choose to have the tool have more or less of an effect on the object, to improve modeling accuracy, and the efficiency of the program.

Most of these functions, however, do not contribute much to the actual running of the program, and a far simpler version can be constructed to test the effectiveness of the sculpting simulation.

Program Basis
Geometry
The program itself would have to be constructed on a sound geometry library. This cannot be stressed enough, as with the complex computations which will have to occur later, any inconsistencies in the underlying structure will multiply and cause program instability.

Data
We will require several data structures to achieve that which we have aimed for. Starting with the lowest-level components first, we will need a vertex structure.

Vertex
A vertex is a point in 3D-space. It has three main components: the X, Y, and Z co-ordinates, which will describe the position of the point. Ancillary flags can also be added (such as the colour of the point). Vertexes can be connected to form more complex data-structures, such as edges.

Edge
An edge is formed of two vertices together. An edge can be described by a line in 3D space. Edges are incredibly important in Boolean operations, as they form the basis of geometry intersection. Unfortunately, edges by themselves can not describe a solid shape, as they lack connectivity. This is created by the addition of another level of geometry: the polygon.

Polygon
A polygon is a many-sided shape, created from a series of inter-connected edges. A polygon must therefore contain a list of edges, and the order of these edges will determine the way that the polygon, or “face”, faces. But single polygons cannot be taken as an enclosed object, and for that we need a set, or collection of them – this can be labeled as a mesh.

Mesh
Meshes are quite simply a collection of polygons. They can therefore have transformations applied to them, which will apply hierarchically to the entire set of components. In this way all of the mesh can be taken as a single entity. This simplifies the objectiveness of the scene, and the visualization of performing the requisite operations.

The data structures can be constructed in such a way as to make the data-handling simpler. The mesh needs to contain a dynamic list of the polygons contained:

MESH  POLYGON
                POLYGON
                POLYGON
                POLYGON
                     ….
            Position

This is virtually all of the information we need to describe an object at this level of abstraction.

Each polygon will need to somehow contain connected series’ of vertexes and edges interlocked together. We can do this by having each vertex connect to an edge, and each edge connects to another vertex in the chain – and so on until the end. The data structure can therefore be modified to include this:

MESH  POLYGON  VERTEX  EDGE  VERTEX  EDGE ………
                POLYGON
                POLYGON
                POLYGON
                       ….
             Position
This data structure will enable us to control all aspects of the geometry. It also has the benefit of being totally dynamic, as we can add or remove any components at will without destroying the object’s connectivity.

Booleans
On top of this geometric layer, another layer will be built. This layer will handle the actual Boolean operations to be performed on the created geometry. This set of functions will make use of the underlying structure to gradually build up in complexity until very large sets of processes are performed from the components.

Any Boolean operation involves several steps. At the highest level, the object must be intersected with another object. This can be loosely defined as the common space occupied by the two objects is operated on by the algorithm.

There are three main types of Boolean operation that can be performed:

Subtraction – one object is literally removed from the other - all portions of the object is deleted from the other object. This is the operation which we will be using in the sculpting program, as it most closely reflects the real-life sculpting process.

Intersection – The resulting object is comprised of the common portions of the two objects.

Addition – The resulting object is the combined whole of the two objects.

As mentioned, the subtraction operation will be used in this program, though all types of operation can be derived from one basic algorithm.

The layered structure of a basic Boolean subtraction algorithm can be shown as such:

Object  Object Intersection algorithm
This is the top-level function. It takes two meshes and subtracts one from the other to create a resulting mesh. For every polygon in the parent mesh, we call the Polygon  Object intersection algorithm.

Polygon  Object intersection algorithm
This is repeated for every polygon in the mesh. For every polygon in the second mesh, we call the Polygon  Polygon intersection algorithm.

Polygon  Polygon intersection algorithm
This is repeated for every polygon in the second mesh. For every edge in the polygon, we call the Edge  Polygon intersection algorithm.

Edge  Polygon intersection algorithm
Repeated for all edges in the polygon. This generates intersected points.

The outcome of the algorithm is that we are left with a list of polygons that intersect other polygons, and a list of vertices, which represent the actual positions of these intersections. These vertices are also connected to the edges which were intersected in the first place.

Once we have the positions of the intersections, we can use this information to create new geometry, or change the existing geometry to reflect the desired operation.

This is a simple example of geometry that may be used in such an operation – it is comprised of two polygons or arbitrary edges.

Two polygons A and B, intersect along the dotted line

The Circles mark the generated intersection points

The polygon is cut along the lines of intersection, and the edges are split into pairs along these points

This is all very well for a simple case like this, but a true subtraction requires a more advanced operation:

This time, three polygons form a more complex scene. Two of the polygons actually form a hull segment, which would cut the third polygon into two pieces.

Polygons B and C cut across the width of polygon A

Once again, the intersection points are generated, and the edges which coincide with them are split into two separate, smaller edges

From these new edges, we can create a new polygon from A, creating polygon D. This is achieved by re-ordering the polygon edges and vertices’ order, sealing off some of the first polygons’ edges, and splicing them anew into a new polygon object

From this more complex but still simple case, we can see how the object has been separated into new geometry. From the type of Boolean operation we need to perform, we can now discard some of the created geometry. In a subtraction, we would discard polygon D, assuming that polygons B and C make up some of the tool mesh.

This same technique would be repeated for all of the polygons in the meshes, eventually removing all intersected parts of the object form the tool, thus completing the subtraction process.
Code
Now that we have explored the basic algorithm in a theoretical sense, and it seems to be viable in terms of producing the required results, we can move on to deciding how to convert the process into an application.

Wrappers
When coding, I usually subscribe to a ‘wrappered’ approach – all elements of the application are contained within a neat object-orientated package – and similar or common packages are grouped under a parent package to make navigation easier.

A wrapper object is essentially a created entity which can contain other packages, and functions to operate on them. In this particular application we will define a ‘root’ wrapper, which we will name application.

This application class will contain the next level of elements, in order of most general to most specialized. A typical hierarchal structure of an application such as this would follow the same basic rules – even in a non-specific format.

application
The root class

	control
	contains all input functionality, handles the keyboard and the mouse

		mouse
		handles all mouse functionality, events and movement

		keyboard
		contains all keyboard functionality, and the current state of each key
	display
contains all camera and viewport parameters and functionality. Handles rendering of the scene

		camera
		contains all camera functionality, and functions to move/orient the camera

		viewport
		holds the current viewport configuration, with functions to control it

	elements
	contains all of the geometry, and all of the unique meshes in the scene

		meshes
		list of all of the meshes in the scene

	resources
	contains all of the textures, sound, and any other instanced resource in the application

		textures
		handles loading/saving of textures, and holds all currently loaded textures

		sounds
		load/save and containment of sound files. This is not required for this application

		sprites
		custom mouse cursors and graphical effects are contained here

This layout is not necessarily the most efficient structure, or even the easiest to perform, but it does produce a reasonably clear coding style to create applications quickly from a standard basis. Components – such as the sound module – can therefore be dropped from the code as they are not needed, or added later if more functionality is required.
Functions
In addition to the data structures themselves, the entire program is constructed from functions. These functions have been tailored to operate in the scope of the object that it has most effect on. For instance, the mesh object will contain the function intersectWithMesh. This function, though self explanatory, will accept another mesh as a parameter, and be inside the scope of the parent mesh. The mesh passed in will be taken to be the tool mesh, and if a subtraction is required, then this second mesh will be subtracted from the parent. 

IntersectWithMesh also takes the required Boolean operation as an enumerated type as its second parameter. This enumeration will have three main states: B_OP_SUBTRACTION, B_OP_ADDITION and B_OP_INTERSECTION. By passing in any of these types, we can tune the output of the operation itself. The declaration for this function would appear as follows in the code itself:

S_MESH *S_MESH::intersectWithMesh( S_MESH *toolMesh, B_OP_TYPE opType);

Here we can see that the function returns another mesh object, which will be the object as a result of the required operation between the required meshes.

This function – which is the most important, core function of the application, will in turn call other functions as explained in the algorithm hierarchy above. The next level of the function structure would be the intersectWithMesh function, which is called from every polygon object inside the parent mesh. This function once again takes the mesh as an input, but needs no operation type, as this is used by the topmost level function, after all lower-level functions have returned successfully.

The declaration for this function would be as follows:

int S_POLY::intersectWithMesh( S_MESH *toolMesh );

This will go through all polygons in the other mesh, and call the next level function for each. This function will be the intersectWithPolygon function:

int S_POLY::intersectWithPolygon( S_POLY *polygon );

inside this function, the true mathematics of the application are performed, as each edge of the polygon is intersected with the other polygon. For each edge, yet another nested function is called, this time it operates on the edge data structure, and will return intersection points for further processing:

S_VERTEX *S_EDGE::intersectWithPolygon( S_POLY *polygon );

This function applies primitive ray/plane intersection mathematics on the specified edge and face, and the generated points are saved into a temporary data structure, linked to the edges and faces which caused the intersections.

Ray-Plane Intersection
This simple algorithm operates on a line and a plane, in order to determine whether the two will meet, and supplies us with the point where this occurs.

Here we can see two vertexes, which lie either side of a plane. The two vertices can be linked by the line as shown.

The line creates what we will call a ray in three-dimensional space, and we can clearly see that this ray intersects the polygon.

By taking the normal (perpendicular ray of the surface) of the plane, we can discover the angle between the vertex ray, and that of the normal.

This gives us angle c. By taking the dot product of the ray vector from the origin and the normal of the plane, and subtracting this from the distance of the plane from the origin, we can discover the distance of our ray from the plane itself, simply by dividing it by the angle c.

This leaves us with the distance d. This distance is quite simply the parametric length of the ray which lies on one side of the plane, in the range of 0 to 1. Using trivial mathematics we can therefore discover the location of the point which will lie on this plane – using the equation:

Ipx = Ax + d * (Bx-Ax)

Where IPx is the intersection point’s x coordinates, Ax is the x coordinate of the vertex A, d is the parametric distance to the plane, and the last portion (Bx-Ax) simply denotes the ray’s vector x component.

Ipy = Ay + d * (By-Ay)
Ipz = Az + d * (Bz-Az)

Would therefore give us the final two components to enable us to describe the intersection point in true 3D space.

Geometry Creation
With all of the intersection points defined, and a link established to the edge and face which was intersected to create them, we can now define new geometry to reflect the operation performed. In our case, using the subtraction operation type, we will be splitting all polygons intersected into two new polygons along the lines of intersection.

If we consider a polygon to be a connected ring of vertices and edges joined together, then we see that it has no real beginning or end, except that of which we give it by the linear nature of our data structure:

firstVertex -> firstEdge -> nextVertex -> nextEdge ... -> FirstVertex

by sheer definition we have a beginning and end – as the beginning is simply the first vertex that we can point to in the ring, and the end is simply the one before the first vertex comes around again. The same applies to edges in this system.

When a polygon is cleanly sliced by intersections, we are left with two new vertexes in the system. Immediately after intersection the polygon itself is left visibly unchanged, although the underlying data structure is now different (it has two new vertices and edges in the chain).

To illustrate this consider the following diagram:

Here we have a polygon A, which is sliced neatly by another polygon (shown in profile) B. The original polygon is a neat ring of connections, one vertex leading to an edge leading to another vertex.

But when the intersection occurs, the polygon A will have an addition of two new vertexes applied to its structure.

As we can see, two new vertexes v1 and v2 have been created, and two new edges e1 and e2 have been created to connect them to the existing structure. Although the polygon now has more vertexes, its outward appearance seems unchanged.

We can see the normal of the intersecting polygon faces one particular way (normal vector N). If we are applying a subtraction, then we will want to discard anything of polygon A, which lies behind (on the reverse face) of polygon B. We can do this by recording at intersection time the state of the edges that we have intersected, and classing them as either leaving or entering the face of polygon B. For example, looking at the following diagram: 

From this diagram we can see that the polygon A has a normal facing in the direction N. The two edges e1 and e2 are sections of a polygon, which is intersected cleanly by A. Each edge is a vector, and so has a direction. The directions of e1 and e2 are shown as arrows on the diagram. 

If we take the “front” of the polygon A as being where the normal is facing toward (the usual convention), then we can label edge e1 as “leaving” the face – it is going from “inside” the polygon to “outside” the polygon, even though these names have no real significance on an example as simple as this, with no convex solid shapes.

In this respect, we can also label edge e2 as “entering” the polygon. This information is important, and is not difficult to compute – it can be incorporated into the ray-plane algorithm – and enables us to discard sections of sliced polygons quickly and efficiently.

If we take the above example, and extend it to take the entire polygon into view, then we can see how the polygon can be split.

Here we have a simple polygon  polygon intersection, with the intersection points computed, and the new edges inserted into the polygon’s structure correctly. To split this polygon into its two new component parts, it is clear that the slice-line is to be on the edge of the two intersection points, joined together to make a new edge.

Here the new edge can be seen, cutting the polygon cleanly into two obvious segments. We must now separate the polygon into its two parts, whilst maintaining the order of the vertex/edge connections – otherwise the polygon will not display properly.

This can be achieved by creating two new empty polygon structures. To each of these structures we will add the first intersection point as the first vertex, and for the first of the two polygons we will add the second intersection point as the second vertex – adding the intersection edge as the first edge to connect them.

We then simply follow the original connection list around the polygon, adding the edges and vertices to the new polygon as we go. We carry on this in this way until we encounter the first intersection point again, at which point we stop, and link the final point to this vertex, thus completing the enclosed polygonal object.

For the other part of the polygon, we start at the first intersection point, but follow it to the next vertex in the original chain.

We then follow this until we meet the second intersection point, at which time we can link it to the first intersection point, to create our second component of the slice. This last edge must be reversed to achieve continuity; otherwise the vertex/edge chain cannot be traversed correctly.

Actuation
We now have all the components that we require to fill in the functions themselves – we have the algorithms, split into reasonable sized chunks for easy coding, we have the data structures, again divided into useful components, and we have the function declarations, knowing which parameters we will need, what they must give us, and what must be carried out in each function.

The visual C++ code itself is contained within the appendix, however after completing a working prototype of the program, several serious issues arose from the seemingly complete set of algorithm/psuedo-code theoretical ideas that we had developed to aid us in the actuation of our application.

Although no theoretical idea can ever transfer seamlessly into reality, the number of problems that I encountered whilst coding surprised me. Errors in the theoretical side only became exposed after trying to code the ideas into workable script.

Floating and Edged Intersections
The most major of these was the discovery of two distinct types of intersection point: The “edged” point – one which lies neatly on an edge – and the “floating” point – one which is suspended on the plane of another polygon.

To better explain this we can see the previous diagrams of a segmented hull slicing a polygon into two pieces:

Previously we simply considered that this would work, as when considering a single case of a polygon being split, we assumed the split would occur as such: 

This, however, is not always the case – as we can see from these very different diagrams. The top situation does not hold true for the bottom, and vice-versa, as in the top case neither of the tool polygons cleanly slices the object polygon into two – the slice is a combination of two separate slices that meet - the problem is not one of mathematics in this case, but one of the scope of the actual code being used.

The meeting point of two separate slices is not a physical object – it is simply a coincidence of two operations which are not connected in any real form – apart form the geometric significance of two intersection end-points coinciding at one position. This point took me many days to class as a new type of intersection point – named a “floating intersection”. 

Once I had made this mental leap, I discovered that I could operate on the intersection points at a higher level – not inside the polygon  polygon intersection level, but right at the top of the structure, inside the mesh  mesh intersection function. The advantage of this is that all of the intersections have been made at this point, and all “floating” points should have their “partners” – the other floating point in the same 3D space – already processed and classed as such.

We can then search the polygon for the “partner” point, and make a linkage between the two points – gradually creating a list of intersections across the polygon. This lets us slice a polygon using a corner or such piece of geometry, and a new case of slice must be coded to cater for this special case of intersection.

This floating intersection case can be extended to cater for any amount of floating points, they simply need to be linked in the correct order by using their floating pairs to determine the next floating point in the chain.

This diagram shows a particularly complex intersection – the thicker chain does not comprise of edges, but of separate polygons, each one cutting another section form the polygon. Even scenes like this may be computed accurately using this method of intersection.

Normals
The other most notable problem that I encountered was that of the so-called “winding-order” of the polygons created. The winding order is the order in which the vertexes are joined to each other through the edges, for example this polygon:

looks no different to this one:

Though it can be noted that the edges revolve in a different direction – a different winding order is present.

Even though this does not seem very important at this stage – the visual Image is not changed (unless back-face culling is present) – it has a very large effect when another Boolean operation is performed onto the polygon. This outcome would be simply that the entering/leaving face discrimination would be fundamentally altered, and the program could not discern which faces to delete, and which to keep.

The actual problem itself concerned the usage of arbitrary-sided polygons (or 3,4 or more edges), and the fact that a polygon of more than 4 side can be classed as either “convex” or concave” in shape. A convex polygon is one where all the angles between edges are less than 180 degrees from the line of the edge:

This polygon has at least 180 degrees between all of its corresponding edges. A concave polygon however does not, and can appear as such:

This creates problems when finding the normal of this polygon, as a concave polygon can sometimes cause the normal of the polygon to “flip” to face exactly the opposite way to which it meant. Using the standard normal-finding algorithm is therefore ineffectual in this fact. It was a long time before I realized that this was the reason that the outputs to the intersection module were facing the “wrong” way.

An improved (but slightly slower) method for computing normals is as such:

A =  (yi – yj) . (zi + zj)

B =  (zi – zj) . (xi + xj)

C =  (xi – xj) . (yi + yj)

Repeating for all vertexes I = 0  numVertices, and j = I +1

This simply loops all of the vertices in the polygon, and adds the equations for the current - and next - vertex together, eventually finding the three components, A B and C, which are the x y and z components of the normal of the polygon. Although this is far slower than simply the dot product of two edges of the polygon, it does cater for all complex types of polygons.

One final problem I encountered, also to do with polygon normals, was the fact that when using parts of the tool mesh to create geometry for the final mesh, I needed to flip the normals in order to preserve continuity across the final surface:

This scene contains two meshes A and B, each with four polygons.

If we subtract mesh B from A in this case, we realize that parts of B will actually go to form the final surface, as such:

In this resulting mesh, you can see that the two intersect polygons are actually parts of the other mesh B, and that they do not conform to the edge order of the other polygons.

This causes a problem because the two offending polygons will face inwards – and with back-face culling enabled will appear transparent. This is not the worst of our problems, as if another Booleans operation is performed, then again, the entering/leaving information will be reversed, and the wrong piece of a mesh may be deleted from the scene.

The solution to this problem actually turned out to be reasonably simple. An additional piece of data was attached to all intersected polygons – the parent mesh, held in another enumerated type, S_PARENT_MESH_TYPE. S_PARENT_MESH_TYPE can therefore be either S_PARENT_MESH_OBJECT or S_PARENT_MESH_TOOL. Any polygons that have come from the tool mesh are therefore flagged as such, and after intersection has occurred, and the new polygons have been formed, we can make sure that we flip them accordingly.

Viability
Even after all of the major problems had been solved to a usable extent, the program is still by no means complete – many hours of beta-testing would be required and hundreds of hours of bug-detection and removal would be needed in order to “finish” the project to a commercial degree. 

This being said – a commercial product was not the anticipated end to the project, what was required was simply a test of viability of the idea that a more artistically-inclined modeling environment could be created, and that it would be useable up to the restrictions imposed by development time and resources.

To this end I say that I have definitely succeeded in producing a piece of software that demonstrates a large gap in the software market for more intuitive systems for both modeling – and all other forms of computer creation, from animation and texturing to other fields such as sound design and video-editing.

Now that the computer field is no longer simply the reign of technical people alone, the software that these people are applying to projects must adapt to suit the needs of a less scientific set of users.

This project could be extended almost infinitely into all forms of the modeling development cycle, features such as intuitive texture placement and support for parametric surfaces such as NURBS and even sub-division surfaces could be included, and of course eventually animation may be added in order to create a complete package for the more artistically inclined user. 

The one thing that all of these modules would have to uphold would be the general design ideal of simple, mouse-driven interfaces, without hundreds of controls or commands, and a more “touchy-feely” environment, to produce more aesthetic work in a shorter time span.

Scott Griffiths
Innovations
BA Computer Animation

Appendix A
Boolean Intersection Algorithm Code

The appendix contains all of the core code used in the intersection algorithm. Trivial functions such as  normalizing(), dotProduct(), crossProduct(), e.t.c. have been removed, as they are standard across all packages. The entire code can be found on the accompanying CD-ROM, along with the header files and the modular driver process, including the geometry library that I created for the application.

MESH  MESH intersection function

S_MESH *S_MESH::booleanIntersect(S_MESH *mesh){

S_OPERATION_TYPE OPERATION = S_OP_SUBTRACTION;

	numIntPolys = 0;
	numUnintPolys = 0;

	S_MESH *newMesh = new S_MESH(EMPTY);

//reset int counter...
	S_POLY *cpoly = this->pfirst;
	while(cpoly)
	{
		cpoly->reset();
		cpoly = cpoly->pnext;
	}
//reset int counter...	
	cpoly = mesh->pfirst;
	while(cpoly)
	{
		cpoly->reset();
		cpoly = cpoly->pnext;
	}

//intersect all faces of tool with object...
	cpoly = mesh->pfirst;
	while(cpoly)
	{
		cpoly->intersectWithObject(this, S_MP_TOOL );
		cpoly = cpoly->pnext;
	}

this->pfirst = NULL;
this->plast = NULL;
this->numPolys = 0;

for (int cvint = 0; cvint < numIntPolys; cvint ++ )
{
	
	S_VERTEX *currentVertex;
	S_VERTEX *nextVertex;
	S_EDGE	 *currentEdge;
	S_POLY	*newPoly;

	int thisPart = 0;

//if this is a floating point generated polygon...
	if ( intPolys[cvint]->num_ints == 4 && intPolys[cvint]->v_ints[0].type == INT_NORMAL )
	{

//smaller part...
		if (intPolys[cvint]->v_ints[0].edge == intPolys[cvint]->firstVertex->nextEdge){
			if (intPolys[cvint]->v_ints[0].enteringFace == 0) thisPart = 2;
			if (intPolys[cvint]->v_ints[0].enteringFace == 1) thisPart = 1;

			if ( OPERATION == S_OP_SUBTRACTION
				&& ((intPolys[cvint]->meshPart == S_MP_OBJECT && thisPart == 1)
				|| (intPolys[cvint]->meshPart == S_MP_TOOL && thisPart == 2))
			)
			{
				S_EDGE	*newEdge = new S_EDGE( 0 );
				S_EDGE	*newEdge2 = new S_EDGE( 0 );
				S_VERTEX *newVert1,*newVert2,*newVert3;

				newVert1 = new S_VERTEX( *( intPolys[cvint]->v_ints[0].intersectPoint ) );
				newVert2 = new S_VERTEX( *( intPolys[cvint]->v_ints[1].intersectPoint ) );
				newVert3 = new S_VERTEX( *( intPolys[cvint]->v_ints[2].intersectPoint ) );
				nextVertex = new S_VERTEX( *(intPolys[cvint]->v_ints[0].edge->nextVertex) );

				newPoly = new S_POLY();
				
				newPoly->meshPart = intPolys[cvint]->meshPart;

				(*this) += newPoly;

				(*newPoly) += newVert1;
				(*newVert1) += newEdge;
				(*newEdge) += newVert2;
				(*newVert2) += newEdge2;
				(*newEdge2) += newVert3;
		
				currentVertex = newVert3;
				currentEdge = new S_EDGE(0);
				
				while(1)
				{
					
					if (!currentVertex) break;
					if (!nextVertex) break;
					
					if (currentEdge->intersected)
					{
						S_EDGE	*newEdge = new S_EDGE(0);
						
						(*currentVertex) += newEdge;
						(*newEdge) += newPoly->firstVertex;
						break;
					}
					
					S_EDGE	*newEdge = new S_EDGE(0);
					
					(*currentVertex) += newEdge;
					(*newEdge) += nextVertex;

					currentVertex = nextVertex;
					currentEdge = nextVertex->nextEdge;
					nextVertex = new S_VERTEX( *(nextVertex->nextEdge->nextVertex));
				}
				if (intPolys[cvint]->meshPart == S_MP_TOOL) newPoly->flip();
			}
		}
		else
		{
			if (intPolys[cvint]->v_ints[2].enteringFace == 0) thisPart = 1;
			if (intPolys[cvint]->v_ints[2].enteringFace == 1) thisPart = 2;

			if ( OPERATION == S_OP_SUBTRACTION
				&& ((intPolys[cvint]->meshPart == S_MP_OBJECT && thisPart == 1)
				|| (intPolys[cvint]->meshPart == S_MP_TOOL && thisPart == 2))
			){

				S_EDGE	*newEdge = new S_EDGE( 0 );
				S_EDGE	*newEdge2 = new S_EDGE( 0 );
				S_VERTEX *newVert1,*newVert2,*newVert3;

				newVert1 = new S_VERTEX( *( intPolys[cvint]->v_ints[2].intersectPoint ) );
				newVert2 = new S_VERTEX( *( intPolys[cvint]->v_ints[1].intersectPoint ) );
				newVert3 = new S_VERTEX( *( intPolys[cvint]->v_ints[0].intersectPoint ) );
				nextVertex = new S_VERTEX( *(intPolys[cvint]->v_ints[0].edge->nextVertex) );
				
				newPoly = new S_POLY();

				newPoly->meshPart = intPolys[cvint]->meshPart;
				
				(*this) += newPoly;
				
				(*newPoly) += newVert1;

				(*newVert1) += newEdge;
				(*newEdge) += newVert2;
				(*newVert2) += newEdge2;
				(*newEdge2) += newVert3;

				currentVertex = newVert3;
				currentEdge = new S_EDGE(0);
				
				while(1)
				{
					
					if (!currentVertex) break;
					if (!nextVertex) break;
					
					if (currentEdge->intersected)
					{

						S_EDGE	*newEdge = new S_EDGE(0);
						(*currentVertex) += newEdge;
   						(*newEdge) += newVert1;

						break;
					}
					
					S_EDGE	*newEdge = new S_EDGE(0);
					
					(*currentVertex) += newEdge;
					(*newEdge) += nextVertex;

					currentVertex = nextVertex;
					currentEdge = nextVertex->nextEdge;
					nextVertex = new S_VERTEX( *(nextVertex->nextEdge->nextVertex));
				}

				if (intPolys[cvint]->meshPart == S_MP_TOOL) newPoly->flip();
			}
		}

//larger part...

		if (intPolys[cvint]->v_ints[2].enteringFace == 0) thisPart = 2;
		if (intPolys[cvint]->v_ints[2].enteringFace == 1) thisPart = 1;

		if ( OPERATION == S_OP_SUBTRACTION
			&& ((intPolys[cvint]->meshPart == S_MP_OBJECT && thisPart == 1)
			|| (intPolys[cvint]->meshPart == S_MP_TOOL && thisPart == 2))
		){

			S_EDGE	*newEdge = new S_EDGE( 0 );
			S_EDGE	*newEdge2 = new S_EDGE( 0 );
			S_VERTEX *newVert1,*newVert2,*newVert3;

			newVert1 = new S_VERTEX( *( intPolys[cvint]->v_ints[2].intersectPoint ) );
			newVert2 = new S_VERTEX( *( intPolys[cvint]->v_ints[0].intersectPoint ) );
			newVert3 = new S_VERTEX( *( intPolys[cvint]->v_ints[1].intersectPoint ) );
			nextVertex = new S_VERTEX( *(intPolys[cvint]->v_ints[2].edge->nextVertex) );

			newPoly = new S_POLY();
			
			newPoly->meshPart = intPolys[cvint]->meshPart;
			
			(*this) += newPoly;
			
			(*newPoly) += newVert1;

			(*newVert1) += newEdge;
			(*newEdge) += newVert2;
			(*newVert2) += newEdge2;
			(*newEdge2) += newVert3;

			currentVertex = newVert1;
			currentEdge = new S_EDGE(0);
			
			while(1)
			{
				
				if (!currentVertex) break;
				if (!nextVertex) break;
				
				if (currentEdge->intersected)
				{
					S_EDGE	*newEdge = new S_EDGE(0);
					(*currentVertex) += newEdge;
   					(*newEdge) += newVert2;

					S_EDGE	*newEdge2 = new S_EDGE(0);
					(*newVert2) += newEdge2;
   					(*newEdge2) += newVert3;

					S_EDGE	*newEdge3 = new S_EDGE(0);
					(*newVert3) += newEdge3;
   					(*newEdge3) += newVert1;

					break;
				}
				
				S_EDGE	*newEdge = new S_EDGE(0);
				
				(*currentVertex) += newEdge;
				(*newEdge) += nextVertex;

				currentVertex = nextVertex;
				currentEdge = nextVertex->nextEdge;
				nextVertex = new S_VERTEX( *(nextVertex->nextEdge->nextVertex));
			}

			if (intPolys[cvint]->meshPart == S_MP_TOOL) newPoly->flip();
		}
	}
	
//=====================================================================================================

//if this is a straight-cut generated polygon...
	if ( intPolys[cvint]->num_ints == 2 && intPolys[cvint]->v_ints[0].type == INT_NORMAL)
	{
		
		if (intPolys[cvint]->v_ints[1].enteringFace == 0) thisPart = 1;
		if (intPolys[cvint]->v_ints[1].enteringFace == 1) thisPart = 2;

		if ( OPERATION == S_OP_SUBTRACTION
			&& ((intPolys[cvint]->meshPart == S_MP_OBJECT && thisPart == 2)
			|| (intPolys[cvint]->meshPart == S_MP_TOOL && thisPart == 1))
		){
			S_EDGE	*newEdge = new S_EDGE( 0 );
			S_EDGE	*newEdge2 = new S_EDGE( 0 );
			S_VERTEX *newVert1 = new S_VERTEX( *( intPolys[cvint]->v_ints[0].intersectPoint ) );
			S_VERTEX *newVert2 = new S_VERTEX( *( intPolys[cvint]->v_ints[1].intersectPoint ) );
			
			newPoly = new S_POLY();
			
			newPoly->meshPart = intPolys[cvint]->meshPart;

			(*this) += newPoly;
			
			(*newPoly) += newVert1;
			(*newVert1) += newEdge;
			(*newEdge) += newVert2;
			
			currentVertex = newVert2;
			nextVertex = new S_VERTEX( *(intPolys[cvint]->v_ints[1].edge->nextVertex) );
			currentEdge = new S_EDGE(0);
			
			while(1)
			{
				
				if (!currentVertex) break;
				if (!nextVertex) break;
				
				if (currentEdge->intersected)
				{
					S_EDGE	*newEdge = new S_EDGE(0);
					
					(*currentVertex) += newEdge;
					(*newEdge) += newPoly->firstVertex;
					break;
				}
				
				S_EDGE	*newEdge = new S_EDGE(0);
				
				(*currentVertex) += newEdge;
				(*newEdge) += nextVertex;

				currentVertex = nextVertex;
				currentEdge = nextVertex->nextEdge;
				nextVertex = new S_VERTEX( *(nextVertex->nextEdge->nextVertex));
				
			}
		}
		else
		{

			S_EDGE	*newEdge = new S_EDGE( 0 );
			S_EDGE	*newEdge2 = new S_EDGE( 0 );
			S_VERTEX *newVert1 = new S_VERTEX( *( intPolys[cvint]->v_ints[1].intersectPoint ) );
			S_VERTEX *newVert2 = new S_VERTEX( *( intPolys[cvint]->v_ints[0].intersectPoint ) );
			
			newPoly = new S_POLY();
			
			newPoly->meshPart = intPolys[cvint]->meshPart;

			(*this) += newPoly;
			
			(*newPoly) += newVert1;
			(*newVert1) += newEdge;
			(*newEdge) += newVert2;
			
			currentVertex = newVert2;
			nextVertex = new S_VERTEX( *(intPolys[cvint]->v_ints[0].edge->nextVertex) );
			currentEdge = new S_EDGE(0);
			
			while(1)
			{
				
				if (!currentVertex) break;
				if (!nextVertex) break;
				
				if (currentEdge->intersected)
				{
					S_EDGE	*newEdge = new S_EDGE(0);
					
					(*currentVertex) += newEdge;
					(*newEdge) += newPoly->firstVertex;
					break;
				}
				
				S_EDGE	*newEdge = new S_EDGE(0);
				
				(*currentVertex) += newEdge;
				(*newEdge) += nextVertex;

				currentVertex = nextVertex;
				currentEdge = nextVertex->nextEdge;
				nextVertex = new S_VERTEX( *(nextVertex->nextEdge->nextVertex));
				
			}	
		}
		if (intPolys[cvint]->meshPart == S_MP_TOOL) newPoly->flip();
	}

//if this is a cutout polygon...
	if ( intPolys[cvint]->num_ints == 6)
	{

		std::vector<S_VERTEX>	cutPolygonInts;

		for (int cvi=0;cvi<6;cvi++)
		{
if (intPolys[cvint]->v_ints[cvi].type == INT_PROCESSED || intPolys[cvint]->v_ints[cvi].type == INT_PROCESSED2) continue;

//add it to our list...
			cutPolygonInts.push_back( *(intPolys[cvint]->v_ints[cvi].intersectPoint) );

			for (int cvi2=0;cvi2<6;cvi2++)
			{
if (cvi == cvi2 || intPolys[cvint]->v_ints[cvi2].type == INT_PROCESSED || intPolys[cvint]->v_ints[cvi2].type == INT_PROCESSED2) continue;
			
				float error = 0.25;

				if (intPolys[cvint]->v_ints[cvi].intersectPoint->x >= intPolys[cvint]->v_ints[cvi2].intersectPoint->x - error && intPolys[cvint]->v_ints[cvi].intersectPoint->x <= intPolys[cvint]->v_ints[cvi2].intersectPoint->x + error && intPolys[cvint]->v_ints[cvi].intersectPoint->y >= intPolys[cvint]->v_ints[cvi2].intersectPoint->y - error && intPolys[cvint]->v_ints[cvi].intersectPoint->y <= intPolys[cvint]->v_ints[cvi2].intersectPoint->y + error && intPolys[cvint]->v_ints[cvi].intersectPoint->z >= intPolys[cvint]->v_ints[cvi2].intersectPoint->z - error && intPolys[cvint]->v_ints[cvi].intersectPoint->z <= intPolys[cvint]->v_ints[cvi2].intersectPoint->z + error)
				{
					intPolys[cvint]->v_ints[cvi2].type = INT_PROCESSED2;
					intPolys[cvint]->v_ints[cvi].type = INT_PROCESSED;
					break;
				}
			}
		}

		S_EDGE	*newEdge = new S_EDGE( 0 );
		S_EDGE	*newEdge2 = new S_EDGE( 0 );
		S_EDGE	*newEdge3 = new S_EDGE( 0 );
		
		S_VERTEX *newVert1 = new S_VERTEX( cutPolygonInts[0] );
		S_VERTEX *newVert2 = new S_VERTEX( cutPolygonInts[1] );
		S_VERTEX *newVert3 = new S_VERTEX( cutPolygonInts[2] );
			
		newPoly = new S_POLY();

		(*this) += newPoly;
			
		(*newPoly) += newVert1;
		(*newVert1) += newEdge;
		(*newEdge) += newVert2;
		(*newVert2) += newEdge2;
		(*newEdge2) += newVert3;
		(*newVert3) += newEdge3;
		(*newEdge3) += newVert1;

		newPoly->flip();
	}

	if ( intPolys[cvint]->num_ints == 8)
	{

		std::vector<S_VERTEX>	cutPolygonInts;

		for (int cvi=0;cvi<8;cvi++)
		{
if (intPolys[cvint]->v_ints[cvi].type == INT_PROCESSED || intPolys[cvint]->v_ints[cvi].type == INT_PROCESSED2) continue;

//add it to our list...
			cutPolygonInts.push_back( *(intPolys[cvint]->v_ints[cvi].intersectPoint) );

			for (int cvi2=0;cvi2<8;cvi2++)
			{
if (cvi == cvi2 || intPolys[cvint]->v_ints[cvi2].type == INT_PROCESSED || intPolys[cvint]->v_ints[cvi2].type == INT_PROCESSED2) continue;
			
				float error = 0.25;

				if (intPolys[cvint]->v_ints[cvi].intersectPoint->x >= intPolys[cvint]->v_ints[cvi2].intersectPoint->x - error && intPolys[cvint]->v_ints[cvi].intersectPoint->x <= intPolys[cvint]->v_ints[cvi2].intersectPoint->x + error && intPolys[cvint]->v_ints[cvi].intersectPoint->y >= intPolys[cvint]->v_ints[cvi2].intersectPoint->y - error && intPolys[cvint]->v_ints[cvi].intersectPoint->y <= intPolys[cvint]->v_ints[cvi2].intersectPoint->y + error && intPolys[cvint]->v_ints[cvi].intersectPoint->z >= intPolys[cvint]->v_ints[cvi2].intersectPoint->z - error && intPolys[cvint]->v_ints[cvi].intersectPoint->z <= intPolys[cvint]->v_ints[cvi2].intersectPoint->z + error)
				{
					intPolys[cvint]->v_ints[cvi2].type = INT_PROCESSED2;
					intPolys[cvint]->v_ints[cvi].type = INT_PROCESSED;
					break;
				}
			}
		}

		S_EDGE	*newEdge = new S_EDGE( 0 );
		S_EDGE	*newEdge2 = new S_EDGE( 0 );
		S_EDGE	*newEdge3 = new S_EDGE( 0 );
		
		S_VERTEX *newVert1 = new S_VERTEX( cutPolygonInts[0] );
		S_VERTEX *newVert2 = new S_VERTEX( cutPolygonInts[1] );
		S_VERTEX *newVert3 = new S_VERTEX( cutPolygonInts[2] );
			
		newPoly = new S_POLY();

		(*this) += newPoly;
			
		(*newPoly) += newVert1;
		(*newVert1) += newEdge;
		(*newEdge) += newVert2;
		(*newVert2) += newEdge2;
		(*newEdge2) += newVert3;
		(*newVert3) += newEdge3;
		(*newEdge3) += newVert1;

		newPoly->flip();

		newEdge = new S_EDGE( 0 );
		newEdge2 = new S_EDGE( 0 );
		newEdge3 = new S_EDGE( 0 );
		
		newVert1 = new S_VERTEX( cutPolygonInts[3] );
		newVert2 = new S_VERTEX( cutPolygonInts[2] );
		newVert3 = new S_VERTEX( cutPolygonInts[1] );
					
		newPoly = new S_POLY();

		(*this) += newPoly;
			
		(*newPoly) += newVert1;
		(*newVert1) += newEdge;
		(*newEdge) += newVert2;
		(*newVert2) += newEdge2;
		(*newEdge2) += newVert3;
		(*newVert3) += newEdge3;
		(*newEdge3) += newVert1;

		newPoly->flip();
	}

}

//add all unintersected polygons back...
	for (int uipoly = 0; uipoly < numUnintPolys; uipoly ++)
	{
		unintPolys[uipoly]->meshPart = S_MP_UNDECIDED;
		
		if (unintPolys[uipoly]->addedAsUnintersected && !unintPolys[uipoly]->addedAsIntersected)
		{
			(*this) += unintPolys[uipoly];
		}

	}

	this->optimise();

	return this;
}

POLY  MESH intersection algorithm

void S_POLY::intersectWithObject( S_MESH *mesh,	S_MESHPART	parentMeshPart)
{

	S_POLY *cpoly = mesh->pfirst;

	while(cpoly)
	{
		this->intersectWithPoly( cpoly, parentMeshPart );
		cpoly = cpoly->pnext;
	}

}

POLY  POLY intersection algorithm

void S_POLY::intersectWithPoly( S_POLY *poly, S_MESHPART	parentMeshPart)
{
	extern S_POLY	*intPolys[1000];
	extern int		numIntPolys;

	extern S_POLY	*unintPolys[1000];
	extern int		numUnintPolys;

	int index = 0;
	S_VERTEX generatedList[10000];

	S_POLY	*tempPoly = NULL;

	V_INTERSECTION	tempV;
	tempV.type = INT_NORMAL;

	int	intersectionOccurred = 0;

//===============================================================
	
//loop all edges of parent polygon...
	S_VERTEX *currentVertex = this->firstVertex;
	while(1)
	{
		if (!currentVertex) break;
		S_EDGE *thisEdge = currentVertex->nextEdge;
		if (!thisEdge) break;
		S_VERTEX *nextVertex = thisEdge->nextVertex;
		if (!nextVertex) break;

//if this edge intersects the target polygon...
		if ( int edgeOrientation = thisEdge->intersectWithPoly( currentVertex, poly, generatedList, &index ))
		{
			
//create a new vertex at the intersection point...
			S_VERTEX *intersectVertex = new S_VERTEX( generatedList[index-1] );

//store this point...
			this->v_ints[this->num_ints].type =	INT_NORMAL;
			this->v_ints[this->num_ints].index = this->num_ints;
			this->v_ints[this->num_ints].intersectPoint = intersectVertex;
			this->v_ints[this->num_ints].edge = thisEdge;
			this->v_ints[this->num_ints].enteringFace = edgeOrientation-1;
			this->v_ints[this->num_ints].floatingTwin = -1;

//link to the intersected edge...
			thisEdge->intersected = 1;
			thisEdge->v_int = &v_ints[this->num_ints];
//increment intersected counter...
			this->num_ints++;

			this->meshPart = parentMeshPart;

//store the floating point point...
			tempV.type = INT_FLOATING;
			tempV.index = poly->num_ints;
			tempV.intersectPoint = intersectVertex;
			tempV.edge = NULL;
			tempV.enteringFace = 0;
			tempV.floatingTwin = -1;

//add this polygon to the list...
			if (this->num_ints == 1)
			{
				intPolys[numIntPolys] = this;
				numIntPolys++;
				this->addedAsIntersected = 1;
			}
			
			intersectionOccurred ++;
		}

//link-list navigation...
		currentVertex = nextVertex;
		if (currentVertex == this->firstVertex) break;
	}

//===============================================================

//loop all edges of target polygon...
	currentVertex = poly->firstVertex;
	while(1)
	{
		if (!currentVertex) break;
		S_EDGE *thisEdge = currentVertex->nextEdge;
		if (!thisEdge) break;
		S_VERTEX *nextVertex = thisEdge->nextVertex;
		if (!nextVertex) break;

//if this edge intersects the parent polygon...
		if ( int edgeOrientation = thisEdge->intersectWithPoly( currentVertex, this, generatedList, &index ))
		{

//create a new vertex at the intersection point...
			S_VERTEX *intersectVertex = new S_VERTEX( generatedList[index-1] );

//store this point...
			poly->v_ints[poly->num_ints].type =	INT_NORMAL;
			poly->v_ints[poly->num_ints].index = poly->num_ints;
			poly->v_ints[poly->num_ints].intersectPoint = intersectVertex;
			poly->v_ints[poly->num_ints].edge = thisEdge;
			poly->v_ints[poly->num_ints].enteringFace = edgeOrientation-1;
			poly->v_ints[poly->num_ints].floatingTwin = -1;

//link to the intersected edge...
			thisEdge->intersected = 1;
			thisEdge->v_int = &v_ints[poly->num_ints];
//increment intersected counter...
			poly->num_ints++;

			if (parentMeshPart == S_MP_OBJECT) poly->meshPart = S_MP_TOOL;
				else poly->meshPart = S_MP_OBJECT;

//store the floating point point...
			this->v_ints[this->num_ints].type =	INT_FLOATING;
			this->v_ints[this->num_ints].index = this->num_ints;
			this->v_ints[this->num_ints].intersectPoint = intersectVertex;
			this->v_ints[this->num_ints].edge = NULL;
			this->v_ints[this->num_ints].enteringFace = 0;
			this->v_ints[this->num_ints].floatingTwin = -1;

//link to the intersected edge...
			thisEdge->intersected = 1;
			thisEdge->v_int = &v_ints[this->num_ints];

			this->checkForTwins( this->num_ints );

//increment intersected counter...
			this->num_ints++;

//add this polygon to the list...
			if (poly->num_ints == 1)
			{
				intPolys[numIntPolys] = poly;
				numIntPolys++;
				poly->addedAsIntersected = 1;
			}
			if (this->num_ints == 1)
			{
				intPolys[numIntPolys] = this;
				numIntPolys++;
				this->addedAsIntersected = 1;
			}
		
			intersectionOccurred ++;
		}

//link-list navigation...
		currentVertex = nextVertex;
		if (currentVertex == poly->firstVertex) break;
	}

//add in a temp poly if exists...
	if (tempV.type == INT_FLOATING)
	{
//store this point...
		poly->v_ints[poly->num_ints] =	tempV;
//increment intersected counter...
		poly->num_ints++;

		poly->addedAsIntersected = 1;
	}

//if this polygon was not intersected at all, and it is part of the original object, then keep it...
	if (!intersectionOccurred)
	{
		//if (parentMeshPart == S_MP_OBJECT)
		//{
			if (!poly->addedAsUnintersected && !poly->addedAsIntersected)
			{
				unintPolys[numUnintPolys] = poly;
				poly->addedAsUnintersected = 1;
				numUnintPolys++;
			}
		//}
}
}
Appendix B
Installation and program use

The program requires no formal installation process. To use it, simply copy the full root directory to a hard disk with adequate space (around 1 MB), then double-click on the “sculptor.exe” file located in the root sculptor directory.

Using the program is very simple:

A Sample view of the sculptor application window

Use the keys W,S, A and D to re-orient the object mesh, and simply click the left-hand mouse button to perform an intersection. The view will be updated accordingly. All faces which have not been intersected will appear green, and all which have will appear blue. Normals are shown projecting from the geometric centers of all polygons, and polygon lists of intersection will be displayed at the top of the viewport once an intersection has occurred. All vertexes are shown as small white dots.

The camera can also be re-orientated by holding the right-hand mouse button whilst dragging the mouse in any direction. This will not change the orientation of the object mesh, but will simply give a different viewpoint of the same mesh. Zooming in and out can be achieved by rolling the mouse-wheel (if equipped).