Argudo, O.; Besora, I.; Brunet, P.; Creus, C.; Hermosilla, P.; Navazo, I.; Vinacua, A. Computer-Aided Design Vol. 79, p. 48-59 DOI: 10.1016/j.cad.2016.06.005 Data de publicació: 2016-10-01 Article en revista
The use of virtual prototypes and digital models containing thousands of individual objects is commonplace in complex industrial applications like the cooperative design of huge ships. Designers are interested in selecting and editing specific sets of objects during the interactive inspection sessions. This is however not supported by standard visualization systems for huge models. In this paper we discuss in detail the concept of rendering front in multiresolution trees, their properties and the algorithms that construct the hierarchy and efficiently render it, applied to very complex CAD models, so that the model structure and the identities of objects are preserved. We also propose an algorithm for the interactive inspection of huge models which uses a rendering budget and supports selection of individual objects and sets of objects, displacement of the selected objects and real-time collision detection during these displacements. Our solution–based on the analysis of several existing view-dependent visualization schemes–uses a Hybrid Multiresolution Tree that mixes layers of exact geometry, simplified models and impostors, together with a time-critical, view-dependent algorithm and a Constrained Front. The algorithm has been successfully tested in real industrial environments; the models involved are presented and discussed in the paper.
The final publication is available at Springer via http://dx.doi.org/10.1016/j.cad.2016.06.005
We propose a 3D mesh curving method that converts a straight-sided mesh to an optimal-quality curved high-order mesh that interpolates a CAD boundary representation. The main application of this method is the generation of discrete approximations of curved domains that are valid for simulation analysis with unstructured high-order methods. We devise the method as follows. First, the boundary of a straight-sided high-order mesh is curved to match the curves and surfaces of a CAD model. Second, the method minimizes the volume mesh distortion with respect to the coordinates of the inner nodes and the parametric coordinates of the curve and surface nodes. The proposed minimization features untangling capabilities and therefore, it repairs the invalid elements that may arise from the initial curving step. Compared with other mesh curving methods, the only goal of the proposed residual system is to minimize the volume mesh distortion. Furthermore, it is less constrained since the boundary nodes are free to slide on the CAD curves and surfaces. Hence, the proposed method is well suited to generate curved high-order meshes of optimal quality from CAD models that contain thin parts or high-curvature entities. To illustrate these capabilities, we generate several curved high-order meshes from CAD models with the implementation detailed in this work. Specifically, we detail a node-by-node non-linear iterative solver that minimizes the proposed objective function in a block Gauss-Seidel manner.
In geometric constraint solving, 2D well constrained geometric problems can be abstracted as Laman graphs. If the graph is tree decomposable, the constraint-based geometric problem can be solved by a Decomposition-Recombination planner based solver. In general decomposition and recombination steps can be completed only when steps on which they are dependent have already been completed. This fact naturally defines a hierarchy in the decomposition-recombination steps that traditional tree decomposition representations do not capture explicitly.; In this work we introduce h-graphs, a new representation for decompositions of tree decomposable Laman graphs, which captures dependence relations between different tree decomposition steps. We show how h-graphs help in efficiently computing parameter ranges for which solution instances to well constrained, tree decomposable geometric constraint problems with one degree of freedom can actually be constructed. (C) 2015 Elsevier Ltd. All rights reserved.
In geometric constraint solving, Decomposition Recombination solvers (DR-solvers) refer to a general solving approach where the problem is divided into a set of sub-problems, each sub-problem is recursively divided until reaching basic problems which are solved by a dedicated equational solver. Then the solution to the starting problem is computed by merging the solutions to the sub-problems.; Triangle- or tree-decomposition is one of the most widely used approaches in the decomposition step in DR-solvers. It may be seen as decomposing a graph into three subgraphs such that subgraphs pairwise share one graph vertex. Shared vertices are called hinges. Then a merging step places the geometry in each sub-problem with respect to the other two.; In this work we report on a new algorithm to decompose biconnected geometric constraint graphs by searching for hinges in fundamental circuits of a specific planar embedding of the constraint graph. We prove that the algorithm is correct. (C) 2014 Elsevier Ltd. All rights reserved.
We propose several measures to evaluate to which extent the shape of a given convex polygon is close to be regular, focusing on a range of characteristics of regularity: optimal ratio area–perimeter, equality of angles and edge lengths, regular fitting, angular and areal symmetry. We prove that our measures satisfy a number of reasonable requirements that guarantee them to be well defined, and provide efficient algorithms for their computation. All these algorithms have been implemented, and we provide experimental results on all the proposed measures.
In parametric design, changing values of parameters to get different solution instances to the problem
at hand is a paramount operation. One of the main issues when generating the solution instance for the
actual set of parameters is that the user does not know in general which is the set of parameter values
for which the parametric solution is feasible. Similarly, in constraint-based dynamic geometry, knowing
the set of critical points where construction feasibility changes would allow to avoid unexpected and
We consider parametric models in the Euclidean space with one internal degree of freedom. In this
scenario, in general, the set of values of the variant parameter for which the parametric model is realizable
and defines a valid shape is a set of intervals on the real line.
In this work we report on our experiments implementing the van der Meiden Approach to compute
the set of parameter values that bound intervals for which the parametric object is realizable. The
implementation is developed on top of a constructive, ruler-and-compass geometric constraint solver.
We formalize the underlying concepts and prove that our implementation is correct, that is, the approach
exactly computes all the feasible interval bounds.
Limitations of current 3D acquisition technology often lead to polygonal meshes exhibiting a number of geometrical and topological defects which prevent them from widespread use. In this paper we present
a new method for model repair which takes as input an arbitrary polygonal mesh and outputs a valid 2-manifold triangle mesh. Unlike previous work, our method allows users to quickly identify areas with potential topological errors and to choose how to fix them in a user-friendly manner. Key steps of our algorithm include the conversion of the input model into a set of voxels, the use of morphological operators to allow the user to modify the topology of the discrete model, and the conversion of the
corrected voxel set back into a 2-manifold triangle mesh. Our experiments demonstrate that the proposed algorithm is suitable for repairing meshes of a large class of shapes.
Dynamic geometry systems are tools for geometric visualization. They allow the user to define geometric
elements, establish relationships between them and explore the dynamic behavior of the remaining
geometric elements when one of them is moved. The main problem in dynamic geometry systems is
the ambiguity that arises from operations that lead to more than one possible solution. Most dynamic
geometry systems deal with this problem in such a way that the solution selection method leads to a
fixed dynamic behavior of the system. This is specially annoying when the behavior observed is not the
one the user intended.
In this work we propose a modular architecture for dynamic geometry systems built upon a set of
functional units which will allow us to apply some well-known results from the Geometric Constraint
Solving field. A functional unit called filter will provide the user with tools to unambiguously capture the
expected dynamic behavior of a given geometric problem.
Andujar, C.; Brunet, P.; Chica, A.; Navazo, I.; Rossignac, J.; Vinacua, A. Computer-Aided Design Vol. 37, num. 8, p. 847-857 DOI: 10.1016/j.cad.2004.09.013 Data de publicació: 2005-07 Article en revista
Since the publication of the original Marching Cubes algorithm, numerous variations have been proposed for guaranteeing water-tight constructions of triangulated approximations of isosurfaces. Most approaches divide the 3D space into cubes that each occupy the space between eight neighboring samples of a regular lattice. The portion of the isosurface inside a cube may be computed independently
of what happens in the other cubes, provided that the constructions for each pair of neighboring cubes agree along their common face. The portion of the isosurface associated with a cube may consist of one
or more connected components, which we call sheets. The topology and combinatorial complexity of the isosurface is influenced by three types of decisions made during its construction: (1) how to connect the four intersection points on each ambiguous face, (2) how to form interpolating sheets for cubes with more than one loop, and (3) how to triangulate each sheet. To determine topological properties, it is only relevant whether the samples are inside or outside the object, and not their precise value, if there is one. Previously reported techniques make these decisions based on local —per cube— criteria, often using precomputed look-up tables or simple construction rules. Instead, we propose global strategies for
optimizing several topological and combinatorial measures of the isosurfaces: triangle count, genus, and number of shells. We describe efficient implementations of these optimizations and the auxiliary data
structures developed to support them.
Level-of-detail occlusion culling is a novel approach to the management of occluders that can be easily integrated into most current visibility culling algorithms. The main contribution of this paper is an algorithm that automatically generates sets of densely overlapping boxes with enhanced occlusion properties from non-convex subsets. We call this method occluder synthesis because it is not sensitive to the way the objects are tesselated but to the space enclosed by them. The extension of this technique by allowing a bounded amount of image error is also discussed. We show that visibility computations can be based on a multiresolution model which provides several representations of these occluders with varying visibility accuracy. Our tests show that occlusion performance in tesselated scenes is improved severely even if no image-error is allowed.