Abstract We have developed new methods for determining the shapes (and albedo distributions), rotation periods, and pole directions (as well as other parameters, e.g., those of the scattering law) of asteroids from their lightcurves. This paper concentrates on shape determination. The recovered shapes are general and not based on modifications of any prior shape model. We produce test lightcurves of various nonconvex bodies with a fast ray-tracing algorithm. We show that the use of positive definite quantities effectively removes the apparent ill-posedness of the problem. Our methods can obtain convex hulls even for strongly nonconvex objects; major concavities can also be resolved.