A question about polygons Devising a computational method for determining if a point lies in a plane convex polygon Problem background Recall our globe cpp ray tracing demo It depicted a scene showing two objects One of the objects was a square tabletop Its edges ran parallel to x and z axes That fact made it easy to determine if the spot where a ray hit the tabletop fell inside or outside of the square s boundary edges We were lucky Alternative geometry What if we wanted to depict our globe as resting on a tabletop that wasn t a nicely aligned square For example could we show a tabletop that was a hexagon The only change is that the edges of this six sided tabletop can t all be lined up with the coordinate system axes We need a new approach to determining if a ray hits a spot that s on our tabletop A simpler problem How can we tell if a point lies in a triangle c q p a Point p lies inside triangle abc b Point q lies outside triangle abc Triangle algorithm Draw vectors from a to b and from a to c We can regard these vectors as the axes for a skewed coordinate system Then every point in the triangle s plane would have a unique pair of coordinates We can compute those coordinates using Cramer s Rule from linear algebra The algorithm idea c ap c1 ab c2 ac a p b c1 det ap ac det ab ac c2 det ab ap det ab ac Cartesian Analogy y axis p c1 c2 x axis x y 1 p lies outside the triangle if c1 0 or c2 0 or c1 c2 1 Determinant function 2x2 typedef float scalar t typedef struct scalar t x y vector t scalar t det vector t a vector t b return a x b y b x a y Constructing a regular hexagon theta 2 PI 6 cos 2 theta sin 2 theta cos 3 theta sin 3 theta cos 4 theta sin 4 theta cos 1 theta sin 1 theta cos 0 theta sin 0 theta cos 5 theta sin 5 theta Subdividing the hexagon A point p lies outside the hexagon unless it lies inside one of these four sub triangles Same approach for n gons Demo program hexagon cpp illustrates the use of our just described algorithm Every convex polygon can be subdivided into triangles so the same ideas can be applied to any regular n sided polygon Exercise modify the demo program so it draws an octagon a pentagon a septagon Extension to a tetrahedron A tetrahedron is a 3D analog of a triangle It has 4 vertices located in space but not all vertices can lie in the same plane Each face of a tetrahedron is a triangle c b o a Cramer s Rule in 3D typedef float scalar t typedef struct scalar t x y z vector t scalar t det vector t a vector t b vector t c scalar t sum 0 0 sum a x b y c z a x b z c y sum a y b z c x a y b x c z sum a z b x c y a z b y c x return sum Is point in tetrahedron Let o a b c be vertices of a tetrahedron Form the three vectors oa ob oc and regard them as the coordinate axes in a skewed 3D coordinate system Then any point p in space has a unique triple of coordinates op c1 oa c2 ob c3 oc These three coordinates can be computed using Cramer s Rule Details of Cramer Rule c1 det op ob oc det oa ob oc c2 det oa op oc det oa ob oc c3 det oa ob op det oa ob oc Point p lies inside the tetrahedron unless c1 0 or c2 0 or c3 0 or c1 c2 c3 1 Convex polyhedron Just as a convex polygon can be divided into subtriangles any convex polyhedron can be divided into several tetrahedrons We can tell if a point lies in the polyhedron by testing to see it lies in one of the solid s tetrahedral parts An example the regular dodecahedron can be raytraced by using these ideas
View Full Document
Unlocking...