Would the point have to be ON the plane, or just between it and the camera (or hidden behind the plane)?
SPECIAL CASE: If (Px - Qx) is equal to zero, then the line is vertical, and calculating the gradient will result in (Py - Qy)/0. Not good. In this case, simply check what the X value of the point is in relation to the line and that will tell you which side of the line it is on. For horizontal lines (Py - Qy) = 0, there is not such error, and the long method can be used.
face = {}
for i = 0,numberoffaces do
face[i] = {}
endHere's a rough plan for the programming:
1. First I need to develop a method of declaring faces.
2. Next, check each vertex in turn to see if it is fully inside any faces.
3. For each face the vertex is inside, check if it is closer than the vertex, or further away.
If you were to find any two points A(X, Y) and B(X, Y) where the line to check whether a point P is inside the polygon crosses the edges, you would then calculate the equation of the line between those two points in the plane through the line AB.
To do this you would calculate the equation of the line as I explained before, only using the Z values of the points A and B in place of the Y values.
Then, determine as before if the point is above (far side) or below (near side) of the line, and that will tell you if it is in front of or behind that face, regardless of the face's orientation. If the face is parallel to the asteroid plane (Z of A = Z of B), then compare the Z value of the point P with the Z of A.
if math.floor(edgenumber/2) == math.ceil(edgenumber/2) then
-- The vertex is inside the face.
else
-- The vertex is outside the face.
end -- faces
i = numberoffaces
-- bottom face
face[i][0] = firstvert + 0
face[i][1] = firstvert + 1
face[i][2] = firstvert + 2
face[i][4] = firstvert + 3for faceID = 0,numberoffaces do
-- detect numberoffedges
passededges = 0
for edgeID = 0,numberofedges
v1 = edgefrom[edgeID]
v2 = edgeto[edgeID]
slope = (vertex2dX[v2] - vertex2dX[v1]) / (vertex2dY[v2] - vertex2dY[v1])
vertexXintercept = vertex2dY[v1] - (slope * vertex2dX[v1]) + vertex2dY[i]
-- intercept is equal to the X-value where the line crosses the P line
if vertex2dX[v2] <= vertex2dX[v1] then
vertex2dX[v2] = min
vertex2dX[v1] = max
else
vertex2dX[v1] = min
vertex2dX[v2] = max
end
if vertex2dX[i] > vertexXintercept and vertexXintercept > min and vertexXintercept < max then
passededges = passededges + 1
end
end
if math.floor(passededges) == math.ceil(passededges) then
-- the vertex is behind a face
draw = false
end
end-- nearside face
face[i][0] = firstedge + 0
face[i][1] = firstedge + 1
face[i][2] = firstedge + 2
face[i][3] = firstedge + 3
i = i + 1
-- farside face
face[i][0] = firstedge + 4
face[i][1] = firstedge + 5
face[i][2] = firstedge + 6
face[i][3] = firstedge + 7
i = i + 1
-- top face
face[i][0] = firstedge + 0
face[i][1] = firstedge + 4
face[i][2] = firstedge + 8
face[i][3] = firstedge + 9
i = i + 1
-- etc
-- for a plane defined by coordinates (Px1, Py1, Pz1), (Px2, Py2, Pz2), and (Px3, Py3, Pz3)
-- and a line defined by coordinates (Lx1, Ly1, Lz1), (Lx2, Ly2, Lz2)
-- find the X, Y, and Z coordinates at which they intersect
-- first get 2 vectors along the plane
-- ("PV1x" stands for Plane Vector #1, X-coordinate)
PV1x = Px2 - Px1
PV1y = Py2 - Py1
PV1z = Pz2 - Pz1
PV2x = Px3 - Px1
PV2y = Py3 - Py1
PV2z = Pz3 - Pz1
-- now find the cross product
-- PV1 X PV2 = normal vector!
i = (PV1y * PV2z) - (PV1z * PV2y)
j = (PV1z * PV2x) - (PV1x * PV2z)
k = (PV1x * PV2y) - (PV1y * PV2x)
-- define d
planex = i
planey = j
planek = k
d = (i * PV1x) + (j * PV1y) + (k * PV1z)
-- for the line, calculate tx, ty, tz
tx = Lx2 - Lx1
ty = Ly2 - Ly1
tz = Lz2 - Lz1
-- calculate t
t = (i * (tx + PV1x)) + (j * (ty + PV1y)) + (k * (tz + PV1z))
-- calculate intersection coordinates
intersectX = t * tx
intersectY = t * ty
intersectZ = t * tz0 = (i * ((t * tx) + Lx1) - Px1)) + (j * ((t * ty) + Ly1) - Py1)) + (k * ((t * tz) + Lz1) - Pz1))0 = (i * (((t * tx) + Lx1) - Px1)) + (j * (((t * ty) + Ly1) - Py1)) + (k * (((t * tz) + Lz1) - Pz1))
t = ((i * (Px1 - Lx1)) + (j * (Py1 - Ly1)) + (k * (Pz1 - Lz1))) / ((i * (Lx2 - Lx1)) + (j * (Ly2 - Ly1)) + (k * (Lz2 - Lz1)))Where did tx, ty and tz go? ???Code: [Select]t = ((i * (Px1 - Lx1)) + (j * (Py1 - Ly1)) + (k * (Pz1 - Lz1))) / ((i * (Lx2 - Lx1)) + (j * (Ly2 - Ly1)) + (k * (Lz2 - Lz1)))
Perhaps this?
t = ((i * (Px1 - Lx1)) + (j * (Py1 - Ly1)) + (k * (Pz1 - Lz1))) / ((i * tx) + (j * ty) + (k * tz))That's the answer I got using this site (http://www.myalgebra.com/). -- get plane coordinates
Px1 = vertex3dXtransformed[firstvertex]
Py1 = vertex3dYtransformed[firstvertex]
Pz1 = vertex3dZtransformed[firstvertex]
Px2 = vertex3dXtransformed[secondvertex]
Py2 = vertex3dYtransformed[secondvertex]
Pz2 = vertex3dZtransformed[secondvertex]
Px3 = vertex3dXtransformed[thirdvertex]
Py3 = vertex3dYtransformed[thirdvertex]
Pz3 = vertex3dZtransformed[thirdvertex]
-- get line coordinates
Lx1 = GetCameraX()
Ly1 = GetCameraY()
Lz1 = CameraZ
Lx2 = vertex3dXtransformed[vertexID]
Ly2 = vertex3dYtransformed[vertexID]
Lz2 = vertex3dZtransformed[vertexID]
-- get 2 vectors along the plane
-- PV1x stands for Plane Vector #1, X-coordinate
PV1x = Px2 - Px1
PV1y = Py2 - Py1
PV1z = Pz2 - Pz1
PV2x = Px3 - Px1
PV2y = Py3 - Py1
PV2z = Pz3 - Pz1
-- now find the cross product, which is a line perpendicular to the plane
-- PV1 X PV2 = normal vector!
i = (PV1y * PV2z) - (PV1z * PV2y)
j = (PV1z * PV2x) - (PV1x * PV2z)
k = (PV1x * PV2y) - (PV1y * PV2x)
-- for the line, calculate tx, ty, tz
tx = Lx2 - Lx1
ty = Ly2 - Ly1
tz = Lz2 - Lz1
t = ((i * (Lx1 - Px1)) + (j * (Ly1 - Py1)) + (k * (Lz1 - Pz1))) / ((i * (Lx2 - Lx1)) + (j * (Ly2 - Ly1)) + (k * (Lz2 - Lz1)))
intersectX = (t * tx) + Lx1
intersectY = (t * ty) + Ly1
intersectZ = (t * tz) + Lz1
-- calculate distance from intersection
intersectdistance2d = (GetCameraX() - intersectX)^2 + (GetCameraY() - intersectY)^2
intersectdistance3d = math.sqrt((CameraZ - intersectZ)^2 + (intersectdistance2d))
if intersectdistance3d > distance3d then
-- return false if the vertex is in front of the face
return false
else
-- return true if the plane is closer than the vertex
return true
end
t = ((i * (Lx1 - Px1)) + (j * (Ly1 - Py1)) + (k * (Lz1 - Pz1))) / ((i * (Lx2 - Lx1)) + (j * (Ly2 - Ly1)) + (k * (Lz2 - Lz1)))t = ((i * (Px1 - Lx1)) + (j * (Py1 - Ly1)) + (k * (Pz1 - Lz1))) / ((i * (Lx2 - Lx1)) + (j * (Ly2 - Ly1)) + (k * (Lz2 - Lz1)))t = ((i * (Px1 - Lx1)) + (j * (Py1 - Ly1)) + (k * (Pz1 - Lz1))) / ((i * (Lx2 - Lx1)) + (j * (Ly2 - Ly1)) + (k * (Lz2 - Lz1))) for faceID = 0,numberoffaces do
-- detect numberoffedges
numberofedgesinthisface = -1
for i = 0,100 do
if face[faceID][i] ~= nil then
numberofedgesinthisface = numberofedgesinthisface + 1
else
break
end
end
passededges = 0
-- this counter is used to check how many edges are passed through to the left of this point
for faceEdgeNumber = 0,numberofedgesinthisface do
-- for each edge in this face
edgeID = face[faceID][faceEdgeNumber]
-- use the ID of the selected edge
v1 = edgefrom[edgeID]
v2 = edgeto[edgeID]
-- set v1 and v2 equal to the ID's of the vertices that join this edge
partoftheface = false
if v1 ~= vertexID and v2 ~= vertexID then
-- make sure the point passed to us in this function is not the same point mentioned in v1 or v2...
if math.floor((vertex2dX[v2] - vertex2dX[v1])) == 0 or math.ceil((vertex2dX[v2] - vertex2dX[v1])) == 0 then
-- vertical edge detected
if vertex2dY[v2] <= vertex2dY[v1] then
minv = vertex2dY[v2]
maxv = vertex2dY[v1]
else
minv = vertex2dY[v1]
maxv = vertex2dY[v2]
end
if vertex2dX[vertexID] > vertex2dX[v2] and vertex2dY[vertexID] > minv and vertex2dY[vertexID] < maxv then
passededges = passededges + 1
end
elseif (vertex2dY[v2] - vertex2dY[v1]) == 0 then
-- horizontal edge detected. It is therefore parallel to the P line and as such will never intersect.
-- so no chance to add a passed edge here.
else
slope = (vertex2dY[v2] - vertex2dY[v1]) / (vertex2dX[v2] - vertex2dX[v1])
-- first calculate the slope of the line formed by the two coordinates
-- we need to find the X-value where the line drawn between v1 and v2 crosses the axis of vertexID
Yintercept = (-slope * vertex2dX[v1]) + vertex2dY[v1]
-- this is the Y-intercept
vertexXintercept = (vertex2dY[vertexID] - Yintercept) / slope
-- vertexXintercept is equal to the X-value where the line crosses the P line
-- ie vertexXintercept is equal to the value of X when this edge reaches Y = vertex2dY[vertexID]
if vertex2dX[v2] <= vertex2dX[v1] then
minv = vertex2dX[v2]
maxv = vertex2dX[v1]
else
minv = vertex2dX[v1]
maxv = vertex2dX[v2]
end
if vertex2dX[vertexID] > vertexXintercept and vertexXintercept > minv and vertexXintercept < maxv then
passededges = passededges + 1
end
end
else
partoftheface = true
break
end
end
if math.floor(passededges / 2) ~= math.ceil(passededges / 2) and partoftheface == false then
-- the vertex is inside a face
draw = false
end
endMost implementations of the ray casting algorithm consecutively check intersections of a ray with all sides of the polygon in turn. In this case the following problem must be addressed. If the ray passes exactly through a vertex of a polygon, then it will intersect 2 segments at their endpoints. While it is OK for the case of the topmost vertex in the example or the vertex between crossing 4 and 5, the case of the rightmost vertex (in the example) requires that we count one intersection for the algorithm to work correctly. A similar problem arises with horizontal segments that happen to fall on the ray. The issue is solved as follows: If the intersection point is a vertex of a tested polygon side, then the intersection counts only if the second vertex of the side lies below the ray. This is effectively equivalent to considering vertices on the ray as lying slightly above the ray.
PV1x = Px2 - Px1
PV1y = Py2 - Py1
PV1z = Pz2 - Pz1
PV2x = Px3 - Px1
PV2y = Py3 - Py1
PV2z = Pz3 - Pz1
-- now find the cross product, which is a line perpendicular to the plane
-- PV1 X PV2 = normal vector!
i = (PV1y * PV2z) - (PV1z * PV2y)
j = (PV1z * PV2x) - (PV1x * PV2z)
k = (PV1x * PV2y) - (PV1y * PV2x)V P P P P VV-----P P P P VV-----P P P P VV-----P P-----P P VV-----P P-----P P VV-----P P-----P P-----Vpseudovertex2dX[edgeID][pseudovertexID] = X-coordinate
pseudovertex2dY[edgeID][pseudovertexID] = Y-coordinate
pseudovertexenabled[edgeID][pseudovertexID] = boolean
vertexenabled[vertexID] = booleanfor edgeID = 0,numberofedges do
-- check if any edges are overlapping any other edges
-- if found to overlap another edge, check that this edge is further away at the 2D point of overlap
-- assuming it IS further away, create a pseudo-vertex at the point where the overlap takes place
-- if it's not further away, don't create the pseudo-vertex for this edge (it will be created for the other edge instead when it is checked)
-- check if any edges are intersecting with a plane
-- if intersecting a plane, create a pseudo-vertex at the point of overlap
end
for pseudovertexID = 0,numberofpseudovertices do
-- check if this pseudo-vertex is inside a face
-- if not inside a face, set state to enabled.
-- if it IS inside a face, check if this pseudo-vertex is behind the face. if behind, set state to disabled
-- if in front, set state to enabled
end
for i = 0,numberofedges do
if i == 0 then
-- DrawFrom = EdgeFrom
end
for j = 0,NumberOfPseudoVerticesInThisEdge do
if for edgeID = 0,numberofedges do
-- check if any edges are overlapping any other edges
-- if found to overlap another edge, check that this edge is further away at the 2D point of overlap
-- assuming it IS further away, check that the point of intersection is not behind any other face
-- if it is not behind any other face, create a pseudo-vertex at the point where the overlap takes place
-- if it's not further away, don't create the pseudo-vertex for this edge (it will be created for the other edge instead when it is checked)
-- check if any edges are intersecting with a plane
-- if intersecting a plane, check if the point of intersection is behind any other faces
-- if the point of intersection is NOT behind any other face, create a pseudo-vertex at the point of overlap
end
finisheddrawing = true
for i = 0,numberofedges do
if i == 0 then
-- DrawFromX = EdgeFrom X
-- DrawFromY = EdgeFrom Y
end
if pseudovertex2dX[i][0] ~= nil then
DrawToX = pseudovertex2dX[i][0]
DrawToY = pseudovertex2dY[i][0]
-- Draw line from DrawFrom to DrawTo
finisheddrawing = false
else
DrawToX = EdgeTo X
DrawToY = EdgeTo Y
-- Draw line from DrawFrom to DrawTo
end
if finisheddrawing == false then
for j = 1, numberofpseudovertices do
if math.ceiling(j) ~= math.floor(j) then
DrawFromX = pseudovertex2dX[i][j]
DrawFromY = pseudovertex2dY[i][j]
if pseudovertex2dX[i][j] ~= nil then
DrawToX = pseudovertex2dX[i][j + 1]
DrawToY = pseudovertex2dX[i][j + 1]
else
DrawToX = EdgeToX
DrawToY = EdgeToY
end
end
end
end
end