 |
| Register | Login | |||||
 |
Main
| Memberlist
| Active users
| ACS
| Commons
| Calendar
| Online users Ranks | FAQ | Color Chart | Photo album | IRC Chat |
|
| | ||
|
| Register | Login | |||||
|
Main
| Memberlist
| Active users
| ACS
| Commons
| Calendar
| Online users Ranks | FAQ | Color Chart | Photo album | IRC Chat |
|
| | ||
| 0 user currently in Programming. | 3 guests |
| Acmlm's Board - I2 Archive - Programming - Nearest point on a plane to a point |
 |  |  |
| Add to favorites | "RSS" Feed | Next newer thread | Next older thread |
| User | Post | ||
|
Squash Monster New Age Retro Hippie Togateiru Fohku Kohgeki!! GRUNGE no HAMSTER otona bite Peace love and turnpike! Level: 40 Posts: 520/677 EXP: 430507 For next: 10802 Since: 03-15-04 From: Maryland (of the Country Between Canada and Mexico) Since last post: 5 hours Last activity: 5 hours |
| ||
| I have a polygon and a point, both in 3D space. I'm trying to find the closest point on that polygon to the point. Does anyone know how to do this? (If it helps at all, I have the polygons stored as arrays of x,y,z coords, nothing complicated.) (What follows is an explanation of why and of what I've tried so far.) I'm working on a game. There's a lightsource which determines the brightness of parts of objects. Originally, all of the objects were rectangular prisms, and I calculated the brightness that should be received at two points and made a gradient. Now, I've added the ability to draw 3D polygons, and I want to use this to optimise the drawing of the room -- I'll find all of the sides of rectangular prims (the rooms are made of an array of boxes) that create a single flat surface and turn that into a polygon, thus making there be less needed to draw (and this won't take much time becouse I can just run it once per room of the game). However, this optimisation, whenever I get around to it, will result in some large polygons, and the closest point to the light for each polygon will be likely to be near the center rather than the sides, which will create really ugly shading if I continue to just choose two points arbitrarily to shade. So, I decided the best way to shade the polygons would be to divide them into multiple parts centered around the closest point to the lightsource then shade each part seperately. This, unfortunately, requires me to find the closest point to the lightsource on that plane. Like most problems in this project, I tried to solve it first by doing the 2D version -- in this case, the closest point on a line. I eventually came up with a pair of equations that would intersect at the point: y = ((a-c)/b-d))x + f - ((a-c)/(b-d))e y = ((b-d)/(a-c))x + a - ((b-d)/(a-c))b Where (a,b) and (c,d) are points on a line and (e,f) is the point that we're trying to be near to. I was having trouble solving this set of equations, so I plugged it into my calculator, and got these (if I copied them off the screen correctly): x = (a^2*(b-d+e)-a*(b*(c+f)-c*(d-2*e)-d*f)-b^3+2*b^2*d+b*(c*f-d^2)+c*(c*e-d*f))/(a^2-2*a*c-b^2+2*b*d+c^2-d^2); y = (a^3-2*a^2*c-a*(b^2-b*(d+e)-c^2+d*e)+(b-d)*(b*(c-f)-c*e+d*f))/(a^2-2*a*c-b^2+2*b*d+c^2-d^2); This is a problem, becouse those are really bloody complicated, and my plan was to use this with the lines made by two different sets of points on the polygon, find the lines perpenducular through each of those that passes through the point that found, and then find the intersection of these last two lines. This is something that would have to run a good number of times each frame, so I'm afraid it's not only too complicated for me, but also for the computer. So, anyone have a better way to do this? |
|||
Dish Spiny Level: 38 Posts: 252/596 EXP: 355646 For next: 14801 Since: 03-15-04 From: Disch Since last post: 18 days Last activity: 18 days |
| ||
edit -- nm... I just read the rest of your post and realized I was way offbase in what you were asking  (edited by Disch on 01-27-05 05:25 PM) (edited by Disch on 01-27-05 05:29 PM) (edited by Disch on 01-27-05 05:32 PM) |
|||
|
Squash Monster New Age Retro Hippie Togateiru Fohku Kohgeki!! GRUNGE no HAMSTER otona bite Peace love and turnpike! Level: 40 Posts: 522/677 EXP: 430507 For next: 10802 Since: 03-15-04 From: Maryland (of the Country Between Canada and Mexico) Since last post: 5 hours Last activity: 5 hours |
| ||
| Um, yes, that would calculate the distance between two points. I don't see how I could use that to figure out what I'm looking for, unless I brute forced it, which is not an option. To clarify: |C | | |B *A | |D Given A, C, and D, I need to find point B, the point on line CD that is closest to A. (That's the 2D version, not the 3D one) EDIT: Heh, it's alright. Your version of the 3D Pythagorean Thearom was better than mine, so I at least learned something. It was sqrt(x^2 + y^2 + z^2), right? (edited by Squash Monster on 01-27-05 05:36 PM) (edited by Squash Monster on 01-27-05 05:37 PM) |
|||
|
Dish Spiny Level: 38 Posts: 254/596 EXP: 355646 For next: 14801 Since: 03-15-04 From: Disch Since last post: 18 days Last activity: 18 days |
| ||
| This is beyond my math training.. .but I've been having fun kind of thinking about it. I'm about out of time until I have to leave, so I'll spill my ideas just in case they're helpful. For any line slope... the perpendicular line's slope can be found by taking the negative reciprical. For example... a line with slope 1/2 would have a perpendicular line of slope -2. The perpendicular line would be the shortest distance between an outside point and any point on the line. So knowing 2 points on your line... you can easily find the slope... and given the slope, you can find the perpendicular slope... and given an outside point and a line slope with that point... as well as the slope of the target line.... you should be able to come up with an intersect point. I was brainstorming the formula for that but like I said I'm out of time. This would just be the 2D version... but if the logic can be found for the 2D version it could be found the same way for the 3D version. And yeah @ sqrt(x^2 + y^2 + z^2). |
|||
|
Squash Monster New Age Retro Hippie Togateiru Fohku Kohgeki!! GRUNGE no HAMSTER otona bite Peace love and turnpike! Level: 40 Posts: 523/677 EXP: 430507 For next: 10802 Since: 03-15-04 From: Maryland (of the Country Between Canada and Mexico) Since last post: 5 hours Last activity: 5 hours |
| ||
| That's almost exactly what I used, but you made me realise that I forgot to take the negative when I got the reciprical. Well, that changes everything. I wonder if it'll be much better though. And cool, that's much easier to calculate for the computer than the pythagoras of the pythagoras method. |
|||
|
Dish Spiny Level: 38 Posts: 255/596 EXP: 355646 For next: 14801 Since: 03-15-04 From: Disch Since last post: 18 days Last activity: 18 days |
| ||
| Bear with me... let me see if I can explain this. Okay... let's say our line AB goes from 4,2 to 8,4... and we have another point at 6,8 of which we're trying to find the closest point on line AB. given our 2 points, the slope of line AB is 1/2. Taking the negative reciprical of that slope, we have a slope of -2/1 for our perpendicular line CD's slope. From here, I tried to find the point on line AB which had the same X coord as our point C (6,8). Using the slope of 1/2 and either point... we can find that 6,3 is a point on line AB. Now our point at 6,3 and our point at 6,8 will gradually be moving closer together at fixed slopes. To find out where they intesect, we only need to find how far the line will move in the X direction... because both lines will be moving a total of 5 in the Y direction (6,8 and 6,3 are only 5 units apart on the Y). Here, we take the ratio of absolute Y movement in each slope... line CD (slope of -2) will be moving 2 units for every 1/2 unit moved by line AB. So the ratio would be 2:0.5.. or 4:1 Knowing this ratio, we only need to find the point on CD where the Y has moved 4/5ths of distance to our "equal X point" (line CD had point 6,8 and line AB had point 6,3... so the distance was 5) 4/5ths of 5 is 4... so from point 6,8... we need to find the point which is moved down the Y axis by 4 units... 8-4 is 4... so that'd be ?,4... and that's where lines AB and CD intersect. Given the slope of line CD being -2/1... we can find that point to be 8,4... which is the nearest intersecting point! Given that 2D method... the process could be repeated for a 3D method. Once you find the nearest point on the X / Y plane... you just need to find the point on the XY / Z plane. I hope that made sense... because I have to leave for school like now. XD edit - clarification error corrected (I really gotta go!!!) (edited by Disch on 01-27-05 07:28 PM) |
|||
|
sloat Level: 16 Posts: 33/85 EXP: 18044 For next: 2212 Since: 05-21-04 From: South Central Delaware Since last post: 19 days Last activity: 5 hours |
| ||
| Ok, i think i figured out a function using a bunch of fancy pants calc that i learned last semester. (Yes, math does come in handy). i was able to come up with a 9 parameter function that will give you a value for t in a parametric equation of a 3D line. if you want to see all the work, i used maple and i can send you the worksheet. you have three given points A, B, and P, where A and B are the end-points of the line and P is the point in space or wherever. Point C is the point we're trying to find. Assume that (Ax, Ay, Az) are the components of A, (Bx, By, Bz) are B, etc. it's a bit of a mess but... t = (Px*Bx-Px*Ax-Ax*Bx+Ax^2+Py*By-Py*Ay-Ay*By+Ay^2+Pz*Bz-Pz*Az-Az*Bz+Az^2)/(Bx^2-2*Ax*Bx+Ax^2+By^2-2*Ay*By+Ay^2+Bz^2-2*Az*Bz+Az^2); note that t should always be between 0 and 1. Cx = Ax + (Bx - Ax)*t; Cy = Ay + (By - Ay)*t; Cz = Az + (Bz - Az)*t; i think that will work. give it a try. |
|||
|
Squash Monster New Age Retro Hippie Togateiru Fohku Kohgeki!! GRUNGE no HAMSTER otona bite Peace love and turnpike! Level: 40 Posts: 524/677 EXP: 430507 For next: 10802 Since: 03-15-04 From: Maryland (of the Country Between Canada and Mexico) Since last post: 5 hours Last activity: 5 hours |
| ||
| Thank you both! I'll hopefully (and I mean that part) be able to try these solutions out some time tommorow. At the moment, I have a bunch of code to do before I have the stuff needed to test it out. I promise that I'll post some screenshots to show what your work helped with when I finish coding the geometry optimisation code and recoding the lighting system and re-integrating the code that makes the player tick. Thanks again. |
| Add to favorites | "RSS" Feed | Next newer thread | Next older thread |
| Acmlm's Board - I2 Archive - Programming - Nearest point on a plane to a point |
| | |
