awesome *alright*

I'll study a bit BSP to be of help with the object lists ;)

I'll study a bit BSP to be of help with the object lists ;)

but isnt Mirrors easier todo with portal rendering?

the mirror is just a portal to a different view of the room, and the portal is set to be not able to enter thru it

the mirror is just a portal to a different view of the room, and the portal is set to be not able to enter thru it

Mirroring is one effect which is easy to accomplish with Portal rendering, true, but it doesn't come cheap - you are simply rendering more polygons than the geometry stipulates are really there, and then you have to pay for it too, by clipping each and every one against the frustum and against the Portal poly.

Environmental texturing, aided by the TL pipeline in hardware, is bound to be faster and still gives visually pleasing results for reflective surfaces.

I'm not pro-bsp, nor am I anti-portal.

The most recent BSP implementation I've seen actually included elements of both rendering systems, ie, it was a BSP which contained portal planes as well as surface planes.

These guys had realized that they could actually add some quality control to the BSP generation algorithm such that the generator could automatically create portals during BSP generation, which could be used to reduce splitting of polygons and improve the balance of the tree - ie, improve both BSP goals at once through minor subdivision of the worldspace via invisible planar surfaces.

How's them apples?

Environmental texturing, aided by the TL pipeline in hardware, is bound to be faster and still gives visually pleasing results for reflective surfaces.

I'm not pro-bsp, nor am I anti-portal.

The most recent BSP implementation I've seen actually included elements of both rendering systems, ie, it was a BSP which contained portal planes as well as surface planes.

These guys had realized that they could actually add some quality control to the BSP generation algorithm such that the generator could automatically create portals during BSP generation, which could be used to reduce splitting of polygons and improve the balance of the tree - ie, improve both BSP goals at once through minor subdivision of the worldspace via invisible planar surfaces.

How's them apples?

I'm seriously considering storing the coordinates for each polygon in "plucker space".

This "plucker space" is a 6D space which is useful for quickly determining whether a ray intersects a polygon or not, and where. Note - not just whether it intersects the PLANE of the polygon, but the GEOMETRY of the polygon, which normally requires a number of ray/plane tests followed by a number of edge/point tests.

This would be extremely useful in a realtime physics simulation involving large numbers of objects in motion as it offers a potential speedup which cannot be easily dismissed.

The cost of this speedup is the precalculation of the PluckerSpace coordinates of each polygon, which in turn describe the polygon's plane as a Plucker HyperPlane.

These would replace the conventional surfacenormal of each polygon.

This "plucker space" is a 6D space which is useful for quickly determining whether a ray intersects a polygon or not, and where. Note - not just whether it intersects the PLANE of the polygon, but the GEOMETRY of the polygon, which normally requires a number of ray/plane tests followed by a number of edge/point tests.

This would be extremely useful in a realtime physics simulation involving large numbers of objects in motion as it offers a potential speedup which cannot be easily dismissed.

The cost of this speedup is the precalculation of the PluckerSpace coordinates of each polygon, which in turn describe the polygon's plane as a Plucker HyperPlane.

These would replace the conventional surfacenormal of each polygon.

I am now absorbing Nathan Whitaker's 'Extracting connectivity information from a BSP tree" whitepaper.

It describes the process of creating Portals between the Leaves of a BSP.

These Portals are then used for VSD (culling) .. if a Portal is visibile, then the Leaf beyond it is visible.

The Portals are not encoded in the BSP at all.

They are generated at runtime from the BSP binary data.

I don't want to implement it yet, but I mean to.

Another great use for these BSP leaf portals is to use them to generate a perLeaf PVS. Alan Baylis has written an excellent tutorial on the subject of generating REALTIME PVS from the LeafPortals of a BSP.

The industry standard is to precalculate this and store it in the binary file.

It's huge, several meg of data for ten thousand poly worlds.

The industry standard is to use RLE and other compressions to get it back down to a reasonable 20 or 30kb, but what a lot of overhead when there's a cheaper way !!

The LeafPortals VSD method places realtime PVS very much within our grasp.

With all due respect to Carmack and Abrash, thanks for all the fish.

It describes the process of creating Portals between the Leaves of a BSP.

These Portals are then used for VSD (culling) .. if a Portal is visibile, then the Leaf beyond it is visible.

The Portals are not encoded in the BSP at all.

They are generated at runtime from the BSP binary data.

I don't want to implement it yet, but I mean to.

Another great use for these BSP leaf portals is to use them to generate a perLeaf PVS. Alan Baylis has written an excellent tutorial on the subject of generating REALTIME PVS from the LeafPortals of a BSP.

The industry standard is to precalculate this and store it in the binary file.

It's huge, several meg of data for ten thousand poly worlds.

The industry standard is to use RLE and other compressions to get it back down to a reasonable 20 or 30kb, but what a lot of overhead when there's a cheaper way !!

The LeafPortals VSD method places realtime PVS very much within our grasp.

With all due respect to Carmack and Abrash, thanks for all the fish.

Just a note to say I've completed the BSP reloader.

I was only reconstructing the Nodes tree before, now I'm reloading the whole lot.

The BSP is reloaded into the following container object:

As you can see, this class only has one public method, and the name is a bit of a giveaway as to its purpose.

pBSPRoot points to a BSPNode object (first in a linked tree).

pVec3Array and pVec2Array are managed arrays of uniqie Vec3 and Vec2 values, respectively, from which the Faces index their primitives.

pTextures is an instance of TextureManager class.

pFaces points to a PolygonManager object, which contains a list of Triangles which are described by the indices of their primitives.

IE - a Triangle has three points - it needs three indices for Position vectors, three indices for UV vectors, and three indices for Normal vectors (pervertex normals), and it also needs a TextureID, which is an indexed Texture.

MeshLoader - the class used to import TriangleSoup from OBJ file format.

It uses ObjectLists to store stuff.

BSPGenerator - the class used to convert a MeshLoader to HSP binary file

BSPNode - the node structure for a reloaded HSPTree

This time it's stored as a LinkedList of Objects (via Pointers).

BSP - the container class used to reload a HSP binary file (uses BSPNode)

I was only reconstructing the Nodes tree before, now I'm reloading the whole lot.

The BSP is reloaded into the following container object:

class BSP, ,C++ compatible

? ? void LoadBinaryFile:pFileName

? ? long pfilemem

? ? long pBSPRoot

? ? long pVec3Array

? ? long pVec2Array

