R-Functions without Parasitic Singularities


Josip Dvornik
Faculty of Civil Engineering
Kaciceva 26
HR 10000 Zagreb, Croatia
e-mail: dvornik@grad.hr


Contents

Abstract

Conventional R-operations generate singularities in intersection points of boundaries of primitive domains. Some singularities are intrinsic and can not be removed. Others are induced by choosing inappropriate primitives, mathematical expressions and/or order of R-operations and they will be named ``parasitic singularities'' (PSg). In this paper, the R-functions without PSg will be referred to as ``Clean R-functions'' (CRF).

Some modifications to the R-function method and some ideas and strategies for CRF generation are introduced in this paper. A new extension to R-operations is the R3-disjunction of three arguments. Unfortunately, these ideas are not general, but specific to a particular classes of problems.

In conclusion, some questions about unexplored subtopics and suggestions for future research are given. The need to direct research towards generalisation is emphasized.

This paper has an apparently relaxed style, but it has a serious intention to draw reader's attention on some only partially solved problems. The purpose is to inspire somebody to find out a more general approach.

Keywords: R-function, R-operation, singularity



1. Introduction


An elegant way to generate smooth real functions on a compound domain is based on the R-operation method, invented by Ukrainian mathematician L. V. Rvachev [1,2]. The method has an analogy with Boolean algebra. R-functions in $ n$-dimensional Euclidean space are defined as continuous real functions that meet the following conditions:

1.1.
Function values inside the domain are positive
1.2.
Values on the boundary are equal to zero
1.3.
Values outside of the domain are negative

Positive values of R-function inside the domain correspond to TRUE values of the Boolean function, and negative values of R-function correspond to FALSE values of the Boolean function. At the boundary, the value of the R-function is equal to zero and the corresponding Boolean truth value is undefined.

R-primitives are smooth functions satisfying conditions 1.1, 1.2 and 1.3 - usually polynomials. For example $ F=1-x^2-y^2$ is a primitive R-function. Function values are positive inside the domain (unit circular disk with centre in the origin of the coordinate system), equal to zero at the boundary (circle), and negative outside the domain.

New R-functions can be generated from the ones already defined using R-operations. R-functions are not unique, because an infinite number of algebraic expressions corresponds to the same Boolean function. If $ p$ and $ q$ (Fig. 1a, 1b) are R-functions, the conventional R-operations are:


R-negation $ \neg p \stackrel{\mathrm{def}}{=}-p$ (Fig. 1c,h)
R-conjunction $ p \wedge q \stackrel{\mathrm{def}}{=}p + q - \sqrt{p^2+q^2+2 \alpha p q}$ (Fig. 1d,h)
R-disjunction $ p \vee q \stackrel{\mathrm{def}}{=}p +q + \sqrt{p^2+q^2+2 \alpha p q} $ (Fig. 1e)



Fig. 1a. $ p$

Fig. 1b. $ q$

Fig. 1c. $ \neg p$

Fig. 1d. $ p \wedge q$

Fig. 1e. $ p \vee q$

Fig. 1f. $ p \equiv q$

Fig. 1g. $ p \;\mathrm{Xor}\; q$

Fig. 1h. $ p\wedge (\neg q)$


$ \alpha$ is a real constant (or a smooth function) satisfying inequality: $ -1 <\alpha < 1$. In this paper $ \alpha=0$ is adopted as a default.

The common multiplication can be included as an additional R-operation corresponding to the Boolean equivalence (Fig. 1f) and, with opposite sign, to the exclusive disjunction (Fig. 1g).


R-equivalence $ p\equiv q \stackrel{\mathrm{def}}{=}p\cdot q$ (Fig. 1f)
R-exclusive disjunction $ p \;\rm {Xor}\; q \stackrel{\mathrm{def}}{=}-p\cdot q$ (Fig. 1g)


This is an well known and natural idea, although not often explicitly mentioned in connection with R-functions. From the Boolean point of view, this operation is redundant, although it is useful in applications because of the following advantages:

a)
It does not generate singularities
b)
For any number of arguments the result is symmetric (independent of the order of arguments).
c)
It generates much simpler algebraic expressions than the R-conjunction/disjunction.


These advantages are illustrated on examples.


