PDA

View Full Version : Octree partitioning heuristic for line segments



pleopard
01-24-2002, 08:51 AM
I am having diffulty designing the logic for partitioning an octree for viewing frustum culling and could use some brainstorming ideas ...

A little background on my project ...

I have several massive databases of terrain contour data. The databases represent elevation data using 2 paradigms: spot elevations, and line segments. The quantity of spot elevations can reach into the hundreds of thousands and the quantity of line segments can reach into the millions.

I defined a set of classes to define the geometry like in the following pseudocode:




// ----------------------------------------------------------------------------
// Define a vector/vertex

struct MgVector3D
{
float x,y,z;
};

// ----------------------------------------------------------------------------
// Define a simple bounding box

class MgBoundingBox
{
MgVector3D minCoord;
MgVector3D maxCoord;
};

// ----------------------------------------------------------------------------
// Define a list (a simple array) of vertices
// This is just an encapsulation of MgVector3D* pArray

class VertexList : public TMgArray<MgVector3D>
{
public:
const MgBoundingBox&amp; boundingBox() const;
...
}

// ----------------------------------------------------------------------------
// Define a simple spot elevation (actually the indices of the spot's
// vertex in a master vertex list

typedef size_t SpotElevation;

// ----------------------------------------------------------------------------
// Define a list (a simple array) of spot elevations
// This is just an encapsulation of SpotElevation* pArray

class SpotElevationList : public TMgArray<SpotElevation>
{
...
};

// ----------------------------------------------------------------------------
// Define a simple line segment

struct LineSegment
{
/// Index of starting vertex in the external vertex array.
unsigned int startIndex;
/// Index of ending vertex in the external vertex array.
unsigned int endIndex;
/// Precomputed length of line
T length;
/// Construct given the indices and line length
LineSegment(unsigned int s=0, unsigned int e=0, T len=0)
: startIndex(s), endIndex(e), length(len)
{
}
};

// ----------------------------------------------------------------------------
// Define a list (a simple array) of line segments
// This is just an encapsulation of LineSegment* pArray

class LineSegmentList : public TMgArray<LineSegment>
{
public:
const MgBoundingBox&amp; boundingBox() const;
...
};

// ----------------------------------------------------------------------------
// Define the contour model that holds everything

class ContourModel
{
const MgBoundingBox&amp; boundingBox() const { return m_Vertices.boundingBox(); }
private:
/// Master pool of vertices.
VertexList m_Vertices;
/// Collection of line segments.
LineSegmentList m_LineSegments;
/// Collection of spot elevations.
SpotElevationList m_SpotElevations;
...
};


I am experimenting with an Octree for partitioning the geometry and have run across a problem that I do not quite understand how to solve ...

When building the Octree, I can easily place the spot elevations based on their position in space. However, deciding which octants to include the line segments in is a lot more difficult. The lines range in length from 0.1 meters to 980 meters (databases range up to 6000x4000 meters).

I thought about doing a line/box intersection test with the line segments and each octant but the lines could easily span many neighboring octants.

I thought about computing the midpoint of each line segment and using that as the basis for assigning them to octants however, the longer segments would frequently be culled even when they should be displayed.

I am new to Octrees and could use any help ... Any ideas?



[This message has been edited by pleopard (edited 01-24-2002).]

j
01-24-2002, 05:57 PM
Maybe group lines into groups of 1000 or so, and then place a reference to the group in every octree node that they are a part of. Then have a flag associated with each group that gets set as soon as the group is rendered, so that you can skip over the group when you encounter it in any other octree nodes.

j