Efficient Max-Norm Distance Computation and Reliable Voxelization

Varadhan, Gokul; Krishnan, Shankar; Kim, Young J.; Diggavi, Suhas; Manocha, Dinesh

Efficient Max-Norm Distance Computation and Reliable Voxelization

Files

116-126.pdf (1.96 MB)

Date

2003

Authors

Varadhan, Gokul
Krishnan, Shankar
Kim, Young J.
Diggavi, Suhas
Manocha, Dinesh

Publisher

The Eurographics Association

Abstract

We present techniques to efficiently compute the distance under max-norm between a point and a wide class of geometric primitives. We formulate the distance computation as an optimization problem and use this framework to design efficient algorithms for convex polytopes, algebraic primitives and triangulated models. We extend them to handle large models using bounding volume hierarchies, and use rasterization hardware followed by local refinement for higher-order primitives. We use the max-norm distance computation algorithm to design a reliable voxel-intersection test to determine whether the surface of a primitive intersects a voxel.We use this test to perform reliable voxelization of solids and generate adaptive distance fields that provides a Hausdorff distance guarantee between the boundary of the original primitives and the reconstructed surface.

        @inproceedings{:10.2312/SGP/SGP03/116-126
,
booktitle = {Eurographics Symposium on Geometry Processing
},
editor = {Leif Kobbelt and Peter Schroeder and Hugues Hoppe
},
title = {{Efficient Max-Norm Distance Computation and Reliable Voxelization
}},
author = {Varadhan, Gokul and 
Krishnan, Shankar and 
Kim, Young J. and 
Diggavi, Suhas and 
Manocha, Dinesh
},
year = {2003
},
publisher = {The Eurographics Association
},
ISSN = {1727-8384
},
ISBN = {3-905673-06-1
},
DOI = {/10.2312/SGP/SGP03/116-126
}
}