# Assorted 3D Graphics Questions

This topic is 3382 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi everyone, I have quite a few questions to ask today 1) In my textbooks, the intersection time for a ray running thru a plane is given by t = d-P0.n/d.n I am just interested in whether the 2 unit vectors are in opposite direction or with a small angle (d.n) I'd like to know if a mesh like a box, I iterate the faces of it, can I assume the normal of the face which is facing down to be pointing towards the ground while I've got an up vector facing up? what is the final value of the dot product between 2 opposite normals? 0 or 1? 2) I'd like to know how to calculate the value of the first scalar d... Do I assume it to be 1 unit? because it is a unit vector. 3) If I want to calculate the closest distance from this point to the ground, (my textbook gives a = q.n - d) once again, I am not sure how to work out the value of scalar d.. Isn't that true a equals d? Thanks I find it hard to explain So bear with me and my English.... Jack

##### Share on other sites
I have a hard time understanding what you are asking, but the problem is not your English. The problem is that you haven't defined the notation you are using. I don't know which of those symbols are scalars and which are vectors, or what they mean, or whether you are using the .' to mean "dot product" or to mean "member of an object" (in the case of "d.n", neither interpretation makes sense).

##### Share on other sites
Assuming A and B are normalized. A dot B is 1 if they are the same, -1 if they are opposite, and 0 if they are perpendicular. In fact ACOS ( A dot B ) gives you the angle between them.

Other than that, sorry but I'm lost as to the rest of the post.

##### Share on other sites
Sorry, I thought I was losing patience when I was doing the typing... today is very hot indeed.

I try to explain what I am intending to do.
I am actually building a navmesh generator, or maybe just call it navgrid generator. Initially, I've planned myself to use triangular objects for the "map". And I changed my mind to using a plane, tessellated down to 1 point granularity, and to let my "AStar" run on it.

My scene constitutes of geometries and a mesh called "Ground"
With enumeration with each vertex on the grid, I shoot a ray upwards with a certain magnitude to see that if it hits something, then I mark that spot as blocked. Not very elegant but I thought it would do the job just fine because my world is small compared to other large commercial games.

So I have an origin the ray is shooting from, a direction which is the up vector
t = d-p0.n/d.n is the formula I obtained from a book called 3D Math Primer by
Fletcher Dunn and Ian Parberry.
You can consider p0 as the origin of the ray, d (vector) be the direction, n be the vector pointing down from one of the geometries, the first d is a scalar which I don't know how to get it. Nevertheless, the book tells me that the denominator d.n can directly inform me that there is intersection between the ray and the object. So for this part, I am just interested in d.n
I know now if 2 vectors are pointing in the opposite direction,
the dotproduct is 1, and that's fine, you may just forget it :)
On the other hand, I wanted to test the distance between the geometry and the "ground", so I flipped my pages and finally found this equation on the same book.
a = q.n - d

The derivation is
q => a touching point of the ray to the geometry
a => the distance between the point and the origin
n => the normal of the geometry

p + an = q
(p+an).n = q.n
p.n+(an).n = q.n
d+a = q.n
a = q.n - d

pg 256 of 3D Math Primer
p.n = d is the vectorial representation of the ray

Hope this clarifies a bit!
Thanks
Jack

##### Share on other sites
A correspondence of the dot product is
a . b = |a| * |b| * cos ( <a,b> )
what means that the value of the dot product is proportional to the lengthes of the both vectors and the cosine of the angle between the both vectors. Obviously, when the both vectors are of unit length, the right side is reduced to the cosine, i.e.
( a / |a| ) . ( b / |b| ) = cos ( <a,b> )

However, if the angle between the 2 vectors is 0° (i.e. they are parallel) then the cosine is 1. If the angle is 90° (i.e. they are perpendicular) then the cosine is 0. If the angle is 180° (i.e. they are anti-parallel) then the cosine is -1.