? ? long pTextures

? ? long pFaces

endclass

As you can see, this class only has one public method, and the name is a bit of a giveaway as to its purpose.

pBSPRoot points to a BSPNode object (first in a linked tree).

pVec3Array and pVec2Array are managed arrays of uniqie Vec3 and Vec2 values, respectively, from which the Faces index their primitives.

pTextures is an instance of TextureManager class.

pFaces points to a PolygonManager object, which contains a list of Triangles which are described by the indices of their primitives.

IE - a Triangle has three points - it needs three indices for Position vectors, three indices for UV vectors, and three indices for Normal vectors (pervertex normals), and it also needs a TextureID, which is an indexed Texture.

MeshLoader - the class used to import TriangleSoup from OBJ file format.

It uses ObjectLists to store stuff.

BSPGenerator - the class used to convert a MeshLoader to HSP binary file

BSPNode - the node structure for a reloaded HSPTree

This time it's stored as a LinkedList of Objects (via Pointers).

BSP - the container class used to reload a HSP binary file (uses BSPNode)

I've added a second Method to the BSP class.

It's called CalculateSurfaceNormals.

BSP_LoadBinaryFile now calls it following reloading of the BSP data.

It's the same code as used in BSPGenerator, and should be put in a separate procedure and called from each Method to reduce the filesize a hundred bytes or so if I really gave a crap.

Basically, I'm preparing to try Rendering stuff soon.

It's called CalculateSurfaceNormals.

BSP_LoadBinaryFile now calls it following reloading of the BSP data.

It's the same code as used in BSPGenerator, and should be put in a separate procedure and called from each Method to reduce the filesize a hundred bytes or so if I really gave a crap.

Basically, I'm preparing to try Rendering stuff soon.

I've added a third Method to the BSP class.

It's name is Render, and it renders the BSPTree recursively.

The code is complete but remains unimplemented due to constraints on my time.

I'll see if everything is working nicely soon enough.

Rendering the BSPTree is very easy indeed.

Each node represents a splittingplane which was obtained from a polygon.

At each node, we classify that plane against the position of the camera, using the ClassifyPoint procedure.

We want to know which side of the plane the camera resides.

If the camera is smack on the plane, we consider it as being on the front side for the sake of convention.

Having determined which side the camera is on, we walk the child tree for the OTHER side first and then the child tree for the SAME side second, then having walked both child trees and returned, we draw the splitterplane poly.

The result of this is that the leaf polygons are drawn first, and the root poly drawn always last, and with the exact order being dependant on the location of the camera, but always using painters algorithm.

It's name is Render, and it renders the BSPTree recursively.

The code is complete but remains unimplemented due to constraints on my time.

I'll see if everything is working nicely soon enough.

Rendering the BSPTree is very easy indeed.

Each node represents a splittingplane which was obtained from a polygon.

At each node, we classify that plane against the position of the camera, using the ClassifyPoint procedure.

We want to know which side of the plane the camera resides.

If the camera is smack on the plane, we consider it as being on the front side for the sake of convention.

Having determined which side the camera is on, we walk the child tree for the OTHER side first and then the child tree for the SAME side second, then having walked both child trees and returned, we draw the splitterplane poly.

The result of this is that the leaf polygons are drawn first, and the root poly drawn always last, and with the exact order being dependant on the location of the camera, but always using painters algorithm.

This is an example of a NODEY BSP TREE (as opposed to a LEAFY tree).

The polygons are distributed throughout the Nodes of the Tree.

The other kind, LEAFY, shoves all the polygons down into the LEAF nodes.

NODEY is more useful for collision detection, but LEAFY can render slightly faster (in theory).

Since I will be wanting to perform collision testing against the world surfaces, NODEY seemed more appropriate.

In some BSP tutorials you will see a lot of references to LEAF nodes - for example, what leaf is the Camera within. These tutorials are geared towards LEAFY tree model, and so I want to make a clear distinction.

When you see such references to LEAF nodes, we are really referring to an entire BRANCH of the tree, from Root to Leaf.

LEAFY bsp tutorials describe the partitioned world as being a bunch of spaces represented by the leaves of the BSPTree, and that the Camera can only be inside one Leaf at a time.

For a Nodey BSPTree, the Camera is somewhere between the Root node and one of the Leaves.

IE, it's somewhere on a Branch from Root to some Leaf.

So when we say "what Leaf is the Camera in" we are really saying "what Leaf's Branch is the Camera in".

This was described more clearly in my last post, regarding Rendering the Tree with respect to the Camera position.

Basically the number of LeafNodes of the BSPTree indicates how many separate volumes the world has been chopped into - true - but we must assume that, having discovered during the render recursion process which Leaf is terminal for the Camera's current position, that this Leaf "owns all the Nodes above it, up to and including Root", because all of those bound the volume which the camera is located in.

If we count the Leaf nodes and number them, we can track "which Leaf we are in" just as in a Leafy Tree.

When it comes to creating PORTALS BETWEEN LEAFNODES, we can aplply the Portals between the actual LeafNodes, but must take ALL geometry into account when clipping the Portal polygon (whittling it down to size, as these start massive and are trimmed to the world geometry).

This process is n times faster than actual BSPGeneration, since we are only clipping a couple of triangles against the world, instead of every triangle against every triangle's plane (n = #polygons)

Therefore it should probably remain a runtime processing step - it seems a waste to store all these extra polygons within the BSP file when they can be regenerated relatively quickly.

So why bother creating these "portals between leaves"?

The answer is pretty straightforwards, it's the obvious reason to use Portals every time.

We will cull the portals against the view frustum.

If a portal is visible, then the leaf beyond it is visible.

If a portal is not visible, then neither is the leaf beyond it.

This can speed up render times even more, bringing the actual number of polygons being rendered at any moment down to at most a few hundred in most situations.

Now we have married the best features of BSP and Portal rendering engines.

I've been having some discussions with Ultrano concerning adaptation of his smAlloc memory manager into a utility objectlist container. I hope to squeeze some new life into it before it is relegated to the (pardon the pun) Heap.

I wonder how many people are still following this thread?

Does anyone else have anything to contribute to this thread?

The polygons are distributed throughout the Nodes of the Tree.

The other kind, LEAFY, shoves all the polygons down into the LEAF nodes.

NODEY is more useful for collision detection, but LEAFY can render slightly faster (in theory).

Since I will be wanting to perform collision testing against the world surfaces, NODEY seemed more appropriate.