Example 1: Two concentric circular disks $ S_1 = R_1^2-x^2-y^2$ and $ S_2 = R_2^2-x^2-y^2$ are given with $ R_1 > R_2$.

The circular ring (annulus) can be defined as:

a) R-conjunction of $ S_1$ and negation of $ S_2$:

$\displaystyle F_a$ $\displaystyle = S_1 \wedge (\neg S_2) = S_1 - S_2 - \sqrt{S_1^2+S_2^2}$    
  $\displaystyle =(R_1^2-x^2-y^2)-(R_2^2-x^2-y^2) -\sqrt{(R_1^2-x^2-y^2)^2+(R_2^2-x^2-y^2)^2}$    

b) negation of R-multiplication (R-Xor, i. e. R-exclusive disjunction):

$\displaystyle F_b = -S_1\cdot S_2 = -(R_1^2-x^2-y^2) (R_2^2-x^2-y^2) $


Example 2: Union of six equal circular disks in 2D with centres in vertices of regular hexagon $ S_1, S_2, S_3, S_4, S_5, S_6$ (Fig. 2a).

a) A conventional solution:

$\displaystyle F_a=(((((S_1\vee S_2)\vee S_3)\vee S_4)\vee S_5)\vee S_6) $

(or some permutation of arguments order and/or different arrangement of parentheses). In any case the result is asymmetrical and complicated.

b) A proposed solution with R-multiplications and only one square root (Fig. 2b,2c,2d):

$\displaystyle F_b=(S_1 \cdot S_3 \cdot S_5)\vee (S_2 \cdot S_4 \cdot S_6) $

Both solutions a) and b) have twelve intrinsic singular points (numbers 1-12 on Fig. 2a).



Fig. 2a.

Fig. 2b. $ S_7 = S_1\cdot S_3\cdot S_5$

Fig. 2c. $ S_8 = S_2\cdot S_4\cdot S_6 = \textrm{Mirr}(S_7)$
(Mirr(p) = mirror image of p)

Fig. 2d. $ F = S_7\vee S_8$


Problem 1: (A modification of example 2)

Union of five equal circular disks with centres in vertices of regular pentagon $ S_1, S_2, S_3, S_4, S_5$ (Fig. 3).

A complete symmetry of the domain must be preserved in the solution. Only one R-operation with square root (R-conjunction or R-disjunction) is allowed.

Hints:

A)
The strategy from the solution b) in example 2 does not work for an odd number of disks.
B)
Except from the given primitives, the auxiliary ones are recommended.



Fig. 3
Fig. 4


[My solutions for this and other problems are given in appendix. They are not unique and do not pretend to be optimal in any sense.]


Problem 2: (A modification of problem 1)

Union of five unequal disks with asymmetric arrangement (Fig. 4).

Again - only one square root is allowed.


Auxiliary primitives are aded in solutions proposed for problems 1 and 2: circular ring and circular disks. Here they play the role of ``patches'' for ``mending'' holes in improper solutions. Generally, the patches can assume a variety of shapes, but must be smooth (without singularities), they must completely cover the holes and lie inside the domain. (In 2D only point contacts of the patches with boundaries are allowed. In 3D - a contacts of the patches with boundaries along a curve are allowed etc.)



2. Singularities


The R-conjunction and R-disjunction generate singularities. In points where both arguments have zero values, a subexpression under the square root also has the zero value. These points are singular and lie on intersections of boundaries of primitives.

R-operations are recursive. An ``output'' of one R-operation can be an ``input'' for the next one. The singular points from the ``input'' are inherited in the ``output''. If the new R-operation contains a square root, and if the corresponding domains (defined by positive values of R-functions) partially overlap, then new singularities will be added. (Different types of singularities will not be distinguished.) After subsequent recursion steps, the final R-function can have inner singularities in the domain.

The singularities in the concave (re-entrant) corners of the boundary are intrinsic and can not be removed. (For analogy, in continuum mechanics concave corners are singular points of stress concentration.) Unnecessary singularities at the boundary and inside the domain can be named ``Parasitic Singularities'' (PSg), and must be avoided if possible. The R-functions without PSg will be referred to as ``clean R-functions'' (CRF). Singularities outside the final domain are irrelevant. Nevertheless, they should not be too close to the boundary, because the existence of a singular point disturbs the function in the neighbourhood. (The function is ``almost singular'' near singularities.)