The "Hessain normal form" of a plane is
( p - o ) . n == 0
where p is any arbitrary point on the plane, o is another arbitrary point on the plane called the "origin", and n is the normal vector of the plane. If you've chosen a point as origin, and then choose any point on the plane as p, then p - o will definitely be a difference vector lying parallel to the plane (BTW: One may say "in the plane", but a difference vector doesn't know the concept of points, only directions). Then, since the normal of the plane is defined to be perpendicular to the plane, the difference vector and the normal vector must be perpendicular, and hence their dot product must be 0 (see above). That is the message of the Hessain formula. Okay?

Now, while p is variable, the o and n are not for a given plane. Resolving the paranthesis above formula yields in:
p . n - o . n == 0
Since o and n are not variable, the dot product can be pre-computed, so that
== p . n - d with d := o . n
just for convenience. The scalar d mentioned in the OP is just this convenience parameter.

Now, a ray is given as
r(t) := p0 + t * rd
where p0 denotes an arbitrary point on the ray called its "origin", rd denotes the direction of the track of the ray, and t denotes the "travel distance" on the track. Then any point on the ray is expressed as a distance t apart from the origin of the ray, where the distance is a measure in multiples of the length of rd.

If the ray hits the plane, then
r(t) == p
so that, replacing p in the plane formula, we get
( p0 + t * rd ) . n - d == 0
Solving the paranthesis
p0 . n + t * rd . n - d == 0
and moving the terms independent on t to the right side
t * rd . n == d - p0 . n
and at last isolating t on the left side
t == ( d - p0 . n ) / rd . n
and you got the formula in the OP after again resolving the paranthesis.

Quote:
 Original post by lucky6969bI'd like to know if a mesh like a box, I iterate the faces of it, can I assume the normal of the face which is facing down to be pointing towards the groundwhile I've got an up vector facing up?

If the mesh is made correctly, then the face normals can be expected to point to the outside of the model. (Althought this is not guaranteed.)

EDIT: Err, why the hell have I had to wrote this explanation if you already know this stuff?

##### Share on other sites
Quote:
 Original post by KulSeranAssuming A and B are normalized. A dot B is 1 if they are the same, -1 if they are opposite, and 0 if they are perpendicular. In fact ACOS ( A dot B ) gives you the angle between them.Other than that, sorry but I'm lost as to the rest of the post.

