CODEWITHSUNDEEP
c++edge-detection
BlueSpud
BlueSpud

Reputation: 1623

How can I determine if two 3d edges are identical?

I'm trying to detect the silhouette edge of a 3d object. I know that you must first determine weather a face is looking at a position then find the edges that are shared between front and back facing.

I've been able to figure out front and back facing things but I can't figure out how to find if the edges are being shared without a lot of if statements. My vertex data is stored from x1,z1,y1,x2,z2,y2,x3,z3,y3 for every polygon.

Upvotes: 1

Views: 225

Answers (2)

SigTerm
SigTerm

Reputation: 26409

if 2 line segments are the same line

Two line segments are the same if they use identical point coordinates or identical point indexes. Testing whether they are ON the same line is entirely different problem that you don't need to solve in order to find silhouette.

  1. Use indexed primitives.
  2. Precalculate list of edges and required topology tables in advance, while loading model.
  3. IF you're trying to draw a shadow, use shadowmaps instead - they're much simpler to comprehend.

Indexed primitives mean that
1. you store all points in array (std::vector<vector3> points; or something similar, where vector3 is datatype that store xyz coordinates), and every point is unique.
2. faces and edges refer to to points using integer point indexes.

I.e. 

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

typedef unsigned int Index;

struct Face{
    enum{vertsPerFace=3};
    Index verts[vertsPerFace];
};

struct Edge{
    enum{vertsPerEdge=2};
    Index verts[vertsPerEdge];
};

When you load model, you build list of points and convert all faces into indexed primitives using std::set std::map or similar structures. Once you have indexed primitves, you can build associative tables (using std::map) that would map edge to the list of faces std::multimap<std::pair<Index, Index>, FaceIndex>, map edges to the faces indexes that use those edges std::map<std::pair<VertexIndex, VertexIndex>, FaceIndex> and so on.

Upvotes: 0

Code-Apprentice
Code-Apprentice

Reputation: 83527

If you are asking how to determine if two line segments are on the same line, you can use a little bit of Euclidean geometry. Let's cover a couple of definitions:

A point A is an n-tuple (a1, a2, ..., an) of real numbers. In the 3D case, n=3.

Scalar multiplication of a point A and a real number t is defined as

tA = (t*a1, t*a2, ..., t*an)

With these two ideas, we can represent a line very easily. For two points A and B, the point P which satisfies the equation

P = tA + (1-t)B

is on the line AB where t is a real number.

When 0 <= t <= 1, P lies between A and B with P=A when t=1 and P=B when t=0.

Now to put this into a programming perspective, you can create two classes: Point and Line. Using the equation given above, it is very easy to determine if a Point lies on a given Line. To determine if two line segments are on the same line, simply use the two Point which define one Line and check if they lie on the other Line.

Upvotes: 1

Related Questions