Note: Continuity $ C^m$ for any finite $ m$ can be obtained by means of modified R-operations [2]:


R-conjunction $ F = (p + q - \sqrt{p^2+q^2}) (p^2+q^2)^{m/2}$
R-disjunction $ F = (p + q + \sqrt{p^2+q^2}) (p^2+q^2)^{m/2}$


If $ F$ is a R-function with singularities, a selective $ C^m$ continuity for a particular singular point with coordinates $ (x_0,y_0)$ can be obtained in a similar way:

$\displaystyle F_1 = F \bigl((x-x_0)^2+(y-y_0)^2\bigr)^{m/2} $

Only the full (infinite) continuity will be considered in the remainder of this paper.


Some ad hoc strategies for CRF generation will be presented. Unfortunately, they are neither general nor systematic, and they spoil the elegance of the R-function method. Nevertheless, many simple examples generate interesting problems.

It has not been proven that there are solutions (CRF) for all possible domain shapes. If such solutions do exist, in complicated examples they are difficult to obtain. In any case, the ad hoc strategy ``method'' is inefficient and unpractical for applications.

In addition to some ad hoc strategies, this paper also introduces two modified R-operations: R3-disjunction and R3-conjunction (symmetric extension of R-disjunction and R-conjunction to 3 arguments).

``Weak'' R-functions, which do not necessarily satisfy condition of negative values outside the domain, are also proposed.



3. Weak R-functions


Functions which strictly satisfy conditions 1.1 (positive values inside the domain) and 1.2 (zero values on boundary), but not strictly satisfy the condition 1.3 (positive values outside the domain are tolerated), can be named ``weak R-functions''. Positive areas outside domain can have contacts with boundaries only in corners (in 2D). Weak R-functions generally need less square roots and more multiplications and therefore they generate less singularities than the strong ones. A drawback is that the weak R-function itself does not carry sufficient information to distinguish whether some point lies inside or outside of the domain. Additional information is necessary, for example a separate Boolean function.

Example 3: A weak R-function without singularities (CRF) on any convex polygon can be generated as the product of linear functions (the R-equivalence of a half-planes) (Fig. 5):

$\displaystyle F = \prod_i (a_i x + b_i y + c_i) $



Fig. 5
Fig. 6


On all figures positive values outside of the domain are depicted light gray.


This expression can easily be expanded to convex polyhedra in 3D (and hyperpolyhedra in n dimensions).

(The conventional strong solution is the R-conjunction of the same half-planes.)


Example 4: 3/4 of a circular disk. The weak solution without PSg is presented (Fig. 6). Of course, the circle centre is an intrinsic singular point A.



4. Some strategies for avoiding parasitic singularities


Example 5: Union of three circular discs with unit radii. The centres lie on vertices of an unit equilateral triangle (Fig. 7a). Primitive R-functions are:

$\displaystyle S_1$ $\displaystyle = 1-(x-1/2)^2-(y+\sqrt{3}/6)^2$    
$\displaystyle S_2$ $\displaystyle = 1-x^2-(y-\sqrt{3}/3)^2$    
$\displaystyle S_3$ $\displaystyle = 1-(x+1/2)^2-(y+\sqrt{3}/6)^2$    


a) Conventional solution:

The conventional R-function for union of three primitives is $ F = (S_1 \vee S_2) \vee S_3$. This solution has two disadvantages:

1
Given domain has three axes of symmetry, but the R-function has only one.
2
An interior PSg exists. The first R-disjunction $ S_1 \vee S_2$ generates two singular points at the intersection of boundaries between $ S_1$ and $ S_2$ (Fig. 7b). Coordinates of these points are $ (1/2, -\sqrt{3}/2)$ and $ (1/2, \sqrt{3}/2)$. After the second R-disjunction these points remain singular (Fig. 7c). One of them falls inside the final domain. (Also two new intrinsic singularities are generated at the boundary.)

b) An symmetrised solution:

The symmetry can be restored by defining a new function as the sum of three conventional R-functions, different only in the order of arguments:

$\displaystyle F = (S_1 \vee S_2)\vee S_3 + (S_2 \vee S_3)\vee S_1 + (S_3 \vee S_1)\vee S_2 $

The new R-function has three PSg in symmetrical arrangement.



