back
to contents
|
|
Anshu Vaish 96050
Ashish Jaiswal 96071
Department of Mechanical Engineering
Indian Institute of Technology
- Kanpur : November 1999
back
to contents
__________________________________________________
METHODOLOGY
How do we go about solving the problem?
We would be working in the 3D cartesian
coordinate system where we have the three
mutually perpendicular axis namely
the x-y-z axis.
To begin with let us first define what are the inputs to the problem.
space : The space inputs comprise of the no. of bounding surfaces
and the
vertices. The bounding surface is defined by these vertices...but finally
represented as equation of the normal to the surface.
point : In the cartesian system a point is defined as (x,y,z).
Note: for each plane we would know
the vertices lying on the plane. The edges joining
these vertices together would enclose
the surface.
General procedure of the solution
1.inputs as stated
above
2.find max_x
3.extend the
ray parallel to x-axis from the point_in_question(x,y,z) to the
point(max_x+1,y,z)
4.find seperately
the intersection of each plane extended infinetely with the ray
obtained from 2.
5.the problem
is now reduced to a 2D PMC* problem where we have the set of
edges and a point(the point of intersection obtained from 3)
6.we count the
number of real intersections(i,e. the point lies inside the region
bounded by the vertices) and accordingly decide the status.
* here we need to consider the special cases
The complete algorithm
Input the following data
all vertices
no of faces
no of vertices on each face
the sequence of appearance on the face
test points(x0,y0,z0)
For each Face
(**)
With the help of the vertices,
we reduce the plane to the equation of the type Ax+By+Cz+D=0
Note: The
coefficients A,B,C and D can be calculated using any three points which
lie on the plane .
Equation of Ray
Ray along X-axis:
x=x0 + l*t (l:direction cosine)
-> In this case it is equal the length of ray.
y=y0
z=z0
Find the parameter t..
t=-[A*x0 +B*y0 +C*z0 +D]/(A*l)
* for existence of point of intersection 0 <=
t < 1 .
We have seven cases in general to
deal with
Case 1
A=0;B!=0,C=0 proj_type_2
Case 2
A=0;B=0;C!=0 proj_type_1
Case 3
A=0;B!=0;C!=0 proj_type_1
Case 4
A!=0;B=0;C=0 proj_type_3
Case 5
A!=0;B!=0;C=0 proj_type_3
Case 6
A!=0;B=0;C!=0 proj_type_3
Case 7
A!=0;B!=0;C!=0 proj_type_3
note A,B,C cannot be zero together.
(
we have type of projections
proj_type_1:projection
on xy plane.....z=0
proj_type_2:projection
on xz plane.....y=0
proj_type_3:projection
on yz plane.....x=0
we have two type of transformation
on planes chosen according to proj_type
trans_type_1:
here we apply 2DPMC on test point and vertices
trans_type_2: here we
apply 2D PMC on intersection point and vertices
)
When A=0(Cases 1,2,3)check if t=0,
if yes
apply trans_type_1
if case is inthe
point lies on the surface of the space;status=1***
if case is on the
point lies on the edge of the space;status=0***
else(t!=0)
**
When A!=0(Cases 4,5,6,7)check if
t=0,
if yes
apply trans_type_1
if case is in
the point lies on the surface of the space***
if case is on the
point lies on the edge of the space***
else(i,e. t!=0)
(****)
find point of intersection and apply trans_type_2
if the case is in
the count of intersections is increased by 1
if the case is on elevate
the ray i,e. increase the y-coordinate****
if the case is out
no change**
Special Case:
Ray passes through
the edge of a plane :
* find the normal of the plane
* find the normal to that edge in the plane of surface pointing inward.
* if the y-component of normal is
positive -> point lies inside
negative -> point lies outside
* if y-component is zero
check the same for x-component.
All surfaces have been taken care of.
(***)
if status=0 or 1 we know the result
is on the edge or surace respectively
else
if count of
intersections is even the point is outside
else inside
END
the code assumes that the reader
knows the algorithm for 2D PMC
back
to contents
_________________________________________________
SAMPLE
INPUT DATA:
4
-----> No of vertices
0 0 0 V1
1 0 0 V2
0 1 0 V3
0 0 1
V4
4 ----->
No of faces
1 3 ---->
Face no , No of vertices in the face
1 2 4 ---> vertex no
2 3
1 3 2
3 3
1 4 3
4 3
2 3 4
5 ------->
No of test Points
-0.5 0 0.5
Test Points
-1 0 0
-1 1 0
-0.5 0.5 0.5
0.1 0.6 0.1
SAMPLE IMAGES
Plane 1: OAC
Plane 2 : OBA
Plane 3 : OCB
Plane 4 : ABC
Colour code for ray: Blue -On Plane
Green-Inside Polyhedral
Black-Outside Polyhedral
CASE 1 P(-0.5
0 0.5)
*Ray through plane
CASE
2 P(-1 0 0)
*Ray along the edge
CASE 3 P(-1 1 0)
*Ray through the vertex
CASE 4 P(-0.5 0.5 0.5)
*Ray through the edge
CASE 5 P(0.1 0.6 0.1)
* Ray intersecting plane at a single point
back
to contents
__________________________________________________
LIMITATIONS
OF THE PROBLEM
We have restricted our code to solving
the membership status of a point in a space
bounded by planes.
This means that we would have only
planar bounding surfaces and any other shape of bounding surface is not
acceptable by the code.
Not exactaly a limitation but a
drawback of our code is that it expects us to enter separately the details
of each face. In case of a hole being present on the surface the code is
capable of providing correct results provided we input the face having
the hole correctly i,e. we should divide the surface into smaller
surfaces so that the combination of these new non- overlapping surfaces
is the original face minus the hole on the surface. This is better explained
thru the following example where we have a rectangular surface with a rectangular
hole. The surface in fig1. needs to be expressed as a combination of smaller
surfaces as in fig2 or fig3.
Limitations as far as the results
are concerned.
The only limitation in the code
has come up because of the defination of EPSILON, we have tested the code
for various solid shapes and with almost all possible critical points cases
and the code has shown satisfactory results.
We have been quite rigrous in our
attempt to find the failure point but have failed to get one.
The various results have been presented.
back
to contents
__________________________________________________
The Results
Test1
4
0 0 0
1 0 0
0 0 1
4
1 3
1 2 4
2 3
1 3 2
3 3
1 4 3
4 3
2 3 4
8
0.400000 0.4 0.1999999
0.4 0.4 2.0000001
0.2 0.2 0.4
0.4 0.4 0.2
0.2 0.2 0.599999
0.2 0.2 0.6000001
0 1 0
0 0 0.99999999999999
Point 1 ( 0.4 0.4 0.1999999
) ->Inside Point
2 (0.4 0.4 2.0000001) ->Outside
Point 3 (0.2 0. 2 0.4
) ->Inside
Point 4 (0.4 0.4 0.2) ->On the surface
Point 5 ( 0.2
0.2 0.599999 ) ->Inside
Point 6 (0.2 0.2 0.6.0000001) ->outside
Point
7 (0 1 0 ) ->On the vertex
Point 8 (0 0 0.99999999999999 ) -> Vertex
Test 2
6
1 0 0
0 1 0
-1 0 0
0 -1 0
0 0 1
0 0 0.5
8
1 3
1 2 5
2 3
2 3 5
3 3
3 4 5
4 3
4 1 5
5 3
1 2 6
6 3
2 3 5
7 3
3 4 6
8 3
4 1 6
8
0 0 0.499999
0 0 0.7777
0 -1.00000000000000000000011111
0.0000000000000001
-1.0000000000000000000001 0
0
0 0 0.8
0 0 .9
0.5 0 0.5
1.00000000000000001 0 0
Point 1 (0 0 0.499999 ) -> Outside
Point 2 (0 0 0.7777 ) ->Inside
Point 3 ( 0 -1.00000000000000000000011111 0.0000000000000001
) -> Vertex
Point 4 ( -1.0000000000000000000000001 0 0 )
-> Vertex
Point 5 ( 0 0 0.8 ) ->Inside
Point 6 (0 0 0.9) ->Inside
Point 7 (0 0 0.5)->On the edge
Point 8 (1.000000000000000000000000001 0 0 )->
On the vertex
Test 3
22
0.000000 1.000000
0.000000
0.000000 0.000000
0.000000
0.500000 0.000000
0.000000
0.475528 0.000000
0.154508
0.404508 0.000000
0.293893
0.293893 0.000000
0.404508
0.154508 0.000000
0.475528
0.000000 0.000000
0.500000
-0.154508 0.000000
0.475528
-0.293893 0.000000
0.404508
-0.404508 0.000000
0.293893
-0.475528 0.000000
0.154508
-0.500000 0.000000
0.000000
-0.475528 0.000000
-0.154508
-0.404508 0.000000
-0.293893
-0.293893 0.000000
-0.404508
-0.154508 0.000000
-0.475528
-0.000000 0.000000
-0.500000
0.154508 0.000000
-0.475528
0.293893 0.000000
-0.404508
0.404508 0.000000
-0.293893
0.475528 0.000000
-0.154508
40
1 3
3
4 1
2 3
4
3 2
3 3
4
5 1
4 3
5
4 2
5 3
5
6 1
6 3
6
5 2
7 3
6
7 1
8 3
7
6 2
9 3
7
8 1
10 3
8
7 2
11 3
8
9 1
12 3
9
8 2
13 3
9
10 1
14 3
10
9 2
15 3
10
11 1
16 3
11
10 2
17 3
11
12 1
18 3
12
11 2
19 3
12
13 1
20 3
13
12 2
21 3
13
14 1
22 3
14
13 2
23 3
14
15 1
24 3
15
14 2
25 3
15
16 1
26 3
16
15 2
27 3
16
17 1
28 3
17
16 2
29 3
17
18 1
30 3
18
17 2
31 3
18
19 1
32 3
19
18 2
33 3
19
20 1
34 3
20
19 2
35 3
20
21 1
36 3
21
20 2
37 3
21
22 1
38 3
22
21 2
39 3
22
3 1
40 3
3
22 2
9
0 0 0
0.0.1 0
0 0.2 0
0 1.0000000000001 0
-0.16 0.5 0
0 0.999999999 0
0 0.99999999 0
0 0.6 -0.16
-0.404508 0.000000
-0.293893
Point 1 ( 0 0 0) ->On vertex
Point 2 (0 0.1 0) -> Inside
Point 3 ( 0 0.2 0) ->Inside
Point 4 ( 0 1.000000000000001 0 ) ->On vertex
Point 5 ( -0.16 0.5 0) ->Inside
Point 6 ( 0 0 .999999999 0 )->vertex
Point 7 (0 0.99999999 0) ->Inside
Point 8 (0 0.6 - 0.16 )->Inside
back
to contents
__________________________________________________
Analysis of Results:End-note
As already stated and as is evident from the variety of test points the code for the polyhedral point membership classification is compitant of providing correct satisfactory results. We think that after having checked so rigrously if a failure turns up...it may be just a matter of chance. As a matter of fact we would appriciate if anyone could test the code and inform us of failure points, if any come up! We had limited complex solid geometry data and hence could come up with only three representative shapes.
Another major reason of our being confident about the correctness of the code is that it has already been brought into implementation by one of the project groups(Anshuman Rai and Sridhar Anand) trying to generate an octree.The results they have obtained verify the correctness.
To end we would just like to state
that as we have been emphasizing from the very begining the polyhedral
PMC forms the basic underlining for many CAD applications. The drawback
of inputing the data file for a solid body can be solved using the project
code compiled by Kuldip Narayan. Apart from this Line Membership Classification
etc are the next very immidiate applications of 3D PMC.
back
to contents