Posts

• zilo Registered User

  July 2010 edited July 2010

  You could simplify things a bit by transforming your vertices by the inverse of your camera transform (puts your camera at the origin and looking down the Z axis, positive or negative depends on if you're using left or right-handed orientation). It looks like you're doing all of your math in world coordinates which can get pretty hairy.

  0 · Agree Awesome
• ArdentMarauder Registered User

  July 2010 edited July 2010

  That's a great idea! Thanks! The inverse of the camera would only have to be done once per frame, so that's not bad at all. Let me see if I can whip that up quick...

  0 · Agree Awesome
• zilo Registered User

  July 2010 edited July 2010

  That's how both OpenGL and DirectX work, though one looks down +Z and one looks down -Z (I forget which is which). It forces you to generate a true transformation matrix for your camera too, instead of using yaw and pitch angles, which can be handy in other ways.

  0 · Agree Awesome
• ArdentMarauder Registered User

  July 2010 edited July 2010

  zilo wrote: »

  That's how both OpenGL and DirectX work, though one looks down +Z and one looks down -Z (I forget which is which). It forces you to generate a true transformation matrix for your camera too, instead of using yaw and pitch angles, which can be handy in other ways.

  
  How is this different than a perspective transformation? The perspective handles the big/small issue... and that's about all I need. Albeit, my case is insanely simple relative to a real graphics engine (no shading, shadows, texture mapping, HLSL, etc)

  0 · Agree Awesome
• zilo Registered User

  July 2010 edited July 2010

  Perspective transformations deal with things like field of view, near and far plane, etc- converting things from their positions inside the view frustum to 2D screen space. Camera transformations are simply where your camera is and which direction it's pointed.
  
  edit: That wikipedia article is kinda weird. As a first attempt I'd ditch that chunk of math and make your "perspective transformation" just chopping off the Z coordinate.
  
  One other benefit to using a proper camera transform is that finding the depth buffer values becomes trivial- it's just the z coordinates of your pixel locations in camera space.

  0 · Agree Awesome
• Clipse Registered User regular

  July 2010 edited July 2010

  ArdentMarauder wrote: »

  Hey helpful PAers, know anything about perspective projection and Z-buffering? ... By hand?
  
  The background

  Spoiler:

  I'm currently working on a system which cannot use DirectX, openGL, or even the straight GDI, and yet must have some 3D rendering capability. Pretty much had to start from scratch. It has been a lot of fun, surprisingly. As for the 3D arm of the project, I had completely written a 2D raster operation library and polygon snap-in a couple months ago for another arm of the same project, so once the 3D matrix math was implemented (and efficient... "some assembly required"), it worked, with a few caveats that I can't seem to wrap my head around.

  
  Filling a polygon

  Spoiler:

  The Z-buffer was implemented right next to the underpinning code for filling a polygon. I'll get to an explanation of the Z-buffer problem in a minute, but my method for filling a polygon is important to that, so filling a polygon is here first. The fillPolygon call determines how many horizontal lines need to be painted to fill that polygon, and sets up an array of [Y lines to fill][horizontal left/right]. Even if it doesn't make sense, trust me, it works. With some assembly (move string of words, specifically), this wound up being the most efficient way I could get the job done.

  
  Moving to 3D

  Spoiler:

  Following the wiki article on the subject, I kept the generic object coordinates (x,y,z) between -1 and 1. This made identifying what is in the viewable range easy, and, using the centroid of any given polygon, I could determine a painting order. I should note here that I guaranteed that all points in a polygon were co-planar as the original (untransformed) vectors were entered into the object. This, however, wasn't perfect, and the next thing to implement was a Z-Buffer.

  
  The Z-Buffer

  Spoiler:

  Finally the crux of the problem, the Z-buffer. Again according to the wiki article on perspective projection, determining the pixel X and Y coordinates was easy, since the projected X and Y (pX, pY, pZ) are guaranteed to be between -1 and 1, and it worked like a charm.
  pixelX = (((pX/ pZ) * 0.5) + 0.5) * renderingWidth pixelY = (((pY/ pZ) * 0.5) + 0.5) * renderingHeight[/CODE] Z-buffering requires a distance (or depth) per pixel, however, and doing a matrix multiply for every pixel, every polygon seemed like quite a bit of overkill. Since I've already guaranteed that all of the points are co-planar, I figured that in my fillPolygon call I could easily determine the equation of the plane made up by the [B]projected[/B] points of the polygon, then use that to find the z values for each item. The first step was to convert the pixel values (pixelX, pixelY) back to world coordinates (pX, pY) or (projectedX, projectedY), as shown in the first 2 lines below. Calculating the z in world-coordinates was a simple matter of using the equation for the plane found earlier. Finally, taking the distance from there to the camera (cX, cY, cZ) is easy... [CODE] pX = ((pixelX / renderingWidth) - 0.5) * 2 pY = ((pixelY / renderingHeight) - 0.5) * 2 pZ = {Use equation for a plane from projected end points of polygon to determine pZ) pD = sqrt((cX-pX)^2 + (cY-pY)^2 + (cZ-pZ)^2)[/CODE] With that distance, I used a simple formula (from the [URL="http://en.wikipedia.org/wiki/Z-buffering"]z-buffer wiki article[/URL]) to scale all viewable Z depths (from sdNear {scaledDistNear} to sdFar {scaledDistFar}) from -1 to 1. [CODE]sD = ((sdFar + sdNear)/(sdFar - sdNear)) + (1 / pD) * ((-2 * sdFar * sdNear)/(sdFar - sdNear))[/CODE] That formula also worked as expected, and yielded values between -1 and 1. From there, implementing the Z-buffer was trivial, but, as is usually the case with this much code, there were problems. [/SPOILER] [SIZE="4"]The questions / tl;dr[/SIZE] For clarification, at this point the all of my math does work, and with the Z-buffer off, it shows the classic problems with simply setting a paint order (two objects intersecting through each other, etc). This means that my math for determining the pixelX, pixelY and the fillPolygon call itself are acting appropriately. The Z-buffer does function, but it has difficulty with a certain subset of camera theta and phi angles (azimuth and elevation). I have deduced that this has to do with my assessment of the pZ coordinate on a per pixel basis. All of that in mind... [LIST] [*]What needs to be done to the a perspective projected Z coordinate when the projection is complete? At the moment, I just leave it as it is, alongside it's projected x and y coordinate (in world coordinates), in order to get an equation of a plane from several of the projected points [*]Is it even mathematically correct to assume that if several (10 to 12) points are co-planar [B]before[/B] perspective projection, that they will [B]still[/B] be co-planar after? [*]Should I be using some other point as a reference for the final distance calculation? At the moment, I'm using the camera position (cX, cY, cZ) in world coordinates. [*]Anything else I should be looking out for? [/LIST][/QUOTE] Disclaimer: I haven't worked on graphics this low level for 7 or 8 years, so most of this is subject to a quick and dirty implementation and sanity check. [LIST] [*]The perspective projected z coordinate should, if I recall correctly, be used as the entry in the z-buffer. If it's negative, the point is behind the image plane and should not be displayed. Naturally depending on how the z-buffer is handled this may have to be converted to an integer, etc. This is much quicker than computing the distance directly, and allows you to linearly interpolate the z-buffer value across triangles. [*]I think in general an affine transformation does not necessarily preserve coplanarity of points. However, you shouldn't really be supporting non-triangle polygons at a low level anyways. Instead, if you want to support them at a high level, implement them with constructs like triangle strips. Done right it won't need anymore data, and will actually be quicker to render because you don't have to deal with all the awful stuff involved in filling an arbitrary polygon. [*]See the first bullet point. [*]Implement simple linear interpolation across triangles and a lot of stuff like basic shading and texture mapping is very easy to add on. [/LIST][CODE]pixelX = (((pX/ pZ) * 0.5) + 0.5) * renderingWidth
  pixelY = (((pY/ pZ) * 0.5) + 0.5) * renderingHeight[/CODE]
  
  Z-buffering requires a distance (or depth) per pixel, however, and doing a matrix multiply for every pixel, every polygon seemed like quite a bit of overkill. Since I've already guaranteed that all of the points are co-planar, I figured that in my fillPolygon call I could easily determine the equation of the plane made up by the projected points of the polygon, then use that to find the z values for each item. The first step was to convert the pixel values (pixelX, pixelY) back to world coordinates (pX, pY) or (projectedX, projectedY), as shown in the first 2 lines below. Calculating the z in world-coordinates was a simple matter of using the equation for the plane found earlier. Finally, taking the distance from there to the camera (cX, cY, cZ) is easy...
  pX = ((pixelX / renderingWidth) - 0.5) * 2 pY = ((pixelY / renderingHeight) - 0.5) * 2 pZ = {Use equation for a plane from projected end points of polygon to determine pZ) pD = sqrt((cX-pX)^2 + (cY-pY)^2 + (cZ-pZ)^2)[/CODE] With that distance, I used a simple formula (from the [URL="http://en.wikipedia.org/wiki/Z-buffering"]z-buffer wiki article[/URL]) to scale all viewable Z depths (from sdNear {scaledDistNear} to sdFar {scaledDistFar}) from -1 to 1. [CODE]sD = ((sdFar + sdNear)/(sdFar - sdNear)) + (1 / pD) * ((-2 * sdFar * sdNear)/(sdFar - sdNear))[/CODE] That formula also worked as expected, and yielded values between -1 and 1. From there, implementing the Z-buffer was trivial, but, as is usually the case with this much code, there were problems. [/SPOILER] [SIZE="4"]The questions / tl;dr[/SIZE] For clarification, at this point the all of my math does work, and with the Z-buffer off, it shows the classic problems with simply setting a paint order (two objects intersecting through each other, etc). This means that my math for determining the pixelX, pixelY and the fillPolygon call itself are acting appropriately. The Z-buffer does function, but it has difficulty with a certain subset of camera theta and phi angles (azimuth and elevation). I have deduced that this has to do with my assessment of the pZ coordinate on a per pixel basis. All of that in mind... [LIST] [*]What needs to be done to the a perspective projected Z coordinate when the projection is complete? At the moment, I just leave it as it is, alongside it's projected x and y coordinate (in world coordinates), in order to get an equation of a plane from several of the projected points [*]Is it even mathematically correct to assume that if several (10 to 12) points are co-planar [B]before[/B] perspective projection, that they will [B]still[/B] be co-planar after? [*]Should I be using some other point as a reference for the final distance calculation? At the moment, I'm using the camera position (cX, cY, cZ) in world coordinates. [*]Anything else I should be looking out for? [/LIST][/QUOTE] Disclaimer: I haven't worked on graphics this low level for 7 or 8 years, so most of this is subject to a quick and dirty implementation and sanity check. [LIST] [*]The perspective projected z coordinate should, if I recall correctly, be used as the entry in the z-buffer. If it's negative, the point is behind the image plane and should not be displayed. Naturally depending on how the z-buffer is handled this may have to be converted to an integer, etc. This is much quicker than computing the distance directly, and allows you to linearly interpolate the z-buffer value across triangles. [*]I think in general an affine transformation does not necessarily preserve coplanarity of points. However, you shouldn't really be supporting non-triangle polygons at a low level anyways. Instead, if you want to support them at a high level, implement them with constructs like triangle strips. Done right it won't need anymore data, and will actually be quicker to render because you don't have to deal with all the awful stuff involved in filling an arbitrary polygon. [*]See the first bullet point. [*]Implement simple linear interpolation across triangles and a lot of stuff like basic shading and texture mapping is very easy to add on. [/LIST][CODE]
  pX = ((pixelX / renderingWidth) - 0.5) * 2
  pY = ((pixelY / renderingHeight) - 0.5) * 2
  pZ = {Use equation for a plane from projected end points of polygon to determine pZ)
  pD = sqrt((cX-pX)^2 + (cY-pY)^2 + (cZ-pZ)^2)[/CODE]
  
  With that distance, I used a simple formula (from the z-buffer wiki article) to scale all viewable Z depths (from sdNear {scaledDistNear} to sdFar {scaledDistFar}) from -1 to 1.
  sD = ((sdFar + sdNear)/(sdFar - sdNear)) + (1 / pD) * ((-2 * sdFar * sdNear)/(sdFar - sdNear))[/CODE] That formula also worked as expected, and yielded values between -1 and 1. From there, implementing the Z-buffer was trivial, but, as is usually the case with this much code, there were problems. [/SPOILER] [SIZE="4"]The questions / tl;dr[/SIZE] For clarification, at this point the all of my math does work, and with the Z-buffer off, it shows the classic problems with simply setting a paint order (two objects intersecting through each other, etc). This means that my math for determining the pixelX, pixelY and the fillPolygon call itself are acting appropriately. The Z-buffer does function, but it has difficulty with a certain subset of camera theta and phi angles (azimuth and elevation). I have deduced that this has to do with my assessment of the pZ coordinate on a per pixel basis. All of that in mind... [LIST] [*]What needs to be done to the a perspective projected Z coordinate when the projection is complete? At the moment, I just leave it as it is, alongside it's projected x and y coordinate (in world coordinates), in order to get an equation of a plane from several of the projected points [*]Is it even mathematically correct to assume that if several (10 to 12) points are co-planar [B]before[/B] perspective projection, that they will [B]still[/B] be co-planar after? [*]Should I be using some other point as a reference for the final distance calculation? At the moment, I'm using the camera position (cX, cY, cZ) in world coordinates. [*]Anything else I should be looking out for? [/LIST][/QUOTE] Disclaimer: I haven't worked on graphics this low level for 7 or 8 years, so most of this is subject to a quick and dirty implementation and sanity check. [LIST] [*]The perspective projected z coordinate should, if I recall correctly, be used as the entry in the z-buffer. If it's negative, the point is behind the image plane and should not be displayed. Naturally depending on how the z-buffer is handled this may have to be converted to an integer, etc. This is much quicker than computing the distance directly, and allows you to linearly interpolate the z-buffer value across triangles. [*]I think in general an affine transformation does not necessarily preserve coplanarity of points. However, you shouldn't really be supporting non-triangle polygons at a low level anyways. Instead, if you want to support them at a high level, implement them with constructs like triangle strips. Done right it won't need anymore data, and will actually be quicker to render because you don't have to deal with all the awful stuff involved in filling an arbitrary polygon. [*]See the first bullet point. [*]Implement simple linear interpolation across triangles and a lot of stuff like basic shading and texture mapping is very easy to add on. [/LIST][CODE]sD = ((sdFar + sdNear)/(sdFar - sdNear)) + (1 / pD) * ((-2 * sdFar * sdNear)/(sdFar - sdNear))[/CODE]
  
  That formula also worked as expected, and yielded values between -1 and 1. From there, implementing the Z-buffer was trivial, but, as is usually the case with this much code, there were problems.

  
  The questions / tl;dr
  For clarification, at this point the all of my math does work, and with the Z-buffer off, it shows the classic problems with simply setting a paint order (two objects intersecting through each other, etc). This means that my math for determining the pixelX, pixelY and the fillPolygon call itself are acting appropriately.
  
  The Z-buffer does function, but it has difficulty with a certain subset of camera theta and phi angles (azimuth and elevation). I have deduced that this has to do with my assessment of the pZ coordinate on a per pixel basis. All of that in mind...
  

  • What needs to be done to the a perspective projected Z coordinate when the projection is complete? At the moment, I just leave it as it is, alongside it's projected x and y coordinate (in world coordinates), in order to get an equation of a plane from several of the projected points
  • Is it even mathematically correct to assume that if several (10 to 12) points are co-planar before perspective projection, that they will still be co-planar after?
  • Should I be using some other point as a reference for the final distance calculation? At the moment, I'm using the camera position (cX, cY, cZ) in world coordinates.
  • Anything else I should be looking out for?

  
  Disclaimer: I haven't worked on graphics this low level for 7 or 8 years, so most of this is subject to a quick and dirty implementation and sanity check.
  

  • The perspective projected z coordinate should, if I recall correctly, be used as the entry in the z-buffer. If it's negative, the point is behind the image plane and should not be displayed. Naturally depending on how the z-buffer is handled this may have to be converted to an integer, etc. This is much quicker than computing the distance directly, and allows you to linearly interpolate the z-buffer value across triangles.
  • I think in general an affine transformation does not necessarily preserve coplanarity of points. However, you shouldn't really be supporting non-triangle polygons at a low level anyways. Instead, if you want to support them at a high level, implement them with constructs like triangle strips. Done right it won't need anymore data, and will actually be quicker to render because you don't have to deal with all the awful stuff involved in filling an arbitrary polygon.
  • See the first bullet point.
  • Implement simple linear interpolation across triangles and a lot of stuff like basic shading and texture mapping is very easy to add on.

  0 · Agree Awesome
• ArdentMarauder Registered User

  July 2010 edited July 2010

  Clipse wrote: »

  • The perspective projected z coordinate should, if I recall correctly, be used as the entry in the z-buffer. If it's negative, the point is behind the image plane and should not be displayed. Naturally depending on how the z-buffer is handled this may have to be converted to an integer, etc. This is much quicker than computing the distance directly, and allows you to linearly interpolate the z-buffer value across triangles.
  • I think in general an affine transformation does not necessarily preserve coplanarity of points. However, you shouldn't really be supporting non-triangle polygons at a low level anyways. Instead, if you want to support them at a high level, implement them with constructs like triangle strips. Done right it won't need anymore data, and will actually be quicker to render because you don't have to deal with all the awful stuff involved in filling an arbitrary polygon.
  • See the first bullet point.
  • Implement simple linear interpolation across triangles and a lot of stuff like basic shading and texture mapping is very easy to add on.

  
  
  
  After checking all of the math on my previous implementation, you're absolutely right. Co-planarity before does not necessarily imply co-planarity after. So it's on to triangles!

  0 · Agree Awesome
• Disrupter Registered User regular

  July 2010 edited July 2010

  Man, this thread makes me wish I hadnt dropped my last math class at college because "i didnt need it"
  
  Cause...yeah...yeah I did fucking need it.

  

  0 · Agree Awesome
• ArdentMarauder Registered User

  July 2010 edited July 2010

  Due to your advice, I've gotten this arm of the project all wrapped up. Thanks!!

  0 · Agree Awesome