In some BSP tutorials you will see a lot of references to LEAF nodes - for example, what leaf is the Camera within. These tutorials are geared towards LEAFY tree model, and so I want to make a clear distinction.

When you see such references to LEAF nodes, we are really referring to an entire BRANCH of the tree, from Root to Leaf.

LEAFY bsp tutorials describe the partitioned world as being a bunch of spaces represented by the leaves of the BSPTree, and that the Camera can only be inside one Leaf at a time.

For a Nodey BSPTree, the Camera is somewhere between the Root node and one of the Leaves.

IE, it's somewhere on a Branch from Root to some Leaf.

So when we say "what Leaf is the Camera in" we are really saying "what Leaf's Branch is the Camera in".

This was described more clearly in my last post, regarding Rendering the Tree with respect to the Camera position.

Basically the number of LeafNodes of the BSPTree indicates how many separate volumes the world has been chopped into - true - but we must assume that, having discovered during the render recursion process which Leaf is terminal for the Camera's current position, that this Leaf "owns all the Nodes above it, up to and including Root", because all of those bound the volume which the camera is located in.

If we count the Leaf nodes and number them, we can track "which Leaf we are in" just as in a Leafy Tree.

When it comes to creating PORTALS BETWEEN LEAFNODES, we can aplply the Portals between the actual LeafNodes, but must take ALL geometry into account when clipping the Portal polygon (whittling it down to size, as these start massive and are trimmed to the world geometry).

This process is n times faster than actual BSPGeneration, since we are only clipping a couple of triangles against the world, instead of every triangle against every triangle's plane (n = #polygons)

Therefore it should probably remain a runtime processing step - it seems a waste to store all these extra polygons within the BSP file when they can be regenerated relatively quickly.

So why bother creating these "portals between leaves"?

The answer is pretty straightforwards, it's the obvious reason to use Portals every time.

We will cull the portals against the view frustum.

If a portal is visible, then the leaf beyond it is visible.

If a portal is not visible, then neither is the leaf beyond it.

This can speed up render times even more, bringing the actual number of polygons being rendered at any moment down to at most a few hundred in most situations.

Now we have married the best features of BSP and Portal rendering engines.

I've been having some discussions with Ultrano concerning adaptation of his smAlloc memory manager into a utility objectlist container. I hope to squeeze some new life into it before it is relegated to the (pardon the pun) Heap.

I wonder how many people are still following this thread?

Does anyone else have anything to contribute to this thread?

I try to follow, but I know too little about BSP to make any worthwile comment

but my thought is: are polycount like 0.5m that much on todays hardware and does speed matter that much of reducing polys, doesnt it matter more of organize it to fewest trianglestrip calls and fewest texturechanges and reorder those trianglestrips to be rendered in right order(from meshes)

theoretically if you have a bounch of trianglestrips, couldnt you instead extend each trianglestrip if possible with a hidden quad, that connects to the next trianglestrip etc

so perfect condition you only have one call to a "sewed together" trianglestrip call

but my thought is: are polycount like 0.5m that much on todays hardware and does speed matter that much of reducing polys, doesnt it matter more of organize it to fewest trianglestrip calls and fewest texturechanges and reorder those trianglestrips to be rendered in right order(from meshes)

theoretically if you have a bounch of trianglestrips, couldnt you instead extend each trianglestrip if possible with a hidden quad, that connects to the next trianglestrip etc

so perfect condition you only have one call to a "sewed together" trianglestrip call

Texture thrashing is an important issue - at the last moment, faces need to be sorted by texture id.

This eliminates the thrashing.

We cannot and do not use trianglestrips for the world surfaces encoded in a BSP.

We can however use them in OSP.

One demo I wrote under D3D a while ago , the terraindemo I've mentioned in the past, was an example of heightmapped terrain via a 2D OSP of sorts.

The world was a big square, chopped into 16x16 patches.

Each patch was a collection of trianglestrips.

I could perform culling on a per-patch basis, but I had not generated a Tree containing patch nodes, so I could not employ hierarchical culling methods directly.

This eliminates the thrashing.

We cannot and do not use trianglestrips for the world surfaces encoded in a BSP.

We can however use them in OSP.

One demo I wrote under D3D a while ago , the terraindemo I've mentioned in the past, was an example of heightmapped terrain via a 2D OSP of sorts.

The world was a big square, chopped into 16x16 patches.

Each patch was a collection of trianglestrips.

I could perform culling on a per-patch basis, but I had not generated a Tree containing patch nodes, so I could not employ hierarchical culling methods directly.

Hey Homer

Like daydreamer I don't know enough about BSP to comment constructively but I'm following the thread with increasing interest.

With regards to clipping to portals, do you actually need to clip the visible polys?

If any part of the poly is visible through the portal why not simply draw the entire poly, the resulting overdraw penalty could be less than the overhead of clipping the poly to the portal.

Like daydreamer I don't know enough about BSP to comment constructively but I'm following the thread with increasing interest.

With regards to clipping to portals, do you actually need to clip the visible polys?

If any part of the poly is visible through the portal why not simply draw the entire poly, the resulting overdraw penalty could be less than the overhead of clipping the poly to the portal.

The industry defacto standard seems to be to limit overdraw to no more than 10x per pixel.

If you're only looking at a 3D cube in empty space this isn't a worry.

But if you are drawing a 3D world then you really need to reduce overdraw as much as you can.

In a portal rendering system, especially where used indoors, we can rely on our limited view through portals to limit rendering to no deeper than the next cell (or leaf) most of the time, but occasionally we'll be able to see other portals through the current portal, and the overdraw per pixel can rapidlly increase (especially for outdoor scenes).

Overdraw is exactly what we are trying to prevent, especially when depth buffering is enabled.

Most of the programming madness in 3D stuff has that much in common - they're almost all methods of attempting to reduce or eliminate overdraw, while correctly handling occlusions.

You don't have to clip polygons to the portal, but depending on the implementation, not doing so can lead to visual artifacts (example is a pure portal engine, where portals can connect arbitrary regions of 3D space, ie arbitrary cells). Regardless, the overdraw is the issue of concern.

If you're only looking at a 3D cube in empty space this isn't a worry.

But if you are drawing a 3D world then you really need to reduce overdraw as much as you can.

In a portal rendering system, especially where used indoors, we can rely on our limited view through portals to limit rendering to no deeper than the next cell (or leaf) most of the time, but occasionally we'll be able to see other portals through the current portal, and the overdraw per pixel can rapidlly increase (especially for outdoor scenes).