Fig. 7a.
Fig. 7b. $ S_4 = S_1\vee S_2$
A, B - singular

Fig. 7c. $ F = S_4\vee S_3$
A - PSg, B - intrinsic

Fig. 7d $ S_5 = S_1 \cdot S_2\cdot S_3$

Fig. 7e $ S_4$

c) CRF solution:

Both drawbacks are eliminated, by means of the fourth auxiliary primitive -a ``patch'' $ S_4$ - a disk with a centre in the centre of symmetry, and radius equal $ \sqrt{4/3}.$

The triply symmetric CRF solution is (Fig. 7d,e):

$\displaystyle F = (S_1\cdot S_2\cdot S_3)\vee S_4 $


Problem 3: Union of three balls with unit radii. The centres lie in vertices of a unit equilateral triangle. This is the 3D variant of the example 5.


Example 6: Union of unit circular disk and a quarter-plane (Fig. 8a).


a) Conventional solution with a PSg:

A infinite quarter-plane is defined as an intersection of two half-planes: $ S_1 = x; S_2 = y; S_4 = S_1\wedge S_2$. The unit circular disk with centre at origin: $ S_3 = 1-x^2-y^2$. The solution is $ F = S_3\vee S4$. This solution has an PSg at origin (Fig. 8a).

Fig. 8a. A - PSg


Fig. 8b. $ S_5 = S_1\cdot S_2$

Fig. 8c. $ S_6 = S_4 \wedge S_5$

Fig. 8d. $ F = S_6\vee S_3$ A, B - intrinsic

b) CRF solution:

The CRF is generated by defining an auxiliary primitive - a half-plane: $ S_4 = x+y-1;$ $ S_5 = S_1\cdot S_2$ (Fig. 8b); $ S_6 = S_4 \wedge S_5$ (Fig. 8c); $ F = S_3\vee S_6$ (Fig. 8d). In this case the auxiliary primitive is not a ``patch'' as in earlier examples and problems but a ``cut'' for the elimination of unwanted parts of original primitives.


Example 7: Two intersecting elliptical disks are given. A R-function has to be determined on the heart shape domain composed of parts of elliptical disks (Fig. 9a). This example can not be solved without auxiliary primitives, even if PSg points are tolerated. Namelly, the heart shape can not be obtained from elliptical disks if only Boolean operations, without other primitives, are allowed.

a) Solution with PSg:

Infinite part of the plane bounded with parabola is chosen as an auxiliary primitive. In the first step a subdomain - ``enlarged halfheart'' is generated by R-conjunction from the elliptic disk and parabolic area (Fig. 9b). The second subdomain is the mirror image of the first one. The purpose of the enlargement is overlapping of the two halves. The second step is the R-disjunction of these parts (Fig. 9a).

The R-disjunction generates two singular points in boundary corners. The intrinsic one is in the corner A while the second point, PSg, is in the convex corner B.


Fig. 9a. A - intrinsic
B - PSg

Fig. 9b. A, B - singular



Fig. 9c. A, C - singular
B - regular

Fig. 9d. A-intrinsic, B-regular
C-sigularity outside

b) CRF solution:

The auxiliary primitive is now a halfplane bounded by a straight line going through the point A, but ``missing'' the point B. The new function, i.e. the R-disjunction of the elliptic disk and the halfplane is generated in the first step (Fig. 9c). The second function is also generated as a mirror image of the first one. The complete solution - a weak R-function - is generated by multiplying these functions (Fig. 9d). This solution has singularities, but not PSg, as the singular points C lie outside the domain and can be tolerated.


Problem 4: ``Photo negative'' of the example 7. The domain is an infinite plane with a heart-shaped opening (hole).

Hints:

A)
Regularity conditions are opposite to the ones given in example 7. The corner A must be regular, while at the corner B there is an intrinsic singularity.
B)
Singular points in the opening (outside the domain) are allowed.



5. R-disjunction of 3 arguments


The example 4 and many others can be automatically solved by introducing a new R-operation - R-disjunction of 3 arguments:

$\displaystyle F$ $\displaystyle = \textrm{R3-disjunction}(S_1,S_2,S_3)$    
  $\displaystyle \stackrel{\mathrm{def}}{=}(S_1\cdot S_2\cdot S_3)\vee (S_1 + S_2 + S_3 + \sqrt{S_1^2 + S_2^2 +S_3^2})$    

