Editing User:Hippieindamakin87

==Suryajith==
I am a final year undergraduate at Indian Institute of Technology,Kanpur, majoring in Mechanical engineering.

===Abstract===
I wish to implement a library/routine which computes a B-rep from the given CSG and further does a B-rep on B-rep evaluation generating a resultant (new) B-rep. The library evaluates the B-rep using lazy rational arithmetic such that the tolerances are taken care of with minimal error. Numerical errors are handled at an algorithm-independent level, which is an original exact arithmetic that performs only the necessary precise computations.The kernel runs on LiDIA and the data structures are handled by MAPC.(C++ library for manipulating algebraically defined points and curves)

===Proposal===
we assume rational polyhedral solids that are polyhedral solids which are represented by their boundaries, in which the coordinates of the vertices and the coefficients of the defining face plane equations are all available as rational numbers, regardless of the way in which these numbers are represented. A rational solid is always numerically consistent; for instance, each vertex-coordinate triple satisfies the plane equation of each incident face.

The B-rep is made up of two lists one for edges and one for faces.

To be valid, the B-rep must satisfy the following three conditions:

#Two distinct edges may neither overlap nor intersect at a point which is not a common endpoint.
#Two distinct faces may intersect only at edges that are listed in the B-rep.
#An edge must have an even number of flaps(piece of a face that hangs on either side of the edge) incident to it. Useless edges that have exactly two incident flaps (of the same maximal face) must be deleted from the B-rep.

====Kernel routines====

For some of the lower-level routines, the algorithms based on floating-point arithmetic are susceptible to failure. These include sign-evaluation of geometric predicates, orientation of points with respect to curves, and component classification. We refer to the resulting set of routines as kernel routines. The efficiency and reliability of the overall evaluation is governed by these routines.
Some of the efficient algorithms to implement the kernel routines use exact arithmetic.
Kernel routines that shall be used are Multivariate Sturm Sequences and Multipolynomial resultants.

*'''Multivariate Sturm Sequences'''
Sturm theorem is a procedure to evaluate distinct real roots of a polynomial. Given two polynomials(in our case the equations of the planes/curves),we can define another polynomial which is a combination of these polynomials(volume polynomial in the case of curves). Here the calculations can be done by approximating the resultant polynomial as a univariate sequence in one of the variables and then solving the sequence w.r.t the remaining variables.

*'''Comparision of algebraic points '''
A vertex in the patch domain is the common solution of two equations. This is usually an algebraic number which cannot exactly be represented using floating-point arithmetic. We represent each real algebraic number using a small rational rectangle. The rational rectangle is guaranteed to isolate each common root of the equations. To minimize the expensive computation, the bounding rectangles are narrowed down to small rectangles.

*'''Topological information of the algebraic curves '''
The intersection curve between two surfaces is typically a high degree algebraic curve which may have multiple real components. Topological resolution involves identifying critical points like turning points and singularities (self intersections and points where the tangent vanishes) and establishing a unique connectivity between them.

*''' Point classification'''
Classifying a component with respect to a solid amounts to classifying a point with respect to the trimmed domain. It is usually done using the ray shooting (like a point in a polygon problem).


====B-rep computation====
*For each pair of patches:
**Generate an intersection curve in the domains of the patches by substituting the parametric representation of each patch into the implicit representation of the other patch. Each intersection curve is represented as the zero set of a bivariate polynomial.
**Resolve the topology of the intersection curves (i.e. determine their structure in the patch domain).
**Intersect the intersection curve with the trimming boundary, determining the position of each intersection point in the domain of both patches (point inversion).
**Determine the curve correspondence, that is, how the individual portions of the algebraic plane curve in one patch domain relate to those in the other domain.
**Clip the intersection curves in each domain so that only the portions inside the trimmed regions of both patches are maintained.

*For each patch:
**Merge intersection curves from the patch/patch intersections to form patch/solid intersection curves.
**Partition the patch into different components based on the trimming curves.
**Classify partitions as to whether they are inside or outside of the other solid by classifying a point contained in each partition.
**Based on the Boolean operation, choose the correct components from each solid to build the ﬁnal solid, updating all topological information.

====Challenges of the B-rep evaluation====
'''Exact data structures and algorithms:'''
MAPC provides routines for handling polynomials (K_POLYs), algebraic plane curves (K_CURVEs), and both 1D points (K_POINT1Ds) and 2D points (K_POINT2Ds)
with algebraic coordinates. It includes routines for determining the topology of algebraic plane curves over a limited domain and intersecting two algebraic plane curves.

'''Point inversion:'''
A point in the domain of a patch P1 determines, via the parameterization, a point P in 3-space. If P is in the intersection of P1 with another patch P2 , it may be necessary to ﬁnd the inverse image of under the parameterization of P2 . This process is point inversion.

'''Curve correspondance:'''
Curve correspondence refers to ﬁnding the orientation of a curve in one patch domain relative to the same curve represented in the domain of another patch.

===Proposed approach===