Overdraw is exactly what we are trying to prevent, especially when depth buffering is enabled.

Most of the programming madness in 3D stuff has that much in common - they're almost all methods of attempting to reduce or eliminate overdraw, while correctly handling occlusions.

You don't have to clip polygons to the portal, but depending on the implementation, not doing so can lead to visual artifacts (example is a pure portal engine, where portals can connect arbitrary regions of 3D space, ie arbitrary cells). Regardless, the overdraw is the issue of concern.

I've been thinking about an OSP implementation where the vertices are relative to the origin of the LeafNode they are within. In turn, the LeafNodes contain the 3D offsets of their origin (to avoid recalculating it all the time) to be used as a translation from world origin during rendering.

The idea appeals to me more because I've recently implemented manager classes for arrays of unique 2D and 3D values which can be referenced via their indices.

It occurred to me when I studied OSP tree generators where I noted that a common first step is to calculate a bounding geometry (cube or sphere) for the entire world, and then generally at this moment, the vertices are all shifted to move the origin of the bounding geometry to conincide with world origin (ie, centralize the world geometry about world zero).

I realized that this could be done at each iteration during the recurive building of the tree, with the offset to the node origin being absolute translation from world origin.

Assuming that any polygons to be rendered by such a system will at least have lighting applied to them in hardware, then we can say they are going to be processed by the TL pipeline and so there's no real cost to perform the translation required to render a node's vertices.

The probability of numeric dupications being discovered by my unique vec2 and vec3 managers is high - I'm effectively using it as a form of realtime vertex compression.

Faces pretty much will always refer to vertices by index, so all I'm really doing is eliminating unnecessary vertices and reducing the number of indices.

I guess this could also apply to a KD-Tree or a BSP-Tree, or N-Tree, it just seems more obvious to me with regards to OSP.

Anyway, the beauty of always basing vertices around a shifted origin is that it allows a very fast classification algorithm during tree generation/modification by simply checking the Sign of the vertices.

We can say that the eight child nodes are +++, ++-, +-+,+--,-++,-+-, --+,--- :)

Another way to do this might be to leave the vertices alone until it comes time to detect collisions, and then transform them into "node space".

This is for when we wish to , for example, create the intersection of a decal crater and the terrain, or when we wish to blow a nice jagged hole in a wall, to handle the intersection across node boundaries where the nodes are at different depth of subdivision.

The idea appeals to me more because I've recently implemented manager classes for arrays of unique 2D and 3D values which can be referenced via their indices.

It occurred to me when I studied OSP tree generators where I noted that a common first step is to calculate a bounding geometry (cube or sphere) for the entire world, and then generally at this moment, the vertices are all shifted to move the origin of the bounding geometry to conincide with world origin (ie, centralize the world geometry about world zero).

I realized that this could be done at each iteration during the recurive building of the tree, with the offset to the node origin being absolute translation from world origin.

Assuming that any polygons to be rendered by such a system will at least have lighting applied to them in hardware, then we can say they are going to be processed by the TL pipeline and so there's no real cost to perform the translation required to render a node's vertices.

The probability of numeric dupications being discovered by my unique vec2 and vec3 managers is high - I'm effectively using it as a form of realtime vertex compression.

Faces pretty much will always refer to vertices by index, so all I'm really doing is eliminating unnecessary vertices and reducing the number of indices.

I guess this could also apply to a KD-Tree or a BSP-Tree, or N-Tree, it just seems more obvious to me with regards to OSP.

Anyway, the beauty of always basing vertices around a shifted origin is that it allows a very fast classification algorithm during tree generation/modification by simply checking the Sign of the vertices.

We can say that the eight child nodes are +++, ++-, +-+,+--,-++,-+-, --+,--- :)

Another way to do this might be to leave the vertices alone until it comes time to detect collisions, and then transform them into "node space".

This is for when we wish to , for example, create the intersection of a decal crater and the terrain, or when we wish to blow a nice jagged hole in a wall, to handle the intersection across node boundaries where the nodes are at different depth of subdivision.

hi.

i m interested in this, since, would you believe it, i m involved in a sort of a student project that deals with building of bsp trees from an arbitrary scene, building "visibility graphs" and "adjacency graphs" and displaying the whole mess in an optimized way. tis hard to stay motivated but i should keep going on. theres a teacher that is a researcher that gives up thesis about bsp... congrats for what you do.well were doing c++,but i m interested in the SplitPolygon function...

bye

i m interested in this, since, would you believe it, i m involved in a sort of a student project that deals with building of bsp trees from an arbitrary scene, building "visibility graphs" and "adjacency graphs" and displaying the whole mess in an optimized way. tis hard to stay motivated but i should keep going on. theres a teacher that is a researcher that gives up thesis about bsp... congrats for what you do.well were doing c++,but i m interested in the SplitPolygon function...

bye

The SplitPolygon procedure actually only works with Triangles in my example, but can work with arbitrary polygons too.

It works by first classifying all Polygon Points against the Plane.

Then we examine the number of points on either side and on the plane to reduce the number of possible outcomes to only three.

1. The triangle is totally on one side of the plane. One, two or even three points may be on the plane, but we push them along the plane normal and classify them as being on the + side.

2. The triangle is split into two triangles. One vertex is on the plane, the other two lay either side of the plane.

3. The triangle is split into three triangles. One vertex is on one side of the plane, the other two vertices are on the other side of the plane.

From these cases, we extrapolate potential triangles based on intersection points.

The SplitPolygon proc I wrote can either actually calculate the split triangles and return them, or it can just perform the classification and return a result implying the split result, used to give a "score" to potential splitplanes when deciding the best plane to split with.

Hope that helped :)

It works by first classifying all Polygon Points against the Plane.

Then we examine the number of points on either side and on the plane to reduce the number of possible outcomes to only three.

1. The triangle is totally on one side of the plane. One, two or even three points may be on the plane, but we push them along the plane normal and classify them as being on the + side.

2. The triangle is split into two triangles. One vertex is on the plane, the other two lay either side of the plane.

3. The triangle is split into three triangles. One vertex is on one side of the plane, the other two vertices are on the other side of the plane.

From these cases, we extrapolate potential triangles based on intersection points.

The SplitPolygon proc I wrote can either actually calculate the split triangles and return them, or it can just perform the classification and return a result implying the split result, used to give a "score" to potential splitplanes when deciding the best plane to split with.