The symbol $ \vee$ on the right hand side represents a conventional R-disjunction of two arguments. This operation generates singularities at boundary points where both subexpressions on the right hand side of the above expression are equal to zero:

  $\displaystyle (S_1\cdot S_2\cdot S_3)$ $\displaystyle = 0,$
  $\displaystyle (S_1 + S_2 + S_3 + \sqrt{S_1^2 + S_2^2 +S_3^2}) = 0$

Examples 8, 9, 10: R3-disjunction (Fig. 10a, 11a, 12a)

On (Fig. 10b, 11b, 12b) is $ \textrm{R3-Xor}(S_1,S_2,S_3) \stackrel{\mathrm{def}}{=}S_1\cdot S_2\cdot S_3$. The figure defined by positive values of the subexpression: $ (S_1 + S_2 + S_3 + \sqrt{S_1^2 + S_2^3 +S_3^2})$ (Fig. 10c, 11c, 12c), can be interpreted as an auxiliary primitive with the same role as $ S_4$ in example 5.



Fig. 10a
Fig. 10b
Fig. 10c

Fig. 11a
Fig. 11b
Fig. 11c

Fig. 12a
Fig. 12b
Fig. 12c


The correctness of analogy of the expression for $ \textrm{R3-disjunction}(S1,S2,S3)$ with Boolean disjunction is proven by means of the ``truth table''


(1) (2) (3) (4) (5) (6)
$ S_1$ $ S_2$ $ S_3$ $ S_1+S_2+S_3+\sqrt{S_1^2+S_2^2+S_3^2}$ $ S_1\cdot S_2\cdot S_3$ (4) $ \vee$ (5)
$ >$ $ >$ $ >$ $ >$ $ >$ $ >$
$ >$ $ >$ $ =$ $ >$ $ =$ $ >$
$ >$ $ >$ $ <$ $ >$ $ <$ $ >$
$ >$ $ =$ $ =$ $ >$ $ =$ $ >$
$ >$ $ =$ $ <$ $ >$ $ =$ $ >$
$ >$ $ <$ $ <$ ? $ >$ $ >$
$ =$ $ =$ $ =$ $ =$ $ =$ $ =$
$ =$ $ =$ $ <$ $ =$ $ =$ $ =$
$ =$ $ <$ $ <$ $ <$ $ =$ $ =$
$ <$ $ <$ $ <$ $ <$ $ <$ $ <$


($ >$ positive, $ <$ negative, $ =$ zero, ? non-unique sign)


The column 6 determined by the R-disjunction is identical with the corresponding Boolean disjunction, and therefore the expression is correct.

(There are probably more expressions with R3-disjunction properties, perhaps infinitely many.)

R3-conjunction (of 3 arguments) is defined from a Boolean transformation:

$\displaystyle \textrm{R3-conjunction}(S_1,S_2,S_3) \stackrel{\mathrm{def}}{=}\neg \textrm{R3-disjunction}(\neg S_1, \neg S_2, \neg S_3) $

Example 8: Union of four unit balls: $ S_1, S_2, S_3, S_4$. The centres are in vertices of the regular unit tetrahedron.

The first compound function is the R-Xor of four balls (product of four implicit expressions with opposite sign)and it leaves holes inside the domain at places of penetration of two balls: $ F_1 = -S_1\cdot S_2\cdot S_3\cdot S_4$. Every hole can be ``mended'' with a ball-shaped ``patch''. The number of patches is equal to the number of tetrahedron edges - i.e six: $ S_5,S_6,S_7,S_8,S_9,S_{10}$. The second auxiliary function is R-Xor of six patches, and it also leaves similar holes. (The R-disjunction of patches is not correct because it generates PSg-s.) $ F_2 = -S_5\cdot S_6\cdot S_7\cdot S_8\cdot S_9\cdot S_{10}$. The R-disjunction of the first and the auxiliary function $ F_1 \vee F_2$ is not an appropriate solution because it also leaves secondary holes. The secondary holes can be mended with a secondary patch - the maximal centrally placed ball completely inside the domain: $ S_{11}$. The complete solution is $ F = \textrm{R3-disjunction}(F_1, F_2, S_{11})$.



