Premium
A Geometric Modeller Based on the Exact Octtree Representation of Polyhedra
Author(s) -
Navazo I.,
Avala D.,
Brunet P.
Publication year - 1986
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.1986.tb00278.x
Subject(s) - boundary representation , representation (politics) , polyhedron , computer science , modeller , geometric design , generalization , boolean data type , theoretical computer science , boundary (topology) , quadratic equation , class (philosophy) , algorithm , algebra over a field , mathematics , artificial intelligence , geometry , pure mathematics , mathematical analysis , biochemistry , chemistry , politics , political science , homology modeling , law , enzyme
Geometric Modellers based on a Boundary Representation scheme are well suited for display operations, but boolean operations require algorithms with quadratic complexity. Using a class of extended octtrees which is presented here, boolean operations become linear, while exact recomputation of the boundary model in the case of polyhedral objects is possible, and memory requirements are less than in classical octtree encodings. Some bounds on the memory savings are given and discussed. The DMI system, a Geometric Modeller based on a hybrid model Boundary ‐ Extended Octtrees, is presented, discussing the main operations and the interface between both models. Some modelling examples are shown. Finally, a generalization of the extended octtree encoding which allows the exact representation of objects limited by sculptured surfaces is presented.