Hope that helped :)

I'm about to rework my BSP code to support quads as well as triangles, and to better handle coplanar polygons.

In the previous post regarding SplitPoly , the third case of a Triangle being split would produce one Triangle and one Quad, rather than three Triangles.

Splitting a Quad results in only a few more Cases.

I've narrowed down the possible Cases for splitting a Quad with a Plane to seven.

Can you think of any more?

(NB - I can modify my existing SplitPoly to handle both types at once, no drama)

1. None of the quad's vertices are on the Plane.

The four vertices are totally on one side of the Plane.

This isn't really an intersecting case.

2. None of the quad's vertices are on the Plane.

Two appear on wither side of the Plane.

The quad is split into two Quads.

3. None of the quad's vertices are on the Plane.

One appears on one side, and three on the other side.

The quad is split into a Triangle (side A) and a Triangle and a Quad (side B).

4. One of the quad's vertices lays on the Plane, the other three are on the same side of the Plane.

The quad is abutting the Plane.

This isn't really an intersecting case.

5. One of the quad's vertices lays on the plane.

One lays on one side, the other two lay on the other side.

The quad is split into a Triangle and a Quad.

6. Two vertices which form an Edge of the quad lay on the Plane.

The other two are on the same side of the Plane.

The quad is abutting the Plane.

This isn't really an intersecting case.

7.. Two vertices which form diagonal corners of the quad lay on the plane.

The other two lay either side of the plane.

The quad is split into two triangles.

The benefit of also supporting quads in the BSP is that we reduce the number of Planes required to both map the world and to perform collision detection against it.

Besides that, I plan on calculating "interleaf portals" soon, which are in fact only invisible quads which "cover the doorways" in the world - they stand between one leaf region and another.

If we hit-detect against these, we can track the nodal location of objects and thus only require surface collision detection against the surfaces in that leafnode, ie, those surfaces which bound the region of space represented by this leafnode.

It would be really handy if we could handle these natively as quads rather than as pairs of triangles because again we are reducing the workload - especially when it comes to stabbing geometry with rays.

In the previous post regarding SplitPoly , the third case of a Triangle being split would produce one Triangle and one Quad, rather than three Triangles.

Splitting a Quad results in only a few more Cases.

I've narrowed down the possible Cases for splitting a Quad with a Plane to seven.

Can you think of any more?

(NB - I can modify my existing SplitPoly to handle both types at once, no drama)

1. None of the quad's vertices are on the Plane.

The four vertices are totally on one side of the Plane.

This isn't really an intersecting case.

2. None of the quad's vertices are on the Plane.

Two appear on wither side of the Plane.

The quad is split into two Quads.

3. None of the quad's vertices are on the Plane.

One appears on one side, and three on the other side.

The quad is split into a Triangle (side A) and a Triangle and a Quad (side B).

4. One of the quad's vertices lays on the Plane, the other three are on the same side of the Plane.

The quad is abutting the Plane.

This isn't really an intersecting case.

5. One of the quad's vertices lays on the plane.

One lays on one side, the other two lay on the other side.

The quad is split into a Triangle and a Quad.

6. Two vertices which form an Edge of the quad lay on the Plane.

The other two are on the same side of the Plane.

The quad is abutting the Plane.

This isn't really an intersecting case.

7.. Two vertices which form diagonal corners of the quad lay on the plane.

The other two lay either side of the plane.

The quad is split into two triangles.

The benefit of also supporting quads in the BSP is that we reduce the number of Planes required to both map the world and to perform collision detection against it.

Besides that, I plan on calculating "interleaf portals" soon, which are in fact only invisible quads which "cover the doorways" in the world - they stand between one leaf region and another.

If we hit-detect against these, we can track the nodal location of objects and thus only require surface collision detection against the surfaces in that leafnode, ie, those surfaces which bound the region of space represented by this leafnode.

It would be really handy if we could handle these natively as quads rather than as pairs of triangles because again we are reducing the workload - especially when it comes to stabbing geometry with rays.

I'm coding it up now.

The number of cases I gave in the last post was overestimated.

Actually, the cases for split classification of a Quad face's vertices are as follows:

1. Front

2. Back

3. TwoFrontTwoBack

4.OneFrontThreeBack

5.ThreeFrontOneBack

We can merge the cases for Tris and Quads and use a modified SplitPoly procedure to handle them both.

SelectBestFace won't care what kind of faces it is evaluating.

It will just call SplitPoly (with intersections disabled) for every combination of face pairs and select the best face based on the absolute difference result, as it already does.

What I'm doing at the moment to handle this stuff is building a list of "references to faces" and then evaluating those.

Since my HSM system stores Faces in Material groups, I tag each reference object with a pointer back to the face's owner material.

I also tag each reference with an indicator of the polygon type (tri or quad).

This allows me to process a simple linear array of the same structure in the poly pair comparator, divide the faces down into sublists, and yet retain the existing material groupings.

At the very least, if I was to process the faces directly, I'd have to rebuild the face arrays to keep a material tag and I'd just be moving larger structures around during processing.

BSPFaceRef struct

? ? TriOrQuad dw ?? ? ? ;<-- identifies whether this refers to a Triangle or Quad face

? ? pMaterial? ?dd ?? ? ? ;<-- points to HSMaterial which owns this face

? ? pFace? ? ? ? dd ?? ? ? ;<-- points to a HSMFace3 or HSMFace4

BSPFaceRef ends

The number of cases I gave in the last post was overestimated.

Actually, the cases for split classification of a Quad face's vertices are as follows:

1. Front

2. Back

3. TwoFrontTwoBack

4.OneFrontThreeBack

5.ThreeFrontOneBack

We can merge the cases for Tris and Quads and use a modified SplitPoly procedure to handle them both.

SelectBestFace won't care what kind of faces it is evaluating.

It will just call SplitPoly (with intersections disabled) for every combination of face pairs and select the best face based on the absolute difference result, as it already does.

What I'm doing at the moment to handle this stuff is building a list of "references to faces" and then evaluating those.

Since my HSM system stores Faces in Material groups, I tag each reference object with a pointer back to the face's owner material.

I also tag each reference with an indicator of the polygon type (tri or quad).

This allows me to process a simple linear array of the same structure in the poly pair comparator, divide the faces down into sublists, and yet retain the existing material groupings.

At the very least, if I was to process the faces directly, I'd have to rebuild the face arrays to keep a material tag and I'd just be moving larger structures around during processing.

