I’ve spend a lot of time over the past couple of years working on a multiplayer strategy game called Deep Rift 9. You can read more about the game here:
The game is being developed by Norsedale ApS, and the initial code-base was lifted from my failed Hexadome 2 project, but has since evolved quite a bit in every direction. More importantly, DR9 has a depth and a visual appearance far beyond what I could have hoped to cook up myself, so it’s all for the better.
In any case, since we’re now entering into the treacherous minefield of public (alpha) testing 🙂 I figured it would be a good time to release some of my development notes on the project – these posts will also be available on the DR9 web site.
Starting kind-of backwards, here’s the first one on how we calculate and render the dynamic borders between players land areas.
Voronoi Diagrams
I don’t remember when I first heard or read about Voronoi Diagrams, but I do remember these guys: http://www.big-robot.com giving a rather funny presentation of how they used Voronoi diagrams to procedurally generate maps in “Sir, you are being hunted” back at Unite Nordic 2013 (jeez, time flies).
Actually, the talk is on YouTube if you’re interested , I’m in the front row, purple shirt, bald spot 🙂
There’s a good page on WikiPedia if you want the details:
The TL;DR version: A Voronoi diagram divides an set of seed-points into convex shapes. There is one seed point in each shape and each shape contains all other points that are closer to that specific seed than they are to any other seed point. The edges of the shape naturally becomes the borders to the surrounding shapes.
Sounds perfect.
Implementation
Luckily for me, I did not have to take this all the way from mathematical concept to working algorithm since several talented people have already laid the foundation and generously shared their implementations. Unfortunately, none of them decided to do it in C# which is what I needed, so I did have to port the code.
The implementation I ended up using is a C++ derivation of Steven Fortune’s original C implementation from AT&T, made by Shane O’sullivan:
Shane O’Sullivans C++ Voronoi implementation
The original source is available from Stevens web page, here:
Steven Fortune’s original C implementation
My C# adaption is below if anyone feels like saving a few hours of tedious pointer-to-reference conversion ;).
Performance
Even though performance is not critical to DR9 – the points that serve as Voronoi “seeds” in DR9 are the cities and they don’t move, nor are they created or destroyed at a very high frequency so the Voronoi generator does not need to run at anywhere near full frame-rate speed – I still decided to do some quick performance tests.
I got rid of a bunch of C and C++ legacy annoyances like additional counters and funky size conversions that are not needed in C# and got a small ~20% performance bump for my efforts (probably not because there was anything wrong with the original code, but more likely because I had earned a penalty when porting, trying to be strict rather than fast).
With this out of the way, and not feeling too eager to mess with the core algorithm, I zoned in on the use of hash tables. Even though hash tables are generally good for performance – at least at scale, something about this particular use-case just didn’t taste right.
Going on nothing but a hunch, I did not really expect to find any gains, so as a quick test, I just dumbed the hash tables down to a size of one, effectively turning them into complicated arrays. Somewhat to my surprise performance increased by another 15%. I initially assumed that my dataset was simply too small for the hashtables to be useful, and I was just suffering the overhead without the benefit, so I bumped my seed count from 128 to 2048.
This had the completely unexpected effect of being 25% faster than the hashed version. Not only was hashing slower, it also scaled worse:
I’m not sure why this is and I have not had time to dig deeper, but there’s a number of things that could be worth investigating:
- The nature of the algorithm may not need real random access, or my data set may have been skewed in such a way that it didn’t – If the searches mostly find candidates in close proximity to where it is, a hashtable has very little use. I did try to shuffle the data but that only pushed the results further in the direction of the non-hashed version, if only marginally so.
- The hash table implementation may have been broken, or using an inappropriate hashing function. I looked at this briefly and it seemed reasonable, using spatial position for hashing which matches the even distribution of my seeds nicely. I didn’t do any profiling of the actual buckets to see if the fill was uneven, but I doubt it.
- The hash table may break optimization done by either the C# compiler or run-time or by the CPU (this could be anything from overflowing the pipeline or missing the cache to fouling up the CPUs branch prediction). Generally, less code, fewer branches, fewer method calls and less messing with shared variables results in better run-time optimization, even if your loops gets a bit longer. Long lesson learned by years of Java programming – you can really mess the hotspot compiler up if you try to be clever on its behalf.
Personally, I have my money on #3 🙂
In any case, once I had the Voronoi structure, connecting neighbouring shapes with the same owner was trivial, and so was traversing the surrounding edges to create a mesh for the border.
The following screenshot shows borders in red, and lines connecting neighbours in gray. Seeds are considered to have the same owner if they have the same color.
What did turn out to be something of a hassle, was rendering it.
Ideally I just wanted it painted as a flat configurable-width line on top of the map, but the map is not flat and it is not “a” map, but rather a bunch of map-patches that are dynamically created and destroyed as the view changes. Because the shape of the Voronoi cells are highly dependent on neighbouring patches (in fact that’s all it depends on) it was not practical to create Voronoi meshes for each patch – it had to be created independently of the patches.
Creating a mesh that followed the terrain was not trivial for two reasons. The first is that the actual map patches are not a true representation of the procedural height map. The patches are sub-divided and smoothened to create a nicer terrain and also contain objects such as trees and mountains and thus the height at any given location was not readily available. The second problem is that the Voronoi diagram extends towards infinity (or 32000 as infinity is defined in DR9 🙂 ) and creating a mesh with that many vertices would never work.
I had to find a way to draw the lines on the map, preferably by storing only the end-points of each border.
My first attempt involved a rather exotic use of the depth buffer and a custom shader. I build a mesh of vertical planes and rendered their intersection with the map patches by measuring the distance in the depth buffer. It worked ok from certain angles, but not at all for borders that were perfectly vertical compared to the camera (which turned out to be a fairly common case).
Fiddling with the shader, I was able to make it less horrible, but never really good (notice how lines get thinner as they become vertical):
My second attempt was to create extruded upside-down U shapes instead of vertical planes. I used the actual procedural height data plus some small distance as the height of the inverted U, but limited to 10 points per edge. This meant that most “real” borders would get subdivided into small enough pieces that they kind of followed the terrain, while the outer ones that extended toward “infinity” would not generate ridiculous amounts of vertices.
The problem with this approach was that the border would sometimes extend high above the terrain, and other times penetrate through it, disappearing all together.
The final fix turned out to be as simple as it comes: I modified the shader to ignore Z-test and reduced the geometry to be only the flat upper face of the inverted U. Because the line kind of follows the terrain, it never gets wildly out of place, and even when it does deviate, nobody can tell because there is no telling where it *should* have been.
This would not have worked if the user was able to tilt or rotate the camera as it would have broken the illusion, but as it happens, they can’t 🙂
My C# port is below. The way this works is that you create an instance of VoronoidGenerator supplying any class that you want to associate with the seeds – it does not matter what it is, only that you can somehow convert it into a 2D location.
You then call AddSeed with each of the seeds you want included and finally Generate to build the actual Graph. Generate takes a locationResolver as its last parameter – this is a function that given a seed of your declared type must return a 2D position.
When Generate completes, you can get the first edge in the graph with GetFirstEdge and then loop the graph by following edges (edge.next). Each graph edge contains the border end points as well as a reference to the seeds on either side of the border.
/*
* The author of this software is Steven Fortune. Copyright (c) 1994 by AT&T
* Bell Laboratories.
* Permission to use, copy, modify, and distribute this software for any
* purpose without fee is hereby granted, provided that this entire notice
* is included in all copies of any software which is or includes a copy
* or modification of this software and in all copies of the supporting
* documentation for such software.
* THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
* WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
* REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
* OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
*/
/*
* This code was originally written by Stephan Fortune in C code. I, Shane O'Sullivan,
* have since modified it, encapsulating it in a C++ class and, fixing memory leaks and
* adding accessors to the Voronoi Edges.
* Permission to use, copy, modify, and distribute this software for any
* purpose without fee is hereby granted, provided that this entire notice
* is included in all copies of any software which is or includes a copy
* or modification of this software and in all copies of the supporting
* documentation for such software.
* THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
* WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
* REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
* OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
*/
/**
* C# adaption for use with Unity by Niels Jørgensen, BoaNeo AB (http://www.boaneo.com)
*
* Permission to use, copy, modify, and distribute this software for any
* purpose without fee is hereby granted, provided that this entire notice
* is included in all copies of any software which is or includes a copy
* or modification of this software and in all copies of the supporting
* documentation for such software.
* THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
* WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
* REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
* OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
*/
using System;
using System.Collections.Generic;
using UnityEngine;
namespace BoaNeoTools.Source.MathNoHash
{
class Pool where T : new()
{
private List _memory = new List();
private int _free;
public int length { get { return _free; } }
public void Reset()
{
_free = 0;
}
public T Allocate()
{
if (_free >= _memory.Count)
_memory.Add(new T());
T obj = _memory[_free++];
return obj;
}
public void Claim(T curr)
{
int idx = _memory.IndexOf(curr);
if (idx >= 0 && idx < _free)
{
_memory.RemoveAt(idx);
_free--;
_memory.Add(curr);
}
}
}
class Point
{
public float x;
public float y;
}
class Seed : Point
{
public object source;
public int seednbr;
public int refcnt;
public Seed() { }
public Seed(object seedSource)
{
source = seedSource;
}
}
class Edge
{
public float a;
public float b;
public float c;
public Seed[] ep = new Seed[2];
public Seed[] reg = new Seed[2];
public int edgenbr;
}
public class GraphEdge
{
public float x1;
public float y1;
public float x2;
public float y2;
public T s1;
public T s2;
public GraphEdge next;
}
class Halfedge
{
public Halfedge ELleft;
public Halfedge ELright;
public Edge ELedge;
public int ELrefcnt;
public int ELpm;
public Seed vertex;
public float ystar;
public Halfedge PQnext;
}
public class VoronoiGenerator
{
Edge DELETED = new Edge(); // Used for ugly comparison
const int le = 0;
const int re = 1;
private List _userSeeds = new List();
private int _seedIdx;
private GraphEdge _allEdges;
private Pool _pointPool = new Pool();
private Pool _graphEdgePool = new Pool();
private Pool _halfedgePool = new Pool();
private Pool _internalSeedPool = new Pool();
private Pool _edgePool = new Pool();
Halfedge ELleftend;
Halfedge ELrightend;
float xmin, xmax, ymin, ymax;
int nvertices;
Halfedge PQhash;
int PQcount;
float _perimeterXmin, _perimeterXmax, _perimeterYmin, _perimeterYmax;
float _minDistanceBetweenSeeds;
public GraphEdge GetFirstEdge()
{
return _allEdges;
}
public void AddSeed( T seedSource )
{
_userSeeds.Add( new Seed(seedSource) );
}
public void RemoveSeed( T seedSource )
{
for (int i = 0; i < _userSeeds.Count; i++)
{
if (_userSeeds[i].source == (object)seedSource)
{
_userSeeds.RemoveAt(i);
return;
}
}
}
public void Generate(float minX, float maxX, float minY, float maxY, float minDist, Func locationResolver)
{
if (_userSeeds.Count == 0)
return;
CleanupEdges();
int i;
_minDistanceBetweenSeeds = minDist;
_graphEdgePool.Reset();
_internalSeedPool.Reset();
_pointPool.Reset();
xmin = float.MaxValue;
ymin = float.MaxValue;
xmax = float.MinValue;
ymax = float.MinValue;
for (i = 0; i < _userSeeds.Count; i++) { Vector2 p0 = locationResolver((T)_userSeeds[i].source); _userSeeds[i].x = p0.x; _userSeeds[i].y = p0.y; _userSeeds[i].seednbr = i; _userSeeds[i].refcnt = 0; if (p0.x xmax) xmax = p0.x; if (p0.y ymax) ymax = p0.y; } _userSeeds.Sort((s1, s2) =>
{
if (s1.y s2.y) return 1;
if (s1.x s2.x) return 1;
return 0;
});
_seedIdx = 0;
_edgePool.Reset();
nvertices = 0;
float temp;
if (minX > maxX)
{
temp = minX;
minX = maxX;
maxX = temp;
}
if (minY > maxY)
{
temp = minY;
minY = maxY;
maxY = temp;
}
_perimeterXmin = minX;
_perimeterYmin = minY;
_perimeterXmax = maxX;
_perimeterYmax = maxY;
_seedIdx = 0;
Voronoi();
}
private void ELinitialize()
{
_halfedgePool.Reset();
ELleftend = HEcreate(null, 0);
ELrightend = HEcreate(null, 0);
ELleftend.ELleft = null;
ELleftend.ELright = ELrightend;
ELrightend.ELleft = ELleftend;
ELrightend.ELright = null;
}
Halfedge HEcreate(Edge e, int pm)
{
Halfedge answer = _halfedgePool.Allocate();
answer.ELedge = e;
answer.ELpm = pm;
answer.PQnext = null;
answer.vertex = null;
answer.ELrefcnt = 0;
answer.ELleft = null;
answer.ELright = null;
answer.ystar = 0;
return answer;
}
void ELinsert(Halfedge lb, Halfedge newHe)
{
newHe.ELleft = lb;
newHe.ELright = lb.ELright;
lb.ELright.ELleft = newHe;
lb.ELright = newHe;
}
Halfedge ELleftbnd(Point p)
{
// Use hash table to get close to desired halfedge
Halfedge he = ELrightend;
//ntry += 1;
// Now search linear list of halfedges for the correct one
do
{
he = he.ELleft;
} while (he != ELleftend && !RightOf(he, p));
return he;
}
// This delete routine can't reclaim node, since pointers from hash table may be present.
void ELdelete(Halfedge he)
{
he.ELleft.ELright = he.ELright;
he.ELright.ELleft = he.ELleft;
he.ELedge = DELETED;
}
Seed LeftReg(Halfedge he)
{
if (he.ELedge == null)
return _userSeeds[0];
return he.ELpm == le ? he.ELedge.reg[le] : he.ELedge.reg[re];
}
Seed RightReg(Halfedge he)
{
if (he.ELedge == null) //if this halfedge has no edge, return the bottom seed (whatever that is)
return _userSeeds[0];
//if the ELpm field is zero, return the seed 0 that this edge bisects, otherwise return seed number 1
return(he.ELpm == le ? he.ELedge.reg[re] : he.ELedge.reg[le]);
}
Edge Bisect(Seed s1, Seed s2)
{
Edge newedge = _edgePool.Allocate();
newedge.edgenbr = 0;
newedge.a = newedge.b = newedge.c = 0;
newedge.reg[0] = s1; //store the seeds that this edge is bisecting
newedge.reg[1] = s2;
RefBump(s1);
RefBump(s2);
newedge.ep[0] = null; //to begin with, there are no endpoints on the bisector - it goes to infinity
newedge.ep[1] = null;
float dx = s2.x - s1.x; //get the difference in x dist between the seeds
float dy = s2.y - s1.y;
float adx = dx > 0 ? dx : -dx; //make sure that the difference in positive
float ady = dy > 0 ? dy : -dy;
newedge.c = (float) (s1.x * dx + s1.y * dy + (dx * dx + dy * dy) * 0.5); //get the slope of the line
if (adx > ady)
{
newedge.a = 1.0f;
newedge.b = dy / dx;
newedge.c /= dx; //set formula of line, with x fixed to 1
}
else
{
newedge.b = 1.0f;
newedge.a = dx / dy;
newedge.c /= dy; //set formula of line, with y fixed to 1
}
newedge.edgenbr = _edgePool.length - 1;
return newedge;
}
//create a new seed where the HalfEdges el1 and el2 intersect - note that the Point in the argument list is not used, don't know why it's there
Seed Intersect(Halfedge el1, Halfedge el2)
{
Edge e1 = el1.ELedge;
Edge e2 = el2.ELedge;
if (e1 == null || e2 == null)
return null;
//if the two edges bisect the same parent, return null
if (e1.reg[1] == e2.reg[1])
return null;
float d = e1.a * e2.b - e1.b * e2.a;
if (-1.0e-10 < d && d < 1.0e-10)
return null;
float xint = (e1.c * e2.b - e2.c * e1.b) / d;
float yint = (e2.c * e1.a - e1.c * e2.a) / d;
Halfedge el;
Edge e;
if ((e1.reg[1].y < e2.reg[1].y) || (e1.reg[1].y == e2.reg[1].y && e1.reg[1].x = e.reg[1].x; if ((right_of_seed && el.ELpm == le) || (!right_of_seed && el.ELpm == re)) return null; //create a new seed at the point of intersection - this is a new vector event waiting to happen Seed v = _internalSeedPool.Allocate(); v.refcnt = 0; v.seednbr = 0; v.x = xint; v.y = yint; return v; } // returns 1 if p is to right of halfedge e bool RightOf(Halfedge el, Point p) { Edge e = el.ELedge; Seed topSeed = e.reg[1]; bool right_of_seed = p.x > topSeed.x;
if (right_of_seed && el.ELpm == le) return true;
if (!right_of_seed && el.ELpm == re) return false;
bool above;
if (e.a == 1.0)
{
float dyp = p.y - topSeed.y;
float dxp = p.x - topSeed.x;
bool fast = false;
if ((!right_of_seed & (e.b = 0.0)))
{
above = dyp >= e.b * dxp;
fast = above;
}
else
{
above = p.x + p.y * e.b > e.c;
if (e.b < 0.0) above = !above;
if (!above) fast = true;
}
if (!fast)
{
var dxs = topSeed.x - (e.reg[0]).x;
above = e.b * (dxp * dxp - dyp * dyp) < dxs * dyp * (1.0 + 2.0 * dxp / dxs + e.b * e.b); if (e.b t2 * t2 + t3 * t3; } return el.ELpm == le ? above : !above; } void EndPoint(Edge e, int lr, Seed s) { e.ep[lr] = s; RefBump(s); if (e.ep[re - lr] == null) return; ClipLine(e); DeRef(e.reg[le]); DeRef(e.reg[re]); _edgePool.Claim(e); } float Distance(Point s, Point t) { float dx = s.x - t.x; float dy = s.y - t.y; return Mathf.Sqrt(dx * dx + dy * dy); } void MakeVertex(Seed v) { v.seednbr = nvertices; nvertices += 1; } void DeRef(Seed v) { v.refcnt -= 1; if (v.refcnt == 0) _internalSeedPool.Claim(v); } void RefBump(Seed v) { v.refcnt += 1; } //push the HalfEdge into the ordered linked list of vertices void PQinsert(Halfedge he, Seed v, float offset) { he.vertex = v; RefBump(v); he.ystar = v.y + offset; Halfedge last = PQhash; Halfedge next; while ((next = last.PQnext) != null && (he.ystar > next.ystar ||
(he.ystar == next.ystar && v.x > next.vertex.x)))
{
last = next;
}
he.PQnext = last.PQnext;
last.PQnext = he;
PQcount += 1;
}
//remove the HalfEdge from the list of vertices
void PQdelete(Halfedge he)
{
if (he.vertex != null)
{
Halfedge last = PQhash;
while (last.PQnext != he)
last = last.PQnext;
last.PQnext = he.PQnext;
PQcount -= 1;
DeRef(he.vertex);
he.vertex = null;
}
}
bool PQempty()
{
return PQcount == 0;
}
Point PQ_min()
{
Point answer = _pointPool.Allocate();
answer.x = PQhash.PQnext.vertex.x;
answer.y = PQhash.PQnext.ystar;
return answer;
}
Halfedge PQextractmin()
{
Halfedge curr = PQhash.PQnext;
PQhash.PQnext = curr.PQnext;
PQcount -= 1;
return curr;
}
void PQinitialize()
{
PQcount = 0;
if (PQhash == null)
{
PQhash = new Halfedge();
}
}
void CleanupEdges()
{
_allEdges = null;
}
void PushGraphEdge(Seed s1, Seed s2, float x1, float y1, float x2, float y2)
{
GraphEdge newEdge = _graphEdgePool.Allocate(); // new GraphEdge();
newEdge.next = _allEdges;
_allEdges = newEdge;
newEdge.s1 = (T)s1.source;
newEdge.s2 = (T)s2.source;
newEdge.x1 = x1;
newEdge.y1 = y1;
newEdge.x2 = x2;
newEdge.y2 = y2;
}
void out_triple(Seed s1, Seed s2, Seed s3)
{
// Debug.Log("OutTriple ()");
}
void ClipLine(Edge e)
{
if (e.reg[0] == null)
return;
float x1 = e.reg[0].x;
float x2 = e.reg[1].x;
float y1 = e.reg[0].y;
float y2 = e.reg[1].y;
//if the distance between the two points this line was created from is less than the square root of 2, then ignore it
if (Mathf.Sqrt(((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1))) = 0.0)
{
s1 = e.ep[1];
s2 = e.ep[0];
}
else
{
s1 = e.ep[0];
s2 = e.ep[1];
}
if (e.a == 1.0)
{
y1 = _perimeterYmin;
if (s1 != null && s1.y > _perimeterYmin)
{
y1 = s1.y;
}
if (y1 > _perimeterYmax)
{
y1 = _perimeterYmax;
}
x1 = e.c - e.b * y1;
y2 = _perimeterYmax;
if (s2 != null && s2.y < _perimeterYmax) y2 = s2.y; if (y2 _perimeterXmax) & (x2 > _perimeterXmax)) | ((x1 < _perimeterXmin) & (x2 _perimeterXmax) { x1 = _perimeterXmax; y1 = (e.c - x1) / e.b; } ; if (x1 _perimeterXmax) { x2 = _perimeterXmax; y2 = (e.c - x2) / e.b; } ; if (x2 _perimeterXmin) x1 = s1.x; if (x1 > _perimeterXmax)
{
x1 = _perimeterXmax;
}
y1 = e.c - e.a * x1;
x2 = _perimeterXmax;
if (s2 != null && s2.x < _perimeterXmax) x2 = s2.x; if (x2 _perimeterYmax) & (y2 > _perimeterYmax)) | ((y1 < _perimeterYmin) & (y2 _perimeterYmax)
{
y1 = _perimeterYmax;
x1 = (e.c - y1) / e.a;
}
;
if (y1 _perimeterYmax)
{
y2 = _perimeterYmax;
x2 = (e.c - y2) / e.a;
}
;
if (y2 < _perimeterYmin)
{
y2 = _perimeterYmin;
x2 = (e.c - y2) / e.a;
}
}
PushGraphEdge(e.reg[0],e.reg[1], x1, y1, x2, y2);
}
private void Voronoi()
{
PQinitialize( );
ELinitialize( );
NextSeed();
Seed new_seed = NextSeed();
Point newintstar = null;
while (true)
{
if (!PQempty())
newintstar = PQ_min();
//if the lowest seed has a smaller y value than the lowest vector intersection, process the seed otherwise process the vector intersection
if (new_seed != null && (PQempty() || new_seed.y < newintstar.y || (new_seed.y == newintstar.y && new_seed.x top.y) //if the seed to the left of the event is higher than the seed
{
//to the right of it, then swap them and set the 'pm' variable to 1
var temp = bot;
bot = top;
top = temp;
pm = re;
}
Edge e = Bisect(bot, top); //create an Edge (or line) that is between the two seeds. This creates
//the formula of the line, and assigns a line number to it
Halfedge bisector = HEcreate(e, pm); //create a HE from the Edge 'e', and make it point to that edge with its ELedge field
ELinsert(llbnd, bisector); //insert the new bisector to the right of the left HE
EndPoint(e, re - pm, v); //set one endpoint to the new edge to be the vector point 'v'.
//If the seed to the left of this bisector is higher than the right
//seed, then this endpoint is put in position 0; otherwise in pos 1
DeRef(v); //delete the vector 'v'
//if left HE and the new bisector don't intersect, then delete the left HE, and reinsert it
Seed p;
if ((p = Intersect(llbnd, bisector)) != null)
{
PQdelete(llbnd);
PQinsert(llbnd, p, Distance(p, bot));
}
//if right HE and the new bisector don't intersect, then reinsert it
if ((p = Intersect(bisector, rrbnd)) != null)
{
PQinsert(bisector, p, Distance(p, bot));
}
}
else break;
}
for (Halfedge lbnd = ELleftend.ELright; lbnd != ELrightend; lbnd = lbnd.ELright)
{
ClipLine(lbnd.ELedge);
}
}
// return a single in-storage seed
Seed NextSeed()
{
Seed s = null;
if (_seedIdx < _userSeeds.Count)
{
s = _userSeeds[_seedIdx];
_seedIdx += 1;
}
return s;
}
}
}
boaneo.wordpress.com 