# Faces & Edges Question

6 replies to this topic

### #1RobotGizmo

New Member

• Members
• 7 posts

Posted 05 February 2007 - 02:57 AM

Hi,
I am looking through someone else's code and I am having a hard time figuring out a how a certain data structure works. This program loads in an array of faces and edges, and I need to render these faces to the screen. However, the faces array doesn't contain any vertex information. It looks like this:

struct CollisionFace

{

Plane p;                                        // plane equation of face is r.n + k = 0

short edge[3];                                  // edges around face. if edge is +ve then

// this face is face[0] in the edge structure.

// if negative then & 0x7fff to get the edge number,

// and the face is face[1]

};

struct CollisionEdge

{

US face[2];                                     // 2 faces (second face == 0xffff for outside egde)

union {

struct {

float a, b, c;                          // ax + by + c = 0 on edge

};                                          // ax + by + c = +ve for face[0]

float eq[3];

};

};



The data for the first face looks like this:
Plane.Normal = -0.3, 0.7, 0.5
Plane.K = -64.0

Then the 3 Edges for this face looks like this:
Edge[0].a = 0.99
Edge[0].b = -0.18
Edge[0].c = -116.6

Edge[1].a = -0.85
Edge[1].b = -0.52
Edge[1].c = 169.2

Edge[2].a = -0.45
Edge[2].b = 0.89
Edge[2].c = -33.3

I know it may be hard to understand this just by looking at 1 set of values, but I'm stuck on this and I'm hoping there's someone out there who understands this a lot better than I do. I just need to render this face to the screen, but in order to do that I need to get the 3 vertices for it.

Thanks!

### #2Reedbeta

DevMaster Staff

• 5305 posts
• LocationBellevue, WA

Posted 05 February 2007 - 07:27 AM

The edges look like they are defined by three lines (ax + by + c = 0 defines a line) within the given face plane. However, since there's no basis for x and y axes on the face plane, it's probably done by projection along the dominant axis (the axis where the face plane's normal vector has the largest magnitude). So, for instance, if the face plane normal vector was (-3, 0, 1) then x would be dominant axis of the face plane, and the "x" and "y" in the edge line equation really represent either "y" and "z" or "z" and "y" in world coordinates. There's nothing in the data structure that suggests what order the other two axes should go in so you may just have to figure that out by trial and error.

The data structure seems to be set up for collision rather than rendering, since it's easy to determine whether something is colliding with this face by testing its location against the edge lines. Anyway, if you need to render it, you can recover the vertices by solving for the intersection points of the edge lines, then projecting them back onto the face plane (do this in preprocessing since it'll be slow).
reedbeta.com - developer blog, OpenGL demos, and other projects

### #3RobotGizmo

New Member

• Members
• 7 posts

Posted 05 February 2007 - 04:15 PM

Hi,
I have a bit more information now. The a,b,c of an edge are the coefficients of a 2D line equation along the edge. The line is:

a*x + b*y + c = 0


The "normal" of the edge is the vector [a b 0]. (with Z being up in this... not Y).

When you said "you can recover the vertices by solving for the intersection points of the edge lines", basically I just need to find where, for example, edge0 and edge1 intersect, then that becomes the first vertex. Then I move that vertex in the direction of the face's plane. by as many units as the Plane.K? The dominant axis is always the up axis.

I found this doc on finding the intersection point of 2 lines, but it assumes that you have the start point and end point of the 2 lines:
http://www.whisqu.se...docs/math28.htm

Is there a way to calculate the intersection point by just having ABC, not the end points? I'm sorry if these questions are a bit newbie-ish, but I'm not familiar enough with this yet.

Thanks!

### #4Nils Pipenbrinck

Senior Member

• Members
• 597 posts

Posted 05 February 2007 - 04:20 PM

RobotGizmo said:


a*x + b*y + c = 0



Is there a way to calculate the intersection point by just having ABC, not the end points? I'm sorry if these questions are a bit newbie-ish, but I'm not familiar enough with this yet.

Thanks!


a*x + b*y  = - c  // equation 1

d*x + e*y  = - f   // equation 2



That's two equations with two unknowns in a very simple form. Basic school math. I'm sure you can solve that on your own.

### #5RobotGizmo

New Member

• Members
• 7 posts

Posted 05 February 2007 - 05:16 PM

Hi Nils,
Thanks for the info. I can easily solve those 2 formulas, but I just have 1 last question. I don't know either the X or Y values, so can I just fill in whatever I want (like a 0) for both X's, then get the resulting Y's? Is that valid? If I use this formula a*x + b*y = - c for the 3 edges, that will give me the 3 vertices, then just transform them using the plane's normals? Sounds pretty straight-forward... but I just want to make sure before I jump in and do it all wrong.

Thanks

### #6Reedbeta

DevMaster Staff

• 5305 posts
• LocationBellevue, WA

Posted 05 February 2007 - 06:03 PM

RobotGizmo said:

I don't know either the X or Y values, so can I just fill in whatever I want (like a 0) for both X's, then get the resulting Y's? Is that valid?

No. You need to solve both equations simultaneously. There is generally only going to be one (x,y) point that satisfies them both. You can find this by doing Gaussian elimination.

Once you have the vertex locations in 2D, you need to move them onto the face plane. That means, if I assume the dominant axis is z, solving the plane equation for z and then plugging in the (x, y) values of the vertex locations to find the proper z coordinates. For instance, if the plane equation is 2x + 3y - z = 5 then you would get z = 2x + 3y - 5, and plug the (x, y) vertex locations into that. If your dominant axis is always z then this should be all you need to do, but as I mentioned, if you have other dominant axes in your data, you'll probably need to do some trial and error to work out the correct assignment of coordinates.
reedbeta.com - developer blog, OpenGL demos, and other projects

### #7RobotGizmo

New Member

• Members
• 7 posts

Posted 05 February 2007 - 07:06 PM

Thanks, Reedbeta. The 2 verts I am going to get from this line equation are going to be X and Z. The plane equation should be giving me the Y (the height in this case), as far as I can tell from the docs. It sounds like I'm going to have to do some reading on Gaussian elimination. I've never done anything with line intersection before, so it's all new to me. I can't imagine how to find out X and Y to satisfy both equations, without lots and lots of guessing/brute force. So it looks like I'm going to be googling/reading my heart out tonight.

Thanks for all the help!

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users