BSPFaceRef struct

? ? TriOrQuad dw ?? ? ? ;<-- identifies whether this refers to a Triangle or Quad face

? ? pMaterial? ?dd ?? ? ? ;<-- points to HSMaterial which owns this face

? ? pFace? ? ? ? dd ?? ? ? ;<-- points to a HSMFace3 or HSMFace4

BSPFaceRef ends

Here's the start of the new SplitPoly code.

As you can see, I'm extracting the Planes of faces every time I compare them.

This is bad, but read on.

You can see the first test being performed here anyway.

We are testing whether ALL of the vertices of the subject polygon are resting on the test plane. If they are, we have a special case of coplanar input polygons which we can take advantage of by grouping faces by Plane in the BSP nodes.

(The VertexPointers in a Face are 12 bytes apart...)

Since no splitting is necessary for a coplanar polygon, we theoretically shove the polygon into a front or back list according to whether their normals face the same way or not.

What I'll probably end up doing is calculating the Planes in the code that drives SplitPoly, and handing the Planes to SplitPoly as more input params (reduces total calculations considerably).

Just out of curiosity, who is following these posts?

As you can see, I'm extracting the Planes of faces every time I compare them.

This is bad, but read on.

You can see the first test being performed here anyway.

We are testing whether ALL of the vertices of the subject polygon are resting on the test plane. If they are, we have a special case of coplanar input polygons which we can take advantage of by grouping faces by Plane in the BSP nodes.

(The VertexPointers in a Face are 12 bytes apart...)

Since no splitting is necessary for a coplanar polygon, we theoretically shove the polygon into a front or back list according to whether their normals face the same way or not.

What I'll probably end up doing is calculating the Planes in the code that drives SplitPoly, and handing the Planes to SplitPoly as more input params (reduces total calculations considerably).

Just out of curiosity, who is following these posts?

;=======================================================

;? ?Note that the following code section treats the input polygons (pplanePolygon and ppolygonToSplit)

;? ?as both being TRIANGLES, regardless of whether they are actually Tri or Quad polygons.

;? ?The simple reasoning behind this is that we can treat the first three vertices of a Quad as a Tri

;? ?for the purposes of calculating a surface normal, since a Quad is always flat, we know that if we

;? ?perceive a Quad as two triangles, that both triangles are coplanar.

;? ?The HSMFace3 and HSMFace4 structures were deliberately designed with this in mind.

;=======================================================

;? ?Get the SurfaceNormal of the polygon which is being evaluated for splitting

;? ?We can disregard the actual number of vertices in each polygon for now.

? ? mov ecx,ppolygonToSplit

? ? mov eax,.BSPFaceRef.pFace

? ? invoke SurfaceNormalFromTrianglePoints, .HSMFace3.pvert0,.HSMFace3.pvert1,.HSMFace3.pvert2,addr polysNormal

;? ?Get the SurfaceNormal of the polygon whose plane is being evaluated as the best splitting plane

;? ?We can disregard the actual number of vertices in each polygon for now.

? ? mov ecx,pplanePolygon

? ? mov eax,.BSPFaceRef.pFace

? ? invoke SurfaceNormalFromTrianglePoints, .HSMFace3.pvert0,.HSMFace3.pvert1,.HSMFace3.pvert2,addr planeNormal

;? ?Get a point on the Plane - the first vertex of the planepoly will do just fine.? ?

;? ?Even though the planepoly might be a Face3 or a Face4 - who cares - vert0 is same

? ? mov ecx,pplanePolygon

? ? mov eax,.BSPFaceRef.pFace

? ? m2m ppointOnPlane,.HSMFace3.pvert0

? ? ;----------------------------------------------------------------------------------------------------

? ? ;Check if ALL THREE (OR FOUR?) of the splittee polygon's vertices lie on the splitter plane

? ? ;ie are the Splitter and Splittee CoPlanar?

? ? ;(Hey, won't this only occur if their SurfaceNormals match? or does planeD differ a lot?)

? ? ;----------------------------------------------------------------------------------------------------

? ? mov ecx,ppolygonToSplit

? ? .if .BSPFaceRef.TriOrQuad==0

? ? ? ? mov numVerts,3

? ? .else

? ? ? ? mov numVerts,4

? ? .endi

? ? xor ecx,ecx

? ? mov numPointsOnPlane,ecx

? ? mov ecx,.BSPFaceRef.pFace

? ? lea esi, .HSMFace3.pvert0

? ? xor ecx,ecx

? ? .while ecx<numVerts

? ? ? ? push ecx

? ? ? ? push esi

? ? ? ? invoke ClassifyPoint, dword ptr, ppointOnPlane, addr planeNormal

? ? ? ? .if eax!=0

? ? ? ? ? ? pop esi

? ? ? ? ? ? pop ecx

? ? ? ? ? ? jmp @F

? ? ? ? .endif

? ? ? ? inc numPointsOnPlane

? ? ? ? pop esi

? ? ? ? add esi,3*4? ? ? ?

? ? ? ? pop ecx

? ? ? ? inc ecx

? ? .endw

? ? ;----------------------------------------------------------------------------------------------------

? ? ;Handle Special Case - Splitter and Splittee are CoPlanar

? ? ;----------------------------------------------------------------------------------------------------

;**code goes here

@@:

Here's the current state of my new SplitPoly procedure.

The last input param is a pointer to a buffer to receive new polygons formed during splitting.

If this parameter is NULL, the procedure merely evaluates a potential polysplit.

So far I've handled the following cases (for both tri and quad polys):

-Coplanar

-Abutting

I only have the cases resulting in Splits to code up.

I'm trying to decide which way to go about it.

ClassifyPoint classifies a 3d point against a plane.

The result is signed and indicates which side of the plane the point lays.

Possible return values are -1, +1 and 0.

The following code relies a lot on ClassifyPoint to determine firstly whether the poly and plane are coplanar, and then to determine whether polygon edges intersect the plane.

The second part is really easy.

If we think of a polygon edge as two points in space, and classify both the points against the plane, we can tell if they are both on the same side of the plane or not.

If they are on the same side of the plane, no intersection occurs :)

If they are NOT on the same side, THE EDGE MUST INTERSECT THE PLANE AT SOME POINT - and we can calculate the intersection point using some vector math and the plane equation, or by other means.

