Archived

This topic is now archived and is closed to further replies.

Orkin Man

Need a couple algorithms...

Recommended Posts

Orkin Man    122
I need I couple of algorithms for the project I''m working on. 1. I need an algorithm that will tell me weither or not a polygon (not a triangle, a polygon) lies within, weither partially or totally, an area defined by a list of planes. 2. I need an algorithm that will tell me weither or not any part of a polygon is within a specified distance of a point. Thanks in advance for any help!

Share this post


Link to post
Share on other sites
Toom    122
The first problem is exactly what frustum culling is all about, so perhaps my little article on the topic may be of some use.

Basically you need to calculate the distance of each point from each plane. The sign tells you which side of the plane it's on.

Given the four numbers that define a plane (A, B, C, and D) you can calculate the distance of a point P from that plane like this:


distance = A * Px + B * Py + C * Pz + D


So by testing all of the points in your polygon against all the plane equations you should be able to determine if it's entirely within or partially within.

The second problem is easier I think. Here's some pseudo code (untested, making it up as I go along here):


Calculate the distance if the point from the plane of the polygon
If it's within your range then return TRUE
For each vertex that defines the polygon:
Calculate the distance of the vertex from the point
If it's within your range then return TRUE
Return FALSE


The distance between the point and a vertex is calculated like this:


distance = sqrt( (Vx - Px)^2 + (Vy - Py)^2 + (Vz - Pz)^2 )


However sqrt() is slow, so leave it out and compare the result to RANGE^2 instead of RANGE. Should have the same result.

Toom

Edited by - toom on January 25, 2001 1:47:34 PM

Share this post


Link to post
Share on other sites
Osku    122
Toom : I''m not sure if your second answer is accurate. The point can be an arbitrary distance away from the polygon even if it is near the plane of the polygon, and the point could be even within the polygon even if it isn''t near a vertex. I not sure how to calculate this but I don''t think your answer was the right one.

Regards, Osku


Share this post


Link to post
Share on other sites
Toom    122
Doh. You are correct of course.

Perhaps something like this:


Calculate the distance of the point from the plane of the polygon
If it''s outside your range return FALSE
Calculate the position on the plane that is perpendicular to the point
If this new point is within the polygon return TRUE
For each vertex that defines the polygon:
Calculate the distance^2 of the point from the vertex
If it''s within your range^2 return TRUE
Return FALSE


Toom

Share this post


Link to post
Share on other sites