I got positive one for opposite normals
See code below
import java.awt.*;
class Vec3{   float x, y,z;   public Vec3()   {       x = 0.f;       y = 0.f;       z = 0.f;   }   public Vec3(float x, float y, float z)   {      this.x = x;      this.y = y;      this.z = z;   }   float Dot (Vec3 b)   {      return ((this.x*b.x)+(this.y*b.y)+(this.z*b.z));   }   void Normalize()   {      float magSq = x*x+y*y+z*z;      if (magSq > 0.0f)      {         float oneOverMag = 1.0f / (float) Math.sqrt(magSq);         x *= oneOverMag;         y *= oneOverMag;         z *= oneOverMag;      }  }}public class dotproduct{   public dotproduct()   {   }   public static void main (String[] args)   {      Vec3 pt0, pt1, pt2;      pt0 = new Vec3(0.0f, 3.0f, 0.0f);      pt1 = new Vec3(0.0f, -4.0f,0.0f);      pt0.Normalize();      pt1.Normalize();      float dot = pt0.Dot(pt1);  // Sorry correct now      System.out.println(dot);   }}`

Thanks
Jack

##### Share on other sites
Hi,
I think I understand the math part now.
Thanks
Jack

##### Share on other sites
Quote:
 Original post by lucky6969bSo I have an origin the ray is shooting from, a direction which is the up vectort = d-p0.n/d.n is the formula I obtained from a book called 3D Math Primer byFletcher Dunn and Ian Parberry.You can consider p0 as the origin of the ray, d (vector) be the direction, n be the vector pointing down from one of the geometries, the first d is a scalar which I don't know how to get it. Nevertheless, the book tells me that the denominator d.n can directly inform me that there is intersection between the ray and the object. So for this part, I am just interested in d.n

If d.n==0 you will ge a division-by-zero, so you must check for this case. When does it happen? Due to the correspondence formula of the dot-product, it happens if d and n are perpendicular, or in other words, the ray (i.e. d) is parallel to the plane. A parallel ray either hits the plane either never or else ever.

BTW: Please don't use the same variable for different purposes in the same formula.

Quote:
 Original post by lucky6969bI know now if 2 vectors are pointing in the opposite direction,the dotproduct is 1, and that's fine, you may just forget it :)

Nope. For opposite directions, the dot-product is negative, and it gets especially -1 if also e.g. both vectors are of unit length.

##### Share on other sites
Quote:
Original post by haegarr
Quote:
 Original post by lucky6969bSo I have an origin the ray is shooting from, a direction which is the up vectort = d-p0.n/d.n is the formula I obtained from a book called 3D Math Primer byFletcher Dunn and Ian Parberry.You can consider p0 as the origin of the ray, d (vector) be the direction, n be the vector pointing down from one of the geometries, the first d is a scalar which I don't know how to get it. Nevertheless, the book tells me that the denominator d.n can directly inform me that there is intersection between the ray and the object. So for this part, I am just interested in d.n

If d.n==0 you will ge a division-by-zero, so you must check for this case. When does it happen? Due to the correspondence formula of the dot-product, it happens if d and n are perpendicular, or in other words, the ray (i.e. d) is parallel to the plane. A parallel ray either hits the plane either never or else ever.

I think I can avoid the division or not doing the division at all because I don't want to calculate t.
I just want to prove that if the object blocking the ray is in existence or not.
If the geometry never gets hit by the ray, the dot product is what?

Quote:

Quote:
 Original post by lucky6969bI know now if 2 vectors are pointing in the opposite direction,the dotproduct is 1, and that's fine, you may just forget it :)

Nope. For opposite directions, the dot-product is negative, and it gets especially -1 if also e.g. both vectors are of unit length.

Yes, I have made a correction in my previous post too.
Thanks
Jack

##### Share on other sites
Quote:
 Original post by lucky6969bI think I can avoid the division or not doing the division at all because I don't want to calculate t.I just want to prove that if the object blocking the ray is in existence or not.

Have you considered that the ray-plane hit test works with an infinite plane? Any ray that is not parallel to the plane will definitely hit the plane somewhere! So, as long as your actual geometry isn't just an infinite plane, you have to compute the hit point (by using t) and furthur check whether the hit point lies inside the geometry boundaries on the plane (e.g. the 3 sides of a triangle).

##### Share on other sites
Quote:
Original post by haegarr
Quote:
 Original post by lucky6969bI think I can avoid the division or not doing the division at all because I don't want to calculate t.I just want to prove that if the object blocking the ray is in existence or not.

Have you considered that the ray-plane hit test works with an infinite plane? Any ray that is not parallel to the plane will definitely hit the plane somewhere! So, as long as your actual geometry isn't just an infinite plane, you have to compute the hit point (by using t) and furthur check whether the hit point lies inside the geometry boundaries on the plane (e.g. the 3 sides of a triangle).

Hmmmm, my initiative is to iterate each vertex of the plane then for each vertex I iterate all of my geometry in the scene. I think it's good enough :)

For infinite plane, I am not too sure.
I presume the point that intersects with the ray is perpendicular to both the "ground" and the geom. So I can use the distance function to achieve this. That is my thought.

I think there are no infinite planes of the art piece...
Jack

##### Share on other sites
Quote:
 Original post by lucky6969bHmmmm, my initiative is to iterate each vertex of the plane then for each vertex I iterate all of my geometry in the scene. I think it's good enough :)For infinite plane, I am not too sure.I presume the point that intersects with the ray is perpendicular to both the "ground" and the geom. So I can use the distance function to achieve this. That is my thought.

(To be nit-picking: A point cannot be perpendicular to something at all. And the ray will be perpendicular to both only if the tested face is a-priori parallel to the ground face.)

I will mention 3 options that came to my mind:

(1) Is it possible for you to use bounding volumes like spheres, cylinders, or boxes, or a combination of them? I mean, due to the concentration of the ground faces to points you already introduce inaccuracies, so using bounding volumes would not be too bad.

(2) Instead of computing a distance perpendicular to the ground, what about the distances of the object's vertices to the concentrated center after projecting them onto the ground?

(3) And perhaps, what if both (1) and (2) are applied in common?

Quote:
 Original post by lucky6969bI think there are no infinite planes of the art piece...

Presumbly not ;)

##### Share on other sites
Quote:
Original post by haegarr
Quote:
 Original post by lucky6969bHmmmm, my initiative is to iterate each vertex of the plane then for each vertex I iterate all of my geometry in the scene. I think it's good enough :)For infinite plane, I am not too sure.I presume the point that intersects with the ray is perpendicular to both the "ground" and the geom. So I can use the distance function to achieve this. That is my thought.

(To be nit-picking: A point cannot be perpendicular to something at all. And the ray will be perpendicular to both only if the tested face is a-priori parallel to the ground face.)

ha ha, that's why I am still on the primer level!!!

Quote:
 I will mention 3 options that came to my mind:(1) Is it possible for you to use bounding volumes like spheres, cylinders, or boxes, or a combination of them? I mean, due to the concentration of the ground faces to points you already introduce inaccuracies, so using bounding volumes would not be too bad.

We have L-shaped objects around :)