Having determined which edges of the polygon intersect the plane, and calculated the intersection points, we can calculate some UV coordinates for the intersection points (we can extrapolate these from the input polygon's vertices).

Finally, we can generate several output polygons based on which edges intersected the plane, the input vertices from the input polygon, and the new vertices from the intersection points.

I must be talking to myself, since I see no replies other than my own :(

The last input param is a pointer to a buffer to receive new polygons formed during splitting.

If this parameter is NULL, the procedure merely evaluates a potential polysplit.

So far I've handled the following cases (for both tri and quad polys):

-Coplanar

-Abutting

I only have the cases resulting in Splits to code up.

I'm trying to decide which way to go about it.

ClassifyPoint classifies a 3d point against a plane.

The result is signed and indicates which side of the plane the point lays.

Possible return values are -1, +1 and 0.

The following code relies a lot on ClassifyPoint to determine firstly whether the poly and plane are coplanar, and then to determine whether polygon edges intersect the plane.

The second part is really easy.

If we think of a polygon edge as two points in space, and classify both the points against the plane, we can tell if they are both on the same side of the plane or not.

If they are on the same side of the plane, no intersection occurs :)

If they are NOT on the same side, THE EDGE MUST INTERSECT THE PLANE AT SOME POINT - and we can calculate the intersection point using some vector math and the plane equation, or by other means.

Having determined which edges of the polygon intersect the plane, and calculated the intersection points, we can calculate some UV coordinates for the intersection points (we can extrapolate these from the input polygon's vertices).

Finally, we can generate several output polygons based on which edges intersected the plane, the input vertices from the input polygon, and the new vertices from the intersection points.

I must be talking to myself, since I see no replies other than my own :(

TEMPVERTEX struct

X REAL4 ?

Y REAL4 ?

Z REAL4 ?

U REAL4 ?

V REAL4 ?

TEMPVERTEX ends

SplitPolygon proc ppolygonToSplit:ptr BSPFaceRef, pplanePolygon:ptr BSPFaceRef, ppolygons:DWORD

local ppointOnPlane:ptr Vec3

local planeNormal:Vec3

local polysNormal:Vec3

local tempVec:Vec3

local inpts[4]:TEMPVERTEX

local outpts[4]:TEMPVERTEX

local numPointsOnPlane ;<-- How many of the polygon's vertices lay on the plane

;These two are counters used to count vertices on each side of plane

;while testing a polygon's Edges (pairs of vertices) against the Plane

local in_c

local out_c

;Two endpoints of an Edge of the polygon to test against the Plane

local ptA:TEMPVERTEX

local ptB:TEMPVERTEX

;These hold the Signed Results after classifying an Edge

;against the Plane. They indicate which side of the Plane

;each endpoint of the Edge exists on, which in turn implies

;whether the Edge and Plane intersect or not.

local sideA:SDWORD

local sideB:SDWORD

;This holds the point on Plane where an Edge intersects it

local intersection:TEMPVERTEX

local outputFlag

;A bunch of variables used while calculating new UV's for intersection points

local x1, x2, y1, y2, z1, z2, u1, u2, v1, v2, ftheScale:REAL4

local iPoint ;Index of current Point (during processing of Points of a Triangle)

local numVerts ;#Vertices in polygon

;================================================================================

; INITIALIZE LOCAL VARIABLES

;================================================================================

xor eax,eax

mov numPointsOnPlane,eax

mov out_c,eax

mov in_c,eax

mov numPointsOnPlane,eax

mov sideA,eax

mov sideB,eax

mov sideC,eax

mov sideD,eax

mov ecx,ppolygonToSplit

.if .BSPFaceRef.TriOrQuad==0

mov numVerts,3

.else

mov numVerts,4

.endi

;================================================================================

; Note that the following code section treats the input polygons (pplanePolygon and ppolygonToSplit)

; as both being TRIANGLES, regardless of whether they are actually Tri or Quad polygons.

; The simple reasoning behind this is that we can treat the first three vertices of a Quad as a Tri

; for the purposes of calculating a surface normal, since a Quad is always flat, we know that if we

; perceive a Quad as two triangles, that both triangles are coplanar.

; The HSMFace3 and HSMFace4 structures were deliberately designed with this in mind.

;================================================================================

; Get the SurfaceNormal of the polygon which is being evaluated for splitting

; We can disregard the actual number of vertices in each polygon for now.

mov ecx,ppolygonToSplit

mov eax,.BSPFaceRef.pFace

invoke SurfaceNormalFromTrianglePoints, .HSMFace3.pvert0,.HSMFace3.pvert1,.HSMFace3.pvert2,addr polysNormal

; Get the SurfaceNormal of the polygon whose plane is being evaluated as the best splitting plane

; We can disregard the actual number of vertices in each polygon for now.

mov ecx,pplanePolygon

mov eax,.BSPFaceRef.pFace

invoke SurfaceNormalFromTrianglePoints, .HSMFace3.pvert0,.HSMFace3.pvert1,.HSMFace3.pvert2,addr planeNormal

; Get a point on the Plane - the first vertex of the planepoly will do just fine.

; Even though the planepoly might be a Face3 or a Face4 - who cares - vert0 is same

mov ecx,pplanePolygon

mov eax,.BSPFaceRef.pFace

m2m ppointOnPlane,.HSMFace3.pvert0

;------------------------------------------------------------------------------------------------------------

;CLASSIFY ALL OF THE POLYGON VERTICES AGAINST THE PLANE

;-------------------------------------------------------------------------------------------------------------

; ptA = polygonToSplit.Vertex[0];

mov eax,polygonToSplit

mov eax,.BSPFaceRef.pFace

mov eax, .HSMFace3.pvert0

fld .Vec3.X

fld .Vec3.Y

fld .Vec3.Z

fstp ptA .Z

fstp ptA .Y

fstp ptA .X

; ptB = polygonToSplit.Vertex[1];

mov eax,polygonToSplit

mov eax,.BSPFaceRef.pFace

mov eax, .HSMFace3.pvert1

fld .Vec3.X

fld .Vec3.Y

fld .Vec3.Z

fstp ptB .Z

fstp ptB .Y

fstp ptB .X

; ptC = polygonToSplit.Vertex[2];

mov eax,polygonToSplit

mov eax,.BSPFaceRef.pFace

mov eax, .HSMFace3.pvert2

fld .Vec3.X

fld .Vec3.Y

fld .Vec3.Z

fstp ptC .Z

fstp ptC.Y

fstp ptC .X

invoke ClassifyPoint, addr ptA, addr pointOnPlane, pplaneNormal

mov sideA,eax

invoke ClassifyPoint,addr ptB, ppointOnPlane, addr planeNormal

mov sideB,eax

invoke ClassifyPoint,addr ptC, ppointOnPlane, addr planeNormal

mov sideC,eax

.if numVerts==4

; ptD = polygonToSplit.Vertex[3];

mov eax,polygonToSplit

mov eax,.BSPFaceRef.pFace

mov eax, .HSMFace3.pvert3

fld .Vec3.X

fld .Vec3.Y

fld .Vec3.Z

fstp ptD .Z

fstp ptD .Y

fstp ptD .X

invoke ClassifyPoint,addr ptD, ppointOnPlane, addr planeNormal

mov sideD,eax

.endif

;----------------------------------------------------------------------------------------------------

;Check if ALL THREE (OR FOUR?) of the splittee polygon's vertices lie on the splitter plane

;ie are the Splitter and Splittee CoPlanar?

;(Hey, won't this only occur if their SurfaceNormals match? or does planeD differ a lot?)

;----------------------------------------------------------------------------------------------------

.if sideA==0

inc numPointsOnPlane

.endif

.if sideB==0

inc numPointsOnPlane

.endif

.if sideC==0

inc numPointsOnPlane

.endif

.if numVerts==4

.if sideD==0

inc numPointsOnPlane

.endif

.endif

mov eax,numPointsOnPlane

.if eax==numVerts

;----------------------------------------------------------------------------------------------------

;Handle Special Case - Splitter and Splittee are CoPlanar

;No splitting will be necessary, but we'll still have to make

;a decision about whether to call this a Front or Back face.

;----------------------------------------------------------------------------------------------------

;Decide whether to toss the splittee into the front or back list

;based on whether the normals face the same way or not.

;Since the normals may differ very slightly due to fpu error and epsilon value,

;simply comparing them is a bad move.

;We could add them and see if the result is near zero, but we're still pissing around.

;Let's do it right and use the poly's normal as a testpoint

;by adding the poly's normal and first vertex and testing against Plane

;----------------------------------------------------------------------------------------------------

mov ecx,pPolygonToSplit

mov ecx,.BSPFaceRef.pFace

mov esi, .HSMFace3.pvert0

fld .Vec3.X

fadd polysNormal.X

fstp tempVec.X

fld .Vec3.Y

fadd polysNormal.Y

fstp tempVec.Y

fld .Vec3.Z

fadd polysNormal.Z

fstp tempVec.Z

invoke ClassifyPoint, addr tempVec, ppointOnPlane, addr planeNormal

.if eax==1

return Front

.elseif eax==-1

return Back

.endif

;----------------------------------------------------------------------------------------------------

.elseif eax==1 ;ONE VERTEX ON PLANE

;----------------------------------------------------------------------------------------------------

;HANDLE ABUTTING CASES OF A SINGLE VERTEX ON PLANE

;----------------------------------------------------------------------------------------------------

.if numVerts==3

.if sideA==0

.if (sideB>0 && sideC>0)

return Front

.elseif (SideB<0 && sideC<0)

return Back

.endif

.elseif sideB==0

.if (sideA>0 && sideC>0)

return Front

.elseif (SideB<0 && sideC<0)

return Back

.endif

.elseif sideC==0

.if (sideA>0 && sideB>0)

return Front

.elseif (sideA<0 && sideB<0)

return Back

.endif

.endif

.elseif numVerts==4

.if sideA==0

.if (sideB>0 && sideC>0 && sideD>0)

return Front

.elseif (SideB<0 && sideC<0 && sideD<0)

return Back

.endif

.elseif sideB==0

.if (sideA>0 && sideC>0 && sideD>0)

return Front

.elseif (SideA<0 && sideC<0 && sideD<0)

return Back

.endif

.elseif sideC==0

.if (sideA>0 && sideB>0 && sideD>0)

return Front

.elseif (SideA<0 && sideB<0 && sideD<0)

return Back

.endif

.elseif sideD==0

.if (sideA>0 && sideB>0 && sideC>0)

return Front

.elseif (SideA<0 && sideB<0 && sideC<0)

return Back

.endif

.endif

.endif

;----------------------------------------------------------------------------------------------------

.elseif eax==2 ;ONE VERTEX ON PLANE

;----------------------------------------------------------------------------------------------------

;HANDLE ABUTTING CASES OF AN EDGE ON PLANE

;----------------------------------------------------------------------------------------------------

.if numVerts==3

.if (sideA==0 && sideB==0)

.if sideC>0

return Front

.elseif sideC<0

return Back

.endif

.elseif (sideA==0 && sideC==0)

.if sideB>0

return Front

.elseif sideB<0

return Back

.endif

.elseif (sideB==0 && sideC==0)

.if sideA>0

return Front

.elseif sideA<0

return Back

.endif

.endif

.elseif numVerts==4

.if (sideA==0 && sideB==0)

.if (sideC>0 && sideD>0)

return Front

.elseif (sideC<0 && sideD<0)

return Back

.endif

.elseif (sideB==0 && sideC==0)

.if (sideA>0 && sideD>0)

return Front

.elseif (sideA<0 && sideD<0)

return Back

.endif

.elseif (sideC==0 && sideD==0)

.if (sideA>0 && sideB>0)

return Front

.elseif (sideA<0 && sideB<0)

return Back

.endif

.elseif (sideA==0 && sideD==0)

.if (sideB>0 && sideC>0)

return Front

.elseif (sideB<0 && sideC<0)

return Back

.endif

.endif

.endif

.endif

;==========================================================

;We have now handled all the following cases:

;-coplanar faces

;-faces with a single abutting vertex

;-faces with an abutting edge

;

;If we get this far, then our polygon MUST be cut by the plane.

;More importantly, we can say that the plane must cut TWO EDGES

;of our polygon, and therefore, and one (or two) edges are "safe".

;eg crap ascii art

;

; /\ ;<-- pA is all alone

; / \ ;<--- output tri

;__/___\____ ;<-- intersection points on edge 0 and 2

; / \ ;<-- output quad

;/_______\ ;<-- "safe" edge = 1

;What we do next will depend very much on whether we are merely

;evaluating the polygon for potential splitting, or actually splitting it.

;The order of vertices in newly-formed output polygons is crucial.

;These polygons will be constructed based on which two edges were cut.

;==========================================================