Overlapping tests in CAD applications

Bruno Autin

Mu Software

Introduction

In CAD applications, an object is represented by discrete cells. It is of primary importance that the cells do not overlap to avoid serious errors of calculations. This problem is addressed within the context of magnetic fields calculated in the Magnetica application created by L. Donadieu. One may distinguish two parts in a magnet: the sources of field: coils or permanent magnets, and the magnetic circuit made of the poles and return yoke. The magnetic circuit is generally meshed automatically using techniques which prevent any danger of overlap. The sources are modelized independently and it is the assembly of the two types of elements which presents risks of collision. In this paper, the detection of collision is purely algebraic and resorts to the determination, if it exists, of an intersection between areas in 2D or volumes in 3D. The Mathematica function at the core of that method is Reduce. The functions providing the algebraic volumes and the test of overlap are contained in Geometrica.

Algebraic volumes

A volume is the space limited by a closed surface. The surface may have a single equation if it represents a classical form. This is the case for a sphere centered at the origin and of radius r; its equation is then

(x^2)+(y^2)+(z^2)-(r^2)=0

The surface partitions the space into two regions where the left hand side of the surface equation is either positive or negative. The two regions of space are the outside (exterior) and the inside (interior) parts of the surface. The algebraic volume (not to be confused with the ordinary volume) is an inequality which characterizes all the points inside the sphere:

(x^2)+(y^2)+(z^2)-(r^2)<0

Very often, the external contour of the volume is a mixture of various portions of surfaces. For instance, the sphere may be limited by two horizontal planes

z=a

and

z=-a

with

a<r.

The space limited by those two planes is defined by the two inequalities

-a<z<a

which may be contracted into the single second degree inequality

(z^2)-(a^2)<0

The interior volume of the sphere limited by the wo planes is the intersection of two spaces. The operator of the intersection is the symbol And:

And[(x^2)+(y^2)+(z^2)-(r^2)<0,(z^2)-(a^2)<0]

Polyhedron

Polyhedra are limited by plane polygons. Their algebraic volume is thus the intersection of n subspaces limited by the planes of the faces, n being the number of faces. In order to fix the sign attributed to each sub-space, a reference point is chosen and known to be inside the polyhedron. Assuming that the polyhedron is convex, the center of gravity is inside the polyhedron.Let (a,b,c) be its coordinates. the plane of a face has an equation of the type

u x+v y+w z+h=0

If the sign of the quantity

u a+v b+w c+h

is, say, positive, then the algebraic volume to be kept for that face is

u x+v y+w z+h>0

and the procedure is repeated for each face. The function

PolyhedronVolume[p]

returns the algebraic volume of the polyhedron p in the form of a pure function of the three components of a point inside the polyhedron. A tetrahedron is taken as an example.

p=Tetrahedron[];
pv=PolyhedronVolume[p]

Cylinder

The cylinder is a basic shape of a conductor. More precisely, it is a cylinder of revolution limited by two planes perpendicular to the axis of revolution. It is generated by rotation of a segment s parallel to the axis δ. Here also, the determination of the subspaces limited by the planes is made using a reference point inside the cylinder. The function

CylinderVolume[s,δ]

has the same type of output as PolyhedronVolume. The example is given for a vertical cylinder of radius 1 and height 1.

s=Segment[CPoint[1,0,0],CPoint[1,0,1]];
d=CLine[CPlane[1,0,0,0],CPlane[0,1,0,0]];
cv=CylinderVolume[s,d]

Torus

The cylinder of revolution was a quadric and its algebraic voume involved a quadratic inequality. The torus is generated by the rotation of a circle about an axis and is a surface of degree 4. It is specified by the center and the radius of the generating circle and by the axis of rotation. When the axis of rotation is Oz, the center is at distance b from Oz and the radius is a, the equation of the torus is

((((x^2)+(y^2)+(z^2)-(a^2)-(b^2)))^2)-4(b^2)((a^2)-(z^2))=0

For the interior of the torus, the left hand side of the above equation is negative. The function which gives the algebraic volume is

TorusVolume[c,a,δ]

where c is the center of the generating circle, a its radius and δ the axis of rotation. The following example gives the algebraic volume of a torus whose axis is Oz, circle center is at distance 2 from Oz and circle radius is 1.

{p1,p2}=CPlane[{1,0},{0,1},0,0];
d=CLine[p1,p2];
ce=CPoint[0,2,0];
a=1;
tv=TorusVolume[ce,a,d]

The left hand side is a polynomial ordered according to the powers of the space variables using the Mathematica function Collect.

Overlap

As explained in the introduction, the overlap is the intersection of two algebraic volumes. If the intersection is empty, there is no overlap. The test of overlap for two volumes v and w is performed by the function

Overlap[v,w]

The function collects all the inequalities of the algebraic volumes in a single list and lets Reduce determining the intersection. If Reduce finds a set of compatible inequalities, Overlap returns True, otherwise, it returns False, as Reduce does. It is to be noted that in the context of research of collisions, one is not interested in the detailed intersection but only in its existence.

Tests involving a polyhedron

Two tetrahedra

th1=Tetrahedron[];
th2=Translate[th1,CPoint[2,0,0]];
{tv1,tv2}=PolyhedronVolume[{th1,th2}];
Overlap[tv1,tv2]

Tetrahedron and cylinder

s=Segment[CPoint[1,0,0],CPoint[1,0,1]];
d=CLine[CPlane[1,0,0,0],CPlane[0,1,0,0]];
cv=CylinderVolume[s,d];
Overlap[tv1,cv]

Tetrahedron and torus

{p1,p2}=CPlane[{1,0},{0,1},0,0];
d=CLine[p1,p2];
ce=CPoint[0,2,0];
a=1;
tov=TorusVolume[ce,a,d];

Overlap[tv1,tov]

?

The too long calculation time may be due to the computer ...

Tests involving a cylinder

Two cylinders

{s1,d1}=Translate[{s,d},CPoint[1,0,0]];
cv1=CylinderVolume[s1,d1];
Overlap[cv,cv1]

Cylinder and torus

This test would correspond to placing a coil around the pole of a cyclotron.

Overlap[cv,tov]

Two tori

Two intersecting coils would produce a short circuit!

{p1,p2}=CPlane[{1,1},{0,1},{1,0},0];
d2=CLine[p1,p2];
ce=CPoint[0,2,0];
tov1=TorusVolume[ce,1,d2];
Overlap[tov,tov1]

Conclusion

1. A conceptual approach of the problem of collisions in CAD, based on the intersection of algebraic volumes has been presented.
2. Actual implementation into a CAD program has still to be done.
3. Comparison with existing methods is still missing.