Quote:
 (2) Instead of computing a distance perpendicular to the ground, what about the distances of the object's vertices to the concentrated center after projecting them onto the ground?

The modelling software (m*x) we use doesn't allow us to break the mesh down into a very fine level because it has a threshold (while a plane can). This method is already my(our) last resort. I can't think of any better ways other than those... sad
Thanks
Jack

[Edited by - lucky6969b on September 15, 2008 4:22:39 AM]

##### Share on other sites
Bounding volumes are approximations of a mesh. Both represent the same geometry, but in the first case coarsly. They are called "bounding" because they all-embrace each vertex of the original mesh. On the other hand, they are approximations because their hull contains (in general) more space than the hull of the original mesh.

Typical single bounding volumes are spheres, cylinders, and boxes. Spheres are invariant against rotation and they consits of a single face (if seen as a topological entity), so they are very efficient in computation. Their disadvantage is that world objects are often not spherical, so a bounding sphere may embrace too much space outside the hull of the original mesh. E.g. a rifle is a long thin object not good for approximation by a sphere.

Bounding boxes have 6 faces, and they are not rotation invariant, of course. They come in different flavors. There are boxes where the 6 sides are aligned with some co-ordinate system; these are called "axis aligned bounding boxes" or AABB for short. Boxes with an arbitrary orientation are called "oriented bounding boxes" or OBB for short. These both variants are often better suited than spheres but still relatively efficient in computation, so they are popular in collision detection (what your problem can be seen as a kind of).

Nearly each and every engine and DCC package is using bounding volumes in the one or other flavor. Some file formats also provide them as well, so that you may got them from your DCC package export for free. But even if not, computing them (at least bounding boxes) is relatively easy.

The first sense of bounding volumes is to reduce the computational effort by reducing the geometry to a low level approximation. So you still have to check ray-volume hits, of course. In the case of a sphere this would be done using an implicit algebraic formula
x2 + y2 + z2 == R2
Similar in the case of a cylinder, but the 2 circular caps are also to be considered. In the case of boxes you "fall back" to ray-plane intersections, but the computations are still easier than those for a mesh; how easy depends on the chosen flavor of the box.

EDIT: Your edit made my post obsolete. Nonetheless I let it stay here for clarification.

##### Share on other sites
Oops. my apology.... :)
Jack

##### Share on other sites

This topic is 3382 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.