The core-collapse supernova phenomenon, one of the most explosive events in the Universe, presents a challenge to theoretical astrophysics. Of the large variety of forms of matter present in core-collapse supernova, we focus on the transitional region between homogeneous (uniform) and inhomogeneous (pasta) phases. A three-dimensional, finite temperature Skyrme-Hartree-Fock (3D-SHF)+BCS calculation yields, for the first time fully self-consistently, the critical density and temperature of both the onset of the pasta in inhomogeneous matter, consisting of neutron-rich heavy nuclei and a free neutron and electron gas, and its dissolution to a homogeneous neutron, proton, and electron liquid. We also identify density regions for different pasta formations between the two limits. We employ four different forms of the Skyrme interaction, SkM*, SLy4, NRAPR, and SQMC700 and find subtle variations in the low density and high density transitions into and out of the pasta phase. One new stable pasta shape has been identified, in addition to the classic ones, on the grid of densities and temperatures used in this work. Our results are critically compared to recent calculations of pasta formation in the quantum molecular dynamics approach and Thomas-Fermi and coexisting phase approximations to relativistic mean-field models.