6. Final questions - sugestions for future research


The ad hoc strategies and model problems clearly have a value as a mental recreation exercise but for a more complicated real problems, this ``method'' becomes increasingly difficult and inefficient. More systematic methods for CRF generation should be developed for applications. However, prior to that some theoretical and practical problems must be resolved. The following are only some of the open issues:

1.
Is it always possible to find CRF on a compound domain?

2.
If the answer to the question 1. is ``no'', is it possible to decide in advance (from some properties of the problem) whether a particular problem can be solved in a first place?

3.
Is there a general algorithm for solving all solvable problems? Or at least all problems from a particular class?

4.
Is it possible to find simpler expressions for R-disjunction and R-conjunction of three arguments?

5.
Is it possible to find expressions for R-disjunction and R-conjunction of more than three arguments?

6.
The similar question for an indefinite number of arguments.

7.
The similar question for a compound R-operation composed of mixed R-conjunctions and R-disjunctions of three and more arguments.

8.
It has been mentioned that singularities outside the domain can be tolerated. Clearly there is a disadvantage if they are too close to boundaries of the domain because of the disturbance to the function in neighbourhood. But how can a safe distance be defined?



Bibliography


[1]
A. P. Filippov: Kolebanija deformiruemyh system (Vibrations of Deformable Systems), Mashinostroenie, Moskow, 1970

[2]
V. L. Rvachev: Metody algebry logiki v matematicheskoj fizike (Methods of Logic Algebras in Mathematical Physics), Naukova dumka, Kiev, 1974.

[3]
A. A. Pasko; V. V. Savchenko: Blending operations for the functionally based constructive geometry, Set-theoretic Solid Modeling: Techniques and Applications, CSG94 Conference Proceedings, Information Geometers, Winchester, UK, 1994, pp. 151-161

[4]
A. Pasko, V. Adzhiev, A. Sourin, V. Savchenko: Function Representation in Geometric Modeling: Concepts, Implementation and Applications, The Visual Computer, vol. 11, No. 8, 1995, pp. 429-446

[5]
K. T. Miura, A. A. Pasko, V. V. Savchenko: Parametric patches and volumes in function representation of geometric solids, CSG96 (Winchester, UK, 17-19 April 1996), Information Geometers, pp. 217-231

[6]
J. Dvornik, Generating Smooth Functions on Compound Domain by R-functions, (in Croatian), KoG, Scientific and Professional Information Journal of the Croatian Society for Constructive Geometry and Computer Graphics, No 1, Zagreb 1996, pp. 27-30



Appendix: Proposed solutions to problems 1 - 4


Solution of Problem 1:

The product of all given primitives $ S_1\cdot S_2\cdot S_3\cdot S_4\cdot S_5$ (Fig. 13a) is not a proper solution because it has holes (negative values inside the domain). These holes are mended by a ``patch'' shaped as a circular ring (Fig. 13b).



Fig. 13a
Fig. 13b


Solution to Problem 2:

The product of all primitives $ S_1\cdot S_2\cdot S_3\cdot S_4\cdot S_5$ also leaves holes similar to the ones in problem 1. But in the irregular case a substitution of one big patch with a few ``minipatches'' is easier - one circular disk for every hole (Fig.14).



Fig. 14


Solution to Problem 3:

The auxiliary disk - ``patch'' from example 5 - is now substituted with the R-disjunction of the self-intersecting torus and a ball. The torus has a central hole, and the ball is now a ``metapatch'' - the secondary ``patch'' for mending the remaining hole in the primary ``patch''. The R-disjunction generates singularity, but it is located at concave boundary points. This singularity is an intrinsic one for the final domain.


Solution to Problem 4:

a) Obviously, a R-negation of a) solution to example 7 is a simple PSg solution.

b) CRF solution. The auxiliary primitive is now a halfplane bounded by a straight line going through the point B but ``missing'' the point A. (Opposite than in example 7). In the first step, the new function i.e. the R-conjunction of elliptic disk and the halfplane is generated (Fig. 15a). The second function is a mirror image of the first one. The complete solution - a weak R-function is generated by multiplication of these functions. (Fig. 15b) This solution has singularities, but not PSg. The singular points in the hole (outside the domain) can be tolerated.


Fig. 15a
Fig. 15b